Expliquer la malédiction de la dimensionnalité à un enfant

93

J'ai souvent entendu parler de malédiction de la dimensionnalité, mais d'une manière ou d'une autre, je suis toujours incapable de saisir l'idée, tout est brumeux.

Est-ce que quelqu'un peut expliquer cela de la manière la plus intuitive, comme vous le feriez à un enfant, pour que moi (et les autres aussi confus que je sois) puissent comprendre ceux-ci pour de bon?


MODIFIER:

Supposons maintenant que l'enfant ait entendu parler du regroupement (par exemple, il sait regrouper ses jouets :)). Comment l'augmentation de la dimensionnalité rendrait-elle plus difficile le regroupement de leurs jouets?

Par exemple, ils ne tenaient compte que de la forme du jouet et de la couleur du jouet (jouets unicolores), mais doivent maintenant tenir compte de la taille et du poids des jouets. Pourquoi est-il plus difficile pour l'enfant de trouver des jouets similaires?


EDIT 2

Pour les besoins de la discussion, je dois préciser que - "Pourquoi est-il plus difficile pour l’enfant de trouver des jouets similaires"? Je veux aussi dire pourquoi la notion de distance est perdue dans les espaces de grande dimension?

Marko
la source
4
Bonne question. Et vous faites vraiment ressortir l'enfant dans chaque statisticien: D Vous m'avez aussi
demandé d'
2
Connexes, mais pas une copie: stats.stackexchange.com/questions/99171/…
Monica
6
"Malédiction de la dimensionnalité à un enfant"? Pas avant le coucher.
ttnphns

Réponses:

79

Le gamin aimera probablement manger des biscuits, alors supposons que vous avez un camion entier avec des biscuits de couleur différente, de forme différente, de goût différent, de prix différent ...

Si le gamin doit choisir mais ne prend en compte qu'une caractéristique, par exemple le goût, quatre possibilités s'offrent à lui: sucré, salé, acide et amer. Le gamin n'a donc qu'à essayer quatre biscuits pour trouver ce qu'il aime le plus.

Si l'enfant aime les combinaisons de goût et de couleur et qu'il y a 4 couleurs différentes (je suis plutôt optimiste ici :-)), il doit déjà choisir parmi différents types de 4x4;

S'il veut, en outre, prendre en compte la forme des cookies et qu'il y a 5 formes différentes, il devra essayer 4x4x5 = 80 cookies

Nous pourrions continuer, mais après avoir mangé tous ces biscuits, il a peut-être déjà mal au ventre ... avant de pouvoir faire son meilleur choix :-) Hormis le mal au ventre, il peut être très difficile de se rappeler les différences de goût. de chaque cookie.

Comme vous pouvez le voir (@Almo), la plupart des choses (toutes?) Deviennent plus compliquées à mesure que le nombre de dimensions augmente, cela vaut pour les adultes, pour les ordinateurs et aussi pour les enfants.


