[TOC]
第15章序列生成笔记，阐述了语言模型学习任务、训练阶段计算效率面临的缺陷以及优化方法，比如，层次化softmax、哈弗曼二叉树编码等，同时介绍了在预测序列生成阶段全局优化方法(Beam search)和评测指标。
给定一段文本序列$x_1:T = x_1, x_2,...x_T$，计算该序列出现的概率分布，也即是计算这些词的联合概率。
$$p(x_{1:T})=p(x_1)p(x_2|x_1)p(x_3|x_{1:2})p(x_4|x_{1:3}),,...,p(x_T|x_{1:(T-1)}) = \prod {t=1}^Tp(x_t|x{1:(t-1)})$$
由以上运算可知，序列的概率密度估计问题可以转成单变量的条件概率估计问题，即是给定$x_{1:(t-1)}$时$x_t$的条件概率$p(x_t|X_{1:(t-1)})$。
给定N 个序列数据${X_{1:T_n}^n}^N_{n=1}$ ,序列概率模型需要模型$p_0(x|X_{1: (t-1)})$来最大化整个数据集上的对数似然函数。要计算的对数似然函数如下:
一旦通过最大似然估计训练了模型$pθ(x|x_{1:(t−1)})$，就可以通过时间顺序来 生成一个完整的序列样本。令xˆt 为在第t时根据分布$pθ(x|xˆ_{1:(t−1)})$生成的词，
其中$X_{1:(t-1)}$是前$t-1$步生成的序列。
自回归的方式可以生成无限长的序列。一般是设置一个特殊符号，如<EOS>来表示序列的结束。在训练时，每一个序列结尾都加上<EOS>，那么在测试时，一旦遇到了<EOS>就会终止下一个字符的生成。
由于自回归模型每次预测只能给出一个最优可能的词，这种贪婪的搜索方式不是全局最优的，一种对此常用的优化策略是使用Beam Search，也就是束搜索。它的搜索过程是：在每一步生成中，均会给出K个最可能的前缀序列，然后从中择优一个序列。其中$K$是束大小。
Beam Search具体思路：
在第一步时生成K 个最可能的词。在后面每一步中，从$K|V|$个候选输出中选择$K$ 个最可能的序列。束搜索可以通过调整束大小K 来平衡计算复杂度和搜索质量之间的优先级。搜索过程如下：
其中词表V = {A, B, C}，束大小为2。
可以使用传统的N元模型求解也可以用神经网络学习。
N元语言模型通常遇到数据稀疏问题，也即是当一个词在一段序列中不存在时，那么该序列的概率值被计为0，显然不合理，面对方法是各种平滑方法，平滑方法的本质是降低高频词的概率，增加低频词的概率。
困惑度可以衡量模型分布与样本经验分布之间的契合程度。困惑度越低则 两个分布越接近。
困惑度为每个词条件概率$p\theta(x_t^n|X_{1:(t-1)}^n$的几何平均数的倒数。测试集中所有序列的概率越大，困惑度越小，模型越好。
BLEU（Bilingual Evaluation Understudy）是衡量模型生成序列和参考序 列之间的N元词组（N-Gram）的重合度，最早用来评价机器翻译模型的质量， 目前也广泛应用在各种序列生成任务中。
序列生成模型的输出层为词表中所有词的条件概率，需要softmax归一化。 当词表比较大时，计算效率比较低。
配分函数的计算需要对词表中每个词计算$s(x_t,h_t;\theta)$然后计算累和。词表较大时，每一轮都要重新计算s函数，显然计算量大。通常是采样近似估计来加速训练过程，比如使用层次化的softmax和基于负采样的方法等。
将词表中词分成k组，每个词只能分到一个组，每个组大小$\frac{|V|} {k}$ 。假设词$w$所属的组是$c(w)$,则：
其中，$h$是神经网络隐藏层输出，$p(c(w)|h)$是给定历史信息$h$条件下，类$c(w)$的后验概率，$p(w|c(w), h)$是给定历史信息$h$和类$c(w)$条件下，词$w$ 的后验概率。
因此，一个词的概率可以分解为两个概率$p(w|c(w), h)$和$p(c(w)|h)$的乘积，它们可以分别利用神经网络来估计，这样计算softmax函数时分别只需要做 $\frac{|V|}{k} $ 和
为了进一步降低 softmax 的计算复杂度，我们可以更深层的树结构来组织词汇表。假设用二叉树来组织词表中的所有词，二叉树的叶子节点代表词表中的词，非叶子节点表示不同层次上的类别。图15.4给出了平衡二叉树和Huffman二叉树的示例。
将二叉树上所有左边标记为0，右边标记为1，那么每一个词可以用根节点到它所在叶子之间路径上的标记来编码。如：
v1:00
v2:01
v3:10
v4:11
假设词v在二叉树上从根节点到所在节点的路径长度为m，其编码可以用位向量表示：$[b1,...b_m]$。则词v的条件概率：
由于$b_j\in{0,1}$ 为二值变量，$p(b_j|b_{j-1}, h)$可以看做是二分类问题，可以用逻辑回归预测。
哈弗曼树编码对高频词使用长度较短的编码，而低频词使用长度较长的编码，使得训练速度更快。
