Erklären Sie einem Kind den „Fluch der Dimensionalität“

91

Ich habe oft vom Fluch der Dimensionalität gehört, aber irgendwie kann ich die Idee immer noch nicht verstehen, es ist alles neblig.

Kann jemand dies auf die intuitivste Weise erklären, wie Sie es einem Kind erklären würden, damit ich (und die anderen, die verwirrt sind, wie ich es bin) diese für immer verstehen können?


BEARBEITEN:

Nehmen wir nun an, das Kind hat irgendwie von Clustern gehört (zum Beispiel wissen sie, wie man ihre Spielsachen zu Clustern zusammenfügt :)). Wie würde die Zunahme der Dimensionalität die Arbeit des Clusterns ihrer Spielzeuge erschweren?

Früher berücksichtigten sie beispielsweise nur die Form des Spielzeugs und die Farbe des Spielzeugs (einfarbiges Spielzeug), jetzt müssen sie jedoch auch die Größe und das Gewicht des Spielzeugs berücksichtigen. Warum fällt es dem Kind schwerer, ähnliches Spielzeug zu finden?


BEARBEITEN 2

Zum Zwecke der Diskussion muss ich klarstellen, dass - "Warum ist es für das Kind schwieriger, ähnliche Spielzeuge zu finden" - ich auch meine, warum der Begriff der Distanz in hochdimensionalen Räumen verloren geht?

Marko
quelle
4
Gute Frage. Und du bringst wirklich das Kind in jedem Statistiker hier raus: D Du hast mich dazu gebracht, ein Emoticon
Dawny33
2
Verwandte, aber kein Duplikat: stats.stackexchange.com/questions/99171/…
Sycorax
6
"Fluch der Dimensionalität für ein Kind"? Nicht vor dem Schlafengehen.
TTNPHNS
Überprüfen Sie dieses heraus: ixtutor.com/curse-of-dimensionality-and-the-truths-about-data
Sanjay Verma

Antworten:

78

Wahrscheinlich wird das Kind gerne Kekse essen, nehmen wir also an, dass Sie einen ganzen LKW mit Keksen haben, die eine andere Farbe, eine andere Form, einen anderen Geschmack, einen anderen Preis haben ...

Wenn das Kind wählen muss, aber nur eine Eigenschaft berücksichtigt, z. B. den Geschmack, dann hat es vier Möglichkeiten: süß, salzig, sauer, bitter, so dass das Kind nur vier Kekse probieren muss, um herauszufinden, was ihm am besten gefällt.

Wenn das Kind Kombinationen von Geschmack und Farbe mag und es 4 (ich bin hier eher optimistisch :-)) verschiedene Farben gibt, dann muss es bereits zwischen 4x4 verschiedenen Typen wählen;

Wenn er zusätzlich die Form der Kekse berücksichtigen möchte und es 5 verschiedene Formen gibt, muss er 4x4x5 = 80 Kekse probieren

Wir könnten weitermachen, aber nachdem er all diese Kekse gegessen hat, hat er vielleicht schon Bauchschmerzen ... bevor er seine beste Wahl treffen kann :-) Abgesehen von den Bauchschmerzen kann es wirklich schwierig werden, sich an die Unterschiede im Geschmack zu erinnern von jedem Cookie.

Wie Sie sehen (@Almo), werden die meisten (alle?) Dinge komplizierter, wenn die Anzahl der Dimensionen zunimmt. Dies gilt für Erwachsene, für Computer und auch für Kinder.


