A maldição da dimensionalidade do aprendizado de máquina é explicada?

Estou tendo problemas para entender a maldição da dimensionalidade. Especificamente, me deparei com ele durante o scikit-learntutorial em python. Alguém pode explicar o abaixo de uma maneira mais simples? Desculpe, estou tentando entender há mais tempo e não consigo entender como eles criaram o cálculo para o número de exemplos de treinamento para obter um estimador KNN eficiente?

Aqui está a explicação:

Para que um estimador seja eficaz, você precisa que a distância entre os pontos vizinhos seja menor que algum valor d, que depende do problema. Em uma dimensão, isso requer em média n ~ 1 / d pontos. No contexto do exemplo KNN acima, se os dados forem descritos por apenas um recurso com valores variando de 0 a 1 e com n observações de treinamento, os novos dados não estarão mais longe do que 1 / n. Portanto, a regra de decisão do vizinho mais próximo será eficiente assim que 1 / n for pequeno em comparação com a escala de variações de recursos entre classes.

Se o número de recursos for p, agora você precisará de n ~ 1 / d ^ p pontos. Digamos que exigimos 10 pontos em uma dimensão: agora são necessários 10 pontos p em dimensões p para pavimentar o espaço [0, 1]. À medida que p se torna grande, o número de pontos de treinamento necessários para um bom estimador cresce exponencialmente.

link aqui

EDIT: também é o til ( ~) suposto representar aproximado nesse exemplo? ou o operador python til?

Traduzindo esse parágrafo:

Que haja um conjunto de recursos que descrevam um ponto de dados. Talvez você esteja olhando o tempo. Esse conjunto de recursos pode incluir itens como temperatura, umidade, hora do dia etc. Assim, cada ponto de dados pode ter um recurso (se você estiver olhando apenas para a temperatura) ou pode ter dois recursos (se você estiver olhando para a temperatura umidade) e assim por diante. O que este parágrafo está dizendo é que, com base no número de dimensões que seus dados possuem (quantos recursos possui), mais difícil é fazer um estimador. Isso ocorre porque, se você simplesmente possui um recurso de dados, ou dados unidimensionais, quando você grava esses dados, obtém um gráfico de linhas e imagina um gráfico de linhas entre, digamos, 0-50 graus C, são necessários apenas 50 pontos aleatórios antes de cada ponto de dados estão a cerca de 1 grau de qualquer outro ponto de dados. Agora deixe' s pensamos em duas dimensões, falando sobre umidade e temperatura, agora é mais difícil descobrir que d seja tal que todos os pontos estejam dentro das unidades "d" uma da outra. Imagine que a temperatura ainda esteja entre 0 e 50, mas agora a umidade também está entre 0 e 100%. Quantos pontos aleatórios são necessários para obter todos os pontos dentro de 1 ou 2 um do outro? Agora é 100 * 50 ou ~ 5.000! Agora imagine 3 dimensões, etc. Você começa a precisar de mais pontos para garantir que cada ponto esteja dentro de d de algum outro ponto. Para facilitar sua vida, tente assumir que "d" é 1 e veja o que acontece. Espero que ajude! Quantos pontos aleatórios são necessários para obter todos os pontos dentro de 1 ou 2 um do outro? Agora é 100 * 50 ou ~ 5.000! Agora imagine 3 dimensões, etc. Você começa a precisar de mais pontos para garantir que cada ponto esteja dentro de d de algum outro ponto. Para facilitar sua vida, tente assumir que "d" é 1 e veja o que acontece. Espero que ajude! Quantos pontos aleatórios são necessários para obter todos os pontos dentro de 1 ou 2 um do outro? Agora é 100 * 50 ou ~ 5.000! Agora imagine 3 dimensões, etc. Você começa a precisar de mais pontos para garantir que cada ponto esteja dentro de d de algum outro ponto. Para facilitar sua vida, tente assumir que "d" é 1 e veja o que acontece. Espero que ajude!

matty-d já forneceu uma resposta muito boa, mas encontrei outra resposta que explica esse problema igualmente, de um usuário do Quora Kevin Lacker:

Digamos que você tenha uma linha reta de 100 metros de comprimento e deixou cair um centavo em algum lugar nela. Não seria muito difícil de encontrar. Você caminha ao longo da linha e leva dois minutos.

Agora, digamos que você tenha um quadrado de 100 metros de cada lado e você deixou cair um centavo em algum lugar nele. Seria muito difícil, como procurar em dois campos de futebol juntos. Pode levar dias.

Agora, um cubo de 100 metros de diâmetro. É como procurar em um prédio de 30 andares do tamanho de um estádio de futebol. Ugh.

A dificuldade de pesquisar pelo espaço fica muito mais difícil à medida que você tem mais dimensões. Você pode não perceber isso intuitivamente quando é apenas indicado em fórmulas matemáticas, pois todas elas têm a mesma "largura". Essa é a maldição da dimensionalidade. Ele começa a ter um nome porque não é intuitivo, útil e, no entanto, simples.

Esse exemplo pode fornecer alguma intuição do problema, mas na verdade não é uma prova rigorosa: é apenas um exemplo em que muitas amostras são necessárias para obter uma "boa" cobertura espacial. Poderia haver (e de fato, por exemplo, hexágonos em 2D já) coberturas muito mais eficientes do que uma grade regular ... (a área sofisticada de sequências de baixa discrepância é dedicada a isso) ... e provar que mesmo com coberturas tão melhores ainda há alguma maldição da dimensionalidade é outra questão. Na verdade, em certos espaços funcionais, existem maneiras de contornar esse aparente problema.