Maldição da dimensionalidade

A maldição da dimensionalidade refere-se a vários fenômenos que surgem quando estamos lidando com a análise e organização de dados em espaços de alta dimensão, mas que não ocorrem em ambientes de baixa dimensão, como o espaço físico tridimensional que experimentamos no dia a dia. A expressão foi cunhada por Richard E. Bellman ao considerar problemas em programação dinâmica.

Fenômenos dimensionalmente amaldiçoados ocorrem em diversos campos, como análise numérica, amostragem, combinatória, aprendizado de máquina, mineração de dados e bancos de dados. O elemento comum desses problemas é que, quando a dimensão aumenta, o volume do espaço cresce de forma tão acelerada que os dados disponíveis se tornam esparsos. Para obter resultados confiáveis, geralmente é necessário um volume de dados que cresce exponencialmente com o aumento da dimensão. Além disso, a organização e a busca de dados frequentemente dependem da identificação de regiões onde os objetos compartilham propriedades semelhantes; no entanto, em dados de alta dimensão, todos os objetos parecem ser esparsos e diferem em várias maneiras, o tornado as estratégias convencionais de organização de dados ineficazes.

Domínios

Combinatória

Em certos problemas, cada variável pode adotar um de vários valores discretos, ou o conjunto de valores possíveis é dividido em um número limitado de alternativas. Quando essas variáveis são combinadas, deve-se considerar um grande número de combinações de valores, um fenômeno conhecido como "explosão combinatória". Mesmo no caso mais simples de $d$ variáveis binárias, o número de combinações possíveis já é $2^{d}$, exponencial na dimensão. Ingenuamente, cada dimensão adicional dobra o esforço necessário para tentar todas as combinações.

Amostragem

O aumento no volume associado à adição de dimensões adicionais em um espaço matemático é exponencial. Para ilustrar, considere que 10² = 100 pontos de amostragem uniformemente espaçados são suficientes para representar um intervalo unitário (visualize um cubo unidimensional) com uma distância máxima de 10⁻² = 0,01 entre eles; no entanto, uma amostragem equivalente de um hipercubo unitário de 10 dimensões com um reticulado que tem um espaçamento de 10⁻² = 0,01 entre pontos adjacentes, exigiria 10²⁰ = [(10²)¹⁰] pontos de amostragem. Em termos gerais, com um espaçamento de 10⁻ⁿ, o hipercubo de 10 dimensões parece ser um fator de 10^n(10−1) = [(10ⁿ)¹⁰/(10ⁿ)] "maior" que o hipercubo unidimensional, que é o intervalo unitário. No exemplo acima com n = 2: ao usar uma distância de amostragem de 0,01, o hipercubo de 10 dimensões parece ser 10¹⁸ "maior" que o intervalo unitário. Este fenômeno resulta de uma combinação dos desafios combinatórios mencionados anteriormente e os problemas relacionados à função de distância explicados a seguir.

Otimização

Ao abordar problemas de otimização dinâmica por meio da técnica de indução reversa numérica, é necessário calcular a função objetivo para todas as possíveis combinações de valores. Este é um obstáculo significativo quando a dimensão da "variável de estado" é elevada.

Aprendizado de máquina

Em problemas de aprendizado de máquina que envolvem o aprendizado de um "estado da natureza" a partir de um número finito de amostras de dados em um espaço de características de alta dimensão, onde cada característica pode assumir diversos valores, é geralmente necessário uma dispor de uma enorme quantidade de dados de treinamento. Isso garante a presença de diversas amostras abrangendo todas as possíveis combinações de valores. Em um sentido abstrato, à medida que o número de características ou dimensões cresce, a quantidade de dados que precisamos para generalizar com precisão cresce exponencialmente.

Uma regra prática comum é que deve haver pelo menos 5 exemplos de treinamento para cada dimensão na representação. No aprendizado de máquina e no que diz respeito ao desempenho preditivo, a maldição da dimensionalidade é frequentemente usada de forma intercambiável com o fenômeno de pico, também conhecido como o fenômeno de Hughes. Esse fenômeno afirma que, com um dado número de amostras de treinamento, o poder preditivo médio (esperado) de um classificador ou regressor aumenta inicialmente à medida que o número de dimensões ou características utilizadas cresce. No entanto, além de uma certa dimensão, em vez de melhorar continuamente, o desempenho começa a deteriorar.

