Découverte :
Généralité autour du concept de machine learning à partir d'automate

Pour beaucoup de personnes, le machine learning consiste à apprendre un classifieur de données. Un exemple d'application principal serait d'être capable de différencier de manière automatique plusieurs variétés d'iris selon la taille de leurs pétales.

Mais selon moi, le machine learning représente beaucoup plus : c'est une science qui permet d'expliquer à un ordinateur comment réaliser une tâche d'apprentissage de manière automatique. Alors oui, cela prend en compte la classification automatique, mais pas que ! La prédiction de séquence, l'inférence grammaticale (qui peut être utile en bio-informatique oui oui !) et tellement d'autres concepts sont englobés dans cette définition. Si bien qu'il me faudrait écrire un livre pour en faire la liste.

Aujourd'hui, je vais me contenter de vous présenter une méthode d’apprentissage automatique à partir d'automate et ses applications. Je vais également faire un aller-retour entre la bioinformatique et le traitement automatique de la langue. Quels sont les concepts et les idées pouvant servir à l'un, et à l'autre? Ces deux disciplines ont des méthodes, des outils, possédant des domaines d'application dans l'autre discipline, et ce bien plus qu'on ne peut l'imaginer. La preuve, j'ai réalisé les deux formations et me sert aujourd'hui de l'ensemble de ces connaissances dans mon stage de master, qui parle de biologie ! Alors voyageons un peu dans ce monde merveilleux qu'est la linguistique, et voyons comment le machine learning est utilisé dans ce domaine pour nous en inspirer.

 

Introduction au concept de machine learning à base d'automate

Un automate c'est quoi? Ce concept nous vient des informaticiens et sert à représenter de manière automatique des méthodes de traitements. Pour vous donner une idée simple (ATTENTION AUX PURISTES : je donne une vision TRÈS simplifiée, à but pédagogique), un automate correspond à un graphe orienté dans lequel il y aura des nœuds (les états), et des arêtes annotées par les transitions entre les états de l'automate. En pratique, l'ensemble des transitions possibles de l'automate constituent l'alphabet de l'automate. En partant d'un état initial, on va pouvoir parcourir l'automate en suivant les transitions proposées à chaque nœud. Les répondeurs téléphoniques automatiques des compagnies d’électricité sont un bon exemple pratique d'automate. En appelant à certains numéros, un automate nous proposera de taper sur les touches de notre téléphone en fonction de ce qu'on souhaite faire.

Ensuite pour tous ceux souhaitant en savoir plus, je recommande l'excellent livre "Grammatical Inférence" de Colin de la Higuera, ses enseignements sont aussi disponibles sur son site web avec des cours reliés à chaque chapitre. Sinon les sites web fournissant des informations sont nombreux, comme par exemple celui-ci.

Mais en quoi faire des automates est du machine learning ? Et bien en machine learning, le but sera de définir comment construire un automate répondant à un problème donné. Voyons un peu à quoi cela ressemble dans les faits.

 

Application au problème d’apprentissage de la langue

