AI-complet - AI-complete

Dans le domaine de l' intelligence artificielle , les problèmes les plus difficiles sont officieusement appelés AI-complet ou AI-hard , ce qui implique que la difficulté de ces problèmes de calcul, en supposant que l'intelligence est computationnelle, est équivalente à celle de la résolution du problème central de l'intelligence artificielle - faire des ordinateurs aussi intelligents que les gens, ou une IA puissante . Appeler un problème AI-complet reflète une attitude selon laquelle il ne serait pas résolu par un simple algorithme spécifique.

On suppose que les problèmes complets de l'IA incluent la vision par ordinateur , la compréhension du langage naturel et la gestion de circonstances inattendues tout en résolvant n'importe quel problème du monde réel.

Actuellement, les problèmes complets de l'IA ne peuvent pas être résolus uniquement avec la technologie informatique moderne, mais nécessiteraient également des calculs humains . Cette propriété pourrait être utile, par exemple, pour tester la présence d'humains comme les CAPTCHA visent à le faire, et pour que la sécurité informatique contourne les attaques par force brute .

Histoire

Le terme a été inventé par Fanya Montalvo par analogie avec NP-complet et NP-difficile dans la théorie de la complexité , qui décrit formellement la classe la plus célèbre de problèmes difficiles. Les premières utilisations du terme se trouvent dans la thèse de doctorat d'Erik Mueller en 1987 et dans le Jargon File d' Eric Raymond en 1991 .

Problèmes complets avec l'IA

Les problèmes complets de l'IA sont supposés inclure :

Traduction automatique

Pour traduire avec précision, une machine doit être capable de comprendre le texte. Il doit être capable de suivre l'argumentation de l'auteur, il doit donc avoir une certaine capacité à raisonner . Il doit avoir une connaissance approfondie du monde pour savoir de quoi il s'agit - il doit au moins être familier avec tous les mêmes faits de bon sens que le traducteur humain moyen connaît. Certaines de ces connaissances se présentent sous la forme de faits qui peuvent être explicitement représentés, mais certaines connaissances sont inconscientes et étroitement liées au corps humain : par exemple, la machine peut avoir besoin de comprendre comment un océan fait ressentir pour traduire avec précision une métaphore spécifique. dans le texte. Il doit également modéliser les objectifs, les intentions et les états émotionnels des auteurs pour les reproduire avec précision dans une nouvelle langue. En bref, la machine doit posséder une grande variété de compétences intellectuelles humaines, y compris la raison , les connaissances de bon sens et les intuitions qui sous-tendent le mouvement et la manipulation , la perception et l'intelligence sociale . On pense donc que la traduction automatique est une IA complète : elle peut nécessiter une IA puissante pour être réalisée aussi bien que les humains peuvent le faire.

Fragilité du logiciel

Les systèmes d'IA actuels peuvent résoudre des versions très simples et/ou restreintes de problèmes complets d'IA, mais jamais dans leur pleine généralité. Lorsque les chercheurs en IA tentent de « faire évoluer » leurs systèmes pour gérer des situations réelles plus complexes, les programmes ont tendance à devenir excessivement fragiles sans une connaissance de bon sens ou une compréhension rudimentaire de la situation : ils échouent en tant que circonstances inattendues en dehors de son contexte de problème d'origine. commencent à apparaître. Lorsque les êtres humains sont confrontés à de nouvelles situations dans le monde, ils sont énormément aidés par le fait qu'ils savent à quoi s'attendre : ils savent ce que sont toutes les choses qui les entourent, pourquoi elles sont là, ce qu'elles sont susceptibles de faire, etc. Ils peuvent reconnaître des situations inhabituelles et s'adapter en conséquence. Une machine sans IA puissante n'a pas d'autres compétences sur lesquelles se rabattre.

Formalisation

La théorie de la complexité computationnelle traite de la difficulté de calcul relative des fonctions calculables . Par définition, il ne couvre pas les problèmes dont la solution est inconnue ou n'a pas été caractérisée formellement. Étant donné que de nombreux problèmes d'IA n'ont pas encore de formalisation, la théorie de la complexité conventionnelle ne permet pas de définir la complétude de l'IA.

