Abdução, Raciocínio por default e Revisão de crenças

OntologiesReasoningComponentsAgentsSimulations

Abdução, Raciocínio por Abdução, Raciocínio por default default eeRevisão de crençasRevisão de crenças

Daniel MoreiraJoão dos Prazeres

Priscila Saboia

EsquemaEsquema

Motivação Introdução

Lembrete de abdução Introduzindo raciocínio por default Lembrete de revisão de crenças

Raciocínio por default Abordagens

NAF Abdução Lógica-defaut

NAF NAF como raciocínio por default

GLPs Sintaxe GLPs estratificados Semânticas declarativas

Completação de Clark Semântica de conjuntos de resposta (SCR) Semântica bem-fundamentada (SBF) SCR X SBF

Semânticas operacionais Resolução SLDNF Resolução SLG

Abdução Aplicações práticas na IA Viés

Positive Abductive Logic Programming (PALP) Sintaxe Semântica declarativa Semântica operacional: SLDA Tranformar GLPs em PALPs

General Abductive Logic Programming (GALP) Semântica operacional: SLDNFA

Raciocínio por default como abdução Abdução em CHRv

Exemplo Revisão de Crença e Manutenção de

Verdade Sistemas de manutenção de verdade; JTMS JTMS e abdução ATMS ATMS e abdução JTMS X ATMS

Conclusão

MotivaçãoMotivação

O que fazer, dentro do contexto da IA - Simbólica, quando um agente não possui conhecimento suficiente para deduzir informações necessárias à escolha da sua próxima ação?

Raciocínio hipotético com informação parcial em ambientes parcialmente observáveis.

(P1) irmaos(joaquim, manoel)

???

(CR1) primos(F1, F2) irmaos(P1, P2) pai(P1, F1) pai(P2, F2)

(CF1) pai(joaquim, jose)(CF2) pai(manoel, joao)(CF3) primos(jose, joao)

Introdução: lembrete de abduçãoIntrodução: lembrete de abdução

Abdução

CPCI CPEC NCEC |= CPEE

ConhecimentoPrévio em Extensão:• Efeitos Observados

e(a), e(b), ...• Causais Observadas

Incompletasco(a), co(b), ...

Novo Conhecimentoem Extensão:

Causas Hipotéticasch(a), ch(b) ...

Viés sobre Hipóteses:

ch(X)

ConhecimentoPrévio Causalem Intenção

e(X) co(X) ch(X)

Introdução: lembrete de abdução (2)Introdução: lembrete de abdução (2)

A partir de: Conhecimento prévio causal em intenção:

loc(P, X, Y, T+1) loc(P, X, Y, T) move(P, X+1, Y, T) mureta(X+1, Y) Conhecimento prévio em extensão incompleto de causas:

loc(player_1, 4, 1, 1) move(player_1, 5, 1, 1) Conhecimento prévio em extensão de efeitos observados:

loc(player_1, 4, 1, 2)

Abduzir: Novo conhecimento em extensão de causa hipotética:

mureta(5, 1)

Introduzindo raciocínio por Introduzindo raciocínio por defaultdefault

Uso de regras-default aplicadas se não geram contradições com a aplicação de regras dedutivas.

Característica não-monotônica Adição de nova informação pode impossibilitar a derivação de fatos antes

deriváveis.

voa(picolino)

(RD1) voa(X) ave(X) // regra default(CR1) ave(X) pinguim(X) // regra dedutiva(CR2) ¬voa(X) pinguim(X) // regra dedutiva(CF1) ave(picolino)(CF2) pinguim(picolino) // nova percepção

Conclusão por default

¬voa(picolino)

Nova conclusão

Introdução: lembrete de revisão de crençaIntrodução: lembrete de revisão de crença Tarefa de raciocínio necessária quando:

Recepção (sensorial ou comunicativa) de novos fatos confirmados contradiz conclusão por default ou hipóteses abduzidas anteriormente.

Tal contradição pode ser observada diretamente, ou indiretamente via dedução.

(RD1) ave(X) bota_ovo(X) tem_bico(X) (CR1) mamifero(X) monotrema(X)*(RI1) false ave(X) mamifero(X)

(CF1) bota_ovo(ornitorrinco) (CF2) tem_bico(ornitorrinco)

(HD1) ave(ornitorrinco) (CF4) mamifero(ornitorrinco)

(CF3) monotrema(ornitorrinco)

* Cláusulas com a cabeça falsa são ditas restrições, sendo peculiares ao formalismo lógico PALP. Estas serão melhor abordadas posteriormente.

(HD1) ave(ornitorrinco)

tell(ave(ornitorrinco))

Conclusão por default

Recepção comunicativa

(CF3) monotrema(ornitorrinco)

tell(monotrema(ornitorrinco))

Revisão de crençaretract(ave(ornitorrinco)).

Dedução

(CF4) mamifero(ornitorrinco)

tell(mamifero(ornitorrinco))

Raciocínio por Raciocínio por default:default: abordagens abordagens

