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

Pour beau­coup de per­sonnes, le machine lear­ning consiste à apprendre un clas­si­fieur de don­nées. Un exemple d'application prin­ci­pal serait d'être capable de dif­fé­ren­cier de manière auto­ma­tique plu­sieurs varié­tés d'iris selon la taille de leurs pétales.

Mais selon moi, le machine lear­ning repré­sente beau­coup plus : c'est une science qui per­met d'expliquer à un ordi­na­teur com­ment réa­li­ser une tâche d'apprentissage de manière auto­ma­tique. Alors oui, cela prend en compte la clas­si­fi­ca­tion auto­ma­tique, mais pas que ! La pré­dic­tion de séquence, l'inférence gram­ma­ti­cale (qui peut être utile en bio-infor­ma­tique oui oui !) et tel­le­ment d'autres concepts sont englo­bés dans cette défi­ni­tion. Si bien qu'il me fau­drait écrire un livre pour en faire la liste.

Aujourd'hui, je vais me conten­ter de vous pré­sen­ter une méthode d’apprentissage auto­ma­tique à par­tir d'automate et ses appli­ca­tions. Je vais éga­le­ment faire un aller-retour entre la bio­in­for­ma­tique et le trai­te­ment auto­ma­tique de la langue. Quels sont les concepts et les idées pou­vant ser­vir à l'un, et à l'autre ? Ces deux dis­ci­plines ont des méthodes, des outils, pos­sé­dant des domaines d'application dans l'autre dis­ci­pline, et ce bien plus qu'on ne peut l'imaginer. La preuve, j'ai réa­li­sé les deux for­ma­tions et me sert aujourd'hui de l'ensemble de ces connais­sances dans mon stage de mas­ter, qui parle de bio­lo­gie ! Alors voya­geons un peu dans ce monde mer­veilleux qu'est la lin­guis­tique, et voyons com­ment le machine lear­ning est uti­li­sé dans ce domaine pour nous en ins­pi­rer.

Introduction au concept de machine learning à base d'automate

Un auto­mate c'est quoi ? Ce concept nous vient des infor­ma­ti­ciens et sert à repré­sen­ter de manière auto­ma­tique des méthodes de trai­te­ments. Pour vous don­ner une idée simple (ATTENTION AUX PURISTES : je donne une vision TRÈS sim­pli­fiée, à but péda­go­gique), un auto­mate cor­res­pond à un graphe orien­té dans lequel il y aura des nœuds (les états), et des arêtes anno­tées par les tran­si­tions entre les états de l'automate. En pra­tique, l'ensemble des tran­si­tions pos­sibles de l'automate consti­tuent l'alphabet de l'automate. En par­tant d'un état ini­tial, on va pou­voir par­cou­rir l'automate en sui­vant les tran­si­tions pro­po­sées à chaque nœud. Les répon­deurs télé­pho­niques auto­ma­tiques des com­pa­gnies d’électricité sont un bon exemple pra­tique d'automate. En appe­lant à cer­tains numé­ros, un auto­mate nous pro­po­se­ra de taper sur les touches de notre télé­phone en fonc­tion de ce qu'on sou­haite faire.

Ensuite pour tous ceux sou­hai­tant en savoir plus, je recom­mande l'excellent livre "Gram­ma­ti­cal Infé­rence" de Colin de la Higue­ra, ses ensei­gne­ments sont aus­si dis­po­nibles sur son site web avec des cours reliés à chaque cha­pitre. Sinon les sites web four­nis­sant des infor­ma­tions sont nom­breux, comme par exemple celui-ci.

Mais en quoi faire des auto­mates est du machine lear­ning ? Et bien en machine lear­ning, le but sera de défi­nir com­ment construire un auto­mate répon­dant à un pro­blème don­né. Voyons un peu à quoi cela res­semble dans les faits.

Application au problème d’apprentissage de la langue

