Fléau de la dimension

Le rapport, c'est que ça justifie le fait de faire du machine learning.

S'il n'y avait pas le fléau de la dimension, avec peu de données et une recherche par plus proche voisin on pourrait inférer et interpoler efficacement.

Le fléau de la dimension montre que ça devient vite impossible.

La méthode n'échoue pas, c'est juste que si tu veux un voisin dans chaque hypercube d'une résolution donnée de ton espace borné (c'est ça le but sans rentrer dans le détail, pouvoir inférer pour n'importe quel nouveau point de ton espace, donc par plus proche voisin il faut des voisins partout dans l'espace), tu vas voir que le nombre de voisins (d'hypercubes en fait) nécessaire croit exponentiellement avec la dimension.

Le but du machine learning c'est de généraliser avec moins de données. Même quand on utilise des millions de données en deep learning, ça reste très largement exponentiellement moins que ce qui serait nécessaire par plus proche voisin brut (bien sûr, du plus proche voisin sur un espace appris de dimension réduite, c'est déjà un algorithme de machine learning).

En gros, les plus proches voisins c'est le truc le plus naïf que tu puisses imaginer.

Or cela nécessite des voisins, c'est-à-dire des données :)o Combien pour que la méthode marche bien ? On se rend vite compte que sous quelques hypothèses assez légères, ce nombre croit exponentiellement avec la dimension.

En effet, si je veux un voisin à une distance L1 d'au plus $m$ de chaque point de l'espace, afin que je puisse faire une prédiction fiable en n'importe quel point, et que mon espace a une taille $D$ dans chaque dimension, alors j'ai besoin de $(D/m)^d$ voisins (donc données) uniformément répartis (un dans chaque hypercube de taille $m^d$) où $d$ est la dimension de l'espace. C'est exactement ce dont tu parles dans ton premier message.

Donc en pratique, la méthode est complètement inapplicable, et justifie le fait de rechercher des méthodes d'apprentissage qui vont apprendre la structure des données ou des distributions afin d'être efficace avec beaucoup moins de données.

Cela justifie au passage l'hypothèse primordiale de manifold de petite dimension en machine learning, car s'il n'y avait aucune structure cachée on ne pourrait rien faire non plus.

C'est pas un petit truc. C'est certes mathématiquement trivial, mais si on n'avait pas ce résultat, alors on n'aurait tout simplement pas besoin de faire du machine learning pour caricaturer.