quelle
Wenn dies das richtige Konzept erklärt (ich weiß nicht wirklich, ob es das tut), dann mag ich diese Antwort, weil ich mir ziemlich sicher bin, dass ein Kind es verstehen kann.
Almo
14
Ich mag deine Antwort, aber ich fühle mich auf halbem Weg. Ich würde mir eine Antwort wünschen, die behandelt, wie Entfernungen mit zunehmender Anzahl von Dimensionen immer weniger aussagekräftig werden.
TrynnaDoStat
1
@TrynnaDoStat: naja ich habe die frage beantwortet, nicht nach entfernungen gefragt? Ich denke, dass keine der bisher geposteten Antworten über Entfernungen spricht? Bin ich zu neugierig, wenn ich frage, warum du es nur bei mir fragst?
3
@ fcoppens Weil deine Antwort die ist, die mir am besten gefällt =)
TrynnaDoStat
Wenn Sie also mehr Dimensionen haben, benötigen Sie auch mehr Daten, die möglicherweise nicht möglich sind.
Anton Andreev
53

Die Analogie, die ich gerne für den Fluch der Dimensionalität verwende, ist ein bisschen geometrischer, aber ich hoffe, sie ist für Ihr Kind immer noch ausreichend nützlich.

Es ist einfach, einen Hund zu jagen und ihn vielleicht zu fangen, wenn er in der Ebene herumläuft (zweidimensional). Es ist viel schwieriger, Vögel zu jagen, die jetzt eine zusätzliche Dimension haben, in die sie sich bewegen können. Wenn wir so tun, als wären Geister höherdimensionale Wesen (ähnlich der Sphäre, die mit A. Square in Flatland interagiert ), sind diese noch schwieriger zu fangen. :)

JM ist zurück.
quelle
5
Oh, das ist gut! Ich würde sogar in die 1D-Richtung gehen ... Vielleicht bewegt sich eine Raupe in einer Röhre?
Greg
2
Guter Punkt ... Also vielleicht ein sehr dünner Ast mit einer Raupe? Es nähert sich irgendwie einer Dimension an. Natürlich jagen Vögel sie, vielleicht eine Krähe in der Nähe?
Greg
1
Oh! Die Schwerkraftmanipulation würde nicht ausreichen, wenn die Krähen eine Taktik lernen würden (sie sind sehr schlau!): Sie jagen zu zweit, wenn sich einer von unten und der andere von oben nähert. Sie wissen, wenn der Käfer die Supermacht einsetzt, würde dies die Chancen für eine dieser Krähen abwägen. Hmmm .... Also, was ist mit einem Fehler mit zwei Superkräften: Gravitationsmanipulation und Zeitkomprimierung? Wäre das nicht furchtbar schwer, einen Fehler in fünf Dimensionen zu finden?
Greg
1
Das Fangen von 2 Hunden, die herumrennen, kann als Jagd in 4t, 10 Hunden in 20t, 10 Schwalben in 30t angesehen werden ...
denis
1
@ Greg, "Fang" hat wirklich nichts mit Dimension zu tun, sie laufen nur unabhängig herum (einige zu unabhängig.)
Denis
19

Ok, also lassen Sie uns das Beispiel des Kindes analysieren, das seine Spielzeuge in Gruppen zusammenfasst.
Stellen Sie sich vor, das Kind hat nur 3 Spielsachen:

  1. ein blauer Fußball
  2. ein blauer Freesbe
  3. ein grüner Würfel (ok, vielleicht ist es nicht das lustigste Spielzeug, das du dir vorstellen kannst)

Lassen Sie uns die folgende erste Hypothese machen, wie ein Spielzeug hergestellt werden kann:

  1. Mögliche Farben sind: rot, grün, blau
  2. Mögliche Formen sind: Kreis, Quadrat, Dreieck

Jetzt können wir (num_colors * num_shapes) = 3 * 3 = 9 mögliche Cluster haben.

Der Junge würde die Spielzeuge wie folgt gruppieren:

  • CLUSTER A) enthält den blauen Ball und den blauen Freesbe, da sie die gleiche Farbe und Form haben
  • CLUSTER B) enthält den überaus lustigen grünen Würfel

Wenn wir nur diese 2 Dimensionen (Farbe, Form) verwenden, haben wir 2 nicht leere Cluster: In diesem ersten Fall sind 7/9 ~ 77% unseres Raumes leer.

