Quand on mentionne le théorème du No Free Lunch, il faudrait aussi préciser qu’en pratique, ce n’est pas vraiment un obstacle
Le simple fait de supposer que les données viennent du monde réel suffit à rendre ce théorème inoffensif
Le livre ne traite pas du tout ce point ; j’aurais aimé qu’il explique qu’ici, « toutes les distributions » revient plutôt à généraliser à un espace de grande dimension de fonctions discontinues toutes les suites de bits possibles produites par des lancers de pièce, et que les fonctions continues n’en constituent qu’un minuscule sous-ensemble
Au fond, cela veut surtout dire que si les données proviennent d’une distribution uniforme aléatoire de « toutes les possibilités », on ne peut pas apprendre à prédire quelque chose comme le résultat du prochain lancer de pièce
Exact. Les théorèmes du No Free Lunch de ce type, ou les résultats fondés sur des hypothèses trop générales, ont généralement l’air beaucoup trop pessimistes
Par exemple, beaucoup de gens pensent naïvement que le problème de l’arrêt ou le théorème de Rice rendent impossible l’analyse statique de programmes
C’est similaire au problème de l’induction de Hume. Sans hypothèses, on ne peut pas relier les observations passées aux prédictions futures
Le fait que le soleil se soit levé mille matins de suite ne rend pas automatiquement plus ou moins probable qu’il se lève demain ; il faut poser une hypothèse du type que les événements ont globalement tendance à se poursuivre de manière similaire au fil du temps
Ce genre d’hypothèse ne peut pas être extrait des données. Même si les choses se sont déroulées de façon similaire par le passé, cela ne dit rien sur l’avenir
Pourtant, la science fonctionne très bien malgré ce problème, et le machine learning continue aussi de bien fonctionner parce que les gens utilisent leur expérience et leurs connaissances a priori lorsqu’ils conçoivent des algorithmes
On appelle ces hypothèses des biais inductifs : elles orientent l’apprentissage vers certains motifs, par exemple « les choses proches ont généralement tendance à être similaires »
Je ne vois pas bien comment cette précision s’applique. Je comprends le théorème du No Free Lunch non pas comme disant que certains problèmes sont inapprenables, mais qu’il n’existe pas d’algorithme unique qui fonctionne bien sur toutes les classes de problèmes
Les exemples utilisés dans la preuve peuvent être artificiels, mais dans la pratique, ne choisit-on pas justement des algorithmes différents selon les hypothèses supplémentaires ?
La théorie de l’apprentissage est une tentative de formaliser les sciences naturelles jusqu’à la prise de décision. L’hypothèse cachée des sciences naturelles est qu’un modèle algorithmique du monde suffisamment sophistiqué permet de prédire les observations futures à partir des observations passées
C’est la même hypothèse que celle posée par Solomonoff dans sa preuve de l’inférence inductive ; il faut donc partir d’un codage Turing-complet, et non du codage prétendument « universel » de Rissanen
Lorsqu’on construit des sous-théories, il est acceptable de s’éloigner de ce point de départ, mais si l’on ne commence pas par là, on aboutit aux résultats bancals que l’on voit depuis 50 ans, comme la confusion autour de ce que signifie exactement le « principe de longueur de description minimale »
En revanche, si l’on cherche à construire des modèles causaux, ce n’est pas acceptable. Pour modéliser des systèmes dynamiques, on ne peut pas s’affranchir d’un code Turing-complet
On peut voir un système dynamique comme une machine à états finis dotée d’un très grand nombre d’états, mais pour produire un code compressé optimal, il faut une sémantique Turing-complète s’exécutant sur un graphe orienté cyclique composé d’un nombre très grand mais fini de bascules ou de portes universelles comme NOR et NAND
A-t-on désormais compris ce qui cause la double descente ?
Je ne sais pas si c’est un résultat généralisé, mais l’équipe Circuits d’Anthropic a proposé une hypothèse assez convaincante. La première phase de descente correspondrait au moment où le modèle mémorise les points de données, tandis que la seconde serait le passage vers l’apprentissage géométrique de caractéristiques
Ici, les caractéristiques peuvent être vues comme un espace vectoriel abstrait de très grande dimension
Cette équipe étudie en profondeur l’idée de superposition, où un même neurone encode plusieurs concepts
Elle a expérimenté avec des modèles jouets et des jeux de données représentant explicitement des caractéristiques latentes, puis les compressant dans un petit ensemble de dimensions de données afin de forcer la superposition, et montre à quoi ressemble cette superposition selon la taille des données d’entraînement
C’est évidemment un modèle jouet, mais au moins pour les modèles soumis à la superposition, l’idée est convaincante https://transformer-circuits.pub/2023/toy-double-descent/ind...
Je ne suis pas spécialiste, mais cet article explore la double descente avec un modèle simple
L’interprétation est la suivante : lorsqu’on passe dans le régime surparamétré, on peut optimiser vers des poids de faible norme, et ces poids généralisent mieux
Que cela explique la double descente de façon générale, ou que cela s’applique à d’autres modèles comme les réseaux de neurones profonds, est une autre question https://arxiv.org/pdf/2303.14151.pdf
On ne sait pas encore. Mon hypothèse préférée, personnellement, est que la descente de gradient stochastique est littéralement stochastique
Comme elle optimise sur un très petit sous-ensemble du corpus d’entraînement, et non sur l’ensemble complet, le gradient n’est pas exact
L’idée est qu’un entraînement excessif pousse à travers les optimums locaux et, au lieu de contourner des puits locaux de surapprentissage, permet de progresser récursivement vers la distribution réelle
Internet regorge d’excellents PDF de maths gratuits rédigés par des universitaires, des enseignants et des ingénieurs. Le problème, c’est qu’il y a aussi énormément de redondance de contenu
Je me demande s’il serait possible de créer un modèle d’IA capable de synthétiser proprement des ensembles de ressources qui se recoupent en un seul PDF cohérent, sans doublons
Il suffirait peut-être de choisir le livre utilisé dans le cours universitaire correspondant
Pas besoin d’un modèle d’IA. Probabilistic Machine Learning de Murphy est une excellente référence et une excellente ressource
Petit pinaillage, mais le titre prête à confusion. Il vaudrait mieux remplacer le premier mot par Machine-Learning ou Statistical-Learning
J’espère que l’auteur le corrigera un jour, si possible
Lecture assez difficile. Par exemple, dès la première page du chapitre 1, il est question de minimisation d’une forme quadratique et l’on montre quelque chose qui ressemble à la formule des moindres carrés linéaires, mais sans aucune explication indiquant si c’est bien cela
Un peu plus de commentaire aiderait probablement
J’aime en revanche le fait qu’il y ait beaucoup d’exercices
Ce texte semble s’adresser à des personnes ayant déjà un certain bagage mathématique et cherchant à comprendre la théorie de l’apprentissage
De plus, le chapitre en question est clairement présenté comme une révision, ce qui suppose que ce contenu a déjà été appris ailleurs, ou le sera
Partir des premiers principes ne veut pas dire que ce soit facile à lire
Comme le dit le commentaire frère, il est clair que ce document ne vise pas les débutants
Cela dit, l’intuition est bonne. Si l’on écrit la fonction objectif des moindres carrés ordinaires, on obtient une forme quadratique
Le choix du mot « quadratique » n’est pas un hasard : c’est une généralisation matricielle d’une fonction du second degré
Cette section traite de la version vectorielle de la minimisation d’une fonction quadratique
Ça ne donne clairement pas l’impression de partir des premiers principes
Les moindres carrés sont une expression quadratique
Quadratique signifie qu’il y a un terme au carré
Intéressant. Existe-t-il de bons livres sur ce sujet ?
Intéressant. Il faudra que je le parcoure quand j’aurai plus de temps
À première vue, il semble couvrir une bonne partie des mêmes sujets que ce livre [1]. Je me demande en quoi les deux diffèrent
[1]: https://www.cambridge.org/core/books/understanding-machine-l...
Un livre de machine learning sorti en 2014, ça a désormais un côté ancien et historique
J’attends avec impatience le jour où je pourrai dire à GPT-5 : « J’ai une idée que j’aimerais essayer ; lis ce livre et dis-moi s’il contient des éléments pertinents pour la faire mieux fonctionner »
Je n’ai jamais entendu dire qu’un LLM avait produit une idée nouvelle. Ce ne serait possible que si c’est une idée que quelqu’un a déjà essayée, non ?
Je me rends compte que transmettre le contexte de $this est la partie difficile
Il est très difficile de décrire mon contexte d’utilisateur avec quelques variables de faible dimension, et je ne comprends pas moi-même assez bien ma situation dans l’univers pour l’expliquer à une IA
Le vocabulaire que je partage avec l’IA est également insuffisant. Internet donne l’impression d’avoir réussi à échanger de manière cohérente un état convenu grâce à un protocole commun, HTTP
Par exemple, dans Uber, on peut transmettre un état dans un monde étroit de requêtes-réponses : numéro de téléphone, véhicule, GPS, heure actuelle, paiement, etc.
Mais en tant qu’étudiant qui veut apprendre les algorithmes, je ne sais pas comment faire passer des informations complexes comme mon âge, mon environnement d’usage d’Internet, mon lieu de vie, ma préférence pour les explications graphiques, mon historique d’intimidation face aux gros livres, des jalons comme CS50, ou mon niveau en Python
Pour une idée de startup aussi, dire simplement qu’elle a « peu de traction » ne suffit pas : il faut transmettre un état comme le réseau de VC, de développeurs et de commerciaux, les preuves de partenariats réussis, le nombre de participants, le chiffre d’affaires, etc.
Même dans le monde réel, les contextes de chacun sont si différents que ce vocabulaire n’existe que dans de petites poches
Supposer que la connaissance existe comme une variable globale et éternelle pose aussi problème. Dans certaines régions, beaucoup de gens n’ont pas l’électricité, ni même un téléphone basique ; le fait qu’un PDF recommandé par une IA soit utile ou non dépend alors des structures de pouvoir locales et de la gouvernance
Je ne sais pas comment tout cela va évoluer, mais rien que d’en envisager les possibilités est passionnant. Les ordinateurs peuvent facilement converser avec nous et ressemblent dès le premier jour à des bébés intelligents, mais le vrai goulet d’étranglement pour en tirer davantage d’utilité est peut-être, au bout du compte, notre incapacité à leur fournir assez de données, pertinentes et bon marché
Si tu lis ce livre toi-même, ton idée s’améliorera. Tu pourrais aussi apprendre des choses nouvelles en chemin
1 commentaires
Commentaires de Hacker News
Quand on mentionne le théorème du No Free Lunch, il faudrait aussi préciser qu’en pratique, ce n’est pas vraiment un obstacle
Le simple fait de supposer que les données viennent du monde réel suffit à rendre ce théorème inoffensif
Le livre ne traite pas du tout ce point ; j’aurais aimé qu’il explique qu’ici, « toutes les distributions » revient plutôt à généraliser à un espace de grande dimension de fonctions discontinues toutes les suites de bits possibles produites par des lancers de pièce, et que les fonctions continues n’en constituent qu’un minuscule sous-ensemble
Au fond, cela veut surtout dire que si les données proviennent d’une distribution uniforme aléatoire de « toutes les possibilités », on ne peut pas apprendre à prédire quelque chose comme le résultat du prochain lancer de pièce
Par exemple, beaucoup de gens pensent naïvement que le problème de l’arrêt ou le théorème de Rice rendent impossible l’analyse statique de programmes
Le fait que le soleil se soit levé mille matins de suite ne rend pas automatiquement plus ou moins probable qu’il se lève demain ; il faut poser une hypothèse du type que les événements ont globalement tendance à se poursuivre de manière similaire au fil du temps
Ce genre d’hypothèse ne peut pas être extrait des données. Même si les choses se sont déroulées de façon similaire par le passé, cela ne dit rien sur l’avenir
Pourtant, la science fonctionne très bien malgré ce problème, et le machine learning continue aussi de bien fonctionner parce que les gens utilisent leur expérience et leurs connaissances a priori lorsqu’ils conçoivent des algorithmes
On appelle ces hypothèses des biais inductifs : elles orientent l’apprentissage vers certains motifs, par exemple « les choses proches ont généralement tendance à être similaires »
Les exemples utilisés dans la preuve peuvent être artificiels, mais dans la pratique, ne choisit-on pas justement des algorithmes différents selon les hypothèses supplémentaires ?
La théorie de l’apprentissage est une tentative de formaliser les sciences naturelles jusqu’à la prise de décision. L’hypothèse cachée des sciences naturelles est qu’un modèle algorithmique du monde suffisamment sophistiqué permet de prédire les observations futures à partir des observations passées
C’est la même hypothèse que celle posée par Solomonoff dans sa preuve de l’inférence inductive ; il faut donc partir d’un codage Turing-complet, et non du codage prétendument « universel » de Rissanen
Lorsqu’on construit des sous-théories, il est acceptable de s’éloigner de ce point de départ, mais si l’on ne commence pas par là, on aboutit aux résultats bancals que l’on voit depuis 50 ans, comme la confusion autour de ce que signifie exactement le « principe de longueur de description minimale »
En revanche, si l’on cherche à construire des modèles causaux, ce n’est pas acceptable. Pour modéliser des systèmes dynamiques, on ne peut pas s’affranchir d’un code Turing-complet
On peut voir un système dynamique comme une machine à états finis dotée d’un très grand nombre d’états, mais pour produire un code compressé optimal, il faut une sémantique Turing-complète s’exécutant sur un graphe orienté cyclique composé d’un nombre très grand mais fini de bascules ou de portes universelles comme NOR et NAND
A-t-on désormais compris ce qui cause la double descente ?
Ici, les caractéristiques peuvent être vues comme un espace vectoriel abstrait de très grande dimension
Cette équipe étudie en profondeur l’idée de superposition, où un même neurone encode plusieurs concepts
Elle a expérimenté avec des modèles jouets et des jeux de données représentant explicitement des caractéristiques latentes, puis les compressant dans un petit ensemble de dimensions de données afin de forcer la superposition, et montre à quoi ressemble cette superposition selon la taille des données d’entraînement
C’est évidemment un modèle jouet, mais au moins pour les modèles soumis à la superposition, l’idée est convaincante
https://transformer-circuits.pub/2023/toy-double-descent/ind...
Plus de détails ici : https://calculatedcontent.com/2019/12/03/towards-a-new-theor...
L’interprétation est la suivante : lorsqu’on passe dans le régime surparamétré, on peut optimiser vers des poids de faible norme, et ces poids généralisent mieux
Que cela explique la double descente de façon générale, ou que cela s’applique à d’autres modèles comme les réseaux de neurones profonds, est une autre question
https://arxiv.org/pdf/2303.14151.pdf
Comme elle optimise sur un très petit sous-ensemble du corpus d’entraînement, et non sur l’ensemble complet, le gradient n’est pas exact
L’idée est qu’un entraînement excessif pousse à travers les optimums locaux et, au lieu de contourner des puits locaux de surapprentissage, permet de progresser récursivement vers la distribution réelle
Internet regorge d’excellents PDF de maths gratuits rédigés par des universitaires, des enseignants et des ingénieurs. Le problème, c’est qu’il y a aussi énormément de redondance de contenu
Je me demande s’il serait possible de créer un modèle d’IA capable de synthétiser proprement des ensembles de ressources qui se recoupent en un seul PDF cohérent, sans doublons
Petit pinaillage, mais le titre prête à confusion. Il vaudrait mieux remplacer le premier mot par Machine-Learning ou Statistical-Learning
J’espère que l’auteur le corrigera un jour, si possible
Lecture assez difficile. Par exemple, dès la première page du chapitre 1, il est question de minimisation d’une forme quadratique et l’on montre quelque chose qui ressemble à la formule des moindres carrés linéaires, mais sans aucune explication indiquant si c’est bien cela
Un peu plus de commentaire aiderait probablement
J’aime en revanche le fait qu’il y ait beaucoup d’exercices
De plus, le chapitre en question est clairement présenté comme une révision, ce qui suppose que ce contenu a déjà été appris ailleurs, ou le sera
Cela dit, l’intuition est bonne. Si l’on écrit la fonction objectif des moindres carrés ordinaires, on obtient une forme quadratique
Le choix du mot « quadratique » n’est pas un hasard : c’est une généralisation matricielle d’une fonction du second degré
Cette section traite de la version vectorielle de la minimisation d’une fonction quadratique
Quadratique signifie qu’il y a un terme au carré
Intéressant. Existe-t-il de bons livres sur ce sujet ?
Intéressant. Il faudra que je le parcoure quand j’aurai plus de temps
À première vue, il semble couvrir une bonne partie des mêmes sujets que ce livre [1]. Je me demande en quoi les deux diffèrent
[1]: https://www.cambridge.org/core/books/understanding-machine-l...
J’attends avec impatience le jour où je pourrai dire à GPT-5 : « J’ai une idée que j’aimerais essayer ; lis ce livre et dis-moi s’il contient des éléments pertinents pour la faire mieux fonctionner »
$thisest la partie difficileIl est très difficile de décrire mon contexte d’utilisateur avec quelques variables de faible dimension, et je ne comprends pas moi-même assez bien ma situation dans l’univers pour l’expliquer à une IA
Le vocabulaire que je partage avec l’IA est également insuffisant. Internet donne l’impression d’avoir réussi à échanger de manière cohérente un état convenu grâce à un protocole commun, HTTP
Par exemple, dans Uber, on peut transmettre un état dans un monde étroit de requêtes-réponses : numéro de téléphone, véhicule, GPS, heure actuelle, paiement, etc.
Mais en tant qu’étudiant qui veut apprendre les algorithmes, je ne sais pas comment faire passer des informations complexes comme mon âge, mon environnement d’usage d’Internet, mon lieu de vie, ma préférence pour les explications graphiques, mon historique d’intimidation face aux gros livres, des jalons comme CS50, ou mon niveau en Python
Pour une idée de startup aussi, dire simplement qu’elle a « peu de traction » ne suffit pas : il faut transmettre un état comme le réseau de VC, de développeurs et de commerciaux, les preuves de partenariats réussis, le nombre de participants, le chiffre d’affaires, etc.
Même dans le monde réel, les contextes de chacun sont si différents que ce vocabulaire n’existe que dans de petites poches
Supposer que la connaissance existe comme une variable globale et éternelle pose aussi problème. Dans certaines régions, beaucoup de gens n’ont pas l’électricité, ni même un téléphone basique ; le fait qu’un PDF recommandé par une IA soit utile ou non dépend alors des structures de pouvoir locales et de la gouvernance
Je ne sais pas comment tout cela va évoluer, mais rien que d’en envisager les possibilités est passionnant. Les ordinateurs peuvent facilement converser avec nous et ressemblent dès le premier jour à des bébés intelligents, mais le vrai goulet d’étranglement pour en tirer davantage d’utilité est peut-être, au bout du compte, notre incapacité à leur fournir assez de données, pertinentes et bon marché