En lisant rapidement le papier s'interroge sur la faisabilité du problème de l'apprentissage par l'exemple, en prenant l'angle de la complexité algorithmique.
L'apprentissage automatique "IA" est défini comme "à partir d'un certain nombre d'exemples de comportements humains (tiré dans un ensemble plus grand de comportements observés), apprendre un modèle ou un algorithme (d'une certaine taille) qui permette de prédire le comportement/décision humain avec une bonne probabilité"
Le raisonnement est de partir d'un problème algorithmique (perfect versus chance).
On dispose d'un certain nombre de données d'une certaine taille (un nombre de bits donnés), à chacun est associé pile ou face. On dispose d'un moyen d'en choisir au hasard
Le problème est de savoir si il existe un algorithme suffisamment "petit" (avec un certain nombre d'instruction, de taille au max k) qui puisse prédire si une donnée de notre jeu de donnée est pile ou face.
Il y a deux cas possible, soit il existe un tel algorithme de taille au max k, soit aucun des algorithmes possibles ne fait mieux que le hasard. Le problème consiste à savoir dans quel cas on est ! (on peut y voir des similarité avec la notion de complexité de kolmogorov, qui consiste à trouver le plus petit programme possible qui reproduit des données, la meilleure manière possible de compresser des données, mais en plus simple, trouver la complexité de Kolmogorov est un problème indécidable)
Il se trouve que résoudre un tel problème est NP-difficile, c'est à dire que la quantité de calcul augmente en général très rapidement avec la taille des données.
Le papier argumente que si il existait une procédure d'apprentissage automatique qui soit aussi capable de simuler un comportement humain, on pourrait l'appliquer sur un tel jeu de donnée pour voir s'il est "apprenable" avec une telle taille de modèle (cas 1), ou pas (cas 2). En lançant la procédure d'apprentissage efficace "de puissance IA" sur plusieurs jeux d'exemple du jeu de données, les auteurs argumentent qu'on pourrait en choisissant le meilleur d'entre eux décider si on est dans le cas 1 ou 2 et donc résoudre le problème "perfect by chance".
Les conséquences seraient que, comme la procédure d'apprentissage "IA" est supposée efficace et que le problème est lui impossible à résoudre efficacement, une IA est condamnée à ne jamais avoir assez d'exemple en pratique et que le nombre d'erreur doit augmenter exponentiellement. Notamment parce que prédire un comportement humain nécessite d'avoir en entrée beaucoup de données, donc le problème est algorithmiquement très gros et un algorithme exponentiel sur ce type de données c'est condamné à l'échec, donc que les modèles appris en pratique sont condamnés à être lacunaires.
Les auteurs clament avoir été charitables en hypothèses sur la procédure d'apprentissage en prenant le meilleur cas, pour trouver une borne inférieure.
Je ne suis pas certain que ce soit le cas, parce que le problème de départ sur lequel ils s'appuient pour la "réduction" est quand même très peu structuré, et que la classe de modèle sur lesquels ils s'appuient est complètement générique. Or on sait que si on restreint la classe de modèle à des modèles plus spécialisés/appropriés dans certaines taches ça change beaucoup de chose, et que les données sont probablement plus structurées que leur problème aléatoire qui ne fait aucune hypothèse sur la structure des données. Il parait évident de dire que le problème est plus simple sur des distributions avec beaucoup de structures que sur des distributions dont on ne sait rien, et que l'humain non plus ne sait rien faire avec des données aléatoires ou bien bruitées imprédictibles, donc c'est pas sympa. Est-ce bien une borne inférieure, si on rajoute des hypothèses sur la structure en entrée on doit pouvoir trouver de meilleures bornes inférieures.
Ils indiquent ensuite que diviser le problème de l'IA général en sous problèmes et en recombinant ces résultats dans un système plus gros ne change pas grand chose à leur argument, je sais pas trop ce que j'en pense pour l'instant. Et ils partent sur des considérations sur le rapport entre la cognition et l'étude de l'intelligence humaine et l'IA.
# (tentative de) résumé du papier
Posté par Thomas Douillard . Évalué à 6 (+3/-0).
En lisant rapidement le papier s'interroge sur la faisabilité du problème de l'apprentissage par l'exemple, en prenant l'angle de la complexité algorithmique.
L'apprentissage automatique "IA" est défini comme "à partir d'un certain nombre d'exemples de comportements humains (tiré dans un ensemble plus grand de comportements observés), apprendre un modèle ou un algorithme (d'une certaine taille) qui permette de prédire le comportement/décision humain avec une bonne probabilité"
Le raisonnement est de partir d'un problème algorithmique (perfect versus chance).
On dispose d'un certain nombre de données d'une certaine taille (un nombre de bits donnés), à chacun est associé pile ou face. On dispose d'un moyen d'en choisir au hasard
Le problème est de savoir si il existe un algorithme suffisamment "petit" (avec un certain nombre d'instruction, de taille au max k) qui puisse prédire si une donnée de notre jeu de donnée est pile ou face.
Il y a deux cas possible, soit il existe un tel algorithme de taille au max k, soit aucun des algorithmes possibles ne fait mieux que le hasard. Le problème consiste à savoir dans quel cas on est ! (on peut y voir des similarité avec la notion de complexité de kolmogorov, qui consiste à trouver le plus petit programme possible qui reproduit des données, la meilleure manière possible de compresser des données, mais en plus simple, trouver la complexité de Kolmogorov est un problème indécidable)
Il se trouve que résoudre un tel problème est NP-difficile, c'est à dire que la quantité de calcul augmente en général très rapidement avec la taille des données.
Le papier argumente que si il existait une procédure d'apprentissage automatique qui soit aussi capable de simuler un comportement humain, on pourrait l'appliquer sur un tel jeu de donnée pour voir s'il est "apprenable" avec une telle taille de modèle (cas 1), ou pas (cas 2). En lançant la procédure d'apprentissage efficace "de puissance IA" sur plusieurs jeux d'exemple du jeu de données, les auteurs argumentent qu'on pourrait en choisissant le meilleur d'entre eux décider si on est dans le cas 1 ou 2 et donc résoudre le problème "perfect by chance".
Les conséquences seraient que, comme la procédure d'apprentissage "IA" est supposée efficace et que le problème est lui impossible à résoudre efficacement, une IA est condamnée à ne jamais avoir assez d'exemple en pratique et que le nombre d'erreur doit augmenter exponentiellement. Notamment parce que prédire un comportement humain nécessite d'avoir en entrée beaucoup de données, donc le problème est algorithmiquement très gros et un algorithme exponentiel sur ce type de données c'est condamné à l'échec, donc que les modèles appris en pratique sont condamnés à être lacunaires.
Les auteurs clament avoir été charitables en hypothèses sur la procédure d'apprentissage en prenant le meilleur cas, pour trouver une borne inférieure.
Je ne suis pas certain que ce soit le cas, parce que le problème de départ sur lequel ils s'appuient pour la "réduction" est quand même très peu structuré, et que la classe de modèle sur lesquels ils s'appuient est complètement générique. Or on sait que si on restreint la classe de modèle à des modèles plus spécialisés/appropriés dans certaines taches ça change beaucoup de chose, et que les données sont probablement plus structurées que leur problème aléatoire qui ne fait aucune hypothèse sur la structure des données. Il parait évident de dire que le problème est plus simple sur des distributions avec beaucoup de structures que sur des distributions dont on ne sait rien, et que l'humain non plus ne sait rien faire avec des données aléatoires ou bien bruitées imprédictibles, donc c'est pas sympa. Est-ce bien une borne inférieure, si on rajoute des hypothèses sur la structure en entrée on doit pouvoir trouver de meilleures bornes inférieures.
Ils indiquent ensuite que diviser le problème de l'IA général en sous problèmes et en recombinant ces résultats dans un système plus gros ne change pas grand chose à leur argument, je sais pas trop ce que j'en pense pour l'instant. Et ils partent sur des considérations sur le rapport entre la cognition et l'étude de l'intelligence humaine et l'IA.
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.