la source
Si cela explique le bon concept (je ne sais pas vraiment si c'est le cas), j'aime cette réponse car je suis à peu près certaine qu'un enfant pourrait le comprendre.
Almo
14
J'aime votre réponse mais j'ai l'impression que c'est à mi-chemin. J'aimerais voir une réponse qui explique comment les distances deviennent de moins en moins significatives à mesure que le nombre de dimensions augmente.
TrynnaDoStat
1
@TrynnaDoStat: bien j'ai répondu à la question, il n'a pas demandé de distances? Je pense qu'aucune des réponses postées jusqu'à présent ne parle de distances? Suis-je trop curieux de demander pourquoi vous ne le demandez qu'à moi?
3
@fcoppens Parce que votre réponse est celle que j'aime le mieux =)
TrynnaDoStat
Donc, si vous avez plus de dimensions, vous avez également besoin de plus de données, ce qui pourrait ne pas être possible.
Anton Andreev
53

L'analogie que j'aime utiliser pour maudire la dimensionnalité est un peu plus géométrique, mais j'espère qu'elle sera encore suffisamment utile pour votre enfant.

Il est facile de chasser un chien et peut-être de l'attraper s'il courait dans la plaine (deux dimensions). Il est beaucoup plus difficile de chasser les oiseaux, qui ont désormais une dimension supplémentaire dans laquelle ils peuvent s'installer. Si nous prétendons que les fantômes sont des êtres de plus grande dimension (semblables à la sphère qui interagit avec A. Square in Flatland ), ils sont encore plus difficiles à attraper. :)

JM est de retour.
la source
5
Oh, c'est un bon! Je voudrais même aller dans la direction 1D ... Peut-être une chenille se déplaçant dans un tube?
Greg
2
Bon point ... Alors peut-être une branche d'arbre très mince, avec une chenille dessus? Il se rapproche en quelque sorte d'une dimension. Naturellement, les oiseaux les chassent, peut-être un corbeau à proximité?
Greg
1
Oh! La manipulation de la gravité ne suffirait pas, si les corbeaux apprenaient une tactique (ils sont très intelligents!): Ils chassent à deux, quand l’on approche d’en bas et l’autre d’en haut. Ils savent que si le bogue utilise la superpuissance, il pèserait les chances de l’un de ces corbeaux. Hmmm .... Alors, qu'en est-il d'un bug avec deux super-pouvoirs: la manipulation de la gravité et la compression du temps? Cela ne compte-t-il pas comme un bogue effroyablement difficile à traquer en 5 dimensions?
Greg
1
Attraper 2 chiens qui courent peut être vu comme une chasse en 4d, 10 chiens en 20d, 10 hirondelles en 30d ...
denis
1
@Greg, "attraper" n'a vraiment rien à voir avec la dimension, ils courent juste de manière indépendante (certains trop indépendamment.)
denis
19

Ok, analysons l'exemple de l'enfant qui regroupe ses jouets.
Imaginez que l'enfant n'ait que 3 jouets:

  1. un ballon de foot bleu
  2. un freesbe bleu
  3. un cube vert (ok peut-être que ce n'est pas le jouet le plus amusant que vous puissiez imaginer)

Faisons l'hypothèse initiale suivante sur la manière de fabriquer un jouet:

  1. Les couleurs possibles sont: rouge, vert, bleu
  2. Les formes possibles sont: cercle, carré, triangle

Nous pouvons maintenant avoir (num_colors * num_shapes) = 3 * 3 = 9 grappes possibles.

Le garçon regrouperait les jouets comme suit:

  • CLUSTER A) contient la boule bleue et le freesbe bleu, car ils ont la même couleur et la même forme
  • CLUSTER B) contient le super cube vert

En utilisant uniquement ces 2 dimensions (couleur, forme), nous avons 2 groupes non vides: dans ce premier cas, 7/9 à 77% de notre espace est vide.

Maintenant augmentons le nombre de dimensions que l'enfant doit prendre en compte. Nous faisons également l'hypothèse suivante concernant la fabrication d'un jouet:

  1. La taille du jouet peut varier entre quelques centimètres et un mètre, par pas de dix centimètres: 0-10cm, 11-20cm, ..., 91cm-1m.
  2. Le poids du jouet peut varier de manière similaire jusqu’à 1 kilogramme, avec des pas de 100 grammes: 0-100g, 101-200g, ..., 901g-1kg.

Si nous voulons regrouper nos jouets maintenant, nous avons (num_colors * num_shapes * num_sizes * num_weights) = 3 * 3 * 10 * 10 = 900 grappes possibles.

Le garçon regrouperait les jouets comme suit:

  • CLUSTER A) contient le ballon bleu car il est bleu et lourd
  • CLUSTER B) contient le freesbe bleu parce que bleu et clair
  • CLUSTER C) contient le super cube vert

En utilisant les 4 dimensions actuelles (forme, couleur, taille, poids), seules 3 grappes ne sont pas vides: dans ce cas, 897/900 ~ 99,7% de l'espace est vide.

