LeDevNovice apprend XState avec vous - Semaine 2

Salut,

La semaine dernière, on est partis en 1936 à la rencontre de ce merveilleux jeune homme qu’est Alan Turing. J'avais retenu 5 principes fondamentaux, et surtout cette idée qui m'avait marqué : le calcul est un processus de changement d'état.

Cette semaine, j'ai avancé sur la frise. On est en 1943. Et là, deux scientifiques vont me faire réaliser un truc que je n'avais pas vu venir : les machines à état, c'est pas juste un concept de mathématicien en fait. C'est un truc que la nature utilise déjà.

Pour comprendre ce qui va se passer en 1943, il faut une nouvelle fois que je vous pose le décor les ami(e)s codeurs.

D'un côté, les neurosciences. Dans les années 1930-40, on sait déjà des choses fondamentales sur le cerveau. On sait qu'un neurone reçoit des signaux, les traite, et émet éventuellement un signal. Et surtout, on sait que ce signal est de type tout-ou-rien. Soit le neurone "tire", soit il ne tire pas. Pas d'entre-deux. C'est binaire. On sait aussi que les connexions entre neurones peuvent être dites excitatrices ("tire !") ou inhibitrices ("ne tire pas !"), et que le neurone décide en fonction de la somme des signaux reçus. Si ça dépasse un certain seuil, il tire. Comme un air de déjà vu non ?

De l'autre côté, la logique mathématique. Turing, Church, Gödel entre autres. On en a parlé la semaine dernière. On manipule des valeurs qui sont soit vraies soit fausses. Encore du binaire. Et on combine ces valeurs avec des opérateurs : ET, OU, NON.

Ces deux domaines existent côte à côte. Mais a l’époque, personne ne fait le lien. Les biologistes regardent dans leurs microscopes. Les logiciens griffonnent des symboles. Personne ne voit la connexion, alors qu'avec le recul elle est presque évidente. Un neurone qui tire ou ne tire pas, c'est une proposition qui est vraie ou fausse. Des synapses excitatrices, c'est un OU. Des synapses inhibitrices, c'est un NON. Un seuil d'activation, c'est un opérateur logique.

Il fallait quelqu'un pour voir ça. Il en fallait même deux.

Warren McCulloch est neurophysiologiste et philosophe. Sa question obsessionnelle depuis ses études à Yale : "Qu'est-ce qu'un nombre, pour qu'un humain puisse le connaître, et qu'est-ce qu'un humain, pour qu'il puisse connaître un nombre ?" (Ouais, certaines personnes se posent des sacrées questions !). Il est convaincu que la réponse se trouve dans la structure logique du cerveau, pas dans sa chimie.

Walter Pitts est, lui, un génie autodidacte né dans une famille pauvre de Detroit. À 12 ans, il lit les Principia Mathematica de Russell et Whitehead. Un monument de logique formelle que la plupart des doctorants trouvent ardu pendant que moi je lisais des mangas a ce même âge. À 15 ans, il écrit même à Bertrand Russell pour lui signaler des erreurs. À 17 ans, il s'enfuit de chez lui, débarque à Chicago, et se glisse dans des cours à l'université sans y être inscrit. Si ca ce n’est pas de la soif d’apprentissage les ami(e)s codeurs !

McCulloch a la question et la connaissance biologique. Pitts a l'outil mathématique et la rigueur formelle. Leur rencontre à Chicago autour de 1942 est un de ces moments rares où deux esprits complémentaires produisent quelque chose qu'aucun des deux n'aurait pu créer seul.

En décembre 1943, ils publient 18 pages qui vont changer la donne : "A Logical Calculus of the Ideas Immanent in Nervous Activity".

Rien que le titre est une déclaration de guerre. L'activité nerveuse contient des idées, ces idées suivent un calcul logique, et ce calcul est immanent. Il est intrinsèque à la biologie elle-même.

Leur coup de génie, c'est de modéliser le neurone comme une unité logique élémentaire. Et de le simplifier radicalement.

Un neurone McCulloch-Pitts, il :

