Self-Supervised Inductive Logic Programming

Each language version is independently generated for its own context, not a direct translation.

Imagine que você está tentando ensinar um robô a escrever poemas ou a desenhar formas complexas, como fractais. Normalmente, para fazer isso, você precisaria ser um especialista: teria que escrever manualmente todas as regras de gramática (o "livro de instruções") e criar uma lista enorme de exemplos do que é um poema "certo" e do que é um "erro". Isso é trabalhoso, chato e limita o que o robô pode aprender.

Este artigo apresenta uma nova maneira de fazer as coisas, chamada Poker (não o jogo de cartas, mas uma referência a um conceito filosófico). O Poker é um sistema de inteligência artificial que aprende de forma auto-supervisionada.

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: O Professor Exigente

Na aprendizagem tradicional (ILP), o robô precisa de um professor humano que:

Dê exemplos positivos (o que é bom).
Dê exemplos negativos (o que é ruim).
Escreva um livro de regras de fundo (background theory) específico para aquele problema.

Se o professor não der exemplos negativos, o robô fica confuso e cria regras muito vagas (como "qualquer coisa é um poema"), o que chamamos de super-generalização. Se o livro de regras for muito específico, o robô não consegue aprender nada além daquele único exemplo.

2. A Solução: O Detetive Poker

O sistema Poker muda as regras do jogo. Ele não precisa de um professor que saiba tudo de antemão. Ele funciona como um detetive inteligente que aprende a partir de:

Alguns exemplos positivos (que você sabe que estão certos).
Muitos exemplos "sem rótulo" (você não sabe se são certos ou errados).
Um livro de regras muito genérico (como um dicionário básico de palavras, sem regras de gramática complexa).

Como ele aprende? (A Analogia do "Teste de Contradição")
Imagine que o Poker cria várias teorias (hipóteses) sobre como o mundo funciona.

Ele pega um exemplo "sem rótulo" e assume que ele é um erro (negativo).
Ele testa suas teorias com essa suposição.
Se essa suposição fizer com que uma teoria rejeite um exemplo que você sabe que é correto (um positivo), o Poker percebe: "Ops! Essa teoria não pode estar certa, porque ela está rejeitando algo bom."
Então, ele descarta essa teoria e, em vez disso, marca aquele exemplo "sem rótulo" como correto (positivo).

É como se o robô estivesse jogando xadrez consigo mesmo: "Se eu assumir que esta peça é ruim, minha estratégia inteira desmorona. Portanto, essa peça deve ser boa."

3. O Truque Mágico: Gerar Próprios Exemplos

O grande diferencial do Poker é que ele cria seus próprios exemplos negativos e positivos durante o aprendizado.

Ele usa o que já aprendeu para gerar novas frases ou desenhos.
Se o que ele gera parece estranho ou contradiz o que ele sabe, ele usa isso para refinar suas regras.
Quanto mais exemplos ele gera e testa, mais preciso ele fica. É como um músico que pratica sozinho: quanto mais ele toca e ouve os erros, melhor fica a música.

4. O "Livro de Regras" Universal (SONF)

Antes, cada tarefa exigia um livro de regras feito sob medida. O Poker usa algo chamado Forma Normal Definitiva de Segunda Ordem (SONF).

Analogia: Em vez de dar ao robô um manual específico para "fazer bolo", você dá a ele um manual de "cozinha universal" que explica como misturar ingredientes, cozinhar e assar, mas não diz exatamente o que é um bolo.
Com esse manual universal, o Poker consegue aprender a fazer bolos, pães ou tortas, desde que você lhe dê alguns exemplos do que você quer. Ele descobre as regras específicas sozinho.

5. Os Resultados: Poker vs. Louise

Os autores testaram o Poker contra outro sistema famoso chamado Louise.

Louise: Sem exemplos negativos, ela ficava confusa e criava regras muito genéricas (super-generalização). Era como um aluno que, sem correção, acha que "tudo é uma resposta certa".
Poker: À medida que gerava mais exemplos e testava suas teorias, ele aprendia a distinguir o certo do errado com precisão. Ele não super-generalizava e conseguia aprender gramáticas complexas e padrões de desenho (como fractais) apenas com poucos exemplos iniciais.