Voici un exemple de ce que vous trouvez sur Wikipedia ( https://en.wikipedia.org/wiki/Curse_of_dimensionality ):
... lorsque la dimensionnalité augmente, le volume de l'espace augmente si rapidement que les données disponibles deviennent clairsemées.


Edit: Je ne suis pas sûr de pouvoir vraiment expliquer à un enfant pourquoi la distance va parfois mal dans des espaces de grandes dimensions, mais essayons de continuer avec notre exemple de l'enfant et de ses jouets.

Ne considérez que les 2 premières caractéristiques (couleur, forme), tout le monde s'accorde à dire que la balle bleue ressemble davantage au freesbe bleu qu'au cube vert.

Ajoutons maintenant 98 autres caractéristiques {par exemple: taille, poids, jour_de_production_de_le_toy, matière, douceur, jour_dans lequel le_toy_a été acheté, par prix, etc.}: eh bien, il serait de plus en plus difficile de juger quel jouet ressemblait à quel.

Alors:

  1. Un grand nombre de caractéristiques peut ne pas être pertinent dans une certaine comparaison de similarité, ce qui conduit à une corruption du rapport signal sur bruit.
  2. En grandes dimensions, tous les exemples "se ressemblent".

Si vous m'écoutez, un bon exposé est intitulé "Quelques informations utiles sur l'apprentissage automatique" ( http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf ), le paragraphe 6 en particulier présente cette genre de raisonnement.

J'espère que cela t'aides!

ndrplz
la source
J'aime beaucoup votre explication, merci. Je comprends beaucoup mieux la rareté de l'espace maintenant, mais pourriez-vous "illustrer" la partie pourquoi est-il difficile pour l'enfant de trouver quels jouets sont les plus similaires dans le cas de plusieurs dimensions? Corrigez-moi si je me trompe, mais je comprends que la notion de distance est corrompue dans de tels espaces. Il est donc plus difficile de déterminer quels jouets sont les plus similaires. Pourquoi donc?
Marko
10100
@whuber: vous avez raison, pour rester trop simple, j'ai utilisé les mauvais mots
ndrplz
@whuber: mais la dimension est souvent considérée comme une mesure de (une notion de) "taille"
kjetil b halvorsen
@Kjetil, c’est un point intéressant à explorer. Mais ne pensez-vous pas qu'il est important de préciser le sens dans lequel une dimension est une "taille" et de la distinguer des autres significations de "taille" dans un contexte statistique?
whuber
14

J'ai trouvé le lien suivant qui fournit une explication très intuitive (et détaillée) de la malédiction de la dimensionnalité: http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

Dans cet article, nous discuterons de la «malédiction de la dimensionnalité» et expliquerons son importance lors de la conception d'un classificateur. Dans les sections suivantes, je fournirai une explication intuitive de ce concept, illustrée par un exemple clair de surapprentissage dû à la malédiction de la dimensionnalité.

En quelques mots, cet article dérive (intuitivement) que l’ajout de nouvelles fonctionnalités (c’est-à-dire l’augmentation de la dimensionnalité de notre espace de fonctionnalités) nécessite de collecter davantage de données. En fait, la quantité de données que nous devons collecter (pour éviter les surajustements) augmente de façon exponentielle à mesure que nous ajoutons plus de dimensions.

Il a aussi de jolies illustrations comme la suivante:

entrez la description de l'image ici

Kostas
la source
+1, le lien est vraiment très bon! J'ai édité une citation et un exemple d'image, mais si vous pouviez en outre fournir un bref résumé de ce qui y est expliqué, ce serait encore mieux.
amibe dit de réintégrer Monica
1
Merci pour la suggestion. J'ai modifié la réponse en conséquence.
Kostas
8

La malédiction de la dimensionnalité est un peu floue dans sa définition car elle décrit des choses différentes mais liées dans différentes disciplines. Ce qui suit illustre la malédiction de la dimensionnalité liée à l’apprentissage automatique:

Supposons qu'une fille ait dix jouets, dont elle n'aime que ceux en italique:

  • un ours en peluche brun
  • une voiture bleue
  • un train rouge
  • une pelle jaune
  • un livre vert
  • un morse en peluche gris
  • un wagon noir
  • une balle rose
  • un livre blanc
  • une poupée orange

Maintenant, son père veut lui offrir un nouveau jouet comme cadeau pour son anniversaire et s'assurer qu'il l'aime bien. Il réfléchit très fort à ce que les jouets qu'elle aime ont en commun et parvient finalement à une solution. Il donne à sa fille un puzzle de toutes les couleurs. Quand elle n’aime pas, il répond: «Pourquoi ne l’aimes-tu pas? Il contient la lettre w.

Le père est victime de la malédiction de la dimensionnalité (et de l'optimisation dans l'échantillon). En considérant les lettres, il se déplaçait dans un espace à 26 dimensions et il était donc très probable qu'il trouverait un critère permettant de séparer les jouets préférés de la fille. Comme dans l'exemple, il n'était pas nécessaire que ce soit un critère à lettre unique, mais cela aurait pu être quelque chose comme:

contient au moins l'un de a, n et p mais aucun de u, f et s.

Pour déterminer de manière adéquate si les lettres sont un bon critère pour déterminer quels jouets sa fille aime, le père devrait connaître les préférences de sa fille sur une quantité gigantesque de jouets¹ - ou tout simplement pour utiliser son cerveau et prendre en compte uniquement les paramètres réellement concevables pour affecter la fille opinion.


226

Wrzlprmft
la source
1
+1 Très clair, merci. Cela devrait être la réponse acceptée.
MiniQuark
7
  • Pensez à un cercle entouré d'un carré.
  • Pensez à une sphère incluse dans le cube unité.
  • Pensez à une hyper sphère à N dimensions contenue dans l’hyper cube Unité à N dimensions.

1n

π/4π/6

Aksakal
la source
5

Moi: "Je pense à un petit animal brun commençant par 'S'. Qu'est-ce que c'est?"

Elle: "Écureuil!"

Moi: "OK, un plus dur. Je pense à un petit animal brun. Qu'est-ce que c'est?"

Elle: "Encore un écureuil?"

Moi non"

Elle: "Rat, souris, campagnol?

Moi: "non"

Elle: "Euh ... donnez-moi un indice"

Moi: "Non, mais je ferai mieux: je vous laisserai répondre à une question CrossValidated"

Elle: [gémit]

Moi: "La question est: Quelle est la malédiction de la dimensionnalité? Et vous connaissez déjà la réponse"

Elle: "Je fais?"

Moi: "Si. Pourquoi était-il plus difficile de deviner le premier animal que le second?"

Elle: "Parce qu'il y a plus de petits animaux bruns que de petits animaux bruns commençant par 'S'?"

Moi: "Bien. Et c'est la malédiction de la dimensionnalité. Jouons à nouveau."

Elle: "ok"

Moi: "Je pense à quelque chose. Qu'est-ce que c'est?"

Elle: "Pas juste. Ce jeu est vraiment difficile."

Moi: "C'est vrai. C'est pourquoi ils appellent ça une malédiction. On ne peut tout simplement pas bien faire sans savoir ce à quoi j'ai tendance à penser."

conjuguéprior
la source
4

Supposons que vous vouliez expédier des marchandises. Vous souhaitez perdre le moins d’espace possible lors de l’emballage des marchandises (c’est-à-dire laisser le moins d’espace vide possible), car les frais d’expédition sont liés au volume de l’enveloppe / du carton. Les conteneurs à votre disposition (enveloppes, boîtes) ont des angles droits, donc pas de sacs, etc.

Premier problème: expédier un stylo (une "ligne") - vous pouvez construire une boîte tout autour sans perdre d’espace.

Deuxième problème: expédier un CD (une "sphère"). Vous devez le mettre dans une enveloppe carrée. En fonction de l'âge de l'enfant, elle pourra peut-être calculer la quantité d'enveloppe restée vide (et savoir qu'il existe encore des CD et pas seulement des téléchargements ;-)).