C'est tout. Et ces simplifications ne sont pas des faiblesses. Faut comprendre les ami(e)s codeurs que c'est là que réside le génie du modèle et de ces personnes. La binarité permet le pont avec la logique. Le temps discret crée des séquences d'états comme chez Turing la semaine dernière. L'inhibition absolue donne le NON logique. Le réseau figé permet de prouver des propriétés.

J'ai personnellement retenu ça comme un enseignement important pour la suite : la simplification n'est pas une perte, c'est un gain. McCulloch et Pitts ont délibérément ignoré la complexité biologique pour révéler la structure logique sous-jacente. C'est probablement exactement ce qu'on fera quand on modélisera un système avec XState : simplifier la réalité pour en extraire la logique essentielle.

Voilà le cœur de leur démonstration. Avec ces neurones formels, on peut construire tous les opérateurs de la logique.

Le OU logique, un neurone avec deux entrées excitatrices et un seuil de 1. "Il me suffit d'un signal pour m'activer." Si au moins une entrée est à 1, ça tire.

Le ET logique, même configuration, mais un seuil de 2. "J'ai besoin de tous les signaux." Ça tire seulement si les deux entrées sont à 1.

La seule différence entre OU et ET, c'est le seuil. La logique émerge du mécanisme de seuil.

Le NON logique, un neurone "toujours actif" avec une entrée inhibitrice. Quand l'entrée est à 1, l'inhibition bloque tout. Résultat, la sortie est l'inverse de l'entrée.

Et puisque ET + OU + NON suffisent pour construire n'importe quelle fonction logique (c'est ce qu'on appelle visiblement la complétude fonctionnelle), ça veut dire qu'un réseau de neurones McCulloch-Pitts peut implémenter toute la logique.

Le cerveau n'est pas juste un sac de réactions chimiques. C'est un circuit logique les ami(e)s codeurs.

Il y a un cas qui m'a particulièrement intéressé : le XOR (OU exclusif). C'est vrai quand exactement une des deux entrées est vraie, pas les deux.

Un seul neurone McCulloch-Pitts ne peut pas le faire. Aucune combinaison de seuil et d'inhibition ne fonctionne. Il faut un réseau. Autrement dit, deux couches de neurones.

La solution, une première couche avec un neurone OU et un neurone ET, puis une couche de sortie qui combine les deux (si OU est actif ET que ET n'est pas actif, alors c'est un XOR).

Ce qui est fondamental ici, c'est que la profondeur du réseau augmente sa puissance de calcul. Un neurone seul est trivial. C'est la combinaison d'unités simples qui crée la complexité. Ce principe-là, on le retrouvera partout. Dans les réseaux de neurones modernes du deep learning, mais surtout, pour nous, dans l'architecture des machines à état. Plutôt que de faire une machine gigantesque, on fait des machines simples qui composent bien ensemble.

Prenons un peu de recul ensemble. À un instant donné, chaque neurone d'un réseau est soit actif (1), soit inactif (0). L'état du réseau, c'est la liste complète de toutes ces activations. Avec 3 neurones, on a 2³ = 8 états possibles. Avec 10 neurones, 1024. Le nombre croît vite, mais il reste fini.

Et à chaque tick d'horloge, le réseau passe d'un état global à un autre, de manière complètement déterministe. Si tu connais l'état actuel et les entrées, tu prédis exactement l'état suivant.

Ça ne vous rappelle pas quelque chose les ami(e)s codeurs ? C'est exactement la définition d'un automate fini, d’une machine à état.

McCulloch et Pitts l'ont prouvé. Tout réseau fini de neurones avec des boucles de rétroaction se comporte comme un automate fini. Et la réciproque est vraie aussi. Pour tout automate fini, on peut construire un réseau de neurones équivalent.

Les réseaux neuronaux et les machines à état sont deux représentations du même concept mathématique.

Et le cerveau humain ? Ses environs 86 milliards de neurones, c'est beaucoup, mais c'est fini. Donc le cerveau se comporte au minimum comme un automate fini astronomiquement complexe. Mais une machine à état quand même.

