Euklidischer Abstand und Rauschen

Beim maschinellen Lernen wird sehr häufig, explizit oder implizit, das euklidische Abstandsmaß verwendet. Werfen wir einen Blick darauf, was dies für verrauschte Daten bedeutet und was wir dagegen tun können.

Bei hohen Dimensionen tritt ein Phänomen auf, das in 2D und 3D noch nicht beobachtet wurde und oft als Fluch der Dimensionen bezeichnet wird: Der Abstand zwischen dem nächstgelegenen und dem am weitesten entfernten Punkt nähert sich dem gleichen Wert an, d.h. alle Punkte sind gleich weit voneinander entfernt, obwohl sich der Informationsgehalt grundlegend unterscheiden kann. Dieses Phänomen kann für eine Vielzahl von Abstandsmetriken beobachtet werden. Besonders ausgeprägt ist es jedoch bei der euklidischen Metrik, die wiederum besonders gut im zwei- und dreidimensionalen Raum funktioniert. Der Effekt ist also kontraintuitiv und wir müssen lernen, ihn zu verstehen.

Sobald dieser Effekt eintritt, führt er unmittelbar zum Zusammenbruch aller maschinellen Lernverfahren, die implizit oder explizit euklidische oder verwandte Metriken auf hochdimensionale Daten anwenden, wie z. B. neuronale Netze (Gradientenverfahren mit entsprechender Verlustdefinition) oder z. B. K-means-Clustering. Obwohl es also eindeutige Lösungen geben würde, kann keine Lösung bestimmt werden, wenn die Daten bewusst oder unbewusst in einen euklidischen Raum eingebettet sind.

Schauen wir uns dieses Phänomen anhand der folgenden Kurvenreihe an.

Die Funktionsabläufe werden durch ein Array von jeweils 100 Zahlenwerten dargestellt oder abgetastet. Jeder einzelne Wert dieser Kurven wird nun mit einem Rauschgenerator moduliert. Jede Wiederholung dieses Experiments führt zu einer anderen Ausprägung der einzelnen Werte.

Bestimmt man nun naiv den euklidischen Abstand zwischen zwei dieser rauschmodulierten Kurven, die in einen euklidischen Raum mit 100 Dimensionen eingebettet sind, wird man sehr große Abstände oder eine sehr große Unähnlichkeit feststellen. Das ist natürlich falsch. Die Ausgangskurven sind genau gleich und die Parameter des Rauschgenerators auch. Der Informationsgehalt in beiden Kurven ist derselbe. Würde man die Kurven ohne Rauschen und das Rauschen einzeln betrachten, so wären die Abstände bei gleichem Offset gleich Null.

Wenn man alle paarweisen euklidischen Abstände in einer Abstandsmatrix als Wärmekarte aufträgt und den Rauschanteil sukzessive erhöht, sieht man, wie alle Abstände abnehmen und sich einem mittleren Abstand annähern.

Wie kann der Fehler behoben werden?

Mit a-priori-Informationen über die Art des Rauschens (unabhängig von allen Singulärwerten) und die Art des Arrays (eine kontinuierliche Funktion) kann, selbst wenn die Daten in einen 100-dimensionalen Raum eingebettet sind, ein geeignetes Regularisierungsverfahren gewählt und das Rauschen bis auf numerische Artefakte wieder abgetrennt werden, da das Rauschen 100 Mal unabhängig auftritt. Dazu verwenden wir so genannte inverse Diffusionsalgorithmen, die das Auftreten des Rauschens invers simulieren und somit das Rauschen "herunterfahren" können. Wir haben dazu Verfahren in das Metric Framework implementiert, die nicht nur für einfache Kurven, sondern für beliebige Daten funktionieren. Die Regularisierung auf Basis der inversen Diffusion ist sehr effektiv, vor allem wenn das Rauschen rudimentär normalverteilt ist.

Wir zerlegen jeden Datensatz auf diese Weise in seine Kurve ohne Rauschen und seine Rauschkomponente. Der Abstand ist nun der euklidische Abstand der regularisierten Kurven plus der euklidische Abstand zwischen den CDFs der Rauschkomponenten, auch Cramér-von-Mises-Abstand genannt.

Wiederholt man das Experiment mit dieser modifizierten Metrik, stellt man fest, dass die Abstände viel weniger abnehmen und die Strukturen weitgehend erhalten bleiben.

Was bedeutet das für die Praxis?

Für das maschinelle Lernen müssen Daten mit so wenig Rauschen wie möglich gesammelt werden. Alternativ kann das Rauschen vor dem Training entfernt werden, aber das kann nur funktionieren, wenn man a priori korrekte Informationen über strukturelle Beziehungen in den Daten und die Art des Rauschens hat. In diesem Beispiel war dies offensichtlich und die Grundwahrheit ist bekannt. Bei Felddaten ist dies jedoch nicht der Fall, insbesondere wenn die technischen Umstände der Datenerhebung nicht bekannt sind.

Einige Algorithmen bieten eine interne Regularisierung. Aber auch hier muss es sich um eine zufällige Anpassung an die Struktur der Daten handeln. Und genau das ist das Problem mit der Regularisierung: Ohne entsprechende Kenntnisse versagt sie und ist kein Allheilmittel. Es kann sogar der gegenteilige Effekt eintreten, dass eine ungeeignete Regularisierung (z. B. auf der Grundlage der Entropie) den Informationsgehalt beseitigt, anstatt das Rauschen zu reduzieren.

Damit bleibt eigentlich nur die Erkenntnis für die Praxis: Verwenden Sie keine verrauschten Daten für maschinelles Lernen, es sei denn, Sie wissen genau, was Sie tun, und können Fachwissen über die Daten einbringen, um das Rauschen zu unterdrücken.

Dies ist wirklich der Abgesang auf jeden AutoML-Ansatz. Es kommt auf die Datenqualität an, nicht auf den Algorithmus.

Übrigens: Bei PANDA nehmen wir Daten, ob Zeitreihen oder Bilder, immer in höchster Qualität auf, zumindest in einer so hohen Auflösung, dass verbleibendes Rauschen durch Oversampling sicher entfernt werden kann.