Statistiques robustes de grande dimension avec ilias diakonikolas

Ilias Diakonikolas est des professeurs du département d’informatique de l’Université du Wisconsin-Madison où ses principaux intérêts de recherche se trouvent dans les algorithmes et l’apprentissage automatique. Son travail se concentre sur la compréhension du compromis entre l’efficacité statistique, l’efficacité informatique et la robustesse pour les problèmes fondamentaux dans les statistiques et l’apprentissage automatique, où la robustesse se réfère largement à la capacité d’un modèle à gérer des données bruyantes.

Ilias a récemment remporté le prix du papier exceptionnel chez Nerips pour son travail, PAC indépendant de la distribution apprenant des demi-espaces avec le bruit de Massartqui se concentre sur un domaine appelé apprentissage robuste à haute dimension et est essentiellement les premiers progrès réalisés autour de l’apprentissage indépendant de la distribution avec le bruit depuis les années 80.

* Alerte nerd !! * Si vous appréciez nos conversations plus techniques, avance que cette interview ne décevra pas.

Robustesse dans l’apprentissage automatique

Ce champ cherche à identifier les algorithmes d’apprentissage automatique qui sont robustes au bruit dans leurs données d’entrée dans une variété de paramètres. Les algorithmes d’apprentissage automatique font généralement des hypothèses sur les données sur lesquelles elles fonctionnent et les modèles (souvent implicites) utilisés pour générer ces données.

Les statisticiens et les informaticiens ont depuis longtemps développé des algorithmes qui peuvent éliminer le bruit lorsque les données d’entrée ne sont qu’une seule ou quelques valeurs (dimensions). Mais avec des données à haute dimension comme les images ou les dossiers médicaux, la séparation des bonnes données du bruit reste un problème de recherche difficile. Ilias souligne que « même un très petit écart par rapport au modèle supposé pourrait rendre l’algorithme d’apprentissage automatique très très fragile … nous devons rectifier cela et développer une méthodologie pour avoir des algorithmes d’apprentissage robustes pour des problèmes de grande dimension. »

Le apprentissage robuste un problème sur lequel Ilias travaille diffère des autres recherches sur robustesse aux attaques contradictoires en termes de lorsque les données sont perturbées. En règle générale, dans le scénario de robustesse contradictoire, vous supposez que le modèle est formé avec des données propres et que l’objectif est d’améliorer ses performances lorsqu’il est présenté avec des données corrompues (c’est-à-dire une attaque de temps de test). Pour le type de robustesse, les Ilias travaillent avec le modèle est formé sur des données corrompues dès le début (c’est-à-dire une attaque de formation).

Problèmes de données corrompues dans des paramètres de grande dimension

Considérez le problème de l’estimation de la moyenne d’un groupe d’échantillons indépendants et distribués à l’identification (IID). Comme vous le savez probablement, le processus est assez simple (prenez la somme et divisez par nombre d’échantillons). Mais s’il y a une valeur aberrante qui ne provient pas de la distribution que vous avez supposée, alors votre moyenne serait erronée et votre estimation pourrait ne jamais converger vers la moyenne réelle (car elle pourrait être arbitrairement loin de la vraie moyenne). Si vous n’opérez qu’en une seule dimension, vous pouvez contourner le problème des valeurs aberrantes en prenant la médiane au lieu de la moyenne.

Si nous appliquons cette même méthode à des points de données à haute dimension et que vos données sont faire le ménage (signifiant tiré d’une seule distribution), vous pouvez alors calculer de la même manière la moyenne empirique. Cependant, si vos données sont corrompues et ont beaucoup de valeurs aberrantes, alors l’approche de la prise de la médiane ne fonctionnera pas.

Dans un cadre de grande dimension, vous ne pouvez pas regarder les coordonnées individuelles et calculer la médiane car le bruit peut s’accumuler à travers plusieurs dimensions, et la quantité d’erreurs peut évoluer à une très grande quantité. Cela peut être évité avec des limites théoriques de l’information, mais l’utilisation d’un algorithme efficace en calcul n’est pas quelque chose que nous savions faire.

Le papier Neirips: indépendant de la distribution, apprentissage PAC, Massart Noise, oh mon!

L’objectif de cet article est de trouver un algorithme capable d’adapter un modèle linéaire à des données bruyantes et à haute dimension. Plus précisément, il vise à effectuer une classification binaire, c’est-à-dire en appliquant un séparateur linéaire qui distingue un point en deux classes: positif ou négatif.

« Ce que nous montrons dans cet article, c’est que, en fait, dans un modèle très raisonnable de perturbations d’étiquettes aléatoires, c’est quelque chose qui … peut être fait avec un algorithme efficace en calcul … vous pouvez réellement apprendre des séparateurs linéaires efficacement en présence de bruit. »

