Wyjaśnienie wzoru na medianę najbliższego punktu początkowego N próbek z kuli jednostkowej

W Elements of Statistics Learning wprowadzono problem podkreślenia problemów z k-nn w przestrzeniach o dużych wymiarach. Istnieje punktów danych, które są równomiernie rozmieszczone w kuli jednostkowej wymiarowej. $N$ $p$

Mediana odległości od początku do najbliższego punktu danych jest wyrażona przez wyrażenie:

d (p, N) = {(1 - {(\frac{1}{2})}^{\frac{1}{N}})}^{\frac{1}{p}}

$d(p,N) = \left(1-\left(\frac{1}{2}\right)^\frac{1}{N}\right)^\frac{1}{p}$

Gdy , formuła rozkłada się do połowy promienia kuli i widzę, jak najbliższy punkt zbliża się do granicy jako , co powoduje, że intuicja za knn rozpada się w dużych wymiarach. Ale nie rozumiem, dlaczego formuła jest zależna od N. Czy ktoś mógłby wyjaśnić? $N=1$ $p \rightarrow \infty$

Również książka rozwiązuje ten problem dalej, stwierdzając: „... przewidywanie jest znacznie trudniejsze w pobliżu krawędzi próbki treningowej. Trzeba ekstrapolować z sąsiednich punktów próbki, a nie interpolować między nimi”. To wydaje się głębokim stwierdzeniem, ale nie mogę zrozumieć, co to znaczy. Czy ktoś mógłby przeredagować?

self-study proof k-nearest-neighbour

— użytkownik64773
źródło

Musisz trochę edytować wyświetlane równanie. Czy ten wykładnik ma zastosowanie tylko do tego w liczniku tak, jak wygląda teraz, czy też chciałbyś, aby dotyczył całego ?

\frac{1}{N}

$\frac 1N$

1

$1$

\frac{1}{2}

$\frac 12$

— Dilip Sarwate

Pomogłoby to odróżnić „hipersferę” (która w jest kolektorem wymiaru ) od „kuli jednostkowej” (która ma wymiar ). Hipersfera jest granicą piłki. Jeśli, jak mówi twój tytuł, wszystkie punkty są próbkowane z hipersfery , wówczas - z definicji - wszystkie mają odległość od początku, mediana odległości wynosi i wszystkie są jednakowo blisko początku.

R^{p}

$\mathbb{R}^p$

p - 1

$p-1$

p

$p$

1

$1$

1

$1$

— whuber

@DilipSarwate Jest stosowany do całego . W książce jest przykład, w którym więc

\frac{1}{2}

$\frac{1}{2}$

N = 500, p = 10

$N=500, p=10$

d (p, N) \approx 0.52

$d(p, N) \approx 0.52$

— 64773

Odpowiedzi:

Objętość hiperfery wymiarowej o promieniu ma objętość proporcjonalną do . $p$ $r$ $r^p$

Tak więc proporcja objętości większej niż odległość od początku wynosi $kr$ . $\frac{r^p-(kr)^p}{r^p}=1-k^p$

Prawdopodobieństwo, że wszystkie losowo wybrane punkty są na odległość większą niż z pochodzenia . Aby uzyskać medianę odległości do najbliższego losowego punktu, ustaw to prawdopodobieństwo na $N$ $kr$ $\left(1-k^p\right)^N$ . Tak więc $\frac12$

{(1 - k^{p})}^{N} = \frac{1}{2}

$\left(1-k^p\right)^N=\tfrac12$

⟹ k = {(1 - \frac{1}{2^{1 / N}})}^{1 / p} .

$\implies k=\left(1-\tfrac1{2^{1/N}}\right)^{1/p}.$

Intuicyjnie ma to pewien sens: im więcej jest losowych punktów, tym bliżej spodziewasz się punktu początkowego, więc powinieneś spodziewać się, że $k$ będzie funkcją malejącą . Tutaj jest funkcją malejącą , więc $N$ $2^{1/N}$ $N$ jest rosnącą funkcją, a zatem $\tfrac1{2^{1/N}}$ $N$ jest malejącą funkcjąpodobnie jak jegoty pierwiastek. $1-\tfrac1{2^{1/N}}$ $N$ $p$

— Henz
źródło

Ach, fajny sposób na to spojrzeć. Czy byłbyś w stanie ponownie zinterpretować cytat w moim drugim pytaniu?

— user64773

Podejrzewam, że może to sugerować, że w dużych wymiarach punkty do przewidzenia znajdują się w znacznej odległości od danych treningowych, jak na krawędzi kuli, więc tak naprawdę nie interpolujesz, ale raczej ekstrapolujesz, a więc niepewności są znacznie większe. Ale tak naprawdę nie wiem.

— Henry

Nie rozumiem - rozumiem, dlaczego to wyrażenie jest prawdopodobieństwem, że wszystkie punkty są dalej niż kr, ale dlaczego ustawienie tego prawdopodobieństwa na 1/2 daje medianę odległości?

— ihadanny,

@ihadanny: wartość

daje ułamek promienia, w którym prawdopodobieństwo, że wszystkie

punkty są dalej, wynosi

k = {(1 - \frac{1}{2^{1 / N}})}^{1 / p}

$k=\left(1-\tfrac1{2^{1/N}}\right)^{1/p}$

N

$N$

, a więc tam, gdzie prawdopodobieństwo co najmniej jednego punktu jest bliższe, wynosi

\frac{1}{2}

$\frac12$

, więc

jest medianą rozkładu odległości najbliższego punktu.

1 - \frac{1}{2} = \frac{1}{2}

$1-\frac12=\frac12$

k r

$kr$

— Henry,

Definicja mediany, połowa jest większa, a połowa mniejsza.

— Grant Izmirlian,

A teraz bez machania ręką

Dla dowolnej sekwencji iid rv, gdzie jest wspólnym CDF
$P (min_{1 \leq i \leq N} Y_{i} > y) = (1 - F (y))^{N},$ $P( \min_{1\le i\le N} Y_i > y ) = (1-F(y))^N,$ $F$
$N$ $X_i$ $p$
$P (min_{1 \leq i \leq N} | | X_{i} | | > r) = (1 - F (r))^{N},$ $P( \min_{1\le i\le N} ||X_i|| > r ) = (1-F(r))^N,$ $F$ $||X_i||, i=1,2,\ldots,N$ $F$ $R^p$

F (r) = P (| | X_{i} | | \leq r) = C r^{p} / (C 1^{p}) = r^{p}

$F(r) = P ( ||X_i|| \le r ) = C r^p/( C 1^p) = r^p$

Tak więc rozwiązanie

1 / 2 = P (min_{1 \leq i \leq N} | | X_{i} | | > r) = (1 - r^{p})^{N}

$1/2 = P( \min_{1\le i\le N} ||X_i|| > r ) = (1- r^p)^N$

jest

r = (1 - (1 / 2)^{1 / N})^{1 / p} .

$r = (1 - (1/2)^{1/N})^{1/p}.$

$N$ $p$

$k$ $R^p$

— Grant Izmirlian
źródło

Jak zwięzłe, ale słownie:

$N$ $p$ $r$ $N^{th}$ $r$ $r$ $r$ $r^p$ . Możemy teraz zapisać wyrażenie [1] jako

P (min_{1 \leq i \leq N} | | X_{i} | | > r) = (1 - r^{p})^{N} .

$P( \min_{1\le i\le N} ||X_i|| > r ) = (1- r^p)^N.$

$1/2$ $r$

— Grant Izmirlian
źródło