Hoe het forced alignment-algoritme van Storyteller werkt

Storyteller is inmiddels een uitgebreid software-ecosysteem geworden, met een volledige webapplicatie, native apps voor Android en iOS, KOReader-plugins en aanstaande apps voor macOS, watchOS en tvOS. Er wordt momenteel alpha- en bètatesten uitgevoerd voor de v3-releases, die vernieuwde gebruikersinterfaces en een grote reeks nieuwe functies voor bibliotheekbeheer zullen brengen.

De kern van Storyteller is echter het alignment-algoritme. Storyteller kan een e-book en een audiobook die de gebruiker aanlevert automatisch uitlijnen door te bepalen waar elk woord uit het e-book wordt uitgesproken in het audiobestand. Dit gebeurt zonder handmatige input. Vervolgens maakt het systeem gebruik van de ingebouwde audio-synchronisatiespecificatie van EPUB, genaamd Media Overlays, om de audio en synchronisatie-informatie in het EPUB-bestand in te bedden. Hierdoor kan de lezer het boek immersief ervaren: de reader-app markeert elke zin terwijl deze door de verteller wordt voorgelezen.

In het begin was Storyteller niets meer dan één Python-script. Het nam een audiobestand en een e-bookbestand en produceerde een nieuw e-book met synchronisatiemetadata. Destijds waren er slechts enkele e-reader-apps (en geen enkel apparaat) die deze bestanden konden verwerken via de EPUB Media Overlay-specificatie. De auteur voerde het script uit op de computer, kopieerde het resulterende EPUB naar de telefoon en gebruikte de beginnende ondersteuning van BookFusion om te lezen en te luisteren.

In die tijd was de auteur onbekend met het veld van forced alignment. Het eerste algoritme was een wankele constructie van lompe, geneste while-loops. Het voelde als tasten in het donker, in de wetenschap dat er waarschijnlijk licht aan het einde was, maar zonder het te kunnen zien.

De Uitdagingen

Ondanks de beginproblemen kwamen er enkele inzichten naar boven. Bestaande forced aligners, zelfs die specifiek ontworpen zijn voor het uitlijnen van e-books en audioboeken, worstelen vaak met uitdagingen die specifiek zijn voor boeken:

  • Hoofdstukvolgorde: E-books en audioboeken hebben vaak een verschillende volgorde van hoofdstukken. Inhoud die in een e-book als voorwerk (frontmatter) wordt beschouwd, zoals een dedicatie, kan in een audiobook aan het einde staan omdat audioboeken vaak direct met de kerninhoud willen beginnen. (Voorbeeld: In Tress of the Emerald Sea van Brandon Sanderson staan de dankwoorden aan het begin van het e-book, maar aan het einde van het audioboek).
  • Bestaansrecht van hoofdstukken: Elk formaat heeft vrijwel zeker hoofdstukken die in het andere formaat volledig ontbreken. Bijlagen, voorwoorden en inhoudsopgaven worden in audioboeken bijna altijd overgeslagen. Omgekeerd bevatten audioboeken soms kleine hoofdstukken die niet in het e-book voorkomen. (Voorbeeld: In You Just Need to Lose Weight van Aubrey Gordon staat een hoofdstuk met dankwoorden aan het einde van het e-book, maar dit ontbreekt volledig in het audioboek).
  • Overgeslagen segmenten: Soms worden kleinere stukken tekst overgeslagen in de audio-uitvoering, of bevat het audioboek juist extra inhoud die niet in het e-book staat, zoals de beschrijving van een afbeelding. (Voorbeeld: In de vertaling van Rosner van Siddhartha slaat de verteller enkele zinnen uit het e-book over, terwijl de rest van de tekst overeenkomt).
  • Alternatieve woordkeuzes: Regisseurs of vertellers kiezen soms bewust een ander woord of een andere zin als het origineel moeilijk vloeiend uit te spreken is. Ook worden er fouten gemaakt. (Voorbeeld: In non-fictie boeken, zoals You Didn’t Hear This From Me, wordt het woord "lezen" vaak vervangen door "luisteren").

