Programação em lógica indutiva

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Ambox important.svg
Foram assinalados vários aspectos a serem melhorados nesta página ou se(c)ção:

Programação em lógica indutiva (ILP) é uma subárea de aprendizado de máquina que utiliza lógica de programação como uma representação uniforme para exemplos, conhecimentos prévios e hipóteses. Dada uma codificação do conhecimento prévio e um conjunto de exemplos representados como um banco de dados lógico de fatos, um sistema ILP irá derivar um programa de lógica hipotetizado que envolve todos os exemplos positivos e nenhum dos exemplos negativos.

  • Esquema: exemplos positivos + exemplos negativos + conhecimento prévio ⇒ hipótese.

Programação em lógica indutiva é particularmente útil em bioinformática e processamento de linguagem natural. Gordon Plotkin e Ehud Shapiro definiram a fundamentação teórica inicial para aprendizagem de máquina indutiva sob um ponto de vista lógico.[1][2][3] Shapiro construiu sua primeira implementação em 1981:[4] um programa em Prolog que indutivamente inferia programas lógicos a partir de exemplos positivos e exemplos negativos. O termo Programação em lógica indutiva foi introduzido pela primeira vez[5] em um artigo publicado por Stephen Muggleton, em 1991.[6] Muggleton também fundou a conferência internacional sobre Programação em lógica indutiva, introduziu as idéias teóricas de Invenção de Predicado, Resolução inversa,[7] e Implicação Inversa.[8] Muggleton implementou Implicação Inversa primeiramente no sistema PROGOL. O termo "indutivo" aqui refere-se ao filosófico (por exemplo, sugerindo uma teoria para explicar fatos observados), ao invés do matemático (por exemplo, a prova de propriedade para todos os membros de um conjunto ordenado).

Definição Formal[editar | editar código-fonte]

O conhecimento de background é dado como uma teoria lógica B, comumente na forma de cláusulas de Horn usado em lógica de programação. Os exemplos positivos e o negativos são fornecidos como uma conjunção de e de  literais não-negados e negados, respectivamente. Uma hipótese correta h é uma proposição lógica que satisfaz os seguintes requisitos.[9]

"Necessidade" não impõe uma restrição sobre h, mas proíbe qualquer geração de uma hipótese, enquanto os fatos positivos são explicáveis sem ela. "Suficiência" requer que qualquer hipótese gerada h explique todos os exemplos positivos ."A Consistência fraca" proíbe a geração de qualquer hipótese h que contradiz o conhecimento prévio B. "Consistência forte" também proíbe a geração de qualquer hipótese h que é inconsistente com os exemplos negativos , dado o conhecimento prévio B; isso implica "Consistência fraca"; se nenhum exemplo negativo é dado, ambas as exigências coincidem. Džeroski [10] exige apenas "Suficiência" (chamado de "Completude" lá) e "Consistência forte".

Exemplo[editar | editar código-fonte]

Relações familiares assu na secção "Exemplo"

O seguinte exemplo bem conhecido sobre o aprendizado de definições das relações familiares usa as abreviações:

, , , , , , , , and .

Ele começa a partir do conhecimento prévio (imagem)

,

dos exemplos positivos

,

e da proposição trivial

para indicar a ausência de exemplos negativos.

A abordagem de "generalização relativa menos geral (rlgg)" de Plotkin[11][12] para Programação em Lógica Indutiva deve ser utilizada para obter uma sugestão sobre como definir formalmente a relação filha .

Esta abordagem utiliza os seguintes passos.

  • Relativizar cada exemplo de literal positivo com o conhecimento prévio completo:
    ,
  • Converter para forma normal conjuntiva:
    ,
  • Anti-unificar cada par compatível [13] [14] de literais:
    • de  e ,
    • de  e ,
    • de  e ,
    • de  e , similar para qualquer outro literal de conhecimento prévio:
    • de  e , e muitos mais literais negados
  • Excluir todos os literais negados contendo variáveis que não ocorrem em um literal positivo:
    • Após excluir todos os literais negados contendo outras variáveis além de , somente  resta, juntamente com todos os literais que vieram do conhecimento prévio
  • Converter cláusulas de volta para a forma de Horn:

A cláusula de Horn resultante é a hipótese h obtida pela abordagem rlgg. Ignorando os fatos do conhecimento prévio, a cláusula informalmente lê " é chamada de uma filha de se é o pai de e é feminina", que é uma definição comumente aceita.

Sobre os requisitos acima, "Necessidade" estava satisfeita porque o predicado não aparece no conhecimento prévio, o que, portanto, não implica qualquer propriedade que contém esse predicado, tal como os exemplos positivos. "Suficiência" é satisfeita pela hipótese h, pois, ela juntamente com a partir do conhecimento prévio, implica o primeiro exemplo positivo , e da mesma forma h e a partir do conhecimento prévio implica o segundo exemplo positivo . "A Consistência fraca" é satisfeita por h, pois h detém a estrutura de Herbrand (finita) descrita pelo conhecimento prévio; semelhante para o "Consistência forte".

