1. O que é um problema

• A IA serve para resolver problemas, imitando, de certa forma a inteligência dos seres -vivos.
• O desejo de construir máquinas ‘resolvedoras’ de problemas impõe a compreensão da natureza íntima dos mesmos.
• Antes de solucionar um problema:
• Quais são os dados?
• Quais são as soluções possíveis?
• O que caracteriza uma solução satisfatória?
• Definição:

• Exemplos
• Diagnóstico Médico: dados disponíveis, tal como exames.
• Conjunto de doenças possíveis
• A condição que caracteriza uma solução satisfatória consiste em encontrar o par (dados, doença) do diagnóstico desejado.
• Achar a solução do problema da busca das raízes de um polinômio com coeficientes reais.
• Um problema pode ser representado matematicamente por uma função. Resolver o problema será então encontrar um modo de implementar esta função ou de aproximá-la com o conhecimento que se dispõe.

1.1. Modos de Definir uma Função

• Por enumeração exaustiva
• Fornece-se todos os conjuntos de pares, dado, resultado.
• Só se aplica no caso em que o conjunto de dados é finito.
• De forma declarativa
• Dar propriedades que devem ser satisfeitas pela solução do problema.
• Da mesma forma que um conjunto pode ser definido por uma propriedade, uma função pode ser definida da mesma maneira.
• Por um programa
• Um programa de computador define a correspondência entre dados e resultados, podendo ser considerado como um modo de definir um problema.
• Um problema definido por um programa poderá ou não chegar à solução.
• Por exemplos
• Conhece-se apenas a definição do problema para um subconjunto dos dados possíveis e este conhecimento pode ser de qualquer uma das formas anteriores.
• Deseja-se conhecer os elementos do conjunto de respostas admissíveis mesmo para dados que não estão incluídos na definição da função.

1.2. Características

• Não existe um único método de resolução para todos os problemas.
• São conhecidos os passos para achar a solução?

• Jogo do 8
• Identificação de assinaturas

• O problema é decomponível?

• Os passos para as soluções podem ser desfeitos?

• O Universo é previsível?
• É possível planejar uma seqüência de passos e o estado resultante será sempre o mesmo.
• Existem problemas onde um fator de chance está envolvido, como por exemplo, no jogo de cartas.

• Uma boa solução é relativa ou absoluta?

• O conhecimento disponível é consistente?

• O estado A é verdadeiro.
• O estado C é verdadeiro.
• Se C, então D. Se D, então A ou-exclusivo C.

1.3. Estratégias

• Duas Abordagens
• Se a solução do problema for uma função, se for possível implementar esta função, tem-se a solução do problema. Este fato leva, na abordagem simbólica à PROGRAMAÇÃO FUNCIONAL (estática).
• A pesquisa da solução pode ser vista como uma pesquisa dentro do espaço de possíveis soluções (generate and test) (dinâmica).
• Utilizando um método para aproximar a função, solução do problema.
• Utilizar um método de busca em que por passos sucessivos se aproxima da solução, usando, algumas vezes passos sem grande justificativa teórica.

1.4. Problemas clássicos

• Missionários e Canibais
• Torres de Hanói
• O Problema do Caixeiro Viajante
• Jogo de xadrez
• Jogo do 8

• Uma teoria em IA consiste na especificação do conhecimento necessário a uma capacidade cognitiva.
• Capacidade cognitiva: solução de problemas, uso de linguagem, tomada de decisões, percepção, etc. Se o conhecimento é central para a cognição, então a inferência é o principal mecanismo e a capacidade cognitiva deve ter:

• uma base de conhecimento
• um motor de inferência

• Motor de Inferência: Mecanismo que gera novos conhecimentos
• Base de Conhecimento: Contém a informação específica sobre o domínio e será tão complexa quanto a capacidade cognitiva a ser simulada.
• Conceitualização: tarefa do projetista do sistema que consiste em escolher uma estrutura matemática, formada por objetos, funções e relações, que descreva o estado das coisas no mundo Esta posição ignora a profunda questão filosófica envolvida no entendimento de um conceito (lembre-se da Sala Chinesa).
• Os seres humanos, desde o nascimento vão acumulando conhecimentos que lhes permitirão agir de modo a mostrar que são seres inteligentes.
• Este processo pode ser descrito como compreendendo os seguintes passos:

• P1 - ocorre o estímulo sensorial.
• P2 - ocorre a retenção do estímulo por pouco tempo.
• P3 - a informação é trabalhada pela memória de trabalho.
• P4 - ocorre a resposta.
• P5 - a informação é registrada ou não na memória de longa duração.

• As pessoas não captam todo o conhecimento que a realidade do mundo lhe proporciona.
• Pessoas diferentes, perante a mesma realidade captam e entendem coisas diferentes.
• A manipulação do conhecimento exige, antes, formas de representação.

2.1. CAPACIDADES COGNITIVAS

• Capacidade de Inferência: a capacidade, mais óbvia que pode ser baseada em uma estrutura adequada de conceitos. A estrutura deve ser suficientemente rica para evitar falhas evidentes de entendimento.

• Percepção: a capacidade de perceber e identificar objetos no mundo real é decorrência do fato de o agente que realiza a percepção possuir conceitos relacionados com estes objetos.
• Crescimento do Conhecimento: como o conhecimento é representado através da forma de conceitos, ele pode ser pensado como uma teoria e, neste caso, o aprendizado é simplesmente um avanço conceitual desta teoria.
• Degeneração do Conhecimento: pode ser explicado pelo aparecimento de defeitos na estrutura conceitual do agente.
• Exemplo: Para interpretar um texto, é necessário:

• Extrair conceitos: objetos, pessoas, imagens.
• Relacionar estes conceitos: ação-agente, causa-efeito.
• Fazer inferências, deduções e induções.

• Para um computador isto é muito difícil devido ao vasto número de conceitos, relações, regras, necessários à interpretação de textos genéricos.
• A restrição do domínio reduz a complexidade do problema.

É importante distinguir entre forma e conteúdo do conhecimento

• Exemplo: Um texto que usa a linguagem natural como recurso de representação pode ter, também seu conteúdo sintetizado através de outros recursos, como por exemplo, a lógica de predicados.
• O conteúdo é o mesmo. As formas de representação diferentes facilitam a manipulação por diferentes agentes (computador, ser humano).

3.1. Conceitos Básicos

• Base de Conhecimento: o repositório de procedimentos, heurísticas, dados, que compõe o conhecimento. Assemelha-se a um banco de dados no sentido de que exige manutenção (atualizações, inserções, deleção), mas o acesso a uma informação é mais elaborado.
• Engenheiro do Conhecimento: o profissional de ciência da computação responsável pela implantação da base de conhecimento. É um profissional com sólidos conhecimentos em técnicas de IA.
• Especialista do Domínio: é um profissional altamente capacitado no domínio para o qual estamos desenvolvendo a aplicação. Supre o engenheiro do conhecimento com os procedimentos (formais e heurísticas) necessários à construção da base de conhecimento.
• Inferência: processo pelo qual deduzimos novas informações a partir das existentes na base de conhecimento. Se a informação não estiver explicitamente na base, a inferência é necessária. Existe um compromisso entre a quantidade de conhecimento armazenada explicitamente na base de conhecimento e a atividade de inferência.

• Inferência Dedutiva: a partir de elementos de conhecimento representados em forma lógica, utiliza-se uma regra de inferência válida para inferir um novo elemento. Algumas regras de inferência utilizadas em lógica são: Modus Ponens, Modus Tollens, Silogismo Hipotético, Especialização, Generalização e Resolução.
• Inferência Abdutiva: a partir de um conhecimento geral da forma "x P(x) ® Q(x) e tendo por objetivo provar Q(a), toma-se por hipótese que a razão pela qual Q(a) se verifica é a validade de P(a).
• Inferência Indutiva: a partir de fatos experimentais que comprovam que a cada vez que a validade de P(a) é verificada, verifica-se a validade de Q(a) (mas não o contrário), para diferentes elementos a, pode-se inferir por indução que é válido.
• Máquina de Inferência: parte da base de conhecimento que abriga os mecanismos (algoritmos e heurísticas) que processam a inferência. Via de regra, tais mecanismos são independentes do domínio (o que não ocorre com o restante da base de conhecimento).
• Tomando-se como referência os métodos fracos, temos:
• a base de conhecimento armazena o estado inicial, o estado final, um procedimento de teste para determinar se um estado é final, e uma seqüência de transformações de estado (árvore de busca);
• a máquina de inferência é um método fraco (por exemplo A*) que utiliza e atualiza a base de conhecimento.
• Inferência Orientada por Dados: é um processo em que a informação contida na base de conhecimento é combinada com o intuito de se gerar novas informações.
• Inferência Orientada por Objetivos: testa-se a veracidade de uma hipótese.
• Inferência Sob Incerteza

