🤖 machine learning

Soft-MSM: Differentiable Context-Aware Elastic Alignment for Time Series

Dieser Beitrag stellt Soft-MSM vor, einen differenzierbaren, kontextbewussten elastischen Alignmentsverlust, der die Move-Split-Merge-Distanz glättet, um eine gradientenbasierte Optimierung zu ermöglichen, und der im Vergleich zu bestehenden Methoden wie Soft-DTW eine überlegene Leistung beim Clustering und der Klassifizierung von Zeitreihen demonstriert.

Ursprüngliche Autoren: Christopher Holder, Anthony Bagnall

Veröffentlicht 2026-05-04

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Christopher Holder, Anthony Bagnall

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, zwei Lieder zu vergleichen. Eines wird etwas schneller gespielt, das andere etwas langsamer. Wenn Sie versuchen, sie von Anfang bis Ende note für note auszurichten (wie mit einem starren Lineal), sehen sie völlig unterschiedlich aus, weil die Takte nicht übereinstimmen.

Dynamic Time Warping (DTW) ist wie ein intelligenter Hörer, der die Zeitachse der Lieder streckt und komprimiert, sodass die Takte perfekt übereinstimmen, was Ihnen ermöglicht zu erkennen, dass es tatsächlich dasselbe Lied ist. Dies ist hervorragend zum Vergleichen zeitbasierter Daten geeignet, wie etwa Herzschläge, Aktienkurse oder Bewegungssensoren.

Es gibt jedoch ein Problem: Dieser „intelligente Hörer" ist etwas starr. Er trifft eine plötzliche, scharfe Entscheidung darüber, wie die Zeit gedehnt werden soll. In der Welt der modernen KI, die durch winzige, sanfte Anpassungen lernt (wie ein Bildhauer, der langsam Stein abmeißelt), stellt diese plötzliche Entscheidungsfindung ein Hindernis dar. Die KI gerät in Verwirrung, weil sie die für eine Verbesserung notwendige „Steigung" nicht berechnen kann.

Hier kommt Soft-MSM ins Spiel, die in diesem Papier vorgestellte neue Methode.

Das Problem mit dem alten Weg

Das Papier konzentriert sich auf eine spezifische, sehr intelligente Methode zum Vergleichen von Zeitreihen namens MSM (Move-Split-Merge). Denken Sie an MSM als einen superfortgeschrittenen Hörer, der nicht nur die Zeit dehnt, sondern auch den Kontext der Musik versteht.

Move (Verschieben): Eine Note nur geringfügig verschieben.
Split (Teilen): Wenn eine Note zu lang ist, kann sie in zwei geteilt werden.
Merge (Zusammenführen): Wenn zwei Noten zu nah beieinander liegen, kann sie sie zusammenführen.

MSM ist darin hervorragend, oft besser als der Standard-„intelligente Hörer" (DTW) bei Aufgaben wie dem Gruppieren ähnlicher Daten. Aber wie beim ursprünglichen DTW trifft es „harte" Entscheidungen. Es sagt: „Diese Note ist definitiv eine Teilung" oder „Das ist definitiv eine Zusammenführung". Da diese Entscheidungen scharf und plötzlich sind, können sie nicht verwendet werden, um moderne KI-Modelle zu trainieren, die für das Lernen eine sanfte, kontinuierliche Rückmeldung benötigen.

Die Lösung: Soft-MSM

Die Autoren haben Soft-MSM entwickelt. Stellen Sie sich vor, Sie nehmen diesen superintelligenten Hörer (MSM) und geben ihm eine „unscharfe" Sichtweise. Anstatt eine plötzliche, harte Entscheidung darüber zu treffen, ob eine Note geteilt oder zusammengeführt werden soll, sagt Soft-MSM: „Es besteht eine 60%ige Wahrscheinlichkeit, dass dies eine Teilung ist, und eine 40%ige Wahrscheinlichkeit, dass es eine Zusammenführung ist."

Diese „Unscharfe" ist mathematisch glatt. Sie ermöglicht es der KI, die Steigung des Hügels zu sehen und genau zu wissen, in welche Richtung sie die Daten schieben muss, um den Vergleich zu verbessern. Sie verwandelt einen zerklüfteten, unpassierbaren Berg in einen sanften, begehbaren Hügel.

