Programação Lógica Indutiva

Visão geral

Programação Lógica Indutiva (Inductive Logic Programming, ILP) é um ramo do aprendizado de máquina (machine learning) que aprende regras simbólicas, legíveis por humanos — tipicamente na forma de cláusulas de Horn (Horn clauses) — a partir de:

Exemplos (positivos e, frequentemente, negativos)
Conhecimento de fundo (fatos e regras existentes escritos em um estilo de programação lógica)

A ILP fica na interseção entre aprendizado de máquina e raciocínio simbólico (symbolic reasoning). Ela é especialmente útil quando seus dados são relacionais/estruturados (grafos, árvores, entidades ligadas) e quando você se importa com interpretabilidade e generalização com conhecimento prévio.

A ILP está intimamente relacionada a:

Lógica e Programação Lógica (Prolog, Datalog), que fornecem os mecanismos subjacentes de representação e inferência.
Regras, Ontologias, Grafos de Conhecimento, onde regras no estilo ILP são usadas para inferência e completude.
A moderna aprendizagem de regras em grafos de conhecimento e abordagens neuro-simbólicas (neuro-symbolic) que combinam modelos neurais com restrições simbólicas.

Fundamentos lógicos: cláusulas de Horn e acarretamento

A maioria dos sistemas clássicos de ILP aprende regras em uma forma semelhante ao Prolog chamada cláusula definida (definite clause) (uma cláusula de Horn com exatamente um literal positivo):

head(X) :- body1(X), body2(X,Y), body3(Y).

Interpretação: a cabeça é verdadeira se todos os literais do corpo forem verdadeiros.

Exemplo:

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

A ILP se baseia em uma noção de acarretamento lógico (logical entailment): dado o conhecimento de fundo B e a hipótese (regras aprendidas) H, queremos que B ∪ H acarrete os exemplos positivos e (idealmente) não acarrete os negativos.

Em muitos cenários de ILP, a suposição de programação lógica de resolução SLD (SLD-resolution) e uma hipótese de mundo fechado (closed-world assumption) (o que não pode ser provado é falso) é usada operacionalmente, embora a semântica exata dependa do sistema e do cenário de aprendizagem.

Configuração central do problema de ILP

Entradas e saídas

Um problema canônico de ILP é:

Conhecimento de fundo: B (um programa lógico: fatos + regras)
Exemplos positivos: E⁺ (fatos que queremos que sejam acarretados)
Exemplos negativos: E⁻ (fatos que queremos que não sejam acarretados)
Linguagem de hipóteses: ℒ (que tipo de regras é permitido)

Objetivo: encontrar uma hipótese H ⊆ ℒ tal que:

Completude: para todo e ∈ E⁺, B ∪ H ⊨ e
Consistência: para todo e ∈ E⁻, B ∪ H ⊭ e

Na prática, como os dados podem ser ruidosos ou incompletos, a ILP frequentemente otimiza uma pontuação (score) (acurácia, compressão, MDL, verossimilhança etc.) em vez de satisfazer restrições perfeitamente.

O que torna a ILP diferente do ML “normal”?

A ILP é relacional e orientada por conhecimento:

Exemplos não são vetores; eles são átomos lógicos (por exemplo, grandparent(alice, bob)).
As características não são fixadas de antemão; elas podem ser construídas via predicados lógicos e variáveis.
O conhecimento de fundo pode codificar estrutura rica (por exemplo, simetria, transitividade, restrições de tipo).

Isso é intimamente relacionado à aprendizagem relacional (relational learning) e se sobrepõe a áreas como aprendizagem relacional estatística e síntese de programas.

Cenários de aprendizagem: a partir de acarretamento vs a partir de interpretações

Duas semânticas comuns de aprendizagem:

Aprendizagem a partir de acarretamento (learning from entailment)
Cada exemplo é um átomo instanciado; o sistema tenta fazer com que ele seja acarretado. Isso é comum na ILP clássica (estilo FOIL/Progol).
Aprendizagem a partir de interpretações (learning from interpretations)
Cada exemplo é uma “interpretação” (um pequeno banco de dados/mundo), e você aprende regras que classificam mundos. Isso é comum em abordagens de árvore de decisão relacional (por exemplo, TILDE).

A distinção importa para escalabilidade e para tarefas como classificação vs descoberta de regras.

Linguagem de hipóteses e viés indutivo

O poder da ILP vem de espaços de hipóteses expressivos — e sua dificuldade vem de buscá-los de forma eficiente. Portanto, o viés indutivo (inductive bias) é central.

Espaço de hipóteses: que regras são permitidas?

Restrições típicas incluem:

Cláusulas de Horn (frequentemente cláusulas definidas)
Limites em:
- número de literais no corpo
- profundidade de recursão
- quais predicados podem aparecer
- conectividade de variáveis (restrição de alcance / segurança)

