目錄
簡介
算法詳解
1.1 對齊
1.2 損失函數
1.3 預測
1.3.1 Greedy Search
1.3.2 Beam Search
CTC的特征
參考知識
簡介
在語音識别中，我們的資料集是音頻檔案和其對應的文本，不幸的是，音頻檔案和文本很難再單詞的機關上對齊。除了語言識别，在OCR，機器翻譯中，都存在類似的Sequence to Sequence結構，同樣也需要在預處理操作時進行對齊，但是這種對齊有時候是非常困難的。如果不使用對齊而直接訓練模型時，由于人的語速的不同，或者字元間距離的不同，導緻模型很難收斂。
CTC(Connectionist Temporal Classification)是一種避開輸入與輸出手動對齊的一種方式，是非常适合語音識别或者OCR這種應用的。
圖1：CTC用于OCR(左)和語音識别(右）
給定輸入序列
以及對應的标簽資料
例如語音識别中的音頻檔案和文本檔案。我們的工作是找到
到
的一個映射，這種對時序資料進行分類的算法叫做Temporal Classification。
這種對時序資料進行分類的算法叫做Temporal Classification。
對比傳統的分類方法，時序分類有如下難點：
- 和
CTC相關知識簡介算法詳解參考知識 的長度都是變化的； CTC相關知識簡介算法詳解參考知識 - 和
CTC相關知識簡介算法詳解參考知識 的長度是不相等的； CTC相關知識簡介算法詳解參考知識 - 對于一個端到端的模型，我們并不希望手動設計 和
CTC相關知識簡介算法詳解參考知識 的之間的對齊。 CTC相關知識簡介算法詳解參考知識
CTC提供了解決方案，對于一個給定的輸入序列
，CTC給出所有可能的
的輸出分布。根據這個分布，我們可以輸出最可能的結果或者給出某個輸出的機率。
損失函數：給定輸入序列
,我們希望最大化
的後驗機率
,
是可導的，測試：給定一個訓練好的模型和輸入序列
,我們希望輸出機率最高的
:
算法詳解
給定輸入
,CTC輸出每個可能輸出及其條件機率，問題的關鍵是CTC的輸出機率是如何考慮
和
之間是如何對齊的，這種對齊也是建構損失函數的基礎。是以，首先我們分析CTC的對齊方式，然後我們在分析CTC的損失函數的構造。
1.1 對齊
需要注意的是，CTC本身是不需要對齊的，但是我們需要知道
的輸出路徑和最終輸出結果的對應關系，因為在CTC中，多個輸出路徑可能對應一個輸出結果，舉例來了解。例如在OCR的任務中，輸入
是含有“CAT”的圖檔，輸出
是文本[C, A, T]。将
分割成若幹個時間片，每個時間片得到一個輸出，一個最簡答的解決方案是合并連續重複出現的字母，如圖2.
圖2：CTC的一種原始對齊政策
這個問題有兩個缺點：
- 幾乎不可能将 的每個時間片都和輸出Y對應上，例如OCR中字元的間隔，語音識别中的停頓
CTC相關知識簡介算法詳解參考知識 - 不能處理有連續重複字元出現的情況，例如單詞"HELLO",按照上面的算法，輸出的是“”HELO"而非"HELLO"
為了解決上面的問題，CTC引入了空白字元
，例如OCR中的字元間距，語音識别中的停頓都可以表示為
。是以，CTC的對齊涉及去除重複字母和去除
兩部分，如圖3
圖三：CTC的對齊政策
這種對齊方式有三個特征
- 與Y之間的時間片映射是單調的，即如果
CTC相關知識簡介算法詳解參考知識 向前移動一個時間片，Y保持不動或者也向前移動一個時間片 CTC相關知識簡介算法詳解參考知識 - X與Y之間的映射是多對一的，即多個輸出可能對應一個映射，反之則不成立，這樣就有了特征三
- X的長度大于或者等于Y的長度。
1.2 損失函數
CTC的時間片的輸出和輸出序列的映射如圖4：
圖4：CTC的流程
也就是說，對應标簽Y，其關于輸入X的後驗機率可以表示為所有映射為Y的路徑之和，我們的目标就是最大化Y關于x=y的後驗機率
。假設每個時間片的輸出是獨立的，則路徑的後延機率是每個時間片機率的累積，公式及其詳細含義如圖5.
圖5：CTC的公式及其詳細含義
上面的CTC算法存在性能問題，對于一個時間片長度為T的N分類任務，所有可能的路徑數為
,，在很多情況下，這幾乎是一個宇宙級别的數字，用于計算Loss幾乎是不現實的。在CTC中采用了動态規劃的思想來對查找路徑進行剪枝，算法的核心思想是如果路徑
和
在時間片t之前的輸出均相等，我們就可以提前合并他們，，如圖6。
圖6：CTC的動态規劃計算輸出路徑
其中，橫軸的機關是X的時間片，縱軸的機關是Y插入
的序列Z。例如對于單詞“ZOO”,插入
後為：
我們用
表示路徑中已經合并的在橫軸機關為t,縱軸機關為s的節點。根據CTC對齊方式的三個特征，輸入有9個時間片，标簽内容為"ZOO",
的所有可能的合法路徑如下圖所示
圖7：CTC中單詞ZOO的所有合法路徑
上圖分成兩種情況
Case1:
現在，我們已經可以高效的計算損失函數，下一步的工作便是計算梯度用于訓練模型。由于
的計算隻涉及加法和乘法，是以其一定是可導函數，進而我們可以使用SGD優化模型。
對于資料集D,模型的優化目标是最小化負對數似然
1.3 預測
當我們訓練好一個RNN模型時，給定一個輸入序列X,
我們需要找到最可能的輸出，也就是求解
Y* = argmaxp(Y|X)
求解最可能的輸出有兩種方案，一種是Greedy Search，第二種是beam search
1.3.1 Greedy Search
每個時間片均取該時間片機率最高的節點作為輸出：
這個方法最大的缺點是忽略了一個輸出可能對應多個對齊方式.
代碼
def remove_blank(labels, blank=0):
import numpy as np
# 求每一列(即每個時刻)中最大值對應的softmax值
def softmax(logits):
# 注意這裡求e的次方時，次方數減去max_value其實不影響結果，因為最後可以化簡成教科書上softmax的定義
# 次方數加入減max_value是因為e的x次方與x的極限(x趨于無窮)為無窮，很容易溢出，是以為了計算時不溢出，就加入減max_value項
# 次方數減去max_value後，e的該次方數總是在0到1範圍内。
max_value = np.max(logits, axis=1, keepdims=True)
exp = np.exp(logits - max_value)
exp_sum = np.sum(exp, axis=1, keepdims=True)
dist = exp / exp_sum
return dist
def remove_blank(labels, blank=0):
new_labels = []
# 合并相同的标簽
previous = None
for l in labels:
if l != previous:
new_labels.append(l)
previous = l
# 删除blank
new_labels = [l for l in new_labels if l != blank]
return new_labels
def insert_blank(labels, blank=0):
new_labels = [blank]
for l in labels:
new_labels += [l, blank]
return new_labels
def greedy_decode(y, blank=0):
# 按列取最大值，即每個時刻t上最大值對應的下标
raw_rs = np.argmax(y, axis=1)
# 移除blank,值為0的位置表示這個位置是blank
rs = remove_blank(raw_rs, blank)
return raw_rs, rs
np.random.seed(11)
y_test = softmax(np.random.random([30,10]))
label_have_blank, label_no_blank = greedy_decode(y_test)
print(label_have_blank)
print(label_no_blank)
1.3.2 Beam Search
Beam Search是尋找全局最優值和Greedy Search在查找時間和模型精度的一個折中。一個簡單的beam search在每個時間片計算所有可能假設的機率，并從中選出最高的幾個作為一組。然後再從這組假設的基礎上産生機率最高的幾個作為一組假設，依次進行，直到達到最後一個時間片，下圖是beam search的寬度為3的搜尋過程，紅線為選中的假設
代碼
import numpy as np
# 求每一列(即每個時刻)中最大值對應的softmax值
def softmax(logits):
# 注意這裡求e的次方時，次方數減去max_value其實不影響結果，因為最後可以化簡成教科書上softmax的定義
# 次方數加入減max_value是因為e的x次方與x的極限(x趨于無窮)為無窮，很容易溢出，是以為了計算時不溢出，就加入減max_value項
# 次方數減去max_value後，e的該次方數總是在0到1範圍内。
max_value = np.max(logits, axis=1, keepdims=True)
exp = np.exp(logits - max_value)
exp_sum = np.sum(exp, axis=1, keepdims=True)
dist = exp / exp_sum
return dist
def remove_blank(labels, blank=0):
new_labels = []
# 合并相同的标簽
previous = None
for l in labels:
if l != previous:
new_labels.append(l)
previous = l
# 删除blank
new_labels = [l for l in new_labels if l != blank]
return new_labels
def insert_blank(labels, blank=0):
new_labels = [blank]
for l in labels:
new_labels += [l, blank]
return new_labels
def beam_decode(y, beam_size=10):
# y是個二維數組，記錄了所有時刻的所有項的機率
T, V = y.shape
# 将所有的y中值改為log是為了防止溢出，因為最後得到的p是y1..yn連乘，且yi都在0到1之間，可能會導緻下溢出
# 改成log(y)以後就變成連加了，這樣就防止了下溢出
log_y = np.log(y)
# 初始的beam
beam = [([], 0)]
# 周遊所有時刻t
for t in range(T):
# 每個時刻先初始化一個new_beam
new_beam = []
# 周遊beam
for prefix, score in beam:
# 對于一個時刻中的每一項(一共V項)
for i in range(V):
# 記錄添加的新項是這個時刻的第幾項，對應的機率(log形式的)加上新的這項log形式的機率(本來是乘的，改成log就是加)
new_prefix = prefix + [i]
new_score = score + log_y[t, i]
# new_beam記錄了對于beam中某一項，将這個項分别加上新的時刻中的每一項後的機率
new_beam.append((new_prefix, new_score))
# 給new_beam按score排序
new_beam.sort(key=lambda x: x[1], reverse=True)
# beam即為new_beam中機率最大的beam_size個路徑
beam = new_beam[:beam_size]
return beam
np.random.seed(11)
y_test = softmax(np.random.random([30, 10]))
beam_chosen = beam_decode(y_test, beam_size=100)
for beam_string, beam_score in beam_chosen[:20]:
print(remove_blank(beam_string), beam_score)
1.3.3 prefix Beam search
最簡單的decode方式當然是最近拿每個frame的最大機率的token，但實際應用中這種方法字錯率會頗高，且無法和語言模型結合。要與語言模型結合，必須有多個candidate，但也不能夠窮盡每個frame每個token的組合，故有beam search。但beam search的candidate會有很多相同的部分，是以有了Prefix beam search。
綴束搜尋（Prefix Beam Search）方法，可以在搜尋過程中不斷的合并相同的字首。
具體較複雜，不過讀者弄懂beam search後再想想prefix beam search的流程不是很難，主要弄懂probabilityWithBlank和probabilityNoBlank分别代表最後一個字元是空格和最後一個字元不是空格的機率即可。
import numpy as np
from collections import defaultdict
ninf = float("-inf")
# 求每一列(即每個時刻)中最大值對應的softmax值
def softmax(logits):
# 注意這裡求e的次方時，次方數減去max_value其實不影響結果，因為最後可以化簡成教科書上softmax的定義
# 次方數加入減max_value是因為e的x次方與x的極限(x趨于無窮)為無窮，很容易溢出，是以為了計算時不溢出，就加入減max_value項
# 次方數減去max_value後，e的該次方數總是在0到1範圍内。
max_value = np.max(logits, axis=1, keepdims=True)
exp = np.exp(logits - max_value)
exp_sum = np.sum(exp, axis=1, keepdims=True)
dist = exp / exp_sum
return dist
def remove_blank(labels, blank=0):
new_labels = []
# 合并相同的标簽
previous = None
for l in labels:
if l != previous:
new_labels.append(l)
previous = l
# 删除blank
new_labels = [l for l in new_labels if l != blank]
return new_labels
def insert_blank(labels, blank=0):
new_labels = [blank]
for l in labels:
new_labels += [l, blank]
return new_labels
def _logsumexp(a, b):
'''
np.log(np.exp(a) + np.exp(b))
'''
if a < b:
a, b = b, a
if b == ninf:
return a
else:
return a + np.log(1 + np.exp(b - a))
def logsumexp(*args):
'''
from scipy.special import logsumexp
logsumexp(args)
'''
res = args[0]
for e in args[1:]:
res = _logsumexp(res, e)
return res
def prefix_beam_decode(y, beam_size=10, blank=0):
T, V = y.shape
log_y = np.log(y)
# 最後一個字元是blank與最後一個字元為non-blank兩種情況
beam = [(tuple(), (0, ninf))]
# 對于每一個時刻t
for t in range(T):
# 當我使用普通的字典時，用法一般是dict={},添加元素的隻需要dict[element] =value即可，調用的時候也是如此
# dict[element] = xxx,但前提是element字典裡，如果不在字典裡就會報錯
# defaultdict的作用是在于，當字典裡的key不存在但被查找時，傳回的不是keyError而是一個預設值
# dict =defaultdict( factory_function)
# 這個factory_function可以是list、set、str等等，作用是當key不存在時，傳回的是工廠函數的預設值
# 這裡就是(ninf, ninf)是預設值
new_beam = defaultdict(lambda: (ninf, ninf))
# 對于beam中的每一項
for prefix, (p_b, p_nb) in beam:
for i in range(V):
# beam的每一項都加上時刻t中的每一項
p = log_y[t, i]
# 如果i中的這項是blank
if i == blank:
# 将這項直接加入路徑中
new_p_b, new_p_nb = new_beam[prefix]
new_p_b = logsumexp(new_p_b, p_b + p, p_nb + p)
new_beam[prefix] = (new_p_b, new_p_nb)
continue
# 如果i中的這一項不是blank
else:
end_t = prefix[-1] if prefix else None
# 判斷之前beam項中的最後一個元素和i的元素是不是一樣
new_prefix = prefix + (i,)
new_p_b, new_p_nb = new_beam[new_prefix]
# 如果不一樣，則将i這項加入路徑中
if i != end_t:
new_p_nb = logsumexp(new_p_nb, p_b + p, p_nb + p)
else:
new_p_nb = logsumexp(new_p_nb, p_b + p)
new_beam[new_prefix] = (new_p_b, new_p_nb)
# 如果一樣，保留現有的路徑，但是機率上要加上新的這個i項的機率
if i == end_t:
new_p_b, new_p_nb = new_beam[prefix]
new_p_nb = logsumexp(new_p_nb, p_nb + p)
new_beam[prefix] = (new_p_b, new_p_nb)
# 給新的beam排序并取前beam_size個
beam = sorted(new_beam.items(), key=lambda x: logsumexp(*x[1]), reverse=True)
beam = beam[:beam_size]
return beam
np.random.seed(11)
y_test = softmax(np.random.random([30, 16]))
beam_test = prefix_beam_decode(y_test, beam_size=100)
for beam_string, beam_score in beam_test[:20]:
print(remove_blank(beam_string), beam_score)
CTC的特征
- 條件獨立：CTC的一個非常不合理的假設是其假設每個時間片都是互相獨立的，這是一個非常不好的假設。在OCR或者語音識别中，各個時間片之間是含有一些語義資訊的，是以如果能夠在CTC中加入語言模型的話效果應該會有提升
- 單調對齊：CTC的另外一個限制是輸入X與輸出Y之間的單調對齊，OCR和語音識别中，這種限制是成立的。但是在一些場景中例如機器翻譯，這個限制便無效了。
- 多對一映射：CTC的又一個限制是輸入序列X的長度大于标簽資料Y的長度，但是對于Y的長度大于X的長度的場景，CTC便失效了。
參考知識
CTC三種搜尋方式
CTC詳解
原出處