Self-Supervised Inductive Logic Programming

Ce papier présente Poker, un nouvel algorithme d'apprentissage logique inductif auto-supervisé capable de générer automatiquement des exemples positifs et négatifs pour apprendre des programmes récursifs sans théorie de fond ni exemples négatifs fournis par un expert, surpassant ainsi le système Louise qui tend à sur-généraliser dans ce contexte.

L'essentiel

🎩 Le Problème : L'Élève qui a besoin d'un Professeur trop exigeant

Imaginez que vous voulez apprendre à un enfant à reconnaître des formes géométriques (des triangles, des carrés, etc.).
Dans la méthode traditionnelle (appelée ILP ou Programmation Logique Inductive), vous devez fournir à l'enfant deux choses :

1. Des exemples positifs : "Voici un triangle."
2. Des exemples négatifs : "Ce n'est PAS un triangle."
3. Un manuel de règles très précis : Vous devez lui expliquer à l'avance ce qu'est un angle, une ligne droite, etc., en fonction de ce que vous voulez qu'il apprenne.

Le problème ? C'est épuisant ! Pour chaque nouveau sujet (apprendre à reconnaître des oiseaux, puis des voitures, puis des poèmes), vous devez réécrire tout le manuel et choisir manuellement les exemples "qui ne sont pas ça". C'est comme si vous deviez réinventer la grammaire française à chaque fois que vous voulez apprendre à quelqu'un à écrire un poème.

🃏 La Solution : Poker, le Détective Autonome

L'auteur, Stassa Patsantzis, a créé un nouveau système appelé Poker. Le nom fait référence à un jeu de cartes, mais aussi à une métaphore philosophique (le "poker" de Wittgenstein contre Popper).

Comment Poker fonctionne-t-il ?
Au lieu d'avoir un manuel rigide et une liste de "mauvais exemples" fournie par un humain, Poker utilise une approche auto-supervisée.

1. Il a un manuel "Universel" : Au lieu d'un manuel spécifique, Poker a un seul manuel très général (appelé SONF ou "Forme Normale Définitive d'Ordre Second"). C'est comme si on lui donnait un livre qui explique toutes les règles possibles de la logique, sans se soucier du sujet précis. C'est un cadre très large, capable de décrire n'importe quelle grammaire.
2. Il joue aux devinettes : Poker reçoit quelques exemples "positifs" (par exemple : "Voici une phrase correcte"). Il n'a pas d'exemples négatifs ("Voici une phrase incorrecte").
3. Il génère ses propres erreurs : C'est là que la magie opère. Poker imagine lui-même des phrases, les teste, et se dit : "Attends, si ma théorie actuelle est vraie, cette phrase que j'ai inventée devrait être vraie. Mais elle semble bizarre. Donc, ma théorie est peut-être fausse."
4. Il se corrige : En générant ses propres exemples (positifs et négatifs) et en vérifiant s'ils sont cohérents, Poker affine sa théorie. C'est comme un détective qui crée des scénarios de crime pour voir si son suspect tient la route. S'il trouve une contradiction, il rejette sa théorie et en cherche une meilleure.

🌳 L'Analogie du Jardinier et des Plantes

Pour bien comprendre, imaginons que nous voulons apprendre à un jardinier à reconnaître une plante spécifique (disons, un cactus).

• L'approche ancienne (Louise) : Vous donnez au jardinier une photo de cactus et vous lui dites : "C'est un cactus". Mais vous ne lui donnez aucune photo de plante qui n'est pas un cactus. Le jardinier, pour ne pas se tromper, va conclure que tout est un cactus (même un arbre ou une fleur). Il a "sur-généralisé". Il manque de "mauvais exemples" pour savoir où s'arrêter.
• L'approche Poker : Vous donnez au jardinier une photo de cactus et un manuel de botanique très général. Le jardinier commence à inventer des plantes dans sa tête : "Et si je faisais une plante avec des épines et des feuilles ?". Il se rend compte que sa définition actuelle accepterait cette plante inventée, alors qu'elle ne devrait pas. Il se corrige : "Ah non, un vrai cactus n'a pas de feuilles". Il invente d'autres plantes, teste, et affine sa définition jusqu'à ce qu'elle soit parfaite, sans que vous ayez besoin de lui montrer des photos de "non-cactus".

