序列建模

相关专题

Index

序列建模简述

序列建模就是将一个输入/观测序列映射到一个输出/标记序列
《统计学习方法》中称之为标注问题
在传统机器学习方法中，常用的模型有：隐马尔可夫模型（HMM），条件随机场（CRF）等
机器学习专题 TODO
在深度学习领域的很长一段时间里，RNN/LSTM 都是序列建模的首选。
《深度学习》 10 序列建模：循环和递归网络
最近，CNN 开始在序列建模领域流行，一个关键想法是——在一维时间序列上使用一维卷积运算

Seq2Seq

上图是一次机器翻译的过程，输入是一个源语言的一个句子 "A B C"，Encoder 一次读入每个单词直到结束符 <EOS>（End of Sequence）；在解码的第一步，Decoder 先读取 Encoder 的最终状态，生成目标语言的第一个词 'W'，接着 Decoder 读取第一步的输出 'W' 作为第二步的输入，进而生成第二个词 'X'，如此直到生成 <EOS> 或达到指定最大长度。
Decoder 生成每个词还要结合当前时间步的隐状态（如果是 LSTM 还有记忆状态），更深入的细节暂时略过。
Seq2Seq 之所以流行，是因为它为不同的问题提供了一套端到端（End to End）的解决方案，免去了繁琐的中间步骤，从输入直接得到结果.
根据任务的输入输出差异，编码器和解码器的设计也不尽相同，但是“Encoder-Decoder”的结构都是一致的。
- 机器翻译：输入源语言的一个句子，输出目标语言的句子；
- 机器问答：输入问题/查询，输出答案；
- 文本摘要：输入一个长句或段落，输出一个摘要短句；
- 语音识别：输入是音频序列信号，输出为识别出的文本；
- 图像描述：输入是图像经过视觉网络的特征，输出是图像的描述文本。
- ...

解码方法（贪心、Beam Search、维特比算法）

Seq2Seq 中的解码方法主要有三种：贪心、Beam Search、维特比算法（动态规划）
这三种方法的思想本质上是一致的，假设选取相同的评价标准（比如概率最大、路径最短等）
- 贪心每到达一个节点，只选择当前状态的最优结果，其他都忽略，直到最后一个节点；贪心法只能得到某个局部最优解；
- Beam Search 会在每个节点保存当前最优的 k 个结果（排序后），其他结果将被“剪枝”，因为每次都有 k 个分支进入下一个状态。Beam Search 也不能保证全局最优，但能以较大的概率得到全局最优解。
- 维特比算法利用动态规划的方法可以保证得到全局最优解，但是当候选状态极大时，需要消耗大量的时间和空间搜索和保存状态，因此维特比算法只适合状态集比较小的情况。

Beam Search（集束搜索）

Beam Search 是一种启发式算法
该方法会保存前 beam_size 个最佳状态，每次解码时会根据所有保存的状态进行下一步扩展和排序，依然只保留前 beam_size 个最佳状态；循环迭代至最后一步，保存最佳选择。
当 beam_size = 1 时，Beam Search 即退化为贪心搜索
一般为了计算资源和性能的平衡，beam_size 会选择一个适中的范围；通常 beam_size 取 8~12 即可（机器翻译、文本摘要）

维特比（Viterbi）算法 TODO

利用动态规划可以求解任何图中的最短路径问题；
维特比算法是针对一种特殊的图结构——“篱笆网络”——而提出的算法，用于在概率图模型中求解概率最大路径；

其他最短路径算法

Dijkstra 算法（迪杰斯特拉算法）
- 基于贪心
- 用于求解某个顶点到其他所有顶点之间的最短路径
- 时间复杂度 O(N^2)
- Dijkstra 算法的使用范围比 Viterbi 算法更广，可用于求解大部分图结构中的最短路径。
Floyd 算法（弗洛伊德算法）
- 求解的是每一对顶点之间的最短路径
- 时间复杂度 O(N^3)