ACTIONS
Le langage des molécules ...
Découvrir un langage, c'est automatisable ?
L'acquisition d'un langage, c'est un jeu d'enfant: l'essentiel est achevé avant l'âge de 3 ans
pour la plupart. Si on arrive à apprendre n'importe quelle langue naturelle, ne peut-on
arriver à apprendre cette autre langue naturelle qu'est le langage du génome ? On est
cependant loin de comprendre les mécanismes internes qui permettent cette acquisition
ni même de savoir comment nous représentons mentalement les langages et il nous faut
inventer une approche rationnelle de l'apprentissage. Notons que la démarche n'est pas
tout à fait celle d'un Champollion déchiffrant les hiéroglyphes : on ne dispose pas d'un
langage de référence sur lequel s'appuyer pour comprendre un nouveau langage, il s'agit
bien d'apprendre un nouveau langage simplement à partir d'un échantillon de phrases.
On sait actuellement assez bien modéliser l'apprentissage de langages réguliers. Une idée
simple mais mathématiquement intéressante est de partir d'un langage qui reconnaît uniquement les phrases autorisées. C'est par exemple l'automate de gauche dans la figure. Ensuite, on peut généraliser le langage correspondant (c'est-à-dire accepter plus de phrases)
en fusionnant deux états quelconques (ils deviennent égaux et on conserve l'union des
transitions auxquelles ils participent). La structure mathématique de l'ensemble des possibilités est ce que l'on appelle un treillis, c'est-à-dire un ensemble partiellement ordonné où tout couple d'éléments admet une borne supérieure et une borne inférieure. Si on
considère l'ensemble de tous les états E, c'est en fait le treillis des partitions sur E, c'està-dire l'ensemble des façons de partitionner E en sous-ensembles distincts, ordonné par
l'inclusion sur les partitions. Généraliser, c'est aller de la gauche vers la droite dans le
treillis. Pour savoir jusqu'où le faire et éviter de reconnaître n'importe quel enchaînement
(automate de droite sur la figure) , on peut par exemple dialoguer avec l'utilisateur en proposant l'automate le plus général et en demandant une phrase impossible si le langage est
jugé trop permissif, afin de filtrer progressivement la bonne solution.
L'apprentissage d'un automate d'états fini par
fusion.
Source : Auteur (J. Nicolas)
Le treillis des partitions d'états
correspondant à l'apprentissage d'un langage
régulier à partir des phrases {ac, ag}.
On a effectué un zoom
sur certains éléments du
treillis. Pour les autres, on
a simplement indiqué les
états fusionnés. La double
ellipse est le plus grand langage compatible
avec l'ensemble de phrases impossibles {a,
aag, agg, aca, acg}. Il est constitué des mots
formant une suite éventuellement vicie de
ag terminée par ac (par exemple agagac fait
partie du langage).
0,2
1,3
0 •
1,2
, ©
2,3
Ta.ngent:e Hors-série n°52. L'informatique
0,1,2
0,1,
2,3
0,2,
1,3
0,3,
1,2
0,2,3
,, c,1
Le langage des molécules ...
Découvrir un langage, c'est automatisable ?
L'acquisition d'un langage, c'est un jeu d'enfant: l'essentiel est achevé avant l'âge de 3 ans
pour la plupart. Si on arrive à apprendre n'importe quelle langue naturelle, ne peut-on
arriver à apprendre cette autre langue naturelle qu'est le langage du génome ? On est
cependant loin de comprendre les mécanismes internes qui permettent cette acquisition
ni même de savoir comment nous représentons mentalement les langages et il nous faut
inventer une approche rationnelle de l'apprentissage. Notons que la démarche n'est pas
tout à fait celle d'un Champollion déchiffrant les hiéroglyphes : on ne dispose pas d'un
langage de référence sur lequel s'appuyer pour comprendre un nouveau langage, il s'agit
bien d'apprendre un nouveau langage simplement à partir d'un échantillon de phrases.
On sait actuellement assez bien modéliser l'apprentissage de langages réguliers. Une idée
simple mais mathématiquement intéressante est de partir d'un langage qui reconnaît uniquement les phrases autorisées. C'est par exemple l'automate de gauche dans la figure. Ensuite, on peut généraliser le langage correspondant (c'est-à-dire accepter plus de phrases)
en fusionnant deux états quelconques (ils deviennent égaux et on conserve l'union des
transitions auxquelles ils participent). La structure mathématique de l'ensemble des possibilités est ce que l'on appelle un treillis, c'est-à-dire un ensemble partiellement ordonné où tout couple d'éléments admet une borne supérieure et une borne inférieure. Si on
considère l'ensemble de tous les états E, c'est en fait le treillis des partitions sur E, c'està-dire l'ensemble des façons de partitionner E en sous-ensembles distincts, ordonné par
l'inclusion sur les partitions. Généraliser, c'est aller de la gauche vers la droite dans le
treillis. Pour savoir jusqu'où le faire et éviter de reconnaître n'importe quel enchaînement
(automate de droite sur la figure) , on peut par exemple dialoguer avec l'utilisateur en proposant l'automate le plus général et en demandant une phrase impossible si le langage est
jugé trop permissif, afin de filtrer progressivement la bonne solution.
L'apprentissage d'un automate d'états fini par
fusion.
Source : Auteur (J. Nicolas)
Le treillis des partitions d'états
correspondant à l'apprentissage d'un langage
régulier à partir des phrases {ac, ag}.
On a effectué un zoom
sur certains éléments du
treillis. Pour les autres, on
a simplement indiqué les
états fusionnés. La double
ellipse est le plus grand langage compatible
avec l'ensemble de phrases impossibles {a,
aag, agg, aca, acg}. Il est constitué des mots
formant une suite éventuellement vicie de
ag terminée par ac (par exemple agagac fait
partie du langage).
0,2
1,3
0 •
1,2
, ©
2,3
Ta.ngent:e Hors-série n°52. L'informatique
0,1,2
0,1,
2,3
0,2,
1,3
0,3,
1,2
0,2,3
,, c,1