34
- Méthodes effectives de raisonnement (Beyond NP): De nombreuses méthodes de raisonnement (ont
leur problème de décision associé ayant une complexité algorithmique qui) se situent au premier niveau de la hiérarchie polynomiale ou au delà. Or les progrès réalisés ces dernières années dans les
solveurs SAT ou de contraintes, qui attaquent en pratique à présent des problèmes NP-complets de
taille importante, permettent à présent d’envisager de résoudre en pratique un certain nombre de ces
méthodes de raisonnement. Une initiative internationale autour de cette problématique (Beyond NP)
existe, et il semble important que la France y prenne sa part, car cela pourrait aboutir à l’application
pratique de ces méthodes de raisonnement.
Décision et gestion de l’incertitude
Dans les années 1970, avec les premiers travaux sur les systèmes experts, apparaît en intelligence artificielle (IA) le besoin de traiter l’incertitude, avec en particulier la nécessité de prendre en compte des
règles dont la conclusion n’est pas complètement certaine (les connaissances des experts ne sont pas
des théorèmes de mathématique). Les décennies suivantes voient le développement progressif de nouvelles modélisations de l’incertitude en IA, à côté des probabilités: ce sont les théories des possibilités,
des fonctions de croyance, et des probabilités imprécises, par ordre croissant de généralité et de pouvoir expressif (et ordre décroissant de simplicité de mise en œuvre). Les trois théories utilisent des
paires d’évaluations duales, nécessité / possibilité, croyance / plausibilité, probabililité inférieure /
probabilité supérieure. Ces nouveaux cadres théoriques sont principalement motivés par le besoin de
représenter des situations d’ignorance partielle, qui sont de nature épistémique (liées au manque
d’information précise) plutôt qu’à la variabilité des phénomènes considérés (que capture les probabilités).
A partir des années 1980, les probabilités ont pris une place prépondérante dans la représentation de
l’incertitude en IA, grâce à la masse des travaux existants sur le sujet et à l’introduction de modèles
graphiques, les réseaux bayésiens, permettant de schématiser la représentation et de propager localement l’incertitude.
Des contreparties de tels modèles graphiques existent maintenant pour les trois autres cadres théoriques de représentation de l’incertitude. Mentionnons aussi les graphes conceptuels pour la représentation graphique de fragments de la logique du premier ordre en relation avec la gestion des taxonomies. Les informations fournies par les sources sont souvent incomplètes et pas forcément totalement
fiables. Ceci pose la question de la synthèse et de la fusion de ces informations. Leur nature et leur
qualité hétérogènes peuvent requérir des cadres théoriques permettant la représentation d’incertitudes
à caractère épistémique. De même dans le raisonnement touchant au risque, il importe de bien distinguer entre incertitude épistémique et incertitude due à la variabilité. La décision (dans l’incertain, multicritère, ou de groupe) est devenue une problématique à part entière de l’IA seulement dans les années
1990. L’apport de l’IA sur ces questions est principalement marqué par un intérêt pour la représentation de préférences partielles et contextuelles, pour les modèles qualitatifs, ou pour une problématique
de calcul prenant en compte la taille éventuellement considérable de l’espace des choix. Diverses extensions, quantitatives ou qualitatives, de l’utilité espérée en (décision dans l’incertain) et de la
moyenne pondérée (en multicritère) ont été proposés et axiomatisés qui s’expriment en termes
d’intégrale de Choquet ou d’intégrale de Sugeno (qui permettent en particulier de prendre en compte
des dépendances entre critères). L’attitude du décideur, pessimiste ou optimiste, face à l’incomplétude
de l’information doit aussi être prise en compte. L’idée naturelle de décision à partir de cas observés a
été aussi formalisée (en termes de similarité entre cas) et justifiée. Les problèmes de décision séquentielle ont conduit l’IA à s’intéresser aux processus de décision markoviens, éventuellement partiellement observés, et à leur contrepartie qualitative.
De tout temps en IA, les cadres de représentation numériques (réseaux neuronaux, et réseaux
bayésiens, notamment) tournés vers l’efficacité calculatoire et l’apprentissage ont été opposés aux
cadres symboliques à base de logique et plus aptes à l’explication. Il est clair qu’un rapprochement et
un interfaçage entre les deux types de cadre est souhaitable et utile dans un certain nombre de pro-
- Méthodes effectives de raisonnement (Beyond NP): De nombreuses méthodes de raisonnement (ont
leur problème de décision associé ayant une complexité algorithmique qui) se situent au premier niveau de la hiérarchie polynomiale ou au delà. Or les progrès réalisés ces dernières années dans les
solveurs SAT ou de contraintes, qui attaquent en pratique à présent des problèmes NP-complets de
taille importante, permettent à présent d’envisager de résoudre en pratique un certain nombre de ces
méthodes de raisonnement. Une initiative internationale autour de cette problématique (Beyond NP)
existe, et il semble important que la France y prenne sa part, car cela pourrait aboutir à l’application
pratique de ces méthodes de raisonnement.
Décision et gestion de l’incertitude
Dans les années 1970, avec les premiers travaux sur les systèmes experts, apparaît en intelligence artificielle (IA) le besoin de traiter l’incertitude, avec en particulier la nécessité de prendre en compte des
règles dont la conclusion n’est pas complètement certaine (les connaissances des experts ne sont pas
des théorèmes de mathématique). Les décennies suivantes voient le développement progressif de nouvelles modélisations de l’incertitude en IA, à côté des probabilités: ce sont les théories des possibilités,
des fonctions de croyance, et des probabilités imprécises, par ordre croissant de généralité et de pouvoir expressif (et ordre décroissant de simplicité de mise en œuvre). Les trois théories utilisent des
paires d’évaluations duales, nécessité / possibilité, croyance / plausibilité, probabililité inférieure /
probabilité supérieure. Ces nouveaux cadres théoriques sont principalement motivés par le besoin de
représenter des situations d’ignorance partielle, qui sont de nature épistémique (liées au manque
d’information précise) plutôt qu’à la variabilité des phénomènes considérés (que capture les probabilités).
A partir des années 1980, les probabilités ont pris une place prépondérante dans la représentation de
l’incertitude en IA, grâce à la masse des travaux existants sur le sujet et à l’introduction de modèles
graphiques, les réseaux bayésiens, permettant de schématiser la représentation et de propager localement l’incertitude.
Des contreparties de tels modèles graphiques existent maintenant pour les trois autres cadres théoriques de représentation de l’incertitude. Mentionnons aussi les graphes conceptuels pour la représentation graphique de fragments de la logique du premier ordre en relation avec la gestion des taxonomies. Les informations fournies par les sources sont souvent incomplètes et pas forcément totalement
fiables. Ceci pose la question de la synthèse et de la fusion de ces informations. Leur nature et leur
qualité hétérogènes peuvent requérir des cadres théoriques permettant la représentation d’incertitudes
à caractère épistémique. De même dans le raisonnement touchant au risque, il importe de bien distinguer entre incertitude épistémique et incertitude due à la variabilité. La décision (dans l’incertain, multicritère, ou de groupe) est devenue une problématique à part entière de l’IA seulement dans les années
1990. L’apport de l’IA sur ces questions est principalement marqué par un intérêt pour la représentation de préférences partielles et contextuelles, pour les modèles qualitatifs, ou pour une problématique
de calcul prenant en compte la taille éventuellement considérable de l’espace des choix. Diverses extensions, quantitatives ou qualitatives, de l’utilité espérée en (décision dans l’incertain) et de la
moyenne pondérée (en multicritère) ont été proposés et axiomatisés qui s’expriment en termes
d’intégrale de Choquet ou d’intégrale de Sugeno (qui permettent en particulier de prendre en compte
des dépendances entre critères). L’attitude du décideur, pessimiste ou optimiste, face à l’incomplétude
de l’information doit aussi être prise en compte. L’idée naturelle de décision à partir de cas observés a
été aussi formalisée (en termes de similarité entre cas) et justifiée. Les problèmes de décision séquentielle ont conduit l’IA à s’intéresser aux processus de décision markoviens, éventuellement partiellement observés, et à leur contrepartie qualitative.
De tout temps en IA, les cadres de représentation numériques (réseaux neuronaux, et réseaux
bayésiens, notamment) tournés vers l’efficacité calculatoire et l’apprentissage ont été opposés aux
cadres symboliques à base de logique et plus aptes à l’explication. Il est clair qu’un rapprochement et
un interfaçage entre les deux types de cadre est souhaitable et utile dans un certain nombre de pro-