Troisième problème: expédier un ballon de football (football, et il faut le gonfler!). Vous devrez le mettre dans une boîte et un espace restera vide. Cet espace vide représentera une fraction du volume total plus élevée que dans l'exemple du CD.

À ce stade, mon intuition à l'aide de cette analogie cesse, car je ne peux pas imaginer une 4ème dimension.

EDIT: L’analogie est la plus utile (voire pas du tout) pour l’estimation non paramétrique, qui utilise des observations «locales» jusqu'au point d’intérêt pour estimer, par exemple, une fonction de densité ou de régression à ce point. La malédiction de la dimensionnalité est que, dans les dimensions supérieures, il faut soit un voisinage beaucoup plus grand pour un nombre donné d'observations (ce qui rend la notion de localité douteuse), soit une grande quantité de données.

Christoph Hanck
la source
Ok, merci pour l'explication. Donc, fondamentalement, il est plus difficile de "remplir" tout l'espace, c'est pourquoi vous avez besoin d'un échantillon beaucoup plus grand? J'ai besoin de préciser un peu ma question :) Je vais la modifier, veuillez vérifier l'autre partie également.
Marko
Oui, voir mon édition - devra penser au regroupement
Christoph Hanck
3
nn
@whuber Voici où la malédiction entre dans l'exemple de la série chronologique. Disons que notre série chronologique est une marche aléatoire sur une certaine quantité de temps (discrète) et qu'à chaque étape, le promeneur déplace une quantité aléatoire (iid ~ uniforme (-1, 1)). Vous gardez une mouche sur une ligne, par exemple. Maintenant, vos réactions / votre vue ne sont que bonnes, et pour garder les yeux sur la volée sans avoir à parcourir toute la ligne, vous devez en faire tout au plus 0,5 unité dans les deux sens. Bien sûr, si vous attendez assez longtemps, la mouche sautera ce montant et vous le perdrez. Mais pour une durée déterminée, combien de chemins (suite)
Julien Clancy
va vous faire perdre la trace de la mouche? La malédiction de la dimensionnalité dit: à peu près toutes, en laissant le temps s’agrandir. Et vous pouvez rendre votre vision aussi finement bonne que vous le souhaitez (c’est-à-dire que vous pouvez détecter presque tous les mouvements 1 dans les deux sens) et la même chose se produit.
Julien Clancy
1

