Automating 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.Peter and WendyJ. M. BarrieStoryteller 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.ChallengesStill, 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 orderEbooks 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 SeaBrandon SandersonAcknowledgementsWHAT 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 existenceEach 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 WeightAubrey GordonAcknowledgementsThis 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 spansSometimes 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.SiddharthaHerman Hessetranslated by Hilda RosnerEbookThese 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.AudiobookThese 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 choicesSometimes 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 MeKelsey McKinneyEbookReading this book, for example, will not feed your family or protect your body.AudiobookListening 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 searchBefore 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 MMSConnectionist 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 WendyJ. M. Barriealla<blank>ioe<blank>aliul<blank>iual<blank>uig<blank>laih<blank>laihl<blank>wkiThis 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 labelsNow 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