Essas restrições equilibram expressividade e tratabilidade.

Generalidade e θ-subsunção

A ILP precisa de uma forma de comparar hipóteses por “generalidade”.

Um conceito-chave é a θ-subsunção (θ-subsumption): a cláusula C1 é mais geral do que C2 se existir uma substituição θ tal que C1θ ⊆ C2 (intuitivamente, C1 cobre ao menos o que C2 cobre). Muitos operadores de refinamento e procedimentos de busca dependem dessa ordenação.

Viés de linguagem vs viés de busca

Dois tipos de viés são comumente distinguidos:

Viés de linguagem (language bias): restringe o que pode ser expresso (por exemplo, “o corpo pode usar parent/2 mas não likes/2”; “máx. 3 literais no corpo”; “sem símbolos de função”).
Viés de busca (search bias): guia como buscamos no espaço (por exemplo, gulosa vs melhor-primeiro; preferir regras mais curtas; objetivo MDL).

Um mecanismo popular de viés de linguagem são as declarações de modo (mode declarations) (usadas por Progol/Aleph), que especificam como predicados podem ser usados e como variáveis podem ser introduzidas.

Exemplo (ilustrativo):

% head: grandparent(+person, +person)
% body: parent(+person, -person) introduces a new variable
% body: parent(+person, +person) uses existing variables
modeh(grandparent(+person, +person)).
modeb(parent(+person, -person)).
modeb(parent(+person, +person)).

Isso reduz dramaticamente o espaço de hipóteses.

Invenção de predicados e recursão

Alguns sistemas de ILP podem inventar novos predicados (conceitos latentes) e aprender definições recursivas. Isso é crucial para aprender estrutura algorítmica (listas, caminhos, gramáticas), mas aumenta a complexidade de busca.

Aprendizagem Meta-Interpretativa (Meta-Interpretive Learning, MIL) (por exemplo, Metagol) é uma estrutura proeminente para aprender programas recursivos usando modelos de regras de nível mais alto (“metarregras (metarules)”).

Sistemas e algoritmos comuns de ILP

Sistemas de ILP diferem principalmente em como buscam regras e como as pontuam.

FOIL (First Order Inductive Learner)

FOIL é um algoritmo clássico de ILP top-down (de cima para baixo) que aprende regras por especialização:

Comece com uma cláusula muito geral (corpo vazio).
Iterativamente adicione literais ao corpo para reduzir a cobertura de exemplos negativos.
Usa uma heurística tipo ganho de informação (análoga a divisões em árvores de decisão).

Esboço:

Aprenda uma regra que cubra muitos positivos e poucos negativos.
Remova os positivos cobertos e repita (abordagem separar-e-conquistar / cobertura).

O FOIL é historicamente importante e intuitivo, mas pode ter dificuldades com:

conhecimento de fundo complexo,
recursão,
dados ruidosos sem tratamento cuidadoso.

Progol e Aleph (acarretamento inverso / orientação bottom-up)

Progol introduziu o acarretamento inverso (inverse entailment), combinando ideias bottom-up (de baixo para cima) e top-down:

Para um exemplo positivo selecionado e, construa uma explicação mais específica possível (frequentemente via uma “cláusula de base (bottom clause)”) usando B.
Em seguida, busque uma generalização dessa cláusula de base que ainda explique positivos e evite negativos.

Aleph é um sistema de ILP open-source amplamente usado, inspirado no Progol, oferecendo controles práticos (modos, limites de busca, tratamento de ruído).

Por que isso importa: construir uma cláusula de base pode focar a busca em hipóteses que são relevantes para um exemplo, frequentemente melhorando a eficiência.

GOLEM e (relativa) generalização menos geral

Alguns métodos de ILP constroem regras por generalização a partir de exemplos, por exemplo via (relativa) generalização menos geral (relative least general generalization, lgg). Essas abordagens são mais bottom-up:

Calcule uma generalização que cubra múltiplos exemplos.
Use conhecimento de fundo para “relativizar” a generalização.

Esses métodos são conceitualmente elegantes, mas podem se tornar caros ou gerais demais sem um viés forte.

TILDE: árvores de decisão relacionais

TILDE adapta o aprendizado de árvores de decisão a dados relacionais:

Nós testam consultas de primeira ordem (por exemplo, “existe Y tal que parent(X,Y)?”).
Folhas predizem um rótulo de classe.

Isso é útil quando a saída é classificação, e não um conjunto de regras de Horn para dedução.

ILASP: ILP com Programação por Conjuntos de Respostas (ASP)