Mes 6 ans sont plus sur le verset de la recherche de cause première, comme dans "mais d'où vient tout ce gaz dans l'univers?" ... eh bien, j'imagine que votre enfant comprend les "dimensions supérieures", ce qui semble très peu probable pour moi.

n[0,1]n[12,12]n

(12)n2n

Maintenant, va chercher ta chambre, papa est au travail.

2n12

Elvis
la source
1
Euh, oui, c'est le même que le cookie répondre par f, mais moins créatif. Mais cela pourrait aider les non-enfants à le voir rédigé de cette façon ...
Elvis
0

Il existe un problème classique, classique, de maths qui le montre bien.

Préféreriez-vous gagner (option 1) 100 centimes par jour, chaque jour pendant un mois, ou (option 2) un sou doublé chaque jour pendant un mois? Vous pouvez poser cette question à votre enfant.

Si vous choisissez l'option 1,
le premier jour, vous obtenez 100 pièces de un cent le deuxième jour, vous obtenez 100 pièces de un cent le troisième jour.

nth

le nombre total de penny est obtenu en multipliant le nombre de jours par le nombre de penny par jour:

i=130100=30100=3000

Si vous choisissez l'option 2:
le jour 1, vous obtenez 1 centime le jour 2, vous obtenez 2 centimes le jour 3, vous obtenez 4 centimes le jour 4, vous obtenez 8 centimes le jour 5, vous en obtenez 16, ... au jour 30, vous obtenez 1 073 741 824 des sous

