Intelligence artificielle
Le champ dans toute son étendue : des agents qui perçoivent, raisonnent et agissent. Recherche, connaissance, planification et apprentissage, et la question de ce qui compte comme comportement intelligent.
Parcours (11)
Recherche en IA et théorie des jeux
Décider quoi faire quand un autre agent décide aussi : jeu optimal contre un adversaire, élagage de la recherche, et équilibre lorsque les intérêts ne divergent qu'en partie.
Apprentissage par renforcement
Bien agir quand les issues sont incertaines : l'equation de Bellman et comment la resoudre, puis ce qui change lorsque l'environnement est inconnu et que l'agent doit apprendre par la seule experience.
Logique et représentation des connaissances
L’autre tradition de l’intelligence artificielle : représenter ce qu’un système sait par des phrases vraies ou fausses, et en dériver ce qui doit suivre - avec des garanties qu’un modèle appris ne peut pas offrir.
Recherche et heuristiques
La plus ancienne idée qui fonctionne en intelligence artificielle : décrire un problème par des états et des actions, puis laisser une exploration systématique trouver le chemin. La stratégie retenue décide si la réponse est optimale, et si la mémoire s’épuise avant qu’elle n’arrive.
Raisonnement probabiliste avec les réseaux bayésiens
Représenter une loi jointe sur de nombreuses variables par un graphe et une poignée de petites tables, puis y répondre aux requêtes exactement quand la structure le permet et par échantillonnage quand elle ne le permet pas.
Raisonnement probabiliste dans le temps
Suivre un monde qui change pendant que vous l'observez à travers un capteur bruité : les deux hypothèses qui rendent le problème traitable, les récursions progressive et rétrograde qui répondent à toute requête sur le passé et le présent, et l'algorithme distinct qu'exige l'histoire la plus probable.
Satisfaction de contraintes
Décrivez un problème par des variables, des domaines et des contraintes, et un solveur générique pourra l’attaquer sans savoir de quoi il parle - à condition de le laisser raisonner sur les contraintes au lieu de seulement deviner des valeurs.
Décider dans l’incertitude
Combinez ce que vous croyez et ce que vous voulez : l’utilité espérée comme critère, la courbe qui explique pourquoi des gens sensés refusent des paris favorables, et un prix de l’information qui reste nul tant qu’elle ne vous fait pas changer d’avis.
Planification classique
Décrivez les actions par ce qu’elles changent et un solveur peut lire la description elle-même : les schémas qui définissent le problème engendrent aussi les heuristiques qui le résolvent, ce qu’aucune recherche en boîte noire ne sait offrir.
Apprendre des modèles probabilistes
Quand les données sont complètes, apprendre un modèle probabiliste revient à compter - la dérivée de la log-vraisemblance fait le reste. Quand des variables sont cachées, il n’y a rien à compter, et le remède consiste à deviner les effectifs, réajuster, et recommencer jusqu’à ce que la vraisemblance cesse de monter.
Décider sous observabilité partielle
Un agent qui ne voit pas dans quel état il se trouve doit agir sur une distribution à la place. Cette distribution est, elle, toujours observable, ce qui ramène le problème à un MDP - sur un espace continu, où les algorithmes exacts ne se referment pas.
Encyclopédie (21)
Réseau bayésien
Un graphe orienté acyclique dont les nœuds sont des variables aléatoires et dont les arêtes expriment une influence directe, avec une table de probabilités conditionnelles à chaque nœud, qui définissent ensemble une loi jointe complète comme un produit de facteurs locaux.
Arbre de décision
Un modèle qui prédit en appliquant une suite de tests à seuil sur des variables isolées, divisant les données en groupes de plus en plus homogènes.
Modèle de Markov caché
Un modèle temporel dans lequel une unique variable d’état discrète évolue comme une chaîne de Markov et émet une observation par pas de temps, si bien que l’état doit être inféré à partir d’un indicateur bruité plutôt qu’observé directement.
Espérance–Maximisation
Une méthode itérative d’estimation par maximum de vraisemblance lorsque certaines variables ne sont pas observées : elle calcule la loi a posteriori des variables cachées sous les paramètres courants, puis réajuste les paramètres comme si ces effectifs espérés avaient été observés.
État de croyance
La loi de probabilité qu’un agent entretient sur les états où il pourrait se trouver, compte tenu de tout ce qu’il a fait et perçu - ce sur quoi il peut agir quand l’état lui-même est caché.
MDP partiellement observable
Un processus de décision markovien dans lequel l’agent ne peut pas observer son état directement, mais seulement des perceptions bruitées de celui-ci - résolu en principe en traitant la distribution sur les états comme l’état d’un MDP ordinaire, totalement observable.
Réseau de neurones
Un modèle composé de couches d’unités simples, chacune calculant une somme pondérée suivie d’une fonction non linéaire, ajusté par descente de gradient au moyen de la rétropropagation.
Problème de satisfaction de contraintes
Un problème énoncé comme un ensemble de variables, un domaine de valeurs permises pour chacune, et des contraintes restreignant les combinaisons de valeurs qui peuvent être prises simultanément, de sorte qu’un solveur générique puisse raisonner sur sa structure sans aucune connaissance du domaine.
Processus de décision markovien
Un modèle formel de prise de décision séquentielle dont les issues sont en partie aléatoires, défini par des états, des actions, des probabilités de transition et des récompenses.
Recherche A*
Une recherche en graphe du meilleur d’abord qui développe le nœud minimisant la somme du coût déjà engagé et d’une estimation du coût restant.
Utilité espérée
La moyenne des utilités des issues possibles d’une action, pondérée par leurs probabilités, et la quantité qu’un agent rationnel maximise lorsqu’il choisit quoi faire dans l’incertitude.
Planification automatique
Trouver une suite d’actions qui atteint un but, où les états sont des ensembles de fluents instanciés et les actions des schémas ne décrivant que ce qu’elles changent.
Graphe de planification
Une structure en couches alternant niveaux de littéraux et niveaux d’actions, annotée de liens d’exclusion mutuelle, qui borne en temps polynomial ce qu’un problème de planification peut atteindre à une étape donnée.
Logique du premier ordre
Un langage formel pour représenter la connaissance en termes d’objets, de leurs propriétés et relations, et de quantification sur ceux-ci.
Minimax
Une règle de décision pour les jeux à somme nulle à deux joueurs, où chacun choisit le coup qui maximise son pire résultat face à une opposition optimale.
Filtre de Kalman
L’algorithme de filtrage exact pour un état continu qui évolue linéairement avec un bruit gaussien et qui est mesuré linéairement avec un bruit gaussien, la croyance entière tenant dans une moyenne et une variance.
Algorithme de Viterbi
Un algorithme de programmation dynamique qui trouve l’unique séquence d’états cachés la plus probable étant donné une séquence d’observations, en propageant le meilleur chemin vers chaque état plutôt que la probabilité totale de l’atteindre.
Softmax
Une fonction qui transforme un vecteur de scores réels en distribution de probabilité en exponentiant chaque score et en divisant par le total, ce qui préserve leur ordre tout en les rendant positifs et de somme un.
Perplexité
L’exponentielle de l’entropie croisée moyenne d’un modèle, lue comme le nombre d’options équiprobables entre lesquelles il choisit effectivement à chaque pas.
Équation de Bellman
La condition de cohérence selon laquelle l’utilité d’un état égale sa récompense immédiate plus la valeur actualisée de la meilleure action disponible, moyennée sur les issues que cette action ne contrôle pas.
Cohérence d’arc
Une propriété d’un problème de contraintes où chaque valeur de chaque domaine possède au moins une valeur de soutien dans chaque domaine voisin, et l’algorithme qui l’impose en supprimant celles qui n’en ont pas.
Articles (20)
La semaine qui n’a pas pu avoir lieu
Prenez l’état le plus probable chaque jour, écrivez-les dans l’ordre, et vous obtenez un rapport auquel le modèle attribue une probabilité exactement nulle : sur un exemple de surveillance de machine sur quatre jours, la réponse jour par jour est sain, sain, en panne, en panne, et passer de sain à en panne est une transition impossible. Ce que sont réellement les deux questions, pourquoi le lissage et Viterbi n’y répondent pas de la même manière, et ce que signifie la probabilité a posteriori de 0,411 du meilleur chemin pour qui doit décider.
Le paramètre que personne ne choisit
La récompense de survie d’un monde en grille est écrite une fois et jamais discutée, et la politique optimale en est une fonction en escalier : huit seuils entre -3 et 0, chacun retournant exactement une case. La valeur classique de -0,04 se trouve à 0,0048 de celle qui décide si l’agent prend le raccourci le long du puits, et au-dessus de -0,0221, quand les pas ne coûtent presque rien, le mouvement optimal dans un coin consiste à foncer volontairement dans un mur.
Le correctif qui a changé le taux de succès bien plus que le coût
Autoriser les déplacements latéraux fait passer l’escalade sur les 8 reines de 14,75 % de parties résolues à 94,55 %, ce qui se lit comme une amélioration d’un facteur six et n’en est pas une : avec redémarrages aléatoires, le coût attendu d’une solution passe de 21,9 à 23,1 pas, et, compté en coups évalués, il baisse de 16 %, de 1 547 à 1 298. Le recuit simulé résout 98,8 % et coûte 1 622 évaluations. Ce qui a changé, c’est surtout la statistique, pas le travail.
Un million de clauses, ou soixante et une
Convertir une formule courte en forme normale conjonctive par distribution donne 1 048 576 clauses et 20 971 520 littéraux ; nommer les sous-formules en donne 61 et 160, soit un facteur 131 072 sur les littéraux, et ne perd rien du tout : les deux ont le même nombre de modèles, vérifié par énumération. C’est le codage, et non le solveur, qui décide du sort d’un problème de satisfiabilité.
Cent mille échantillons, quatre cents qui comptent
Sur le réseau du cambriolage avec les deux voisins qui appellent, l’échantillonnage par rejet garde 183 tirages sur 100 000 et la pondération par vraisemblance les garde tous pour une taille d’échantillon efficace de 396. Les deux estimations s’écartent d’environ 10 % d’une probabilité a posteriori de 0,284172, et la raison se calcule exactement : 252 échantillons portent 76 % du poids et 99,975 % du poids au carré.
Apprendre les nombres d’un modèle probabiliste
D’où viennent réellement les nombres d’un réseau bayésien ou d’une gaussienne : la recette en trois temps du maximum de vraisemblance déroulée sur des paramètres discrets puis continus, l’a priori Beta qui répare ce qu’elle fait d’un événement jamais vu, Bayes naïf et l’unique effectif nul qui le détruit, et l’algorithme EM pour le cas où les effectifs ne peuvent pas être relevés du tout - chaque chiffre calculé plutôt qu’affirmé.
Agir quand on ne voit pas l’état
Ce qui change quand un agent reçoit des perceptions bruitées au lieu de son état : l’état de croyance qui le remplace et la mise à jour par filtrage qui le maintient, la réduction exacte d’un POMDP à un MDP sur les croyances, la fonction de valeur linéaire par morceaux et convexe qui rend cette réduction calculable en principe, et les raisons mesurées pour lesquelles elle ne l’est pas en pratique - avec le point fixe de la croyance, les vecteurs alpha et la fonction de valeur calculés et non affirmés.
Les décisions dans l’incertitude : utilité et information
Pourquoi il peut être rationnel de refuser un pari dont la valeur monétaire espérée est positive, ce que mesure la courbure d’une fonction d’utilité, et comment donner un prix à une observation avant de l’acheter - y compris dans le cas fréquent où le prix honnête est nul.
Satisfaction de contraintes et propagation
Ce qui change quand on décrit un problème par des variables, des domaines et des contraintes plutôt que comme une boîte noire : une commutativité qui réduit l’arbre gratuitement, une propagation qui prouve qu’une branche est sans espoir avant de l’explorer, et une mesure montrant que la plus célèbre des heuristiques d’ordonnancement ne fait rien à elle seule.
La planification classique : schémas, relaxations et graphes
Pourquoi la planification reçoit sa propre représentation au lieu d’être une note de bas de page de la recherche, comment supprimer des morceaux de la description d’une action produit une heuristique gratuitement, et ce qu’un graphe de planification remarque que les heuristiques but par but manquent systématiquement.
Raisonner sur un monde qui change
Comment deux hypothèses de Markov transforment un historique non borné en deux petites tables, les récursions progressive et rétrograde qui répondent à toute question sur le présent et le passé, pourquoi la séquence la plus probable exige un algorithme à elle seule, et ce qui change quand l’état est un nombre réel plutôt qu’une liste.
Réseaux bayésiens et inférence probabiliste
Comment un graphe et quelques petites tables tiennent lieu d’une loi jointe à des milliers d’entrées, comment y répondre exactement à une requête par énumération et élimination de variables, et que faire quand l’inférence exacte est hors de portée : échantillonnage par rejet, pondération par vraisemblance et échantillonnage de Gibbs, chacun travaillé sur les deux mêmes réseaux.
La recherche classique : de la largeur d’abord à A*
Transformer un problème en espace d’états et laisser un algorithme le parcourir : ce que coûtent vraiment la complétude et l’optimalité, pourquoi c’est la mémoire et non le temps qui met en échec la recherche en largeur, et les deux conditions sur une heuristique qui rendent A* prouvablement optimal.
Les probabilités à partir de zéro : le langage de l’incertitude
Construire les probabilités depuis la base : les mondes possibles, l’univers, les deux axiomes fondamentaux, puis les règles d’addition et de multiplication, chacune démontrée plutôt qu’affirmée, avec des exemples numériques résolus.
La logique et la représentation des connaissances
Raisonner sur ce qui doit être vrai : modèles et conséquence logique déroulés par énumération exhaustive, correction et complétude, pourquoi la logique propositionnelle épuise son pouvoir expressif, et là où la logique du premier ordre prend le relais.
Le théorème de Bayes et la mise à jour des croyances
Démontrer le théorème de Bayes à partir de la définition de la probabilité conditionnelle, puis résoudre deux fois l’exemple du taux de base qui trompe presque tout le monde : une fois avec la formule, une fois par simple dénombrement.
L’apprentissage par renforcement et le Q-learning
Apprendre à bien agir sans modèle du monde : mises à jour par différence temporelle, la règle du Q-learning, exploration contre exploitation, et une exécution qui retrouve l’optimum planifié à partir de la seule expérience.
Les processus de décision markoviens
Comment planifier quand les actions ne font pas fiablement ce qu’on veut : états, modèle de transition, récompenses et actualisation, l’équation de Bellman, et l’itération sur les valeurs menée numériquement jusqu’à son point fixe.
La recherche adversariale et le minimax
Comment un programme joue contre un adversaire qui cherche à le battre : la valeur minimax, pourquoi l’élagage alpha-bêta atteint la même réponse en examinant moins de nœuds, et un arbre de jeu élagué coup par coup.
La théorie des jeux et l’équilibre de Nash
Le raisonnement stratégique quand les joueurs ne sont pas strictement opposés : stratégies dominantes, le dilemme du prisonnier déroulé depuis sa matrice de gains, l’équilibre de Nash, l’optimalité de Pareto, et pourquoi équilibre et efficacité peuvent s’opposer.
Outils (1)
Recherche (5)
On Computable Numbers, with an Application to the Entscheidungsproblem
Introduit une machine abstraite qui lit et écrit des symboles sur un ruban selon une table finie de règles, et s’en sert pour montrer qu’aucune procédure générale ne peut décider si un programme quelconque s’arrête.
Programming a Computer for Playing Chess
Expose comment une machine pourrait jouer aux échecs : représenter les positions, engendrer les coups légaux, explorer l’arbre de jeu par minimax, et évaluer les positions non terminales par une fonction de score heuristique.
Computing Machinery and Intelligence
Propose de remplacer la question « les machines peuvent-elles penser ? » par un test comportemental, dans lequel un interrogateur tente de distinguer une machine d’un humain par conversation écrite.
The Perceptron: A Perceiving and Recognizing Automaton
Introduit le perceptron, une unité entraînable qui calcule une somme pondérée de ses entrées et s’active si la somme dépasse un seuil, avec une règle d’ajustement des poids à partir d’exemples étiquetés.
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Introduit l’algorithme A*, qui ordonne la recherche par la somme du coût déjà engagé et d’une estimation heuristique du coût restant, et démontre son optimalité lorsque l’heuristique ne surestime jamais.
Projets (2)
Game-Playing Agent
Minimax avec élagage alpha-bêta sur un véritable arbre de jeu, plus un solveur d’équilibres pour petits jeux sous forme normale : le jeu optimal contre un adversaire, et contre un joueur rationnel.
Gridworld RL Lab
Itération sur la valeur, itération sur la politique et Q-learning sur le même monde en grille, pour comparer directement un planificateur qui connaît le modèle à un apprenant qui l’ignore.