Cet article est mon récit gratuit de la capacité d' apprentissage peut être indécidable, Shai Ben-David, et al.
Récemment sur Habré, l'article Machine learning a fait face à un problème mathématique non résolu , qui est une traduction de l'article de Shay Ben-David dans l'article Nature News du même nom. Cependant, en raison de la nature du sujet et de la brièveté de l'examen original, il est resté complètement incompréhensible pour moi ce qui était dans l'article. Connaissant Shai Ben-David, en tant qu'auteur de l'excellent livre "Understanding Machine Learning: From Theory to Algorithms", je me suis intéressé à ce sujet, j'ai pris connaissance de ce travail et j'ai essayé de souligner les principaux points ici.
Je dois dire tout de suite que l'article est assez compliqué et, peut-être, j'ai raté quelques points importants, mais ma critique sera plus complète que celle qui est déjà sur Habré.
Quelques mots sur l'apprentissage PAC en général
La première chose qui m'a dérouté dans une critique de Nature News était que le problème d'apprentissage lui-même était présenté comme quelque chose de complètement nouveau. En fait, c'est un problème long et relativement bien étudié.
Quelques concepts de base pour ceux qui ne connaissent pas la questionLe risque est fonction de - la valeur réelle et prédite de la variable cible, qui reflète à quel point nous nous sommes trompés dans notre prédiction. Une valeur inférieure reflète une erreur plus petite. L'exemple le plus simple d'un problème de classification est une fonction d'indicateur. . Pour la régression, ce sera l'écart type . De toute évidence, il peut y avoir des options plus complexes. Un autre nom pour ce concept est la fonction de perte.
Risque moyen - la valeur de risque moyenne sur l'ensemble de l'espace de données d'entrée. Étant donné qu'un tel espace est généralement infini (par exemple, pour les fonctionnalités réelles), ou exponentiellement grand (par exemple, un espace de tailles d'image de 1024x1024 et de valeurs de pixels de 0 à 255), nous ne pouvons pas estimer directement cette valeur. Cependant, il existe des méthodes d'estimation de cette quantité que nous n'allons pas aborder maintenant. C'est cet indicateur que nous voulons finalement minimiser. Parfois, cet indicateur est également appelé erreur de généralisation.
Le risque empirique est la valeur moyenne du risque sur un certain ensemble de données empiriques sélectionné dans l'ensemble de l'espace de données d'entrée. Habituellement, nos algorithmes d'apprentissage automatique sont impliqués dans la minimisation de cette valeur.
La tâche de l'apprentissage automatique est de construire une solution (fonction) basée sur l'ensemble de données empiriques disponibles qui donnerait une valeur minimale de risque moyen.
Il existe une théorie de l'apprentissage probablement presque correct (Probablement un apprentissage correct ou approximatif, PAC ).
Définition simplifiée d'un algorithme d'apprentissage machine formé par PACAlgorithme A construisant, en utilisant un échantillon empirique X de taille n, une fonction h qui restaure la valeur de la variable cible est entraînée par PAC si pour n'importe quel seuil et confiance la taille de l'échantillon d'apprentissage n est telle que pour la fonction h apprise, la condition suivante est remplie: la probabilité que la valeur de risque moyenne dépasse moins de .
Nous pouvons le comprendre de cette façon: après avoir sélectionné certaines de nos exigences pour la fonction h , du point de vue de sa valeur de risque moyenne, nous saurons qu'il y a une telle taille de l'ensemble de données (sélectionnées, évidemment, indépendamment et au hasard dans tout l'espace) que lorsque nous apprenons sur elle, nous Nous atteindrons ces exigences.
Cette théorie remonte aux années 80 du siècle dernier. Cependant, il ne fournit aucun indicateur mesurable qui refléterait la capacité d'apprentissage d'un algorithme. Mais une telle réponse est donnée par la théorie de l'apprentissage statistique ( théorie VC ) déjà développée par V. Vapnik et A. Chervonenkis. Cette théorie est basée sur un indicateur numérique de la dimension VC. La dimension VC est une estimation combinatoire de la taille maximale des données que l'algorithme peut diviser en deux parties de toutes les manières possibles.
ExempleSupposons que nous ayons un algorithme qui construit un hyperplan de séparation dans un espace à n dimensions. Considérons un espace unidimensionnel: deux points dans un tel espace peuvent toujours être divisés, mais trois ne peuvent plus être divisés, ce qui signifie que VC = 2. Considérons un espace à deux dimensions: trois points sont toujours divisés en deux classes, mais quatre points ne peuvent pas être divisés par tous les moyens possibles, donc VC = 3.
En fait, il peut être strictement démontré que VC pour une classe d'hyperplans dans un espace à n dimensions est .
Le théorème principal de la théorie VC, dans l'une des formulations possibles, prouve le fait que si la dimension VC de l'algorithme est finie, alors il est entraîné par PAC. De plus, la dimension VC est un indicateur de la rapidité avec l'augmentation de la taille de l'échantillon empirique, la valeur du risque empirique converge vers la valeur du risque moyen.
Ainsi, le problème de l'apprentissage automatique des algorithmes d'apprentissage automatique en soi est relativement bien étudié et a une base mathématique rigoureuse.
Quel est donc le sujet d'un article dans Nature?
Les auteurs écrivent que le problème avec la théorie PAC, basée sur différentes dimensions de dimension, est qu'elle n'est pas universelle.
Divers indicateurs de dimension de la théorie des PAC Les auteurs donnent un exemple intéressant d'un problème dont l'énoncé lui-même est conçu de telle sorte que le succès ne peut pas être formulé comme un apprentissage PAC. Les auteurs écrivent:
Imaginez que nous ayons un site Internet sur lequel nous affichons des publicités. Définissez X comme l'ensemble de tous les visiteurs potentiels de ce site. La publicité est sélectionnée dans un certain pool publicitaire. Supposons conditionnellement que chaque annonce du pool soit dirigée vers une certaine catégorie d'utilisateurs: annonces sportives aux amateurs de sport, etc. La tâche consiste à placer exactement le type de publicité qui convient le mieux aux visiteurs du site .
Le problème ici est que nous ne savons pas vraiment qui visitera le site à l'avenir. Pour résumer, l'énoncé d'un tel problème peut être décrit comme suit:
Avoir un ensemble de fonctionnalités sur l'ensemble trouver une telle fonction de sorte que sa métrique sur la distribution inconnue était maximum. De plus, il est nécessaire de trouver une telle fonction basée sur un ensemble limité de quantités indépendantes identiquement distribuées à partir de
Formation EMX
Shai Ben-David et ses collègues présentent un nouveau concept - E stimulant le M a X imum (apprentissage EMX), qui donne simplement des critères d'apprentissage pour de tels problèmes de maximisation:
Pour l'ensemble de fonctionnalités , ensembles d'entrées et distribution inconnue pour n'importe quel nombre fonction est -Formation EMX pour toute distribution :
Cette définition de l'apprentissage est sans aucun doute plus générale que le concept de SAA.
Alors, où le continuum et le «problème non résolu des mathématiques» ont-ils à voir avec cela?
Les auteurs prouvent le théorème suivant:
Chiffre d'affaires EMX concernant indépendant du système d'axiomes Zermelo - Frenkel avec l'axiome de choix (ci-après ZFC).
En d'autres termes, en utilisant des axiomes mathématiques standard, nous ne pouvons dans le cas général prouver ni la possibilité de trouver une solution au problème d'apprentissage EMX ni prouver l'impossibilité de trouver cette solution.
Les auteurs montrent également que dans le cas général de l'apprentissage EMX, il n'y a pas d'analogue de la dimension VC (ou de toute autre dimension) qui serait fini dans le cas de la mesurabilité EMX, et vice versa, l'apprentissage EMX découlerait de sa finitude. Plus strictement, ils l'ont formulé comme suit:
Il y a une telle constante que si nous supposons la cohérence de ZFC, alors il n'y a pas une telle propriété que pour certains $ en ligne $ m, M> c $ en ligne $ pour tout et ensemble de fonctionnalités serait réalisée:
- Si vrai alors complexité de l'apprentissage EMX ne dépasse pas M;
- Si faux alors complexité de l'apprentissage EMX au moins m;
Au contraire, cela est vrai, par exemple, pour la dimension VC, car pour égal ce sera essentiellement une formulation du théorème principal de la théorie VC.
Conclusion
Le message de l'ouvrage est en effet peu lié aux enjeux pratiques de l'apprentissage automatique, voire aux questions théoriques de la théorie de l'apprentissage statistique. Il m'a semblé qu'il y avait deux pensées principales dans le travail:
- Une belle connexion entre l'apprentissage EMX et les théorèmes de Gödel;
- L'impossibilité fondamentale de créer une caractérisation universelle de l'apprentissage (comme la dimension VC) pour la classe générale des problèmes d'apprentissage automatique.
Dans le même temps, je n'aime pas du tout le titre "L'apprentissage automatique a rencontré un problème mathématique non résolu", utilisé dans la traduction d'une revue de cet article . À mon avis, c'est un clickbait absolu, de plus, il ne correspond tout simplement pas à la réalité. L'œuvre originale ne signifie pas que quelqu'un a rencontré quelque chose. L'apprentissage automatique et la théorie des PAC ont tous deux fonctionné et continuent de fonctionner. Il est souligné que la théorie PAC ne peut pas être généralisée à certaines déclarations particulières du problème d'apprentissage automatique, des connexions intéressantes sont trouvées avec les théorèmes de Gödel, mais pas un mot sur un problème non résolu que l'apprentissage automatique a rencontré.