Wirkt sich der Fluch der Dimensionalität auf einige Modelle stärker aus als auf andere?

15

Die Stellen, die ich über den Fluch der Dimensionalität gelesen habe, erklären ihn hauptsächlich in Verbindung mit kNN und linearen Modellen im Allgemeinen. Ich sehe regelmäßig Spitzenreiter in Kaggle, die Tausende von Funktionen in einem Datensatz verwenden, der kaum 100.000 Datenpunkte enthält. Sie verwenden unter anderem hauptsächlich Boosted-Bäume und NN. So viele Features scheinen zu hoch zu sein und ich glaube, sie würden durch den Fluch der Dimensionalität beeinträchtigt. Dies scheint jedoch nicht der Fall zu sein, da diese Modelle sie zu Spitzenreitern machen. Zurück zu meiner ursprünglichen Frage: Werden einige Modelle stärker vom Fluch der Dimensionalität betroffen als andere?

Konkret interessieren mich folgende Modelle (nur weil mir diese bekannt sind / verwendet werden):

  • Lineare und logistische Regression
  • Entscheidungsbäume / RandomForest / Boosted Trees
  • Neuronale Netze
  • SVM
  • kNN
  • k-bedeutet Clustering
neural-networks svm k-means k-nearest-neighbour high-dimensional Dileep Kumar Patchigolla
quelle
Die kurze Antwort lautet definitiv ja, aber vielleicht möchten Sie Modelle, an denen Sie tatsächlich interessiert sind? Ich bin sicher, die CV-Community könnte Ihnen von Tausenden verschiedener Arten von Modellen erzählen, die vom Fluch der Dimensionalität betroffen sind. Wenn Sie sich auf bestimmte Modelltypen beschränken, kann dies hilfreich sein, um diese Frage zu beantworten.
@RustyStatistician - Ich habe ein paar Modelle hinzugefügt, die mich interessieren.
Dileep Kumar Patchigolla
Diese Frage interessiert mich sehr, blieb aber unbeantwortet. Wie kann ich dies sichtbar machen, um Antworten zu erhalten?
Dileep Kumar Patchigolla

Antworten:

16

Im Allgemeinen erschwert der Fluch der Dimensionalität das Durchsuchen eines Raums erheblich und beeinflusst die Mehrzahl der Algorithmen, die durch Partitionierung ihres Vektorraums "lernen". Je größer die Dimensionalität unseres Optimierungsproblems ist, desto mehr Daten benötigen wir, um den zu optimierenden Bereich auszufüllen.

Verallgemeinerte lineare Modelle

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

Entscheidungsbäume
Entscheidungsbäume leiden auch unter dem Fluch der Dimensionalität. Entscheidungsbäume unterteilen direkt den Abtastraum an jedem Knoten. Mit zunehmendem Abtastraum nehmen die Abstände zwischen den Datenpunkten zu, wodurch es sehr viel schwieriger wird, eine "gute" Aufteilung zu finden.

Zufällige Wälder
Zufällige Wälder verwenden eine Sammlung von Entscheidungsbäumen, um ihre Vorhersagen zu treffen. Anstatt jedoch alle Funktionen Ihres Problems zu verwenden, verwenden einzelne Bäume nur eine Teilmenge der Funktionen. Dies minimiert den Raum, über den jeder Baum optimiert, und kann dabei helfen, das Problem des Fluches der Dimensionalität zu bekämpfen.


Boosting-Algorithmen von Boosted Tree wie AdaBoost leiden unter dem Fluch der Dimensionalität und neigen dazu, zu überladen, wenn die Regularisierung nicht verwendet wird. Ich werde nicht weiter darauf eingehen, weil der Beitrag AdaBoost weniger oder anfälliger für Überanpassungen ist. erklärt den Grund warum besser als ich konnte.