Chez les lin­guistes de tous les pays du monde, il existe le rêve secret de trou­ver une méthode uni­ver­selle pour apprendre chaque langue du monde (cette méthode expli­que­rait par exemple com­ment le déve­lop­pe­ment céré­bral d'un bébé se spé­cia­lise jour après jour pour apprendre n'importe quelle langue qui devien­dra sa langue mater­nelle). Une approxi­ma­tion consiste alors à étu­dier les stress vocaux asso­ciés à chaque mot (pour sim­pli­fier : la vitesse et l'intensité à laquelle un mot est pro­non­cé), le lin­guiste va ain­si décom­po­ser la langue en cher­chant dans chaque mot l'emplacement de l'accentuation et l'intensité vocale. Il étu­die­ra par la suite les méca­nismes de construc­tion d'une phrase et les varia­tions d'intensités et de stress propres à chaque langue.

Quand un infor­ma­ti­cien se voit confron­té à ce pro­blème-là, une réac­tion pos­sible est de se dire "je vais faire un appren­tis­sage auto­ma­tique d'automate sur toutes les langues du monde pour trou­ver le com­por­te­ment de chaque langue de manière auto­ma­tique. J'aurais alors appris toutes les langues du monde avec la même méthode !".

C'est à ce moment que les choses se com­pliquent : bien que l'idée paraisse simple sur le papier, qu'en est-il en pra­tique ? Com­ment, à par­tir d'un échan­tillon sur une langue, est-il pos­sible de l'apprendre ? C'est la ques­tion posée chaque année à tous les étu­diants du mas­ter Appren­tis­sage et Trai­te­ment Auto­ma­tique de la Langue de Nantes en pro­jet de fin de semestre. À ce jour, aucun étu­diant n'a trou­vé de réponse uni­ver­selle, pas même votre rédac­teur favo­ri (et ce n'est pas faute d'avoir essayé…). Pour vous pré­sen­ter un état de l'art autour de cela, je vous pro­pose d'explorer une piste d'idée que j'ai eue pour résoudre ce pro­blème !

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

Au début, j'ai eu pour ambi­tion de résoudre ce pro­blème tout seul en me disant que j'aurais une idée extra­or­di­naire que des cher­cheurs n'auraient pas eue pen­dant 20 ans. Après lec­ture de quelques livres sur le sujet… il me res­tait une semaine pour pro­po­ser un ren­du et… pas la moindre idée facile à mettre en place. Très clai­re­ment, les solu­tions pro­po­sées dans ces livres étaient trop com­pli­quées à implé­men­ter pour moi en une semaine, je n'étais donc pas très fier. His­toire de faire quelque chose d'efficace et amu­sant, je me suis dit "et si avant d'apprendre de mes don­nées, je réa­li­sais un ali­gne­ment des­sus ?". Pour­quoi cela serait-il inté­res­sant ? Car plu­tô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 per­met­tant de mieux assi­mi­ler cha­cune d'entre elles, mais aus­si en posi­tion­nant chaque séquence l'une par rap­port à l'autre, me don­nant une idée de l'information redon­dante conte­nue dans mes don­nées. L'ordre étant déter­mi­né par le logi­ciel d'alignement mul­tiple pour ali­gner un maxi­mum les motifs récur­rents entre chaque séquence il me devient alors plus facile de me dire que la phrase sui­vante à un motif en com­mun avec la pré­cé­dente, trou­ver ce motif et le vali­der dans mon appren­tis­sage. Toutes les répé­ti­tions dans mon data­set seront ali­gnées, me per­met­tant éga­le­ment d'apprendre plus faci­le­ment ce type d’événement dans mon auto­mate !

(J'ai dû trans­for­mer arti­fi­ciel­le­ment mes séquences en pro­téines pour pou­voir faire un ali­gne­ment mul­tiple par Clus­talW, mais les data­sets sont les mêmes sinon, oui oui je vous le jure ! Bien sûr, j'ai fait en sorte de consi­dé­rer que chaque acide ami­né avait le même poids dans l'alignement.)

Et voi­là com­ment une idée toute simple venue de la bio-infor­ma­tique m'a per­mis de ne pas rendre un pro­jet vide. Pour les curieux, après une semaine de tra­vail j'ai réus­si à pro­duire une méthode appre­nant cor­rec­te­ment 10% des langues à ma dis­po­si­tion, et il me res­tait de nom­breuses amé­lio­ra­tions à mettre en place, me per­met­tant d'espérer jusqu'à 40% de réus­site. Voyons main­te­nant un peu com­ment les auto­mates peuvent être uti­li­sés en bio­in­for­ma­tique !

Pour les petits curieux, voi­ci l'automate issu de ce data­set :

Des idées d'applications en bioinformatique

Si j'ai réus­si à ne pas vous perdre jusque là, voi­ci pour vous la par­tie peut-être la plus exploi­table de l'article ! Actuel­le­ment, l’apprentissage d'automate est uti­li­sé par des cher­cheurs sur Rennes, notam­ment Fran­çois Coste. Ces recherches per­mettent notam­ment la carac­té­ri­sa­tion, la clas­si­fi­ca­tion et la pré­dic­tion de fonc­tions pro­téiques.

Ce genre de méthode per­met notam­ment l’apparition de pro­grammes tels que Pro­to­ma­ta, cet outil acces­sible en ligne per­met à par­tir d'un ensemble de séquences de pro­téines appar­te­nant à une même famille d'apprendre un automate/​une signa­ture carac­té­ris­tique de la famille. Cet outil peut être uti­li­sé pour mieux com­prendre les spé­ci­fi­ci­tés des séquences por­tant la fonc­tion de la famille et pré­dire l'appartenance de nou­velles séquences à la famille.

Une autre équipe a éga­le­ment uti­li­sé ce genre de concept pour l'analyse d'image, et la détec­tion de can­cer du sein de manière auto­ma­tique. L'automate est ici uti­li­sé avec des pro­ba­bi­li­tés pour ten­ter d'améliorer la prise de déci­sion sur la pré­sence ou l'absence de can­cer à chaque ana­lyse d'une nou­velle image. Des simu­la­tions de com­por­te­ments d'étudiants on put éga­le­ment être faite à par­tir de ce type de théo­rie en consi­dé­rant un étu­diant comme un auto­mate et ses tran­si­tions comme ses vitesses de réponse à une ques­tion simple.

Quand on cherche la notion d'automate sur Pub­med, on remarque que la notion la plus récur­rente est la notion d'auto­mate cel­lu­laire. Bien que le nom semble joli et qu'on trouve assez rapi­de­ment un petit modèle appe­lé "le jeu de la vie", ce concept n'est pas un concept d'automate pou­vant s'apprendre, mais plus un sys­tème avec des règles défi­nies qui n'évoluent pas dans le temps. Ce genre de théo­rie ne fait donc pas par­tie du machine lear­ning (bien qu'ayant pas mal ins­pi­ré la recherche en bio­in­for­ma­tique ces der­nières décen­nies).

Conclusion

Bon, main­te­nant, vous avez pu voir que le machine lear­ning, c'est plein de choses, et qu'il existe des mil­liers d'idées à en tirer dans notre tra­vail avec un petit exemple réel. Vous avez aus­si pu voir que nos liens avec lin­guistes, et infor­ma­ti­ciens experts en trai­te­ment auto­ma­tique de la langue ne sont pas si éloi­gnés en fonc­tion du domaine. En cher­chant un peu, il est pos­sible de s'apporter un enri­chis­se­ment mutuel consé­quent. Je suis volon­tai­re­ment res­té à un niveau très super­fi­ciel tout le long de l'article. D'autres billets du genre plus tech­nique seront à venir, notam­ment sur la recherche d'informations dans des don­nées tex­tuelles !

Enjoy, et mer­ci aux relec­teurs : AnLe­bre­ton, Kum­qua­tum et Yoann M !

Ps : Je pro­fite éga­le­ment de ce sujet pour remer­cier hum­ble­ment Colin de la Higue­ra de m'avoir appris autant dans ses ensei­gne­ments sur le sujet.

Ps 2 : Je ne suis pas dans l'équipe dans le Fran­cois Coste ni dans ces col­la­bo­ra­teurs proches ou éloi­gnés. Toute publi­ci­té et enthou­siasme mar­qué pour ses recherches ne sont qu'une bien heu­reuse mal­adresse.

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