NAF (negation as failure – negação por falha): novo conectivo naf; Abdução: tarefa de raciocínio; Lógica-default: nova regra de inferência;

Ver AIMA, capítulo 10, seção 7, para maiores detalhes. Herança não-monotônica:

Elephant+cor: branco

RoyalElephant

Clyde:RoyalElephant





RoyalElephant+cor: branco

Clyde:RoyalElephant





RoyalElephant+cor: branco

Clyde:RoyalElephant

+cor: branco





RoyalElephant+cor: cinza

Clyde:RoyalElephant

+cor: branco

Nova Percepçã

o





RoyalElephant+cor: cinza

Clyde:RoyalElephant

+cor: cinza

NAF – Negação por falhaNAF – Negação por falha

Conectivo unário (naf) antes de um termo A; Ao encontrar premissa da forma naf A...

A máquina de inferência tenta deduzir A. Se consegue em tempo finito, deriva que naf A é falso; Se não consegue em tempo finito, deriva que naf A é verdadeiro.

Semanticamente, naf é distinto da negação clássica , da lógica: A é verdadeiro sse BC |= A; naf(A) é verdadeiro sse BC| A;

onde BC é a base de conhecimento.

Exemplo de NAFExemplo de NAF

Negação por falha funciona com hipótese do mundo fechado

(CR1) ave(X) tem_bico(X) bota_ovo(X) tem_pena(X)(CR2) mamifero(X) naf(ave(X))(CF1) tem_bico(ornitorrinco)(CF2) bota_ovo(ornitorrinco)

(P1) mamifero(ornitorrinco)

Exemplo de NAFExemplo de NAF

Negação por falha funciona com hipótese do mundo fechado

(CR1) ave(X) tem_bico(X) bota_ovo(X) tem_pena(X)(CR2) mamifero(X) naf(ave(X))(CF1) tem_bico(ornitorrinco)(CF2) bota_ovo(ornitorrinco)

MI-NAF*: Verdadeiro.

* MI-NAF: máquina de inferência que implementa a negação por falha.

(P1) mamifero(ornitorrinco)

NAF como raciocínio por NAF como raciocínio por defaultdefault

(P1) voa(picolino)

(CR1) voa(X) ave(X) naf(pinguim(X))(CR2) ave(X) pinguim(X)(CF1) ave(picolino)


(P1) voa(picolino)

(CR1) voa(X) ave(X) naf(pinguim(X))(CR2) ave(X) pinguim(X)(CF1) ave(picolino)(CF3) pinguim(picolino) // nova percepção

MI-NAF*: Verdadeiro


(P1) voa(picolino)


Característica não-monotônica Adição de nova informação impossibilitou derivação de fatos antes deriváveis.

(P1) voa(picolino)

(CR1) voa(X) ave(X) naf(pinguim(X))(CR2) ave(X) pinguim(X)(CF1) ave(picolino)(CF3) pinguim(picolino) // nova percepção

MI-NAF*: Verdadeiro


(P1) voa(picolino)

MI-NAF*: Falso

CFOLFunctionalTerm

CFOLAtomicFormula

GLPs: sintaxe abstrataGLPs: sintaxe abstrata

GLP

Functor =

GLPPremisse

Functor = Premisse

Conclusion

General Logic Program

NegativeLiteral

Functor = naf

Literal*

*GLPClause

Fact

context GLPClause inv DC: Conclusion.CFOLAtomicFormula.CFOLTerm false

context Fact inv Fact: Premisse -> size() = 1 andPremisse.Literal.CFOLTerm = true

PredicateSymbol

CFOLTerm

CFOLNonFunctionalTerm

Arg1..*

FunctionSymbolConstantSymbolCFOLVariable

Functor

Functor

*StratifiedGLP

Functor =

GLPs sem ciclos de dependência entre predicados através de naf

Exemplo de GLPExemplo de GLP

(CR1) ave(X) homeotermico(X) naf mamifero(X)(CR2) mamifero(X) homeotermico(X) naf ave(X)(CR3) mama(X) mamifero(X)(CR4) bota_ovo(X) ave(X)

(CF1) mama(ornitorrinco)(CF2) bota_ovo(ornitorrinco)

GLPs sem ciclos de dependência entre predicados através de naf

GLP estratificado:

femea(X) mulher(X)mulher(X) humano(X) naf(homem(X))humano(X) homem(x)

GLP não-estratificado:

femea(X) mulher(X)mulher(X) humano(X) naf(homem(X))humano(X) homem(X)homem(X) naf(mulher(X))

GLPs estratificadosGLPs estratificados

femea(X)

mulher(X)

humano(X)

homem(X)

naf

femea(X)

mulher(X)

humano(X)

homem(X)

nafnaf

Semânticas declarativas de GLPsSemânticas declarativas de GLPs

Completação de Clark; Semântica de conjuntos de resposta; Semântica bem-fundamentada

Completação de Clark para GLPsCompletação de Clark para GLPs

Mesmo algoritmo para DLPs, estendido para substituir nafs por negações clássicas ¬