Explorons la terminologie introduite dans le titre du document d’Ilias:

Indépendant de la distribution. En observant des exemples étiquetés de X (points en dimensions élevées) et y (étiquettes binaires), nous n’avons pas besoin de faire des hypothèses sur les X! Nous pouvons simplement supposer que nos X sont des échantillons IID et à partir d’une distribution fixe, mais même cela peut être arbitraire car en réalité, vous ne savez peut-être rien de la distribution des données.

Pac Learning (probablement approximativement correct). Il s’agit du modèle standard de classification binaire donnée par Leslie Valiant dans les années 80, et des modèles similaires de Vapnik, où vous essayez de trouver un classificateur qui se généralise sur des données invisibles.

Demi-espace: Le séparateur linéaire que nous recherchons entre les classes positives et négatives.

Massart Noise. Une façon de modéliser le bruit dans vos données consiste à définir la probabilité qu’un point de données (ou un étiquette dans ce cas) soit renversé. Le bruit de Massart est un peu plus subtil. Avec le bruit de Massart, la probabilité qu’une étiquette soit perturbée est délimitée par une certaine constante mais Nous ne savons pas La probabilité exacte qu’il va être retourné, il peut être n’importe quoi de zéro à la constante.

Appliquer de manière itérative une descente de gradient stochastique

Pour essayer de résoudre ce problème, Ilias et l’approche initiale de son équipe ont été d’essayer d’utiliser une bonne descente (SGD). Malheureusement, ils ont appris que non seulement SGD échouerait, mais ils ont prouvé qu’il serait impossible d’utiliser pour résoudre ce problème.

Cependant, tout n’a pas été perdu. En prouvant l’intraitabilité de SGD, l’équipe a découvert que SGD peut réellement résoudre un non-trivial partie du problème. Cela était suffisant pour leur donner un orteil, et ce document présente un algorithme pour laisser le SGD de manière itérative résoudre cette partie du processus, puis la relancer sur ce qui reste à obtenir plus de la solution à chaque fois.

Bien sûr, un algorithme peut exister, mais cela ne signifie pas qu’il est efficace, par exemple, s’il nécessite un nombre exponentiel d’itérations pour trouver une solution. En fait, Ilias et son équipe ont démontré que dans chaque itération, une fraction polynomiale non triviale et inverse de l’espace est couverte, donc le nombre maximal d’itérations nécessaires pour couvrir l’espace est tout au plus un nombre polynomial d’itérations.

Quelle est la prochaine étape?

Pour Ilias, ce n’est que le début: « Dans un certain sens, (ceci) est le premier article de cette ligne de travail à faire l’apprentissage indépendant de la distribution avec le bruit … et je pense que cela va conduire à de nombreux développements. »

Une continuation de l’œuvre dans le journal se fait avec son collègue Christos Tzamos et deux doctorants à l’UW, montrant que si vous faites des hypothèses raisonnables sur la distribution basée sur la concentration et l’anti-concentration (c’est-à-dire que la distribution des intrants n’est pas trop dense ou vide nulle part), SGD peut travailler comme ça.

Une entreprise connexe est une enquête sur laquelle Ilias a travaillé avec le collaborateur de longue date, Daniel Kane appelé Progrès récents dans les statistiques robustes algorithmiques à grande dimension. L’enquête couvre un aperçu d’environ 100 articles explorant les techniques qui ont été développées dans l’espace jusqu’à présent, et évalue dans quelle direction la communauté devrait aller suivre. L’enquête sera publiée bientôt dans le cadre du livre Au-delà de l’analyse des pires cas.

Implications pratiques: intoxication et mise en œuvre des données

L’une des implications pratiques des statistiques robustes est la prévention de l’empoisonnement des données. L’empoisonnement aux données est le phénomène qui se produit lorsque vous avez des données entrantes de l’extérieur et que le système est vulnérable aux utilisateurs malveillants qui insérent de fausses données qui détruisent le comportement du modèle.

Bien que le potentiel d’applications soit important, ce qui retient la mise en œuvre généralisée est que les algorithmes utilisent des méthodes spectrales et ne sont pas automatiques car la communauté d’apprentissage automatique le veut. De plus, de nombreux problèmes du monde réel sont non convexes, ce qui signifie que SGD ne peut pas être appliqué directement. Ilias pense que cela peut changer bientôt et travaille actuellement à l’élimination des algorithmes et à la structure de ces problèmes non convexes pour les formuler de telle manière que le SGD peut les résoudre suffisamment.