A maldição da dimensionalidade afeta alguns modelos mais do que outros?

15

Os lugares que eu tenho lido sobre a maldição da dimensionalidade explicam isso em conjunto com o kNN principalmente, e com os modelos lineares em geral. Eu vejo regularmente os principais executivos do Kaggle usando milhares de recursos no conjunto de dados que dificilmente tem 100 mil pontos de dados. Eles usam principalmente árvores reforçadas e NN, entre outros. Muitos recursos parecem altos demais e eu sinto que eles seriam afetados pela maldição da dimensionalidade. Mas isso não parece ser o caso, pois esses modelos os colocam no topo das competições. Então, voltando à minha pergunta original - alguns modelos são afetados pela dimensionalidade amaldiçoam mais do que outros?

Especificamente, estou interessado nos seguintes modelos (apenas porque estes são os que eu conheço / usei):

  • Regressão linear e logística
  • Árvores de Decisão / RandomForest / Árvores Impulsionadas
  • Redes neurais
  • SVM
  • kNN
  • clustering k-means
neural-networks svm k-means k-nearest-neighbour high-dimensional Dileep Kumar Patchigolla
fonte
A resposta curta é definitivamente sim, mas talvez você queira modelos nos quais realmente esteja interessado? Tenho certeza de que a comunidade CV poderia falar sobre milhares de tipos diferentes de modelos que são afetados pela maldição da dimensionalidade. Portanto, restringir seu foco a certos tipos de modelos pode ajudar a responder a essa pergunta.
@RustyStatistician - Adicionei alguns modelos nos quais estou interessado.
Dileep Kumar Patchigolla
Estou bastante interessado nesta questão, mas ela permaneceu sem resposta. Como posso trazer isso à tona para obter respostas?
Dileep Kumar Patchigolla

Respostas:

16

Em geral, a maldição da dimensionalidade dificulta muito o problema de pesquisar em um espaço e afeta a maioria dos algoritmos que "aprendem" ao particionar seu espaço vetorial. Quanto maior a dimensionalidade do nosso problema de otimização, mais dados precisamos para preencher o espaço que estamos otimizando.

Modelos lineares generalizados

Os modelos lineares sofrem imensamente com a maldição da dimensionalidade. Os modelos lineares dividem o espaço em um único plano linear. Mesmo se não estivermos procurando calcular diretamente

β^=(X′X)-1X′y
o problema colocado ainda é muito sensível à colinearidade e pode ser considerado "mal condicionado" sem algum tipo de regularização. Em espaços dimensionais muito altos, há mais de um plano que pode ser ajustado aos seus dados e, sem o tipo adequado de regularização, o modelo pode se comportar muito mal. Especificamente, o que a regularização faz é tentar forçar a existência de uma solução única. A regularização L1 e L2 ao quadrado tentam minimizar os pesos e podem ser interpretadas selecionando o modelo com os menores pesos para ser o modelo mais "correto". Isso pode ser pensado como uma formulação matemática do Occams Razor.

Árvores de
decisão As árvores de decisão também sofrem com a maldição da dimensionalidade. As árvores de decisão particionam diretamente o espaço de amostra em cada nó. À medida que o espaço da amostra aumenta, as distâncias entre os pontos de dados aumentam, o que torna muito mais difícil encontrar uma divisão "boa".

Florestas
aleatórias As florestas aleatórias usam uma coleção de árvores de decisão para fazer suas previsões. Mas, em vez de usar todos os recursos do seu problema, as árvores individuais usam apenas um subconjunto dos recursos. Isso minimiza o espaço que cada árvore está otimizando e pode ajudar a combater o problema da maldição da dimensionalidade.

Os
algoritmos de Boosting Tree , como o AdaBoost, sofrem com a maldição da dimensionalidade e tendem a se exceder se a regularização não for utilizada. Não vou me aprofundar, porque o post AdaBoost é menos ou mais propenso a sobreajuste? explica a razão pela qual melhor do que eu poderia.

Redes neurais
As redes neurais são estranhas no sentido de que ambas são e não são impactadas pela maldição da dimensionalidade dependente da arquitetura, ativações, profundidade etc. Portanto, reiterar a maldição da dimensionalidade é o problema que uma grande quantidade de pontos é necessária em alta dimensões para cobrir um espaço de entrada. Uma maneira de interpretar redes neurais profundas é pensar em todas as camadas que esperam que a última camada faça uma projeção complicada de um coletor de alta dimensão em um coletor de dimensão mais baixa, onde a última camada será classificada em cima. Assim, por exemplo, em uma rede convolucional de classificação onde a última camada é uma camada softmax, podemos interpretar a arquitetura como fazendo uma projeção não linear em uma dimensão menor e, em seguida, fazendo uma regressão logística multinomial (a camada softmax) nessa projeção. Portanto, de certa forma, a representação compactada de nossos dados nos permite contornar a maldição da dimensionalidade. Novamente, essa é uma interpretação: na realidade, a maldição da dimensionalidade afeta as redes neurais, mas não no mesmo nível dos modelos descritos acima.

SVM
SVM tendem a não exagerar tanto quanto os modelos lineares generalizados devido à excessiva regularização que ocorre. Confira este post SVM, Overfitting, maldição da dimensionalidade para obter mais detalhes.

K-NN, K-Means

Tanto K-mean quanto K-NN são grandemente impactados pela maldição da dimensionalidade, uma vez que ambos usam a medida da distância ao quadrado L2. À medida que a quantidade de dimensões aumenta, a distância entre vários pontos de dados também aumenta. É por isso que você precisa de uma quantidade maior de pontos para cobrir mais espaço, na esperança de que a distância seja mais descritiva.

Fique à vontade para perguntar detalhes sobre os modelos, pois minhas respostas são bem gerais. Espero que isto ajude.

Armen Aghajanyan
fonte
Olá Amém. Grandes explicações sucintas para todos os modelos que pedi. Problemas com modelos lineares ainda não estão claros para mim: os modelos lineares têm desempenho melhor ou pior que os modelos k-NN e k-Means para o mesmo número de dimensões? E quando você disse que a colinearidade é um problema para modelos lineares, você implica que, sem nenhuma (ou mínima) colinearidade, as altas dimensões não são um problema para os modelos lineares?
Dileep Kumar Patchigolla
É difícil quantificar se os modelos lineares terão um desempenho melhor do que k-nn ou k-médias para um problema arbitrário. Se o seu problema é linearmente separável, eu colocaria minhas apostas no modelo linear, enquanto se o seu espaço for um pouco mais complicado, eu usaria o k-nn. A colinearidade piora o problema da maldição da dimensionalidade, mesmo sem colinearidade, a maldição da dimensionalidade ainda se aplica. Os meios K devem sofrer na mesma extensão que k-nn, pois ambos são acionados por vizinhos e geralmente usam a mesma função de distância. Na realidade, é difícil quantificar quão ruim é o COD. Espero que isto ajude!
Armen Aghajanyan
Qual é a sua definição de maldição da dimensionalidade (CoD)? Sua resposta parece sugerir que os modelos lineares sofrem mais com o CoD, isso é enganoso: sendo um método global, os modelos lineares sofrem muito menos do que os métodos localizados, como o KNN.
Matifou 24/02/19