概述
背景
在实际的序列学习场景中经常会遇到从没有切分的，带有噪音的数据中对序列的label进行预测，例如语音识别中需要将声学信号转换成words或者是 sub-words.
文章提出了一种新的rnn训练方法，可以将没有切分的序列生成相应的标签。
传统方法的问题
传统方法中常用的HMM,CRF等有一些可以较好的解决这种序列标注问题，但是它们也存在相应的问题：
- 通常需要大量的领域相关知识，例如定义相关的label，选择crf的输入特征等等。
- 需要基于一定的相关性假设，例如HMM中观察序列之间是相互独立的。
- 对HMM 来说训练是产生式的，即使序列标注问题是一个判别问题。
RNN的优势
- 不需要任何关于数据的先验知识，除了选择定义输入和输出的格式。
- 具有强大的特征表达能力，能够很好的对问题进行建模，并且可以表示判别式模型。
- 对于噪音问题处理的更加鲁棒。
- 可以利用long-range seququence 建模。
效果
效果优于hmm和hmm-rnn模型。
具体思路
将网络的输出表示为所有可能的label序列的概率分布，有了这个概率分布可以定义目标函数为直接最大化正确的label序列的概率。
因为目标函数可导，所以可以用标准的bp方法进行训练。
Temporal Classification
记号
$S$表示从一个分布$D_{X \times Z}$提取的训练样本
输入空间$X = (Rm)*$ 是所有的$m$维的实数向量。
目标空间 $Z = L ^* $ 是所有的Label（有限的）组成的序列空间。
我们称$L^*$中的元素为label sequences 或labellings。
任意的一个样本$s \in S,s= (x,z)$,
目标序列$z = (z_1, z_2, ..., z_U)$,
输入序列$x = (x_1, x_2,...,x_T)$
其中$U <= T$
目标是用$S$来训练一个temporal classifier s.t. $h: X -> Z$
Label Error Rate
度量错误
给定一个测试集$S^\prime \subset D_{X \times Z}$
定义$h$的标签错误率（LER = Label Error Rate)为$S ^ \prime$数据集上的标准化的 分类结果和目标之间的编辑距离。
\begin{equation}
LER(h,S^\prime) = {1 \over {|S ^ \prime|}} \sum _{(x, z) \in S ^ \prime} { {ED(h(x),z)} \over {|z|} }
\label{eq:defLER}
\end{equation}
其中$ED(p,q)$是sequence$p,q$之间的编辑距离。（插入，替换和删除）
Connectionist Temporal Classification
介绍了如何表示RNN的输出可以用来做CTC,最直接的想法是将RNN的输出表示为一个给定的输入的关于Label sequences的条件概率分布
网络输出到标签序列
CTC网络有一个softmax输出层，
输出层有$|L| + 1$个输出单元，
其中$|L|$指的是label的个数，
1代表空格或其他非label的输出。
具体形式
首先定义初步的映射关系
输入序列$X,|X| = T$
RNN $m$个输入，$n$个输出($n = |L| + 1$)和权重向量$w$ as \space a \space continuous \space map :
$N_w ： (R^m) ^ T -> (R^n) ^ T$
定义$y = N_w(x)$是神经网络从输出，并且$y_k ^ t$是第$k$个单元的在时间$t$时的激活值
即label $k$在时间$t$概率,则有长度$T$的序列关于$L ^ \prime = L \bigcup \{blank\}$概率为：
\begin{equation}
p(\pi | X) = \prod _ {t = 1} ^ T y_{\pi _t} ^ t, \forall \pi \in {L ^ \prime } ^ T
\label{eq:ctcSeqProb}
\end{equation}
定义一个多对一的映射
映射形式如下:
$\beta : (L ^ \prime )^T -> L {<=T}$,$L{<= T}$是可能的标签
具体步骤:
将所有的空格和重复的标签从路径中移除，例如
$\beta (a\ab\)= \beta (\aa\\abb) = aa$,其中代表空格
计算关于$l \in L^ {<= T}$的条件概率
\begin{equation}
p(l|x) = \sum _ {\pi \in \beta ^ {-1}(l)} p (\pi | x)
\label{eq:binverseprob}
\end{equation}
构建分类器
有了以上的计算方法，分类器的输出应该是对输入生成的标注可能性最大的一个序列。
\begin{equation}
h(x) = arg max _ {l \in L ^{\leq T}} p(l | x)
\label{eq:targetFunction}
\end{equation}
此过程可以借鉴传统的叫法decoding，但是目前还没有一个通用的，tractable的解码算法。
目前常用以下两种 近似的方法 来做解码：
第一种解码方法（Best Path Decoding)
思路：假设最可能的路径（$\pi$）往往和最可能的labeling相关：
\begin{equation}
h(x) \approx \beta(\pi ^ )
\label{eq:decodeMethod1}
\end{equation}
其中：$\pi ^ = arg max _ {\pi \in N^t} p (\pi | x)$
此方法简单易于实现，而且找到的是在各个时间点的激活值最大的值，但是不能保证找到的是最有可能的label序列。
第二种解码方法(Prefix Search Decoding)
类似于前后向算法基础上进行，具体见第四章（下一章训练网络部分）
这种方法只要时间足够往往可以找到最优的结果，但是解码时间跟序列长度成指数增长。
通常使用启发式的解码方法。
启发式的思路如下：
首先根据输出中预测是blank的节点进行切分，然后分段进行prefix 查找。
缺陷
通常情况下启发式的方法工作的很好，并且能够找到最优的路径，但是在一些情况下会出错，例如在一个分割点的两端两者的预测label都相同，而且概率较小。
训练网络
CTC前后向算法
我们需要一个高效的方式来计算$p(l|x)$,但是参考公式 \ref{eq:binverseprob} 会发现这是一个难以计算的任务。
本文引入了动态规划的方法，类似于hmm中的前后向算法，如下：
一个序列$q$,长度为$r$,记为$q_{1:p}$ 和$q_{r-p, r}$作为它的最前和最后的$p$的标记。
对一个labeling序列 $l$,定义前向变量$ \alpha _ t (s) = \sum _ {\pi \in N^T:\beta(\pi_{1:t})=l_{1:s}} \prod _ {t ^\prime = 1} ^ t y _ {\pi _ {t ^ \prime}} ^ {t ^ \prime} $
（前s个label由前t个观察序列生成的概率，应该s<=t）
对序列在处理一下对序列$l$前后及中间增加一个blank，则$l-> l^\prime,长度为2|l|+1$
（此时应该$s< |l^\prime| - 2(T-t)-1$）
则有以下等式成立
$$
\alpha 1 (1) = y_b ^ 1 \
\alpha _ 1 (2) = y{l _ 1} ^ 1 \
\alpha _ 1 (s) = 0, {\forall s > 2}
$$
并且有递归形式如下：
\begin{equation}
\alpha_t(s) =
\begin{cases}
(\alpha_{t-1}(s) + \alpha_{t - 1}(s - 1))y_{l_s ^ \prime} ^ t, & \text {$if \space l ^ \prime _ s = b \space or \space l ^ \prime _ {s - 2} = l _ s ^ \prime$} \
(\alpha_{t-1}(s) + \alpha_{t - 1}(s - 1) + \alpha _ {t - 1} (s - 2)) y_{l_s ^ \prime} ^ t, & \text {otherwise}
\end{cases}
\label{eq:recurrForward}
\end{equation}
其中 $y_k ^ t$是第$k$个单元的在时间$t$时的激活值
即label $k$在时间$t$概率,则有长度$T$的序列关于$L ^ \prime = L \bigcup \{blank\}$概率
解释
状态序列$b,l_1,b,l_2,b,l_3,...,b,l_k,b$
- 当前状态为blank
则当前状态可以由 前一个状态是blank（$\alpha _{t - 1} (s)$)或者前一个状态是状态序列中的前一个状态（$\alpha _{t - 1} (s - 1)$转移而来 - 当前状态和两步前的状态相同
则当前状态可以由前一个状态是blank（$\alpha _{t - 1} (s)$)和前一个状态跟两步前相同的状态（$\alpha _{t - 1} (s - 1)$转移而来 - 其余的情况有三条转移途径
当前状态不为空，而且前两步的状态和当前状态不同- 两步前状态不为空
则当前状态可以由中间状态为两步前状态，空和当前状态三条路径转移而来。 - 两步前状态为空
则当前状态可以由中间状态为空，中间状态为状态序列中两步前状态和中间状态为当前状态转移而来。
- 两步前状态不为空
定义前向算法
参考文献
minimum edit distance
Temporal classification Extending the classification paradigm to multivariate time series
Supervised Sequence Labelling with Recurrent Neural Networks 第7章
