Upload
others
View
6
Download
0
Embed Size (px)
Citation preview
Agentes Lógicos
• A inteligência dos seres humanos é alcançada, não somente por mecanismos puramente reflexos, mas, por processos de raciocínio que operam em representações internas do conhecimento.
• Em IA, essa abordagem à inteligência é incorporada em agentes baseados em conhecimento.
Agentes Lógicos
• Os agentes de resolução de problemas conhecem as coisas, mas apenas em um sentido muito limitado, inflexível: – O modelo de transição do puzzle de oito peças somente
possui o conhecimento das ações para obter um resultado – O modelo pode ser utilizado para prever o resultado das
ações, mas não para deduzir que duas peças não podem ocupar o mesmo espaço.
– As representações atômicas utilizadas por agentes de resolução de problemas podem ser muito limitantes: • Seja um ambiente parcialmente observável, a única escolha do
agente para representar o que sabe sobre o estado atual é listar todos os possíveis estados concretos. E isto em grandes ambientes seria uma perspectiva sem esperança.
Agentes Lógicos
• Uma alternativa aos agentes estudados é o uso da lógica como uma classe geral de representações para apoiar ao agente baseado no conhecimento.
Agentes Lógicos
• Os agentes baseados no conhecimento: – Poderão combinar e recombinar informações para
atender às finalidades inumeráveis.
– São capazes de aceitar novas tarefas sob a forma de metas descritas de modo explícito, podem alcançar competência rapidamente ao serem informados ou ao adquirirem novos conhecimentos sobre o ambiente e podem se adaptar a mudanças no ambiente, atualizando o conhecimento relevante.
Agentes Lógicos
• Bases de conhecimento (BC): – É o componente central de um agente baseado em
conhecimento. – É um conjunto de sentenças*.
• Cada sentença é expressa em uma linguagem chamada linguagem de representação de conhecimento e representa alguma asserção sobre o mundo.
• Uma sentença toma o nome de axioma quando a sentença for tomada como dada sem ser derivada de outras sentenças.
*”sentença” é utilizada como um termo técnico; relacionada mas, não é idêntica às sentenças em português e em outros idiomas ou linguagens naturais.
Agentes Lógicos
• Os nomes-padrão para as operações são: (a) TELL (informar): o que precisa saber, adicionar novas
sentenças à base de conhecimento; e (b) ASK (perguntar): a si mesmo o que fazer. • Inferência: quando se formula (com ASK) uma pergunta
para a base de conhecimento, a resposta deve seguir do que foi informado (com TELL) anteriormente à base de conhecimento.
• Ambas operações podem envolver inferência: a derivação de novas sentenças a partir de sentenças antigas.
Agentes Lógicos
Programa de agente baseado em conhecimento
• Dada uma percepção, o agente adiciona a percepção na sua base de conhecimento, pergunta à base de conhecimento qual a melhor ação e informa à base de conhecimento que executou de fato essa ação.
Agentes Lógicos
• O agente baseado no conhecimento parece semelhante aos agentes estudados anteriormente. Mas, devido às definições de TELL e ASK, este agente não é um programa arbitrário para calcular ações.
• Por exemplo: um táxi automatizado que tem a meta de pegar um passageiro em Coqueiros para Trindade : – Se ele tiver a informação (TELL) que está em Coqueiros e
que a ponte Colombo Salles é a única ligação entre os dois locais, então pode-se esperar que ele cruze a ponte Colombo Salles porque sabe que isso o levará a atingir sua meta.
Agentes Lógicos
• A análise dessa situação independe de como o táxi funciona no nível de implementação.
• Não importa como foi implementado seu conhecimento geográfico (listas encadeadas ou mapas de pixels ou propagando sinais com ruído em uma rede de neurônios)
• Ele se adapta a uma descrição no nível de conhecimento, em que precisamos especificar apenas o que o agente sabe e quais são suas metas, a fim de corrigir seu comportamento.
Agentes Lógicos
• O agente deve ser capaz de:
– Representar estados, ações, etc.
– Incorporar novas percepções.
– Atualizar representações internas do mundo.
– Deduzir propriedades ocultas do mundo.
– Deduzir ações apropriadas.
Mundo de Wumpus
Desempenho
ouro +1000, morte-1000
passo -1 , flecha -10
Ambiente
Malha 4x4. O agente inicia no quadrado [1,1], voltado para a direita. Posições de ouro e wumpus aleatória.
Sensores:
[fedor, brisa, brilho, impacto, grito]
Atuadores: esquerda, direita, pegar, deixar, atirar
Regras:
quadrados próximos ao wumpus fedem
quadrados próximos ao poço: brisa
quadrado do ouro: brilho
Atirar mata wumpus se está em frente
Atirar usa uma única flecha
Agarrar pega objeto se no mesmo quadrado
Mundo de Wumpus PEAS:
• Observável?? Não, apenas percepção local.
• Determinístico? Sim, resultados exatamente especificados.
• Episódico ?? Não, sequencial ao nível das ações.
• Estático?? Sim, Wumpus e Poços não se movem.
• Discreto?? Sim.
• Agente único ?? Sim., O Wumpus é essencialmente uma característica natural do ambiente.
Explorando o mundo de wumpus
Primeira percepção: [nada, nada, nada, nada, nada]
Deduz: [1,2] e [2,1] são seguros...
Explorando o mundo de wumpus
O agente se move para [2,1] e sente uma brisa
Nova percepção: [nada , brisa , nada , nada , nada]
Dedução: não há poço em [1,1], portanto há poço em [3,1] ou [2,2]
Explorando o mundo de wumpus
O agente retorna e se move para [1,2] e sente um fedor
Nova percepção: [fedor , nada, nada , nada , nada]
Novas Deduções: • Não há Wumpus em [1,1] • Não houve fedor em [2,1],
não há Wumpus em [2,2]. • Wumpus em [1,3]. • Sem brisa em [1,2] , não
há Poço em [2,2].
Explorando o mundo de wumpus
• Estas inferências são difíceis pois baseiam-se em informações obtidas em diferentes instantes e lugares, e ainda na falta de uma percepção...
Já tinha-se inferido que deve haver Poço em [2,2] ou [3,1]. Com as novas deduções deve –se concluir que o Poço esta em [3,1].
Explorando o mundo de wumpus
• Em cada caso, o agente tira uma conclusão a partir das informações disponíveis: essa conclusão tem a garantia de ser correta se as informações disponíveis estiverem corretas.
• E essa é uma propriedade fundamental do raciocínio lógico.
Lógica
• Lógica é uma linguagem formal para representar conhecimento e como as conclusões poder ser obtidas a partir dessas informações, inferências.
• O conhecimento é expresso como sentenças.
Linguagem formal: usada para representar conhecimento. Métodos de inferência: usados para representar raciocínio.
Lógica
• Com a Lógica pode-se representar e validar argumentos.
• Na Lógica clássica ou bivalente, toda sentença deve ser possível de ser avaliada como verdadeira ou falsa.
Representar argumentos: Com uma sequencia de sentenças em que uma delas é a conclusão e as demais são premissas. Validar argumentos: verificar se a conclusão é uma consequência lógica das premissas.
Lógica
• Proposição
Sentença declarativa que pode ser verdadeira ou falsa, mas não as duas coisa ao mesmo tempo.
Excelente apresentação! Esta semana tem oito dias. Em que continente fica o Brasil? A Lua é um satélite da Terra.
Lógica
• Conetivos
Elementos que permitem construir sentenças complexas a partir de outras simples, eles são “não, “e”, “ou”, “então”,” se e somente se”.
Esta chovendo A rua esta molhada
Não Esta chovendo Se esta chovendo então a rua esta molhada
Lógica -- sintaxe
Lógica -- sintaxe
• Sintaxe refere-se à escrita correta na linguagem formal;
• Sentenças expressas respeitando a Sintaxe da linguagem são denominadas fórmulas bem formadas (fbf) :
– Exemplo: Em aritmética
• 𝑥 + 𝑦 = 4 é uma fbf
• 𝑥2𝑦 += não é uma fbf
Lógica -- semântica
• Define o significado das sentenças, isto é, o valor verdade de cada sentença em relação a seu domínio.
• Exemplo: Em álgebra
– 𝑥 + 𝑦 = 4
• É verdade na interpretação 𝑥 = 2 e 𝑦 = 2,
• É falsa na interpretação 𝑥 = 1 e 𝑦 = 1.
Lógica -- semântica
Lógica – argumento válido
Lógica – argumento válido
Lógica -- Dedução
– Dedução significa que uma coisa segue de outras:
𝑩𝑪 ⊨ 𝜶
– A partir da Base de conhecimento (BC) pode-se deduzir (inferir) a sentença
– é verdadeira em todo o domínio onde a BC é verdadeira.
Lógica -- Dedução
– Por exemplo:
• Se a BC contem as sentenças “ Os gigantes venceram” e “Os vermelhos venceram” pode-se deduzir “Ou os Gigantes venceram ou os vermelhos venceram”.
• A partir de 𝑥 + 𝑦 = 4 posso deduzir 4 = 𝑥 + 𝑦
– Deduzir é uma relação entre sentenças (sintaxe) que estão baseadas na semântica.
Lógica -- Dedução
• Modelos são formalmente mundos estruturados em relação aos quais a verdade pode ser avaliada.
• Pode-se disser que 𝑚 é um modelo de uma sentença se é verdadeira em 𝑚.
𝑀(𝛼) é o conjunto de todos os modelos de
Logo BC ⊨ α se e somente se 𝑀(𝐵𝐶) ⊆ 𝑀(𝛼) Por exemplo:
BC = Gigantes venceram e Vermelhos venceram
= Gigantes venceram
Lógica -- Dedução
• Dada duas sentenças e , se em todos as interpretações em que é verdadeira, também o é dizemos que é consequência lógica de :
𝜶 ⊨ 𝜷
“se é verdadeira também deve ser.”
Lógica: Dedução no mundo do wumpus
• Situação após detectar nada em [1,1], mover à direita e brisa em [2,1]
• Considerar as interpretações possíveis modelos para ? Supondo apenas poços.
• 3 escolhas booleanas, 8 possíveis modelos.
Lógica: Dedução no mundo do wumpus
Lógica: Dedução no mundo do wumpus
• BC = regras do mundo de wumpus + observações
Lógica: Dedução no mundo do wumpus
• BC = regras do mundo de wumpus + observações
• 1 = "[1,2] é seguro", 𝐵𝐶 ⊨ 𝛼1 provado ! 1 pode ser inferido da BC.
Lógica: Dedução no mundo do wumpus
• BC = regras do mundo de wumpus + observações
• 2 = "[2,2] é seguro", 𝐵𝐶 ⊭ 𝛼2
Lógica: Dedução no mundo do wumpus
• Em alguns modelos em que BC é verdadeira, 2 é falsa, logo não há como deduzir se há um poço em [2,2] nem se não há...
Lógica: Dedução no mundo do wumpus
• O procedimento mostrado para verificar 1 e 2 é um algoritmo de inferência denominado:
verificação de modelos
pois enumera todos os modelos possíveis para verificar se é verdadeira em todos os modelos em que BC é verdadeira.
Inferência: 𝐵𝐶 ⊨𝑖 𝛼
• Significa que a sentença é derivável (inferida/deduzida) da BC pelo algoritmo de inferência i.
• Soundness: O algoritmo de inferência que deriva apenas
sentenças permitidas (pertencentes ao modelo) é chamado de correto(consistente)ou se diz que ele preserva a verdade
Sempre que 𝐵𝐶 ⊨𝑖 𝛼 é verdade que 𝐵𝐶 ⊨ 𝛼
• Completeness, Um algoritmo de inferência será completo se puder derivar qualquer consequência lógica.
Sempre que 𝐵𝐶 ⊨ 𝛼 é verdade que 𝐵𝐶 ⊨𝑖 𝛼
Inferência
• Usando a lógica tem-se um processo de raciocínio: “Se BC é verdadeira no mundo real, qualquer sentença a derivada de BC por um procedimento de inferência correto também será verdadeira no mundo real”
• A pesar do processo de inferência operar sobre a “sintaxe”, ele corresponde ao relacionamento no mundo real. Essa correspondência entre o mundo e a representação está ilustrada na Figura acima.
Como sabemos que a BC é verdadeira no mundo real?
• Os sensores do agente criam a conexão.
– E se houver exceções?
– E se a verdade for temporária?
– E se houver regras gerais não previstas??
Lógica proposicional: sintaxe
• Dada uma sentença S, então S é uma sentença negada.
• Um literal é uma sentença atômica, chamada também de literal positivo, e, se for negada de literal negativo.
• Precedência dos operadores lógicos – Utilize parênteses:
((A B) C))
– Ou se apoie na ordem de precedência:
, , , e
Exemplo:
P Q R S equivale a: (( P) (Q R)) S
Lógica proposicional: semântica
• A semântica define as regras para determinar a verdade de uma sentença com respeito a um modelo específico.
• Um modelo proposicional simplesmente fixa o valor verdade para todo símbolo proposicional.
• Por exemplo, seja uma BC com os símbolos proposicionais :𝑃1,2, 𝑃2,2, 𝑃3,1, um possível modelo será:
𝑚1 = {𝑃1,2 = 𝑓𝑎𝑙𝑠𝑎, 𝑃2,2 = 𝑓𝑎𝑙𝑠𝑎, 𝑃3,1 = 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎}
Lógica proposicional: semântica
• Regras para avaliar o valor verdade com respeito a um modelo m:
– S é verdade sse S é falso – S1 S2 é verdade sse S1 é verdade e S2 é verdade – S1 S2 é verdade sse S1é verdade ou S2 é verdade – S1 S2 é verdade sse S1 é falso ou S2 é verdade – i.e., é falso sse S1 é verdade e S2 é falso – S1 S2 é verdade sse S1S2 é verdade e S2S1 é verdade
Lógica proposicional: semântica
• Tabela verdade
Assim, reduz-se a verdade de sentenças complexas à verdade de sentenças mais simples em um processo recursivo. Por exemplo: P1,2 (P2,2 P3,1) = verdadeira (falsa verdadeira) = verdadeira
verdadeira = verdadeira Obs. Cada linha da tabela é uma interpretação possível.
Procedimento de inferência no mundo do wumpus
• Deseja-se saber se , ¬P1,2 é verdadeira na BC
• Devem-se enumerar todos os modelos e verifique se α é verdadeira em todo modelo no qual BC é verdadeira.
• No caso da lógica proposicional, os modelos são atribuições de verdadeiro ou falso a todo símbolo proposicional.
• Os símbolos proposicionais relevantes são
B11, B21, P11, P12, P21,P22 e P31
Com sete símbolos, existem 27 = 128 modelos possíveis.
Procedimento de inferência no mundo do wumpus
Base de Conhecimento
P11
B11
B21
B11 (P12 P21)
B21 (P11 P22 P31)
Procedimento de inferência no mundo do wumpus
• Em três desses modelos a BC é verdadeira e ¬P1,2 é verdadeira; consequentemente, não existe nenhum poço em [1,2].
• Por outro lado, P2,2 é verdadeira em dois dos três modelos e falsa em um, e assim não podemos dizer ainda se existe um poço em [2,2].
Inferência por enumeração de modelos
• Um algoritmo de enumeração de tabela-verdade para decidir a consequência lógica proposicional.
• Para n símbolos, complexidade temporal é O(2n), e espacial é O(n)
Equivalência lógica
• Duas sentenças são logicamente equivalentes se e somente se (sss) são verdadeiras nos mesmos modelos:
sss 𝛼 ⊨ 𝛽 e 𝛽 ⊨ 𝛼
Validade e satisfatibilidade
Uma sentença é válida se verdadeira em todos os modelos, Por exemplo: Verdadeiro, A A, A A, (A (A B)) B
» Tautologias
Validade é ligada à inferência via o Teorema da Dedução : 𝐵𝐶 ⊨ 𝛼 se e somente se (BC ) é valida
Uma sentença é satisfatível se é verdadeira em algum modelo
Por exemplo: A B (esta fbf será verdadeira em alguns modelos)
Uma sentença é insatisfatível se verdadeira em nenhum modelo Por exemplo: AA
Satisfatibilidade é ligada à inferência via o seguinte: 𝐵𝐶 ⊨ 𝛼 se e somente se (KB ) é insatisfatível Por exemplo: Provar por contradição ou pelo absurdo
Inferência e provas
• Regras de inferência: – Modus ponens
,
– Eliminação-do-e
– Todas as equivalências anteriores podem ser usadas como regras de inferência.
Inferência e provas: Mundo de wumpus
R1: P11 não há nenhum poço em [1,1]
R2: B11 não há nenhuma brisa em [1,1]
R3: B21 há brisa em [2,1]
• Um quadrado tem brisa se e somente se existe poço em um quadrado vizinho R4: B11 (P12 P21)
R5: B21 (P11 P22 P31)
Inferência e provas: Mundo de wumpus
• Objetivo é provar se 𝐵𝐶 ⊨ 𝛼 para alguma sentença 𝛼. Isto é, P12 é consequência lógica de BC?
• Eliminação do bicondicional em R4:
• R6: (B11 (P12 P21)) ((P12 P21) B11)
Inferência e provas: Mundo de wumpus
– Eliminação do “e” em R6:
R7:(B11(P12P21))
R7*:((P12P21)B11)
– Contraposição em R7*:
R8: ( B11 (P12 P21))
Inferência e provas: Mundo de wumpus
– Modus ponens com R2 e R8:
R9: (P12 P21)
– Regra de De Morgan em R9:
R10: P12 P21
Nem [1,2], nem [2,1] possui um poço!, foi provado que P12 é consequência lógica de BC.
Métodos de Prova
• Verificação do modelo
– Se BC contêm n símbolos ao todo, então existem 2𝑛 modelos: • A complexidade de tempo do algoritmo é O(2𝑛). • A complexidade de espaço é somente O(n) porque a enumeração é feita em
profundidade. – Em geral, todo algoritmo de inferência conhecido para lógica
proposicional tem uma complexidade no pior caso que é exponencial em relação ao tamanho da entrada.
• Aplicação de regras de inferência
– Gerar novas sentenças a partir das anteriores. – Prova = aplicação sequencial de regras de inferência. – As regras de inferência são corretas, mas, se as regras de inferência
disponíveis forem inadequadas, a meta não será acessível — não existirá nenhuma prova que utilize apenas essas regras de inferência. • Exemplo, se removêssemos a regra de eliminação de bicondicional, a prova
apresentada na seção anterior não seria possível.
Prova por Resolução
• Os procedimentos de inferência baseados na resolução funcionam pela utilização do princípio de prova por contradição.
Para mostrar que 𝐵𝐶 ⊨ 𝛼
mostramos que (BC ∧ ¬α) é não satisfatível.
Algoritmo de Resolução
Algoritmo: • 1º : A entrada (BC ∧ ¬α) é convertida em Forma Normal
Conjuntiva - FNC. A forma normal conjuntiva FNC é uma conjunção de
disjunções de literais: (A B) (B C D)
• 2º : A regra de resolução é aplicada às cláusulas restantes. • 3º : Cada par que contém literais complementares é
resolvido para gerar uma nova cláusula, que é adicionada ao conjunto se ainda não estiver presente.
Algoritmo de Resolução
Exemplo: Sejam as proposições:
(B1,1 P1,2 P2,1) (P2,2 B1,1)
Aplicando a Regra de Resolução obtém-se:
P1,2 P2,1 P2,2
Regras de Resolução 1) 𝑝 ∨ 𝑞
2) ¬𝑞 ∨ 𝑟
3) 𝑝 ∨ 𝑟 de 1 e 2
1) 𝑝 ∨ 𝑞
2) ¬𝑞
3) 𝑝 de 1 e 2
Algoritmo de Resolução
• O processo continua até acontecer um destes dois fatos:
– Não há nenhuma cláusula nova que possa ser adicionada, nesse caso BC não tem como consequência lógica; ou,
– Duas cláusulas resolvem produzindo uma cláusula vazia, nesse caso BC tem como consequência lógica .
Algoritmo de Resolução
• Cláusula vazia:
– É uma disjunção de nenhum disjunto
– Equivalente a Falso porque uma disjunção só é verdadeira se pelo menos um de seus disjuntos é verdadeiro.
– Outra maneira de ver que uma cláusula vazia representa uma contradição é observar que ela só surge da solução de duas cláusulas unitárias complementares como P e ¬P.
Algoritmo de Resolução
• Prova por contradição, i.e., para provar “a” em BC, mostrar que BCa é insatisfatível
• Um algoritmo de resolução simples para lógica proposicional.
• A função RESOLVER-LP retorna o conjunto de todas as cláusulas possíveis obtidas pela resolução de suas duas entradas.
Prova por Resolução
• Qualquer algoritmo de busca completo, aplicando apenas a regra de resolução, pode derivar qualquer conclusão permitida por qualquer base de conhecimento em lógica proposicional!
Prova por Resolução: Conversão a CNF
B1,1 (P1,2 P2,1) 1. Eliminar , trocando por ( )( ).
(B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1)
2. Eliminar , trocando por . (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)
Prova por Resolução: Conversão a CNF
3. Mover para dentro usando as leis de de Morgan e negação dupla:
(B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)
4. Aplicar a lei distributiva ( sobre ) e eliminar ‘(‘ ’)’:
(B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1)
Algoritmo de Resolução: Mundo de Wumpus
• O agente esta em [1,1] e não existe brisa (R2 e R4), então não pode haver poços em quadrados (P1,2)
BC = (B1,1 (P1,2 P2,1)) B1,1
= P1,2
Algoritmo de Resolução: Mundo de Wumpus
Duas cláusulas produzindo uma cláusula vazia: duas cláusulas
unitárias complementares como P e ¬P.
BC
Cláusulas de Horn e cláusulas definidas
• A completude da Resolução a torna um método de inferência muito importante.
• Há situações práticas, nas que o pleno poder de resolução não é necessário.
• Algumas BC do mundo real satisfazem certas restrições sobre a forma de sentenças que elas contêm, que permite que elas utilizem um algoritmo de inferência mais restrito e eficiente.
Cláusulas de Horn e cláusulas definidas
• Uma destas formas restritas é a cláusula definida:
– É uma disjunção de literais dos quais exatamente um é positivo:
Exemplos: a cláusula (¬ L1,1 ∨ ¬Brisa, ∨ B1,1) é uma cláusula definida, já a cláusula (¬B1,1 ∨ P1,2 ∨ P2,1) não é uma cláusula definida.
Cláusulas de Horn e cláusulas definidas
• A cláusula de Horn é uma disjunção de literais dos quais pelo menos um é positivo.
• Todas as cláusulas definidas são cláusulas de Horn
• As cláusulas sem literal positivo são chamadas cláusulas objetivo.
• As cláusulas de Horn são fechadas sob resolução: se você resolver duas cláusulas de Horn, receberá de volta uma cláusula de Horn.
Cláusulas de Horn e cláusulas definidas
• As BC que contém apenas cláusulas definidas são interessantes por três razões: 1. Toda cláusula definida pode ser escrita como uma
implicação cuja premissa é uma conjunção de literais positivos e cuja conclusão é um único literal positivo.
Exemplo: A cláusula definida (¬ L1,1 ∨ ¬ Brisa ∨ B1,1) Pode ser escrita como (L1,1 ∧ Brisa) ⇒ B1,1
A implicação informa que, se o agente está em [1,1] e há uma brisa, então [1,1] está com brisa.
Cláusulas de Horn e cláusulas definidas
• Na forma de Horn, a premissa é chamada corpo, e a conclusão, cabeça.
• Uma sentença que consiste em um único literal positivo, como L1, 1, é chamada de fato.
• Também pode ser escrita na forma de implicação como “Verdadeiro ⇒ L1, 1”, mas é mais simples escrever apenas L1, 1.
Cláusulas de Horn e cláusulas definidas
2. A inferência com cláusulas de Horn pode ser feita através de algoritmos de encadeamento para a frente e encadeamento para trás • Ambos os algoritmos são naturais e, por isso, as etapas
de inferência são óbvias e fáceis de os seres humanos seguirem.
• Esse tipo de inferência é a base para a programação lógica.
3. A decisão da consequência lógica com as cláusulas de Horn pode ser feita em tempo linear no tamanho da base do conhecimento.
Forward chaining
• Ideia: Ativa qualquer regra cuja premissa seja satisfeita na BC, a conclusão obtida será acrescentada ao conjunto de fatos da BC, até que a consulta seja encontrada.
Exemplo--Forward chaining
Exemplo--Forward chaining
Exemplo--Forward chaining
Exemplo--Forward chaining
Exemplo--Forward chaining
Exemplo--Forward chaining
Exemplo--Forward chaining
Exemplo--Forward chaining
Prova de completude
• É fácil ver que o FC é correto: toda inferência é em essência uma aplicação de Modus Ponens.
• O FC é completo: toda sentença atômica permitida será derivada: – Para verificar isso, considerar o estado final da tabela
inferida (depois que o algoritmo alcança um ponto fixo em que nenhuma nova inferência é possível).
– A tabela contém verdadeiro para cada símbolo inferido durante o processo e falso para todos os outros símbolos.
– Podemos visualizar a tabela como um modelo lógico; além disso, toda cláusula definida na BC original é verdadeira nesse modelo.
Prova de completude
• O FC é um exemplo do conceito geral de raciocínio orientado a dados — isto é, o raciocínio em que o foco da atenção começa com os dados conhecidos.
• FC pode ser usado em um agente para derivar conclusões a partir de percepções de entrada: – Exemplo, o agente de wumpus poderia informar (com TELL) suas percepções à
base de conhecimento, utilizando um algoritmo de encadeamento para a frente incremental em que novos fatos pudessem ser adicionados à agenda para iniciar novas inferências.
• Em seres humanos, certa quantidade de raciocínio orientado a dados ocorre à medida que chegam novas informações. – Exemplo, se estou em um ambiente fechado e ouço a chuva começando a cair,
pode me ocorrer que o piquenique será cancelado. Ainda assim, não me ocorrerá que o jardim do meu vizinho ficará molhada; os seres humanos mantêm o encadeamento para a frente sob cuidadoso controle, temendo ficar sobrecarregados com o acúmulo de consequências irrelevantes.
Backward chaining
• Ideia: O “backward” trabalha a partir da pergunta q à base de conhecimento: – Para provar q na BC,
• verificar se q já faz parte de BC, ou • provar pela BC todas as premissas de alguma regra que conclua
q
– Evitar laços: verifique se o novo sub-objetivo já esta na pilha de objetivos
– Evitar trabalho repetido: verificar se um novo sub-objetivo
• Já foi provado como verdadeiro, ou • Já falhou.
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Exemplo--Backward chaining
Backward chaining
• BC funciona no sentido inverso, a partir da consulta: – Se a consulta θ é reconhecida como verdadeira, não é necessário nenhum
trabalho; – Caso contrário, o algoritmo encontra as implicações na base de
conhecimento cuja conclusão é θ; – Se for possível demonstrar que todas as premissas de uma dessas
implicações são verdadeiras (por encadeamento para trás), então θ é verdadeira.
• O encadeamento para trás é uma forma de raciocínio orientado por metas (objetivos).
• BC é útil para responder a perguntas específicas como: “O que devo fazer agora?” e “Onde estão minhas chaves?”.
• Com frequência, o custo do encadeamento para trás é muito menor que um custo linear em relação ao tamanho da base de conhecimento porque o processo só toca fatos relevantes.
Forward vs. backward chaining
• ForwC é baseado nos dados, – Pode ser usado para derivar conclusões a partir de percepções de
entrada, sem uma consulta específica em mente;
– Pode executar muito trabalho irrelevante para o objetivo;
– Executa um trabalho extensivo;
• BackC é baseado no objetivo, – Apropriado para resolução de problemas;
– Funciona em tempo linear
– Complexidade de BackC pode ser muito menor do que linear em relação ao tamanho da base de conhecimento por que o processo só toca fatos relevantes para provar um objetivo.