Wie sie es geschafft haben

Um dies zu ermöglichen, mussten die Autoren einen neuen „Türsteher"-Mechanismus erfinden.

Das alte Tor: Das ursprüngliche MSM hatte ein Tor, das entweder vollständig offen oder vollständig geschlossen war, basierend auf strengen Regeln.
Das neue Tor: Sie ersetzten dies durch ein „sanftes Tor", das sich allmählich öffnet. Dies ermöglicht es der Mathematik, durch das System zu fließen, ohne zu brechen, und erlaubt der KI, Gradienten (die Richtung der Verbesserung) durch die komplexe „Teilungs- und Zusammenführungs"-Logik zu berechnen.

Was sie herausfanden

Die Forscher testeten diese neue Methode an 112 verschiedenen Datensätzen (eine enorme Vielfalt an zeitbasierten Daten). Hier ist, was sie entdeckten:

Besseres Mitteln: Beim Versuch, die „durchschnittliche" Form einer Gruppe ähnlicher Zeitreihen zu finden (wie das Finden des durchschnittlichen Signals eines Cricket-Schiedsrichters), erzeugte Soft-MSM ein viel saubereres, genaueres Mittel als frühere Methoden. Es wurde nicht durch das Rauschen verwirrt.
Besseres Gruppieren (Clustering): Als sie Soft-MSM verwendeten, um ähnliche Objekte zusammenzufassen, leistete es deutlich bessere Arbeit als die bisherigen besten Methoden (wie Soft-DTW). Es war wie ein besserer Sortieralgorithmus für einen chaotischen Haufen Kleidung.
Bessere Klassifizierung: Als sie diese Mittelwerte verwendeten, um vorherzusagen, zu welcher Kategorie ein neues Datenelement gehörte, war Soft-MSM genauer.

Der Kompromiss

Das Papier weist auf einen kleinen Preis hin, der für diese Glätte zu zahlen ist. Das ursprüngliche MSM war ein perfektes „Metrik" (es folgte strengen mathematischen Regeln bezüglich der Distanz). Soft-MSM opfert diese perfekte mathematische Starrheit, um die Fähigkeit zu gewinnen, in glattem, gradientenbasiertem Lernen verwendet zu werden. Die Autoren argumentieren jedoch, dass für die meisten praktischen KI-Aufgaben die Fähigkeit, sanft zu lernen, viel wertvoller ist als eine perfekte Metrik zu sein.

Zusammenfassung

Das Papier stellt Soft-MSM vor, ein neues Werkzeug, das eine leistungsstarke Methode zum Vergleichen von Zeitreihen (MSM) mit moderner, sanft lernender KI kompatibel macht. Durch den Ersatz scharfer, plötzlicher Entscheidungen durch sanfte, probabilistische ermöglicht es Computern, bessere Muster in zeitbasierten Daten zu lernen, was zu besseren Durchschnitten, besseren Gruppierungen und genaueren Vorhersagen führt. Der Code ist bereits in einem Open-Source-Toolkit namens aeon verfügbar, damit andere ihn nutzen können.

1. Problemstellung

Das maschinelle Lernen für Zeitreihen (TSML) stützt sich stark auf Distanzmaße, um zeitliche Fehlausrichtungen zwischen Sequenzen zu behandeln. Elastische Distanzen wie Dynamic Time Warping (DTW) und Move-Split-Merge (MSM) adressieren dies, indem sie optimale Ausrichtungspfade finden, die Zeitachsen dehnen oder komprimieren.

Die Einschränkung elastischer Distanzen: Obwohl sie für Aufgaben wie Clustering und Klassifizierung effektiv sind, sind traditionelle elastische Distanzen nicht differenzierbar. Dies verhindert ihre direkte Verwendung als Verlustfunktionen in gradientenbasierten Optimierungen (z. B. neuronale Netze, iterative Mittelung).
Die Einschränkung bestehender Lösungen: Soft-DTW wurde eingeführt, um DTW differenzierbar zu machen, indem das harte Minimum in seiner Rekursion durch einen glatten Soft-Minimum-Operator ersetzt wird. Soft-DTW lässt sich jedoch nicht direkt auf andere elastische Distanzen wie MSM erweitern. MSM ist DTW in der Leistung oft überlegen, da es kontextbewusste Übergangskosten (Split-/Merge-Strafen) verwendet, die von der lokalen Anordnung von drei Werten abhängen. Die stückweise Natur der Kostenfunktion von MSM erzeugt nicht-glätte Bereiche, durch die Standard-Soft-Minimum-Ansätze nur schwer differenzieren können.

