Gibt es in realen Daten wirklich einen „Fluch der Dimensionalität“?

17

Ich verstehe, was "Fluch der Dimensionalität" ist, und ich habe einige hochdimensionale Optimierungsprobleme gelöst und kenne die Herausforderung der exponentiellen Möglichkeiten.

Ich bezweifle jedoch, dass der "Fluch der Dimensionalität" in den meisten Daten der realen Welt existiert (also lassen Sie uns Bilder oder Videos für einen Moment beiseite, ich denke über Daten wie demografische Kunden- und Kaufverhaltensdaten nach).

Wir können Daten mit Tausenden von Features erfassen, aber es ist weniger wahrscheinlich, dass die Features einen Raum mit Tausenden von Dimensionen vollständig abdecken können. Aus diesem Grund sind Techniken zur Dimensionsreduzierung so beliebt.

Mit anderen Worten, es ist sehr wahrscheinlich, dass die Daten nicht die exponentielle Informationsebene enthalten, dh, viele Features sind stark korreliert und viele Features erfüllen 80-20 Regeln (viele Instanzen haben den gleichen Wert).

In einem solchen Fall werden Methoden wie KNN meiner Meinung nach immer noch einigermaßen gut funktionieren. (In den meisten Büchern besagt der "Fluch der Dimensionalität", dass Dimension> 10 problematisch sein könnte. In ihren Demos verwenden sie eine gleichmäßige Verteilung in allen Dimensionen, in denen die Entropie wirklich hoch ist. Ich bezweifle, dass dies in der realen Welt jemals passieren wird.)

Meine persönliche Erfahrung mit realen Daten ist, dass der "Fluch der Dimensionalität" die Schablonenmethode (wie KNN) nicht zu sehr beeinflusst und in den meisten Fällen die Dimensionen ~ 100 immer noch funktionieren.

Trifft dies auf andere Menschen zu? (Ich habe 5 Jahre lang mit realen Daten in verschiedenen Branchen gearbeitet und nie beobachtet, dass "alle Distanzpaare ähnliche Werte haben", wie im Buch beschrieben.)

hxd1011
quelle
1
Da Sie Bilder und Bildanalysen ausdrücklich ausgeschlossen haben, möchte ich in den Kommentaren nur vermerken, dass sich dieses Feld ziemlich regelmäßig mit dem Fluch der Dimensionalität befasst. Es ist sehr einfach, eine Overfit-Lösung zu finden.
Ashe
7
Binär / Dummy / One-Hot-codierte kategoriale Features können ein entfernungsbasiertes Modell leicht in die Luft
jagen
2
Ein Kollege von mir hat mit dem Verkauf von Sonnenbrillen gearbeitet. Eine ganze Reihe von Merkmalen war kategorisch mit einer großen Anzahl möglicher Ebenen (z. B. Marken, Materialien verschiedener Teile der Brille usw.). Ich hatte definitiv Angst vor dem CoD, aber es ist immer schwer zu sagen, ob es in einem bestimmten Datensatz vorhanden ist oder nicht, und wir haben mit ziemlicher Wahrscheinlichkeit nicht viele Standardtricks gemacht, da wir keine Experten für diesen bestimmten Analysetyp sind.
S. Kolassa - Wiedereinsetzung von Monica am
@StephanKolassa Haben entfernungsbasierte Methoden im Anwendungsfall Sonnenbrille funktioniert?
Haitao Du
Nicht allzu gut. Es war kein sehr erfolgreiches Projekt.
S. Kolassa - Reinstate Monica

Antworten:

15

In diesem Aufsatz (1) wird der Segen der Uneinheitlichkeit als Kontrapunkt zum Fluch der Dimensionalität erörtert . Die Hauptidee besteht darin, dass die Daten nicht gleichmäßig innerhalb des Merkmalsraums verteilt sind, sodass eine Traktion erzielt werden kann, indem die Art und Weise identifiziert wird, in der die Daten organisiert sind.

(1) Pedro Domingos, "Einige nützliche Informationen zum maschinellen Lernen"

