Section 06 Sciences de l'information : fondements de l'informatique, calculs, algorithmes, représentations, exploitations

IV. Données et connaissances – intelligence artificielle et interactions

L'intelligence artificielle a connu des évolutions remarquables ces dernières années. Les laboratoires français ont eu des contributions significatives dans les domaines de l'apprentissage, de la fouille de données et de la théorie de la décision.

A. Apprentissage

Le souci des applications, et en particulier l'exploitation des bases de données, a focalisé l'intérêt des chercheurs sur l'apprentissage de motifs ou de régularités au sein de données. Le but est de découvrir un modèle, celui-ci pouvant prendre la forme d'une théorie ou d'une distribution de probabilités par exemple. Or l'espace des fonctions des modèles est immensément vaste. Dès lors l'inférence d'un modèle particulier à partir de données disponibles pose la double question de l'exploration de cet espace et de l'estimation de la qualité des modèles envisageables par cette exploration. Il faut donc, d'une part, définir un critère inductif permettant de jauger les modèles en fonction des observations et de toute autre connaissance préalable, et d'autre part, trouver un moyen de guider une recherche dans l'espace des modèles. C'est ce double défi qui est au cœur de l'apprentissage et celui qui motive les algorithmes développés.

Un nombre croissant de champs d'applications (génomique, analyse de texte, recherche d'information sur le web, étude de réseaux sociaux...) soulèvent des problèmes qui ne s'inscrivent pas dans le cadre classique de l'apprentissage et nourrissent de nouvelles directions de recherche :

– Données non indépendantes et identiquement distribuées. L'apprentissage ne peut plus se faire en une fois, à partir d'une base fixée d'exemples. Il faut avoir recours à des algorithmes d'apprentissage en ligne dont la complexité devient alors un enjeu majeur.

– Données non vectorielles. Les données sont alors de formats différents ce qui pose des problèmes de comparaison et de définition de la notion de distance.

– Graph mining, c'est-à-dire l'exploitation de données relatives à des graphes. L'objectif peut être de caractériser les nœuds d'un graphe, ou de comparer des graphes. Dans tous les cas, de nouvelles techniques de comparaison de données aux hypothèses doivent être mises au point.

Une autre problématique vient de l'apprentissage en présence de grandes masses de données. Dans cette situation, le temps de calcul devient le principal facteur limitant les performances de l'apprentissage statistique. Cette considération est à contre-courant de la théorie de l'apprentissage statistique traditionnelle qui prend rarement en compte le coût des algorithmes d'apprentissage. Alors que les travaux de Vapnik ne s'y intéressent pas, ceux de Valiant n'autorisent que des algorithmes de coût polynomial. Les travaux fondateurs de Bottou (Microsoft Research, Redmond) et Bousquet (Google, Zurich) démontrent que ce changement d'échelle conduit vers un compromis qualitativement différent, et que par conséquent le meilleur algorithme d'optimisation n'est pas nécessairement le meilleur algorithme d'apprentissage. Par exemple, bien que la descente de gradient stochastique soit un algorithme d'optimisation médiocre, ils montrent, en théorie et aussi en pratique, que sa performance est excellente pour l'apprentissage à grande échelle. Du point de vue logiciel, on assiste à un important développement des systèmes de recommandation, comme ceux qui interviennent dans la gestion du contenu des pages web : le succès fulgurant de Criteo ou le système de recommandation utilisé par Amazon en sont des exemples frappants.

B. Masse de données et de connaissances

Avec l'avènement du Web sémantique et du Linked Open Data, les données et connaissances disponibles dans de nombreux domaines d'application (biologie, médecine, physique, journalisme, culture, loisir) et accessibles via Internet constituent un énorme gisement de connaissances à découvrir et à valoriser. La nécessité d'intégrer, de croiser, d'interroger à grande échelle des données distribuées et hétérogènes a mis en avant deux grandes thématiques à la croisée des bases de données et de la représentation de connaissances formalisées pour le raisonnement automatique.

La première concerne l'exploitation d'ontologies pour la structuration, l'intégration et l'interrogation de données à grande échelle. La communauté française a ici contribué activement au raisonnement à grande échelle sur des données incomplètes en présence d'ontologies. Cette problématique a forcé les chercheurs à concevoir des logiques de description d'ontologies ayant de bonnes propriétés en complexité des données, et à optimiser les algorithmes de raisonnement et d'interrogation des données en présence d'ontologies par des techniques de réécritures de requêtes. Ces travaux ont fortement influencé les recommandations récentes du W3C pour les langages standards du Web sémantique et ont permis une large adoption des principes du Linked data qui sont en train de révolutionner le Web, où fleurissent de façon décloisonnée données et ontologies interconnectées.

La deuxième se consacre à la fouille de données pour l'extraction automatique de connaissances. Ici aussi, la communauté française a obtenu plusieurs contributions significatives. Des progrès importants ont permis un meilleur passage à l'échelle d'algorithmes avancés en fouille de données pour l'extraction de motifs fréquents ou de règles d'association à partir de données massives de plus en plus complexes (séquences, arbres, graphes), à la fois par l'exploitation du parallélisme mais aussi par des structures de données et des techniques d'exploration efficace issues du rapprochement avec l'analyse formelle de concepts.

C. Théorie de la décision

La théorie mathématique de la décision individuelle modélise le comportement d'un agent face à des situations de choix. Jusqu'à récemment, les travaux portaient sur le développement de modèles axiomatiques dans la lignée des travaux de Savage. Étant donnés un ensemble de choix, une distribution de probabilités sur les états possibles et une fonction d'utilité, l'idée est de définir des axiomes qu'une règle de décision devrait satisfaire. Plus récemment, l'attention s'est tournée vers les questions algorithmiques de la décision. La communauté française a eu des contributions saillantes dans ce domaine et a créé l'International Conference on Algorithmic Decision Theory.

D'autre part, après le succès des systèmes multi-agents tant au niveau théorique qu'appliqué, nous assistons à l'émergence d'une nouvelle problématique, appelée choix social, où un groupe d'agents doit s'accorder de manière collective sur une décision commune selon une procédure centralisée. Les applications variées concernent aussi bien le vote, que le partage équitable de ressources, ou la recherche de consensus (agrégation de jugement). Dans les deux premiers cas, il s'agit d'agréger des préférences, alors que dans le troisième cas il s'agit d'agréger des croyances. À la croisée entre théorie du choix social et informatique se développe un nouveau domaine de recherche, le choix social computationnel, dont un des objectifs est d'importer des concepts et procédures de la théorie du choix social pour résoudre des problèmes issus de l'informatique (par exemple les procédures d'agrégation pour le classement de pages web et la recherche d'information, ou encore l'utilisation de procédures de vote pour la classification et la reconnaissance des formes), un autre but étant d'utiliser des notions et méthodes venant de l'informatique (langages de représentation, complexité, algorithmique, protocole d'interactions...) pour résoudre des problèmes de décision de groupe complexes.