Explicação da fórmula para o ponto mais próximo mediano da origem das amostras N da bola unitária

Em Elements of Statistical Learning , um problema é introduzido para destacar problemas com k-nn em espaços de alta dimensão. Existem pontos de dados que são distribuídos uniformemente em uma esfera unitária dimensional. $N$ $p$

A distância média da origem ao ponto de dados mais próximo é dada pela expressão:

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}$

Quando , a fórmula se divide em metade do raio da bola, e posso ver como o ponto mais próximo se aproxima da borda como , fazendo com que a intuição por trás do knn se quebre em grandes dimensões. Mas não consigo entender por que a fórmula depende de N. Alguém poderia esclarecer? $N=1$ $p \rightarrow \infty$

Além disso, o livro aborda essa questão ainda mais afirmando: "... a previsão é muito mais difícil perto das bordas da amostra de treinamento. É preciso extrapolar dos pontos de amostra vizinhos em vez de interpolar entre eles". Parece uma afirmação profunda, mas não consigo entender o que isso significa. Alguém poderia reformular?

self-study proof k-nearest-neighbour user64773
fonte

Você precisa editar um pouco a equação exibida. O expoente aplicável apenas a esse no numerador da forma como está agora ou você deseja que ele se aplique a todo ?

\frac{1}{N}

$\frac 1N$

1

$1$

\frac{1}{2}

$\frac 12$

precisa saber é o seguinte

Ajudaria a distinguir a "hiperesfera" (que em é uma variedade de dimensão ) da "bola unitária" (que tem dimensão ). A hiperesfera é o limite da bola. Se, como o seu título diz, todos os pontos são amostrados da hiperesfera , então - por definição - todos eles têm a distância da origem, a distância média é e todos estão igualmente próximos da origem.

R^{p}

$\mathbb{R}^p$

p - 1

$p-1$

p

$p$

1

$1$

1

$1$

whuber

@DilipSarwate É aplicado a todo o . No livro não é um exemplo em que assim

\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$

user64773

Respostas:

O volume de uma hiperbola dimensional do raio tem um volume proporcional a . $p$ $r$ $r^p$

Portanto, a proporção do volume a mais de uma distância da origem é . $kr$ $\frac{r^p-(kr)^p}{r^p}=1-k^p$

A probabilidade de que todos os pontos escolhidos aleatoriamente são mais do que uma distância a partir da origem é . Para obter a distância mediana para o ponto aleatório mais próximo, defina essa probabilidade igual a . Então $N$ $kr$ $\left(1-k^p\right)^N$ $\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}.$

Intuitivamente isto faz algum sentido: os pontos mais aleatórias existem, o mais perto que você espera a mais próxima à origem para ser, então você deve esperar ser uma função decrescente do . Aqui é uma função decrescente de , então é uma função crescente de e, portanto, é uma diminuição da função de como é o seu th raiz. $k$ $N$ $2^{1/N}$ $N$ $\tfrac1{2^{1/N}}$ $N$ $1-\tfrac1{2^{1/N}}$ $N$ $p$

Henry
fonte

Ah, boa maneira de ver. Você poderia reinterpretar a citação na minha segunda pergunta?

user64773

Suspeito que possa estar sugerindo que, em grandes dimensões, os pontos a prever estão efetivamente muito longe dos dados de treinamento, como se estivessem no limite de uma esfera, para que você não esteja realmente interpolando, mas extrapolando, e as incertezas são muito maiores. Mas eu realmente não sei.

Henry

Eu não entendo - eu entendo por que essa expressão é a probabilidade de todos os pontos serem maiores que kr, mas por que definir essa probabilidade como 1/2 dá a distância média?

ihadanny

@ihadanny: o valor fornece a fração do raio em que a probabilidade de todos os pontos estarem mais longe é e, onde a probabilidade de pelo menos um ponto estar mais próxima é , então é a mediana da distribuição da distância do ponto mais próximo.

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

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

N

$N$

\frac{1}{2}

$\frac12$

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

$1-\frac12=\frac12$

k r

$kr$

Henry

Definição de mediana, metade é maior e metade é menor.

Grant Izmirlian

E agora sem a mão acenando

Para qualquer sequência de IDs, onde é o CDF comum
$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$
Portanto, se tivermos iid distribuído uniformemente na esfera unitária em dimensões, então em que é a CDF comum das distâncias, . Finalmente, qual é o CDF, , para um ponto uniformemente distribuído na bola unitária em ? A probabilidade de que o ponto esteja na bola de raio r dentro da bola de raio unitário é igual à razão de volumes: $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$

Assim, a solução para

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$

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

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

Também sua pergunta sobre a dependência do tamanho da amostra, . Para fixo, à medida que a bola se enche de mais pontos, naturalmente a distância mínima à origem deve se tornar menor. $N$ $p$

Finalmente, há algo errado na sua proporção de volumes. Parece que deve ser o volume da bola unitária em . $k$ $R^p$

Grant Izmirlian
fonte

Como conciso, mas em palavras:

Queremos encontrar a distância média do ponto mais próximo da origem em pontos uniformemente distribuídos na bola na origem do raio unitário nas dimensões . A probabilidade de que a menor distância excede , (chamar esta expressão quantidade [1]) é o poder da probabilidade de que um único ponto uniformemente distribuído excede , por causa da independência estatística. O último é um menos a probabilidade de que um único ponto uniformemente distribuído seja menor que . Este último é a razão entre os volumes da bola de raio e a bola de raio unitário, ou . Agora podemos escrever a expressão [1] como $N$ $p$ $r$ $N^{th}$ $r$ $r$ $r$ $r^p$

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.$

Para encontrar a mediana da distribuição do mínimo das distâncias, defina a probabilidade acima como e resolva para , obtendo a resposta. $1/2$ $r$

Grant Izmirlian
fonte