概述

背景

在实际的序列学习场景中经常会遇到从没有切分的，带有噪音的数据中对序列的label进行预测，例如语音识别中需要将声学信号转换成words或者是 sub-words.
文章提出了一种新的rnn训练方法，可以将没有切分的序列生成相应的标签。

传统方法的问题

传统方法中常用的HMM,CRF等有一些可以较好的解决这种序列标注问题，但是它们也存在相应的问题：
1. 通常需要大量的领域相关知识，例如定义相关的label，选择crf的输入特征等等。
2. 需要基于一定的相关性假设，例如HMM中观察序列之间是相互独立的。
3. 对HMM 来说训练是产生式的，即使序列标注问题是一个判别问题。

RNN的优势

1. 不需要任何关于数据的先验知识，除了选择定义输入和输出的格式。
2. 具有强大的特征表达能力，能够很好的对问题进行建模，并且可以表示判别式模型。
3. 对于噪音问题处理的更加鲁棒。
4. 可以利用long-range seququence 建模。

效果

效果优于hmm和hmm-rnn模型。

具体思路

将网络的输出表示为所有可能的label序列的概率分布，有了这个概率分布可以定义目标函数为直接最大化正确的label序列的概率。
因为目标函数可导，所以可以用标准的bp方法进行训练。

Temporal Classification

记号

$S$表示从一个分布$D_{X \times Z}$提取的训练样本
输入空间$X = (R^m)^*$ 是所有的$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 a continuous 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个观察序列生成的概率）
对序列在处理一下对序列$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$
1. 当前状态为blank
则当前状态可以由 前一个状态是blank（$\alpha _{t - 1} (s)$)或者前一个状态是状态序列中的前一个状态$\alpha _{t - 1} (s - 1)$转移而来
2. 当前状态和两步前的状态相同
则当前状态可以由前一个状态是blank（$\alpha _{t - 1} (s)$)和前一个状态跟两步前相同的状态$\alpha _{t - 1} (s - 1)$转移而来
3. 其余的情况有三条转移途径
当前状态不为空，而且前两步的状态和当前状态不同
1. 两步前状态不为空
则当前状态可以由中间状态为两步前状态，空或当前状态三条路径转移而来。
2. 两步前状态为空
则当前状态可以由中间状态为空，中间状态为状态序列中两步前状态和中间状态为当前状态转移而来。
示意图如下：

从而有整条序列$l$的概率由$l ^ \prime$最后是空格和最后不是空格求和而来。

$$\begin{equation} p(l|x) = \alpha_T(|l ^\prime|) + \alpha_T(|l ^\prime| - 1) \label{eq:forwardfullProbability} \end{equation}$$

类似可以有后向变量$\beta _ t (s)$

$$\begin{equation} \beta_t(s) = \sum _ {\pi \in N^T: B(\pi_{t:T})=l_{s:|l|} } \prod _{t ^ \prime } ^ T y _{\pi _ {t ^ \prime}} ^ {t ^ \prime} \label{eq:backVariable} \end{equation}$$

其中

$$\beta_ T(|l ^ \prime |) = y_ b ^ T \\\\ \beta_ T (|l ^ \prime | - 1) = y_ {l_ {|l|}} ^ T \\\\ \beta_ T (s) = 0,\forall s < | l ^ \prime| - 1$$

$$\begin{equation} \beta_ t(s) = \begin{cases} {\overline \beta}_ t(s) y_ {l_s ^\prime} ^ t ,& \text{if $l^\prime_ s = b$ or $l ^ \prime_ {s + 2} = l_ s ^ \prime $} \\\\ (\overline \beta_ t (s) + \beta_ {t + 1} (s + 2)) y_ {l_s ^ \prime} ^ t, & \text {otherwise} \end{cases} \label{eq:recurrBackward} \end{equation}$$

并且有

$$\begin{equation} \overline \beta_ t = \beta_ {t + 1}(s) + \beta_ {t + 1}(s + 1) \label{eq:backFullProb} \end{equation}$$
and $\beta_ t (s) = 0 \forall s > 2t$ and $\forall s > |l ^ \prime|$

上述的前后向算法会导致下溢，我们的处理方式是定义如下公式

$$C_t = \sum_ s \alpha_t (s),\hat \alpha_t(s) = {\alpha_t (s) \over C_t}$$
替换( $\ref{eq:recurrForward}$),( $\ref{eq:forwardfullProbability}$)式中的 $\alpha_t$

类似定义后向的计算方式如下：

$$D_t = \sum_ s \beta_t (s),\hat \beta_t(s) = {\beta_t (s) \over D_t}$$
替换( $\ref{eq:recurrBackward}$),( $\ref{eq:backFullProb}$)式中的 $\beta_t$

要计算maximum likelihood error 如下式：

$$ln(p(l|x)) = \sum _ {t = 1} ^ T ln(C_t)$$

参考文献

minimum edit distance
Temporal classification Extending the classification paradigm to multivariate time series
Supervised Sequence Labelling with Recurrent Neural Networks 第7章