3.2. Características de representações profícuas (Winston)

• Boas representações explicitam as coisas importantes.
• Revelam restrições naturais, facilitando algumas classes de computações.
• São completas, podendo dizer tudo o que devem ser capazes de dizer.
• São concisas, necessitando apenas de recursos mínimos e sendo ao mesmo tempo ainda eficientes quando efetuam inferências.
• Podem ser rapidamente recuperadas e armazenadas.
• Informações raramente usadas são abordadas e recuperadas apenas quando necessárias.
• Permitem uma aquisição fácil e são legíveis pelo especialista, quando for o caso.
• Permitem a aplicação dos mecanismos de inferência necessários.
• Consistência: Não armazena informações conflitantes.
• Completude: Não apresenta lacunas no conhecimento armazenado. Todo o conhecimento necessário para a resolução do problema está explicitamente armazenado ou pode ser determinado via inferência.
• Coerência: Não existem ilhas isoladas de conhecimento; não se relacionam com o restante do conhecimento armazenado.
• Redundância: A mesma unidade de conhecimento é armazenada de forma duplicada.

3.3. Formas de representação do conhecimento
3.3.1.1. Sistemas ou Regras de Produção

• Concebidas por Emil Post (1943) quando demonstrou que um procedimento computável pode ser modelado como um sistema de produção.
• Muito utilizada nas décadas de 50 e 60. É o formalismo mais difundido de representação de conhecimento.
• Consiste em transformar o problema em um grafo de estados. Este grafo deve possuir um estado inicial e deve-se ter uma forma de identificar um estado final quando algum for atingido.
• Um Sistema de Produção é definido como uma tupla SP = <R, E, e₀, F>, onde R é um conjunto de regras, E é um conjunto de estados, e₀ é o estado inicial e F é o conjunto de estados finais.
• As regras são constituídas de um lado esquerdo (um padrão), que determina a que estados a regra pode ser aplicada, e um lado direito, que descreve a transformação a ser aplicada aos estados que se encaixam no padrão, originando novos estados.
• O padrão p consiste de um predicado que mapeia o conjunto de estados do problema em valores booleanos (verdadeiro ou falso). O padrão define como verdadeiros os estados aos quais a regra é aplicável. A aplicação da regra consiste em aplicar a operação p a um destes estados, gerado um novo estado.
• São estruturas do tipo SE <condição> ENTÃO <ação> onde:

• <condição> estabelece um teste cujo resultado depende do estado atual da base de conhecimento. Tipicamente o teste verifica a presença ou não de certas informações na base.
• <ação> altera o estado atual da base de conhecimento, adicionando, modificando ou removendo unidades de conhecimento presentes na base. Pode acarretar também em efeitos externos à base, como por exemplo, a escrita de uma mensagem no vídeo.

• Exemplo1: Problema dos dois baldes de água.

• Enunciado do problema: Você recebe dois baldes de água, um de quatro litros e outro de três litros. Nenhum deles possui qualquer marcação de medida. Há uma torneira que pode ser utilizada para encher os baldes de água. Como colocar exatamente dois litros d'água dentro do balde de quatro litros? [RIC 94]
• O espaço de estados para este problema pode ser modelado como o conjunto de pares ordenados de números naturais (x,y) tal que x = 0, 1, 2, 3 ou 4 e y = 0, 1, 2 ou 3, onde x representa a quantidade de água no balde de 4 litros, e y representa a quantidade de água no balde de 3 litros.
• O estado inicial do problema é o estado no qual ambos os baldes estão vazios: (0,0), e o conjunto de estados finais é constituído por todos os estados onde a quantidade de água no primeiro balde é 2, ou seja: (2,n), onde n = 0, 1, 2 ou 3.
• Possível conjunto de regras de produção para o problema:

• Veja aqui a Resolução do Exemplo1

