Erklärung der Formel für den Median, der dem Ursprung von N Proben aus der Einheitskugel am nächsten liegt

11

In Elements of Statistical Learning wird ein Problem eingeführt, um Probleme mit k-nn in hochdimensionalen Räumen hervorzuheben. Es gibt N Datenpunkte, die gleichmäßig in einer p dimensionalen Einheitskugel verteilt sind.

Der mittlere Abstand vom Ursprung zum nächsten Datenpunkt wird durch den Ausdruck angegeben:

d(p,N)=(1(12)1N)1p

Wenn N=1 , zerfällt die Formel auf den halben Radius des Balls, und ich kann sehen, wie sich der nächstgelegene Punkt der Grenze als nähert p, wodurch die Intuition hinter knn in hohen Dimensionen zusammenbricht. Aber ich kann nicht verstehen, warum die Formel von N abhängt. Könnte jemand bitte klarstellen?

Das Buch geht auch weiter auf dieses Problem ein, indem es erklärt: "... die Vorhersage ist in der Nähe der Ränder der Trainingsprobe viel schwieriger. Man muss von benachbarten Probenpunkten extrapolieren, anstatt zwischen ihnen zu interpolieren." Dies scheint eine tiefgreifende Aussage zu sein, aber ich kann nicht verstehen, was es bedeutet. Könnte jemand umformulieren?

user64773
quelle
1
Sie müssen Ihre angezeigte Gleichung ein wenig bearbeiten. Ist das Exponent gilt nur für diese1im Zähler, so wie er jetzt aussieht, oder wollten Sie, dass er für die gesamte1 gilt1N1 ? 12
Dilip Sarwate
1
Es würde helfen, die "Hypersphäre" (die in eine Mannigfaltigkeit der Dimension p - 1 ist ) von der "Einheitskugel" (die die Dimension p hat ) zu unterscheiden. Die Hypersphäre ist die Grenze des Balls. Wenn, wie Ihr Titel sagt, alle Punkte aus der Hypersphäre abgetastet werden , haben sie per Definition alle den Abstand 1 vom Ursprung, der mittlere Abstand 1 und alle sind gleich nahe am Ursprung. Rpp1p11
whuber
@DilipSarwate Wird auf die gesamte 1 angewendet . In dem Buch gibt es ein Beispiel, in demN=500,p=10,alsod(p,N)0,5212N=500,p=10d(p,N)0.52
user64773

Antworten:

8

Das Volumen eines dimensionalen Hyperballs mit dem Radius r hat ein Volumen proportional zu r p .prrp

Der Anteil des Volumens, der größer als ein Abstand vom Ursprung ist, ist also r p - ( k r ) pkr.rp(kr)prp=1kp

Die Wahrscheinlichkeit , dass alle zufällig ausgewählte Punkte sind mehr als ein Abstand k r vom Ursprung ( 1 - k p ) N . Um den Medianabstand zum nächsten zufälligen Punkt zu erhalten, setzen Sie diese Wahrscheinlichkeit auf 1Nkr(1kp)N . Also(1-kp)N=112

(1kp)N=12
k=(1121/N)1/p.

Intuitiv macht dies Sinn: Je mehr zufällige Punkte vorhanden sind, desto näher erwarten Sie, dass der Punkt dem Ursprung am nächsten liegt. Sie sollten also erwarten, dass eine abnehmende Funktion von N ist . Hier ist 2 1 / N eine abnehmende Funktion von N , also 1kN21/NN ist eine zunehmende Funktion vonNund damit1-1121/NN ist eine abnehmende Funktion vonN,ebenso wie seinep-te Wurzel.1121/NNp

Henry
quelle
Ah, schöne Sichtweise. Könnten Sie das Zitat in meiner zweiten Frage neu interpretieren?
user64773
Ich vermute, es könnte darauf hindeuten, dass in hohen Dimensionen zu prognostizierende Punkte tatsächlich weit von den Trainingsdaten entfernt sind, als ob sie sich am Rand einer Kugel befinden. Sie interpolieren also nicht wirklich, sondern extrapolieren, und die Unsicherheiten sind viel größer. Aber ich weiß es nicht wirklich.
Henry
Ich verstehe es nicht - ich verstehe, warum dieser Ausdruck die Wahrscheinlichkeit ist, dass alle Punkte weiter als kr sind, aber warum ergibt das Setzen dieser Wahrscheinlichkeit auf 1/2 den Medianabstand?
Ihadanny
1
@ihadanny: der Wert gibt den Bruchteil des Radius an, bei dem die Wahrscheinlichkeit, dass alleNPunkte weiter entfernt sind,1beträgtk=(1121/N)1/pN , und wenn die Wahrscheinlichkeit, dass mindestens ein Punkt näher liegt,1-1beträgt12 , also istkrder Median der Verteilung der Entfernung des nächsten Punktes. 112=12kr
Henry
Definition des Medians, die Hälfte ist größer und die Hälfte ist kleiner.
Grant Izmirlian
1

Und jetzt ohne Handbewegung

  1. Für jede Folge von iid rvs ist wobei F die gemeinsame CDF ist

    P(min1iNYi>y)=(1F(y))N,
    F
  2. Wenn also iid X i in der Einheitskugel in p- Dimensionen gleichmäßig verteilt hat , dann ist P ( min 1 i N | | X i | | > r ) = ( 1 - F ( r ) ) N , wobei F ist die gemeinsame CDF der Entfernungen, | | X i | | , i = 1 , 2 ,NXip

    P(min1iN||Xi||>r)=(1F(r))N,
    F . Was ist schließlich die CDF F für einen gleichmäßig verteilten Punkt in der Einheitskugel in R p ? Die Wahrscheinlichkeit, dass der Punkt in der Kugel mit dem Radius r innerhalb der Kugel mit dem Einheitsradius liegt, entspricht dem Volumenverhältnis:||Xi||,i=1,2,,NFRp

F(r)=P(||Xi||r)=Crp/(C1p)=rp

Also die Lösung zu

1/2=P(min1iN||Xi||>r)=(1rp)N

ist

r=(1(1/2)1/N)1/p.

Np

kRp

Grant Izmirlian
quelle
0

So prägnant aber in Worten:

NprNthrrrrp. Wir können jetzt Ausdruck [1] als schreiben

P(min1iN||Xi||>r)=(1rp)N.

1/2r

Grant Izmirlian
quelle