Self-Supervised Inductive Logic Programming

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

Immagina di voler insegnare a un bambino a riconoscere le regole di un gioco, ma con un problema: non hai un manuale di istruzioni e non puoi dire al bambino quali mosse sono sbagliate.

Questo è esattamente il problema che affronta la ricerca di Stassa Patsantzis, presentata in questo articolo. Il lavoro si concentra su un campo chiamato Programmazione Logica Induttiva (ILP), che è un modo per insegnare ai computer a "pensare" come programmatori, creando regole logiche complesse partendo da esempi.

Ecco una spiegazione semplice, usando metafore quotidiane, di cosa fa questo nuovo sistema chiamato Poker.

1. Il Problema: L'Insegnante che sa troppo (e troppo poco)

In passato, per insegnare a un computer una regola (come la grammatica di una lingua o un pattern matematico), gli umani dovevano fornire due cose:

Esempi positivi: "Guarda, questa frase è corretta".
Esempi negativi: "Guarda, questa frase è sbagliata".
Un manuale di base (Background Theory): Una lista di mattoncini logici già pronti che il computer poteva usare per costruire la regola.

Il problema: Preparare questi "esempi negativi" e quel "manuale" richiede un esperto umano. È come se per insegnare a un bambino a guidare, dovessimo prima scrivere noi il manuale di meccanica e poi elencargli tutti i modi in cui non deve guidare. È lento, costoso e difficile da fare per ogni nuovo compito.

2. La Soluzione: Poker, l'Insegnante "Autodidatta"

L'autrice ha creato un nuovo sistema chiamato Poker (un nome preso da un aneddoto filosofico, non dal gioco di carte). Poker è un sistema di Auto-Supervisione.

Ecco come funziona la sua magia, con un'analogia:

Immagina che Poker sia un detective che deve scoprire le regole di un crimine (il linguaggio da imparare).

Gli indizi iniziali: Ha solo alcune foto di scene del crimine corrette (esempi positivi etichettati).
La confusione: Ha anche un mucchio di foto senza etichetta (esempi non etichettati). Non sa se sono scene di crimine o no.
Nessun manuale: Non ha un libro di leggi pre-scritto, ha solo un dizionario di parole base.

Cosa fa Poker?

Finge e prova: Poker crea una prima ipotesi di regole basata sulle foto corrette.
Crea i suoi nemici: Prende le foto "non etichettate" e dice: "Facciamo finta che questa sia una scena di crimine (negativa)".
Il test del contraddittorio: Se la sua ipotesi attuale accetta anche questa foto "finta", allora c'è un problema. Poker si chiede: "Aspetta, se la mia regola accetta questa foto che ho detto essere sbagliata, allora la mia regola è troppo generica (troppo sciocca) o la foto in realtà è corretta?"
Correzione: Se la regola accetta troppo, Poker la restringe. Se la foto era in realtà corretta, la etichetta come "positiva" e la aggiunge alla lista degli esempi giusti.
Ripetizione: Ripete questo processo, generando sempre più esempi "finti" (sia positivi che negativi) e correggendo le sue regole finché non trova la formula perfetta.

3. La Magia: I "Mattoncini Universali" (SONF)

Di solito, gli esperti devono costruire un set di "mattoncini" (regole di base) specifico per ogni gioco. Se impari il calcio, ti servono mattoncini per il calcio; se impari il tennis, ti servono quelli per il tennis.

Poker usa invece un set di mattoncini chiamato SONF (Second Order Definite Normal Form).

Metafora: Invece di darti un set di LEGO specifico per costruire solo una casa, ti dà un set di LEGO Universali che possono costruire qualsiasi edificio, da una capanna a un grattacielo.
Grazie a questi mattoncini universali, Poker non ha bisogno che l'umano gli dica "ecco i mattoncini per il calcio". Lui sa come usarli da solo per costruire la regola del calcio, del tennis o della grammatica inglese.

4. I Risultati: Più esempi, meno errori

Gli esperimenti mostrano che:

