Explication de la formule du point médian le plus proche de l'origine des N échantillons de l'unité de balle

11

Dans Elements of Statistical Learning , un problème est introduit pour mettre en évidence les problèmes de k-nn dans les espaces de grande dimension. Il y a N points de données qui sont uniformément distribués dans une boule d'unité p dimensionnelle.

La distance médiane de l'origine au point de données le plus proche est donnée par l'expression:

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

Lorsque , les pauses de formule vers le bas à la moitié du rayon de la balle, et je peux voir comment le point le plus proche se rapproche de la frontière comme p , rendant ainsi l'intuition derrière KNN briser les dimensions élevées. Mais je ne comprends pas pourquoi la formule dépend de N. Pourriez-vous clarifier quelque chose?N=1p

Le livre aborde également ce problème en déclarant: "... la prédiction est beaucoup plus difficile près des bords de l'échantillon d'apprentissage. Il faut extrapoler à partir des points d'échantillonnage voisins plutôt qu'interpoler entre eux". Cela semble être une déclaration profonde, mais je n'arrive pas à comprendre ce que cela signifie. Quelqu'un pourrait-il reformuler?

user64773
la source
1
Vous devez modifier un peu votre équation affichée. Est-ce que exposant applicable uniquement à ce1dans le numérateurà quoiil ressemble maintenant, ou vouliez-vous qu'il s'applique à l'ensemble11N1 ? 12
Dilip Sarwate
1
Cela aiderait à distinguer l '"hypersphère" (qui dans est une variété de dimension p - 1 ) de la "boule unitaire" (qui a la dimension p ). L'hypersphère est la limite de la balle. Si, comme votre titre l'indique, tous les points sont échantillonnés à partir de l' hypersphère , alors - par définition - ils ont tous la distance 1 de l'origine, la distance médiane est 1 , et tous sont également proches de l'origine. Rpp1p11
whuber
@DilipSarwate Il est appliqué à l'ensemble . Dans le livre, il y a un exemple oùN=500,p=10doncd(p,N)0,5212N=500,p=10d(p,N)0.52
user64773

Réponses:

8

Le volume d'une hyperbille de dimension de rayon r a un volume proportionnel à r p .prrp

Donc, la proportion du volume supérieure à une distance de l'origine est r p - ( k r ) pkr.rp(kr)prp=1kp

La probabilité que tous les points d' choisis au hasard sont plus d'une distance k r de l'origine est ( 1 - k p ) N . Pour obtenir la distance médiane au point aléatoire le plus proche, définissez cette probabilité égale à 1Nkr(1kp)N . Donc(1-kp)N=112

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

kN21/NN121/NN1121/NNp

Henri
la source
Ah, belle façon de voir les choses. Pourriez-vous réinterpréter la citation de ma deuxième question?
user64773
Je soupçonne que cela peut suggérer que dans les dimensions élevées, les points à prédire sont effectivement loin des données d'entraînement, comme s'ils étaient au bord d'une sphère, donc vous n'êtes pas vraiment interpolant mais plutôt extrapolant, et donc les incertitudes sont beaucoup plus grandes. Mais je ne sais pas vraiment.
Henry
Je ne comprends pas - je comprends pourquoi cette expression est la probabilité que tous les points soient plus éloignés que kr, mais pourquoi la définition de cette probabilité à 1/2 donne la distance médiane ??
ihadanny
1
k=(1121/N)1/pN12112=12kr
Définition de la médiane, la moitié est plus grande et la moitié est plus petite.
Grant Izmirlian
1

Et maintenant sans agiter la main

  1. P(min1iNYi>y)=(1F(y))N,
    F
  2. Ainsi, si nous avons iid uniformément distribué dans la boule unitaire en dimensions, alors où est la CDF commune des distances, . Enfin, quel est le CDF, , pour un point uniformément distribué dans la boule unitaire dans ? La probabilité que le point se trouve dans la boule de rayon r à l'intérieur de la boule de rayon unitaire est égale au rapport des volumes:NXip

    P(min1iN||Xi||>r)=(1F(r))N,
    F||Xi||,i=1,2,,NFRp

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

Ainsi, la solution à

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

est

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

De plus , votre question sur la dépendance de la taille de l' échantillon, . Pour fixe, au fur et à mesure que la balle se remplit de plus de points, la distance minimale à l'origine devrait naturellement devenir plus petite.pNp

Enfin, il y a quelque chose qui cloche dans votre rapport de volumes. Il semble que devrait être le volume de la boule unitaire dans .R pkRp

Grant Izmirlian
la source
0

Aussi concis mais en mots:

Nous voulons trouver la distance médiane du point le plus proche de l'origine en points uniformément répartis dans la balle à l'origine du rayon unitaire en dimensions. La probabilité que la plus petite distance dépasse , (appelons cette expression de quantité [1]) est la puissance de la probabilité qu'un seul point uniformément distribué dépasse , en raison de l'indépendance statistique. Ce dernier est un moins la probabilité qu'un seul point uniformément distribué soit inférieur à . Ce dernier est le rapport des volumes de la boule de rayon à la boule de rayon unitaire, ou . Nous pouvons maintenant écrire l'expression [1] commeNprNthrrrrp

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

Pour trouver la médiane de la distribution du minimum des distances, définissez la probabilité ci-dessus à et résolvez pour , en obtenant la réponse.1/2r

Grant Izmirlian
la source