femea(X) mulher(X)mulher(X) humano(X) naf(homem(X))humano(X) homem(x)

X1(femea(X1) X (X1 = X mulher(X)))

X1(mulher(X1) X (X1 = X humano(X) ¬homem(X)))

X1(humano(X1) X (X1 = X homem(X)))

X1(¬ homem(X1))

Completação de Clark para GLPs (2)Completação de Clark para GLPs (2)

Limitaçãoligado(X) aperta_botao(X) naf(ligado(X))

X1(ligado(X1) X(X1 = X aperta_botao(X) ¬ligado(X)))

Simplificado ligado(X) por p, X1 = X por a e aperta_botao(X) por b...

p a b ¬p

Supondo p = a = b = VerdadeiroVerdadeiro Falso

Solução: escrever GLPs estratificados.

Inconsistente!

Semântica de conjunto de respostasSemântica de conjunto de respostas

Modelos estáveis Justificativa de um elemento E de um modelo Mh de Herbrand: elementos de Mh

formando o corpo de uma regra que conclui E; Modelo estável: modelo mínimo de Herbrand cujos elementos são todos

justificados; Um programa lógico é consistente se possui um modelo estável.

anc(X, Y) pai(X, Y)anc(X, Z) anc(X, Y) pai(Y, Z)pai(joaquim, jose)pai(manoel, joaquim)

MHM ={pai(manoel, joaquim), anc(manoel, joaquim), pai(joaquim, jose),

anc(joaquim, jose), anc(manoel, jose)}

Semântica de conjuntos de resposta (2)Semântica de conjuntos de resposta (2)

Certos GLPs apresentam mais de um modelo mínimo de Herbrand, que não são estáveis.

ave(X) homeotermico(X) naf(mamifero(X)).mamifero(X) homeotermico(X) naf(ave(X)).mama(X) mamifero(X).homeotermico(ornitorrinco).

MHM1 = {homeotermico(ornitorrinco), ave(ornitorrinco)}





MHM2 = {homeotermico(ornitorrinco), mamifero(ornitorrinco), mama(ornitorrinco)}





MHM2 = {homeotermico(ornitorrinco), mamifero(ornitorrinco), mama(ornitorrinco)}


Modelos estáveis em GLPs: Para obtê-los, reduz-se o programa P: 1. Elimina-se todas as regras que possuam um literal naf(A), estando A em um dos modelos

mínimos; 2. Elimina-se todos os literais negativos das regras restantes.

P = { ave(X) homeotermico(X) naf(mamifero(X))mamifero(X) homeotermico(X) naf(ave(X))mama(X) mamifero(X)homeotermico(ornitorrinco) }

MHM1 = {homeotermico(X), ave(ornitorrinco)}

R1(P, A = ave(X)) ={ ave(X) homeotermico(X)

mama(X) mamifero(X)homeotermico(ornitorrinco) }

MHM(R1) = {homeotermico(ornitorrinco), ave(ornitorrinco)}


P = { ave(X) homeotermico(X) naf(mamifero(X))mamifero(X) homeotermico(X) naf(ave(X))mama(X) mamifero(X)homeotermico(ornitorrinco) }

MHM2 = {homeotermico(X), mamifero(ornitorrinco), mama(ornitorrinco)}

R2(P, A = mamifero(X)) =

{ mamifero(X) homeotermico(X)mama(X) mamifero(X)homeotermico(ornitorrinco) }

MHM(R2) = {homeotermico(ornitorrinco), mamifero(ornitorrinco), mama(ornitorrinco)}

Semanticamente, P significa um conjunto de respostas, dadas para cada possível redução de P.

R1(P, ave(X)):

{homeotermico(ornitorrinco), ave(ornitorrinco)} | ave(ornitorrinco)(supondo ave(ornitorrinco) = Verdadeiro)

+

R2(P, mamifero(X)):

{mamifero(ornitorrinco), homeotermico(ornitorrinco), mama(ornitorrinco)} | mamifero(ornitorrinco)(supondo mamifero(ornitorrinco) = Verdadeiro)

Conjuntos de resposta e abduçãoConjuntos de resposta e abdução

Semanticamente, P significa um conjunto de respostas, dadas para cada possível redução de P.

R1(P, ave(X)):

{homeotermico(ornitorrinco), ave(ornitorrinco)} | ave(ornitorrinco)(supondo ave(ornitorrinco) = Verdadeiro)

+

R2(P, mamifero(X)):

{mamifero(ornitorrinco), homeotermico(ornitorrinco), mama(ornitorrinco)} | mamifero(ornitorrinco)(supondo mamifero(ornitorrinco) = Verdadeiro)

Conjuntos de resposta e abduçãoConjuntos de resposta e abdução

Semântica bem-fundamentadaSemântica bem-fundamentada

Adota a lógica ternária. Lógica ternária:

Valores-verdade: Falso = 0; Indefinido = ½; Verdadeiro = 1.

(Re)Definições das fórmulas lógicas:¬F = 1 – FF G = min(F, G)F G = max(F, G)F G = se F < G então 0 senão 1F G = se F = G então 1 senão 0

