Estimating the Reliability of Dynamic Time Warping Alignments Using Circumstantial Evidence

Stellen Sie sich vor, Sie versuchen, zwei verschiedene Aufnahmen desselben Liedes abzugleichen, wie etwa eine Jazz-Improvisation von zwei verschiedenen Bands, die dieselbe Melodie spielen. Manchmal werden die Musiker schneller, langsamer oder spielen in der Mitte sogar ein völlig anderes Solo. Um diese Aufnahmen aufeinander abzustimmen, nutzen Wissenschaftler einen cleveren Computer-Trick namens Dynamic Time Warping (DTW). Denken Sie bei DTW an ein superintelligentes Gummiband, das eine Aufnahme dehnt und staucht, um sie perfekt über die andere zu legen und so für jede Note die bestmögliche Übereinstimmung zu finden.

Aber das ist der knifflige Teil: DTW ist so eifrig darauf, eine Übereinstimmung zu finden, dass es manchmal zwei Dinge zusammenführt, die eigentlich nicht zusammengehören – so als würde man versuchen, ein Schlagzeugsolo mit einer Violinstimme abzugleichen, nur weil der Computer glaubt, es sei die „beste“ verfügbare Passung. Die große Frage in diesem Bereich lautet: Woher wissen wir, wann der Computer selbstbewusst richtig liegt und wann er nur rät? Diese Arbeit untersucht diese Unsicherheit und fragt, ob wir einen „Lügendetektor“ für diese Computer-Ausrichtungen bauen können, um uns zu sagen, welche Teile der Übereinstimmung vertrauenswürdig sind und welche wackelig.

Der Detektiv der „Indizienbeweise“

Die Autoren dieser Arbeit, Aanya Pratapneni, Alice Yuan und TJ Tsai vom Harvey Mudd College, beschlossen, dieses Rätsel mithilfe eines Konzepts namens Indizienbeweis zu lösen. Anstatt zu versuchen, komplexe mathematische Formeln zu berechnen, um die Wahrheit zu erraten, stellten sie eine einfache Frage: Wenn der Computer sich einer Übereinstimmung wirklich sicher ist, würde er dann immer noch dieselbe Übereinstimmung wählen, wenn wir ihm ein wenig mehr Freiheit zum Umherschweifen ließen?

Um ihre Methode zu verstehen, stellen Sie sich vor, Sie versuchen, den kürzesten Weg durch einen dichten, nebligen Wald zu finden.

1. Der Standard-Weg (DTW): Ihnen werden strenge Regeln gegeben: Sie müssen am unten-linken Tor beginnen und am oben-rechten Tor enden. Sie folgen dem Pfad, der scheinbar die wenigsten Dornen hat. Das ist das, was der Standard-DTW-Algorithmus macht.
2. Der „Was-wäre-wenn“-Weg (FlexDTW): Stellen Sie sich nun denselben Wald vor, aber sagen Sie dem Wanderer: „Okay, du musst nicht am Tor starten oder am Tor enden. Du kannst überall an der linken oder unteren Kante starten und überall an der oberen oder rechten Kante aufhören.“ Das ist das, was die Forscher FlexDTW nennen.

Die Kernidee:
Wenn der Wald einen sehr offensichtlichen, klaren Pfad hat (einen „starken“ Pfad), wird der Wanderer denselben Pfad wählen, selbst wenn Sie die Regeln lockern. Er wird sagen: „Hey, das ist eindeutig der beste Weg, egal wo ich starte!“
Wenn der Wald jedoch voller verwirrender, dorniger Büsche ist, durch die kein klarer Weg führt (ein „schwacher“ Pfad), wird der Wanderer verwirrt sein. Wenn Sie die Regeln lockern, wird er vielleicht eine völlig andere Route wählen, weil der ursprüngliche Pfad eigentlich gar nicht so besonders war.

Die Forscher entwickelten eine Metrik (ein Bewertungssystem) basierend auf dieser Idee. Sie nehmen einen kleinen Ausschnitt der ursprünglichen Übereinstimmung des Computers, führen die „lockerere“ FlexDTW-Version nur auf diesem Ausschnitt aus und sehen nach, wie sehr sich der Pfad verändert.

• Keine Veränderung? Die ursprüngliche Übereitschaft war stark und zuverlässig.
• Große Veränderung? Die ursprüngliche Übereinstimmung war schwach und unzuverlässig.

Wie sie es getestet haben

