Upload
sidone
View
46
Download
0
Embed Size (px)
DESCRIPTION
Programação em Lógica Indutiva. Jacques Robin DI-UFPE. O que é programação em lógica?. Paradigma de linguagem de programação que unifica: Engenharia de Software (especificação formal, linguagens de programação) - PowerPoint PPT Presentation
Citation preview
Programação em Lógica IndutivaProgramação em Lógica Indutiva
Jacques RobinDI-UFPE
O que é programação em lógica?O que é programação em lógica?
Paradigma de linguagem de programação que unifica:• Engenharia de Software (especificação formal, linguagens de
programação)• Inteligência Artificial (raciocínio com Formalismos de
Representação do Conhecimento)• Banco de Dados -- Dedutivos (BDD)• Teoria Lógica (TL) das provas
Metáfora computacional considerando:• Teoria Lógica = Especificação Formal de Software =
Programa Executável = BDD = Base de Conhecimento (BC)• Programar = Especificar = apenas declarar axiomas e regras• Axiomas da TL = fatos da BC = parte extensional do BDD
= dados explícitos de um BD tradicional• Regras da TL e da BC = parte intencional do BDD• Teoremas da TL deduzidos a partir dos axiomas e das regras
= dados implícitos do BDD
West é criminoso?West é criminoso? : em L1 : em L1
Requisitos em inglês1. It is crimimal for an American to
sell weapons to an hostile country
2. Nono owns missiles3. Nono acquires all its missiles
from West4. West is American5. Nono is a nation6. Nono is an enemy of the USA0. Is West a crimimal?
Em lógica da 1a ordem1. P,W,N american(P) weapon(W)
nation(N) hostile(N) sells(P,N,W) criminal(P)
2. W owns(nono,W) missile(W)3. W owns(nono,W) missile(W)
sells(west,nono,W)7. X missile(W) weapon(W)8. X enemy(N,america) hostile(N)4. american(west)5. nation(nono)6. enemy(nono,america)9. nation(america)
West é criminoso?West é criminoso? em formal normalem formal normal
Em lógica da 1a ordem1. P,W,N american(P)
weapon(W) nation(N) hostile(N) sells(P,N,W) criminal(P)
2. W owns(nono,W) missile(W)3. W owns(nono,W) missile(W)
sells(west,nono,W)7. X missile(W) weapon(W)8. X enemy(N,america)
hostile(N)4. american(west)5. nation(nono)6. enemy(nono,america)9. nation(america)
Em formal normalamerican(P) weapon(W)
nation(N) hostile(N) sells(P,N,W) criminal(P)
owns(nono,m1)missile(m1)owns(nono,W) missile(W)
sells(west,nono,W)missile(W) weapon(W)enemy(N,america) hostile(N)american(west)nation(nono)enemy(nono,america)nation(america)
West é criminoso?West é criminoso? em Prolog em Prolog
Em Lógica de Horn:american(P) weapon(W)
nation(N) hostile(N) sells(P,N,W) => criminal(P)
owns(nono,m1)missile(m1)owns(nono,W) missile(W)
sells(west,nono,W)missile(W) weapon(W)enemy(N,america) hostile(N)american(west)nation(nono)enemy(nono,america)nation(america)
Em Prolog:criminal(P) :- american(P),
weapon(W), nation(N), hostile(N), sells(P,N,W).
owns(nono,m1).missile(m1).sells(west,nono,W) :-
owns(nono,W), missile(W).weapon(W) :- missile(W).hostile(N) :- enemy(N,america).american(west).nation(nono).enemy(nono,america).nation(america).
West é criminoso?West é criminoso? Funcionamento de Funcionamento de PrologProlog
criminal(P) :- american(P), weapon(W), nation(N), hostile(N), sells(P,N,W).
owns(nono,m1).missile(m1).sells(west,nono,W) :-
owns(nono,W), missile(W).weapon(W) :- missile(W).hostile(N) :- enemy(N,america).american(west).nation(america).enemy(nono,america).nation(nono).
criminal(west)? <- yes.•american(west)? -> yes.•weapon(W)? <- W = m1.
missile(W)? -> W = m1.•nation(N)? -> N = america.•hostile(america)? <- no.
enemy(america,america)? -> no.•backtrack: nation(N), N \ {america}? -> N = nono.•hostile(nono)? <- yes.
enemy(nono,america)? -> yes.•sells(west,nono,m1)? <- yes.
owns(nono,m1)? -> yes.missile(nono,m1)? -> yes.
Aprendizagem Indutivo
Programação em Lógica
Programação em Lógica Indutiva (IPL)
O que é ILP (Inductive Logic O que é ILP (Inductive Logic Programming)?Programming)?
ILP x resto da aprendizagem • Descobre conhecimento novo expressado em lógica da 1a
ordem ILP x resto da programação em lógica
• Inverte mecanismos de dedução para implementar indução
Programação em Lógica Indutiva x Programação em Lógica Indutiva x DedutivaDedutiva
PL Dedutiva (Prolog, BD dedutivas):• Fatos positivos declarados Regras |= Fatos positivos
deduzidos • Conhecimento prévio em extensão Conhecimento prévio em
intenção • |= Novo conhecimento comprovado em extensão
PL Indutiva (Progol, BD indutivas):• Fatos positivos declarados Fatos negativos declarados • Regras declaradas ?|= Regras induzidas• Conhecimento prévio em extensão Conhecimento prévio em
intenção • |= Novo conhecimento hipotético em intenção
Linguagens de ILP x Prolog:• com negações no BD e nas conclusões • sem símbolo de função, e.g.: pessoa(nome(joão),idade(20))• sem fatos universais, e.g.: ancestral(X,adão).
Programação em Lógica Indutiva: Programação em Lógica Indutiva: tarefa genéricatarefa genérica
Dados:• B = Base de conhecimento prévio (regras)• D+ = base de dados (exemplos, fatos) positivos• D- = base de dados (exemplos, fatos) negativos• Viés de aprendizagem (restrições sobre forma das regras)
Aprende hipótese H (regras) tal que: • H verifica restrições do viés de aprendizagem, e D-, B H D-, e D+, B H |= D+ em ILP monótona, ou D+, B H D+ em ILP não monótona definido por limiar, para evitar overfitting e ser tolerante
ao ruído
Viés de aprendizagem em ILPViés de aprendizagem em ILP
Objetivo: reduzir busca no espaço de hipótese Sintática paramétrica sobre cláusulas: limitar
•número de premissas por cláusula,•número de variáveis por cláusula,•profundidade dos termos das cláusulas,•nível dos termos das cláusulas.
Semântica sobre predicados: •tipos dos seus argumentos•instanciação dos seus argumentos
constante #, variável de entrada + ou variável de saída -
•número de vezes que um predicado pode ser satisfeito
Programação em Lógica Indutiva (ILP):Programação em Lógica Indutiva (ILP):característicascaracterísticas
Tarefas: classificação, previsão e controle Ambiente pode ser:
• inacessível, não episódico • contínuo, ruidoso• dinâmico?, grande?• relacional, diverso
Supervisionado: E+E- ou E+
Treino antes da ação
Incremental ou não Não iterativo Top-down ou bottom-up ou
bidirecional Guloso Global Aproveita conhecimento
prévio para podar busca da hipótese
Aproxima qualquer funçãoRepresentação do conhecimento: •exemplos, conhecimento prévio e conhecimento aprendido •uniformemente representados por conjunto de conjunto de cláusulas de Horn, •i.e., regras da lógica 1a ordem da forma c(...,X,Y,Z, ...) :- p1(...,X,Y,...),...,pn(...,Y,Z,...).
com semântica ...X,Y,Z,... c(...,X,Y,Z, ...) p1(...,X,Y,...) ... pn(...,Y,Z,...)
Necessidades das regras relacionaisNecessidades das regras relacionais
Conhecimento a priori
name1 = ann
…
name5 = tom
father11 = F
…
father31 = T
…
father54 = T
mother11 = F
…
mother55 = F
female1 = T
…
female5 = F
male1 = F
Exemplos positivos:daughter42 = Tdaughter13 = T
Exemplo negativos:daughter11 = F…daughter44 = F
Aprende:daughter13(D,P) :- female3(D),
parent13(P,D).daughter42(D,P) :- female4(D),
parent42(P,D).
Aprender relações abstratas com ILPAprender relações abstratas com ILP
Conhecimento a prioriIntencional:parent(F,C) :- father(F,C). parent(M,C) :- mother(P,C).Extensional:father(pat,ann).father(tom,sue).female(ann).female(eve).female(sue).male(pat).male(tom).mother(eve,sue).mother(ann,tom).
ExemplosPositivos:daughter(sue,eve).daughter(ann,pat).Negativos:not daughter(tom,ann).not daughter(eve,ann).
Aprende:daughter(D,P) :- female(D), parent(P,D).
Aprender definição recursiva com ILPAprender definição recursiva com ILP
Conhecimento a prioriIntencional:parent(F,C) :- father(F,C). parent(M,C) :- mother(M,C).Extensional:father(pat,ann).father(tom,sue).female(ann).female(eve).female(sue).male(pat).male(tom).mother(eve,sue).mother(ann,tom).
Exemplos positivos:ancestor(tom,sue).ancestor(eve,sue)....Exemplo negativos:not ancestor(ann,eve).not ancestor(sue,eve)....Definição induzida:ancestor(A,D) :- parent(A,D).ancestor(A,D) :- parent(A,P), ancestor(P,D).
ILP x métodos baseados em atributosILP x métodos baseados em atributos(ID3, Redes Neurais, Redes Bayesianas) (ID3, Redes Neurais, Redes Bayesianas)
Vantagens: Aprende conhecimento relacional em lógica da 1a ordem Aprende conhecimento diretamente executável
(programa Prolog) Re-aproveita conhecimento prévio no mesmo formalismo Capaz de inventar novos predicados (i.e., conceitos)Limitações: Dificilmente aprende conhecimento interessante a partir
apenas de exemplos Métodos suficientemente eficientes para grandes BD:
• requer viés muito restringidor sobre regras a aprender• não tem capacidade a inventar novos predicados
Aplicações práticas de KDD por ILPAplicações práticas de KDD por ILP
Medicina e saúde: • previsão dos efeitos de uma
nova droga composta a partir dos efeitos dos seus componentes em drogas testadas
• previsão da forma 3D de uma proteína a partir da sua seqüência de ácidos-amidos
• descoberta de regras diagnosticas em reumatologia
CAD/CAM: • descoberta de regras
escolhendo resolução de elementos finitos em modelos numéricos de estresses em estruturas
• derivar regras de diagnostico de falha em satélites a partir de regras causais modelando o funcionamento dos mesmos
Jogos: • descoberta de regras para jogar
xadrez Engenharia de software:
• programação (em lógica) automática
• otimização de código (de programas lógicos)
• teste e depuração de código (de programas lógicos)
• descobertas de restrições de integridade implícitas em BD
Processamento de linguagem natural:• aprendizagem de regras de
gramáticas de uma língua natural a partir de grande corpus de textos
Regras e operadores para ILPRegras e operadores para ILP
Especialização (refinamento) baseado em -Generalização
Generalização Mínima Relativa (RLGG Relative Least General Generalization)
Resolução inversa em V Resolução inversa em W (invenção de predicados) Implicação inversa Derivação inversa (inverse entailment)
-Generalização -Generalização ((-Subsumption)-Subsumption)
G -generaliza S sse substituição , (G) S• ie, G se unifica com uma parte de S • ex, com = {D/ann}, daughter(D,P) :- female(D).
-generaliza daughter(ann,P) :- female(ann), parent(P,ann). Sugere 2 operadores de especializações:
• aplicar substituição, ex, especializar daughter(D,P) :- female(D). em daughter(ann,P) :- female(ann).
• acrescentar premissa, ex, especializar daughter(D,P) :- female(D). em daughter(D,P) :- female(D), parent(P,D).
Propriedades:• (G -generaliza S) (G |= S) -- “G entails S” • mas em geral (G |= S) (G -generaliza S)
Busca top-down em reticulado de Busca top-down em reticulado de refinamento: exemplorefinamento: exemplo
daughter(D,P).
daughter(D,D). daughter(D,P) :- parent(P,D).
daughter(D,P) :- parent(D,X).
daughter(D,P):- female(D).
daughter(D,P):- female(D), female(D).
daughter(D,P):- female(D),
parent(P,D).
... ... ...
daughter(D,P):- parent(P,D),
female(D).
... ...
Busca top-down Busca top-down em reticulado de refinamentoem reticulado de refinamento
Adaptação de ID3 para representação da 1a ordem Espaço de hipótese:
• reticulado no qual cada no -generaliza seus filhos• em cima: conclusão a aprender sem premissa
• em baixo: contradição ou hipótese mais específica Hms tal que: Hms B |= D+ (e Hms B | D-)
Percorre reticulado de cima para baixo em largura 1a
Cada passo implementa uma abordagem gerar e testar• gerar: todas as hipóteses Hn em L(H) refinando a hipótese atual
• testar: função heurística de: número de D+ tal que: Hn B |= D+ número de D- tal que: Hn B |= D- tamanho de Hn
Viés sintático parametrizadoViés sintático parametrizado
lista dos nomes de predicado permitidos em hipóteses
número máximo de premissas por cláusula número máximo de variáveis por cláusula profundidade máxima dos termos das cláusulas nível máximo dos termos das cláusulas:
• variável V é ligada em cláusula C :- P1, …, Pn sse: V C, ou i {1, …, n}, W V: V Pi W Pi W ligada em C :- P1, …,
Pn.
• cláusula ligada sse todas suas variáveis são ligadas ex, p(X) :- q(Z) não ligada, p(X) :- q(X,Y),r(Y,Z),u(Z,W) ligada.
• nível n(t) de um termo t em cláusula ligada C :- P1, …, Pn: 0 se t C, ou 1 + min(n(s)) se t Pi s Pi ex, n(C, grandfather(G) :- male(G), parent(G,F), parent(F,C)) = 2