Erhöhen wir nun die Anzahl der Dimensionen, die das Kind berücksichtigen muss. Wir machen auch die folgende Hypothese, wie ein Spielzeug hergestellt werden kann:

  1. Die Größe des Spielzeugs kann zwischen wenigen Zentimetern und 1 Meter in Zehn-Zentimetern-Schritten variieren: 0-10 cm, 11-20 cm, ..., 91 cm-1 m
  2. Das Gewicht des Spielzeugs kann in ähnlicher Weise bis zu 1 kg in Schritten von 100 g variieren: 0-100 g, 101-200 g, ..., 901 g-1 kg.

Wenn wir unser Spielzeug JETZT in Gruppen zusammenfassen möchten, haben wir (num_colors * num_shapes * num_sizes * num_weights) = 3 * 3 * 10 * 10 = 900 mögliche Gruppen.

Der Junge würde die Spielzeuge wie folgt gruppieren:

  • CLUSTER A) enthält den blauen Fußball, weil er blau und schwer ist
  • CLUSTER B) enthält das blaue Freesbe, weil es blau und hell ist
  • CLUSTER C) enthält den überaus lustigen grünen Würfel

Unter Verwendung der aktuellen 4 Dimensionen (Form, Farbe, Größe, Gewicht) sind nur 3 Cluster nicht leer. In diesem Fall sind also 897/900 ~ 99,7% des Raums leer.

