Programação lógica abdutiva

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

A programação lógica abdutiva ( ALP ) é uma estrutura de representação de conhecimento de alto nível que pode ser usada para resolver problemas declarativamente com base no raciocínio abdutivo . Ele estende a programação lógica normal , permitindo que alguns predicados sejam definidos de forma incompleta, declarados como predicados abdutíveis. A resolução de problemas é efetuada derivando hipóteses sobre esses predicados abdutíveis (hipóteses abdutivas) como soluções de problemas a serem resolvidos. Esses problemas podem ser observações que precisam ser explicadas (como na abdução clássica) ou objetivos a serem alcançados (como na programação lógica normal ). Pode ser usado para resolver problemas de diagnóstico, planejamento , linguagem natural eaprendizado de máquina . Também tem sido usado para interpretar a negação como fracasso como uma forma de raciocínio abdutivo.

Sintaxe

Programas de lógica abdutiva têm três componentes,Onde:

  • P é um programa lógico exatamente da mesma forma que na programação lógica
  • A é um conjunto de nomes de predicados, chamados de predicados abdutíveis
  • IC é um conjunto de fórmulas clássicas de primeira ordem.

Normalmente, o programa lógico P não contém nenhuma cláusula cujo núcleo (ou conclusão) se refira a um predicado abdutível. (Esta restrição pode ser feita sem perda de generalidade.) Também na prática, muitas vezes, as restrições de integridade em IC são muitas vezes restritas à forma de negações, ou seja, cláusulas da forma:

   falso:- A1,...,An, não B1, ..., não Bm.

Tal restrição significa que não é possível que todos A1,...,An sejam verdadeiros e ao mesmo tempo todos B1,...,Bm sejam falsos.

Significado informal e resolução de problemas

As cláusulas em P definem um conjunto de predicados não abdutíveis e através disso fornecem uma descrição (ou modelo) do domínio do problema. As restrições de integridade em CI especificam propriedades gerais do domínio do problema que precisam ser respeitadas em qualquer solução de um problema.

Um problema, G , que expressa uma observação que precisa ser explicada ou um objetivo que é desejado, é representado por uma conjunção de literais positivos e negativos (NAF). Tais problemas são resolvidos calculando "explicações abdutivas" de G .

Uma explicação abdutiva de um problema G é um conjunto de instâncias básicas positivas (e às vezes também negativas) dos predicados abdutíveis, de modo que, quando estes são adicionados ao programa lógico P, o problema Ge as restrições de integridade IC ambas são válidas. Assim, as explicações abdutivas estendem o programa lógico P pela adição de definições totais ou parciais dos predicados abdutíveis. Desta forma, explicações abdutivas formam soluções do problema de acordo com a descrição do domínio do problema em P e IC. A extensão ou complementação da descrição do problema dada pelas explicações abdutivas fornece novas informações, até então não contidas na solução do problema. Critérios de qualidade para preferir uma solução a outra, muitas vezes expressos por meio de restrições de integridade, podem ser aplicados para selecionar explicações abdutivas específicas do problema G .

A computação em ALP combina o raciocínio inverso da programação lógica normal (para reduzir problemas a subproblemas) com um tipo de verificação de integridade para mostrar que as explicações abdutivas satisfazem as restrições de integridade.

Os dois exemplos a seguir, escritos em inglês estruturado simples e não na sintaxe estrita do ALP, ilustram a noção de explicação abdutiva no ALP e sua relação com a resolução de problemas.

Exemplo 1

O programa de lógica abdutiva,, Tem emas seguintes sentenças:

  A grama está molhada se choveu. 
A grama está molhada se o aspersor estiver ligado.
O sol estava brilhando.

Os predicados abdutíveis emsão "choveu" e "o aspersor estava ligado" e a única restrição de integridade emé:

  falso se choveu e o sol estava brilhando.

A observação de que a grama está molhada tem duas explicações potenciais, "choveu" e "o aspersor estava ligado", que implicam na observação. No entanto, apenas a segunda explicação potencial, "o sprinkler estava ligado", satisfaz a restrição de integridade.

Exemplo 2

Considere o programa de lógica abdutiva que consiste nas seguintes cláusulas (simplificadas):

  X é cidadão se X nasceu nos EUA. 
