Malédiction de la dimensionalité

Fléau de la dimension ou Malédiction de la dimension (Curse of dimensionality) est un terme inventé par Richard Bellman pour qualifier le problème de l'augmentation explosive du volume de données associée à l'ajout de dimensions supplémentaires dans un espace mathématique.

Leo Breiman donne l'exemple de 100 observations couvrant l'intervalle unidimensionnel [0,1] dans les réels: il est possible de dresser un histogramme des résultats et d'en tirer des inférences. En revanche, dans l'espace correspondant à 10 dimensions [0,1]¹⁰, les 100 observations sont des points isolés dans un vaste espace vide, et ne permettent pas l'analyse statistique. Pour réaliser dans [0,1]¹⁰ une couverture équivalente à celle des 100 point dans [0,1], il ne faut pas moins de 10²⁰ observations – entreprise gigantesque et souvent impraticable.

Le fléau de la dimension est un obstacle majeur dans l'apprentissage automatique, qui revient souvent à tirer des inférences d'un nombre réduit d'expériences dans un espace de possibilités de dimension élevée. Il devient alors souvent nécessaire d'injecter des informations a priori de manière à contraindre le système d'apprentissage pour obtenir des inférences. Il doit être préparé au type d'information à extraire. On parle alors d'inférence bayésienne.

Bibliographie

Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.