Programação lógica indutiva

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

A programação lógica indutiva ( ILP ) é um subcampo da inteligência artificial simbólica que usa a programação lógica como uma representação uniforme para exemplos, conhecimento prévio e hipóteses. Dada uma codificação do conhecimento de fundo conhecido e um conjunto de exemplos representados como um banco de dados lógico de fatos, um sistema ILP derivará um programa lógico hipotético que envolve todos os exemplos positivos e nenhum dos negativos.

  • Esquema: exemplos positivos + exemplos negativos + conhecimento préviohipótese .

A programação lógica indutiva é particularmente útil em bioinformática e processamento de linguagem natural . Gordon Plotkin e Ehud Shapiro estabeleceram a base teórica inicial para o aprendizado de máquina indutivo em um ambiente lógico. [1] [2] [3] Shapiro construiu sua primeira implementação (Model Inference System) em 1981: [4] um programa Prolog que inferia indutivamente programas lógicos a partir de exemplos positivos e negativos. O termo Programação Lógica Indutiva foi introduzido pela primeira vez [5] em um artigo de Stephen Muggleton em 1991. [6]Muggleton também fundou a conferência internacional anual sobre Programação em Lógica Indutiva, introduziu as idéias teóricas de Invenção de Predicados, Resolução Inversa , [7] e Implicação Inversa. [8] Muggleton implementou a vinculação inversa primeiro no sistema PROGOL . O termo " indutivo " aqui se refere à indução filosófica (isto é, sugerindo uma teoria para explicar fatos observados) em vez de matemática (isto é, provando uma propriedade para todos os membros de um conjunto bem ordenado).

Definição formal

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

A " necessidade " não impõe uma restrição a h , mas proíbe qualquer geração de uma hipótese, desde que os fatos positivos sejam explicáveis ​​sem ela. " Suficiência " requer qualquer hipótese gerada h para explicar todos os exemplos positivos. A " consistência fraca " proíbe a geração de qualquer hipótese h que contradiga o conhecimento prévio B. A " consistência forte " também proíbe a geração de qualquer hipótese h que seja inconsistente com os exemplos negativos, dado o conhecimento prévio B ; implica " Consistência fraca "; se não forem dados exemplos negativos, ambos os requisitos coincidem. Džeroski [10] requer apenas " Suficiência " (chamada de "Integridade" lá) e " Consistência forte ".

Exemplo

Relações familiares assumidas na seção "Exemplo"

O exemplo bem conhecido a seguir sobre a aprendizagem de definições de relações familiares usa as abreviações

par : pai , fem : feminino , dau : filha , g : George , h : Helen , m : Mary , t : Tom , n : Nancy , ee : Eve .

Começa a partir do conhecimento prévio (cf. imagem)

,

os exemplos positivos

,

e a proposição trivial verdadeira para denotar a ausência de exemplos negativos.

A abordagem de " relativa menos generalização geral (rlgg) " de Plotkin [11] [12] para programação lógica indutiva deve ser usada para obter uma sugestão sobre como definir formalmente a relação filha dau .

Essa abordagem usa as etapas a seguir.

  • Relativize cada literal de exemplo positivo com o conhecimento de fundo completo:
    ,
  • Converter para a forma normal da cláusula :
    ,
  • Anti-unifique cada par [ 13] compatível [ 14] de literais:
    • a partir dee,
    • a partir dee,
    • a partir dee,
    • a partir dee, semelhante para todos os outros literais de conhecimento de fundo
    • a partir dee, e muitos outros literais negados
  • Exclua todos os literais negados contendo variáveis ​​que não ocorrem em um literal positivo:
    • depois de excluir todos os literais negados contendo outras variáveis ​​que não, sópermanece, juntamente com todos os literais de base do conhecimento de fundo
  • Converta as cláusulas de volta para a forma Horn:

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

Em relação aos requisitos acima , " Necessidade " foi satisfeita porque o predicado dau não aparece no conhecimento de fundo, o que não pode implicar qualquer propriedade contendo este predicado, como os exemplos positivos. A " suficiência " é satisfeita pela hipótese calculada h , uma vez que ela, juntamente comdo conhecimento prévio, implica o primeiro exemplo positivo, e da mesma forma h edo conhecimento de fundo implica o segundo exemplo positivo. A " consistência fraca " é satisfeita por h , uma vez que h se mantém na estrutura (finita) de Herbrand descrita pelo conhecimento prévio; semelhante para " Consistência forte ".

A definição comum da relação avó, viz., não pode ser aprendido usando a abordagem acima, pois a variável y ocorre apenas no corpo da cláusula; os literais correspondentes teriam sido excluídos na 4ª etapa da abordagem. Para superar essa falha, essa etapa deve ser modificada de modo que possa ser parametrizada com diferentes heurísticas de pós-seleção literais . Historicamente, a implementação do GOLEM é baseada na abordagem rlgg.

Sistema de Programação Lógica Indutiva

O sistema de Programação Lógica Indutiva é um programa que toma como entrada teorias lógicase produz uma hipótese correta H wrt teoriasUm algoritmo de um sistema ILP consiste em duas partes: busca de hipóteses e seleção de hipóteses. Primeiro uma hipótese é pesquisada com um procedimento de programação lógica indutiva, então 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 pontua cada uma das hipóteses encontradas e retorna aquelas com a pontuação mais alta. Um exemplo de função de pontuação inclui o comprimento mínimo de compactação em que uma hipótese com a menor complexidade de Kolmogorov tem a pontuação mais alta e é retornada. Um sistema ILP é completo se para qualquer teoria lógica de entradaqualquer hipótese correta H wrt para essas teorias de entrada pode ser encontrada com seu procedimento de busca de hipóteses.