Semântica bem-fundamentada (2)Semântica bem-fundamentada (2)

Lógica ternária (continuação) Tabela-verdade:

P Q P Q PQ PQ PQ PQ

T

T F F T T T T

F F T F T F F

U F U U T F U

F

T T F F T T T

F T T F F T T

U T U F U T T

U

T U F U T T T

F U T F U F U

U U U U U T U

Semântica bem-fundamentada (3)Semântica bem-fundamentada (3)

Estende a idéia de modelos estáveis; Permite o valor INDEFINIDO U para termos ground que não são

absolutamente Falsos nem Verdadeiros.

ave(X) homeotermico(X) naf(mamifero(X))mamifero(X) homeotermico(X) naf(ave(X))mama(X) mamifero(X)homeotermico(ornitorrinco)

ME = {homeotermico(ornitorrinco) = T, mamifero(ornitorrinco) = U, ave(ornitorrinco) = U, mama(ornitorrinco) = U, todos os demais termos falsos}

Semântica operacional baseada em SBF: responde a perguntas gerais com Verdadeiro (T), Falso (F) ou Indefinido (U).

Semântica de conjuntos de resposta XSemântica de conjuntos de resposta XSemântica bem-fundamentadaSemântica bem-fundamentada

Semântica de conjuntos de resposta Booleana; Vários modelos; Crédula:

Define a semântica em termos de suposições sobre fatos não fundamentados (abdução).

a b naf c c d naf a b d

Semântica bem-fundamentada Ternária Modelo único; Cética:

Assume que fatos não fundamentados são indefinidos.

b, da c

SCR:

{a, b, d} | a

{c, b, d} | c

SBF:

{b, d} verdadeiros{a, c} indefinidos

GLPs: semânticas operacionaisGLPs: semânticas operacionais

Resolução SLDNF (implementa a semântica declarativa da completação de Clark);

Resolução SLG (implementa a semântica declarativa bem-fundamentada).

Resolução SLDNFResolução SLDNF

Combinação de resolução SLD para resolver literais positivos, e negação por falha finita para resolver literais negativos.

Resolução SLD para resolver literais positivos... Encadeamento para trás, com regra específica de seleção de termos nas

premissas das cláusulas a serem resolvidas, em tempo linear.

+

Negação por falha finita para resolver literais negativos... naf A é VERDADEIRO sse A tem uma árvore SLD com falha finita; naf A é FALSO sse A tem uma refutação SLD com substituição-resposta

computada vazia (i. e. sem substituir todos os argumentos do literal por constantes).

Exemplo de resolução SLDNFExemplo de resolução SLDNF

alicerce(X) sobre(Y, X) no_chao(X)no_chao(X) naf(fora_do_chao(X))fora_do_chao(X) sobre(X, Y)acima(X, Y) sobre(X, Y)acima(X, Y) sobre(X, Z) acima(Z, Y)sobre(c, b)sobre(b, a)

Pergunta: alicerce(X)

A

B

C

Exemplo de resolução SLDNF (2)Exemplo de resolução SLDNF (2)

alicerce(X)

sobre(Y0, X), no_chao(X)

no_chao(b)

naf(fora_do_chao(b))

fora_do_chao(b)

sobre(b, Y0)

FF

no_chao(a)

naf(fora_do_chao(a))

fora_do_chao(a)

sobre(a, Y0)

FF

Pergunta: naf(sobre(X, Y)) “Quais são os blocos X e Y em que X não está sobre Y?”

Resposta: Nenhuma (stuck)... Esta situação chama-se floundering.

Limitações da resolução SLDNFLimitações da resolução SLDNF

sobre(X, Y)

sobre(c, b)

naf(sobre(X, Y))

??? sobre(b, a)

A

B

C

X=c, Y=b* X=b, Y=a*

* Não são uma substituição-resposta computada vazia...

Limitações da resolução SLDNF (2)Limitações da resolução SLDNF (2)

Mais exemplos:

termina(X) naf(em_loop(X))em_loop(X) em_loop(X)

mulher(X) naf(homem(X))homem(X) naf(mulher(X))

termina(X)

naf(em_loop(X))

em_loop(X)

em_loop(X)

mulher(X)

naf(homem(X))

homem(X)

naf(mulher(X))

Resolução SLG:Resolução SLG:programação em lógica tabeladaprogramação em lógica tabelada

Pilha de objetivos substituída por tabela de objetivos e respostas; Para cada objetivo, tabela guarda:

Ponteiro para objetivo que o chamou; Ponteiro para alguma variação sua:

Renomeação de variáveis, por exemplo p(f(X),Y) p(f(A),B); Cláusula instanciada cuja conclusão unifica com o referido objetivo; Posição da clásusula no programa; Todas as suas respostas.

gid goal vg cg instantiated rule rn answers

1a anc(A,dan) anc(A,dan) :- parent(A,dan) C1

2a parent(A,dan) 1a parent(fay,dan) C3 A = fay

