Recitation 9

(CTC Decoding and Beam Search)

Gabrial, Harini & Quentin

HW1P2 vs. HW3P2

HW1P2

• Sequence Classification for phoneme recognition.
• Time-synchronous outputs.

HW3P2

• Sequence to Sequence with Order Synchrony
• Training: Using CTC Loss to deal with…
• The problem of alignment
• The problem of repetition
• Inference
• Greedy Search
• Beam Search

Training

Problem Set-up

• Inputs and targets are not time-aligned
• |Y| ≠ |X|
• |Y| and |X| not proportional
• However, they are order-aligned
• We will compress predicted sequences
• We need to be able to yield repeating outputs after compression

Model

x(T-1)

x(T)

x(0)

x(1)

…

y(0)

Model

y(1)

Model

y(T-1)

Model

y(T)

x(1)

Model

y(1)

x(1)

Model

y(1)

Someone says “zoo”

We want to transcribe “zoo” at these time steps

Z

O

O

…

…

Inputs

Probabilities

Target

(Training)

Two problems

(1) time alignment and (2) repetition

One Asset

(1) order alignment

Model

x(T-1)

x(T)

x(0)

x(1)

…

y(0)

Model

y(1)

Model

y(T-1)

Model

y(T)

x(1)

Model

y(1)

x(1)

Model

y(1)

Someone says “zoo”

We want to transcribe “zoo” at these time steps

Z

O

O

…

…

?

?

?

?

?

?

…

Inputs

Probabilities

Target

All time-aligned targets for Target

?

?

?

?

?

?

…

?

?

?

?

?

?

…

Use CTC to get time-aligned targets

(Training)

The problem of repetition…

(Training)

A note on repetition…

“zzzooo”

“zoo”

“zo”

“zzzzzzzzo”

“zo” (🙁)

(Training)

A note on repetition…

“zzzooo”

“zoo”

“zo”

“zzzzzzzzo”

“zo” (🙁)

“zzz%oo%o”

“zo%o”

“zo”

“zzzzzzzzo”

“zoo” (😀)

“zzzooo”

“zoo”

“zo”

zzzzzzzo”

“zo” (🙁)

To account for repetitions, introduce a “break” character (“%”)

The problem of alignment…

(Training)

A note on alignment…

“z%o%oo”

“z%oo%o”

…

“zooo%o”

“zoo”(🙁)

(Training)

A note on alignment…

“z%o%oo”

“z%oo%o”

…

“zooo%o”

“zoo”(🙁)

If we use a time-aligned target, we can compute a differentiable loss.

But which alignment should we choose?

We could use the Viterbi algorithm to find the most probable path and use that to calculate the loss. However, there is a better option…

Using the asset of order alignment, as well as some additional “rules”, we can actually use ALL POSSIBLE ALIGNMENTS and calculate an EXPECTED LOSS over them.

We could use the Viterbi algorithm to find the most probable path and use that to calculate the loss. However, there is a better option…

Using the asset of order alignment, as well as some additional “rules”, we can actually use ALL POSSIBLE ALIGNMENTS and calculate an EXPECTED LOSS over them.

1. Alignments b/t X and Y are monotonic (once you advance to the next input, you may only keep the corresponding output or advance to the next output)

​

2. Alignment of X to Y is many-to-one (there may be many input elements aligning to a single output element).

​

3. Length of Y ≤ Length of X

​

Given: The “break” character, order alignment, and some additional rules…

Task: Find possible alignments, their probabilities, then calculate a differentiable loss

We could use the Viterbi algorithm to find the most probable path and use that to calculate the loss. However, there is a better option…

Using the asset of order alignment, as well as some additional “rules”, we can actually use ALL POSSIBLE ALIGNMENTS and calculate an EXPECTED LOSS over them.

(Training)

We want to transcribe “zoo” at these time steps

Z

O

O

Target

y(0)

y(1)

y(T-1)

y(T)

y(1)

y(1)

…

Probabilities

(Training)

We want to transcribe “zoo” at these time steps

Z

O

O

Target

P(“a”)

P(“b”)

.

.

.

P(“z”)

P(“a”)

P(“b”)

.

.

.

P(“z”)

P(“a”)

P(“b”)

.

.

.

P(“z”)

P(“a”)

P(“b”)

.

.

.

P(“z”)

P(“a”)

P(“b”)

.

.

.

P(“z”)

P(“a”)

P(“b”)

.

.

.

P(“z”)

…

Probabilities

(Training)

We want to transcribe “zoo” at these time steps

Z

O

O

Target

P(“%”)

P(“z”)

P(“%”)

P(“o”)

P(“%”)

P(“o”)

P(“%”)

P(“%”)

P(“z”)