ILASP aprende programas lógicos sob semântica de ASP (Answer Set Programming), que pode representar raciocínio não monotônico (non-monotonic reasoning) (regras com padrões e exceções). Isso é valioso quando você precisa de raciocínio no estilo “senso comum” além de cláusulas de Horn.

Trade-off: aprendizagem baseada em ASP pode ser computacionalmente mais pesada, mas mais expressiva.

Aprendizagem Meta-Interpretativa (Metagol)

Sistemas MIL (por exemplo, Metagol) aprendem programas usando metarregras como:

P(A,B) :- Q(A,C), R(C,B).

Ao instanciar metarregras, a MIL pode:

aprender definições recursivas,
inventar predicados,
aprender programas compactos a partir de poucos exemplos.

Isso está fortemente conectado à síntese de programas e à pesquisa neuro-simbólica moderna.

Exemplo trabalhado: aprendendo uma regra de família

Suponha que temos fatos de fundo:

parent(alice, bob).
parent(bob, carol).
parent(alice, dave).
parent(dave, emma).
parent(frank, bob).

Exemplos positivos (relações de avós que queremos):

grandparent(alice, carol).
grandparent(alice, emma).
grandparent(frank, carol).

Exemplos negativos (não são avós):

grandparent(bob, carol).
grandparent(carol, emma).

Um sistema típico de ILP poderia aprender:

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

Essa regra generaliza além dos exemplos. Por exemplo, ela acarretaria grandparent(frank, carol) porque parent(frank,bob) e parent(bob,carol) estão em B.

Ponto-chave: a ILP não está “memorizando pares”. Ela aprende um padrão relacional com uma variável intermediária Y.

ILP e grafos de conhecimento: aprendizagem de regras em escala

Grafos de conhecimento (KGs) representam fatos como triplas (sujeito, relação, objeto), por exemplo:

parent(alice, bob)
bornIn(person, city)

Regras de Horn no estilo ILP se mapeiam naturalmente para modelos de regras em KGs:

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).
locatedIn(X,Z) :- locatedIn(X,Y), locatedIn(Y,Z).   % transitivity (if valid)

Similaridades

Ambos são representações relacionais.
Ambos suportam inferência lógica (completude baseada em regras).
Ambos se beneficiam de restrições de fundo (tipos, domínios/faixas, axiomas de ontologia).

Isso se sobrepõe diretamente a Regras, Ontologias, Grafos de Conhecimento e parcialmente a Lógicas de Descrição (embora LDs enfatizem fragmentos decidíveis e raciocínio sobre ontologias, enquanto a ILP enfatiza aprender regras a partir de dados).

Diferenças e questões práticas em KGs

Hipótese de Mundo Aberto (Open World Assumption, OWA)
Muitos KGs são incompletos: fatos ausentes não são necessariamente falsos. A ILP clássica frequentemente espera exemplos negativos explícitos; portanto, a aprendizagem de regras em KGs frequentemente usa:
- amostragem negativa (assumir que algumas triplas não observadas são falsas),
- medidas de confiança em vez de consistência rígida.
Escala
KGs modernos podem ter milhões de entidades/triplas. A ILP tradicional pode ter dificuldade, a menos que seja fortemente restringida ou implementada com otimizações no estilo de banco de dados.
Mineração de regras vs ILP
Sistemas de mineração de regras em KGs (por exemplo, mineradores no estilo AMIE, aprendizes de regras baseados em caminhos) são conceitualmente próximos da ILP, mas frequentemente:
- restringem formas de regras (por exemplo, regras em cadeia),
- usam suporte/confiança em vez de cobertura baseada em acarretamento,
- enfatizam escalabilidade e contagem aproximada.

Complementaridade com embeddings

Métodos de embeddings de KG (veja Embeddings de Grafo de Conhecimento) são bons em generalização estatística, mas são menos interpretáveis. Regras no estilo ILP podem:

fornecer explicações (“por que isso foi previsto?”),
codificar restrições rígidas,
melhorar a precisão ao impor estrutura.

Pipelines híbridos comumente usam embeddings para propor candidatos e regras para validá-los ou explicá-los.

ILP em métodos neuro-simbólicos

I.A. neuro-simbólica (Neuro-symbolic AI) combina aprendizagem neural com representações simbólicas e raciocínio. A ILP contribui com o lado simbólico: regras explícitas e generalização estruturada.

Padrões-chave de integração:

Aprendizagem diferenciável de regras (differentiable rule learning): aprender pesos/estruturas de regras usando métodos baseados em gradiente (por exemplo, encadeamento direto diferenciável, unificação suave). Esses métodos trocam exatidão por treinabilidade com ferramentas de aprendizado profundo.
Orientação neural para busca em ILP (neural guidance for ILP search): modelos neurais propõem literais/regras promissoras; a ILP as verifica logicamente.
Percepção + ILP: um modelo neural mapeia entradas brutas (imagens/texto) para símbolos, então a ILP aprende regras sobre esses símbolos (útil para interpretabilidade e generalização few-shot).