No entanto, considerando o contexto de um classificador simples (análise discriminante linear no modelo gaussiano multivariado com a suposição de uma matriz de covariância comum conhecida), Zollanvari et al. demonstraram analiticamente e empiricamente que, desde que a eficácia cumulativa relativa de um conjunto de características adicionais (em relação às características que já fazem parte do classificador) seja maior (ou menor) que o tamanho desse conjunto de características adicionais, o erro esperado do classificador construído usando essas características adicionais será menor (ou maior) que o erro esperado do classificador construído sem elas. Em outras palavras, tanto o tamanho das características adicionais quanto seu efeito discriminatório cumulativo (relativo) são importantes para observar uma diminuição ou aumento no poder preditivo médio.

No aprendizado de métrica, dimensões mais altas às vezes podem permitir que um modelo obtenha melhor desempenho. Depois de normalizar as imersões para a superfície de uma hiperesfera, o sistema FaceNet obtém o melhor desempenho usando 128 dimensões, em vez de 64, 256 e 512 dimensões no estudo de ablação dos autores. Verificou-se que uma função de perda para a dissimilaridade invariante unitária entre as imersões de palavras é minimizada em dimensões altas.

Mineração de dados

Conjunto de dados de mutações genéticas em indivíduos

Nome do indivíduo	Gene 1	Gene 2	. . .	gene 2000
Indivíduo 1	1	0	. . .	1
. . .	. . .	. . .	. . .	. . .
Individual 200	0	1	. . .	1

Na mineração de dados, a maldição da dimensionalidade refere-se a um conjunto de dados com um grande número de características.

Considere a primeira tabela, a qual apresenta informações sobre 200 indivíduos e 2.000 genes (características). Os valores 1 ou 0 indicam a presença ou ausência de mutações genéticas naquele gene. Um aplicativo de mineração de dados para esse conjunto de dados pode encontrar a correlação entre mutações genéticas específicas e criar um algoritmo de classificação, como uma árvore de decisão, para determinar se um indivíduo tem câncer ou não.

Crescimento de permutações de pares de associação à medida que o tamanho do par aumenta

Número de pares	Cálculo para permutações	Número de permutações calculadas para cada linha
2	$2000!/(2000-2)!$	7006399800000000000♠3998000
3	$2000!/(2000-3)!$	7009798800400000000♠7988004000
4	$2000!/(2000-4)!$	7013159520439880000♠15952043988000
5	$2000!/(2000-5)!$	7016318402798000480♠31840279800048000

Uma prática comum de mineração de dados neste contexto seria criar regras de associação entre mutações genéticas que levam ao desenvolvimento de cânceres. Para fazer isso, seria necessário percorrer cada mutação genética de cada indivíduo e encontrar outras mutações genéticas que ocorressem além de um limite desejado e criar pares. O procedimento começaria com pares de dois, depois três, depois quatro até resultarem em um conjunto vazio de pares. A complexidade desse algoritmo pode levar ao cálculo de todas as permutações de pares de genes para cada indivíduo ou linha. Dado que a fórmula para calcular as permutações de n itens com um tamanho de grupo de r é ${\frac {n!}{(n-r)!}}$, calcular o número de permutações de três pares de qualquer indivíduo seria 7988004000 pares diferentes de genes para avaliar para cada indivíduo. O crescimento do número de pares criados é de ordem fatorial à medida que o tamanho dos pares aumenta. O crescimento é representado na tabela de permutação (veja à direita).

Conforme ilustrado na tabela de permutações anterior, um dos principais problemas que os mineradores de dados enfrentam em relação à maldição da dimensionalidade é que o espaço de possíveis valores de parâmetros cresce de forma exponencial ou fatorial à medida que o número de características no conjunto de dados aumenta. Esse problema afeta criticamente o tempo e o espaço computacional ao procurar associações ou características ideais a serem consideradas.