X é cidadão se X nasceu fora dos EUA e X é residente nos EUA e X é naturalizado.
X é um cidadão se X nasceu fora dos EUA e Y é a mãe de X e Y é um cidadão e X está registrado.
Maria é a mãe de João.
Maria é cidadã.

juntamente com os cinco predicados abdutíveis, "nasceu nos EUA", "nasceu fora dos EUA", "é residente nos EUA", "é naturalizado" e "está registrado" e a restrição de integridade:

  false se John for residente dos EUA.

O objetivo "João é cidadão" tem duas soluções abdutivas, uma das quais é "João nasce nos EUA", a outra é "João nasce fora dos EUA" e "João é registrado". A solução potencial de tornar-se cidadão por residência e naturalização falha porque viola a restrição de integridade.

Um exemplo mais complexo que também está escrito na sintaxe mais formal do ALP é o seguinte.

Exemplo 3

O programa de lógica abdutiva abaixo descreve um modelo simples do metabolismo da lactose da bactéria E. coli. O programa, P , descreve (em sua primeira regra) que a E. coli pode se alimentar do açúcar lactose se produzir duas enzimas permease e galactosidase. Como todas as enzimas, estas são produzidas se forem codificadas por um gene (Gene) que é expresso (descrito pela segunda regra). As duas enzimas de permease e galactosidase são codificadas por dois genes, lac(y) e lac(z) respectivamente (indicados na quinta e sexta regra do programa), em um agrupamento de genes (lac(X)) – chamado de operon – que é expresso quando as quantidades (amt) de glicose são baixas e lactose são altas ou quando ambas estão em nível médio (ver quarta e quinta regra). Os abdutíveis, A, declare todas as instâncias básicas dos predicados "quantidade" como assumidas. Isso reflete que no modelo as quantidades em qualquer momento das várias substâncias são desconhecidas. Esta é uma informação incompleta que deve ser determinada em cada caso de problema. As restrições de integridade, IC , afirmam que a quantidade de qualquer substância (S) pode assumir apenas um valor.

Conhecimento de domínio (P)
   alimentação ( lactose )  :-  make ( permese ),  make ( galactosidase ). 
   make ( Enzima )  :-  código ( Gene ,  Enzima ),  expresso ( Gene ). 
   expresso ( lac ( X ))  :-  quantidade ( glicose ,  baixa ),  quantidade ( lactose ,  hi ). 
   expresso ( lac ( X )) :-  quantidade ( glicose ,  média ),  quantidade ( lactose ,  média ). 
   código ( lac ( y ),  permease ). 
   código ( lac ( z ),  galactosidase ). 
   temperatura ( baixa )  : -  quantidade ( glicose ,  baixa ).
Restrições de integridade (IC)
   false  :-  quantidade ( S ,  V1 ),  quantidade ( S ,  V2 ),  V1   V2 .
Abducíveis (A)
   abducible_predicate ( quantidade ).

O objetivo do problema é. Isso pode surgir como uma observação a ser explicada ou como um estado de coisas a ser alcançado ao encontrar um plano. Esse objetivo tem duas explicações abdutivas:

A decisão de qual dos dois adotar pode depender da informação adicional disponível, por exemplo, pode-se saber que quando o nível de glicose está baixo o organismo apresenta um determinado comportamento – no modelo essa informação adicional é que a temperatura do organismo é baixo – e observando a verdade ou falsidade disso é possível escolher a primeira ou a segunda explicação respectivamente.

Uma vez que uma explicação foi escolhida, ela se torna parte da teoria, que pode ser usada para tirar novas conclusões. A explicação e, mais geralmente, essas novas conclusões formam a solução do problema.

Semântica formal

A semântica formal da noção central de uma explicação abdutiva em ALP pode ser definida da seguinte maneira.

Dado um programa de lógica abdutiva,, uma explicação abdutiva para um problemaé um conjuntode átomos de terra em predicados abdutíveis tais que:

  • é consistente

Esta definição deixa em aberto a escolha da semântica subjacente da programação lógica através da qual damos o significado exato da relação de implicaçãoe a noção de consistência dos programas lógicos (estendidos). Qualquer uma das diferentes semânticas da programação lógica, como a semântica de conclusão, estável ou bem fundamentada, pode (e tem sido usada na prática) para fornecer diferentes noções de explicações abdutivas e, portanto, diferentes formas de estruturas ALP.