Um zu sehen, ob ihr „Lügendetektor“ funktionierte, haben sie nicht nur geraten; sie erschufen einen Spielplatz aus 19 verschiedenen Szenarien unter Verwendung von Aufnahmen von Chopin-Mazurkas (einer Art klassischer Klaviermusik). Sie nahmen Paare von Aufnahmen und „manipulierten“ diese heimlich.

Manchmal ersetzten sie einen ganzen Block der Musik durch ein anderes Lied (was eine „nicht-übereinstimmende“ Region erzeugte). Ein anderes Mal ersetzten sie nur ein winziges Segment von 10 % oder 30 % des Liedes. Dies taten sie an verschiedenen Stellen: am Anfang, in der Mitte oder am Ende. Dadurch entstand eine Mischung aus „zuverlässigen“ Übereinstimmungen (wo die Musik tatsächlich zusammenpasste) und „unzuverlässigen“ Übereinstimmungen (wo der Computer gezwungen war, zwei verschiedene Dinge aufeinander abzustimmen).

Sie führten dann ihre Zuverlässigkeitsmetrik auf diese manipulierten Aufnahmen an, um zu sehen, ob sie die „falschen“ Teile korrekt als unzuverlässig markieren konnte.

Was sie herausfanden

Die Ergebnisse waren äußerst beeindruckend. Die Metrik erwies sich als ein sehr guter Detektiv.

• Der Score: Bei den Tests über alle ihre Szenarien hinweg erreichte die Metrik einen AUROC von 0,97. In der Welt der Informatik ist dies ein sehr hoher Wert, was bedeutet, dass sie exzellent darin war, zwischen den „guten“ Übereinstimmungen und den „schlechten“ zu unterscheiden.
• Die Baseline: Sie verglichen ihre Methode mit einer „naiven“ Baseline, die lediglich betrachtete, wie „billig“ der Pfad war (unter der Annahme, dass billigere Pfade besser sind). Ihre neue Methode deklassierte die Baseline. Beispielsweise identifizierte die neue Methode in einem Test, bei dem die Hälfte der Übereinstimmungen gefälscht war, die zuverlässigen Teile zu 94,1 % der Zeit, während die alte Methode nur 31,9 % erreichte.

Die Grenzen des Detektivs

Das Paper ist jedoch ehrlich darüber, wo der Detektiv stolpert. Die Methode ist nicht perfekt darin, sehr kurze Geheimnisse zu entdecken.

• Das „Chunk“-Problem: Die Methode betrachtet die Musik in „Chunks“ (Zeitblöcken). In ihrem besten Setup verwendeten sie Chunks von 300 Frames (was etwa 232 Millisekunden entspricht).
• Der Fehlermodus: Wenn ein „falscher“ oder „echter“ Musikabschnitt kürzer ist als die Chunk-Größe, könnte die Methode ihn übersehen. Wenn es zum Beispiel eine seltsame 2-Sekunden-Störung mitten in einem Song gibt, der einen 7 Sekunden langen Chunk hat, könnten die „guten“ Teile des Chunks den „schlechten“ Teil verdecken, sodass das Ganze zuverlässig erscheint.
• Repetition: Die Methode wird auch verwirrt, wenn sich die Musik oft wiederholt (wie ein Refrain, der exakt dreimal gleich klingt). Wenn der Computer drei identische Pfade sieht, könnte er den falschen wählen, und der „Freiheits-Test“ wird dies nicht erkennen, da alle Pfade gleich aussehen.

Das Fazit

Dieses Paper behauptet nicht, das Problem der Musikausrichtung für immer gelöst zu haben, noch sagt es, dass seine Methode für jede Art von Musik funktioniert. Stattdessen bietet es ein neues, unüberwachtes Werkzeug (eines, das keine menschlichen Lehrer braucht, die seine Arbeit überprüfen), das mittels „Indizienbeweisen“ mitteilt, wann wir einer Computer-Ausrichtung vertrauen können.

Indem sie einfach fragten: „Würde dieser Pfad gleich bleiben, wenn wir die Regeln lockerten?“, fanden die Autoren einen Weg, die wackeligen Teile der Übereinstimmung hervorzuheben. Obwohl die Methode bei sehr kurzen Glitches oder hochgradig repetitiver Musik Schwierigkeiten hat, identifizierte sie zuverlässige Regionen mit hoher Genauigkeit und gab Musikern sowie Forschern eine viel bessere Möglichkeit zu wissen, ob ihre digitalen Ausrichtungen echtes Gold oder nur Schein sind.