Pour résoudre ce problème, une théorie de la complexité pour l'IA a été proposée. Il est basé sur un modèle de calcul qui répartit la charge de calcul entre un ordinateur et un humain : une partie est résolue par ordinateur et l'autre par un humain. Ceci est formalisé par une machine de Turing à assistance humaine . La formalisation définit la complexité de l'algorithme, la complexité du problème et la réductibilité, ce qui permet à son tour de définir des classes d'équivalence .

La complexité de l'exécution d'un algorithme avec une machine de Turing assistée par l'homme est donnée par une paire , où le premier élément représente la complexité de la partie humaine et le second élément est la complexité de la partie machine.

Résultats

La complexité de la résolution des problèmes suivants avec une machine de Turing à assistance humaine est :

  • Reconnaissance optique de caractères pour le texte imprimé :
  • Essai de Turing :
    • pour une conversation -phrase où l'oracle se souvient de l'historique de la conversation (oracle persistant) :
    • pour une conversation en -phrase où l'historique de la conversation doit être retransmis :
    • pour une conversation -phrase où l'historique de la conversation doit être retransmis et la personne prend un temps linéaire pour lire la requête :
  • Jeu ESP :
  • Étiquetage des images (basé sur le protocole Arthur-Merlin ) :
  • Classification de l'image : humain uniquement : , et avec moins de dépendance à l'humain : .

Voir également

Les références

  1. ^ Shapiro, Stuart C. (1992). Intelligence artificielle Dans Stuart C. Shapiro (éd.), Encyclopedia of Artificial Intelligence (deuxième édition, pp. 54-57). New York : John Wiley. (La section 4 est sur les « Tâches complètes de l'IA ».)
  2. ^ Roman V. Yampolskiy. Le test de Turing en tant que caractéristique déterminante de l'exhaustivité de l'IA. En intelligence artificielle, calcul évolutif et métaheuristique (AIECM) --Sur les traces d'Alan Turing. Xin-She Yang (éd.). p. 3-17. (Chapitre 1). Springer, Londres. 2013. http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf
  3. ^ Luis von Ahn, Manuel Blum, Nicholas Hopper et John Langford. CAPTCHA : Utilisation de problèmes d'IA difficiles pour la sécurité Archivé le 04/03/2016 sur la Wayback Machine . Dans Actes d'Eurocrypt, Vol. 2656 (2003), p. 294-311.
  4. ^ Bergmair, Richard (7 janvier 2006). "Stéganographie en langage naturel et primitive de sécurité "IA-complète"". CiteSeerX  10.1.1.105.129 . Citer le journal nécessite |journal=( aide ) (inédit ?)
  5. ^ Mallery, John C. (1988), "Penser à la politique étrangère: Trouver un rôle approprié pour les ordinateurs artificiellement intelligents", La réunion annuelle de 1988 de l'International Studies Association. , Saint-Louis, Missouri.
  6. ^ Mueller, Erik T. (1987, mars). Daydreaming and Computation (Technical Report CSD-870017) Thèse de doctorat, Université de Californie, Los Angeles. ("La rêverie n'est qu'un autreproblème d' IA complet : si nous pouvions résoudre n'importe quel problème d'intelligence artificielle, nous pourrions résoudre tous les autres", p. 302)
  7. ^ Raymond, Eric S. (1991, 22 mars). Jargon File Version 2.8.1 (La définition de "AI-complete" a d'abord été ajoutée au fichier de jargon.)
  8. ^ Ide, N.; Véronis, J. (1998). « Introduction au numéro spécial sur la désambiguïsation du sens des mots : l'état de l'art » (PDF) . Linguistique computationnelle . 24 (1) : 2–40.
  9. ^ Lénat, Douglas ; Guha, RV (1989), Building Large Knowledge-Based Systems , Addison-Wesley, pp. 1-5
  10. ^ un b Dafna Shahaf et Eyal Amir (2007) Vers une théorie de l'exhaustivité de l'IA . Commonsense 2007, 8e Symposium international sur les formalisations logiques du raisonnement de sens commun .