Was bedeutet es, wenn wir sagen, dass die meisten Punkte in einem Hyperwürfel an der Grenze liegen?

Wenn ich einen 50-dimensionalen Hyperwürfel habe. Und ich definiere seine Grenze durch oder wobei die Dimension des Hyperwürfels ist. Die Berechnung des Punktanteils an der Grenze des Hyperwürfels dann . Was bedeutet es? Bedeutet das, dass der Rest des Raums leer ist? Wenn der Punkte an der Grenze liegen, dürfen die Punkte im Würfel nicht gleichmäßig verteilt sein? $0<x_j<0.05$ $0.95<x_j<1$ $x_j$ $0.995$ $99\%$

machine-learning math Rohit Kumar Singh
quelle

Nein, es bedeutet, dass die Peripherie geräumiger ist und der Effekt der Dimensionalität entspricht. Es ist etwas eingängig. Dieses Phänomen hat Konsequenzen für die Verteilung des Abstands zwischen zufälligen Knotenpaaren, die relevant werden, wenn Sie die nächsten Nachbarn in hochdimensionalen Räumen gruppieren oder berechnen möchten.

Emre

Berechnen Sie, welcher Anteil der Punkte auf einem Liniensegment nahe seiner Grenze liegt. Dann zeigt in ein Quadrat. Zeigt dann in einen Würfel. Was kannst du über sie sagen?

user253751

Antworten:

Von $99\%$ der Punkte in einem Hypercube ' zu sprechen , ist etwas irreführend, da ein Hypercube unendlich viele Punkte enthält. Sprechen wir stattdessen über die Lautstärke.

Total volume = \underset{50 times}{\underset{⏟}{1 \times 1 \times \dots \times 1}} = 1^{50} = 1.

$\text{Total volume} = \underbrace{1 \times 1 \times \dots \times 1}_{50 \text{ times}} = 1^{50} = 1.$

$x = (x_1, x_2, \dots, x_{50})$

0.05 < x_{1} < 0.95 and 0.05 < x_{2} < 0.95 and \dots and 0.05 < x_{50} < 0.95.

$0.05 < x_1 < 0.95 \,\text{ and }\, 0.05 < x_2 < 0.95 \,\text{ and }\, \dots \,\text{ and }\, 0.05 < x_{50} < 0.95.$

0.9

$0.9$

= 0.95 - 0.05

$=0.95 - 0.05$

Interior volume = \underset{50 times}{\underset{⏟}{0.9 \times 0.9 \times \dots \times 0.9}} = {0.9}^{50} \approx 0.005.

$\text{Interior volume} = \underbrace{0.9 \times 0.9 \times \dots \times 0.9}_{50 \text{ times}} = 0.9^{50} \approx 0.005.$

1 - {0.9}^{50} \approx 0.995.

$1 - 0.9^{50} \approx 0.995.$

$99.5\%$

Follow-up: Ignatius warf eine interessante Frage auf, wie dies mit der Wahrscheinlichkeit zusammenhängt. Hier ist ein Beispiel.

$0$ $1$

$0.05$ $0.95$ $0.05$ $0.95$

$10\%$ $50$ $1 - 0.9^{50} \approx 0.995.$ $99.5\%$

Faustregel: In hohen Dimensionen sind extreme Beobachtungen die Regel und nicht die Ausnahme.

Elias Strehle
quelle

Es lohnt sich, das Zitat des OP zu verwenden: "Bedeutet das, dass der Rest des Raums leer ist?" und antworten: Nein, das bedeutet, dass der Rest des Raums relativ klein ist . . . Oder ähnlich in deinen eigenen Worten. . .

Neil Slater

Wirklich schöne Erklärung des Begriffs "Fluch der Dimensionalität"

Ignatius

Fragen Sie sich, ob Folgendes richtig ist: Wenn in diesem Beispiel eine Reihe von Features in jeder der 50 Dimensionen gleichmäßig entlang [0,1] verteilt ist, beträgt (99,5% -0,5%) 99% des Volumens (Hypercube-Feature) Leerzeichen) erfasst nur die 10% -Werte jedes Features

ignatius

"Jeder Eingabeparameter ist mit einer Wahrscheinlichkeit von nur 5% extrem." Ich denke, diese Wahrscheinlichkeit beträgt 10%.

Rodvi

@ Rodvi: Du hast natürlich recht, danke! Behoben.

Elias Strehle

Sie können das Muster auch in niedrigeren Dimensionen deutlich sehen.

1. Dimension. Nehmen Sie eine Linie mit der Länge 10 und einer Grenze mit 1. Die Länge der Grenze beträgt 2 und das innere Verhältnis 8, 1: 4.

2. Dimension. Nehmen Sie ein Quadrat von Seite 10 und die Grenze 1 erneut. Die Fläche der Grenze beträgt 36, das innere Verhältnis 64, 9:16.

3. Dimension. Gleiche Länge und Grenze. Das Volumen der Grenze beträgt 488, das Innere 512, 61:64 - bereits nimmt die Grenze fast so viel Platz ein wie das Innere.

4. Dimension, jetzt ist die Grenze 5904 und das Innere 4096 - die Grenze ist jetzt größer.

Selbst bei immer kleineren Grenzlängen überholt das Grenzvolumen mit zunehmender Abmessung immer den Innenraum.

HP Williams
quelle

Der beste Weg, es zu "verstehen" (obwohl es für einen Menschen meiner Meinung nach unmöglich ist), besteht darin, die Volumina einer n-dimensionalen Kugel und eines n-dimensionalen Würfels zu vergleichen. Mit dem Wachstum von n (Dimensionalität) "tritt" das gesamte Volumen der Kugel aus und konzentriert sich in den Ecken des Würfels. Dies ist ein nützliches allgemeines Prinzip, an das Sie sich in der Codierungstheorie und ihren Anwendungen erinnern sollten.

Die beste Erklärung für das Lehrbuch findet sich in Richard W. Hammings Buch "Coding and Information Theory" (3.6 Geometric Approach, S. 44).

Der kurze Artikel in Wikipedia gibt Ihnen eine kurze Zusammenfassung derselben, wenn Sie bedenken, dass das Volumen eines n-dimensionalen Einheitswürfels immer 1 ^ n beträgt.

Ich hoffe es wird helfen.

Alex Fedotov
quelle