P(“%”)

P(“o”)

P(“%”)

P(“o”)

P(“%”)

P(“%”)

P(“z”)

P(“%”)

P(“o”)

P(“%”)

P(“o”)

P(“%”)

P(“%”)

P(“z”)

P(“%”)

P(“o”)

P(“%”)

P(“o”)

P(“%”)

P(“%”)

P(“z”)

P(“%”)

P(“o”)

P(“%”)

P(“o”)

P(“%”)

P(“%”)

P(“z”)

P(“%”)

P(“o”)

P(“%”)

P(“o”)

P(“%”)

Probabilities

Limit to the characters in the Target with breaks inserted

…

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Not all of these are “viable” paths/alignments. Which ones are?

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

Dotted lines are paths that may seem viable at first, but are not!

(Training)

This path won’t work, because it would skip the “z” (not monotonic)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

Dotted lines are paths that may seem viable at first, but are not!

(Training)

This path won’t work, because it would skip the first “o”

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

Let’s start from the outer edges and work our way in…

This path won’t work because you won’t be able to get to the final character “in time” based on the sequence length.

Dotted lines are paths that may seem viable at first, but are not!

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

These are the viable alignments

(skips bolded)

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

These are the viable alignments

​

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

At any given node, you can calculate the posterior probability of reaching that node at that time step using the product of the probability of reaching from the “forward” and “backward” passes

(See Lecture)

This is where dynamic programming comes in handy!

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

We can calculate the probability of ALL ALIGNMENTS using the forward/backward method and use these to compute an EXPECTED LOSS.

(Training)

%

z

%

<start>

<end>

“zoo”

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

%

z

%

o

%

o

%

We can calculate the probability of ALL ALIGNMENTS using the forward/backward method and use these to compute an EXPECTED LOSS.

(Training)

NOW WE CAN TRAIN

(YAY!)

Training Procedure

With Connectionist Temporal Classification(CTC)

1. Define model (e.g., deep bidirectional LSTM)
2. Initialize network to output targets + “break” character
3. Pass training instances through network to obtain probability distribution over labels/symbols
4. Construct graph/table of “viable” alignments
5. Compute probabilities of alignments using Forward/Backward Algorithm (see Lecture)
6. Compute Expected Divergence over all alignments (see Lecture)
7. Propagate gradients backward and update parameters

Model

x(T-1)

x(T)

x(0)

x(1)

…

y(0)

Model

y(1)

Model

y(T-1)

Model

y(T)

x(1)

Model

y(1)

x(1)

Model

y(1)

Someone says “zoo”

We want to transcribe “zoo” at these time steps

Z

O

O

…

…

?

?

?

?

?

?

…

Inputs

Probabilities

Target

All time-aligned targets for Target

?

?

?

?

?

?

…

?

?

?

?

?

?

…

Use CTC to get time-aligned targets

(Training)

Inference

Q: What’s different at inference?

​

​

Q: What’s different at inference?

A: No target

A: No sequence “rules”

Q: What’s different at inference?

A: No target

A: No sequence “rules”

The “tree” is about to get very large :/ (gulp)

What are our options?

​

• Greedy Search

​

• Exhaustive Search (not really possible)

​

• Beam Search

​

Inference

​

Greedy Search

• Greedy Search is an easy-to-implement option for CTC decoding at inference time
• Greedy Search simply selects the most probable time step at each time-step
• Although this method is easy to implement and fast, it has the disadvantage of missing out on high-probability (score) overall paths due to it’s greedy search

​

�

​

​

Y_probs

Greedy Search

DECODED STRING

?

Y_probs

Greedy Search

A

Y_probs

Greedy Search

A

B

Y_probs

Greedy Search

A

B

A

Y_probs

Greedy Search

A

B

A

B

Y_probs

Greedy Search

DECODED STRING

A B A B

0.391*0.341*0.402*0.358 = 0.0191884642

Inference

​

Beam Search

• To have better decoding than Greedy Search, but keep the method feasible at the same time, we can choose to “explore” top-k paths at each time-step
• By exploring more than one most-probable output sequences at each time-step, we will reach a sub-optimal path that is likely to be better than the Greedy Search strategy
• By limiting our exploration options to a specific Beam Width - k, we also ensure that the computation is tractable, as opposed to the Exhaustive Search strategy

​

�

​

​

Y_probs

Beam Search

DECODED STRING

?

Parameters

Scores

Beam Search

Old

Scores

Beam Search

Old

New

Scores

Beam Search

Old

Scores

Beam Search

Old

New

Scores

Beam Search

Old

Scores

Beam Search

Old

New

Scores

Beam Search

Old

Scores

Beam Search

Old

New

Beam Search

Beam Search