A definição comum da relação avó, , não pode ser aprendida através da abordagem acima, uma vez que a variável y ocorre somente na cláusula corpo; os literais correspondentes teriam sido eliminados na 4ª etapa da abordagem. Para superar essa falha, que passo tem que ser modificada de tal forma que possa ser parametrizada com diferentes heurística de pós-seleção de literais. Historicamente, a implementação GOLEM é baseada na abordagem rlgg.

Sistema de Programação em Lógica Indutiva[editar | editar código-fonte]

Systema de Programação em Lógica Indutiva é um programa que toma como entrada teorias lógicas  e retorna uma hipótese correta H em relação a essas teorias. Um algoritmo de um sistema de ILP é composto de duas partes: a hipótese de pesquisa e hipótese de seleção. Primeiro uma hipótese é pesquisada com um método de Programação em Lógica Indutiva, em seguida, um subconjunto das hipóteses encontradas (na maioria dos sistemas, uma hipótese) é escolhido por um algoritmo de seleção. Um algoritmo de seleção de pontua cada um das hipóteses e devolve aquelas com a maior pontuação. Um exemplo de função de pontuação inclue compactação mínima de comprimento onde de uma hipótese com uma menor complexidade de Kolmogorov tem a pontuação mais alta e é devolvida. Um sistema de ILP é completa se e somente se para qualquer entrada de teorias lógicas  qualquer hipótese correta H em relação a estas teorias pode ser encontrad com seu método de pesquisa de hipótese.

Pesquisa de Hipótese[editar | editar código-fonte]

Modernos sistemas de ILP como Progol,[6] Hail, [15] e Imparo [16] encontram uma hipótese H, utilizando o princípio da implicação inversa[6] para as teorias B, E, H: Primeiro eles constroem uma teoria intermediária F chamada de uma teoria ponte que satisfaça as condições and . Em seguida, como , eles generalizam a negação da teoria ponte F com a anti-implicação.[17] No entanto, a operação de anti-implicação, sendo altamente não-determinística, é computacionalmente mais cara. Portanto, uma pesquisa de hipótese alternativa pode ser conduzida usando a operação da inversa de classificação (anti-subsunção), que é menos não-determinística que anti-implicação.

Perguntas sobre completude de uma pesquisa de hipótese específica de um sistema ILP de surgiram. Por exemplo, Progol o método de pesquisa de hipótese com base na regra de inferência da implicação inversa não é completa pelo  exemplo de Yamamoto .[18] por outro lado, Imparo é completa, tanto para o método de anti-implicação [19] quanto para o método de classificação inversa estendida [20]

Implementações[editar | editar código-fonte]

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Plotkin G.D. Automatic Methods of Inductive Inference, PhD thesis, University of Edinburgh, 1970.
  2. Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press, Cambridge, MA, 1991, pp. 199–254.
  3. Shapiro, Ehud Y. (1983). Algorithmic program debugging. Cambridge, Mass: MIT Press. ISBN 0-262-19218-7
  4. Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.
  5. Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. CiteSeerX: 10.1.1.56.1790
  6. a b c Muggleton, S.H. (1991). «Inductive logic programming». New Generation Computing. 8 (4): 295–318. doi:10.1007/BF03037089 
  7. Muggleton S.H. and Buntine W. "Machine invention of first-order predicate by inverting resolution","Proceedings of the 5th International Conference on Machine Learning, 1988.
  8. Muggleton S.H., "Inverting entailment and Progol", New Generation Computing, 13:245-286, 1995.
  9. Muggleton, Stephen (1999). «Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic». Artificial Intelligence. 114: 283–296. doi:10.1016/s0004-3702(99)00067-3 ; here: Sect.2.1
  10. Džeroski, Sašo (1996), «Inductive Logic Programming and Knowledge Discovery in Databases», in: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 117–152 ; here: Sect.5.2.4
  11. Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., eds. «A Note on Inductive Generalization». Edinburgh University Press. Machine Intelligence. 5: 153–163 
  12. Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., eds. «A Further Note on Inductive Generalization». Edinburgh University Press. Machine Intelligence. 6: 101–124 
  13. i.e. sharing the same predicate symbol and negated/unnegated status
  14. in general: n-tuple when n positive example literals are given
  15. Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.
  16. Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.
  17. Yoshitaka Yamamoto, Katsumi Inoue, and Koji Iwanuma. Inverse subsumption for complete explanatory induction. Machine learning, 86(1):115–139, 2012.
  18. Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.
  19. a b Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.
  20. David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836
  21. Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). «ProGolem: a system based on relative minimal generalization» (PDF). ILP 
  22. Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). «Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study» (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162 

Ler mais[editar | editar código-fonte]