nth2n

i=1302n=(231)1=21474836481=2147483647

Toute personne ayant la cupidité choisira le plus grand nombre. La simple cupidité est facile à trouver et nécessite peu de réflexion. Les animaux qui parlent sont facilement capables d'avidité - les insectes y sont notoirement doués. Les humains sont capables de beaucoup plus.

Si vous commencez avec un centime au lieu de cent, la cupidité est plus facile, mais si vous modifiez le pouvoir d'un polynôme, il devient plus complexe. Complexe peut aussi signifier beaucoup plus de valeur.

À propos de "la malédiction"
L'opération mathématique la plus importante liée à la physique est l'inversion de matrice. Il pilote des solutions de systèmes d’équations aux dérivées partielles, les plus courantes étant les équations de Maxwell (électromagnétique), les équations de Navier Stokes (fluides), l’équation de Poisson (transfert diffusif) et les variations de la loi de Hookes (solides déformables). Chacune de ces équations est construite autour de cours universitaires.

n3

La malédiction existe parce que si elle est surmontée, il y a un pot de valeur dorée au bout de l'arc-en-ciel. Ce n'est pas facile - de grands esprits se sont activement attaqués au problème.

lien:

Étudiant
la source
1
Votre exemple semble être davantage lié à la différence entre croissance polynomiale et croissance exponentielle, par opposition à la malédiction de la dimensionnalité.
JM n'est pas un statisticien
la croissance polynomiale et exponentielle est la malédiction. Si elle était linéaire, le chiffrement ne fonctionnerait pas et la fusion en bouteille serait facile à simuler. Voici une énumération de la "malédiction" (hyperlien wikipedia) - sans laquelle les mathématiques informatiques deviendraient soudainement beaucoup plus étonnantes qu’elles ne le sont déjà. en.wikipedia.org/wiki/…
EngrStudent
C’est la tradition urbaine qui a découvert en 2008 une avancée décisive dans l’inversion de matrice qui passe en dessous de 2, mais elle a été classifiée et est utilisée pour des simulations d’armes nucléaires ou autres.
EngrStudent
1
J'étais presque convaincu jusqu'à "utilisé pour des simulations d'armes nucléaires ou autres". ; P Mais sérieusement, Coppersmith-Winograd semble toujours être le meilleur, bien qu’avec une constante implicite qui ne le rende utile que pour de très grandes matrices.
JM n'est pas un statisticien
Tangentiellement liée à votre réponse et à votre commentaire précédent: calculer efficacement le déterminant n’est pas trop difficile, mais calculer le permanent est une question différente.
JM n'est pas un statisticien
0

Fcop a offert une grande analogie avec les cookies mais n'a couvert que l'aspect densité de la malédiction de la dimensionnalité. Nous pouvons étendre cette analogie au volume d'échantillonnage ou à la distance en répartissant le même nombre de cookies de Fcop dans, disons, dix boîtes sur une ligne, 10 x 10 cases à plat sur la table et 10 x 10 x 10 dans une pile. Vous pouvez ensuite montrer que pour manger la même quantité de cookies, l'enfant devra ouvrir de plus en plus de boîtes.

Il s’agit vraiment des attentes, mais prenons une approche du «scénario du pire» pour illustrer notre propos.

S'il y a 8 biscuits et que nous voulons en manger une moitié, c'est-à-dire 4, sur 10 boîtes dans le pire des cas, il suffit d'ouvrir 6 boîtes. C'est 60% - à peu près la moitié aussi. De 10x10 (encore une fois dans le pire des cas) - 96 (%). Et de 10x10x10 - 996 (99,6%). C'est presque tous!

Peut-être que l'analogie de la pièce de stockage et la distance parcourue entre les pièces feraient mieux que les boîtes ici.

Diego
la source
Bonne extension :-)