Dies ist ein Beispiel für das, was Sie auf Wikipedia finden ( https://en.wikipedia.org/wiki/Curse_of_dimensionality ):
... wenn die Dimensionalität zunimmt, nimmt das Volumen des Raums so schnell zu, dass die verfügbaren Daten spärlich werden.


Bearbeiten: Ich bin nicht sicher, ob ich einem Kind wirklich erklären kann, warum in hochdimensionalen Räumen die Entfernung manchmal falsch ist, aber lassen Sie uns versuchen, mit unserem Beispiel des Kindes und seines Spielzeugs fortzufahren.

Betrachten wir nur die beiden ersten Merkmale {Farbe, Form}, so sind sich alle einig, dass der blaue Ball dem blauen Freesbe ähnlicher ist als dem grünen Würfel. Fügen

wir nun weitere 98 Features hinzu: Größe, Gewicht, Produktionstag, Material, Weichheit, Preis usw. Nun, es würde mir immer schwerer fallen, zu beurteilen, welches Spielzeug welchem ​​ähnlich ist.

Damit:

  1. Eine große Anzahl von Merkmalen kann für einen bestimmten Ähnlichkeitsvergleich irrelevant sein und zu einer Verfälschung des Signal-Rausch-Verhältnisses führen.
  2. In hohen Dimensionen sehen alle Beispiele "gleich" aus.

Wenn Sie mir zuhören, ist ein guter Vortrag "Ein paar nützliche Dinge, die Sie über maschinelles Lernen wissen sollten" ( http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf ), insbesondere Absatz 6 Art von Argumentation.

Hoffe das hilft!

ndrplz
quelle
Ich mag deine Erklärung sehr, danke. Ich verstehe die Kargheit des Raumes jetzt viel besser, aber können Sie den Teil "veranschaulichen", warum es für das Kind schwierig ist, welche Spielzeuge bei mehr Dimensionen ähnlicher sind? Korrigieren Sie mich, wenn ich falsch liege, aber ich verstehe, dass der Begriff der Entfernung in solchen Räumen verfälscht ist, sodass es schwieriger ist, festzustellen, welche Spielzeuge ähnlicher sind. Warum ist das so?
Marko
10100
@whuber: du hast recht, um es zu einfach zu halten, ich habe die falschen Worte verwendet
ndrplz
@whuber: aber Dimension wird oft als Maß für (ein Konzept von) "Größe" gesehen
kjetil b halvorsen
@Kjetil, das ist ein interessanter Punkt, der durchaus eine Erkundung wert sein könnte. Aber halten Sie es nicht für wichtig, zu klären, in welchem ​​Sinne eine Dimension eine "Größe" ist, und sie von anderen Bedeutungen der "Größe" in einer statistischen Umgebung zu unterscheiden?
whuber
14

Ich bin auf den folgenden Link gestoßen, der eine sehr intuitive (und detaillierte) Erklärung für den Fluch der Dimensionalität bietet: http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

In diesem Artikel werden wir den sogenannten 'Fluch der Dimensionalität' diskutieren und erklären, warum dies beim Entwerfen eines Klassifikators wichtig ist. In den folgenden Abschnitten werde ich dieses Konzept intuitiv erläutern und anhand eines klaren Beispiels für eine Überanpassung aufgrund des Fluchs der Dimensionalität erläutern.

Mit wenigen Worten, dieser Artikel leitet (intuitiv) ab, dass das Hinzufügen weiterer Features (dh das Erhöhen der Dimensionalität unseres Feature-Space) das Sammeln weiterer Daten erfordert. Tatsächlich wächst die Datenmenge, die wir sammeln müssen (um eine Überanpassung zu vermeiden), exponentiell, wenn wir weitere Dimensionen hinzufügen.

Es hat auch schöne Abbildungen wie die folgende:

Bildbeschreibung hier eingeben

kostas
quelle
+1, der Link ist in der Tat sehr gut! Ich habe in einem Zitat und einem Beispiel ein Bild bearbeitet, aber wenn Sie zusätzlich eine kurze Zusammenfassung dessen liefern können, was dort erklärt wird, wäre es noch besser.
Amöbe
1
Danke für den Vorschlag. Ich habe die Antwort entsprechend bearbeitet.
Kostas
8

Der Fluch der Dimensionalität ist in seiner Definition etwas verschwommen, da er verschiedene, aber verwandte Dinge in verschiedenen Disziplinen beschreibt. Das Folgende veranschaulicht den Fluch der Dimensionalität des maschinellen Lernens:

Angenommen, ein Mädchen hat zehn Spielzeuge, von denen es nur die in Kursivschrift mag:

  • ein brauner Teddybär
  • ein blaues Auto
  • ein roter Zug
  • ein gelber Bagger
  • ein grünes Buch
  • ein graues Plüschwalroß
  • ein schwarzer Wagen
  • eine rosa Kugel
  • ein weißes Buch
  • eine orange Puppe

Jetzt möchte ihr Vater ihr ein neues Spielzeug zum Geburtstag schenken und dafür sorgen, dass es ihr gefällt. Er überlegt sehr genau, was die Spielsachen, die sie mag, gemeinsam haben und kommt schließlich zu einer Lösung. Er gibt seiner Tochter ein buntes Puzzle. Wenn sie es nicht mag, antwortet er: „Warum magst du es nicht? Es enthält den Buchstaben w. "

Der Vater ist dem Fluch der Dimensionalität (und der In-Sample-Optimierung) zum Opfer gefallen. Durch die Betrachtung von Buchstaben bewegte er sich in einem 26-dimensionalen Raum und so war es sehr wahrscheinlich, dass er ein Kriterium finden würde, das die von der Tochter geliebten Spielzeuge voneinander trennt. Dies musste nicht wie im Beispiel ein Einbuchstabenkriterium sein, sondern hätte auch so etwas sein können

enthält mindestens eines von a, n und p, aber keines von u, f und s.

Um zu beurteilen, ob Buchstaben ein gutes Kriterium für die Entscheidung sind, welches Spielzeug seine Tochter mag, müsste der Vater die Vorlieben seiner Tochter für eine gigantische Menge an Spielzeug kennen¹ - oder einfach sein Gehirn benutzen und nur Parameter berücksichtigen, die tatsächlich für die Tochter denkbar sind Meinung.


226

Wrzlprmft
quelle
1
+1 Sehr klar, danke. Dies sollte die akzeptierte Antwort sein.
MiniQuark
7
  • Stellen Sie sich einen Kreis vor, der von einem Quadrat umschlossen ist.
  • Stellen Sie sich eine Kugel vor, die im Einheitswürfel eingeschlossen ist.
  • Stellen Sie sich eine n-dimensionale Hyperkugel vor, die im Hyperwürfel der n-dimensionalen Einheit eingeschlossen ist.

1n

π/4π/6

Aksakal
quelle
5

Ich: "Ich denke an ein kleines braunes Tier, das mit 'S' beginnt. Was ist das?"

Sie: "Eichhörnchen!"

Ich: "Okay, härter. Ich denke an ein kleines braunes Tier. Was ist das?"

Sie: "Immer noch ein Eichhörnchen?"

Ich nein"

Sie: "Ratte, Maus, Wühlmaus?

Ich: "Nein"

Sie: "Ähm ... gib mir einen Hinweis"

Ich: "Nein, aber ich werde einiges besser machen: Ich lasse Sie auf eine CrossValidated-Frage antworten."

Sie: [stöhnt]

Ich: "Die Frage ist: Was ist der Fluch der Dimensionalität? Und du kennst bereits die Antwort."

Sie: "Tue ich?"

Ich: "Das tust du. Warum war es schwieriger, das erste Tier zu erraten als das zweite?"

Sie: "Weil es mehr kleine braune Tiere gibt als kleine braune Tiere, die mit 'S' beginnen?"

Ich: "Richtig. Und das ist der Fluch der Dimensionalität. Lass uns noch einmal spielen."

Sie: "OK"

Ich: "Ich denke an etwas. Was ist das?"

Sie: "Nein, fair. Dieses Spiel ist viel zu schwer."

Ich: "Stimmt. Deshalb nennen sie es einen Fluch. Man kann es einfach nicht gut machen, ohne die Dinge zu kennen, über die ich nachdenke."

Konjugatvorstufe
quelle
4

Angenommen, Sie möchten einige Waren versenden. Sie möchten beim Verpacken der Waren so wenig Platz wie möglich verschwenden (dh so wenig Platz wie möglich lassen), da sich die Versandkosten auf das Volumen des Umschlags / der Schachtel beziehen. Die zur Verfügung stehenden Behälter (Umschläge, Kisten) haben einen rechten Winkel, also keine Säcke usw.

Erstes Problem: Versenden Sie einen Stift (eine "Linie") - Sie können eine Kiste um ihn herum bauen, ohne dass Platz verloren geht.

Zweites Problem: Versenden Sie eine CD (eine "Kugel"). Sie müssen es in einen quadratischen Umschlag stecken. Je nachdem, wie alt das Kind ist, kann es möglicherweise berechnen, wie viel des Umschlags leer bleibt (und weiß immer noch, dass es CDs und nicht nur Downloads gibt ;-)).

