Intelligence artificielle

au-delà des systèmes experts
INTRODUCTION
Doter une machine d'intelligence, c'est une idée qui fascine l'humanité depuis longtemps. En permettant des réalisations concrètes, l'informatique a précisé le concept de l'intelligence, qui est assez flou dans l'esprit de la plupart des gens.
Pour certains, les ordinateurs sont des «cerveaux électroniques» qui sont sans doute intelligents. N'est-ce pas vrai que des ordinateurs savent gérer nos comptes bancaires, ou encore calculer nos impôts, choses que même les plus intelligents d'entre nous n'arrivent que rarement à faire correctement?
Pour d'autres, l'intelligence se définit précisément par ce que la machine ne peut pas faire. A l'époque où jouer aux échecs était trop complexe pour une machine, c'était encore un jeu qui demandait de l'intelligence. Mais aujourd'hui, où n'importe quel petit ordinateur peut nous battre? Ce n'est plus le fait de jouer aux échecs qui est difficile, mais peut-être la reconnaissance d'un visage, chose que l'ordinateur ne sait pas encore faire...
Les chercheurs en Intelligence Artificielle se trouvent alors constamment confrontés au dilemme qu'on attend de leurs programmes de faire ce que l'ordinateur ne savait pas encore faire. Par exemple, dans les années 80, on attendait de l'IA la capacité de fournir des programmes traitant de domaines où les connaissances étaient peu structurées. Ces systèmes à base de connaissances devaient avoir les caractéristiques suivantes:
la séparation entre les connaissances déclaratives et la procédure d'inférence permettant de réutiliser les mêmes connaissances pour des tâches différentes;
comme la procédure d'inférence reste fixe, la construction d'un outil informatique se réduit à la formalisation des connaissances et serait donc très simplifiée;
la mise à jour d'un système existant serait de ce fait également facilitée de beaucoup;
les connaissances pourraient parfois avoir un caractère flou et heuristique;
le système pourrait profiter de techniques d'apprentissage pour améliorer ses performances.
Les outils qui étaient proposés à l'époque -des systèmes experts composés de règles si... alors- n'étaient pas toujours capables de satisfaire à toutes ces attentes. D'un côté, une règle si-alors contient en elle une forte composante procédurale, et ne satisfait pas à l'idée d'une séparation entre connaissances déclaratives et procédurales. D'un autre côté, les formalismes pour la construction des règles n'étaient pas assez restreints pour permettre un apprentissage avec un nombre important de données. Parmi les objectifs, seul celui de l'inférence floue a vraiment pu être atteint; il trouve son application aujourd'hui dans de nombreuses applications d'aide à la décision (systèmes experts) ou même de réglage automatique (contrôle flou).

La technologie des systèmes experts à base de règles a maintenant 20 ans. Entre-temps, les chercheurs en Intelligence Artificielle ont mis au point des technologies qui aujourd'hui sont enfin capables de remplir la plupart des désirs de jadis. Citons par exemple:

le raisonnement fondé sur les modèles, en s'appuyant sur une formulation sous-jacente des connaissances sous forme de contraintes, permet une séparation plus nette entre la procédure d'inférence et les connaissances mêmes. Les modèles peuvent être utilisés à des buts variés et sont souvent faciles à mettre à jour;
des abstractions permettent de limiter la complexité d'un problème combinatoire;
le raisonnement fondé sur les cas permet de traiter des problèmes peu formalisés. Il permet également d'apprendre de nouvelles connaissances et d'améliorer les performances avec l'expérience.
Les logiciels fondés sur ces techniques connaissent un grand succès dans les applications. L'importance du marché industriel, ainsi que le volume de recherches dans ce domaine est toujours en croissance continue. Dans cet article, nous allons examiner quelques principes essentiels de ces techniques.

