連結時序分類(CTC)
選讀・PR 06・模板比對與結構化辨識 的補充資料(第 1/1 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
語音辨識器聽到 200 個音框(frame),要寫出「cat」,卻沒有人標出哪一個音框是「c」。CTC 讓網路在每個音框上說出一個字母,或是「還沒有新東西」(空白,blank),然後把所有讀出來等於該逐字稿的逐幀情境全部加總,作為這份逐字稿的分數。它就是把發射模型換成網路輸出的 HMM 前向演算法 [20]。
設 是含 個音框的輸入, 是標籤字母表加上空白 , 是網路在第 幀對符號 給出的機率(由 算出的 softmax 輸出)。一個對齊(alignment) 替每一幀指定一個符號,扮演的是 HMM 中隱藏狀態序列的角色。CTC 假設在給定 時各幀的輸出彼此獨立,因此
收合映射(collapsing map) 先合併連續重複的符號,再刪除空白,例如 。空白正是讓連續兩個相同字母成為可能的關鍵:,但 。標籤序列 的機率與訓練損失為
其中加總涵蓋所有收合後等於 的對齊, 是要最小化的損失函數。這類對齊的數量隨 呈指數成長,所以和 HMM 前向演算法一樣改用動態規劃。把擴充標籤序列(extended label sequence) 寫成長度 :在標籤之前、之間與之後都插入空白,即 。令 為前 幀被讀成 前 個符號、且第 幀位於位置 的總機率,則
其中索引落在 之外時 ,且其餘 。三項分別代表「停在同一個符號」、「前進一格」與「跳過一個空白」;指示函數只允許在兩個不同的標籤之間跳過空白,因為在相同標籤之間跳過會讓它們合併成一個。最後 ,因為對齊可以結束在最後一個標籤,也可以結束在最末的空白。計算成本是 。方向相反的後向遞迴可求得梯度,不過實務上直接對前向計算做自動微分就夠了。
解碼。 貪婪(最佳路徑)解碼在每一幀取機率最大的符號,再套用 ;它成本很低,但不一定得到機率最高的標籤序列,因為該序列的機率是許多對齊的加總 [20]。前綴束搜尋(prefix beam search)則是逐幀擴張標籤前綴,對每個前綴分別記錄「以空白結尾」與「以標籤結尾」的機率(使收合後得到同一前綴的對齊得以合併),並且只保留最好的 個前綴;[20] 的精確前綴搜尋(prefix search)是同一個想法,只是沒有束寬限制。
下面的程式在 5 幀的玩具範例上實作此遞迴,符號為空白、「a」(1)與「b」(2),並與列舉全部 種對齊的暴力法互相核對。
程式碼 · Python · 57 行
import itertools
import numpy as np
rng = np.random.default_rng(1)
T, V = 5, 3 # 5 frames; symbols 0 = blank, 1 = "a", 2 = "b"
logits = rng.normal(size=(T, V))
probs = np.exp(logits) / np.exp(logits).sum(axis=1, keepdims=True) # probs[t, k] = p(k | x, t)
def collapse(path):
"""The map B: merge repeats, then drop blanks."""
out = [k for i, k in enumerate(path) if i == 0 or k != path[i - 1]]
return tuple(k for k in out if k != 0)
def ctc_forward(probs, y):
"""p(y | x) by the alpha recursion over the blank-extended label sequence."""
ext = [0]
for k in y:
ext += [k, 0] # blank, y1, blank, y2, ..., yL, blank
T, S = len(probs), len(ext)
if T == 0:
return float(len(y) == 0)
alpha = np.zeros((T, S))
alpha[0, 0] = probs[0, 0]
if S > 1:
alpha[0, 1] = probs[0, ext[1]]
for t in range(1, T):
for s in range(S):
a = alpha[t - 1, s] + (alpha[t - 1, s - 1] if s >= 1 else 0.0)
if s >= 2 and ext[s] != 0 and ext[s] != ext[s - 2]:
a += alpha[t - 1, s - 2] # skip a blank only between different labels
alpha[t, s] = a * probs[t, ext[s]]
return alpha[-1, -1] + (alpha[-1, -2] if S > 1 else 0.0)
assert np.isclose(ctc_forward(probs, ()), np.prod(probs[:, 0]))
assert ctc_forward(probs[:2], (1, 1)) == 0.0 # two frames cannot spell "aa"
assert ctc_forward(probs[:0], ()) == 1.0
assert ctc_forward(probs[:0], (1,)) == 0.0
# Brute force: enumerate all V**T = 243 alignments and group them by B(path).
paths = list(itertools.product(range(V), repeat=T))
for y in [(1, 2), (1, 1)]:
good = [p for p in paths if collapse(p) == y]
brute = sum(np.prod([probs[t, k] for t, k in enumerate(p)]) for p in good)
fwd = ctc_forward(probs, y)
assert np.isclose(fwd, brute)
print(f"y={y}: {len(good)} alignments, brute={brute:.6f}, forward={fwd:.6f}, loss={-np.log(fwd):.4f}")
best = tuple(int(k) for k in probs.argmax(axis=1)) # greedy (best-path) decoding
print("greedy path:", best, "->", collapse(best))
# Exact best label sequence by grouping all alignments (feasible only for tiny T).
score = {}
for p in paths:
score[collapse(p)] = score.get(collapse(p), 0.0) + np.prod([probs[t, k] for t, k in enumerate(p)])
top = max(score, key=score.get)
print("best label sequence:", top, "p =", round(score[top], 6))
print("greedy sequence p :", round(score[collapse(best)], 6))目標為「ab」時,243 種對齊中有 35 種收合成它,前向遞迴與暴力法都得到 ,損失為 1.6914。目標為「aa」時,只有 15 種對齊符合,因為每一種都必須在兩個字母之間放一個空白;,損失為 2.9204。貪婪解碼選出的路徑是 ,收合後是「aba」;對標籤序列做窮舉搜尋得到的最佳結果同樣是「aba」,,所以兩者在這個玩具範例上一致,但一般情況下並不保證。
空轉錄也是合法的邊界情況:每個影格都必須輸出空白,所以機率為 。程式把它和無法對齊的非空轉錄分開處理,並檢查兩者。這個小例子直接在機率空間計算;長序列應使用縮放或對數空間的遞迴,避免下溢。
假設失效的時候。 條件獨立表示第 幀的輸出不能參考模型先前輸出了什麼,只能透過網路內部的特徵間接得知;語言知識必須來自編碼器的上下文,或在解碼時結合外部語言模型,而把先前標籤回饋到預測中的模型則放棄了這個假設。單調對齊表示輸出順序必須跟隨輸入順序,因此無法處理順序會改變的任務,例如翻譯。它還要求足夠的幀數:至少是 加上相鄰相同標籤的個數,所以「aa」需要 ;輸入更短時 ,損失為無窮大。
參考文獻
- S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2009, Chapters 8 and 9. publisher page
- C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, Sections 8.1–8.4 and 13.1–13.3. official book page and PDF
- J. P. Lewis, “Fast Normalized Cross-Correlation,” Vision Interface, 1995. paper
- N. S. Hashemi, R. B. Aghdam, A. S. B. Ghiasi, and P. Fatemi, “Template Matching Advances and Applications in Image Analysis,” arXiv:1610.07231, 2016. arXiv
- H. Sakoe and S. Chiba, “Dynamic Programming Algorithm Optimization for Spoken Word Recognition,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 26, no. 1, pp. 43–49, 1978. doi:10.1109/TASSP.1978.1163055
- T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh, “Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping,” Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 262–270, 2012. doi:10.1145/2339530.2339576
- R. A. Wagner and M. J. Fischer, “The String-to-String Correction Problem,” Journal of the ACM, vol. 21, no. 1, pp. 168–173, 1974. doi:10.1145/321796.321811
- D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty Years of Graph Matching in Pattern Recognition,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 18, no. 3, pp. 265–298, 2004. doi:10.1142/S0218001404003228
- P. Foggia, G. Percannella, and M. Vento, “Graph Matching and Learning in Pattern Recognition in the Last 10 Years,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 28, no. 1, 1450001, 2014. doi:10.1142/S0218001414500013
- L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition,” Proceedings of the IEEE, vol. 77, no. 2, pp. 257–286, 1989. doi:10.1109/5.18626
- A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Transactions on Information Theory, vol. 13, no. 2, pp. 260–269, 1967. doi:10.1109/TIT.1967.1054010
- L. E. Baum, T. Petrie, G. Soules, and N. Weiss, “A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains,” The Annals of Mathematical Statistics, vol. 41, no. 1, pp. 164–171, 1970. doi:10.1214/aoms/1177697196
- R. E. Kalman, “A New Approach to Linear Filtering and Prediction Problems,” Journal of Basic Engineering, vol. 82, no. 1, pp. 35–45, 1960. doi:10.1115/1.3662552
- J. D. Lafferty, A. McCallum, and F. C. N. Pereira, “Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data,” Proceedings of the 18th International Conference on Machine Learning (ICML), pp. 282–289, 2001. paper page
- C. Sutton and A. McCallum, “An Introduction to Conditional Random Fields,” Foundations and Trends in Machine Learning, vol. 4, no. 4, pp. 267–373, 2012. doi:10.1561/2200000013
- A. Bagnall, J. Lines, A. Bostrom, J. Large, and E. Keogh, “The Great Time Series Classification Bake Off: A Review and Experimental Evaluation of Recent Algorithmic Advances,” Data Mining and Knowledge Discovery, vol. 31, pp. 606–660, 2017. doi:10.1007/s10618-016-0483-9
- M. Middlehurst, P. Schäfer, and A. Bagnall, “Bake Off Redux: A Review and Experimental Evaluation of Recent Time Series Classification Algorithms,” Data Mining and Knowledge Discovery, vol. 38, pp. 1958–2031, 2024. doi:10.1007/s10618-024-01022-1
- H. Ismail Fawaz, G. Forestier, J. Weber, L. Idoumghar, and P.-A. Muller, “Deep Learning for Time Series Classification: A Review,” Data Mining and Knowledge Discovery, vol. 33, pp. 917–963, 2019. doi:10.1007/s10618-019-00619-1
- M. Cuturi and M. Blondel, “Soft-DTW: A Differentiable Loss Function for Time-Series,” ICML, 2017. arXiv:1703.01541
- A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber, “Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks,” Proceedings of the 23rd International Conference on Machine Learning (ICML), pp. 369–376, 2006. doi:10.1145/1143844.1143891
- P. Krähenbühl and V. Koltun, “Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials,” NIPS, 2011. arXiv:1210.5644
- S. Zheng, S. Jayasumana, B. Romera-Paredes, V. Vineet, Z. Su, D. Du, C. Huang, and P. H. S. Torr, “Conditional Random Fields as Recurrent Neural Networks,” ICCV, 2015. arXiv:1502.03240
- G. Lample, M. Ballesteros, S. Subramanian, K. Kawakami, and C. Dyer, “Neural Architectures for Named Entity Recognition,” NAACL, 2016. arXiv:1603.01360
- A. Gu and T. Dao, “Mamba: Linear-Time Sequence Modeling with Selective State Spaces,” arXiv:2312.00752, 2023. arXiv