• EXEMPLO2: Problema dos Canibais e Missionários
• Enunciado do problema: Três canibais e três missionários estão viajando juntos e eles precisam atravessar um rio. Todos os seis devem passar para o outro lado. Entretanto, o único meio de atravessar o rio é uma canoa que só comporta, no máximo, duas pessoas. Aí está outra dificuldade: em nenhum momento, em nenhuma das margens o número de canibais pode ser maior do que o número de missionários, porque isso poderia ser perigoso para os missionários. Como eles podem fazer para atravessar o rio? [CHA 77]
• O estado inicial é (3,3,0,0,0) e o único estado final é (0,0,3,3,1).
• As regras são todas de movimentação de no máximo duas pessoas de uma margem à outra do rio. Assim, pode-se movimentar dois canibais, dois missionários, um canibal e um missionário, apenas um canibal ou apenas um missionário, tanto da margem original para a margem oposta quanto vice-versa. Tem-se, assim, 10 regras possíveis, das quais uma é mostrada a seguir.
• Para transportar dois missionários da margem original para a margem oposta:

• As restrições do problema estão expressas nas condições das regras: m_{1 ³}2 exige que existam pelo menos dois missionários na margem original para que possam ser transportados. (m₁ – 2 ³ c₁ ou m₁- 2 = 0) exige que o númerode missionários que permanecerão na margem original após o transporte seja maior ou igual ao número de canibais na mesma margem ou igual a zero. Finalmente, (m₂ + 2 ³ c₂) exige que o número de missionários na margem oposta após a travessia seja maior ou igual ao número de canibais nesta margem.

• As soluções apresentadas não são as únicas possíveis. Além disso, não foi mostrado como a solução foi encontrada. Este é exatamente o ponto onde entram os algoritmos de busca no espaço de estados. A modelagem de um problema como um sistema de produção consiste apenas em definir o espaço de estados e as regras.
• VANTAGENS
• MODULARIDADE: podem ser consideradas como peças independentes. Novas regras podem ser acrescentadas ao conjunto já existente sem maiores preocupações.
• NATURALIDADE: pode ser considerada uma forma natural de pensar a solução de problemas.
• UNIFORMIDADE: todas as regras são escritas seguindo oo mesmo padrão. Permite que pessoas não familiarizadas com o sistema possam também analisar o seu conteúdo.
• DESVANTAGENS
• OPACIDADE: é difícil verificar a completeza destes sistemas, bem como verificar os possíveis fluxos de processamento.
• INEFICIÊNCIA: resulta particularmente do número de regras a combinar e também do esforço de matching necessário ao suporte de execução das regras. "Matching" entende-se como a verificação das regras que se aplicam ao estado do problema, bem como a verificação de que regras antecedem ou sucedem outras regras. Pode-se contornar este problema investindo na ordenação apropriada das regras e formas de selecioná-las.
• Não raciocinam em vários níveis.
• Não olham os problemas a partir de perspectivas diferentes.
• Não sabem como e quando violam suas próprias regras.
• Não tem acesso ao raciocínio que está por trás das regras.
• DOMÍNIOS DE APLICAÇÃO
• Domínios em que o conhecimento é difuso, consistido em muitos fatos, caso da medicina, em oposição aos domínios onde ele é uma teoria concisa e unificada, por exemplo, na física.
• Domínios nos quais processos podem ser representados como um conjunto de ações independentes, em oposição a domínios com subprocessos dependentes.
• Domínios em que o espaço de estados é facilmente obtido, como por exemplo em taxonomia .

3.3.1.2. Redes Semânticas

• É o nome utilizado para definir um conjunto heterogêneo de sistemas.
• Consiste em um conjunto de nodos conectados por um conjunto de arcos.

• Os nodos , em geral, representam objetos.
• Os arcos representam relações binárias entre os objetos.

• Originalmente foram usadas para suporte a linguagem natural. Em 1968 Ross Quillian as usou para representar modelos psicológicos de memórias humana chamado memórias semânticas.

• Conceitos são representados por nodos e relações entre conceitos por arcos.
• Explica diversos resultados experimentais.

3.3.1.3. Redes Semânticas Elementares