Drittes Problem: Schiff einen Fußball (Fußball, und es muss aufgeblasen werden!). Sie müssen es in eine Schachtel legen, und etwas Platz bleibt leer. Dieser leere Bereich macht einen höheren Anteil des Gesamtvolumens aus als im CD-Beispiel.

An diesem Punkt hört meine Intuition mit dieser Analogie auf, weil ich mir keine vierte Dimension vorstellen kann.

BEARBEITEN: Die Analogie ist (wenn überhaupt) für die nichtparametrische Schätzung am nützlichsten, bei der Beobachtungen "lokal" bis zum interessierenden Punkt verwendet werden, um beispielsweise eine Dichte- oder eine Regressionsfunktion an diesem Punkt zu schätzen. Der Fluch der Dimensionalität ist, dass man in höheren Dimensionen entweder eine viel größere Nachbarschaft für eine bestimmte Anzahl von Beobachtungen (was den Begriff der Lokalität in Frage stellt) oder eine große Datenmenge benötigt.

Christoph Hanck
quelle
Ok, danke für die Erklärung. Im Grunde ist es also schwieriger, den gesamten Raum "auszufüllen", weshalb Sie ein viel größeres Sample benötigen? Ich muss meine Frage etwas präzisieren :) Ich bearbeite sie, bitte überprüfen Sie auch den anderen Teil.
Marko
Ja, siehe meine Bearbeitung - muss über Clustering nachdenken
Christoph Hanck
3
nn
@whuber Hier kommt der Fluch in das Zeitreihenbeispiel. Nehmen wir an, unsere Zeitreihe ist ein zufälliger Gang über eine bestimmte Zeitspanne (diskret), und in jeder Phase bewegt der Läufer einen zufälligen (iid ~ uniform (-1, 1)) Betrag. Du verfolgst eine Fliege auf einer Linie, sagen wir. Jetzt sind Ihre Reaktionen / Ihr Sehvermögen nur noch so gut, und um Ihre Augen auf dem Laufenden zu halten, ohne dass Sie sich um die Linie drehen müssen, müssen Sie sich höchstens 0,5 Einheiten in beide Richtungen bewegen. Wenn Sie lange genug warten, springt die Fliege natürlich um diesen Betrag und Sie verlieren ihn. Aber für jede feste Zeit, wie viele Pfade (Forts.)
Julien Clancy
werden Sie die Fliege aus den Augen verlieren? Der Fluch der Dimensionalität sagt: so ziemlich alle, wenn man die Zeit länger werden lässt. Und Sie können Ihr Sehvermögen so gut machen, wie Sie möchten (dh Sie können Bewegungen von fast 1 in beide Richtungen erkennen), und dasselbe passiert.
Julien Clancy
1