LE RAISONNEMENT FONDÉ SUR MODELES
La séparation entre les connaissances déclaratives sous forme de règles d'une part, et les connaissances procédurales implicites dans un moteur d'inférence général d'autre part, est à la base de la programmation par règles logiques. Elle provient des travaux de Newell & Simon sur le General Problem Solver, travaux qui proposaient le chaînage de règles comme modèle général de tout raisonnement humain. On peut remarquer déjà que cette méthode, illustrée à gauche de la figure 1, ne laisse aucune place pour formuler la stratégie à employer pour effectuer certaines tâches, si ce n'est de manière implicite dans les règles. Or, pour faire face à la complexité d'une application pratique, il est indispensable de fixer certaines stratégies. Un ensemble de règles implique donc une forte composante de connaissances stratégiques qui restent implicites. Le raisonnement fondé sur modèle, illustré à droite de la figure 1, remplace le seul et unique moteur d'inférence par des procédures spécialisées qui englobent les stratégies utiles pour les diverses tâches de raisonnement, par exemple:


Figure 1: Le raisonnement fondé sur des règles utilise un seul moteur d'inférence qui est capable de traiter des règles logiques (à gauche). Le raisonnement fondé sur des modèles, par contre, utilise plusieurs moteurs adaptés à différentes tâches, mais capables de traiter un seul modèle commun (à droite).


le diagnostic, dont le but est de trouver les composantes défectueuses qui sont à l'origine d'un dysfonctionnement,
le monitoring, dont le but est de décider si une dysfonction a eu lieu,
la configuration et la conception, où il faut proposer un ensemble consistant de composantes et connexions qui remplissent un certain ensemble de fonctions.
Lors d'une application concrète, ces moteurs peuvent alors utiliser des connaissances sous forme d'un modèle qui est déclaratif et utilisable en même temps par différents processus.
Dans les sciences, un modèle est normalement exprimé sous forme d'un ensemble d'équations. Dans la programmation classique, ces équations sont d'abord transformées en formules de calcul qui peuvent être exécutées par un ordinateur. Il existe des nombreuses manières de transformer un modèle en algorithme, et chaque algorithme ainsi obtenu contient donc une forte composante procédurale qui dépend du calcul à effectuer: le programme qui calcule x à partir de y sera différent de celui qui calcule y à partir de x.

Des tâches complexes comme le diagnostic ou la configuration ont par contre besoin d'utiliser les modèles dans toutes les directions, suivant le cas concret. On utilise alors des moteurs de satisfaction de contraintes pour identifier les solutions admises par un système de contraintes. Une contrainte peut être n'importe quelle relation qui limite les combinaisons admissibles de valeurs d'un ensemble de variables. Les tâches génériques peuvent alors toutes être effectuées par des algorithmes simples qui se basent sur un moteur de satisfaction de contraintes, par exemple:

diagnostic: quelles combinaisons de contraintes sont inconsistantes avec le comportement observé? Comme chaque contrainte est liée à une composante, ceci donne directement un diagnostic.
monitoring: est-ce que le comportement observé satisfait à toutes les contraintes du modèle?
configuration: quel ensemble de composantes et de valeurs de paramètres satisfait aux contraintes posées par un ensemble de fonctions données?
Les mêmes connaissances peuvent donc être utilisées pour de nombreuses tâches très variées. Le logiciel qui sert au diagnostic, monitoring, configuration ou encore autre tâche, peut être préfabriqué, et seul le modèle reste à coder pour une application spécifique. En plus, pour des objets artificiels conçus à l'aide d'un système de CAO intelligent, les modèles nécessaires peuvent être fournis automatiquement sur la base du modèle construit par le système CAO. On pourra donc générer des moteurs de diagnostic ou de configuration automatiquement pour tout nouveau produit conçu. La société japonaise MITA va prochainement commercialiser une photocopieuse capable de corriger certaines pannes de manière autonome en utilisant un système de raisonnement fondé sur modèles.

La formulation des connaissances sous forme de contraintes a aussi l'avantage de permettre la formulation de modèles incomplets et qualitatifs. Ceci peut intervenir à plusieurs niveaux:

les équations peuvent être en nombre insuffisant pour déterminer des solutions précises.
certaines contraintes peuvent être des inégalités qui donnent uniquement les limites d'un espace de solutions.
des contraintes peuvent être formulées sur des domaines discrets et spécifiées en fixant des ensembles de valeurs compatibles.
Les deux dernières possibilités sont requises pour la formulation de modèles qualitatifs, importants notamment dans la configuration et conception. Le raisonnement à base de modèles se réduit ainsi à la résolution de problèmes de satisfaction de contraintes. De nombreuses techniques ont été développées au cours des dernières années pour traiter ce problème. En général, un problème de satisfaction de contraintes peut être résolu par une recherche parmi les combinaisons de valeurs imaginables, mais ceci impliquerait une complexité exponentielle. Des techniques de consistance permettent de réduire l'ensemble des combinaisons à considérer en utilisant des algorithmes simples et efficaces qui appliquent des critères locaux. Des techniques de consistance ont été formulées pour de nombreux domaines, et dans beaucoup de cas permettent de réduire de manière importante le temps requis pour la recherche qui suit, voire éviter la recherche complètement. Dans le contexte de la programmation logique par contraintes, exemplifié par les langages CLP() ou CHIP [1], on utilise des techniques de programmation linéaire, provenant de la recherche opérationnelle. Une technologie spécifique a été développée pour appliquer ces techniques également à la solution de problèmes à variables discrètes.
Le laboratoire d'Intelligence Artificielle de l'EPFL a contribué à la technologie notamment dans le domaine de la modélisation qualitative de l'espace ainsi que dans les méthodes de consistance pour des contraintes à domaines continus. Le LIA a utilisé ces techniques dans plusieurs applications modèles pour la conception et le diagnostic.

LES ABSTRACTIONS
La plupart des problèmes complexes ont une nature combinatoire. Les algorithmes exacts pour leur solution ont souvent une complexité exponentielle, et les approximations sont très coûteuses à calculer. Or, les applications pratiques comportent souvent un grand nombre d'éléments et conduisent ainsi à des temps de calcul trop élevés.
Une solution pour échapper à cette complexité est de formuler le problème à un niveau d'abstraction plus élevé. Comme le montre la figure 2, en choisissant le bon niveau d'abstraction, un problème peut être ramené à n'importe quelle complexité voulue, le prix à payer étant que le problème abstrait ne donnera pas accès à toutes les solutions du problème original. Ce problème peut être résolu en partie en choisissant des abstractions plus fines aux endroits où cela rapporte le plus. Une théorie ainsi qu'un survol des travaux utilisant des abstractions se trouvent dans [2].


Figure 2: Les abstractions permettent de limiter la complexité d'un raisonnement en réduisant le nombre d'éléments qui entrent dans la combinatoire. Chaque abstraction regroupe un certain nombre d'objets en un seul. Une formulation à la complexité voulue peut être obtenue en utilisant des objets appartenant aux niveaux d'abstraction appropriés.

Comme exemple d'utilisation des abstractions, considérons la tâche du diagnostic. En général, la recherche d'un diagnostic est un problème de complexité exponentielle dans le nombre de composantes. Des abstractions peuvent être introduites en regroupant certaines composantes ensemble dans des composantes plus complexes (figure 3). Une fois que le système aura identifié la composante défectueuse à ce niveau abstrait, il pourra remplacer uniquement cette composante par des abstractions plus fines. Même si la procédure de diagnostic est de complexité exponentielle, elle pourra ainsi traiter la plupart des cas dans un temps à peu proportionnel au nombre de composantes. Cette stratégie a été appliquée par exemple dans un système de diagnostic d'un réseau électrique au Nord de l'Italie.



Figure 3: Le diagnostic d 'un système à nombreuses composantes est moins complexe si l'on considère d'abord un système abstrait construit en regroupant des composantes. Une fois que la composante abstraite (en gris) est identifiée, on revient aux détails.

