A “maldição da dimensionalidade” realmente existe em dados reais?

17

Entendo o que é "maldição da dimensionalidade", e resolvi alguns problemas de otimização dimensional e conheço o desafio das possibilidades exponenciais.

No entanto, duvido que a "maldição da dimensionalidade" exista na maioria dos dados do mundo real (bem, vamos deixar imagens ou vídeos de lado por um momento, estou pensando em dados como dados demográficos do cliente e dados de comportamento de compra).

Podemos coletar dados com milhares de recursos, mas é menos provável que até mesmo os recursos possam abranger totalmente um espaço com milhares de dimensões. É por isso que as técnicas de redução de dimensão são tão populares.

Em outras palavras, é muito provável que os dados não contenham o nível exponencial de informações, ou seja, muitos recursos são altamente correlacionados e muitos atendem às regras 80-20 (muitas instâncias têm o mesmo valor).

Nesse caso, acho que métodos como o KNN ainda funcionarão razoavelmente bem. (Na maioria dos livros, "maldição da dimensionalidade" diz que a dimensão> 10 pode ser problemática. Em suas demonstrações, eles usam distribuição uniforme em todas as dimensões, onde a entropia é realmente alta. Duvido que no mundo real isso aconteça.)

Minha experiência pessoal com dados reais é que a "maldição da dimensionalidade" não afeta muito o método do modelo (como o KNN) e, na maioria dos casos, as dimensões ~ 100 ainda funcionariam.

Isso é verdade para outras pessoas? (Trabalhei com dados reais em diferentes setores por 5 anos, nunca observei "todos os pares de distâncias têm valores semelhantes", conforme descrito no livro.)

hxd1011
fonte
1
Como você excluiu especificamente imagens e análises de imagens, colocarei um comentário nos comentários dizendo que esse campo lida com a maldição da dimensionalidade regularmente. É muito fácil obter uma solução com excesso de ajuste.
Ashe
7
Binary / manequim / one-quente características categóricas codificados pode facilmente explodir um modelo baseado em distância
shadowtalker
2
Um colega meu trabalhou com a venda de óculos de sol. Um grande número de recursos era categórico com um grande número de níveis possíveis (por exemplo, marcas, materiais de diferentes partes dos óculos, etc.). Eu definitivamente tinha medo do CoD, mas sempre é difícil dizer se ele está presente em um determinado conjunto de dados, e provavelmente não fizemos muitos truques padrão, não sendo especialistas nesse tipo de análise em particular.
S. Kolassa - Restabelece Monica
@StephanKolassa Então, os métodos baseados em distância funcionaram no caso de uso de óculos de sol?
Haitao Du
Não muito bem. Não foi um projeto de muito sucesso.
S. Kolassa - Restabelece Monica

Respostas:

15

Este artigo (1) discute a bênção da não uniformidade como um contraponto à maldição da dimensionalidade. A ideia principal é que os dados não sejam uniformemente dispersos no espaço de recursos, para que você possa ganhar força identificando as maneiras pelas quais os dados são organizados.

(1) Pedro Domingos, "Algumas Coisas Úteis a Saber sobre Aprendizado de Máquina"

Sycorax diz restabelecer Monica
fonte
7

A maldição da dimensionalidade no aprendizado de máquina é mais frequentemente o problema de explodir o espaço vazio entre os poucos pontos de dados que você possui. Dados baixos do coletor podem piorar ainda mais. Aqui está um exemplo de configuração com 10000 amostras em que tento fazer o kNN com 1 vizinho.

from numpy.random import normal
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import precision_score
import matplotlib.pyplot as plt
import numpy as np
from math import sqrt
from scipy.special import gamma

N=10000
N_broad=2
scale=20

dims=[]
precs=[]


def avg_distance(k):
    return sqrt(2)*gamma((k+1)/2)/gamma(k/2)

for dim in range(N_broad+1,30):
    clf = KNeighborsClassifier(1, n_jobs=-1)

    X_train=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_train=(X_train[:,N_broad]>0).astype(int)
    clf.fit(X_train, y_train)

    X_test=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_test=(X_test[:,N_broad]>0).astype(int)
    y_test_pred=clf.predict(X_test)

    prec=precision_score(y_test, y_test_pred)
    dims.append(dim)
    precs.append(prec)
    print(dim, prec)

plt.plot(dims, precs)
plt.ylim([0.5,1])
plt.xlabel("Dimension")
plt.ylabel("Precision")
plt.title("kNN(1) on {} samples".format(N))
plt.show()

Você não gostou de distribuições totalmente uniformes, por isso criei um coletor 2D com dimensões menores (reduzidas scale) espalhadas pelo plano 2D das duas primeiras coordenadas. Por acaso, uma das dimensões menores é preditiva (o rótulo é 1 quando essa dimensão é positiva).

A precisão cai rapidamente com o aumento da dimensão.precisão kNN

Obviamente, precisão = 0,5 seria uma adivinhação aleatória. Com uma superfície de decisão, que é mais complicada do que um avião, ficaria ainda pior.

É como se as bolas de kNN fossem muito escassas para serem úteis na detecção de um hiperplano suave. Com dimensões mais altas, eles se sentem cada vez mais solitários.

Por outro lado, métodos como o SVM têm uma visão global e se saem muito melhor.

Gerenuk
fonte
5

Considere, por exemplo, séries temporais (e imagens e áudio). As leituras dos sensores (Internet das Coisas) são muito comuns.

A maldição da dimensionalidade é muito mais comum do que você pensa. Há uma grande redundância lá, mas também muito barulho.

O problema é que muitas pessoas simplesmente evitam esses desafios de dados reais e usam apenas os mesmos conjuntos de dados UCI extraídos repetidamente.

Anony-Mousse -Reinstate Monica
fonte
P(X)=P(X1)n=2NP(Xn|Xn-1)
1
Talvez a maioria dos dados do mundo real seja proveniente de sensores como imagens, vídeo e séries temporais?
Anony-Mousse - Re: Monica
2
@ hxd1011 A propriedade markov é uma abstração que pode não ter nada a ver com dados reais!
Sycorax diz Reinstate Monica
0

Há um artigo maravilhoso, "Modelagem Estatística: as duas culturas" , de Breiman. Ele explica os dois grupos de cientistas que lidam com dados e como cada um deles vê a "dimensionalidade". A resposta para sua pergunta é "depende" de qual grupo você é. Verifique o papel.

Zamir Akimbekov
fonte
Obrigado @Zamir Akimbekov, há ótimas discussões aqui e outro artigo interessante aqui #
Haitao Du