Sycorax sagt Reinstate Monica
quelle
7

Der Fluch der Dimensionalität beim maschinellen Lernen ist häufiger das Problem der Explosion des leeren Raums zwischen den wenigen Datenpunkten, die Sie haben. Niedrige Verteilerdaten können es noch schlimmer machen. Hier ist ein Beispiel-Setup mit 10000 Beispielen, bei dem ich versuche, kNN mit 1 Nachbarn zu machen.

from numpy.random import normal
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import precision_score
import matplotlib.pyplot as plt
import numpy as np
from math import sqrt
from scipy.special import gamma

N=10000
N_broad=2
scale=20

dims=[]
precs=[]


def avg_distance(k):
    return sqrt(2)*gamma((k+1)/2)/gamma(k/2)

for dim in range(N_broad+1,30):
    clf = KNeighborsClassifier(1, n_jobs=-1)

    X_train=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_train=(X_train[:,N_broad]>0).astype(int)
    clf.fit(X_train, y_train)

    X_test=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_test=(X_test[:,N_broad]>0).astype(int)
    y_test_pred=clf.predict(X_test)

    prec=precision_score(y_test, y_test_pred)
    dims.append(dim)
    precs.append(prec)
    print(dim, prec)

plt.plot(dims, precs)
plt.ylim([0.5,1])
plt.xlabel("Dimension")
plt.ylabel("Precision")
plt.title("kNN(1) on {} samples".format(N))
plt.show()

Sie mochten keine vollständig gleichmäßigen Verteilungen, daher habe ich eine 2D-Mannigfaltigkeit mit kleineren (um reduzierten scale) Abmessungen erstellt , die um die 2D-Ebene der ersten beiden Koordinaten gestreut sind. In jedem Fall ist eine der kleineren Dimensionen vorhersehbar (die Bezeichnung ist 1, wenn diese Dimension positiv ist).

Die Präzision nimmt mit zunehmender Dimension schnell ab.kNN Präzision

Natürlich wäre Präzision = 0,5 eine Zufallsschätzung. Mit einer Entscheidungsoberfläche, die komplizierter ist als ein Flugzeug, würde es noch schlimmer werden.

Es ist, als ob die kNN-Kugeln zu dünn wären, um eine glatte Hyperebene zu untersuchen. Bei höheren Dimensionen fühlen sie sich zunehmend einsamer.

Auf der anderen Seite haben Methoden wie SVM eine globale Sichtweise und sind viel besser.

Gerenuk
quelle
5

Betrachten Sie zum Beispiel Zeitreihen (und Bilder und Audio). Sensorwerte (Internet der Dinge) sind weit verbreitet.

Der Fluch der Dimensionalität ist viel häufiger als Sie denken. Dort gibt es eine große Redundanz, aber auch viel Rauschen.

Das Problem ist, dass viele Menschen diese Herausforderungen realer Daten einfach vermeiden und immer und immer wieder dieselben UCI-Datensätze verwenden.

Anony-Mousse - Setzen Sie Monica wieder ein
quelle
P(X)=P(X1)n=2NP(Xn|Xn-1)
1
Vielleicht die meisten Daten der realen Welt ist von Sensoren wie Bilder, Videos und Zeitreihen?
Anony-Mousse
2
@ hxd1011 markov-Eigenschaft ist eine Abstraktion, die möglicherweise nichts mit echten Daten zu tun hat!
Sycorax sagt Reinstate Monica
0

Es gibt einen wunderbaren Artikel, "Statistische Modellierung: die beiden Kulturen" , von Breiman. Er erklärt die beiden Gruppen von Wissenschaftlern, die mit Daten umgehen und wie jeder von ihnen "Dimensionalität" betrachtet. Die Antwort auf Ihre Frage lautet "es kommt darauf an", in welcher Gruppe Sie sich befinden. Überprüfen Sie das Papier.

Zamir Akimbekov
quelle
Dank @Zamir Akimbekov gibt es große Diskussionen hier , und ein weiteres interessantes Papier hier
Haitao Du