Mostrar código-fonte de Programação em lógica indutiva

{{Multitag|mnot|p1=tec|data=dezembro de 2016}}
'''Programação em lógica indutiva&nbsp;'''('''ILP''') é uma subárea de [[aprendizado de máquina]] que utiliza [[Programação lógica|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&nbsp;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''&nbsp;&#x21D2; ''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.<ref>Plotkin G.D. Automatic Methods of Inductive Inference, PhD thesis, University of Edinburgh, 1970.</ref><ref>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.</ref><ref>Shapiro, Ehud Y. (1983). ''Algorithmic program debugging''. Cambridge, Mass: MIT Press. ISBN 0-262-19218-7</ref> Shapiro construiu sua primeira implementação em 1981:<ref>Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.</ref> 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<ref>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]]: {{url|1=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1790|2=10.1.1.56.1790}}</ref> em um artigo publicado por Stephen Muggleton, em 1991.<ref name="muggleton1995inverse">{{citar periódico|último1 = Muggleton |primeiro1 = S.H. |título= Inductive logic programming | doi = 10.1007/BF03037089 |periódico= New Generation Computing | volume = 8 |número= 4 |páginas= 295–318 |ano= 1991 | pmid =  | pmc = }}</ref> 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,&nbsp;Resolução inversa,<ref>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.</ref> e Implicação Inversa.<ref>Muggleton S.H., "Inverting entailment and Progol",  New Generation Computing, 13:245-286, 1995.</ref> Muggleton implementou Implicação Inversa primeiramente no sistema&nbsp;PROGOL. O termo "''indutivo''" aqui refere-se ao&nbsp;[[Método indutivo|filosófico]]&nbsp;(por exemplo, sugerindo uma teoria para explicar fatos observados), ao invés do&nbsp;[[Indução matemática|matemático]]&nbsp;(por exemplo, a prova de propriedade para todos os membros de um conjunto ordenado).

== Definição Formal ==
O ''conhecimento de background''&nbsp;é dado como uma teoria lógica B, comumente na forma de [[Cláusula de Horn|cláusulas de Horn]] usado em [[Programação lógica|lógica de programação]]. Os exemplos&nbsp;''positivos'' e o ''negativos''&nbsp;são fornecidos como uma conjunção de <math>E^+</math> e <math>{\displaystyle E^{-}} </math> de &nbsp;[[Literal (lógica matemática)|literais]] não-negados e negados, respectivamente. Uma ''hipótese&nbsp;correta'' h é uma proposição lógica que satisfaz os seguintes requisitos.<ref>{{citar periódico|primeiro1 =Stephen|último1 =Muggleton|título=Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic|periódico=Artificial Intelligence|volume=114|páginas=283–296|ano=1999|doi=10.1016/s0004-3702(99)00067-3}}; here: Sect.2.1</ref>
:[[Entailment#Semantic consequence| <math>\begin{array}{llll} \text{Necessidade:} & B & \not\models & E^+ \\ \text{Suficiência:} & B \land h & \color{blue}{\models} & E^+ \\ \text{Consistência Fraca:} & B \land h & \not\models & \textit{false} \\ \text{Consistência Forte:} & B \land h \land E^- & \not\models & \textit{false} \end{array}</math>]]

"''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&nbsp;h explique todos os exemplos positivos <math>E^+</math>."''A Consistência fraca''" proíbe a geração de qualquer hipótese h que contradiz o conhecimento prévio&nbsp;B.
"''Consistência forte''" também proíbe a geração de qualquer hipótese h que é inconsistente com os exemplos negativos <math>E^-</math>, dado o conhecimento prévio&nbsp;B; isso implica "''Consistência fraca''"; se nenhum exemplo negativo é dado, ambas as exigências coincidem. Džeroski<ref>{{citation|primeiro1 =Sašo|último1 =Džeroski|contribuição=Inductive Logic Programming and Knowledge Discovery in Databases|páginas=117–152|editor-nome1 =U.M.|editor-sobrenome1 =Fayyad|editor-nome2 =G.|editor-sobrenome2 =Piatetsky-Shapiro|editor-nome3 =P.|editor-sobrenome3 =Smith|editor-nome4 =R.|editor-sobrenome4 =Uthurusamy|título=Advances in Knowledge Discovery and Data Mining|publicado=MIT Press|ano=1996}}; here: Sect.5.2.4</ref> exige apenas "''Suficiência''" (chamado de "Completude" lá) e  "''Consistência forte''".

== Exemplo ==
[[Ficheiro:Family_relations_example_for_inductive_logic_programming_article.gif|esquerda|miniaturadaimagem|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:
:<math>\textit{par}: \textit{pai}</math>, <math>\textit{fem}: \textit{feminino}</math>, <math>\textit{dau}: \textit{filha}</math>, <math>g:\textit{George}</math>, <math>h:\textit{Helen}</math>, <math>m:\textit{Mary}</math>, <math>t:\textit{Tom}</math>, <math>n:\textit{Nancy}</math>, and <math>e:\textit{Eve}</math>.
Ele começa a partir do conhecimento prévio (imagem)
:<math>\textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e)</math>,
dos exemplos positivos
:<math>\textit{dau}(m,h) \land \textit{dau}(e,t)</math>,
e da proposição&nbsp;trivial
:<math>\textit{true}</math>
para indicar a ausência de exemplos negativos.

A abordagem de "generalização relativa menos geral (rlgg)" de Plotkin<ref>{{citar periódico|primeiro1 =Gordon D.|último1 =Plotkin|título=A Note on Inductive Generalization|editor-nome1 =B.|editor-sobrenome1 =Meltzer|editor-nome2 =D.|editor-sobrenome2 =Michie|publicado=Edinburgh University Press|periódico=Machine Intelligence|volume=5|páginas=153–163|ano=1970}}</ref><ref>{{citar periódico|primeiro1 =Gordon D.|último1 =Plotkin|título=A Further Note on Inductive Generalization|editor-nome1 =B.|editor-sobrenome1 =Meltzer|editor-nome2 =D.|editor-sobrenome2 =Michie|publicado=Edinburgh University Press|periódico=Machine Intelligence|volume=6|páginas=101–124|ano=1971}}</ref> para Programação em Lógica Indutiva deve ser utilizada para obter uma sugestão sobre como definir formalmente a relação filha <math>\textit{dau}</math>.

Esta abordagem utiliza os seguintes passos.
* Relativizar cada exemplo de literal positivo com o conhecimento prévio completo:
*: <math>\begin{align}
\textit{dau}(m,h) \leftarrow \textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e) \\
\textit{dau}(e,t) \leftarrow \textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e)
\end{align}</math>,
* Converter para&nbsp;[[forma normal conjuntiva]]:
*: <math>\begin{align}
\textit{dau}(m,h) \lor \lnot \textit{par}(h,m) \lor \lnot \textit{par}(h,t) \lor \lnot \textit{par}(g,m) \lor \lnot \textit{par}(t,e) \lor \lnot \textit{par}(n,e) \lor \lnot \textit{fem}(h) \lor \lnot \textit{fem}(m) \lor \lnot \textit{fem}(n) \lor \lnot \textit{fem}(e) \\
\textit{dau}(e,t) \lor \lnot \textit{par}(h,m) \lor \lnot \textit{par}(h,t) \lor \lnot \textit{par}(g,m) \lor \lnot \textit{par}(t,e) \lor \lnot \textit{par}(n,e) \lor \lnot \textit{fem}(h) \lor \lnot \textit{fem}(m) \lor \lnot \textit{fem}(n) \lor \lnot \textit{fem}(e)
\end{align}</math>,
* [[Antiunificação (ciências da computação)|Antiunificar]]&nbsp;cada&nbsp;par compatível&nbsp;<ref>i.e. sharing the same predicate symbol and negated/unnegated status</ref>&nbsp;<ref>in general: n-tuple when n positive example literals are given</ref>&nbsp;de literais:
** <math>\textit{dau}(x_{me},x_{ht})</math> de&nbsp;<math>\textit{dau}(m,h)</math> e <math>\textit{dau}(e,t)</math>,
** <math>\lnot \textit{par}(x_{ht},x_{me})</math> de&nbsp;<math>\lnot \textit{par}(h,m)</math>&nbsp;e&nbsp;<math>\lnot \textit{par}(t,e)</math>,
** <math>\lnot \textit{fem}(x_{me})</math> de&nbsp;<math>\lnot \textit{fem}(m)</math> e <math>\lnot \textit{fem}(e)</math>,
** <math>\lnot \textit{par}(g,m)</math> de&nbsp;<math>\lnot \textit{par}(g,m)</math> e <math>\lnot \textit{par}(g,m)</math>, similar para qualquer outro literal de conhecimento prévio:
** <math>\lnot \textit{par}(x_{gt},x_{me})</math> de&nbsp;<math>\lnot \textit{par}(g,m)</math>&nbsp;e&nbsp;<math>\lnot \textit{par}(t,e)</math>, 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&nbsp;<math>x_{me},x_{ht}</math>, somente&nbsp;<math>\textit{dau}(x_{me},x_{ht}) \lor \lnot \textit{par}(x_{ht},x_{me}) \lor \lnot \textit{fem}(x_{me})</math> resta, juntamente com todos os literais que vieram do conhecimento prévio
* Converter cláusulas de volta para a forma de Horn:
** <math>\textit{dau}(x_{me},x_{ht}) \leftarrow \textit{par}(x_{ht},x_{me}) \land \textit{fem}(x_{me}) \land (\text{todos os fatos do conhecimento prévio})</math>
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ê "''<math>x_{me}</math> é chamada de uma filha de <math>x_{ht}</math> se <math>x_{ht}</math> é o pai de <math>x_{me}</math> e <math>x_{me}</math> é feminina", que é uma definição comumente aceita.

Sobre os requisitos&nbsp;[[#Definição forma|acima]], "''Necessidade''" estava satisfeita porque o predicado <math>\textit{dau}</math> 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 {{mvar|h}}, pois, ela juntamente com <math>\textit{par}(h,m) \land \textit{fem}(m)</math> a partir do conhecimento prévio, implica o primeiro exemplo positivo <math>\textit{dau}(m,h)</math>, e da mesma forma {{mvar|h}} e <math>\textit{par}(t,e) \land \textit{fem}(e)</math> a partir do conhecimento prévio implica o segundo exemplo positivo <math>\textit{dau}(e,t)</math>. "''A Consistência fraca''" é satisfeita por {{mvar|h}}, pois {{mvar|h}} detém a&nbsp;[[estrutura de Herbrand]]&nbsp;(finita)&nbsp;descrita pelo conhecimento prévio; semelhante para o "''Consistência forte''".

A definição comum da relação avó,&nbsp;<math>\textit{gra}(x,z) \leftarrow \textit{fem}(x) \land \textit{par}(x,y) \land \textit{par}(y,z)</math>, 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&nbsp;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&nbsp;GOLEM é baseada na abordagem&nbsp;rlgg.

== Sistema de Programação em Lógica Indutiva ==
Systema de Programação em Lógica Indutiva é um programa que toma como entrada teorias lógicas&nbsp;<math>B, E^+, E^-</math> e retorna uma hipótese correta&nbsp;{{mvar|H}}&nbsp;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&nbsp;<math>B, E^+, E^-</math> qualquer hipótese correta&nbsp;{{mvar|H}}&nbsp;em relação a estas teorias pode ser encontrad com seu método de pesquisa de hipótese.

=== Pesquisa de Hipótese ===
Modernos sistemas de ILP como Progol,<ref name="muggleton1995inverse" /> Hail,<ref>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.</ref>  e Imparo<ref>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.</ref> encontram uma hipótese {{mvar|H}}, utilizando o princípio da implicação inversa<ref name="muggleton1995inverse" /> para as teorias {{mvar|B}}, {{mvar|E}}, {{mvar|H}}: <math>B \land H \models E \iff B \land \neg E \models \neg H</math> Primeiro eles constroem uma teoria intermediária&nbsp;F chamada de uma teoria ponte que satisfaça as condições <math>B \land \neg E \models F</math> and <math>F \models \neg H</math>. Em seguida, como <math>H \models \neg F</math>, eles generalizam a negação da teoria ponte&nbsp;F com a anti-implicação.<ref>Yoshitaka Yamamoto, Katsumi Inoue, and Koji Iwanuma. Inverse subsumption for complete explanatory induction. Machine learning, 86(1):115–139, 2012.</ref>&nbsp;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 (antisssubsunçã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 &nbsp;'''exemplo de Yamamoto '''.<ref>Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.</ref> por outro lado, Imparo é completa, tanto para o método de anti-implicação&nbsp;<ref name="kimber2009induction">Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.</ref>&nbsp;quanto para o método de classificação inversa estendida&nbsp;<ref>David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836</ref>

=== Implementações ===
* 1BC e 1BC2: de primeira ordem naive Bayesian classificadores: (http://www.cs.bris.ac.uk/Research/MachineLearning/1BC/)
* ACE (UM Combinado do Motor) (http://dtai.cs.kuleuven.be/ACE/)
* Aleph (http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/)
* Átomo (http://www.ahlgren.info/research/atom/)
* Claudien (http://dtai.cs.kuleuven.be/claudien/)
* DL-Aluno (http://dl-learner.org)
* (Dmáx<nowiki/>http://dtai.cs.kuleuven.be/dmax/)
* [[Aprendiz indutivo de primeira ordem|FOLHA]] (ftp://ftp.cs.su.oz.au/pub/foil6.sh{{Ligação inativa|1=|data=maio de 2019}})
* Golem (ILP) (http://www.doc.ic.ac.uk/~shm/Software/golem)
* Imparo<ref name="kimber2009induction" />
* Inthelex (INcremental Teoria de Aprendiz, a partir de Exemplos)http://lacam.di.uniba.it:8000/systems/inthelex/)
* Limão:https://web.archive.org/web/20020516195248/http://cs.anu.edu.au/people/Eric.McCreath/lime.html)
* Metagol (http://github.com/metagol/metagol)
* Mio (http://libra.msra.cn/Publication/3392493/mio-user-s-manual{{Ligação inativa|1=|data=maio de 2019}})
* MIS (Modelo de Inferência do Sistema) por Ehud Shapiro
* Ontolearn (https://github.com/dice-group/Ontolearn)
* PROGOL (http://www.doc.ic.ac.uk/~shm/Software/progol5.0)
* RSD (https://web.archive.org/web/20070301162526/http://labe.felk.cvut.cz/~zelezny/rsd/)
* Tércio (http://www.cs.bris.ac.uk/publications/Papers/1000545.pdf)
* Warmr (agora incluído no ACE)
* ProGolem (http://ilp.doc.ic.ac.uk/ProGolem/) <ref>{{citar periódico|último1 =Muggleton|primeiro1 =Stephen|último2 =Santos|primeiro2 =Jose|último3 =Tamaddoni-Nezhad|primeiro3 =Alireza|título=ProGolem: a system based on relative minimal generalization|periódico=ILP|data=2009|url=http://www.doc.ic.ac.uk/~jcs06/papers/ilp09/progolem.pdf}}</ref><ref>{{citar periódico|último1 =Santos|primeiro1 =Jose|último2 =Nassif|primeiro2 =Houssam|último3 =Page|primeiro3 =David|último4 =Muggleton|primeiro4 =Stephen|último5 =Sternberg|primeiro5 =Mike|título=Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study|periódico=BMC Bioinformatics|data=2012|volume=13|página=162|url=http://www.doc.ic.ac.uk/~jcs06/Hexose/hexose.pdf|doi=10.1186/1471-2105-13-162}}</ref>

== Veja também ==
* Raciocínio de senso comum
* Conceito de análise formal
* [[Método indutivo|Método Indutivo]]
* [[Método indutivo|Raciocínio indutivo]]
* Programação Indutiva
* [[Probabilidade indutiva|Probabilidade Indutiva]]
* Estatísticas relacionais de aprendizagem
* Versão espaço de aprendizagem

== Referências ==
{{reflist}}

== Ler mais ==
{{Refbegin}}
* {{citar periódico|último1 = Muggleton |primeiro1 = S. |último2 = De Raedt | doi = 10.1016/0743-1066(94)90035-3 |primeiro2 = L. |título= Inductive Logic Programming: Theory and methods |periódico= The Journal of Logic Programming | volume = 19-20 |páginas= 629–679 |ano= 1994 | pmid =  | pmc = }}
* {{citar livro |primeiro1 = N. |último1 = Lavrac |primeiro2 = S. |último2 = Dzeroski |título = Inductive Logic Programming: Techniques and Applications |publicado = Ellis Horwood |local = New York |ano = 1994 |isbn = 0-13-457870-8 |url = http://www-ai.ijs.si/SasoDzeroski/ILPBook/ |acessodata = 2016-12-06 |arquivourl = https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/ |arquivodata = 2004-09-06 |urlmorta = yes }}
* Visual example of inducing the grandparenthood relation by the [[#Implementations|Atom system]]. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html
{{Refend}}

[[Categoria:Programação lógica|*]]