Van deze problemen kunnen basis-systemen voor forced alignment alternatieve woordkeuzes meestal goed afhandelen. Overgeslagen segmenten zijn uitdagender, maar de resultaten zijn meestal acceptabel. Echter, ontbrekende of herordende hoofdstukken zijn vaak een dealbreaker. Oudere tools, zoals syncabook, vereisten dat gebruikers vooraf handmatig aangaven welke e-book-hoofdstukken correspondeerden met welke audio-hoofdstukken. Dit is tijdrovend en lastig, zeker omdat veel audioboeken geen hoofdstukmetadata of aparte bestanden per hoofdstuk hebben.

Om dit op te lossen, was een zoekalgoritme nodig.

Voorwaarde: Boundary Search

Voordat het eigenlijke forced alignment-probleem kan worden aangepakt, moet eerst worden vastgesteld waar een specifiek teksthoofdstuk (ruwweg) te vinden is in de audio, indien dit überhaupt mogelijk is.

Dit is een lastig probleem omdat er nog geen uitlijning is gedaan en de verbale inhoud van de audio dus onbekend is. Zelfs met een perfecte transcriptie (die we niet hebben, aangezien dat juist het probleem is dat we willen oplossen) kunnen we niet simpelweg de transcriptie scannen, omdat zelfs een perfecte transcriptie kan afwijken van de basistekst van het e-book.

In plaats van een volledige transcriptie te maken, wordt er gebruikgemaakt van een tekstuele representatie van de audio. Met het Massively Multilingual Speech (MMS) model worden CTC emissions gegenereerd, die vervolgens via greedy decoding worden omgezet in tekst.

CTC, Wav2Vec 2.0 en MMS

Connectionist Temporal Classification (CTC) is al meer dan tien jaar een standaard in automatische spraakherkenning en forced alignment. Het is in essentie een loss function: de functie die machine learning-modellen gebruiken om hun output te evalueren en zichzelf te trainen. Een model moet een "CTC-head" bevatten, een laag die "CTC-emissies" produceert. Emissies zijn een tussenliggende representatie.

Omdat elk model met een CTC-head dezelfde vorm van output produceert, zijn er standaardalgoritmen om deze emissies te decoderen naar tekst. Voor Storyteller zijn dit "unconstrained greedy decoding" en "Viterbi forced alignment".

Wav2Vec 2.0 werkt in de tegenovergestelde richting: het is een vooraf getrainde encoder die audio-data omzet in de interne representatie waar het machine learning-model mee kan werken.

Het model dat de Wav2Vec 2.0-encoder en de CTC-decoder combineert, en is gefinetuned op een corpus van data om de gewichten te optimaliseren die de CTC-loss function minimaliseren, is Massively Multilingual Speech (MMS).

Wanneer audio in fragmenten door MMS wordt gehaald, ontstaan er CTC-emissies. Deze emissies vormen een tweedimensionale matrix: één vector van karakter-waarschijnlijkheden per frame audio (waarbij een frame 20ms aan audio is).

Decoderen zonder labels

Om te bepalen waar elk hoofdstuk begint en eindigt in de audio, wordt gebruikgemaakt van de regelmaat van de emissies. Omdat elk emissie-vector een frame van 20ms vertegenwoordigt, weten we het exacte tijdstip als we weten in welk frame een hoofdstuk begint.

Om tekst te kunnen zoeken, moet er iets zijn om de tekst mee te vergelijken. Dit gebeurt via het unconstrained greedy decoding algoritme:

  1. Loop door elk frame en haal het token met de hoogste waarschijnlijkheid op.
  2. Voeg alle opeenvolgende gelijke tokens samen.
  3. Verwijder alle 'blanks' (lege tekens).

Het resultaat is een benadering van wat er is gezegd, zonder hoofdletters, interpunctie of spaties. Deze tekst lijkt sterk op de tekst uit het e-book. Om de match te verbeteren, wordt de e-booktekst "geconditioneerd": interpunctie wordt verwijderd, witruimte wordt samengevoegd, alle letters worden kleinletters en getallen worden omgezet naar woorden (bijv. "2.000" naar "tweeduizend").

RANSAC'd n-grams

Omdat greedy decoding niet perfect is en er vaak afwijkingen zijn tussen audio en tekst, kan er niet gezocht worden naar een exacte match. In plaats daarvan wordt de tekst opgedeeld in kleine stukjes: n-grams. In dit geval is een "gram" een karakter en is "n" gelijk aan 10.

In zowel het document als de query worden alle 10-letter-sequenties geregistreerd, inclusief hun startpositie. Door matches tussen deze n-grams te vinden, kan de positie van de query in het document worden bepaald.