• Usam-se nodos para representar substantivos, adjetivos, pronomes e nomes próprios.
• Os arcos são reservados basicamente para representar verbos transitivos e preposições.
• Exemplo: "O cão corre atrás do gato"
• cão1 e gato1 são ambos instâncias de classes genéricas.
• pode-se generalizar também a relação entre eles, representando os indivíduos específicos com nodos anônimos e indicando a inclusão destes indivíduos em sua respectiva classe, através da relação é - um.
• relações de inclusão entre classes são representadas por relações subclasse - de.
• Os nodos rotulados representam classes genéricas, enquanto que os nodos anônimos representam indivíduos específicos.
• Nem sempre é assim, pois, se conhecermos, por exemplo, o nome do gato, podemos rotular o nodo que o representa com este nome.
• Para saber se um nodo representa uma instância, é só observar se ele está na origem de algum arco do tipo "é- um".

3.3.1.4. Redes Semânticas Generalizadas

• Procura resolver limitações das redes semânticas elementares ao representar verbos.
• Exemplo: "O Pluto correu atrás do Félix e o Félix correu atrás do Mickey ."
• devemos distinguir atos particulares de "correr atrás" de "correr atrás em geral".
• As redes semânticas generalizadas se diferenciam das elementares por representarem os verbos através de nodos e não mais de arcos

3.3.1.5. Redes Semânticas com Valores de Verdade

• Pode ser necessário representar fatos dos quais não se conhece o valor de verdade, ou mesmo, fatos que sabemos serem falsos. Uma maneira de fazê-lo é rotulando cada nodo- predicado com um valor VERDADEIRO, FALSO ou DESCONHECIDO.
• "Armirio Fraga disse que não vazou informações privilegiadas ."

3.3.1.6. Redes Semânticas Particionadas

• Muitas vezes é necessário representar relações quantificadas em redes .
• "Todos os homens são mortais."

3.3.2. Quadros e Roteiros

• Os Quadros ou Cenários ("Frames "), e sua variação, os roteiros ("Scripts"), foram introduzidos para permitir a expressão das estruturas internas dos objetos, mantendo a possibilidade de representar herança de propriedades.
• As pessoas, ao enfrentarem uma nova situação, guardam o repertório do comportamento para situações similares. Alguém que já assistiu alguma vez a um juri popular sabe que tipo de "quadro" irá encontrar se for a outro. (juiz, auxiliar de justiça, réu, advogado de defesa, promotor, etc.)
• Idéias fundamentais introduzidas por Marvin Minksy em 1975 ("A framework to represent knowledge").
• Está na origem das idéias que levaram às linguagens de programação orientadas a objetos.
• Um quadro consiste em um conjunto de atributos ("slots") que através de seus valores, descrevem as características do objeto representado pelo quadro.
• Os valores atribuídos aos atributos podem ser, além dos valores do objeto em particular, valores default, ponteiros para outros quadros, e conjuntos de regras de procedimento que podem ser implementados.
• Se os valores dos atributos forem apontadores para outros quadros, cria-se uma rede de dependências entre os quadros.
• Os conjuntos de procedimentos indicam que procedimento deve ser executado quando certas condições forem satisfeitas, por exemplo: ao ser criado o atributo, ao ser lido o valor do atributo, ao ser modificado o valor do atributo, ou ao ser destruído o valor do atributo.

• Os quadros também são organizados em uma hierarquia de especialização, criando outra dimensão de dependência entre eles (herança).
• Permite a especificação de propriedades de uma classe de objetos através da declaração de que esta classe é uma subclasse de outra que goza da propriedade em questão.

Quadros

• O processo de herança e instanciação favorece a reutilização de código evitando definições repetitivas e aproveitando funções de acesso definidas para as facetas se-lido, se-escrito, se- necessário, etc.
• Deve-se notar que as estruturas de quadros são ativas, pois sua manipulação causa o disparo automático das facetas.
• São úteis para domínio de problemas onde as formas e o conteúdo do dado desempenha um papel importante na solução do problema.

• São estruturas semelhantes aos quadros que descrevem seqüências estereotipadas de eventos em contextos particulares.
• A principal diferença que se pode estabelecer em relação aos quadros fica a nível das estruturas adotadas.
• Os eventos descritos formam uma cadeia causal.
• O início da cadeia é o conjunto de condições de entrada que permite a possibilidade de ocorrência do primeiro evento do roteiro.
• O fim da cadeia é o conjunto de resultados que permitirá a ocorrência de eventos posteriores.
• O raciocínio com roteiros serve especialmente para verificar se determinado evento ocorreu e também para verificar a relação entre os eventos, o que pode ser conseguido pelo exame da cadeia causal.