Explicar “Maldição da dimensionalidade” para uma criança

Ouvi muitas vezes sobre a maldição da dimensionalidade, mas de alguma forma ainda não consigo entender a ideia, está tudo nebuloso.

Alguém pode explicar isso da maneira mais intuitiva, como você explicaria a uma criança, para que eu (e os outros confusos como eu sou) entendesse isso definitivamente?

EDITAR:

Agora, digamos que a criança de alguma forma tenha ouvido falar sobre agrupamentos (por exemplo, eles sabem agrupar seus brinquedos :)). Como o aumento da dimensionalidade tornaria mais difícil o trabalho de agrupar seus brinquedos?

Por exemplo, eles costumavam considerar apenas a forma e a cor do brinquedo (brinquedos de uma cor), mas agora precisam considerar também o tamanho e o peso dos brinquedos. Por que é mais difícil para a criança encontrar brinquedos semelhantes?

EDIT 2

Para fins de discussão, preciso esclarecer que: "Por que é mais difícil para a criança encontrar brinquedos semelhantes"? Também quero dizer por que a noção de distância é perdida em espaços de alta dimensão?

Provavelmente o garoto vai gostar de comer biscoitos, então vamos supor que você tenha um caminhão inteiro com biscoitos de cor diferente, forma diferente, sabor diferente, preço diferente ...

Se a criança tiver que escolher, mas levar em conta apenas uma característica, por exemplo, o sabor, ela terá quatro possibilidades: doce, sal, azedo, amargo, de modo que a criança precisará apenas de quatro biscoitos para encontrar o que mais gosta.

Se o garoto gosta de combinações de gosto e cor, e existem 4 (estou bastante otimista aqui :-)) cores diferentes, ele já precisa escolher entre tipos diferentes de 4x4;

Além disso, se ele quiser levar em conta a forma dos cookies e houver 5 formas diferentes, ele precisará experimentar 4x4x5 = 80 cookies

Poderíamos continuar, mas depois de comer todos esses biscoitos, ele já deve ter dor de barriga ... antes que ele possa fazer sua melhor escolha :-) Além da dor de barriga, pode ser realmente difícil lembrar as diferenças de sabor de cada cookie.

Como você pode ver (@Almo), quase todas (todas?) As coisas se tornam mais complicadas à medida que o número de dimensões aumenta, isso vale para adultos, computadores e também para crianças.

A analogia que gosto de usar para a maldição da dimensionalidade é um pouco mais do lado geométrico, mas espero que ainda seja suficientemente útil para o seu filho.

É fácil caçar um cachorro e talvez pegá-lo se ele estivesse correndo pela planície (duas dimensões). É muito mais difícil caçar pássaros, que agora têm uma dimensão extra em que eles podem se mudar. Se fingirmos que os fantasmas são seres de dimensões superiores (semelhante à Esfera interagindo com A. Square na Planície ), eles são ainda mais difíceis de capturar. :)

Ok, então vamos analisar o exemplo da criança agrupando seus brinquedos.
Imagine que a criança tem apenas 3 brinquedos:

1. uma bola de futebol azul
   
2. um freesbe azul
3. um cubo verde (ok, talvez não seja o brinquedo mais divertido que você possa imaginar)

Vamos fazer a seguinte hipótese inicial sobre como um brinquedo pode ser fabricado:

1. As cores possíveis são: vermelho, verde, azul
2. As formas possíveis são: círculo, quadrado, triângulo

Agora podemos ter (num_colors * num_shapes) = 3 * 3 = 9 agrupamentos possíveis.

O menino agruparia os brinquedos da seguinte maneira:

• Aglomerado A) contém a bola azul e o azul livre, porque têm a mesma cor e forma
• O GRUPO B) contém o cubo verde super engraçado

Usando apenas essas 2 dimensões (cor, forma), temos 2 grupos não vazios: portanto, neste primeiro caso, 7/9 a 77% do nosso espaço está vazio.

Agora vamos aumentar o número de dimensões que a criança deve considerar. Também fazemos a seguinte hipótese sobre como um brinquedo pode ser fabricado:

3. O tamanho do brinquedo pode variar de alguns centímetros a 1 metro, em passos de dez centímetros: 0-10cm, 11-20cm, ..., 91cm-1m
4. O peso do brinquedo pode variar de maneira semelhante até 1 kg, com etapas de 100 gramas: 0-100g, 101-200g, ..., 901g-1kg.

Se queremos agrupar nossos brinquedos AGORA, temos (num_colors * num_shapes * num_sizes * num_weights) = 3 * 3 * 10 * 10 = 900 agrupamentos possíveis.

O menino agruparia os brinquedos da seguinte maneira:

• O GRUPO A) contém a bola de futebol azul porque é azul e pesada
• O GRUPO B) contém o azul livre porque é azul e claro
• CLUSTER C) contém o cubo verde super engraçado

Usando as 4 dimensões atuais (forma, cor, tamanho, peso), apenas 3 clusters não estão vazios: nesse caso, 897/900 ~ 99,7% do espaço está vazio.

Este é um exemplo do que você encontra na Wikipedia ( https://en.wikipedia.org/wiki/Curse_of_dimensionality ):
... quando a dimensionalidade aumenta, o volume do espaço aumenta tão rápido que os dados disponíveis se tornam escassos.

Edit: Não tenho certeza se eu realmente poderia explicar a uma criança por que a distância às vezes dá errado em espaços de alta dimensão, mas vamos tentar prosseguir com o nosso exemplo da criança e seus brinquedos.

Considere apenas os dois primeiros recursos {cor, forma} que todos concordam que a bola azul é mais parecida com o azul livre do que com o cubo verde.

Agora, vamos adicionar outros 98 recursos {digamos: tamanho, peso, dia_de_produção_do_ brinquedo, material, suavidade, dia_do_queijo_do_ brinquedo, foi comprado pelo pai, preço etc.}: bem, para mim seria cada vez mais difícil julgar qual brinquedo é semelhante ao qual.

Assim:

1. Um grande número de recursos pode ser irrelevante em uma certa comparação de similaridade, levando a uma corrupção da relação sinal / ruído.
2. Em altas dimensões, todos os exemplos são "parecidos".
   
   

Se você me ouvir, uma boa palestra é "Algumas Coisas Úteis para Saber sobre o Aprendizado de Máquina" ( http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf ), o parágrafo 6 em particular apresenta isso tipo de raciocínio.

Espero que isto ajude!

Encontrei o seguinte link que fornece uma explicação muito intuitiva (e detalhada) da maldição da dimensionalidade: http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

Neste artigo, discutiremos a chamada 'Maldição da Dimensionalidade' e explicaremos por que é importante ao projetar um classificador. Nas seções a seguir, fornecerei uma explicação intuitiva desse conceito, ilustrada por um exemplo claro de sobreajuste devido à maldição da dimensionalidade.

Em poucas palavras, este artigo deriva (intuitivamente) de que adicionar mais recursos (por exemplo, aumentar a dimensionalidade do nosso espaço de recursos) requer coletar mais dados. De fato, a quantidade de dados que precisamos coletar (para evitar ajustes excessivos) aumenta exponencialmente à medida que adicionamos mais dimensões.

Ele também tem boas ilustrações, como a seguinte:

A maldição da dimensionalidade é um pouco confusa na definição, pois descreve coisas diferentes, mas relacionadas, em diferentes disciplinas. A seguir, ilustra a maldição da dimensionalidade do aprendizado de máquina:

Suponha que uma garota tenha dez brinquedos, dos quais ela gosta apenas daqueles em itálico:

• um ursinho marrom
• um carro azul
• um trem vermelho
• uma escavadeira amarela
• um livro verde
• uma morsa cinza de pelúcia
• uma carroça preta
• uma bola rosa
• um livro branco
• uma boneca laranja

Agora, seu pai quer lhe dar um novo brinquedo de presente de aniversário e quer garantir que ela goste. Ele pensa muito sobre o que os brinquedos que ela gosta têm em comum e finalmente chega a uma solução. Ele dá à filha um quebra-cabeça colorido. Quando ela não gosta, ele responde: “Por que você não gosta? Ele contém a letra w. "

O pai foi vítima da maldição da dimensionalidade (e otimização dentro da amostra). Ao considerar as letras, ele estava se movendo em um espaço de 26 dimensões e, portanto, era muito provável que encontrasse algum critério para separar os brinquedos que a filha gostava. Isso não precisava ser um critério de letra única, como no exemplo, mas também poderia ter sido algo como

contém pelo menos um de a, n e p, mas nenhum de u, f e s.

Para saber adequadamente se as letras são um bom critério para determinar quais brinquedos a filha gosta, o pai precisa conhecer as preferências da filha em uma quantidade enorme de brinquedos¹ - ou apenas usar o cérebro e considerar apenas parâmetros que são realmente concebíveis para afetar a filha. opinião.

¹ ordem de grandeza: , se todas as letras fossem igualmente prováveis ​​e ele não levasse em consideração múltiplas ocorrências de letras.$2^{26}$

• Pense em um círculo fechado no quadrado da unidade.
• Pense em uma esfera fechada no cubo da unidade.
• Pense em uma hiper-esfera n-dimensional fechada no hipercubo da unidade n-dimensional.

O volume do hipercubo é 1, é claro, quando medido em unidades. No entanto, o volume de uma hiperesfera diminui com n crescente.$1^n$

Se havia algo interessante dentro da hiper-esfera, é cada vez mais difícil vê-lo em dimensões mais altas. No caso dimensional, a hiper-esfera desaparece! Essa é a maldição.$\infty$

ATUALIZAÇÃO: Parece que algumas pessoas não conseguiram a conexão com as estatísticas. Você pode ver o relacionamento se imaginar escolher um ponto aleatório dentro de um hipercubo. No caso bidimensional, a probabilidade de que este ponto esteja dentro do círculo (hiper-esfera) é , no caso tridimensional é etc. No caso dimensional, a probabilidade é zero.$\pi/4$$\pi/6$$\infty$

Eu: "Estou pensando em um pequeno animal marrom começando com 'S'. O que é isso?"

Ela: "Esquilo!"

Eu: "OK, mais difícil. Estou pensando em um pequeno animal marrom. O que é isso?"

Ela: "Ainda é um esquilo?"

Eu não"

Ela: "Rato, rato, ratazana?

Eu: "Não"

Ela: "Umm ... me dê uma pista"

Eu: "Não, mas farei algo melhor: vou deixar você responder a uma pergunta CrossValidated"

Ela: [geme]

Eu: "A questão é: qual é a maldição da dimensionalidade? E você já sabe a resposta"

Ela: "eu faço?"

Eu: "Você sabe. Por que foi mais difícil adivinhar o primeiro animal que o segundo?"

Ela: "Porque existem mais animais marrons pequenos do que pequenos marrons começando com 'S'?"

Eu: "Certo. E essa é a maldição da dimensionalidade. Vamos jogar de novo."

Ela: "OK"

Eu: "Estou pensando em alguma coisa. O que é isso?"

Ela: "Não é justo. Este jogo é muito difícil."

Eu: "É verdade. É por isso que eles chamam de maldição. Você simplesmente não pode se sair bem sem saber as coisas em que penso".

Suponha que você queira enviar algumas mercadorias. Você deseja desperdiçar o mínimo de espaço possível ao embalar as mercadorias (ou seja, deixe o mínimo de espaço vazio possível), porque os custos de envio estão relacionados ao volume do envelope / caixa. Os recipientes à sua disposição (envelopes, caixas) têm ângulos retos, portanto não há sacos etc.

Primeiro problema: envie uma caneta (uma "linha") - você pode construir uma caixa em torno dela sem perder espaço.

Segundo problema: envie um CD (uma "esfera"). Você precisa colocá-lo em um envelope quadrado. Dependendo da idade da criança, ela poderá calcular quanto do envelope permanecerá vazio (e ainda saberá que existem CDs e não apenas downloads ;-)).