Une technique qui construit des abstractions dynamiques dans le domaine de l'allocation de ressources a été mise au point au LIA de l'EPFL. Il s'agit d'assigner un certain ensemble de ressources à des tâches fixes dans le temps de manière à ce qu'aucune ressource ne doive effectuer plusieurs tâches en même temps. Les abstractions construites sont des regroupements de tâches et de ressources équivalentes qui peuvent être identifiées dans un problème donné. Dans la pratique, ces abstractions réduisent souvent la complexité d'un problème au point où il peut être résolu par l'utilisateur même. En ce moment, nous sommes en train d'appliquer la méthode à l'affectation des avions de la compagnie Swissair.

LE RAISONNEMENT FONDÉ SUR LES CAS
Il est évident que le raisonnement s'applique uniquement là où on connaît des modèles, ou au moins des fragments de modèles. Dans des applications où cela n'est pas le cas, il faudra toujours avoir recours à des heuristiques. Ces heuristiques résument le savoir d'un expert acquise lors de nombreuses expériences.
La question se pose cependant si de telles heuristiques existent vraiment ou si elles ne sont pas plutôt un résultat de la pression à formaliser les connaissances sous cette forme. Dans des domaines complexes, il est douteux que des décisions puissent être prises en tenant compte uniquement d'une petite quantité d'informations. Cependant, ceci est exactement ce que demande une règle heuristique, dont les conditions sont très simples et ne peuvent nullement représenter toute la complexité du problème.
Une autre théorie de la mémoire et du raisonnement humain dit que toute conclusion se base directement sur des analogies avec des expériences précédentes et précises. L'idée du raisonnement à base de cas, illustrée par la figure 4, est qu'au lieu de généraliser les expériences sous forme d'heuristiques générales, cette généralisation se fait uniquement au moment où un problème concret doit être résolu. Elle revient alors à la construction d'analogies entre des expériences précédentes et le problème actuel. L'avantage évident est que les cas sont capables de tenir compte d'un contexte beaucoup plus large que les règles heuristiques.


Figure 4: Dans le raisonnement heuristique, on suppose que les expériences sont généralisées au moment où elles surviennent et mémorisées sous forme d 'heuristiques généralisées. Dans le raisonnement à base de cas, la généralisation des expériences précédentes ne se fait qu'au moment où un problème doit être résolu.