Resolução SLG:Resolução SLG:programação em lógica tabelada (2)programação em lógica tabelada (2)

Para provar objetivo G: Procura por variação G’ na tabela; Se há alguma, utiliza resposta de G´ como resposta de G Senão, encadeia para trás G, de modo a obter a primeira resposta para G; Depois de encontrar tal resposta (ou falhar) :

Armazena-a na tabela; Faz backtrack para encontrar outras respostas e também armazená-las; Continua a prova com a próxima premissa para o objetivo de chamada.

gid goal vg cg instantiated rule rn answers

1a anc(A,dan) anc(A,dan) :- parent(A,dan) C1

2a parent(A,dan) 1a parent(fay,dan) C3 A = fay

AbduçãoAbdução

Programa loc(P, X, Y, T+1) loc(P, X, Y, T) move(P, X+1, Y, T) mureta(X+1, Y) loc(player_1, 4, 1, 1) move(player_1, 5, 1, 1)

Observação loc(player_1, 4, 1, 2)

IC false loc(P,X,Y,T) mureta(X, Y)

Explicação mureta(5, 1)

Aplicações práticas da abdução em IAAplicações práticas da abdução em IA

Diagnóstico de Falha (Diagnóstico médico): P : descreve o comportamento “normal” do sistema; O : comportamento que está anormal; E : componente anormal que explica esse comportamento anormal do

sistema.

Visão de Alto Nível: O : descrições parciais dos objetos; E : são os objetos a serem reconhecidos.

Raciocínio Default: O : conclusões; E : suposições acreditadas por default .

Planejamento: O : estado a ser alcançado; E : planos .

Viés sobre hipóteses abdutivas: objetivosViés sobre hipóteses abdutivas: objetivos E – um conjunto de átomos que explicam O; Viés restringe explicações:

Encontrar explicações que atendam a restrições de integridade;Encontrar causas mais profundas (básicas), no lugar de causas

intermediárias, efeitos dessas causas profundas;Encontrar um número mínimo de causas que expliquem o máximo de

observações;Considerar apenas instâncias de um conjunto pré-definido de

predicados chamado de abduzíveis. Geralmente escolhidos dentro dos predicados sem definição intencional na base de

conhecimento Podem ser priorizados em níveis de preferências

Viés sobre hipóteses abdutivas:Viés sobre hipóteses abdutivas:causas básicas e mínimascausas básicas e mínimas

Exemplo:

grama-molhada choveu-ontem-noitegrama-molhada regador-ligadosapatos-molhados grama-molhada

Para a observação sapatos-molhados : Causas básicas

{grama-molhada} não é básica{choveu-ontem-noite} e {regador-ligado} são básicas.

Causas mínimas{choveu-ontem-noite, regador-ligado} não é mínima. {choveu-ontem-noite} e {regador-ligado} são mínimas.

Viés sobre hipóteses abdutivas: Viés sobre hipóteses abdutivas: restrições de integridaderestrições de integridade

Excluir hipóteses que: Violam diretamente um conjunto pré-definido de restrições de integridades Cuja inclusão na base de conhecimento permite deduzir fatos que violam uma

dessas restrições Exemplo:

At(Wumpus(x)) At(Wumpus(y)) x = ysprinkler choveu false

Viés sobre hipóteses abdutivas: Viés sobre hipóteses abdutivas: minimizaçãominimização

Excluir conjunto de hipóteses que podem ser explicadas em termos de (i.e., deduzidas a partir de) outras hipóteses igualmente válidas Exemplo: grassIsWet, quando sabemos sprinkler-was-on

Preferir conjunto de hipóteses com maior número de efeitos observados (corroboração) Exemplo: formigasDeAsas corrobora chuva e não sprinkler

Preferir conjunto de hipóteses mais geral Preferir conjunto de hipóteses mais conciso: quanto menos pre-

requisitos, mais plausível é que as hipóteses sejam verdade.

PALP – Positive Abductive Logic ProgramPALP – Positive Abductive Logic Program

Uma teoria Abductive Logic Program é uma tripla (P, A, I), onde: P é o programa A são os predicados abduzíveis I são as restrições de integridade

Se tivermos um goal G e (um subconjunto de A que possui explicações para G): P U |= G P U |= I P U é consistente

PALPs: sintaxe abstrataPALPs: sintaxe abstrata

CFOLFunctionalTerm

CFOLAtomicFormula

PALP

Functor =

PALPPremisse

Functor =

Premisse

Conclusion

Positive Abductive Logic Program

**PALPClause

Fact

context IntegrityConstraint inv IC: Conclusion.CFOLAtomicFormula.CFOLTerm = false

context Fact inv Fact: Premisse -> size() = 1 andPremisse.CFOLAtomicFormula.CFOLTerm = true

PredicateSymbolCFOLTerm

CFOLNonFunctionalTerm

Arg1..*

FunctionSymbolConstantSymbolCFOLVariable

Functor

Functor*

IntegrityConstraint

Abducible

