Estimating the Reliability of Dynamic Time Warping Alignments Using Circumstantial Evidence

Stel je voor dat je probeert twee verschillende opnames van hetzelfde nummer te matchen, zoals een jazzimprovisatie door twee verschillende bands die dezelfde tune spelen. Soms versnellen de muzikanten, vertragen ze, of nemen ze zelfs een compleet andere solo in het midden. Om deze opnames op één lijn te krijgen, gebruiken wetenschappers een slimme computertruc genaamd Dynamic Time Warping (DTW). Denk aan DTW als een super slimme elastiek die één opname uitrekt en indrukt om deze perfect over de andere te laten passen, waarbij voor elke noot de best mogende match wordt gevonden.

Maar hier komt het lastige deel bij: DTW is zo gretig om een match te vinden, dat het soms twee dingen bij elkaar dwingt die eigenlijk niet bij elkaar horen, zoals het proberen te matchen van een drumsolo met een vioolmelodie, simpelweg omdat de computer denkt dat het de "beste" match is die hij kan vinden. De grote vraag in dit vakgebied is: Hoe weten we wanneer de computer met vertrouwen gelijk heeft, en wanneer hij gewoon aan het gokken is? Dit artikel duikt in deze onzekerheid en vraagt zich af of we een "leugendetector" voor deze computer-alignments kunnen bouwen om ons te vertellen welke delen van de match betrouwbaar zijn en welke wankel.

De Detective met het "Omstandigheidsbewijs"

De auteurs van dit artikel, Aanya Pratapneni, Alice Yuan en TJ Tsai van Harvey Mudd College, besloten dit mysterie op te lossen met een concept genaamd omstandigheidsbewijs. In plaats van te proberen complexe wiskundige formules te berekenen om de waarheid te raden, stelden ze een simpele vraag: Als de computer echt zeker is van een match, zal hij dan nog steeds dezelfde match kiezen als we hem een beetje meer vrijheid geven om te dwalen?

Om hun methode te begrijpen, stel je voor dat je probeert de kortste route door een dicht, mistig bos te vinden.

1. De Standaard Wandeling (DTW): Je krijgt strikte regels: je moet beginnen bij de poort linksonder en eindigen bij de poort rechtsboven. Je volgt het pad dat lijkt te de minste doorns te hebben. Dit is wat het standaard DTW-algoritme doet.
2. De "Wat Als"-Wandeling (FlexDTW): Stel je nu voor dat je datzelfde bos neemt, maar je zegt tegen de wandelaar: "Oké, je hoeft niet bij de poort te beginnen of bij de poort te eindigen. Je kunt overal op de linker- of onderrand beginnen, en overal op de boven- of rechterrand stoppen." Dit is wat de onderzoekers FlexDTW noemen.

Het Grote Idee:
Als het bos één heel duidelijk, helder pad heeft (een "sterk" pad), zal de wandelaar datzelfde pad kiezen, zelfs als je de regels versoepelt. Ze zullen zeggen: "Hé, dit is duidelijk de beste weg, ongeacht waar ik begin!"
Echter, als het bos vol zit met verwarrende, doornige struiken zonder duidelijke weg erdoorheen (een "zwak" pad), zal de wandelaar in de war raken. Als je de regels versoepelt, kunnen ze een compleet andere route kiezen omdat het oorspronkelijke pad eigenlijk niet zo bijzonder was.

De onderzoekers bouwden een metriek (een scoresysteem) gebaseerd op dit idee. Ze nemen een klein fragment van de oorspronkelijke match van de computer, draaien de "soepelere" FlexDTW-versie op alleen dat fragment, en kijken hoe meget het pad verandert.

• Geen Verandering? De oorspronkelijke match was sterk en betrouwbaar.
• Grote Verandering? De oorspronkelijke match was zwak en onbetrouwbaar.

Hoe Ze Het Testten

