Fléau de la dimension

Le phénomène a été originellement identifié par Richard Bellman alors qu'il travaillait sur des problèmes d'optimisation dynamique[1] - [2].

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[3]. Pour réaliser dans [0,1]¹⁰ une couverture équivalente à celle des 100 points 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.

Une des solutions consiste à remplacer les données originales par des données dans un espace de plus petite dimension, tout en conservant l'essentiel des caractéristiques de celles-ci. C'est la réduction de la dimensionnalité. Deux approches classiques sont la sélection de caractéristique, qui consiste à choisir un petit ensemble de variables représentatives, et l'extraction de caractéristique, qui consiste à définir de nouvelles variables plus pertinentes.