Any comments are encouranged in any ways (e.g. issue，comment etc）
-
- 2.1. intuition: forward algorithm
- 2.2. implementation: forward algorithm with dynamic programming
- 2.3. Alpha Matrix
- 2.4. Dynamic programming based on 3 conditions
Before reading
the tutorial is a collection of many other resources and my own notes. Note that the ref if any in the tutorial means the whole passage. And part to be referred if any means the part has been summarized or detailed by me. Feel free to click the [the part to be referred] to read the original.
Feel free to skip it if you already know the purpose of CTC coming into being.
We need to learn CRNN because in the context we need an output to be a sequence.
ref: the overview from CRNN to CTC !! highly recommended !!
multi-digit sequence recognition
- Characted-based
- word-based
- sequence-to-sequence
- CRNN = CNN + RNN
- CNN --> relationship between pixel
- (the small fonts) Specifially, each feature vec of a feature seq is generated from left to right on the feature maps. That means the i-th feature vec is the concatenation of the columns of all the maps. So the shape of the tensor can be reshaped as e.g. (batch_size, 32, 256)
Usually, CE is applied to compute loss as the following way. And gt(also target) can be encoded as a stable matrix or vector.
However, in OCR or audio recognition, each target input/gt has various forms. e.g. "I like to play piano" can be unpredictable in handwriting.
Some stroke is longer than expected. Others are short.
Assume that the above example is encoded as number sequence [5, 3, 8, 3, 0].
- Tips: blank(the blue box symbol here) is introduced because we allow the model to predict a blank label due to unsureness or the end comes, which is similar with human when we are not pretty sure to make a good prediction. ref:lihongyi lecture starting from 3:45
Therefore, we see that this is an one-to-many question where e.g. "I like to play piano" has many target forms. But we not just have one sequence. We might also have other sequence e.g. "I love you", "Not only you but also I like apple" etc, none of which have a same sentence length. And this is what cross entropy cannot achieve in one batch. But now we can encode all sequences/sentences into a new sequence with a max length of all sequences.
e.g.
"I love you" --> len = 10
"How are you" --> len = 11
"what's your name" --> len = 16
In this context the input_length should be >= 16.
For dealing with the expanded targets, CTC is introduced by using the ideas of (1) HMM forward algorithm and (2) dynamic programing.
Tips: the reason we have - inserted between each two token is because, for each moment/horizontal(Note) position we allow the model to predict a blank representing unsureness.
Note that moment is for audio recognition analogue. horizontal position is for OCR analogue.
the complete code is CTC.py
given 3 samples, they are
"orange" :[15, 18, 1, 14, 7, 5] len = 6
"apple" :[1, 16, 16, 12, 5] len = 5
"watermelon" :[[23, 1, 20, 5, 18, 13, 5, 12, 15, 14] len = 10
{0:blank, 1:A, 2:B, ... 26:Z}
# ------------ a dummy input ----------------
log_probs = torch.randn(15, 3, 27).log_softmax(2).detach().requires_grad_()# 15:input_length 3:batchsize 27:num of token(class)
# targets = torch.randint(0, 27, (3, 10), dtype=torch.long)
targets = torch.tensor([[15, 18, 1, 14, 7, 5, 0, 0, 0, 0],
[1, 16, 16, 12, 5, 0, 0, 0, 0, 0],
[23, 1, 20, 5, 18, 13, 5, 12, 15, 14]]
)
# assume that the prediction vary within 15 input_length.But the target length is still the true length.
"""
e.g. [a,0,0,0,p,0,p,p,p, ...l,e] is one of the prediction
"""
input_lengths = torch.full((3,), 15, dtype=torch.long)
target_lengths = torch.tensor([6,5,10], dtype = torch.long)Recall that one target can be encoded in many different forms. So we introduce a targets mat to represent it as follows.
target_prime = targets.new_full((2 * target_length + 1,), blank) # create a targets_prime full of zero
target_prime[1::2] = targets[i, :target_length] # equivalent to insert blanks in targets. e.g. targets = "dog" --> "-d-o-g-"Now we got target_prime(also expanded target) for e.g. "apple"
target_prime is
tensor([ 0, 1, 0, 16, 0, 16, 0, 12, 0, 5, 0]) which is visualized as the red part(also t1)
Note that the t8 is only for illustration. In the example, the width of target matrix should be 15(input_length).
probs = log_probs[:input_length, i].exp()Then we convert original inputs from log-space like this, referring to "In practice, the above recursion ..." in original paper https://www.cs.toronto.edu/~graves/icml_2006.pdf
# alpha matrix init at t1 indicated by purple boxes.
alpha_col = log_probs.new_zeros((target_length * 2 + 1,))
alpha_col[0] = probs[0, blank] # refers to green box
alpha_col[1] = probs[0, target_prime[1]]- blank is the index of blank(here it's 0)
- target_prime[1] refers to the 1-st index of the token. e.g. "apple": "a", "orange": "o"
refer to the details in CTC.py