2. Methodik: Soft-MSM

Die Autoren schlagen Soft-MSM vor, eine glatte, differenzierbare Relaxation der Move-Split-Merge-Distanz. Die zentrale Herausforderung bestand darin, die MSM-Übergangskosten differenzierbar zu machen, während ihre kontextbewusste Struktur erhalten bleibt.

Wichtige technische Innovationen:

Glatte gatede Surrogatfunktion für Übergangskosten:
- Die ursprüngliche MSM-Kostenfunktion wendet eine feste Strafe $c$ an, wenn ein Punkt $x$ zwischen den Nachbarn $y$ und $z$ liegt, und eine zusätzliche Strafe sonst. Dies ist eine stückweise Funktion mit nicht-differenzierbaren Grenzen.
- Lösung: Die Autoren führen eine glatte Between-Gate-Funktion $g(x, y, z)$ ein, die einer hyperbolischen Tangens-Approximation ähnelt:
  $g(x, y, z) = \frac{1}{2} \left( 1 - \frac{u}{\sqrt{u^2 + \epsilon}} \right), \quad \text{wobei } u = (x-y)(x-z)$
- Dieses Gate wechselt glatt zwischen 1 (wenn $x$ zwischen $y$ und $z$ liegt) und 0 (sonst), wodurch Gradienten durch die Entscheidungsgrenze fließen können.
- Die Übergangskosten werden neu definiert als:
  $\text{trans}_\gamma(x, y, z; c) = c + (1 - g(x, y, z)) \cdot \text{softmin}_\gamma((x-y)^2, (x-z)^2)$
- Sie ersetzen zudem den absoluten Unterschied in der lokalen Distanz durch eine quadratische Differenz, um die Differenzierbarkeit bei $x=y$ sicherzustellen.
Vorwärts- und Rückwärtsrekursionen:
- Vorwärtspass: Berechnet die akkumulierte Kostenmatrix $C$ unter Verwendung eines Soft-Minimum-Operators ( $\text{softmin}_\gamma$ ) anstelle des harten Minimums und integriert die neuen glatten Übergangskosten.
- Rückwärtspass: Leitet die glatte Ausrichtungsmatrix $A$ und die Jacobian (Gradient) bezüglich der Eingabezeitreihen ab. Der Gradient wird in Beiträge von diagonalen (Match), vertikalen (Split) und horizontalen (Merge) Kanten zerlegt, gewichtet mit den Ausrichtungswahrscheinlichkeiten.
Theoretische Eigenschaften:
- Differenzierbarkeit: Nachweislich stetig differenzierbar für $\gamma > 0$ und $\epsilon > 0$ .
- Grenzverhalten: Wenn $\gamma \to 0$ und $\epsilon \to 0$ , konvergiert Soft-MSM punktweise zur Standard-MSM-Rekursion (mit quadratischen Abweichungen).
- Metrik-Eigenschaft: Soft-MSM ist keine Metrik (sie verletzt die Identität ununterscheidbarer Elemente und kann negativ sein). Um dies zu beheben, schlagen die Autoren eine divergenzkorrigierte Formulierung vor (analog zur Soft-DTW-Divergenz), um Nicht-Negativität und einen Selbstabstand von Null sicherzustellen.
- Komplexität: Behält die gleiche Zeit- und Speicherkomplexität von $O(m^2)$ wie Standard-MSM bei.

3. Hauptbeiträge

Erste differenzierbare MSM: Die erste Formulierung einer differenzierbaren Version der Move-Split-Merge-Distanz, die ihre Verwendung im gradientenbasierten Lernen ermöglicht.
Neuartige glatte Gate-Funktion: Eine mathematische Herleitung einer glatten Gate-Funktion, die die kontextabhängigen Split-/Merge-Strafen von MSM handhabt, ohne die strukturellen Vorteile der ursprünglichen Distanz zu verlieren.
Geschlossene Gradientenformeln: Herleitung der Jacobian-Transformation, die eine direkte Optimierung von Zeitreihensequenzen mittels Soft-MSM ermöglicht.
Implementierung: Die Methode ist im Open-Source-aeon-Toolkit implementiert, was Reproduzierbarkeit unterstützt.

