Full search page →

DLCV 06 · How does CTC write a double letter?

AdvancedDLCV 06 · Text in Images: OCR and Document UnderstandingImage lab

Description

Edit the blank probability in the frames between two equal letters of a toy recognizer output, and watch greedy best-path decoding and prefix beam search read it.

Try this: At the default setting (blank 0.45 and O 0.55 in each of the two frames between the O’s, greedy decoding) the largest entry of every frame gives the path B O O O O K, which merges to BOK: one O is lost. Yet the correct word has the largest total probability, 0.410, against 0.310 for BOK, because every alignment with a blank in either gap frame reads BOOK. Switch to prefix beam search (beam 3): it writes BOOK. Now move the blank probability. At 0.50 greedy decoding also writes BOOK (a tie goes to the blank). With beam search, 0.40 still gives BOOK, but at 0.35 it writes BOK (0.377 against 0.343 for BOOK). At 0.05 the network almost surely saw one long O: both decoders write BOK and the loss −ln p(BOOK) is 2.819. Finally choose SEE: greedy decoding flips at 0.50 and beam search between 0.35 and 0.40, just as for BOOK. Why can the sum over alignments recover a double letter that no single frame votes for?

Predict first

In the default matrix each of the two frames between the O’s says blank 0.45 and O 0.55, and every other frame is sure of its letter. What does greedy best-path decoding write for BOOK?

Hints

The chapter section that uses this lab:

Explanation

Answer the prediction first, or open the explanation when you are ready.

Show the explanation

BOK. In both gap frames the largest entry is the O (0.55 against 0.45), so the best path is B O O O O K; merging repeats gives B O K, and no blank is left to separate two O’s. The collapsing map never writes three O’s from this path either. The path has probability 0.158, yet the correct word BOOK has probability 0.410 summed over its alignments, more than the 0.310 of BOK: greedy decoding looks at one path, not at the text.

Lab · DLCV 06 · How does CTC write a double letter?

Predict first

In the default matrix each of the two frames between the O’s says blank 0.45 and O 0.55, and every other frame is sure of its letter. What does greedy best-path decoding write for BOOK?

Loading image…

Toy network output: one row per frame, one column per symbol (orange bar: the frames between the repeated letters)
The five most probable texts, with all alignments of each added up

Try this: At the default setting (blank 0.45 and O 0.55 in each of the two frames between the O’s, greedy decoding) the largest entry of every frame gives the path B O O O O K, which merges to BOK: one O is lost. Yet the correct word has the largest total probability, 0.410, against 0.310 for BOK, because every alignment with a blank in either gap frame reads BOOK. Switch to prefix beam search (beam 3): it writes BOOK. Now move the blank probability. At 0.50 greedy decoding also writes BOOK (a tie goes to the blank). With beam search, 0.40 still gives BOOK, but at 0.35 it writes BOK (0.377 against 0.343 for BOOK). At 0.05 the network almost surely saw one long O: both decoders write BOK and the loss −ln p(BOOK) is 2.819. Finally choose SEE: greedy decoding flips at 0.50 and beam search between 0.35 and 0.40, just as for BOOK. Why can the sum over alignments recover a double letter that no single frame votes for?

A hand-made toy, not the output of a trained recognizer. Each letter of the word has one sure frame (the letter 0.85, the blank 0.15); between two equal letters there are two gap frames in which the network hesitates between the blank (probability q, the slider) and the letter (1 − q). Every other entry is 0, so the matrix asks one question only: blank or letter? BOOK has 6 frames (B, O, two gap frames, O, K) and SEE has 5. The collapsing map merges repeats first and then deletes blanks, so a double letter can be written only with a blank between its copies. Greedy decoding takes the largest entry of every frame; a tie goes to the blank, as NumPy’s argmax goes to the first index. The right-hand bars add up every alignment of each text by enumeration (4⁶ = 4,096 alignments for BOOK, 3⁵ = 243 for SEE); the probability of the correct word is also computed with the forward algorithm, and the tests check the two against each other. Prefix beam search keeps, for each prefix, the probability of alignments that end in a blank and of those that end in the last letter, and only the 3 best prefixes after every frame; pruning can lose some alignments, so its own probability can be a little below the exact one (0.366 against 0.377 for BOK at q = 0.35). The same code reproduces the 5-frame ‘cat’ example of the chapter (greedy ca, beam 3 cat 0.344, exact 0.363).

Method and image sources

Open in the Playground →