Extrac˘c~ao de Conhecimentoec/files_0708/slides/ilp.pdf · Indu˘c~ao de Regras Indu˘c~ao de Programas em L ogica Generaliza˘c~ao Menos Geral (Least General Generalisation) Os

ClassificacaoArvores de Classificacao

Version SpacesInducao de Regras

Inducao de Programas em Logica

Extraccao de Conhecimento– Programa Doutoral em Engenharia Informatica –– Mestrado Integrado em Engenharia Informatica –

Rui CamachoLIACC/FEUP Universidade do Porto

www.fe.up.pt/∼ec

[email protected]

Outubro 2007

Rui Camacho Extraccao de Conhecimento




Inducao de Programas emLogica





Sumario

I O contexto do ILP

I Definicoes Basicas

I Sistemas de ILP

I Aplicacoes

I Conclusoes





ILP

I Sub-area da Aprendizagem (Machine Learning) que por suavez e parte da Inteligencia Artificial

I Tem contribuicoes da Programacao em Logica e da Estatıstica

I Utiliza um subconjuto da Logica de Predicados de PrimeiraOrdem (LPPO) como esquema de representacao tanto dosdados como dos resultados

I Procura automatizar processos de inducao





Um sistema de ILP

E:

I Uma tecnologia para geracao e teste de hipoteses

I Construcao automatica de modelos para dados

I Modelos e dados descritos numa linguagem formal (LPPO)

Resultado:

I Conjunto de hipoteses que explica os exemplos positivos e econsistente com os negativos





Ingredientes para um sistema ILP

Informalmente:

I Background Knowledge: programa Prolog definindoinformacao potencialmente util

I Restricoes a linguagem das hipoteses

I Exemplos do conceito

Formalmente:

SejaB = C1 ∧ C2 ∧ . . . conhecimento do domınio (background)E = E+∧ E− exemplos

E+ = e1 ∧ e2 ∧ . . . exemplos positivosE− = f1 ∧ f2 ∧ . . . exemplos negativos

H = D1 ∧ D2 ∧ . . . hipoteses





ILP: exemplo

B =

8>>>>><>>>>>:

determination(activa/1, atm/5).determination(activa/1, bond/4).determination(activa/1, > /2).determination(activa/1, lumo/2).determination(activa/1, logp/2).determination(activa/1, carbon 5 aromatic ring/2).

E+ =

activa(d1)←activa(d2)←

E− =

← activa(d3)← activa(d4)

H = activa(X) ← logp(X,Log), Log > 3.2





Exemplo do resultado

active molecule(A) if:hydrogen acceptor(A,C) &hydrogen acceptor(A,D) &distance(C,D,4.17) &hydrophobe(A,E) &distance(C,E,3.38) &distance(D,E,7.20) &hydrophobe(A,F) &distance(C,F,3.68) &distance(D,F,5.41) &distance(E,F,5.0).

retirado da pagina Web de David Page





ILP

I Processo de Inducao e transformado numa procura num“grafo especial”

I O “grafo especial” e obtido associando uma relacao de ordemparcial (relacao de generalizacao) com o conjunto dasclausuals definidas

I O “grafo especial” e um Reticulado

I o “grafo especial” (Reticulado) esta ordenado

I E possıvel efectuar uma procura sistematica no Reticulado

I O resultado e o “melhor” conjunto de hipoteses satisfazendodeterminado conjunto de restricoes





Contexto para ILP – formalismo

SejaB = C1 ∧ C2 ∧ . . . conhecimento previo (background)E = E+∧ E− exemplosE+ = e1 ∧ e2 ∧ . . . exemplos positivosE− = f1 ∧ f2 ∧ . . . exemplos negativosH = D1 ∧ D2 ∧ . . . hipoteses





Contexto para ILP

Condicoes:

Consistencia previa:B 6|= �E+∧ E− 6|= �

Satisfacao a prioriB ∧ E− 6|= �

Satisfacao a posterioriB ∧ H ∧ E− 6|= �

Necessidade a prioriB 6|= E+

Suficiencia a posterioriB ∧ H |= E+

Necessidade a posterioriB ∧hi |= e+

1 ∨ e+2 ∨ · · · ∨ e+

n (∀hi , hi ∈ H)





Contexto para ILP: exemplo

every bird has wingsevery bird has a beakevery vulture is a birdevery vulture is a carnivore

B =

8>><>>:haswings(X )← bird(X )hasbeak(X )← bird(X )bird(X )← vulture(X )carnivore(X )← vulture(X )

found tweety : has wings and has a beak

E+ =

haswings(tweety)←hasbeak(tweety)

H = bird(tweety)←H’ = vulture(tweety)←





Inducao

Inducao = Abducao + Justificacao(logico) (estatıstico)

abducao – processo de formacao de hipoteses (filosofo Pierce)grau de confirmacao (Carnap)corroboracao (Popper)





“Justificacao”

Cobertura (Coverage)

Compressibilidade





Subordinacao-θ

Sejam C e D duas clausulas (conjunto de literais). C subordina D,ou C � D, se e so se existir uma substituicao θ tal que Cθ ⊆ D.

� e uma ordem parcial sobre as classes de equivalencia dasclausulas.

Sejam C e D duas clausulas. C ≡ D se e so se C � D e D � C

subordinacao-θ traducao de θ-subsumption





Subordinacao-θ vs Implicacao Logica

Sejam C e D duas clausulas. C � D se e so se C → D.

Sejam C e D duas clausulas. C → D nao implica que C � D.

Examplo: C = nat(s(X)) ← nat(X)D = nat(s(s(X))) ← nat(X)

D e C auto-resolvida e portanto C → D. No entanto C nao subordina D.





Reticulado de subordinacao (Subsumption lattice)

Um reticulado e um conjunto parcialmente ordenado em que qual-quer par de elementos a,b tem um greatest lower bound (glb) (rep-resentado por a u b) e um least upper bound (lub) (representadopor a t b) dentro do conjunto.





Reticulado de generalizacao - exemplo





Generalizacao Menos Geral(Least General Generalisation)

Os literais l e m sao compatıveis se tem o mesmo sımbolo depredicado e mesmo sinal.O least upper bound (lub) do reticulado imposto por � e ageneralizacao menos geral (least general generalisation – lgg) dosliterais.A lgg entre dois literais compatıveis l e l’ e unica (a menos daequivalencia de literais) (G. Plotkin 1970).

Examplo: l = member(3, cons(2,cons(3,nil)))l’ = member(5, cons(4,cons(5,cons(6,nil))))

lgg(l, l’) = member(V3,5, cons(V2,4, cons(V3,5,Vnil ,cons(6,nil))))≡ member(X, cons(Y, cons(X,Z)))





LGG de clausulas

Sejam C e D duas clausulas (conjuntos de literais). A lgg de C e Dsob a subordinacao-θ e:

lgg(C .D) = {lgg(l ,m) | l ∈ C e m ∈ D e l e m sao compativeis}

RLGG de clausulasA clausula H e a Generalizacao Menos Geral Relativa (RelativeLeast General Generalisation – rlggB) de e+

1 e e+2 se e so se

H = lgg(⊥H (B, e+1 ),⊥H (B, e+

2 ))





Operador de Refinamento

Dada uma linguagem com restricoes (a language bias) L, umoperador de refinamento ρ mapeia a clausula C num conjunto declausulas ρ(C) que sao especializacoes (refinamentos) dex C:ρ(C) = {C’ | C ∈ L, C � C’ }tipicamente calcula as especializacoes mais gerais:1. Aplica uma substituicao a clausula, e2. adiciona um literal no corpo da clausula.





Inversao da Regra de Resolucao





Restricoes extra-logicasrestricoes da linguagem (bias)

ij-determinacyRule modelsMode declarationsTipos para os dadosDCGs





Searching the Hypothesis space

