Fléau de la dimension
Cet article est une ébauche concernant les probabilités et la statistique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
Le fléau de la dimension ou malédiction de la dimension (curse of dimensionality) est un terme inventé par Richard Bellman en 1961 pour désigner divers phénomènes qui ont lieu lorsque l'on cherche à analyser ou organiser des données dans des espaces de grande dimension alors qu'ils n'ont pas lieu dans des espaces de dimension moindre.
Plusieurs domaines sont concernés et notamment l'apprentissage automatique, la fouille de données, les bases de données, l'analyse numérique ou encore l'échantillonnage. L'idée générale est que lorsque le nombre de dimensions augmente, le volume de l'espace croît rapidement si bien que les données se retrouvent « isolées » et deviennent éparses. Cela est problématique pour les méthodes nécessitant un nombre significatif de données pour être valides, les rendant alors peu efficaces voire inopérantes.
Historique
modifierLe phénomène a été originellement identifié par Richard Bellman alors qu'il travaillait sur des problèmes d'optimisation dynamique[1],[2].
Exemples illustratifs
modifierLeo 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]10, 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]10 une couverture équivalente à celle des 100 points dans [0,1], il ne faut pas moins de 1020 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.
Solutions
modifierUne 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.
Notes et références
modifier- Richard Ernest Bellman, Dynamic programming, Princeton University Press, (ISBN 978-0-691-07951-6, lire en ligne),
Nouvelle édition : (en) Richard Ernest Bellman, Dynamic Programming, Courier Dover Publications, , 340 p. (ISBN 978-0-486-42809-3, lire en ligne) - (en) Richard Ernest Bellman, Adaptive control processes : a guided tour, Princeton University Press, (lire en ligne)
- (en) Christophe Giraud, Introduction to High-Dimensional Statistics, Chapman and Hall/CRC,