Poker migliora man mano che gli dai più "foto non etichettate". Più esempi ha a disposizione per fare i suoi "esperimenti mentali" (generare esempi falsi e correggersi), più diventa bravo. È come se un bambino imparasse più velocemente se potesse provare a giocare e sbagliare da solo, invece di aspettare che l'adulto gli dica ogni volta "no, non così".
I sistemi vecchi (come Louise) falliscono senza esempi negativi. Senza qualcuno che dica "questo è sbagliato", i vecchi sistemi tendono a diventare troppo generici. Pensano che qualsiasi cosa sia corretta (es. "tutte le frasi sono grammaticalmente corrette"), il che è inutile. Poker, invece, impara a dire "no, questa è sbagliata" da solo.

In Sintesi

Questo paper presenta Poker, un nuovo modo per insegnare ai computer a creare regole logiche complesse (come grammatiche o algoritmi) senza bisogno di un esperto umano che scriva il manuale o elenchi gli errori.

Poker impara da solo, generando i propri "esercizi di allenamento" e correggendo i propri errori, proprio come un umano che impara una nuova abilità provando, sbagliando e adattandosi, invece di leggere solo un manuale noioso. È un passo avanti verso un'intelligenza artificiale che può imparare in modo più autonomo e flessibile.

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

Titolo

Inductive Logic Programming Auto-Supervisionato (Self-Supervised ILP)

1. Il Problema

L'Inductive Logic Programming (ILP), e in particolare l'apprendimento Meta-Interpretativo (MIL), è noto per la sua capacità di imparare programmi logici ricorsivi con predicati inventati a partire da pochi esempi. Tuttavia, l'applicazione pratica di questi sistemi è limitata da due forti dipendenze dall'esperto umano:

Teoria di Background Specifica: La necessità di fornire manualmente una teoria di background (insieme di regole e fatti) tarata specificamente sul problema da risolvere.
Esempi Negativi: La necessità di fornire esempi negativi etichettati manualmente per evitare l'iper-generalizzazione (over-generalisation) del modello appreso.

Il paper si pone la domanda: Cosa succede se non sono disponibili né una teoria di background specifica né esempi negativi? L'obiettivo è formalizzare un nuovo setting in cui il sistema possa imparare solo da esempi positivi etichettati, esempi non etichettati (unlabelled) e una teoria di background il più possibile generale.

2. Metodologia: Poker e l'Approccio Auto-Supervisionato

L'autore presenta Poker, un nuovo sistema MIL che implementa un algoritmo per l'ILP auto-supervisionato (SS-ILP).

A. Il Setting SS-ILP

Invece del setting standard che richiede $E^+$ (positivi), $E^-$ (negativi) e una teoria $B$ specifica, il nuovo setting fornisce:

$E^+$ : Esempi positivi etichettati.
$E?$ : Esempi non etichettati (che possono essere positivi o negativi).
$T = B \cup M$ : Una teoria di background di ordine superiore, dove $B$ è di primo ordine (vocabolario terminale) e $M$ è una Second-Order Definite Normal Form (SONF). La teoria è "massimamente generale" e non specifica per il target.

B. L'Algoritmo di Poker

Poker risolve il problema della mancanza di esempi negativi attraverso un processo iterativo di rilevamento delle contraddizioni:

Generazione Iniziale: Costruisce un insieme di ipotesi $T$ che accettano gli esempi positivi $E^+$ .
Generazione di Esempi: Esegue le ipotesi attuali come generatori per produrre nuovi esempi non etichettati ( $E?$ ), espandendo il dataset.
Etichettatura e Specializzazione: Assume inizialmente che tutti gli esempi non etichettati siano negativi. Rimuove dall'insieme $T$ $T$ tutte le ipotesi che accettano un esempio "negativo".
- Se la rimozione di queste ipotesi fa sì che il sistema non accetti più alcuni esempi di $E^+$ (contraddizione), l'esempio viene ri-etichettato come positivo e spostato in $E^+$ .
- Se la rimozione non crea contraddizioni, l'esempio rimane negativo e le ipotesi che lo accettano vengono scartate.
Convergenza: Il processo si ripete, specializzando l'ipotesi fino a quando non è consistente con tutti gli esempi etichettati.