Terceiro problema: enviar uma bola de futebol (futebol, e ele deve ser inflado!). Você precisará colocá-lo em uma caixa e algum espaço permanecerá vazio. Esse espaço vazio será uma fração mais alta do volume total do que no exemplo do CD.

Nesse ponto, minha intuição usando essa analogia cessa, porque não consigo imaginar uma quarta dimensão.

EDIT: A analogia é mais útil (se houver) para a estimativa não paramétrica, que usa observações "locais" para o ponto de interesse para estimar, digamos, uma densidade ou uma função de regressão nesse ponto. A maldição da dimensionalidade é que, em dimensões mais altas, é necessário um bairro muito maior para um determinado número de observações (o que torna a noção de localidade questionável) ou uma grande quantidade de dados.

Meus 6 anos estão mais no verso da pesquisa de causa primária, como em "mas de onde veio todo esse gás no universo?" ... bem, eu imagino que seu filho entenda "dimensões mais altas", o que parece muito improvável para mim.

Vamos fazer a seguinte pergunta: escolha pontos aleatórios (uniformemente) em um cubo , um por um. Quanto tempo leva para obter um ponto no canto inferior ?$n$$[0,1]^n$$\left[ {1\over2}, {1\over2}\right]^n$

A resposta, jovem rapaz, é que a probabilidade de um ponto aleatório estar neste canto inferior é , o que significa que o número esperado de pontos a serem sorteados antes de atingir a esquerda O canto é (pelas propriedades da distribuição geométrica). E como você o conhece pelo problema do trigo e do tabuleiro de xadrez, isso rapidamente se torna imenso.$\left({1\over 2}\right)^n$$2^n$

Agora vá pegar seu quarto, papai tem que trabalhar.