Resumo Final

O Poker é um sistema de IA que aprende a aprender.

Antes: Você precisava ser um especialista para ensinar o robô (dar exemplos negativos e regras específicas).
Agora: Você só precisa dar alguns exemplos positivos e um dicionário básico. O robô usa a lógica para criar seus próprios testes, descobrir seus próprios erros e refinar suas regras até ficar perfeito.

É como se você ensinasse uma criança a andar de bicicleta apenas mostrando o caminho certo, e ela mesma descobrisse, através de quedas e tentativas, como equilibrar-se, sem que você precisasse explicar a física da gravidade ou segurar a bicicleta o tempo todo.

Each language version is independently generated for its own context, not a direct translation.

Título: Self-Supervised Inductive Logic Programming

Autor: Stassa Patsantzis (German University of Digital Sciences)
Sistema Proposto: Poker

1. O Problema

A Programação Lógica Indutiva (ILP), e especificamente a Aprendizagem Meta-Interpretiva (MIL), é capaz de aprender programas lógicos recursivos com predicados inventados a partir de poucos exemplos. No entanto, o cenário padrão de ILP enfrenta uma limitação prática significativa:

Dependência de Conhecimento Específico: Os sistemas atuais exigem que o usuário forneça manualmente uma teoria de fundo (background theory) específica para o problema e um conjunto de exemplos negativos.
Custo de Engenharia: A seleção cuidadosa de exemplos negativos e a programação da teoria de fundo exigem conhecimento profundo do domínio e do problema, o que se torna um fardo constante e limita a aplicação de ILP em cenários do mundo real.
O Cenário Não Resolvido: O que acontece se a teoria de fundo específica ou os exemplos negativos não estiverem disponíveis? Como evitar a generalização excessiva (over-generalisation) sem dados negativos explícitos?

2. Metodologia: O Sistema Poker e o Cenário SS-ILP

O autor propõe um novo cenário formal chamado ILP Auto-supervisionada (SS-ILP) e implementa um novo algoritmo no sistema Poker.

A. Definição do Cenário SS-ILP

Diferente do cenário padrão, o SS-ILP recebe:

Exemplos positivos rotulados ( $E^+$ ).
Exemplos não rotulados ( $E?$ ), que podem ser positivos ou negativos.
Uma teoria de fundo de ordem superior maximamente geral (em vez de uma teoria específica para o alvo).
Objetivo: Aprender uma hipótese correta ( $H$ ) e um rótulo ( $L$ ) para os exemplos não rotulados, sem receber exemplos negativos explícitos inicialmente.

B. O Algoritmo Poker

O núcleo do Poker baseia-se na detecção de contradições para gerar e rotular exemplos automaticamente:

Geração Inicial: O sistema constrói um conjunto de hipóteses iniciais ( $T$ ) que aceitam os exemplos positivos rotulados ( $E^+$ ), utilizando uma teoria de fundo maximamente geral.
Geração de Exemplos: O sistema executa as hipóteses em $T$ para gerar novos exemplos não rotulados.
Rotulagem por Contradição:
- O algoritmo assume inicialmente que um exemplo não rotulado ( $e?$ ) é negativo.
- Remove de $T$ todas as hipóteses que aceitam $e?$ .
- Verificação: Se a remoção dessas hipóteses faz com que o conjunto restante ( $T'$ ) rejeite algum exemplo positivo original ( $E^+$ ), ocorre uma contradição. Isso implica que $e?$ não pode ser negativo (pois seria necessário para explicar $E^+$ ).
- Ação: Se houver contradição, $e?$ é reclassificado como positivo e movido para $E^+$ . Caso contrário, é mantido como negativo.
Iteração: Este processo especializa iterativamente o conjunto de hipóteses até que seja consistente com os exemplos positivos, refinando a teoria aprendida.

C. Teoria de Fundo: Second Order Definite Normal Form (SONF)

Para eliminar a necessidade de teorias específicas, o Poker utiliza Formas Normais Definitivas de Segunda Ordem (SONFs).

Uma SONF é um conjunto de metarregras (metarules) com restrições que são suficientemente gerais para expressar qualquer programa lógico de uma classe específica (ex: Gramáticas Livres de Contexto ou L-Systems).
O artigo define duas SONFs principais:
1. C-GNF (Chomsky-Greibach): Para Gramáticas Livres de Contexto (CFLs).
2. LNF (Lindenmayer): Para Gramáticas de Sistemas L.
Essas formas normais garantem que o sistema possa aprender qualquer gramática dentro da classe sem precisar de uma teoria de fundo "costurada" para o problema específico.

3. Contribuições Principais

Novo Cenário Formal: Definição formal do SS-ILP, onde o aprendizado ocorre a partir de exemplos positivos rotulados e não rotulados, sem exemplos negativos explícitos.
Algoritmo e Sistema Poker: Implementação de um novo algoritmo de MIL que aprende, gera e rotula exemplos automaticamente, evitando a generalização excessiva.
Definição de SONFs: Introdução das Formas Normais Definitivas de Segunda Ordem, permitindo teorias de fundo reutilizáveis e maximamente gerais.
Prova Teórica: Demonstração de que a probabilidade de o Poker retornar uma hipótese correta aumenta monotonicamente com o número de exemplos não rotulados disponíveis.
Validação Empírica: Experimentos comparativos mostrando a superioridade do Poker sobre sistemas de ponta (como o Louise) na ausência de exemplos negativos.

4. Resultados Experimentais

Os experimentos foram realizados em duas tarefas: aprendizado de Gramáticas Livres de Contexto (CFLs) e Gramáticas de Sistemas L (L-Systems). O sistema foi comparado com o Louise (um sistema MIL de última geração que não gera exemplos).

Desempenho em L-Systems (Geradores):
- O Poker mostrou aumento na precisão gerativa e redução no tamanho da hipótese à medida que o número de exemplos gerados automaticamente aumentava.
- O Louise, sem exemplos negativos, sofreu de generalização excessiva (over-generalisation), produzindo hipóteses que aceitavam strings incorretas, e seu desempenho degradou com mais exemplos de treinamento.
Desempenho em CFLs (Reconhecedores):
- Com $k=0$ (sem exemplos gerados), o Poker teve alta taxa de verdadeiros positivos (TPR) mas baixa taxa de verdadeiros negativos (TNR), devido à falta de dados negativos.
- À medida que $k$ (número de exemplos gerados) aumentava, tanto a TPR quanto a TNR do Poker aumentaram até atingir o máximo.
- O Louise manteve-se consistentemente com generalização excessiva em todos os experimentos.
Conclusão dos Dados: A capacidade de gerar exemplos negativos automaticamente permite que o Poker utilize uma teoria de fundo maximamente geral sem perder precisão, enquanto sistemas que dependem de dados negativos manuais falham quando esses dados não estão disponíveis.

5. Significado e Impacto

Este trabalho representa um avanço significativo na democratização da Programação Lógica Indutiva:

Redução da Barreira de Entrada: Remove a necessidade de que especialistas em IA definam manualmente teorias de fundo complexas e conjuntos de exemplos negativos para cada novo problema.
Robustez: O sistema torna-se robusto a ruídos e capaz de aprender em cenários onde apenas exemplos positivos (ou dados brutos não rotulados) estão disponíveis.
Generalização: A introdução das SONFs oferece um caminho principiado para criar teorias de fundo reutilizáveis que cobrem classes inteiras de problemas (como linguagens formais), em vez de soluções ad-hoc.
Aplicabilidade: O Poker demonstra que é possível aprender programas lógicos recursivos complexos (com predicados inventados) de forma autônoma, aproximando a ILP de aplicações práticas em cenários do mundo real onde a anotação completa de dados é inviável.

Em resumo, o Poker transforma a ILP de uma disciplina dependente de engenharia de conhecimento intensiva para uma abordagem mais auto-supervisionada e escalável, provando que a geração automática de exemplos negativos é a chave para evitar a generalização excessiva sem dados rotulados negativos.