Mein 6. Lebensjahr ist mehr auf den Vers der Primärursachenforschung ausgerichtet, wie in "Aber woher kam all dieses Gas im Universum?" ... nun, ich kann mir vorstellen, dass Ihr Kind "höhere Dimensionen" versteht, was sehr scheint unwahrscheinlich für mich.

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

(12)n2n

Jetzt hol dein Zimmer ab, Papa muss arbeiten.

2n12

Elvis
quelle
1
Äh, ja, das ist dasselbe wie die Cookie-Antwort von f coppens, aber weniger kreativ. Aber es kann den Nichtkindern helfen, es so formuliert zu sehen ...
Elvis
0

Es gibt ein klassisches mathematisches Lehrbuchproblem, das dies zeigt.

Möchten Sie lieber (Option 1) 100 Cent pro Tag verdienen, jeden Tag für einen Monat, oder (Option 2) jeden Tag einen verdoppelten Cent für einen Monat? Sie können Ihrem Kind diese Frage stellen.

Wenn Sie Option 1 wählen, erhalten Sie
am ersten Tag 100 Pennys. Am zweiten Tag erhalten Sie 100 Pennys. Am dritten Tag erhalten Sie 100 Pennys. Am 30. Tag erhalten Sie 100 Pennys

nth

Die Gesamtzahl der Pfennige ergibt sich aus der Multiplikation der Anzahl der Tage mit der Anzahl der Pfennige pro Tag:

i=130100=30100=3000

Wenn Sie Option 2 wählen:
Am 1. Tag erhalten Sie 1 Cent am 2. Tag erhalten Sie 2 Cent am 3. Tag erhalten Sie 4 Cent am 4. Tag erhalten Sie 8 Cent am 5. Tag erhalten Sie 16 Cent ... am 30. Tag erhalten Sie 1.073.741.824 Pennies

nth2n

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

Jeder mit Gier wird die größere Zahl wählen. Einfache Gier ist leicht zu finden und erfordert wenig Nachdenken. Unaussprechliche Tiere sind leicht zu Gier fähig - Insekten sind dafür berüchtigt. Der Mensch kann viel mehr.