context PALPClause inv Abducibles: not Conclusion.isKindOf(Abducible)

Semântica declarativa de PALPSemântica declarativa de PALP

Modelo Estável Generalizado: Programa abdutivo (P,A,I), onde um subconjunto de A M() é um modelo estável generalizado de (P,A,I), sse:

M() é um modelo estável de P , e M() ╞ I

é uma explicaçaõ abdutiva de uma observação Q sse: M() é um modelo estável generalizado de (P,A,I), e M() ╞ Q

Exemplo 1: Seja P: p a

q b Seja A = {a, b} Seja I = p q Seja Q = p Então M(1)={a, p} e M(2)={a,b,p,q} são Modelos Estáveis Generalizados

de (P,A,I). Portanto 1 = {a} e 2 = {a,b} são hipóteses abdutivas de p.

Semântica declarativa de PALP (2)Semântica declarativa de PALP (2) Exemplo 2: O = faulty(a) . A = broken, fuse, melted_fuse

(1.1) faulty(L) lamp(L), broken(L).(1.2) faulty(L) lamp(L), current_break(L).(1.3) current_break(L) fuse(L, F), melted_fuse(F).(1.4) current_break(L) general_power_failure.(1.5) lamp(a).(1.6) lamp(b).

Temos: M(1) = {broken(a), lamp(a), faulty(a)} para 1 = {broken(a)} M(2) = {fuse(a, ), melted_fuse(), current_break(a), lamp(a), faulty(a)} para 2 = {fuse(a,

), melted_fuse()} M(3) = {current_break(a), lamp(a), general_power_failure} não é um modelo estável

generalizado para 3 = {general_power_failure}

SLDA – Semântica operacional de PALPSLDA – Semântica operacional de PALP SLDA é uma extensão de SLD para abdução, onde um conjunto de fórmulas

atômicas é suposto verdadeiro para conseguir O dado P: P + E |- O

SLDA constrói uma refutação: <G0, 0>, ..., <Gi, i>, ..., <Gn, n> Onde passos ou de resolução ou de abdução são utilizados para gerar cada

conjunto. Para o exemplo, A = {broken, fuse, melted_fuse, general_power_failure}

(1.1) faulty(L) lamp(L), broken(L).(1.2) faulty(L) lamp(L), current_break(L).(1.3) current_break(L) fuse(L, F), melted_fuse(F).(1.4) current_break(L) general_power_failure.(1.5) lamp(a).(1.6) lamp(b).

SLDA – Semântica operacional de PALPSLDA – Semântica operacional de PALP

Faulty(a)

Lamp(a), broken(a) Lamp(a), current_break(a)

(1.1)

(1.2)

broken(a)

(1.5)

(i) = {broken(a)}

(1.5)

current_break(a)

(1.4)

general_power_failure

(iv) = {general_power_failure}

(1.3)

fuse(a, F), melted_fuse(F)