Au-delà de l'histoire (qui est une nouvelle passionnante à découvrir), cette semaine m'a apporté des intuitions très concrètes pour la suite.

Les états doivent correspondre à des réalités concrètes. Chez Turing, l'état était une abstraction mathématique. Chez McCulloch-Pitts, c'est une réalité physique. Un neurone avec un courant qui circule ou pas. Quand je modéliserai mes machines XState avec vous les ami(e)s codeurs, un état "loading" devra correspondre à une réalité (une requête est en cours). Un état "authenticated" devra correspondre à une réalité (un token existe). Si un état ne correspond à rien d'identifiable, c'est probablement un mauvais état.

Le seuil, c'est l'ancêtre des gardes. Un neurone tire seulement si la stimulation atteint un certain niveau. Dans XState, c'est exactement le concept de garde (guard) : une transition ne se déclenche que si une condition est remplie. Le parallèle est direct.

L'inhibition, c'est le fait que certains événements sont ignorés dans certains états. C'est un des trucs qui m'excite le plus pour la pratique. Quand ta machine est dans l'état "submitting", un deuxième clic sur "Soumettre" est tout simplement... rien. Il n'est pas géré. Il est "inhibé" par l'état. Pas besoin de coder un if (!isSubmitting) partout. L'état lui-même bloque l'événement. Les états impossibles deviennent structurellement impossibles.

McCulloch et Pitts avaient vu ça en 1943 avec les neurones. 80 ans plus tard, c'est le même principe dans nos applis web.

La semaine dernière, Turing m'avait donné 5 principes. McCulloch et Pitts m'en donnent un sixième :

1. L'état détermine le comportement (Turing) enrichi, l'état est une réalité physique, pas juste une abstraction.

2. Le calcul est une série de transitions (Turing)

3. La finitude est une force (Turing)

4. Le déterminisme est un super-pouvoir (Turing)

5. Séparer ce qui est fini de ce qui est variable (Turing)

6. La puissance émerge de la composition d'unités simples (McCulloch-Pitts)

Ce dernier principe, c'est peut-être celui qui aura le plus d'impact dans ma pratique. Ne pas chercher à faire une machine monstrueuse. Faire des machines simples qui composent bien ensemble. C'est le secret des neurones, et d'après ce que j'ai lu, c'est le secret de XState aussi (via le modèle acteur, que vous pouvez déjà retrouvez si vous êtes curieux).

Petit aparté historique, parce que ça m'a fasciné de voir les ramifications. Le papier de McCulloch-Pitts a engendré trois lignées directes :

Les automates finis. Le mathématicien Stephen Kleene a lu leur papier et s'est demandé : "Que peuvent calculer exactement ces réseaux ?" En 1956, il a prouvé que les réseaux McCulloch-Pitts reconnaissent exactement la classe des langages réguliers, et il a inventé pour les décrire... les fameuses expressions régulières. Oui, les regex que vous utilisez peut-être au quotidien sont, par filiation directe, des descendantes du modèle neuronal de 1943.

L'intelligence artificielle. La conférence de Dartmouth en 1956, acte fondateur de l'IA, a rassemblé des chercheurs profondément influencés par McCulloch-Pitts. Von Neumann lui-même les a cités comme influence majeure pour l'architecture des ordinateurs.

Le deep learning. En 1958, Rosenblatt a inventé le perceptron. C’est un neurone McCulloch-Pitts avec apprentissage. La graine qui, 60 ans plus tard, donnera tout ce qu'on appelle "IA" aujourd'hui.

Pour notre parcours, c'est surtout la première lignée qui compte. Sans McCulloch-Pitts, pas de Kleene, pas d'automates finis formalisés, pas de Harel, pas de XState. La chaîne est directe.

On avance sur la frise : Stephen Kleene (1956) et comment il a formalisé les résultats de McCulloch-Pitts en automates finis et inventé les expressions régulières. On va découvrir que les regex qu'on tape machinalement sont, mathématiquement, des machines à état.

On se rapproche du code. Encore un peu de patience les ami(e)s codeurs.

À vendredi prochain,

@LeDevNovice

Je code, je galère, je comprends, je partage.