GoKawiilAutomating immersive reading
How Storyteller’s forced alignment algorithm works.
All children, except one, grow up. They soon know that they will grow up, and the way Wendy knew was this. One day when she was two years old she was playing in a garden, and she plucked another flower and ran with it to her mother. I suppose she must have looked rather delightful, for Mrs. Darling put her hand to her heart and cried, 'Oh, why can't you remain like this for ever!' This was all that passed between them on the subject, but henceforth Wendy knew that she must grow up. You always know after you are two. Two is the beginning of the end. Play Pause 10 Seek backward 10 Seek forward 0:00 0:00 Peter and Wendy J. M. Barrie
Storyteller is now a sprawling ecosystem of software, with a full stack web application, native apps for Android and iOS, KOReader plugins, and upcoming macOS, watchOS, and tvOS apps. We're alpha and beta testing v3 releases of the above, which will bring updated UIs, a huge suite of new library management features, and more. We're really excited to show you what we've been working on! But at the core of Storyteller is its alignment algorithm. Storyteller can take an ebook and an audiobook that you provide it and align them, finding where each word of the ebook is spoken in the audiobook. It does this automatically, without any input from you. Then it uses the EPUB specification's built-in audio synchronization system, called Media Overlays, to embed the audio and synchronization info into the EPUB. That lets you read your book immersively, with your reader app highlighting each sentence as it's narrated by the narrator, just like in the demo above (which is using real Storyteller alignments!). Initially, that's all Storyteller was: one Python script. It took one audiobook file and one ebook file, and it output a new ebook file with audio synchronization metadata. At the time, there were a very small number of ereader apps (and zero ereader devices) that could consume these files, which used the EPUB Media Overlay specification for their functionality. I would run the script on my computer, copy the resulting EPUB to my phone, and then use BookFusion's fledging Media Overlay support to read and listen to my books. Back then, I was completely unfamiliar with the field of forced alignment that I was unwittingly sprinting into headlong. My first alignment algorithm was a wobbly construction of clunky, nested while loops. I felt like I was stumbling through the dark, aware that there was probably light at the end, but unable to see it.
Challenges Still, I found a few insights along the way. Existing forced aligners, even ones designed for this specific task of aligning ebooks and audiobooks, struggled with a few challenges common to books, and even my first fledgling attempt handled these (to varying degrees of success): Chapter order Ebooks and audiobooks may (and often do) have different chapter orders. For example, content that would be considered frontmatter in an ebook, like a dedication, may be read at the end of the audiobook instead, since audiobooks often attempt to start with the content immediately. Tress of the Emerald Sea Brandon Sanderson Acknowledgements WHAT A RIDE. When I sat down to write this book on a whim, I had no idea where the whole project would end up going… acknowledgements. what a ride. In Tress of the Emerald Sea, the acknowledgements come at the very beginning of the ebook, but at the very end of the audiobook. Chapter existence Each format will almost certainly have chapters that the other is missing entirely. Appendices, forewards, tables of contents — these are all almost always skipped in audiobooks. And audiobooks often have small chapters that don't exist in ebooks, as well. You Just Need to Lose Weight Aubrey Gordon Acknowledgements This book has been made possible by the hard work and extraordinary generosity of so many people. In You Just Need to Lose Weight, there is an acknowledgements chapter at the end of the ebook, but it doesn't exist at all in the audiobook. Skipped spans Sometimes smaller spans of content will be skipped in the audiobook narration, or the audiobook will contain content that isn't in the ebook, like a description of an image or graphic. Siddhartha Herman Hesse translated by Hilda Rosner Ebook These were Siddhartha’s thoughts; this was his thirst, his sorrow. He often repeated to himself the words from one of the Chandogya-Upanishads. “In truth, the name of Brahman is Satya. Indeed, he who knows it enters the heavenly world each day.” It often seemed near—the heavenly world—but never had he quite reached it, never had he quenched the final thirst. Audiobook These were Siddhartha’s thoughts; this was his thirst, his sorrow. It often seemed near—the heavenly world—but never had he quite reached it, never had he quenched the final thirst. In Rosner's translation of Siddhartha, the audiobook narration skips several sentences in the ebook, but otherwise matches the text. Alternate word choices Sometimes audiobook directors or narrators will intentionally choose a different word or phrase when the original is hard to speak fluently or sounds awkward when read aloud. Also, sometimes they make mistakes! You Didn’t Hear This From Me Kelsey McKinney Ebook Reading this book, for example, will not feed your family or protect your body. Audiobook Listening to this book, for example, will not feed your family or protect your body. Non-fiction books, like You Didn't Hear This From Me, often have to swap instances of the word "read" or "reading" for "listen" or "listening." Of these, even fairly basic forced alignment systems can generally handle alternate word choices without issue. And skipped spans can be challenging, especially when the audio skips spans in the text, but the results usually aren't disastrous, just imperfect. But the missing and reordered chapters can be dealbreakers for many forced aligners. Tools that existed before Storyteller, like the very cool syncabook, required that users identify which ebook chapters correspond to which audiobook chapter in advance. This is both very manual and rather challenging, as many audiobooks don't even have chapter metadata or proper per-chapter files. I wanted to do better, and that meant solving this problem. I needed a search algorithm.
Prerequisite: Boundary search Before we can even look at the actual forced alignment problem, we need to find (roughly) where a given chapter of text can be found in the audio, if it can be found at all. As prerequisite problems go, this one is… uh… kinda rough. We haven't done any alignment yet, so we don't know anything about the verbal content of the audio. And even if we had a perfect transcription (which we don't have any way of getting1 — doing this is the forced alignment problem we need to solve later), we can't just scan the transcript for the contents of the chapter, because even a perfect transcription will deviate from the baseline ebook text. So we can't do the easy thing. But while we can't get a full, accurate transcription of the audio, we can get some textual representation of it. We can use the Massively Multilingual Speech2 model to generate CTC emissions, and then greedily decode those emissions to produce text. ... I will now explain the prior jargon. We're gonna go pretty deep. There will be graphics. CTC, Wav2Vec 2.0, and MMS Connectionist Temporal Classification (CTC, and yes, it does sound like something out of Dune) has been a staple of automatic speech recognition and forced alignment for over a decade. It's essentially a loss function: the function used by machine learning models to evaluate their output and train themselves. In order to work with this loss function, a model must contain a "CTC head", a layer that outputs "CTC emissions." Emissions are an intermediate representation used by CTC — they'll be discussed in depth in a moment. Because any model using a CTC head will produce the same shape of output (the aforementioned CTC emissions), there are also standard algorithms for further decoding emissions into text. The two we care about for our use case are "unconstrained greedy decoding" and "Viterbi forced alignment". We'll explain these in detail as we get to them. So we have a way to turn our model's internal representation into emissions, via our CTC decoder. Wav2Vec 2.0 goes the other way — it's a pretrained encoder, responsible for turning audio data into the internal representation that the machine learning model can operate on. The model itself, which incorporates the Wav2Vec 2.0 encoder, the CTC decoder, and is then fine-tuned on some corpus of data so that it can "learn" the weights that minimize the CTC loss function, is Massively Multilingual Speech, or MMS. We can take some audio, feed it into MMS in chunks, and get out some CTC emissions. The emissions themselves are a two-dimensional matrix: one vector of character probabilities3 per frame of audio, where a frame is 20ms of audio. Peter and Wendy J. M. Barrie all a <blank> i o e <blank> a l i u l <blank> i u a l <blank> u i g <blank> l a i h <blank> l a i h l <blank> w k i ↻ replay This is the actual emission data from the first word of the first sentence of J. M. Barrie’s Peter and Wendy. The Wav2Vec encoder processes the audio in 20ms frames, and the CTC head outputs emissions per frame. These are the top 5 most likely characters per frame, as emitted by MMS. Background color saturation represents the probability that the given token is being spoken during that frame. Decoding without labels Now that we have our emissions, we need to solve our prerequisite problem: finding where each chapter starts and stops in the audio. One nice feature of emissions is that they're regular — since each emission vector represents one 20ms frame of audio, if we can find which frame a chapter starts in, we also know what millisecond it starts in. In order to search for text, we need something that we can compare text to. Our emissions don't really fit this bill, at the moment. But we can extract text out of our emissions, can't we? What if we just walked through our emission vectors, and, for each one, we took the character with the highest probability? We wouldn't get a good transcription in any sense, but we would get some text, and a lot of it would probably be correct. <blank> ⋮ a i e ⋮ o u ⋮ <blank> ⋮ a i ⋮ u ⋮ r ⋮ l ⋮ <blank> ⋮ a i ⋮ u ⋮ l ⋮ w ⋮ <blank> ⋮ i ⋮ u ⋮ l ⋮ g ⋮ w ⋮ <blank> ⋮ a i ⋮ u ⋮ l ⋮ h ⋮ <blank> ⋮ a i ⋮ o ⋮ l ⋮ h ⋮ <blank> ⋮ i ⋮ k l ⋮ y ⋮ w ⋮ ↻ replay The greedy decoding algorithm is rather simple. First, we walk through each frame and retrieve the token with the highest probability. Then, we collapse all adjacent equal tokens. Then, we drop all of the blanks. We're left with an approximation of what was spoken, with no capitalization, punctuation, or whitespace. I'm calling this algorithm "unconstrained greedy decoding." Unconstrained because we didn't provide a baseline text to try to decode to, and greedy because at each step, we take the best probability, and never reconsider previous steps. Here’s what it looks like when we run in on the entire section from the demo at the start of this post: allchildrenexceptonegrowuptheysoonknowthattheywillgrowupandthewaywendyknewwasthisonedaywhenshewastwoyearsoldshewasplayinginagardenandshepluckedanotherflowerandranwithittohermotherisupposeshemusthavelookedratherdelightfulformisisdarlingputherhandtoherheartandcriedowhycan'tyouremainlikethisforeverthiswasallthatpassedbetweenthemonthesubjectbuthenceforthwendyknewthatshemustgrowupyoualwaysknowafteryouartootooisthebeginningoftheend The resulting text looks quite a bit like our ebook's text! And we can make them look even more similar by conditioning the ebook text: removing punctuation, collapsing whitespace, and lowercasing each character. We can even convert numerals to their spelled forms, e.g. "2,000" to "two thousand". I talked more about how we can do this conditioning without losing track of where the text came from in the original XHTML in a previous post. RANSAC’d n-grams You've probably noticed that our greedy decoding doesn't perfectly match our query. And this is only a very small sample — most audiobooks will have several deviations from the ebook text, as we discussed earlier, and most greedy decodings will have loads of transcription errors. So we can't just scan through the document until we find our exact query text. Instead, we need to break up our document and query into pieces small enough that many of them are likely to match between the two. These are called "n-grams." For our purposes, a gram will be equivalent to a character, and our "n" will be 10. In both our document and query, we will record every single 10-letter span, along with the position it starts at. Many of these will exist in both texts — we can use those matches to locate the query in the document! Ebook A l l c h i l d r e n , e x c e p t o n e , g r o w u p . T h e y s o o n k n o w t h a t t h e y w i l l g r o w u p , a n d t h e w a y W e n d y k n e w w a s t h i s . O n e d a y w h e n s h e w a s t w o y e a r s o l d s h e w a s p l a y i n g i n a g a r d e n , a n d s h e plucked ano t h e r f l o w e r a n d r a n w i t h i t t o h e r m o t h e r . I s u p p o s e s h e m u s t h a v e l o o k e d r a t h e r d e l i g h t f u l , f o r M r s . D a r l i n g p u t h e r hand to her h e a r t a n d c r i e d , ' O h , w h y c a n ' t y o u r e m a i n l i k e t h i s f o r e v e r ! ' T h i s w a s a l l t h a t p a s s e d b e t w e e n t h e m o n t h e s u b j e c t , b u t h e n c e f o r t h W e n d y knew that sh e m u s t g r o w u p . Y o u a l w a y s k n o w a f t e r y o u a r e t w o . T w o i s t h e b e g i n n i n g o f t h e e n d . Audiobook allchildrenexceptonegrowuptheysoonknowthattheywillgrowupandthewaywendyknewwasthisonedaywhenshewastwoyearsoldshewasplayinginagardenandshe pluckedano therflowerandranwithittohermotherisupposeshemusthavelookedratherdelightfulformisisdarlingputher handtoherh eartandcriedowhycan'tyouremainlikethisforeverthiswasallthatpassedbetweenthemonthesubjectbuthenceforthwendy knewthatsh emustgrowupyoualwaysknowafteryouartootooisthebeginningoftheend Back ↻ replay Next First we condition our ebook text by lowercasing any uppercase letters, removing punctuation, and removing whitespace. This algorithm has a few really nice features: It's incredibly robust to noisy decodings. Whether the audiobook narration has many deviations from the ebook text, or the greedy decoding just did an especially poor job of estimating the spoken content, even if only 10% of the n-grams match, that's still thousands of points we can use for finding our line. It gives us lots of additional information. We'll dive into this more later, but we can use information from this algorithm, like the local rate of speech and the location of known inliers, to implement our actual forced alignment pass. It's really efficient!