Wenn Sie mit einem Penny anstelle von hundert anfangen, ist die Gier einfacher, aber wenn Sie die Potenz für ein Polynom ändern, ist sie komplexer. Komplex kann auch viel wertvoller sein.

Über "den Fluch"
Die "wichtigste" physikalisch-mathematische Operation ist die Matrixinversion. Es treibt Lösungen von Systemen partieller Differentialgleichungen an, von denen die häufigsten Maxwell-Gleichungen (Elektromagnetik), Navier-Stokes-Gleichungen (Flüssigkeiten), Poisson-Gleichung (Diffusionsübertragung) und Variationen des Hookes-Gesetzes (deformierbare Feststoffe) sind. Um jede dieser Gleichungen sind Universitätskurse aufgebaut.

n3

Der Fluch existiert, denn wenn er überwunden ist, befindet sich am Ende des Regenbogens ein Topf mit goldenem Wert. Es ist nicht einfach - große Köpfe haben sich intensiv mit dem Problem befasst.

Verknüpfung:

EngrStudent
quelle
1
Ihr Beispiel scheint eher mit der Darstellung des Unterschieds zwischen polynomischem und exponentiellem Wachstum im Gegensatz zum Fluch der Dimensionalität zu tun zu haben.
JM ist kein Statistiker
Polynom und exponentielles Wachstum sind der Fluch. Wenn es linear wäre, würde die Verschlüsselung nicht funktionieren, und die Fusion in einer Flasche wäre leicht zu simulieren. Hier ist eine Aufzählung des "Fluches" (Wikipedia-Hyperlink) - ohne den die Computermathematik plötzlich viel erstaunlicher werden würde als sie es bereits ist. en.wikipedia.org/wiki/…
EngrStudent
Es ist eine urbane Überlieferung, die 2008 einen großen Durchbruch in der Matrixinversion entdeckte, der unter 2 sinkt, aber klassifiziert wurde und für Simulationen von Atomwaffen oder dergleichen verwendet wird.
EngrStudent
1
Ich war fast überzeugt, bis "für Simulationen von Atomwaffen oder dergleichen verwendet". ; P Aber im Ernst, Kupferschmied-Winograd scheint immer noch das Beste zu sein, obwohl es mit einer impliziten Konstante nur für wirklich große Matrizen nützlich ist.
JM ist kein Statistiker
Tangential im Zusammenhang mit Ihrer Antwort und Ihrem vorherigen Kommentar: Die Determinante effizient zu berechnen ist nicht allzu schwierig, aber die permanente zu berechnen ist eine andere Sache.
JM ist kein Statistiker
0

Fcop bot eine großartige Analogie zu Cookies, deckte jedoch nur den Aspekt der Abtastdichte des Fluches der Dimensionalität ab. Wir können diese Analogie auf das Stichprobenvolumen oder die Entfernung ausweiten, indem wir die gleiche Anzahl von Fcop-Keksen in z. B. zehn Kisten in einer Zeile, 10x10 Kisten flach auf dem Tisch und 10x10x10 in einem Stapel verteilen. Dann können Sie zeigen, dass das Kind immer mehr Kisten öffnen muss, um den gleichen Anteil an Keksen zu essen.

Es geht wirklich um die Erwartungen, aber lassen Sie uns einen "Worst-Case-Szenario" -Ansatz verwenden, um dies zu veranschaulichen.

Wenn es 8 Kekse gibt und wir eine Hälfte essen möchten, dh 4, von 10 Kisten müssen wir im schlimmsten Fall nur 6 Kisten öffnen. Das sind 60% - auch nur etwa die Hälfte. Ab 10x10 (im schlimmsten Fall erneut) - 96 (%). Und von 10x10x10 - 996 (99,6%). Das sind fast alle!

Vielleicht ist die Analogie zum Lagerraum und die Entfernung, die zwischen den Räumen zurückgelegt wird, hier besser als bei Kisten.

Diego
quelle
Gute Erweiterung :-)