Chez les linguistes de tous les pays du monde, il existe le rêve secret de trouver une méthode universelle pour apprendre chaque langue du monde (cette méthode expliquerait par exemple comment le développement cérébral d'un bébé se spécialise jour après jour pour apprendre n'importe quelle langue qui deviendra sa langue maternelle). Une approximation consiste alors à étudier les stress vocaux associés à chaque mot (pour simplifier : la vitesse et l'intensité à laquelle un mot est prononcé), le linguiste va ainsi décomposer la langue en cherchant dans chaque mot l'emplacement de l'accentuation et l'intensité vocale. Il étudiera par la suite les mécanismes de construction d'une phrase et les variations d'intensités et de stress propres à chaque langue.

Quand un informaticien se voit confronté à ce problème-là, une réaction possible est de se dire "je vais faire un apprentissage automatique d'automate sur toutes les langues du monde pour trouver le comportement de chaque langue de manière automatique. J'aurais alors appris toutes les langues du monde avec la même méthode !".

source : http://st2.ullet.net/

Exemple d'automatique linguistique Source : http://st2.ullet.net/

C'est à ce moment que les choses se compliquent : bien que l'idée paraisse simple sur le papier, qu'en est-il en pratique ? Comment, à partir d'un échantillon sur une langue, est-il possible de l'apprendre? C'est la question posée chaque année à tous les étudiants du master Apprentissage et Traitement Automatique de la Langue de Nantes en projet de fin de semestre. À ce jour, aucun étudiant n'a trouvé de réponse universelle, pas même votre rédacteur favori (et ce n'est pas faute d'avoir essayé...). Pour vous présenter un état de l'art autour de cela, je vous propose d'explorer une piste d'idée que j'ai eue pour résoudre ce problème!

walmatjari

Petit exemple de fichier que nous avions à traiter. Pour l'exemple 2 il faut voir ça comme une séquence de mots W0S2 puis W0S0. Chacun d'eux correspondant à des stress d'une langue.

 

Des idées pour résoudre ce problème venu de la bioinformatique

Au début, j'ai eu pour ambition de résoudre ce problème tout seul en me disant que j'aurais une idée extraordinaire que des chercheurs n'auraient pas eue pendant 20 ans. Après lecture de quelques livres sur le sujet... il me restait une semaine pour proposer un rendu et... pas la moindre idée facile à mettre en place. Très clairement, les solutions proposées dans ces livres étaient trop compliquées à implémenter pour moi en une semaine, je n'étais donc pas très fier. Histoire de faire quelque chose d'efficace et amusant, je me suis dit "et si avant d'apprendre de mes données, je réalisais un alignement dessus ?". Pourquoi cela serait-il intéressant ? Car plutôt que d'apprendre sur une suite de séquences, j’apprends sur des séquences qui me sont livrées dans un ordre me permettant de mieux assimiler chacune d'entre elles, mais aussi en positionnant chaque séquence l'une par rapport à l'autre, me donnant une idée de l'information redondante contenue dans mes données. L'ordre étant déterminé par le logiciel d'alignement multiple pour aligner un maximum les motifs récurrents entre chaque séquence il me devient alors plus facile de me dire que la phrase suivante à un motif en commun avec la précédente, trouver ce motif et le valider dans mon apprentissage. Toutes les répétitions dans mon dataset seront alignées, me permettant également d'apprendre plus facilement ce type d’événement dans mon automate !

alimultiple

Exemple de sortie de l'alignement multiple. L'idée était d'aligner les répétitions pour identifier les boucles!

(J'ai dû transformer artificiellement mes séquences en protéines pour pouvoir faire un alignement multiple par ClustalW, mais les datasets sont les mêmes sinon, oui oui je vous le jure ! Bien sûr, j'ai fait en sorte de considérer que chaque acide aminé avait le même poids dans l'alignement.)

Et voilà comment une idée toute simple venue de la bio-informatique m'a permis de ne pas rendre un projet vide. Pour les curieux, après une semaine de travail j'ai réussi à produire une méthode apprenant correctement 10% des langues à ma disposition, et il me restait de nombreuses améliorations à mettre en place, me permettant d'espérer jusqu'à 40% de réussite. Voyons maintenant un peu comment les automates peuvent être utilisés en bioinformatique!

Pour les petits curieux, voici l'automate issu de ce dataset :

toto

Et une langue apprise une ! La langue en question est un patois portant le doux nom de Walmajarri.

Des idées d'applications en bioinformatique

Si j'ai réussi à ne pas vous perdre jusque là, voici pour vous la partie peut-être la plus exploitable de l'article! Actuellement, l’apprentissage d'automate est utilisé par des chercheurs sur Rennes, notamment François Coste. Ces recherches permettent notamment la caractérisation, la classification et la prédiction de fonctions protéiques.

Ce genre de méthode permet notamment l’apparition de programmes tels que Protomata, cet outil accessible en ligne permet à partir d'un ensemble de séquences de protéines appartenant à une même famille d'apprendre un automate/une signature caractéristique de la famille. Cet outil peut être utilisé pour mieux comprendre les spécificités des séquences portant la fonction de la famille et prédire l'appartenance de nouvelles séquences à la famille.

Une autre équipe a également utilisé ce genre de concept pour l'analyse d'image, et la détection de cancer du sein de manière automatique. L'automate est ici utilisé avec des probabilités pour tenter d'améliorer la prise de décision sur la présence ou l'absence de cancer à chaque analyse d'une nouvelle image. Des simulations de comportements d'étudiants on put également être faite à partir de ce type de théorie en considérant un étudiant comme un automate et ses transitions comme ses vitesses de réponse à une question simple.

Quand on cherche la notion d'automate sur Pubmed, on remarque que la notion la plus récurrente est la notion d'automate cellulaire. Bien que le nom semble joli et qu'on trouve assez rapidement un petit modèle appelé "le jeu de la vie", ce concept n'est pas un concept d'automate pouvant s'apprendre, mais plus un système avec des règles définies qui n'évoluent pas dans le temps. Ce genre de théorie ne fait donc pas partie du machine learning (bien qu'ayant pas mal inspiré la recherche en bioinformatique ces dernières décennies).

Conclusion

Bon, maintenant, vous avez pu voir que le machine learning, c'est plein de choses, et qu'il existe des milliers d'idées à en tirer dans notre travail avec un petit exemple réel. Vous avez aussi pu voir que nos liens avec linguistes, et informaticiens experts en traitement automatique de la langue ne sont pas si éloignés en fonction du domaine. En cherchant un peu, il est possible de s'apporter un enrichissement mutuel conséquent. Je suis volontairement resté à un niveau très superficiel tout le long de l'article. D'autres billets du genre plus technique seront à venir, notamment sur la recherche d'informations dans des données textuelles!

Enjoy, et merci aux relecteurs : AnLebreton, Kumquatum et Yoann M !

Ps: Je profite également de ce sujet pour remercier humblement Colin de la Higuera de m'avoir appris autant dans ses enseignements sur le sujet.

Ps 2 : Je ne suis pas dans l'équipe dans le Francois Coste ni dans ces collaborateurs proches ou éloignés. Toute publicité et enthousiasme marqué pour ses recherches ne sont qu'une bien heureuse maladresse.

Ps 3 : L'homme qui distribue des graphes d’apprentissage dans des ruelles sombres, c'est moi.

  • À propos de
  • Bioinformaticien de formation ayant complété son cursus par un master de machine learning appliqué aux langues à Nantes. Actuellement en Doctorat au laboratoire physique théorique de la matière condensé à Paris, ma thèse a pour sujet l'organisation 3D des génomes eucaryotes et les éléments répétés. J'aime python, le machine learning et les techniques d'études des chromosomes.

Un commentaire sur “Généralité autour du concept de machine learning à partir d'automate

  1. J\'aime bien comment vous vous appropriez des concepts informatiques (qui semble bien banal pour un informaticien) et vous leur donnez une autre vie, une autre vision ! bravo bravo !
    On commence à voir à peine l\'effet positif de la pluridisciplinarité !
    Alan Turing n\'était-il pas lui même pluridisciplinaire alliant Math - info - Biologie (morphologie des plantes et des fleurs)...etc .
    Bref, continue ...

    FM.

Laisser un commentaire