🚀 Les Résultats : Pourquoi c'est génial ?

Les chercheurs ont testé Poker sur deux types de tâches complexes :

1. Les grammaires informatiques (pour comprendre des langages comme les phrases mathématiques).
2. Les L-Systèmes (des règles pour dessiner des formes fractales, comme des fougères ou des courbes de dragon).

Ce qu'ils ont découvert :

• Plus Poker génère d'exemples "de son cru" (des hypothèses qu'il teste), plus il devient précis.
• Les systèmes anciens (comme Louise), sans exemples négatifs, finissent par tout accepter (ils deviennent trop "gentils" et confondent tout).
• Poker, lui, apprend à faire la différence entre ce qui est vrai et ce qui ne l'est pas, simplement en se posant des questions et en se trompant volontairement pour apprendre.

💡 En Résumé

Poker est un système d'intelligence artificielle qui apprend à apprendre seul.

• Il n'a pas besoin d'un expert humain pour lui dire "ceci est faux".
• Il utilise un cadre de règles très large (le manuel universel).
• Il génère ses propres erreurs, les détecte, et s'améliore continuellement.

C'est une étape majeure pour rendre l'intelligence artificielle moins dépendante des humains pour préparer les données, la rendant plus flexible et capable de résoudre des problèmes nouveaux sans avoir besoin d'un manuel réécrit à chaque fois.

Résumé technique

1. Problématique

L'Inductive Logic Programming (ILP), et plus spécifiquement l'apprentissage méta-interprétatif (MIL), excelle à apprendre des programmes logiques récursifs avec invention de prédicats à partir de peu d'exemples. Cependant, cette capacité repose traditionnellement sur deux hypothèses restrictives :

1. Une théorie de fond (background theory) spécifique au problème : Elle doit être conçue manuellement par un expert pour chaque tâche d'apprentissage.
2. Des exemples négatifs : Un ensemble d'exemples étiquetés comme faux ($E^-$) est nécessaire pour éviter la sur-généralisation (apprendre un programme trop large qui accepte tout).

Le défi central abordé par l'auteur est le suivant : Comment apprendre un programme logique correct sans théorie de fond spécifique et sans exemples négatifs pré-établis ? L'absence d'exemples négatifs conduit souvent les systèmes ILP à sur-généraliser, tandis que la nécessité de théories manuelles limite l'application réelle de l'ILP.

2. Méthodologie : Poker et l'Apprentissage Auto-Supervisé

L'auteur propose un nouveau cadre formel appelé ILP Auto-Supervisé (SS-ILP) et un nouvel algorithme implémenté dans un système nommé Poker.

Le Cadre SS-ILP

Contrairement au cadre standard de l'ILP, le cadre SS-ILP ne fournit pas d'exemples négatifs. Les données d'entrée se composent de :

• Un ensemble d'exemples positifs étiquetés ($E^+$).
• Un ensemble d'exemples non étiquetés ($E^?$), qui peuvent être positifs ou négatifs.
• Une théorie de fond d'ordre supérieur maximalement générale (au lieu d'une théorie spécifique).

L'Algorithme Poker

Poker fonctionne par détection de contradictions et génère automatiquement des exemples pendant l'apprentissage. Le processus itératif est le suivant :

1. Généralisation initiale : Le système construit un ensemble d'hypothèses initiales ($T$) qui acceptent les exemples positifs $E^+$, en utilisant une théorie d'ordre supérieur très générale.
2. Génération d'exemples : L'ensemble d'hypothèses $T$ est exécuté comme un générateur pour produire de nouveaux exemples non étiquetés, qui sont ajoutés à $E^?$.
3. Étiquetage par contradiction (Labeling) :
   • Poker suppose initialement que chaque exemple non étiqueté $e \in E^?$ est négatif.
   • Il retire de l'ensemble $T$ toutes les hypothèses qui acceptent cet exemple $e$.
   • Vérification de cohérence : Si la suppression de ces hypothèses fait que l'ensemble restant $T'$ rejette un exemple positif connu ($E^+$), alors l'hypothèse initiale (que $e$ est négatif) est une contradiction.
   • Correction : L'exemple $e$ est alors re-étiqueté comme positif et ajouté à $E^+$.
4. Convergence : Ce processus spécialise l'ensemble des hypothèses jusqu'à ce qu'il soit cohérent avec tous les exemples étiquetés. La précision de l'étiquetage augmente avec le nombre d'exemples non étiquetés.