The space:H = {H’ | � � H � ⊥H(B,E+) and B ∧ H ∧ E− 6|= �}

search direction:1. H0 = � (most general)

progressively add a most general literal (ex: p(X,Y,Z)) orinstanciate a variable with a variable or themost general functional term (ex: f(X,Y)).

2. H0 = ⊥H(B,E+) (most specific)progressively remove a literal or

replace a term by a variable.





Sistemas de ILP

GOLEM (S. Muggleton) baseado em lggMIS (Y. Shapiro) operadores de refinamento

CIGOL (S. Muggleton) inversao da regra da ResolucaoProgol (S. Muggleton) Mode Directed Inverse EntailmentFOIL (R. Quinlan) pesquisa gananciosa e funcao

de Teoria da InformacaoCLINT (L. De Raedt) shift de linguagensLINUS (Nada Lavrac et al.) usa um sub-sistema proposicionalAleph (A. Srinivasan) Mode Directed Inverse Entailment

IndLog (R. Camacho) Mode Directed Inverse Entailment

Onde procurar:

(ILPnet2) http://www.cs.bris.ac.uk/%7EILPnet2/index.html(MLnet) http://www.mlnet.org/(Oxford Univ.) http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/applications.html





Mode Direct Inverse Entailement

From

B ∧ H ` e+i ,

using the Deduction Theorem we get

B ∧e+i ` H

⊥H(B,ei ,C) is the most specific clause from thegeneralisation lattice that subsumes the example(e+

i ) relative to the background (B) andsatisfies the constraints (C)





Aplicacoes de Engenharia

I Deteccao de problemas de trafego

I Dimensionamento de malhas em Metodos de Elementos finitos

I Trefilagem de aco

I Analise de dados sobre acidentes rodoviarios





Metodo dos Elementos Finitos





Aplicacoes em Ciencias da Vida

I Previsao da estrutura 3-D de proteınas

I Descoberta de novoc neuropeptidos

I Elicitacao da estrutura da Diterpina

I Diagnostico precoce de doencas reumaticas

I Mutagenicidade de substancias

I Pharmacophore discovery for ACE inhibition

I Protein exposure

I Carcinogenicidade em roedores





Previsao da estrutura 3-D de proteınas





Relacao Estrutura-Actividade (SARs)





Aplicacoes em Controlo

I Caracterizar os movimentos dos olhos de um patologistaanalisando uma lamina

I Behavioural cloning





Aplicacoes de Diversas

I Analise de resultados de prospeccao de mercado de bebidasnao alcoolicas

I Caracterizacao da sonatas de Rakmaninov

I Processamento de linguagem natural





Vantagens da utilizacao do ILP

I Poderosa linguagem de representacao (LPPO)

I Rapidez face a um investigador

I Compreensibilidade dos resultados

I Aceita informacao adicional sobre o domınio

I Pode combinar harmoniosamente computacoes numericas comrelacoes

I Largo espectro de domınios de aplicacao

I Maioria dos sistemas de ILP estao disponıveis na Web





Desvantagens da utilizacao do ILP

I Lento (em aplicacoes complexas)

I Precisa utilizador “experiente em ILP” para usar os sistemas

I Espaco de procura cresce “muito rapidamente” com o numerode relacoes no background knowledge





Conclusoes

I Desenvolvimento de Assistentes Inteligentes para aplicacoescientıficas

I Os modelos construidos para os dados sao inteligiveis

I Possıvel usar modelos estatısticos e/ou geometricos combinadosharmoniosamente com relacoes

I A paralelizacao/distribuicao pode alargar “facilmente” o alcance dasaplicacoes

I Paralizacao/distribuicao pode melhorar substancialmente aqualidade dos resultados (visitar mais nos do espaco de procura)


Documents

Extrac˘c~ao de Conhecimentoec/files_0708/slides/ilp.pdf · Indu˘c~ao de Regras Indu˘c~ao de Programas em L ogica Generaliza˘c~ao Menos Geral (Least General Generalisation) Os