Outro problema que os mineradores de dados podem enfrentar ao lidar com características demais é a noção de que o número de previsões ou classificações falsas tende a aumentar à medida que o número de características no conjunto de dados cresce. Em termos do problema de classificação discutido acima, manter todos os pontos de dados pode levar o modelo a ter um número maior de falsos positivos e falsos negativos.

Isso pode parecer contra-intuitivo, mas considere a tabela de mutações genéticas acima, descrevendo todas as mutações genéticas para cada indivíduo. Cada mutação genética, correlacionada com câncer ou não, terá algum input ou peso no modelo que orienta o processo de tomada de decisão do algoritmo. Pode haver mutações que são atípicas ou que dominam a distribuição geral de mutações genéticas quando, na verdade, não se correlacionam com o câncer. Essas características podem trabalhar contra um modelo, dificultando a obtenção de resultados ótimos.

A resolução desse problema cabe ao minerador e não há uma solução universal. O primeiro passo que qualquer minerador de dados deve dar é explorar os dados, na tentativa de entender como eles podem ser usados para resolver o problema. É preciso primeiro entender o que os dados significam e o que se está tentando descobrir antes de decidir se algo deve ser removido do conjunto de dados. Em seguida, pode-se criar ou usar uma seleção de características ou algoritmo de redução de dimensionalidade para remover amostras ou características do conjunto de dados, se for necessário. Um exemplo de tais métodos é o método de amplitude interquantil, usado para remover valores atípicos em um conjunto de dados calculando o desvio padrão de uma característica ou ocorrência.

Função de distância

Quando uma medida como a distância euclidiana é definida usando muitas coordenadas, há pouca diferença nas distâncias entre diferentes pares de pontos.

Uma maneira de ilustrar a "vastidão" do espaço euclidiano de alta dimensão é comparar a proporção de uma hiperesfera inscrita com o raio $r$ e dimensão $d$, em um hipercubo com arestas de comprimento $2r.$ O volume dessa esfera é ${\frac {2r^{d}\pi ^{d/2}}{d\;\Gamma (d/2)}}$, em que $\Gamma$ é a função gama, enquanto o volume do cubo é $(2r)^{d}$. Conforme a dimensão $d$ do espaço aumenta, a hiperesfera torna-se um volume insignificante em relação ao do hipercubo. Isso pode ser visto claramente calculando a proporção ao fazer a dimensão $d$ tender ao infinito:

${\frac {V_{\mathrm {hiperesfera} }}{V_{\mathrm {hipercubo} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0$ quando $d\rightarrow \infty$.

Além disso, a distância entre o centro e os cantos é $r{\sqrt {d}}$, que aumenta arbitrariamente para um r fixo. Nesse sentido, quando os pontos são gerados uniformemente em um hipercubo de alta dimensão, quase todos os pontos estão há muito mais do que $r$ unidades de distância do centro. Em altas dimensões, o volume do hipercubo d-dimensional unitário (cujas coordenadas dos vértices são $\pm 1$) está concentrado perto de uma esfera com o raio ${\sqrt {d}}/{\sqrt {3}}$ para altas dimensões d. De fato, para cada coordenada $x_{i}$ o valor médio de $x_{i}^{2}$ no cubo é

$\left\langle x_{i}^{2}\right\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1}{3}}$ .

A variância de $x_{i}^{2}$ para uma distribuição uniforme no cubo é

${\frac {1}{2}}\int _{-1}^{1}x^{4}dx-\left\langle x_{i}^{2}\right\rangle ^{2}={\frac {4}{45}}$

Portanto, o quadrado da distância da origem, ${\textstyle r^{2}=\sum _{i}x_{i}^{2}}$, tem o valor médio d/3 e variância 4d/45. Para d grande, a distribuição de $r^{2}/d$ está próxima da distribuição normal com média 1/3 e desvio padrão $2/{\sqrt {45d}}$ de acordo com o teorema do limite central. Assim, ao gerar uniformemente pontos em altas dimensões, tanto o "meio" do hipercubo quanto os cantos ficam vazios, e todo o volume concentra-se próximo à superfície de uma esfera de raio "intermediário" ${\textstyle {\sqrt {d/3}}}$.

Isso também ajuda a entender a distribuição qui-quadrado. De fato, a distribuição qui-quadrado (não central) associada a um ponto aleatório no intervalo [-1, 1] é a mesma que a distribuição do quadrado do comprimento de um ponto aleatório no d-cubo. Pela lei dos grandes números, essa distribuição se concentra em uma faixa estreita em torno de d vezes o desvio padrão ao quadrado (σ²) do desvio original. Isso ilumina a distribuição qui-quadrado e também ilustra que a maior parte do volume do d-cubo se concentra próximo da fronteira de uma esfera de raio $\sigma {\sqrt {d}}$.

Um desenvolvimento adicional desse fenômeno é o seguinte. Qualquer distribuição fixa nos números reais induz uma distribuição produto em pontos de $\mathbb {R} ^{d}$. Para qualquer n fixo, verifica-se que as diferenças entre a distância mínima e máxima entre um ponto de referência aleatório Q e uma lista de n pontos de dados aleatórios P₁, ..., P_n tornam-se indiscerníveis relativamente à distância mínima:

$\lim _{d\to \infty }E\left({\frac {\operatorname {dist} _{\max }(d)-\operatorname {dist} _{\min }(d)}{\operatorname {dist} _{\min }(d)}}\right)\to 0$.

Isso é frequentemente citado dizendo que as funções de distância perdem sua utilidade (para o critério do vizinho mais próximo em algoritmos de comparação de características, por exemplo) em altas dimensões. No entanto, pesquisas recentes mostraram que isso só é válido no cenário artificial quando as distribuições unidimensionais $\mathbb {R}$ são independentes e identicamente distribuídas. Quando os atributos são correlacionados, os dados podem se tornar mais fáceis e fornecer maior contraste de distância e a relação sinal-ruído desempenha um papel importante, portanto, a seleção de características deve ser usada.

Mais recentemente, foi sugerido que pode haver uma falha conceitual no argumento de que a perda de contraste cria uma maldição em altas dimensões. O aprendizado de máquina pode ser entendido como o problema de atribuir instâncias a seus respectivos processos generativos de origem, com rótulos de classe atuando como representações simbólicas de processos generativos individuais. A derivação da maldição assume que todas as instâncias são resultados independentes e idênticos de um único processo generativo de alta dimensão. Se houvesse apenas um processo generativo, existiria apenas uma classe (que ocorre naturalmente) e o aprendizado de máquina seria conceitualmente mal definido tanto em alta quanto em baixa dimensão. Assim, o argumento tradicional de que a perda de contraste cria uma maldição pode ser fundamentalmente inapropriado. Além disso, foi demonstrado que, quando o modelo generativo é modificado para acomodar múltiplos processos generativos, a perda de contraste pode se transformar de uma maldição para uma bênção, pois garante que o vizinho mais próximo de uma instância seja quase certamente a instância a qual está mais relacionada. A partir dessa perspectiva, a perda de contraste torna as distâncias em dimensões altas especialmente significativas em vez de especialmente não significativas, como frequentemente se argumenta.

Busca do vizinho mais próximo

O efeito complica a busca do vizinho mais próximo em um espaço de alta dimensão. Não é possível rejeitar candidatos rapidamente usando a diferença em uma coordenada como um limite inferior para uma distância baseada em todas as dimensões.

No entanto, observou-se recentemente que o mero número de dimensões não resulta necessariamente em dificuldades, uma vez que dimensões adicionais relevantes também podem aumentar o contraste. Além disso, para a classificação resultante, é útil discernir vizinhos próximos e distantes. Dimensões irrelevantes ("ruído"), no entanto, reduzem o contraste da maneira descrita acima. Na análise de séries temporais, onde os dados são inerentemente de alta dimensão, as funções de distância também funcionam de forma confiável, desde que a relação sinal-ruído seja alta o suficiente.

Classificação por k-vizinhos mais próximos

Outro efeito da alta dimensionalidade nas funções de distância diz respeito aos grafos de k-vizinhos mais próximos (k-NN) construídos a partir de um conjunto de dados usando uma função de distância. À medida que a dimensão aumenta, a distribuição do grau de entrada do dígrafo de k-NN torna-se assimétrica com um pico à direita devido ao surgimento de um número desproporcional de hubs, ou seja, pontos de dados que aparecem em muito mais listas de k-NN de outros pontos de dados do que a média. Esse fenômeno pode ter um impacto considerável em várias técnicas de classificação (incluindo o classificador k-NN), aprendizado semissupervisionado e agrupamento, e também afeta a recuperação de informações.

Detecção de anomalias

Em uma pesquisa de 2012, Zimek et al. identificaram os seguintes problemas ao procurar anomalias em dados de alta dimensão:

1. Concentração de pontuações e distâncias: valores derivados, como distâncias, tornam-se numericamente semelhantes
2. Atributos irrelevantes: em dados de alta dimensão, um número significativo de atributos pode ser irrelevante
3. Definição de conjuntos de referência: para métodos locais, os conjuntos de referência geralmente são baseados no vizinho mais próximo
4. Pontuações incomparáveis para diferentes dimensionalidades: diferentes subespaços produzem pontuações incomparáveis
5. Interpretabilidade das pontuações: as pontuações muitas vezes já não transmitem um significado semântico
6. Espaço de busca exponencial: o espaço de busca não pode mais ser percorrido sistematicamente
7. Viés de espionagem de dados: dado o grande espaço de busca, para toda significância desejada, uma hipótese pode ser encontrada
8. Hubness: certos objetos ocorrem com mais frequência nas listas de vizinhos do que outros.

Muitos dos métodos especializados analisados abordam um ou outro desses problemas, mas permanecem muitas questões de pesquisa em aberto.

Bênção da dimensionalidade

Surpreendentemente e apesar das dificuldades esperadas da "maldição da dimensionalidade", heurísticas de senso comum baseadas nos métodos mais diretos "podem produzir resultados que são quase certamente ótimos" para problemas de alta dimensão. O termo "bênção da dimensionalidade" foi introduzido no final de 1990. Donoho, em seu "Manifesto do Milênio", explicou claramente por que a "bênção da dimensionalidade" formará a base da futura mineração de dados. Os efeitos da bênção da dimensionalidade foram descobertos em muitas aplicações e baseiam-se no fenômeno da concentração medida. Um exemplo da bênção do fenômeno da dimensionalidade é a separabilidade linear de um ponto aleatório de um grande conjunto aleatório finito com alta probabilidade, mesmo que esse conjunto seja exponencialmente grande: o número de elementos nesse conjunto aleatório pode crescer exponencialmente com a dimensão. Além disso, esse funcional linear pode ser selecionado na forma do discriminante de Fisher linear mais simples. Este teorema de separabilidade foi comprovado para uma ampla classe de distribuições de probabilidade: distribuições gerais uniformemente log-côncavas, distribuições produto em um cubo e muitas outras famílias (revistas recentemente em).

“A bênção da dimensionalidade e a maldição da dimensionalidade são as duas faces da mesma moeda.” Por exemplo, a propriedade típica de distribuições de probabilidade de dimensão essencialmente alta em um espaço de alta dimensão é: o quadrado da distância de pontos aleatórios a um ponto selecionado é, com alta probabilidade, próxima da média (ou mediana) dos quadrados das distâncias. Esta propriedade simplifica significativamente a geometria esperada dos dados e a indexação de dados de alta dimensão (bênção), mas, ao mesmo tempo, torna a busca por similaridade em dimensões altas difícil e até inútil (maldição).

Zimek et al. observaram que, embora as formalizações típicas da maldição da dimensionalidade afetem os dados iid, ter dados separados em cada atributo torna-se mais fácil mesmo em dimensões altas, e argumentaram que a relação sinal-ruído é importante: os dados se tornam mais fáceis com cada atributo que adiciona sinal, e mais difíceis com atributos que apenas adicionam ruído (erro irrelevante) aos dados. Em particular, para a análise de dados não supervisionada, este efeito é conhecido como inundação.

Ver também

• Análise de componentes principais
• Decomposição em valores singulares
• Lista de transformadas relacionadas à transformada de Fourier
• Programação dinâmica