A definição acima tem uma visão particular sobre a formalização do papel das restrições de integridadecomo restrições às possíveis soluções abdutivas. Requer que estes sejam implicados pelo programa lógico estendido com uma solução abdutiva, significando assim que em qualquer modelo do programa lógico estendido (que se pode pensar como um mundo resultante dado) os requisitos das restrições de integridade são atendidos. Em alguns casos, isso pode ser desnecessariamente forte e o requisito mais fraco de consistência, ou seja, queé consistente, pode ser suficiente, significando que existe pelo menos um modelo (possível mundo resultante) do programa estendido onde as restrições de integridade são válidas. Na prática, em muitos casos, essas duas formas de formalizar o papel das restrições de integridade coincidem, pois o programa lógico e suas extensões sempre têm um modelo único. Muitos dos sistemas ALP usam a visão de vinculação das restrições de integridade, pois isso pode ser facilmente implementado sem a necessidade de procedimentos extras especializados para a satisfação das restrições de integridade, uma vez que essa visão trata as restrições da mesma maneira que o objetivo do problema.

Implementação e sistemas

A maioria das implementações do ALP estende o modelo computacional de programação lógica baseado em resolução SLD. O ALP também pode ser implementado por meio de seu link com Answer Set Programming (ASP), onde os sistemas ASP podem ser empregados. Exemplos de sistemas da primeira abordagem são ACLP, A-system, CIFF, SCIFF, ABDUAL e ProLogICA.

Veja também

Notas

Referências

  • Poole, D.; Goebel, R.; Aleliunas, R. (1987). "Teórico: um sistema de raciocínio lógico para padrões e diagnóstico" . Em Cercone, Nick; McCalla, Gordon (eds.). A Fronteira do Conhecimento: Ensaios na Representação do Conhecimento . Springer. pp. 331-352. ISBN 978-0-387-96557-4.
  • Kakas, AC; Mancarella, P. (1990). "Modelos estáveis ​​generalizados: uma semântica para abdução". Em Aiello, LC (ed.). ECAI 90: anais da 9ª Conferência Europeia de Inteligência Artificial . Pitman. págs. 385-391. ISBN 978-0273088226.
  • Consola, L.; Dupre, DT; Torasso, P. (1991). "Sobre a relação entre rapto e dedução". Jornal de Lógica e Computação . 1 (5): 661-690. CiteSeerX  10.1.1.31.9982 . doi : 10.1093/logcom/1.5.661 .
  • Kakas, AC; Kowalski, RA; Toni, F. (1993). "Programação Lógica Abdutiva". Jornal de Lógica e Computação . 2 (6): 719-770. CiteSeerX  10.1.1.37.3655 . doi : 10.1093/logcom/2.6.719 .
  • Denecker, Marc; De Schreye, Danny (Fevereiro de 1998). "SLDNFA: Um procedimento abdutivo para programas de lógica abdutiva". Jornal de Programação Lógica . 34 (2): 111–167. CiteSeerX  10.1.1.21.6503 . doi : 10.1016/S0743-1066(97)00074-5 .
  • Denecker, M.; Kakas, AC (julho de 2000). "Edição especial: programação lógica abdutiva" . Jornal de Programação Lógica . 44 (1–3): 1–4. doi : 10.1016/S0743-1066(99)00078-3 .
  • Denecker, M.; Kakas, AC (2002). "Abdução em Lógica de Programação" . Em Kakas, AC; Sadri, F. (eds.). Lógica Computacional: Programação Lógica e Além: Ensaios em Honra de Robert A. Kowalski . Notas de aula em Ciência da Computação. Vol. 2407. Springer. págs. 402-437. ISBN 978-3-540-43959-2.
  • Poole, D. (1993). "Abdução de chifre probabilística e redes Bayesianas" (PDF) . Inteligência Artificial . 64 (1): 81–129. doi : 10.1016/0004-3702(93)90061-F .
  • Esposito, F.; Ferilli, S.; Basile, TMA; Di Mauro, N. (Fevereiro de 2007). "Inferência de teorias de abdução para lidar com incompletude na aprendizagem de primeira ordem" (PDF) . Conhecimento Inf. Sist . 11 (2): 217–242. doi : 10.1007/s10115-006-0019-5 . S2CID  10699982 . Arquivado do original (PDF) em 17/07/2011.

Links externos