Fluch der Dimensionalität

Fluch der Dimensionalität ist ein Begriff, der von Richard Bellman eingeführt wurde, um den rapiden Anstieg im Volumen beim Hinzufügen weiterer Dimensionen in einen mathematischen Raum zu beschreiben.

Leo Breiman beschreibt beispielhaft, dass 100 Beobachtungen den eindimensionalen Raum der reellen Zahlen zwischen 0 und 1 gut abdecken. Aus diesen Beobachtungen lässt sich ein Histogramm berechnen und Schlussfolgerungen lassen sich ziehen. Werden vergleichsweise in einem 10-dimensionalen Raum der gleichen Art (jede Dimension kann Werte zwischen 0 und 1 annehmen) 100 Stichproben gesammelt, sind dies isolierte Punkte, die den Raum nicht ausreichend abdecken, um sinnvolle Aussagen über diesen Raum zu treffen. Um eine ähnliche Abdeckung wie im eindimensionalen Raum zu erreichen, müssen 100¹⁰=10²⁰ Stichproben gezogen werden, was einen wesentlich höheren Aufwand zur Folge hat.