Pesquisa de hipóteses

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

Surgem questões de completude de um procedimento de pesquisa de hipóteses de um sistema ILP específico. Por exemplo, o procedimento de busca de hipóteses do Progol baseado na regra de inferência de implicação inversa não está completo pelo exemplo de Yamamoto . [18] Por outro lado, Imparo é completo tanto pelo procedimento anti-implicação [19] quanto pelo procedimento de subsunção inversa estendida [20] .

Implementações

Veja também

Referências

  1. ^ Métodos automáticos de Plotkin GD, tese de doutorado, Universidade de Edimburgo, 1970.
  2. ^ Shapiro, Ehud Y. Inferência indutiva de teorias de fatos , Relatório de pesquisa 192, Universidade de Yale, Departamento de Ciência da Computação, 1981. Reimpresso em J.-L. Lassez, G. Plotkin (Eds.), Lógica Computacional, The MIT Press, Cambridge, MA, 1991, pp. 199-254.
  3. ^ Shapiro, Ehud Y. (1983). Depuração de programa algorítmico . Cambridge, Mass: MIT Press. ISBN  0-262-19218-7
  4. ^ Shapiro, Ehud Y. " O sistema de inferência modelo ." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.
  5. ^ Luc De Raedt. Uma Perspectiva da Programação em Lógica Indutiva. The Workshop on Current and Future Trends in Logic Programming, Shakertown, a aparecer em Springer LNCS, 1999. CiteSeerX : 10.1.1.56.1790
  6. ^ a b c Muggleton, SH (1991). "Programação lógica indutiva". Computação de Nova Geração . 8 (4): 295–318. CiteSeerX 10.1.1.329.5312 . doi : 10.1007/BF03037089 . 
  7. Muggleton SH e Buntine W. " Invenção de máquina de predicado de primeira ordem invertendo a resolução ", "Proceedings of the 5th International Conference on Machine Learning, 1988.
  8. ^ Muggleton, SH (1995). "Invertendo vinculação e Progol". Computação de Nova Geração . 13 (3–4): 245–286. CiteSeerX 10.1.1.31.1630 . doi : 10.1007/bf03037227 . 
  9. ^ Muggleton, Stephen (1999). "Programação em Lógica Indutiva: Problemas, Resultados e o Desafio de Aprender Linguagem em Lógica" . Inteligência Artificial . 114 (1–2): 283–296. doi : 10.1016/s0004-3702(99)00067-3 .; aqui: Seção 2.1
  10. ^ Džeroski, Sašo (1996), "Programação Lógica Indutiva e Descoberta de Conhecimento em Bancos de Dados", em Fayyad, UM; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Avanços na Descoberta de Conhecimento e Mineração de Dados (PDF) , MIT Press, pp. 117–152 ; aqui: Seção 5.2.4
  11. ^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "Uma nota sobre generalização indutiva". Inteligência de Máquina . 5 : 153-163.
  12. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "Uma nota adicional sobre generalização indutiva". Inteligência de Máquina . 6 : 101-124.
  13. ^ ou seja, compartilhando o mesmo símbolo de predicado e status negado/não negado
  14. ^ em geral: n -tupla quando n literais de exemplo positivos são fornecidos
  15. ^ Ray, O., Broda, K., & Russo, AM (2003). Aprendizagem indutiva abdutiva híbrida . No LNCS: Vol. 2835. Anais da 13ª conferência internacional sobre programação lógica indutiva (pp. 311-328). Berlim: Springer.
  16. ^ Kimber, T., Broda, K., & Russo, A. (2009). Indução ao fracasso: aprendendo teorias de Horn conectadas . No LNCS: Vol. 5753. Anais da 10ª conferência internacional sobre programação lógica e raciocínio não-monotônico (pp. 169-181). Berlim: Springer.
  17. Yoshitaka Yamamoto, Katsumi Inoue e Koji Iwanuma. Subsunção inversa para indução explicativa completa . Aprendizado de máquina, 86(1):115–139, 2012.
  18. ^ Akihiro Yamamoto. Quais hipóteses podem ser encontradas com implicação inversa? Em Programação em Lógica Indutiva, páginas 296–308. Springer, 1997.
  19. ^ a b Timothy Kimber. Aprendizagem de programas de lógica definida e normal por indução em caso de falha . Tese de doutorado, Imperial College London, 2012.
  20. ^ David Toth (2014). Imparo é completo por subsunção inversa . arXiv:1407.3836
  21. ^ Muggleton, Stephen; Santos, José; Tamaddoni-Nezhad, Alireza (2009). "ProGolem: um sistema baseado em generalização mínima relativa" (PDF) . ILP .
  22. ^ Santos, José; Nassif, Houssam; Página, David; Muggleton, Stephen; Sternberg, Mike (2012). "Identificação automatizada de características de interações proteína-ligante usando programação lógica indutiva: um estudo de caso de ligação de hexose" (PDF) . BMC Bioinformática . 13 : 162. doi : 10.1186/1471-2105-13-162 . PMC 3458898 . PMID 22783946 .   

Leitura adicional