(ii) = {fuse(a, }

melted_fuse(F)

Transformar GLPs em PALPsTransformar GLPs em PALPs

Transformar GLP P em PALP <P*, A*, I*>: p P, definir novo predicado p* dual negado de p A* = {p* | pP} P* = P com todos os literais naf p substituidos por p* I* = {(p p*) | pP, p* A*} {p p* | pP, p* A*}

I não é uma restrição de integridade de Horn. É uma fórmula clássica da lógica de primeira ordem

GALP – General Abductive Logic ProgramGALP – General Abductive Logic Program

Conjunto de abduzíveis pode conter predicados negados por falha Interpretação abdutiva de NAF:

Literais negados com naf são hipóteses abdutivas negativas Válidas se satisfazem um conjunto de restrições de integridades

Melhor compreendido através da semântica operacional: SLDNFA

SLDNFA – Semântica operacional de GALPSLDNFA – Semântica operacional de GALP

SLDNFA é similar a SLDA, derivando nos passos de refutação: Se um goal é positivo, ele funciona como SLDA Se um goal é negativo, ele apenas adota o passo de resolução e não o

passo de abdução. A árvore de falha (que é do SLD) de um literal negativo deve ser

reconsiderada toda vez que um passo de abdução adiciona um predicado abduzível a

Raciocínio por Raciocínio por defaultdefault como abdução como abdução

Tanto regras default quando predicados abduzíveis são maneiras de completar uma base de conhecimento certo parcial com conhecimento incerto

Podemos chegar a mesma conclusão com uma máquina de inferência abdutiva, inserindo um novo predicado que representa a regra default.

O novo predicado é abduzível E uma nova regra é inserida na base, de onde podemos concluir por abdução

(A1) abducible(ave-voa)(C1) voa(X) ave(X)(C2) ave(X) pinguim(X)(C3) ¬voa(X) pinguim(X)(C4) ave(picolino)(C5) ave-voa(x)(C6) voa(x) ave(X) ave-voa(x)

voa(picolino)

Chegamos a mesma conclusão por abdução

Abdução em CHRAbdução em CHR

Seja um programa abdutivo (P, A, I), sua transformação em um programa CHR C(P, A, I) é: Para cada p P | p é intencional, escrevemos uma regra de simplificação,

chamada Regra de Definição de p. Exemplo:

parent(P, C) father(P, C).parent(P, C) mother(P, C).

Se torna:

parent(P, C) father(P, C) mother(P, C)

Para cada p P | p é extencional, escrevemos uma regra de propagação, chamada Regra de Fechamento de p. Exemplo:

father(P, C).

father(P, C) (P=john C=mary) (P=john C=peter)

Se torna:

Abdução em CHRAbdução em CHR (2)(2)

CP tem uma regra de propagação chamada Regra de Introdução Extensional, listando todos os fatos de todos os predicados extensionais.

Exemplo:

facts father(john, mary) father(john, peter) mother(jane, mary) person(john, male)...

Restrições de Integridade são regras de propagação. Exemplo:

father(F1, C) father(F2, C) F1 = F2.

A Regra de Fechamento é deixada de lado quando o predicado é abduzível

Exemplo de abdução em CHRExemplo de abdução em CHR

john (male) jane (female)

peter (male) mary (female)paul (male)

paipai mãe

Exemplo de abdução em CHRExemplo de abdução em CHR (2) (2)% Definition RulesR1@ parent(P,C) father(P,C) mother(P,C).R2@ sibling(C1,C2) C1≠C2 parent(P,C1) parent(P,C2).

% Extensional Introduction RuleR3@ facts father(john, mary) father(john, peter) mother(jane, mary) person(john, male) person(peter,male) person(jane,female) person(mary,female) person(paul,male).

% Closing RulesR4@ father(X,Y) (X=john Y=mary) (X=john Y=peter).R5@ mother(X,Y) (X=jane Y=mary).R6@ person(X,Y) (X=john Y=male) (X=peter Y=male) (X=jane Y=female) (X=mary Y=female) (X=paul Y=male).

% Integrity ConstraintsR7@ father(F1,C) father(F2,C) F1=F2.R8@ mother(M1,C) mother(M2,C) M1=M2.R9@ person(P,G1) person(P,G2) G1=G2.R10@ father(F,C) person(F,male) person(C,S).R11@ mother(M,C) person(F,female) person(C,G).

Exemplo de abdução em CHRExemplo de abdução em CHR (3) (3)

Sejam father e mother abduzíveis. G = sibling(paul, mary)

R1@ parent(P,C) father(P,C) mother(P,C).R2@ sibling(C1,C2) C1≠C2 parent(P,C1) parent(P,C2).R6@ Person(X,Y) (X=john Y=male) (X=peter Y=male) (X=jane

Y=female) (X=mary Y=female) (X=paul Y=male).R7@ father(F1,C) father(F2,C) F1=F2.R8@ mother(M1,C) mother(M2,C) M1=M2.R9@ person(P,G1) person(P,G2) G1=G2.R10@ father(F,C) person(F,male) person(C,S).R11@ mother(M,C) person(F,fmale) person(C,G).

Exemplo de abdução em CHRExemplo de abdução em CHR (4) (4)Rule RDCS BICS

r2 father(john, mary) father(john, peter) mother(jane, mary) person(john, male) person(peter,male) person(jane,female) person(mary,female) person(paul,male) sibling(paul, mary).

true

r1a father(john, mary) father(john, peter) mother(jane, mary) person(john, male) person(peter,male) person(jane,female) person(mary,female) person(paul,male) parent(P, paul) parent(P, mary).

paul≠mary ^true

r1a father(john, mary) father(john, peter) mother(jane, mary) person(john, male) person(peter,male) person(jane,female) person(mary,female) person(paul,male) person(mary,female) person(paul,male) father(P, paul) parent(P, mary).

paul≠mary ^true

r7 father(john, mary) father(john, peter) mother(jane, mary) person(john, male) person(peter,male) person(jane,female) person(mary,female) person(paul,male) person(mary,female) person(paul,male) father(P, paul) father(P, mary).

paul≠mary ^true

father(john, mary) father(john, peter) mother(jane, mary) person(john, male) person(peter,male) person(jane,female) person(mary,female) person(paul,male) person(mary,female) person(paul,male) father(P, paul) father(P, mary).

paul≠mary ^ P=john ^ true

Revisão de crenças: manutenção de verdadeRevisão de crenças: manutenção de verdade

Quando fazer revisão de crenças Fatos deduzidos se mostram incorretos em face de um novo fato recebido.

Utiliza retract(old fact) em decorrência de tell(new fact).

Porém, surge o problema da manutenção da verdade.

O que foi deduzido a partir do fato retirado, tem que ser por sua vez retirado.

Sistemas de manutenção de verdade (TMSs) devem resolver essas complicações.

Exemplo:(R1) estaEm(Player,X) segurando(B) estaEm(B,X)(F1) estaEm(player_1,5)

(F2) segurando(bola)

(F3) estaEm(bola,5) // F1 e F2

tell(BC,estaEm(player_1,6))

retract(BC,estaEm(player_1,5))

Precisamos retrair também estaEm(bola,5)

Revisão de crenças:Revisão de crenças:manutenção de verdade (2)manutenção de verdade (2)

Sistemas de manutenção de verdadeSistemas de manutenção de verdade

Resolvedor de problemas

Base de Conhecimento

TMS

NósNogoods

Estado de Crenças

Inferências

Cada inferência realizada pelo resolvedor é informada ao TMS e armazenada como uma justificativa ( p p1,...,pn )

Um TMS registra nogoods que expressam suposições(q1,...,qn) que não devem ocorrer juntas ( ¬ [q1,...,qn] )

O TMS deve determinar que proposições podem ser derivadas do conjunto de justificativas sem violar os nogoods.

JTMS - Manutenção da verdadeJTMS - Manutenção da verdadebaseada em justificativabaseada em justificativa

Abordagem JTMS (Justification-Based Truth Maintenance System): Cada proposição na KB é anotada com uma justificativa (as proposições

a partir da qual ela foi inferida)

P P1,...,Pn, ~Pn+1,...,~Pm

Cada proposição é rotulada IN ou OUT

P pode ser derivado(é IN - esta em KB) se P1,...,Pn podem ser derivados(são IN) e Pn+1,...,Pm (são OUT - não estão em KB) não podem ser derivados

Exemplo de JTMSExemplo de JTMS

Atualização de rótulos

p ~q q ~r

p q r

OUT IN OUT

JTMS é informado que p é verdadeiro



p ~q q ~r

p q r

OUT IN OUT

IN




p ~q q ~r

p q r

OUT IN OUT

IN OUT




p ~q q ~r

p q r

OUT IN OUT

IN OUT IN




p ~q q ~r

p q r

OUT IN OUT

IN OUT IN

JTMS informa ao resolvedor de problemas o novo estado de crenças:P – IN, q – OUT e r - IN

JTMS e abduçãoJTMS e abdução

p q r ~qq ~r

nogood = pConjuntoIN_1 = {p,q}ConjuntoIN_2 = {r}

JTMS como um programa abdutivo com abordagem do naf

Justificativas = cláusulas do programa

~pn = naf pn

nogood = IC

JTMS e abdução (2)JTMS e abdução (2)

p q r ~qq ~r

nogood = pConjuntoIN_1 = {p,q}ConjuntoIN_2 = {r}

p q r naf(q)q naf(r)

É possível utilizar a semântica declarativa de GALPs para entender o significado de um JTMS.

IC = pME1 = {p,q}ME2 = {r}

ATMS - Manutenção da verdadeATMS - Manutenção da verdadebaseada em suposiçãobaseada em suposição

Abordagem ATMS (Assumption-Based Truth Maintenance System): Cada proposição na BC é anotada com um conjunto de justificativas

(cada justificativa é um conjunto de proposições que torna verdade a proposição)

P Q1,...,Qn

P R1,...,Rn

P é derivado se Q1,...,Qn são derivados ou R1,...,Rn são derivados

Quando o contexto é alterado, para saber se um fato é ou não acreditado basta verificar se um dos conjuntos de suas proposições está contido no contexto

Contexto: tudo o que é acreditado no momento.

Exemplo de ATMSExemplo de ATMS

Exemplo

1. p a,b2. p b,c,d3. q a,c4. q d,eNogood (a,b,e)

Nova justificativa r p,q

ATMS registrará: r a,b,c // 1 e 3 | é registrado r b,c,d,e // 2 e 4 | é registrado r a,b,d,e // 1 e 4 | Nogood (a,b,e) r a,b,c,d // 2 e 3 | tem o mesmo valor de r a,b,c

ATMS e abduçãoATMS e abdução

1. Dado: Programa lógico abdutivo P (P é um PALP); Efeito observado G; Conjunto de hipóteses abdutivas Δ; Restrições de integridade I.

2. Tem-se: P U Δ |= G; P U G satisfaz I.

3. Similar ao registro computado pelo ATMS: G Δ

Exemplo: r a,b,c r a b c

JTMS X ATMSJTMS X ATMS

Rótulos dos nós JTMS Acreditado ou Não acreditado (IN ou OUT). ATMS Conjunto de conjuntos mínimos de nós que devem estar contidos no

contexto para o nó ser acreditado. Tratamento de múltiplas alternativas

JTMS É necessário acrescentar ou remover premissas e depois tornar a calcular todos os rótulos dos nós da rede.

ATMS Altera-se o contexto, que representa aquilo em que se acredita, e para saber se se acredita num nó basta ver se um dos conjuntos de nós do seu rótulo está contido no contexto. Neste aspecto, é muito melhor do que o JTMS.

ConclusãoConclusão

Raciocínio por default e revisão de crenças baseada em manutenção de verdade podem ser vistos como casos particulares de abdução.

Abdução pode ser implementada em CHRV.

Raciocínio por default e revisão de crenças podem ser implementados em CHRV, se devidamente mapeados para o framework abdutivo!!

Documents

Abdução, Raciocínio por default e Revisão de crenças