La malédiction dimensionnelle affecte-t-elle certains modèles plus que d'autres?

15

Les endroits que j'ai lus sur la malédiction de la dimensionnalité l'expliquent conjointement avec kNN principalement et les modèles linéaires en général. Je vois régulièrement les meilleurs classeurs de Kaggle utiliser des milliers d'entités sur un ensemble de données qui ne contient pratiquement pas 100 000 points de données. Ils utilisent principalement les arbres boostés et NN, entre autres. Que de nombreuses fonctionnalités semblent trop élevées et je pense qu'elles seraient affectées par la malédiction de la dimensionnalité. Mais cela ne semble pas être le cas, car ces modèles les placent en tête des compétitions. Donc, revenons à ma question initiale - certains modèles sont-ils plus affectés par la malédiction de la dimensionnalité que d'autres?

Plus précisément, je m'intéresse aux modèles suivants (uniquement parce que ce sont ceux que je connais / utilise):

  • Régression linéaire et logistique
  • Arbres de décision / Forêts aléatoires / Arbres boostés
  • Les réseaux de neurones
  • SVM
  • kNN
  • clustering k-means
neural-networks svm k-means k-nearest-neighbour high-dimensional Dileep Kumar Patchigolla
la source
La réponse courte est certainement oui, mais peut-être voulez-vous des modèles qui vous intéressent réellement? Je suis sûr que la communauté CV pourrait vous parler de milliers de types de modèles différents qui sont affectés par la malédiction de la dimensionnalité. Ainsi, le fait de restreindre votre attention à certains types de modèles peut aider à répondre à cette question.
@RustyStatistician - J'ai ajouté quelques modèles qui m'intéressent.
Dileep Kumar Patchigolla
Je suis assez intéressé par cette question mais elle est restée sans réponse. Comment puis-je mettre cela en évidence, pour obtenir des réponses?
Dileep Kumar Patchigolla

Réponses:

17

En général, la malédiction de la dimensionnalité rend le problème de la recherche à travers un espace beaucoup plus difficile et affecte la majorité des algorithmes qui "apprennent" en partitionnant leur espace vectoriel. Plus la dimensionnalité de notre problème d'optimisation est élevée, plus nous avons besoin de données pour remplir l'espace sur lequel nous optimisons.

Modèles linéaires généralisés

β^=(X′X)−1X′y

Arbres de
décision Les arbres de décision souffrent également de la malédiction de la dimensionnalité. Les arbres de décision partitionnent directement l'espace échantillon à chaque nœud. À mesure que l'espace d'échantillonnage augmente, les distances entre les points de données augmentent, ce qui rend beaucoup plus difficile de trouver une «bonne» répartition.

Forêts
aléatoires Les forêts aléatoires utilisent une collection d'arbres de décision pour faire leurs prédictions. Mais au lieu d'utiliser toutes les fonctionnalités de votre problème, les arborescences individuelles utilisent uniquement un sous-ensemble des fonctionnalités. Cela minimise l'espace sur lequel chaque arbre optimise et peut aider à lutter contre le problème de la malédiction de la dimensionnalité.

Les
algorithmes de Boosted Tree Boosting tels que AdaBoost souffrent de la malédiction de la dimensionnalité et ont tendance à sureffectuer si la régularisation n'est pas utilisée. Je n'entrerai pas dans les détails, car la publication AdaBoost est-elle moins ou plus sujette au sur-ajustement? explique la raison pour laquelle mieux que moi.

Les réseaux de neurones
Les réseaux de neurones sont étranges dans le sens où ils sont tous deux et ne sont pas impactés par la malédiction de la dimensionnalité dépendant de l'architecture, des activations, de la profondeur, etc. dimensions pour couvrir un espace d'entrée. Une façon d'interpréter les réseaux de neurones profonds est de penser que toutes les couches s'attendent à ce que la toute dernière couche fasse une projection compliquée d'un collecteur de dimension élevée dans un collecteur de dimension inférieure, où la dernière couche se classe par-dessus. Ainsi, par exemple, dans un réseau convolutif pour la classification où la dernière couche est une couche softmax, nous pouvons interpréter l'architecture comme faisant une projection non linéaire sur une dimension plus petite, puis faisant une régression logistique multinomiale (la couche softmax) sur cette projection. Donc, dans un sens, la représentation compressée de nos données nous permet de contourner la malédiction de la dimensionnalité. Encore une fois, c'est une interprétation, en réalité, la malédiction de la dimensionnalité affecte en fait les réseaux de neurones, mais pas au même niveau que les modèles décrits ci-dessus.

SVM
SVM a tendance à ne pas surévaluer autant que les modèles linéaires généralisés en raison de la régularisation excessive qui se produit. Consultez ce post SVM, Overfitting, malédiction de dimensionnalité pour plus de détails.

K-NN, K-Means

K-mean et K-NN sont tous deux fortement impactés par la malédiction de la dimensionnalité, car ils utilisent tous deux la mesure de distance au carré L2. À mesure que la quantité de dimensions augmente, la distance entre les différents points de données augmente également. C'est pourquoi vous avez besoin d'un plus grand nombre de points pour couvrir plus d'espace dans l'espoir que la distance soit plus descriptive.

N'hésitez pas à demander des détails sur les modèles, car mes réponses sont assez générales. J'espère que cela t'aides.

Armen Aghajanyan
la source
Salut Amen Excellentes explications succinctes pour tous les modèles que j'ai demandés. Les problèmes avec les modèles linéaires ne sont toujours pas clairs pour moi: les modèles linéaires fonctionnent-ils mieux ou moins bien que les modèles k-NN et k-Means pour le même non: de dimensions? Et lorsque vous avez dit que la colinéarité est un problème pour les modèles linéaires, impliquez-vous qu'avec une colinéarité nulle (ou minimale), les dimensions élevées ne sont pas un problème avec les modèles linéaires?
Dileep Kumar Patchigolla
Il est difficile de quantifier si les modèles linéaires fonctionneront mieux que k-nn ou k-moyennes pour un problème arbitraire. Si votre problème est séparable linéairement, je placerais mes paris sur le modèle linéaire, tandis que si votre espace est un peu plus compliqué, j'irais avec k-nn. La colinéarité aggrave le problème de la malédiction de la dimensionnalité, même sans colinéarité, la malédiction de la dimensionnalité s'applique toujours. Les K-moyennes devraient souffrir dans la même mesure que les k-nn car ils sont tous deux conduits par les voisins et utilisent généralement la même fonction de distance. En réalité, il est difficile de quantifier la gravité du DCO. J'espère que cela t'aides!
Armen Aghajanyan
Quelle est votre définition de la malédiction de la dimensionnalité (CoD)? Votre réponse semble suggérer que les modèles linéaires souffrent le plus du CoD, ce qui est trompeur: étant une méthode globale, les modèles linéaires souffrent beaucoup moins que les méthodes localisées telles que KNN.
Matifou