PS sobre agrupamento ... pense nos seus pontos espalhados nesta caixa de alta dimensão. É tão grande que existem sub-caixas com arestas de comprimento . Levará algum tempo antes de escolher dois pontos na mesma sub-caixa. Bem, isso pode ser um problema, mesmo quando o ponto não é desenhado uniformemente de maneira aleatória, mas em alguns clusters. Se os clusters não forem escolhidos arbitrariamente pequenos, pode levar muito tempo para escolher dois pontos na mesma subcaixa. Você entende que isso dificulta o agrupamento ...$2^n$${1\over 2}$

Há um clássico, livro didático, problema de matemática que mostra isso.

Você prefere ganhar (opção 1) 100 centavos por dia, todos os dias durante um mês, ou (opção 2) um centavo dobrado todos os dias durante um mês? Você pode fazer esta pergunta ao seu filho.

Se você escolher a opção 1,
no dia 1 você recebe 100 moedas de um centavo no dia 2 você recebe 100 moedas de um centavo no dia 3 você recebe 100 moedas de um centavo ... no dia 30 você recebe 100 moedas de um centavo

no dia você recebe 100 centavos.$n^{th}$

o número total de moedas de um centavo é encontrado multiplicando o número de dias pelo número de moedas de um centavo por dia:

Se você escolher a opção 2:
no dia 1, você recebe 1 centavo no dia 2, recebe 2 centavos no dia 3, recebe 4 centavos no dia 4, recebe 8 centavos no dia 5, recebe 16 centavos ... no dia 30, obtém 1.073.741.824 moedas de um centavo

no dia, você recebe centavos.$n^{th}$$2^n$

o número total de moedas de um centavo está observando que a soma de todos os dias anteriores é um menor que o número de moedas de um centavo recebidas no dia atual:

Qualquer pessoa com ganância escolherá o número maior. A ganância simples é fácil de encontrar e requer pouca reflexão. Animais que não falam são facilmente capazes de ganância - os insetos são notoriamente bons nisso. Os seres humanos são capazes de muito mais.

Se você começar com um centavo em vez de cem, a ganância é mais fácil, mas se você mudar o poder de um polinômio, é mais complexo. Complexo também pode significar muito mais valioso.

Sobre a "maldição"
A operação matemática "mais importante" relacionada à física é a inversão de matriz. Dirige soluções de sistemas de equações diferenciais parciais, sendo as mais comuns as equações de Maxwell (eletromagnética), as equações de Navier Stokes (fluidos), a equação de Poisson (transferência difusiva) e variações na lei de Hookes (sólidos deformáveis). Cada uma dessas equações possui cursos universitários construídos em torno deles.

A inversão de matriz bruta, como ensinada na Álgebra Linear, também conhecida como método de Gauss-Jordan, requer ordem de operações para serem concluídas. Aqui "n" não é o número de dimensões, mas o número de blocos discretizados. Abstrai facilmente para o número de dimensões. Se forem necessários 10 blocos para representar adequadamente a geometria de um objeto 2d, serão necessários pelo menos 10 ^ 2 para representar adequadamente um analógico 3d e 10 ^ 2 ^ 2 para representar um analógico 4d. Se você está pensando em termos de geometria, pode dizer "não existem 4 dimensões", mas em termos de quantidades físicas como temperatura, concentração ou velocidade em uma direção específica, cada uma exige sua própria "coluna" e conta como uma dimensão. Tomar essas equações de 2d para 3d pode aumentar o "n" em vários poderes.$n^3$

A maldição existe porque se for superada, há um pote de valor dourado no final do arco-íris. Não é fácil - grandes mentes enfrentaram o problema vigorosamente.

ligação:

• https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

O Fcop ofereceu uma grande analogia com os cookies, mas cobriu apenas o aspecto da densidade de amostragem da maldição da dimensionalidade. Podemos estender essa analogia ao volume de amostragem ou à distância distribuindo o mesmo número de biscoitos da Fcop em, digamos, dez caixas em uma linha, caixas de 10 x 10 na mesa e 10 x 10 em uma pilha. Então você pode mostrar que, para comer a mesma porção de biscoitos, a criança terá que abrir cada vez mais caixas.

É realmente sobre as expectativas, mas vamos adotar uma abordagem do "pior cenário possível" para ilustrar.

Se houver 8 biscoitos e quisermos comer meio, ou seja, 4, de 10 caixas, na pior das hipóteses, precisamos abrir apenas 6 caixas. Isso é 60% - quase metade também. De 10x10 (novamente no pior caso) - 96 (%). E de 10x10x10 - 996 (99,6%). Isso é quase todos eles!

Pode ser a analogia da sala de armazenamento e a distância percorrida entre as salas seria melhor do que as caixas aqui.