Le raisonnement à base de cas est utilisé formellement dans le domaine du droit, où des argumentations basées sur des décisions précédentes jouent souvent un rôle plus important que les règles formalisées par la loi. Il est également souvent invoqué dans les affaires, où il existe même des écoles qui remplacent l'enseignement de toute règle heuristique par la seule étude de cas. Dans le domaine technique, son usage est jusqu'ici moins explicite, même si des concepteurs font souvent recours à des cas précédents.
Un moteur de raisonnement à base de cas comporte deux composantes importantes: I'indexation, qui sert à trouver les cas à prendre en compte pour le problème actuel, et l'adaptation, qui sert à modifier un ou plusieurs cas pour les rendre applicables au problème actuel.
Diverses méthodes ont été proposées pour l'indexation. Les plus simples d'entre elles définissent une métrique fixe de similarités entre cas, et choisissent les cas qui sont les plus proches du problème courant suivant cette métrique. La grande difficulté de l'indexation est cependant que ce n'est pas la similitude des problèmes qui est importante, mais l'adaptabilité de la solution au problème courant. Pour cette raison, des méthodes plus poussées d'indexation se basent sur une métrique qui essaye de capturer la facilité d'adapter la solution du cas au problème courant.
Dans certaines applications, l'adaptation d'un cas ne doit pas forcement être automatique. Par exemple, il existe des systèmes d'EAO où les cas proposent des solutions qui sont expliquées à l'aide de séquences vidéos. En général, l'adaptation doit se baser sur des connaissances généralement valables, c'est-à-dire un modèle du domaine, pour assurer que le résultat de la modification reste toujours valable. Cependant, et c'est là le grand avantage, ce modèle peut être très incomplet.
Le raisonnement fondé sur les cas a un désavantage important, celui d'être très gourmand en ressources informatiques. Stoker et indexer selon des critères complexes une base de 10'000 cas, de quelque KBytes chacun, n'est devenu possible que très récemment. Les exemples d'applications du raisonnement à base de cas sont néanmoins déjà nombreux. Des chercheurs chez Lockheed ont développé un système pour optimiser la configuration du chargement des fours autoclaves qui est utilisé en pratique depuis sa conception en 1989. D'autres applications dans le diagnostic et la planification ont suivi. En EAO, une grande équipe du ILS (Institute for the Learning Sciences) à Chicago a construit de nombreux systèmes d'EAO à base de cas, notamment pour le compte de la société Arthur Andersen.
A l'EPFL, le Laboratoire d'Intelligence Artificielle a contribué à la technologie en développant des techniques de raisonnement à base de modèles pour l'adaptation de cas. Ces techniques ont été étudiées notamment sur l'exemple de la conception de bâtiments et de mécanismes. Dans ces domaines, les chercheurs ont démontré comment la méthode de re-interprétation permet d'utiliser des cas pour arriver à des solutions innovatrices.
Une autre application, mise au point en collaboration avec Nestlé, concerne la modélisation de processus. Certains types de machines de torréfaction sont très difficiles à modéliser quantitativement, et leur contrôle pose donc des problèmes importants. Un système à base de cas est capable de modéliser le comportement du processus en utilisant une base de cas précédents et un modèle partiel et qualitatif du processus. Les cas comprennent une centaine de mesures de paramètres critiques à deux instants successifs. Chaque cas permettrait donc de prédire les mesures suivantes pour une situation où les mesures actuelles correspondent à celles du cas présent. Le modèle permet de sélectionner et combiner un certain nombre de cas en se basant sur divers principes selon la sélection de l'utilisateur. Un exemple est le principe suivant: si une variable x est en croissance monotone avec y, et x problème < X cas alors y problème < x cas car autrement la relation monotone serait violée. Utilisant un certain nombre de relations monotones, on peut alors utiliser les cas pour déterminer des intervalles pendant lesquels les valeurs recherchées doivent tomber. Le prototype du LIA est actuellement en phase d'évaluation par les opérateurs d'une usine de torréfaction a Hayes (Angleterre). Cette application met bien en évidence les avantages du raisonnement à base de cas: l'usine de torréfaction est beaucoup trop complexe pour que son comportement puisse être résumé par quelques heuristiques (ou des réseaux de neurones, autre technologie essayée en vain par les chercheurs). La base des cas met à disposition la mémoire nécessaire pour modéliser correctement tous les aspects du comportement de l'usine. La solution a notamment l'avantage de n'exiger aucune modélisation détaillée par un expert, ce qui serait trop coûteux en pratique.
Pour ceux qui veulent profiter de la technologie tout de suite, sachez qu'un collaborateur du LIA a mis au point un moteur simple de diagnostic à base de cas qui sera prochainement commercialisé par la société ISE Software. Il existe d'autres outils commerciaux, ainsi qu'un livre introduisant le sujet [3].

CONCLUSIONS
La vie moderne comporte de plus en plus de processus artificiels. L'intelligence naturelle de l'humain, bien adaptée pour des tâches comme la reconnaissance d'un visage, doit être complétée par une intelligence artificielle mieux adaptée à la résolution de problèmes complexes. Même si les yeux du grand public se sont tournés vers d'autres domaines, plus spectaculaires, la recherche en Intelligence Artificielle a fait des progrès très importants vers ce but ces dernières années. Les nouvelles techniques, notamment le raisonnement fondé sur des modèles ou des cas, la satisfaction de contraintes et les abstractions, permettent maintenant de satisfaire une grande part des promesses qui ont été faites il y a 10 ans. Le temps est venu maintenant de les appliquer à des problèmes pratiques.