Om te zien of hun "leugendetector" werkte, hebben ze niet zomaar geraden; ze creëerden een speeltuin van 19 verschillende scenario's met opnames van Chopin Mazurka's (een type klassieke pianomuziek). Ze namen paren opnames en "tamperden" er stiekem mee.

Soms vervingen ze een heel muziekstuk door een ander nummer (wat een "niet-overeenkomend" gebied maakt). Andere keren vervingen ze slechts een klein deel van 10% of 30% van het nummer. Ze deden dit op verschillende plaatsen: aan het begin, in het midden of aan het einde van het nummer. Dit creëerde een mix van "betrouwbare" matches (waar de muziek daadwerkelijk overeenkwam) en "onbetrouwbare" matches (waar de computer gedwongen werd om twee verschillende dingen te matchen).

Vervolgens draaiden ze hun betrouwbaarheidsmetriek op deze gemanipuleerde opnames om te zien of het erin slaagde de "nep" delen correct als onbetrouwbaar te markeren.

Wat Ze Vonden

De resultaten waren zeer indrukwekkend. De metriek bleek een zeer goede detective te zijn.

• De Score: Wanneer ze de metriek testten over al hun scenario's, behaalde de metriek een AUROC van 0,97. In de wereld van computerwetenschappen is dit een zeer hoge score, wat betekent dat het uitstekend was in het onderscheiden tussen de "goede" matches en de "slechte" matches.
• De Baseline: Ze vergeleken hun methode met een "naïeve" baseline, die alleen keek naar hoe "goedkoop" het pad was (ervan uitgaande dat goedkopere paden beter zijn). Hun nieuwe methode verpletterde de baseline. Bijvoorbeeld, in een test waarbij de helft van de matches nep was, identificeerde de nieuwe methode betrouwbare delen 94,1% van de tijd correct, terwijl de oude methode slechts 31,9% wist te halen.

De Limieten van de Detective

De paper is echter eerlijk over waar de detective struikelt. De methode is niet perfect in het opsporen van zeer korte geheimen.

• Het "Chunk"-Probleem: De methode kijkt naar de muziek in "chunks" (blokken tijd). In hun beste opstelling gebruikten ze chunks van 300 frames (wat ongeveer 232 milliseconden is).
• De Foutmodus: Als een "nep" of "echt" muziekgedeelte korter is dan de chunk-grootte, kan de methode het missen. Bijvoorbeeld, als er een vreemde glitch van 2 seconden in het midden van een nummer zit, maar de chunk is 7 seconden lang, kunnen de "goede" delen van de chunk het "slechte" deel verbergen, waardoor het hele ding betrouwbaar lijkt.
• Herhaling: De methode raakt ook in de war als de muziek zichzelf veel herhaalt (zoals een refrein dat drie keer precies hetzelfde klinkt). Als de computer drie identieke paden ziet, kan hij het verkeerde pad kiezen, en de "vrijheidstest" zal het niet ontdekken omdat alle paden er hetzelfde uitzien.

De Conclusie

Dit artikel beweert niet dat het het probleem van muziek-alignment voor altijd heeft opgelost, noch zegt het dat hun methode voor elk type muziek werkt. In plaats daarvan biedt het een nieuwe, ongesuperviseerde tool (één die geen menselijke leraren nodig heeft om het werk te controleren) die "omstandigheidsbewijs" gebruikt om ons te vertellen wanneer we een computer-alignment kunnen vertrouwen.

Door simpelweg te vragen: "Zou dit pad hetzelfde blijven als we de regels versoepelen?", hebben de auteurs een manier gevonden om de wankele delen van de match te benadrukken. Hoewel het moeite heeft met zeer korte glitches of zeer repetitieve muziek, identificeerde het succesvol betrouwbare regio's met een hoge nauwkeurigheid, waardoor muzikanten en onderzoekers een veel betere manier hebben om te weten wanneer hun digitale alignments van puur goud zijn en wanneer ze slechts waardeloos zijn.