C. Second-Order Definite Normal Form (SONF)

Un contributo teorico chiave è la definizione di SONF. Invece di creare metarule specifiche per ogni compito, le SONF sono insiemi di metarule vincolate (constrained metarules) sufficientemente generali da poter esprimere qualsiasi programma logico di una certa classe (es. grammatiche context-free o L-System).

C-GNF (Chomsky-Greibach): Una SONF per grammatiche Context-Free (CFG).
LNF (Lindenmayer): Una SONF per grammatiche L-System.
Queste forme normali eliminano la necessità di un'ingegneria manuale delle metarule per ogni nuovo dominio.

3. Contributi Chiave

Nuovo Setting Teorico: Formalizzazione dell'ILP auto-supervisionato (SS-ILP).
Algoritmo Poker: Un nuovo algoritmo MIL che apprende da esempi etichettati e non, generando automaticamente esempi positivi e negativi durante l'addestramento.
Definizione di SONF: Introduzione delle Second-Order Definite Normal Forms come teoria di background universale per classi di programmi, rimuovendo la necessità di teorie specifiche per task.
Dimostrazione Teorica: Prova che la probabilità di ottenere un'ipotesi corretta aumenta monotonicamente con il numero di esempi non etichettati disponibili.
Implementazione: Realizzazione di Poker in Prolog, estendendo l'algoritmo Top Program Construction (TPC).

4. Risultati Sperimentali

Gli esperimenti confrontano Poker con Louise (uno stato dell'arte MIL) su due compiti: apprendimento di grammatiche per Context-Free Languages (CFL) e L-System.

Setup: Entrambi i sistemi ricevono solo esempi positivi etichettati e il vocabolario terminale (nessuna teoria specifica, nessun esempio negativo fornito). Poker ha accesso a un numero variabile ( $k$ ) di esempi non etichettati che genera e etichetta automaticamente.
Risultati su L-System (Frattali):
- Poker: La sua accuratezza generativa aumenta e la dimensione dell'ipotesi diminuisce all'aumentare degli esempi generati automaticamente ( $k$ ).
- Louise: Senza esempi negativi, tende all'iper-generalizzazione (over-generalisation), con un'accuratezza che diminuisce e ipotesi che crescono di dimensione.
Risultati su CFL (Stringhe binarie):
- Quando $k=0$ , Poker ha un alto tasso di veri positivi (TPR) ma un basso tasso di veri negativi (TNR) a causa della mancanza di vincoli negativi.
- All'aumentare di $k$ , sia TPR che TNR aumentano fino a massimizzarsi. Poker impara correttamente la grammatica target (es. $1^n0^n$ ) distinguendola da linguaggi più generali (es. $1^n0^m$ ).
- Louise fallisce sistematicamente nel distinguere i linguaggi target da quelli massimamente generali senza esempi negativi.

5. Significato e Implicazioni

Il lavoro di Patsantzis rappresenta un passo significativo verso l'automazione dell'ILP:

Riduzione del Carico Cognitivo: Libera l'utente dalla necessità di fornire manualmente esempi negativi e di progettare teorie di background complesse per ogni nuovo problema.
Generalizzazione: Dimostra che è possibile imparare programmi logici ricorsivi complessi partendo da una teoria di background "grezza" e massimamente generale, purché si disponga di un meccanismo per generare e filtrare esempi negativi.
Validità Teorica: La prova che l'accuratezza migliora monotonicamente con più dati non etichettati offre una garanzia teorica sulla scalabilità dell'approccio.
Applicabilità: L'uso di SONF apre la strada all'applicazione dell'ILP in domini dove la conoscenza di dominio è scarsa o difficile da formalizzare a priori, rendendo l'apprendimento di grammatiche e programmi logici più accessibile e robusto.

In sintesi, Poker trasforma l'ILP da un sistema che richiede una conoscenza esperta profonda e manuale a un sistema auto-supervisionato capace di auto-correggersi e auto-migliorarsi attraverso la generazione di dati sintetici.