Tsetlin
Machine
Une approche de l'apprentissage automatique qui produit des règles lisibles, écrites en logique simple : si … et … et non … alors … Cette page la démonte pièce par pièce, avec des animations que vous pilotez vous-même.
D'après Ole-Christoffer Granmo, An Introduction to Tsetlin Machines, chapitres 1 et 4
Qu'est-ce qu'une Tsetlin Machine ?
Une Tsetlin Machine reconnaît des objets en coordonnant plusieurs règles de la forme si condition alors classe. Chaque règle appartient à une classe (par exemple « Voiture ») et apprend seule à reconnaître les objets de cette classe. Pour décider, les règles votent, et la classe qui obtient le plus de voix l'emporte.
La condition d'une règle n'utilise que deux opérateurs : ET et NON. Pas de OU, pas de coefficients cachés. C'est ce qui la rend interprétable : une règle apprise se lit comme une phrase, par exemple si Quatre roues et Transporte des personnes et non Ailes alors Voiture.
Le nom vient de Michael Lvovitch Tsetlin (22 septembre 1924 – 30 mai 1966), mathématicien et physicien soviétique. Il a inventé un algorithme d'apprentissage qui garde la trace de son expérience avec un seul nombre entier, et qui est capable de « changer d'avis ».
Classe : la catégorie à prédire (ici Voiture ou Avion). Apprentissage supervisé : la machine apprend à partir d'exemples dont on lui donne la bonne réponse.
Approximateur universel
Comme les réseaux de neurones, elle peut en principe représenter n'importe quelle fonction.
À base de règles
Comme les arbres de décision, elle produit des règles lisibles par un humain.
À base de sommes
Comme la régression logistique ou le classifieur bayésien naïf, elle additionne des indices (ici, des votes).
Proche du matériel
Elle travaille sur des bits, avec une faible empreinte énergétique et mémoire : adaptée à l'informatique embarquée et à l'IoT.
Source : Granmo, ch. 1, encadrés « Tsetlin Machine Origins » et « Tsetlin Machines vs Black Boxes », p. 8–9 ; §1.2, p. 13–14
Tout devient vrai ou faux
Une Tsetlin Machine ne voit pas l'objet lui-même, seulement ses caractéristiques, et chacune doit être vraie ou fausse. Le livre prend six véhicules (trois voitures, trois avions) décrits par cinq caractéristiques. À chacune on ajoute sa négation (« non Ailes ») : l'ensemble forme les littéraux.
Caractéristique booléenne : une propriété qui ne peut valoir que vrai ou faux (un véhicule est jaune ou ne l'est pas). Littéral : une caractéristique ou sa négation ; la machine traite les deux de la même façon.
| N° | Quatre roues | Transporte des pers. | Ailes | Jaune | Bleu | Classe |
|---|
Source : Granmo, ch. 1, §1.1 et Tableau 1.1, p. 7–9 ; §1.2 « Literals », p. 14
La mémoire d'un littéral
Une mémoire d'ordinateur classique garde ou efface. La Tsetlin Machine imite plutôt la mémoire humaine, qui oublie peu à peu : chaque littéral occupe une position sur une échelle de 1 à 10. De 1 à 5, il est oublié et ne fait pas partie de la règle. De 6 à 10, il est mémorisé et entre dans la condition. Au départ, tous les littéraux sont en position 5 : presque mémorisés, mais encore oubliés.
Exemple : le littéral Quatre roues dans une règle qui prédit « Voiture ».
Source : Granmo, ch. 1, §1.3 « Rule Memory » et « Rule Initialization », Fig. 1.3–1.5, p. 14–16
Reconnaître, effacer, rejeter
On présente les véhicules un par un à une règle chargée de prédire « Voiture ». Selon le cas, elle reçoit l'une de trois rétroactions (feedback : le signal qui ajuste sa mémoire).
Reconnaître (Recognize)
L'objet est une voiture et la condition est vraie : les littéraux vrais montent d'un cran, les faux descendent. La règle se met à ressembler à l'objet.
Effacer (Erase)
L'objet est une voiture mais la condition est fausse : tous les littéraux descendent. La règle s'efface et se simplifie.
Rejeter (Reject)
L'objet est un avion mais la condition est vraie : les littéraux faux pour cet objet et encore oubliés (1 à 5) montent, toujours, sans tirage au sort. La règle apprend à exclure l'avion.
Tirage au sort : avant chaque montée ou descente de Reconnaître et Effacer, on tire un nombre entre 0 et 1. La montée n'a lieu que s'il ne dépasse pas la valeur de mémorisation (ici 0,1), la descente que s'il ne dépasse pas la valeur d'oubli (ici 0,9). Ainsi, aucune coïncidence ne peut bloquer l'apprentissage. Une position ne dépasse jamais 10 et ne descend jamais sous 1.
Barre violette : littéral mémorisé (6 ou plus), donc présent dans la règle. Pointillé : seuil entre 5 et 6. ✓ / ✗ : valeur du littéral pour l'objet présenté. ↑ / ↓ : mouvement appliqué ; « sauté » : le tirage au sort a annulé le mouvement.
Source : Granmo, ch. 1, §1.3 « Examples 1–3 » (Fig. 1.6–1.9, p. 18–22) et §1.4 « Example with Vehicle Data » (Fig. 1.10–1.11, p. 25–26). Scénario du livre : tirages fixés comme dans le texte.
Plusieurs règles votent
Une règle seule n'a pas le dernier mot. Chaque règle dont la condition est vraie vote pour sa classe, et la classe majoritaire l'emporte. La machine combine ainsi des règles détaillées (comme un arbre de décision) et une somme d'indices (comme une régression logistique).
Pendant l'apprentissage, une marge de vote T (Vote Margin, un nombre entier) fixe l'objectif : la bonne classe doit avoir T voix d'avance. On calcule v = voix pour la classe de l'objet − voix pour l'autre classe, ramené entre −T et +T. Chaque règle reçoit alors une rétroaction avec la probabilité (T − v) / (2T). Loin de l'objectif, on corrige beaucoup ; une fois la marge atteinte, on ne touche plus à rien. C'est ainsi que les règles se répartissent les rôles.
Les deux règles du livre (Fig. 1.12) : R1 si Quatre roues et Transporte des personnes et non Ailes alors Voiture (la règle apprise dans l'animation 3) et R2 si Ailes alors Avion. On les applique ici aux six véhicules du Tableau 1.1.
Ces valeurs de v et de p sont calculées par nous avec la formule du chapitre 1 (algorithme, étapes 3 et 4) ; elles ne viennent pas d'un tableau du livre. Le livre ne détaille que le vote du véhicule n°4 : R1 fausse, R2 vraie, Avion l'emporte 1 contre 0. Avec ces deux seules règles, chaque véhicule obtient v = +1 : à T = 2, aucun n'atteint la marge et chacun est mis à jour avec p = 0,25 ; à T = 1, la marge est atteinte (p = 0).
Source : Granmo, ch. 1, §1.5 (Fig. 1.12, règles R1 et R2, vote du véhicule n°4, p. 28–29) et §1.6 (marge de vote et algorithme complet, étapes 3–4, p. 31–32) ; formule générale en T : ch. 4, §4.4, p. 84, et arXiv:1804.01508
Chercher un motif dans une image
Dans une image, un motif peut apparaître n'importe où. Plutôt que d'apprendre une règle par emplacement, on fait glisser une fenêtre de 3 × 3 pixels sur l'image. La règle est testée sur chaque morceau (un patch) : elle est vraie pour l'image si elle correspond à au moins un patch.
Convolution : balayer l'entrée avec une petite fenêtre et appliquer la même règle à chaque position. Ici, pixel noir = vrai, pixel blanc = faux, et Xligne,colonne désigne un pixel de la fenêtre.
si X1,2 et X2,1 et non X2,2 et X2,3 et X3,2 alors Cercle
Lors de l'apprentissage, si plusieurs patchs correspondent, on en choisit un au hasard pour mettre la règle à jour ; le reste suit le chapitre 1.
Source : Granmo, ch. 4, §4.2 (règle R5, p. 78), §4.3 (Fig. 4.3, image et patchs, p. 79–81), §4.4 (p. 82–84)
Ce qu'il faut retenir
Une Tsetlin Machine unifie trois stratégies : trouver des motifs fréquents (Reconnaître et Effacer), les rendre discriminants (Rejeter), et répartir le travail entre plusieurs règles grâce à la marge de vote. Le résultat reste une liste de règles en ET / NON qu'un humain peut lire et vérifier, là où les modèles dits « boîte noire » sont trop complexes pour être compris. Et comme tout se ramène à des bits, le calcul reste léger.
Et pour votre entreprise ?
Vous vous demandez si une IA explicable a sa place dans vos processus ? Parlons-en.
- Ole-Christoffer Granmo, An Introduction to Tsetlin Machines, livre gratuit publié par chapitres sur son site officiel : tsetlinmachine.org. Chapitre 1 « Your First Tsetlin Machine », brouillon daté du 7/11/22, p. 6–36 (PDF du chapitre 1) ; chapitre 4 « Convolution », brouillon daté du 9/12/23, p. 73–88 (PDF du chapitre 4).
- Ole-Christoffer Granmo, « The Tsetlin Machine – A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic », arXiv:1804.01508.
Traduction et simplifications : Xavier Tapia. Les termes anglais du livre sont indiqués entre parenthèses à leur première occurrence.