4. Experimentelle Ergebnisse

Die Autoren bewerteten Soft-MSM an 112 UCR-Zeitreihendatensätzen in drei Hauptszenarien:

A. Mittelwertbildung von Zeitreihen (Baryzentrum)

Ziel: Finden einer repräsentativen Zeitreihe (Baryzentrum), die die Summe der Distanzen zu einer Menge von Eingangsreihen minimiert.
Vergleich: Soft-MSM-Baryzentrum (Soft-MBA) vs. Standard-MSM-Baryzentrum (MBA) und Stochastischer Subgradienten-MBA (SSG-MBA).
Ergebnis: Soft-MBA erzielte auf 97,2 % bis 100 % der Datensätze (abhängig vom Glättungsparameter $\gamma$ ) einen niedrigeren MSM-Fréchet-Verlust als sowohl MBA als auch SSG-MBA. Es übertraf die harten Gegenstücke signifikant, was zeigt, dass die differenzierbare Relaxation zu besserer Konvergenz und niedrigerem Verlust führt.

B. Clustering von Zeitreihen

Ziel: Verwendung von k-Means mit elastischen Zentroiden.
Vergleich: Soft-MBA vs. Soft-DTW-Baryzentrum (Soft-DBA), k-Shape und euklidisches k-Means.
Ergebnis:
- Soft-MBA übertraf Soft-DBA sowohl in der Clustering-Genauigkeit als auch im Adjustierten Rand-Index (ARI) signifikant.
- Soft-MBA war mit k-Shape (ein starker Baseline) konkurrenzfähig, trotz der Verwendung eines grundlegend anderen Ähnlichkeitsmaßes.
- Soft-MBA zeigte eine größere Robustheit gegenüber dem Glättungsparameter $\gamma$ im Vergleich zu Soft-DBA.

C. Klassifizierung nach Nächstem Zentroid

Ziel: Klassifizierung von Zeitreihen basierend auf der Distanz zu Klassenprototypen (Baryzentren).
Ergebnis: Klassifikatoren, die Soft-MBA-Prototypen verwendeten, erreichten eine signifikant höhere Genauigkeit und ausgeglichene Genauigkeit als solche, die Soft-DBA-Prototypen verwendeten.
Qualitative Analyse: Auf dem CRICKETX-Datensatz erzeugte Soft-MBA glattere, besser interpretierbare Klassenprototypen (die das Signal „sechs Runs" klar erfassen) im Vergleich zu den von anderen Methoden erzeugten verrauschten Prototypen.

5. Bedeutung und Auswirkung

Überbrückung der Lücke: Soft-MSM überbrückt erfolgreich die Lücke zwischen leistungsstarken elastischen Distanzen (wie MSM) und modernen gradientenbasierten Deep-Learning-Frameworks.
Überlegenheit gegenüber Soft-DTW: Die Ergebnisse deuten darauf hin, dass für viele Zeitreihenaufgaben MSM ein überlegenes Distanzmaß zu DTW ist und dass die Differenzierbarkeit bessere Ergebnisse liefert als die einfache Verwendung von Soft-DTW.
Breite Anwendbarkeit: Die Methode ebnet den Weg für die Verwendung von MSM-basierten Verlusten in:
- Tiefem Zeitreihen-Forecasting.
- Generativen Modellen für Daten-Augmentierung.
- Schwach überwachter Ausrichtung und Segmentierung.
- Repräsentationslernen (z. B. Series2Vec).
Induktive Verzerrung: Sie bietet eine neue induktive Verzerrung basierend auf „Move, Split and Merge"-Operationen, die insbesondere für stückweise konstante oder ereignisgesteuerte Zeitreihendaten nützlich ist.

Zusammenfassend ist Soft-MSM ein bedeutender Fortschritt im maschinellen Lernen für Zeitreihen und bietet eine differenzierbare, kontextbewusste elastische Distanz, die bei Mittelwertbildung, Clustering und Klassifizierungsaufgaben bestehende Soft-DTW-basierte Ansätze übertrifft.