Neuronale Netze
Neuronale Netze sind in dem Sinne seltsam, dass sie beide vom Fluch der Dimensionalität abhängig von der Architektur, den Aktivierungen, der Tiefe usw. betroffen sind und nicht. Um den Fluch der Dimensionalität zu wiederholen, ist das Problem, dass eine große Anzahl von Punkten in der Höhe erforderlich ist Abmessungen, um einen Eingaberaum abzudecken. Eine Möglichkeit, tiefe neuronale Netze zu interpretieren, besteht darin, sich vorzustellen, dass alle Schichten die allerletzte Schicht als eine komplizierte Projektion einer hochdimensionalen Mannigfaltigkeit in eine niederdimensionale Mannigfaltigkeit ausführen, auf der dann die letzte Schicht klassifiziert wird. In einem Faltungsnetzwerk zur Klassifizierung, in dem die letzte Schicht eine Softmax-Schicht ist, können wir die Architektur so interpretieren, dass eine nichtlineare Projektion auf eine kleinere Dimension und dann eine multinomiale logistische Regression (die Softmax-Schicht) auf dieser Projektion durchgeführt wird. In gewisser Weise erlaubt uns die komprimierte Darstellung unserer Daten, den Fluch der Dimensionalität zu umgehen. Auch dies ist eine Interpretation, in Wirklichkeit wirkt sich der Fluch der Dimensionalität tatsächlich auf neuronale Netze aus, jedoch nicht auf der gleichen Ebene wie die oben beschriebenen Modelle.

SVM
SVM neigen dazu, aufgrund der übermäßigen Regularisierung, die auftritt, nicht so viel wie verallgemeinerte lineare Modelle zu überladen. Schauen Sie sich diesen Beitrag SVM, Überanpassung, Fluch der Dimensionalität für weitere Details an.

K-NN, K-Means

Sowohl K-mean als auch K-NN sind stark vom Fluch der Dimensionalität betroffen, da beide das L2-Quadrat-Abstandsmaß verwenden. Mit zunehmender Größe vergrößert sich auch der Abstand zwischen verschiedenen Datenpunkten. Aus diesem Grund benötigen Sie eine größere Anzahl von Punkten, um mehr Platz abzudecken, in der Hoffnung, dass die Entfernung aussagekräftiger wird.

Bitte fragen Sie nach Einzelheiten zu den Modellen, da meine Antworten ziemlich allgemein sind. Hoffe das hilft.

Armen Aghajanyan
quelle
Hi Amen Tolle prägnante Erklärungen für alle Modelle, die ich gefragt habe. Probleme mit linearen Modellen sind für mich immer noch nicht klar: Sind lineare Modelle besser oder schlechter als k-NN- und k-Means-Modelle für dieselbe Anzahl von Dimensionen? Und wenn Sie sagten, Kollinearität sei ein Problem für lineare Modelle, implizieren Sie dann, dass hohe Dimensionen bei linearen Modellen ohne (oder mit minimaler) Kollinearität kein Problem sind?
Dileep Kumar Patchigolla
Es ist schwer zu quantifizieren, ob lineare Modelle für ein beliebiges Problem eine bessere Leistung als k-nn oder k-means liefern. Wenn Ihr Problem linear trennbar ist, würde ich meine Einsätze auf das lineare Modell setzen, während ich mit k-nn weitermachen würde, wenn Ihr Raum etwas komplizierter ist. Kollinearität verschärft das Problem des Fluchs der Dimensionalität, auch ohne Kollinearität gilt der Fluch der Dimensionalität weiterhin. K-Mittel sollten in gleichem Maße leiden wie k-nn, da beide nachbargetrieben sind und im Allgemeinen die gleiche Abstandsfunktion verwenden. In der Realität ist es schwer zu quantifizieren, wie schlecht der Nachnahme ist. Hoffe das hilft!
Armen Aghajanyan
Was ist Ihre Definition von Fluch der Dimensionalität (CoD)? Ihre Antwort scheint darauf hinzudeuten, dass lineare Modelle am meisten unter CoD leiden. Dies ist irreführend: Da es sich um eine globale Methode handelt, leiden lineare Modelle viel weniger unter lokalisierten Methoden wie KNN.
Matifou