Tópicos relacionados frequentemente discutidos junto com ILP incluem I.A. Neuro-Simbólica e Programação Probabilística, pois muitos sistemas modernos incorporam incerteza.

Aplicações práticas

A ILP é uma excelente escolha quando você tem dados estruturados, conhecimento de domínio e precisa de regras explicáveis.

Aplicações comuns incluem:

Bioinformática e química
- Aprender regras que relacionam subestruturas à atividade
- Modelar propriedades relacionais (moléculas como grafos, interações)
Extração de informação e completude de ontologias/BC (KB)
- Induzir regras para inferir novos fatos em grafos de conhecimento corporativos
Segurança e fraude
- Regras sobre dados relacionais de eventos (quem acessou o quê, de onde, após quais ações)
Robótica e planejamento
- Aprender pré-condições/efeitos de ações a partir de rastros quando combinado com planejadores simbólicos
Síntese de programas e aprendizagem de conceitos
- Aprender definições recursivas ou programas de processamento de listas em sistemas no estilo MIL

Uma vantagem recorrente é a auditabilidade: hipóteses aprendidas podem ser inspecionadas, testadas e curadas como código normal.

Considerações de avaliação e implantação

Métricas

Dependendo da tarefa, você pode avaliar:

Acurácia de regras em exemplos de teste
Precisão/recall (especialmente com positivos/negativos desbalanceados)
Cobertura: quantos positivos são explicados
Complexidade do modelo: número/tamanho das regras (frequentemente ligado à interpretabilidade)

Alguns sistemas usam objetivos no estilo Comprimento Mínimo de Descrição (Minimum Description Length, MDL): preferir hipóteses que comprimam os dados (explicar muitos fatos com poucas regras).

Ruído, contradições e incompletude

Dados reais frequentemente violam suposições lógicas estritas. Sistemas práticos de ILP lidam com isso por meio de:

permitir alguns exemplos classificados incorretamente (parâmetros de “ruído”),
pontuar regras probabilisticamente ou com restrições suaves,
usar amostragem negativa cuidadosa (especialmente em KGs).

Restrições operacionais

Integração com banco de dados importa: avaliar cláusulas candidatas pode se tornar uma carga de trabalho pesada em junções.
Projeto de viés (modos, limites de profundidade) frequentemente domina o desempenho; a ILP raramente é “plug-and-play”.
Recursão pode ser poderosa, mas computacionalmente arriscada sem limites fortes.

Limitações e direções atuais de pesquisa

Escalabilidade

A ILP clássica pode ser cara devido à busca combinatória e à avaliação repetida de consultas. Melhorias de pesquisa e engenharia incluem:

empurrar a avaliação para motores Datalog / backends SQL,
busca aproximada e amostragem,
paralelização e cache,
modelos de regras restritos para KGs grandes.

Melhor tratamento de incerteza

Sistemas modernos frequentemente avançam em direção à ILP probabilística (probabilistic ILP) ou à aprendizagem relacional estatística (statistical relational learning), onde regras têm pesos ou probabilidades (relacionado a Modelos Gráficos Probabilísticos). Isso ajuda com rótulos ruidosos e grafos de conhecimento incompletos.

Aprendizagem neuro-simbólica e aprendizagem de representações

Trabalhos atuais exploram:

usar redes neurais para orientar busca simbólica,
camadas lógicas diferenciáveis para aprender regras de ponta a ponta,
combinar embeddings (similaridade/generalização rápida) com regras (estrutura e garantias).

Interação com modelos de base

Uma direção prática emergente é usar grandes modelos de linguagem para:

propor predicados/regras candidatas,
gerar modelos de conhecimento de fundo,
auxiliar o refinamento de regras com humano no loop,

enquanto ainda se depende de avaliação no estilo ILP para garantir correção lógica contra os dados.

Resumo

A Programação Lógica Indutiva aprende regras lógicas a partir de exemplos mais conhecimento de fundo, tipicamente como cláusulas de Horn. Seus pontos fortes definidores são:

Aprendizagem relacional (lida naturalmente com grafos e estrutura multi-entidade)
Uso de conhecimento de fundo (forte generalização quando existe estrutura prévia)
Interpretabilidade (regras são legíveis e verificáveis)

Os desafios centrais da ILP — complexidade de busca, ruído e escala — impulsionaram um ecossistema rico de algoritmos (FOIL, Progol/Aleph, ILASP, MIL/Metagol) e conexões modernas com aprendizagem de regras em grafos de conhecimento e métodos neuro-simbólicos.