Dit algoritme biedt diverse voordelen:

  • Robuustheid: Zelfs als slechts 10% van de n-grams matcht (door ruis of transcriptiefouten), zijn er nog steeds duizenden punten beschikbaar om de uitlijning te bepalen.
  • Extra informatie: Het levert informatie op over de lokale spreeksnelheid en de locatie van bekende inliers, wat essentieel is voor de uiteindelijke forced alignment-stap.
  • Efficiëntie: Het proces is zeer snel.

Forced Alignment

Nadat de boundary search heeft bepaald waar hoofdstukken beginnen en eindigen, kan het eigenlijke forced alignment-algoritme worden toegepast: het CTC Viterbi-algoritme.

Forced alignment wordt meestal gezien als een globaal optimalisatieprobleem. Het doel is om een loss function (zoals "de som van alle waarschijnlijkheden van de gekozen karakters") over het hele hoofdstuk te maximaliseren. Omdat het berekenen van alle mogelijke uitkomsten extreem kostbaar is, worden twee technieken gebruikt:

1. Match-ankers

Tijdens de eerdere n-gram-analyse zijn matches gevonden die zeer waarschijnlijk correct zijn. Door alleen matches te gebruiken die globaal uniek zijn in hun respectievelijke documenten, kunnen "ankers" worden geplaatst. Omdat we zeker weten dat de tekst en audio op die punten overeenkomen, hoeft het algoritme alleen de frames tussen deze ankers te verwerken. Door ongeveer elke 2.000 tekens een anker te plaatsen, wordt het probleem opgedeeld in behapbare segmenten in plaats van een heel hoofdstuk van tienduizenden tekens in één keer te verwerken.

2. Viterbi

Viterbi is een bottom-up dynamic programming algoritme. Het vindt de oplossing door eerst deelproblemen op te lossen en deze op te bouwen naar de uiteindelijke oplossing. De kern is: als B op het kortste pad van A naar C ligt, dan moet het gedeelte van dat pad van A naar B ook het kortste pad van A naar B zijn.

Voor een woord als "All" ziet het proces er als volgt uit:

  • States en Transitions: De states zijn de tekens van het hoofdstuk. Er worden blank tokens tussen elk teken geplaatst om dubbele letters (zoals de "ll" in "all") te kunnen representeren als l → blank → l.
  • Toegestane transities: Blijven in de huidige state (stay), naar de volgende state gaan (next), of een blank state overslaan (skip) (alleen toegestaan tussen verschillende karakters).
  • Berekening: In plaats van alle mogelijke paden te enumereren (wat exponentieel groeit), houdt Viterbi per frame alleen de huidige scores van de states bij en een historie van de gebruikte transities.

Aan het einde van de frames wordt de terminale state met de hoogste score gekozen, waarna de transities worden teruggevolgd naar het begin om het optimale pad te bepalen. Hierdoor hoeven er niet honderden paden vergeleken te worden, maar slechts twee: het pad naar de laatste letter en het pad naar de laatste blank.

Door dit proces te herhalen, kunnen de exacte start- en eindtijd van elk token, woord en zin in het boek worden bepaald. Aangezien elk frame 20ms duurt, is de tijdsbepaling zeer nauwkeurig.

***

Voetnoten

  1. Er bestaan systemen voor automatische spraakherkenning zoals Whisper (waar een eerdere versie van Storyteller op was gebaseerd), maar zelfs in talen met goede ondersteuning is de output imperfect. Bovendien wijkt de inhoud van een audio-hoofdstuk vaak af van de tekst.
  2. Meta heeft inmiddels een nieuw Wav2Vec 2.0-gebaseerd model uitgebracht genaamd Omnilingual ASR. Hoewel dit meer talen ondersteunt, is voor dit specifieke doel de "geromaniseerde" tekst-output van MMS te prefereren. Dit is minder rekenintensief (slechts 31 tokens) en het is makkelijker om "verkeerd gehoorde" woorden of uitspraken van de verteller uit te lijnen, omdat Latijns schrift per letter relatief fonetisch is.
  3. Technisch gezien gaat het om logits; er wordt een softmax-functie gebruikt om deze om te zetten in waarschijnlijkheden.
  4. Men zou ook greedy of windowed local optimization kunnen gebruiken, maar dan is de kans veel groter dat men vastloopt in lokale optima, wat de algehele uitlijning verstoort.