Théorie de Fond : Les SONF

Pour remplacer la théorie de fond spécifique, l'auteur introduit les Formes Normales Définies d'Ordre Second (SONF - Second Order Definite Normal Forms).

• Une SONF est un ensemble de méta-règles contraintes (metarules) suffisamment générales pour exprimer n'importe quel programme logique d'une classe donnée (par exemple, toutes les grammaires hors-contexte ou les grammaires L-System).
• L'article définit deux SONF spécifiques :
  • C-GNF (Chomsky-Greibach) : Pour les grammaires hors-contexte (CFL).
  • LNF (Lindenmayer) : Pour les grammaires L-System.
• Ces formes utilisent des contraintes sur les substitutions de variables d'ordre second pour éliminer les récursions inutiles et garantir l'efficacité, sans nécessiter de connaissances spécifiques au domaine.

3. Contributions Clés

1. Nouveau cadre SS-ILP : Une formalisation de l'apprentissage ILP sans exemples négatifs fournis, utilisant des exemples non étiquetés et une théorie générale.
2. Algorithme Poker : Un nouvel algorithme MIL capable de générer et d'étiqueter automatiquement des exemples positifs et négatifs, évitant ainsi la sur-généralisation.
3. Définition des SONF : Introduction des Formes Normales Définies d'Ordre Second, permettant d'utiliser une théorie de fond universelle pour une classe de problèmes, supprimant le besoin de théories "sur-mesure".
4. Preuve théorique : Démonstration que la probabilité de retour d'une hypothèse correcte par Poker augmente de manière monotone avec le nombre d'exemples non étiquetés (Théorème 1).
5. Implémentation et Validation : Création du système Poker en Prolog et validation expérimentale sur des tâches de grammaires.

4. Résultats Expérimentaux

Les expériences comparent Poker à l'état de l'art, le système Louise (qui nécessite des exemples négatifs et une théorie spécifique), sur deux tâches :

• Apprentissage de grammaires L-System (fractales) : Poker apprend à générer des chaînes (Dragon Curve, etc.) avec une précision croissante et une taille d'hypothèse décroissante à mesure que le nombre d'exemples générés automatiquement augmente. En revanche, Louise, privée d'exemples négatifs, sur-généralise massivement (précision générative en baisse, taille de l'hypothèse en hausse).
• Apprentissage de grammaires Hors-Contexte (CFL) : Sur des langages binaires (parité, $a^n b^n$, palindromes, etc.), Poker atteint un taux de vrais positifs (TPR) et de vrais négatifs (TNR) optimaux lorsque le nombre d'exemples générés ($k$) est élevé. Avec $k=0$, Poker sur-généralise (TNR faible), mais la performance s'améliore rapidement avec $k$. Louise sur-généralise systématiquement dans tous les cas.

Conclusion des résultats : La capacité de Poker à générer ses propres exemples négatifs permet d'utiliser une théorie de fond maximale sans risque de sur-généralisation, contrairement aux systèmes classiques.

5. Signification et Impact

Ce travail représente une avancée majeure pour l'accessibilité de l'ILP dans des scénarios réels où l'expertise humaine pour créer des théories de fond et sélectionner des exemples négatifs est coûteuse ou indisponible.

• Réduction de la charge humaine : En automatisant la sélection des exemples négatifs et en utilisant des théories générales (SONF), Poker libère l'utilisateur de la nécessité de concevoir manuellement des biais d'apprentissage complexes pour chaque nouvelle tâche.
• Robustesse : La méthode démontre qu'il est possible d'apprendre des structures logiques complexes (récursives, avec invention de prédicats) à partir de données partiellement étiquetées, comblant ainsi un fossé entre l'ILP symbolique et les méthodes d'apprentissage auto-supervisé modernes (comme le contraste dans le Deep Learning).
• Généralité : L'approche ouvre la voie à l'application de l'ILP à des domaines diversifiés au-delà de la grammaire, tant qu'une forme normale d'ordre second peut être définie.

En résumé, Poker transforme l'ILP en un système capable d'apprendre de manière autonome à partir de données brutes et partiellement étiquetées, en remplaçant le besoin d'expertise manuelle par des mécanismes algorithmiques de génération et de détection de contradictions.