本章笔记基于[Neubig2017]第四章和NNMNLP第二章的一部分
上一章提到的N元语法模型实际上就是基于计数和条件概率，而log-linear语言模型（或称对数-线性语言模型）使用了另一种方法。在一些经典的文献中，log-linear语言模型通常被称作为“最大熵语言模型”（maximum entropy language model）
模型简介
Log-linear语言模型的本质是把语言模型的建立看作是一个多元分类问题，核心是从上文中提取特征。形式化地说，假设上文为\(e_{t-n+1}^{t-1}\)，log-linear语言模型需要一个特征函数\(\phi(e_{t-n+1}^{t-1})\)，其将上文信息作为输入，输出一个\(N\)维特征向量（注意这里是feature vector而不是eigenvector）\(\boldsymbol{x} \in \mathbb{R}^N\)，这个\(\boldsymbol{x}\)就是对上文信息的一个表示（这里的\(N\)不是N元语法里面的那个N，不表示上文单词数量！）
最简单的提取特征的方法是将上文中的每个单词都做一个独热编码（one-hot encoding）。例如，假设语言模型的词汇表为\(V\)，大小记为\(|V|\)，词汇表中每个单词都会被分配一个ID，记作\(i\)且有\(1 \le i \le |V|\)，那么对某个ID为\(i\)的单词，其独热编码以后的结果就是一个\(V\)维的向量，这个向量在第\(i\)个维度上的值为1，其余都是0。如果用类似二元语法的思想（即只用目标单词的前一个单词做预测）来做log-linear语言模型，这样就够了。但是如果想在上文里包含更多的单词，就需要进行扩展。一种常见的思路是将每个单词的独热向量拼接起来，这样，如果上文中包含了\(M\)个单词，得到的特征向量的长度\(N\)就是\(M|V|\)。当然，除了对上文单词做独热编码，log-linear语言模型还允许灵活加入其它特征，这也是该模型的一大长处。常见的特征还包括
- 上文的语义类别。可以使用聚类方法将相似单词聚类，这样，上文每个单词的独热编码不再是单词表长度，而是聚类得到的类别个数
- 上文单词的其它语义信息，例如词性标注（POS-Tag）信息
- 词袋特征。此时，不止考虑前面少数几个单词，而是考虑前面所有单词，统计它们出现的个数。注意在这种情况下会失去单词的位置信息，不过可以捕捉到单词的共现信息
下文中所使用的特征仍然是前面少数几个单词的独热编码
得到特征以后，模型会使用参数\(\theta\)计算出一个得分向量\(\boldsymbol{s} \in \mathbb{R}^{|V|}\)，对应于词汇表中的所有单词。这里参数\(\theta\)具体包含两个参数：权重矩阵\(\boldsymbol{W} \in \mathbb{R}^{|V| \times N}\)和偏置向量\(\boldsymbol{b} \in \mathbb{R}^{|V|}\)，都是训练得出。得到\(\boldsymbol{W}\)和\(\boldsymbol{b}\)以后，对给定的\(\boldsymbol{x}\)，就可以计算得到一个得分向量\(\boldsymbol{s}\)，其中 \[ \boldsymbol{s} = \boldsymbol{Wx} + \boldsymbol{b} \] 由于真正应用中词汇表的大小通常都比较大，特征数也比较多，因此权重矩阵\(\boldsymbol{W}\)通常会很大（如果只使用前面提到的独热编码的上文信息做特征，假设上文单词数为2，词汇表大小为20000，则权重矩阵的大小就是\(20000 \times 40000\)。同时，\(\boldsymbol{x}\)本身也是一个比较大的向量，两者相乘比较耗时。由于\(\boldsymbol{x}\)通常是若干独热编码向量的组合，因此它会特别稀疏，只有少许维度非0（而且可能只取值为1）。所以，可以使用如下操作避免矩阵乘法带来的性能问题： \[ \boldsymbol{s} = \sum_{j: x_j \not= 0}\boldsymbol{W}_{., j}x_j + \boldsymbol{b} \] 其中\(\boldsymbol{W}_{., j}\)代表矩阵\(\boldsymbol{W}\)的第\(j\)列。上一个式子的直接翻译是“对特征向量\(\boldsymbol{x}\)，找出其所有不为零的维度，然后找出权重矩阵\(\boldsymbol{W}\)对应的列，将这一列向量乘以特征向量对应维度的值，再把所有这样处理得到的向量相加，最后加上偏置向量”
这样得到的得分向量每个维度的值都可能是任意的一个实数。为了得到一个更好的，有概率意义的结果，可以做一个softmax计算以达到归一化的效果 \[ \boldsymbol{p} = {\rm softmax}(\boldsymbol{s}) \] 具体计算方法为，对\(\boldsymbol{s}\)的每个分量\(s_j\)，其对应的\(p_j\)为 \[ p_j = \frac{\exp(s_j)}{\sum_i\exp(s_i)} \]
Softmax的计算问题
本节来自于花书DLBook第4.1节
然而，真实计算softmax函数的值时，既可能出现上溢的情况，又可能出现下溢的情况。假设最后得到的\(\boldsymbol{s} = \left[\begin{matrix}1000 \\ 1003\end{matrix}\right]\)，一般计算\(e^{1000}\)的时候都会上溢，例如使用python计算
1 | import math |
而如果最后得到的\(\boldsymbol{s} = \left[\begin{matrix}-1000 \\ -1003\end{matrix}\right]\)，一般计算\(e^{-1000}\)的时候又都会下溢，例如
1 | import math |
此时softmax的分母会被认为是0，进而抛出异常
因此，真正计算时，通常会将原始要计算的向量\(\boldsymbol{s}\)做一个处理得到向量\(\boldsymbol{z}\)，即对\(\boldsymbol{s}\)的每个分量\(s_i\)都减去\(\boldsymbol{s}\)最大的那个分量。即 \[ \boldsymbol{z} = \boldsymbol{s} - \max_i s_i \] 记\(\max_i s_i = c\)，同时\(\rm{softmax}(\boldsymbol{z}) = \boldsymbol{q},\ \rm{softmax}(\boldsymbol{s}) = \boldsymbol{p}\)，下面证明有\(\boldsymbol{q} = \boldsymbol{p}\)。假设\(\boldsymbol{c}\)是维度与\(\boldsymbol{z}\)和\(\boldsymbol{s}\)的维度均相等的向量，其每个分量\(c_i = \max_i s_i = c\)，即\(\forall i, j, 1 \le i, j \le {\rm dim}\ \boldsymbol{c} \Rightarrow c_i = c_j = c\)， \[ \begin{align*} &&\boldsymbol{q} = {\rm softmax}(\boldsymbol{z}) &= {\rm softmax}(\boldsymbol{s} - \boldsymbol{c}) \\ &&\Rightarrow q_i&= \frac{\exp(s_i - c)}{\sum_j \exp(s_j - c)} \\ &&&= \frac{\exp(s_i)}{\exp(c)\sum_j\left(\exp(s_j) / \exp(c)\right)} \\ &&& = \frac{\exp(s_i)}{\exp(c) / \exp(c)\sum_j\exp(s_j)} = \frac{\exp(s_i)}{\sum_j\exp(s_j)} = p_i \\ && \Rightarrow \boldsymbol{q} &= \boldsymbol{p}\ \blacksquare \end{align*} \] 因此，计算\(\rm{softmax}\left(\left[\begin{matrix}1000 \\ 1003\end{matrix}\right]\right)\)等价于计算\(\rm{softmax}\left(\left[\begin{matrix}-3 \\ 0\end{matrix}\right]\right)\)，以此类推。这样的处理方法保证所有\(\exp\)函数的参数的最大值为0，因此避免了上溢的可能。同时，所有softmax函数的分母里都会有至少一个为1的项，也就避免了分母下溢，被0除的可能。但是，分子仍然存在下溢的可能，因此在计算\(\log \rm{softmax}\)的值时仍然需要特别小心
模型示例
我们举个例子。假设词汇表的大小只有2，包括A、B两个词。现在已知最后出现的两个词为B和A，log-linear语言模型的作用就是训练一个权重矩阵\(\boldsymbol{W}\)和偏置向量\(\boldsymbol{b}\)，进而推断此时接下来两个词出现的概率。假设\(\boldsymbol{W}\)和\(\boldsymbol{b}\)已经训练好，有 \[ \boldsymbol{W} = \left[\begin{matrix}1.2 & -1.2 & 8.5 & 4.5 \\ -0.6 & 1.3 & -3.5 & -2.7 \\ \end{matrix}\right], \boldsymbol{b} = \left[\begin{matrix}0.1 \\ -0.3\end{matrix}\right] \] 那么特征向量\(\boldsymbol{x}\)按照前面介绍的独热编码应该为 \[ \boldsymbol{x} = \left[\begin{matrix}0 \\ 1 \\ 1 \\ 0\end{matrix}\right] \] 则 \[ \boldsymbol{s} = \left[\begin{matrix}-1.2 \\ 1.3 \end{matrix}\right] + \left[\begin{matrix}8.5 \\ -3.5 \end{matrix}\right] + \left[\begin{matrix}0.1 \\ -0.3 \end{matrix}\right] = \left[\begin{matrix}7.4 \\ -2.5 \end{matrix}\right] \] 经过softmax计算，有\(\boldsymbol{p} = \left[\begin{matrix}0.99995 \\ 0.00005\end{matrix}\right]\)，说明接下来很可能会出现A
可以看出，权重矩阵的每一列都有一定的意义。如果特征向量由若干个独热编码组成，那么\(\boldsymbol{W}\)的第\(j\)列实际上表明了第\(j\)个特征激活时，各个词出现的可能性。这个列向量的分量越大，说明对应的词出现的可能性越大，反之说明越小。例如，\(\left[\begin{matrix}8.5 \\ -3.5\end{matrix}\right]\)这一列是前一个词为A时，接下来出现A和B的可能性。这意味着此时出现A的可能性远大于出现B的可能性
学习模型参数
损失函数
第一节讲述了在有权重矩阵和偏置向量的情况下，如何使用建立好的模型根据给定的上文预测即将出现的词。那么接下来的问题是如何得到（学习）这些模型参数\(\theta\)。为此，需要先定义一个合适的损失函数\(\ell\)。所谓损失函数，其直观意义可以看做是在给定当前模型参数\(\theta\)的情况下，模型的预测值\(\hat{y}\)与真实值\(y\)之间差了多远，也就是现在这个模型有多差。因此，训练模型参数的过程，就是要调整参数\(\theta\)使得损失函数\(\ell\)尽量小的过程。通常情况下，损失函数等于似然的负对数 \[ \ell (\mathcal{E}_{\rm train},\boldsymbol{\theta}) = -\log P(\mathcal{E}_{\rm train}|\boldsymbol{\theta}) = -\sum_{E \in \mathcal{E}_{\rm train}}\log P(E|\boldsymbol{\theta}) \] 这个想法和最大似然的思想是等价的，因为最大似然等价于最小化负似然，而加入对数函数不影响目标函数的单调性。假设这样的损失函数在微观上（每个词的级别上）也适用，则有 \[ \ell (e^t_{t-n+1}, \boldsymbol{\theta}) = \log P(e_t|e_{t-n+1}^{t-1}) \]
使用随机梯度下降（SGD）进行优化
熟悉logistic回归和其它统计学习方法的读者应该可以马上意识到，log-linear语言模型实际上可以看作是logistic回归变种在NLP领域上的一个应用，而logistic回归通常使用梯度下降法做优化。当样本量太大时，通常使用随机梯度下降。不过这里本文还是准备对随机梯度下降做一个具体的介绍
本部分内容参考了花书4.3小节
大部分机器学习问题的最终形式都是一个优化问题，即给定一个参数为\(\theta\)的函数\(f(\theta)\)，找到一个合适的\(\theta\)，使得\(f\)能取得最小值。用数学的语言描述，就是求出\(\theta^\ast = \mathop{\rm arg\min}_{\theta}f(\theta)\)——当然，有些时候需要找到能使\(f\)取得最大值的\(\theta\)，在这种情况下，同样的\(\theta\)也会使\(-f(\theta)\)取得最小值，所以两者是等价的。这里的这个\(f\)也就是前面提到的损失函数\(\ell\)
这样一来，问题就被抽象为求最值的问题。在比较简单的，一元函数的情况下，对函数求导并令导数为0，就可以求出最优的\(\theta\)。但是，考虑到有些情况下上述方法无法得到解析解，因此还需要使用一种迭代的方法来完成同样的任务。对于给定的函数\(f\)，其一阶导数的一个重要性质是，如果其在某个点\(x\)的一阶导数\(f'(x) > 0\)，则函数单调递增；如果一阶导数\(f'(x) < 0\)，则函数单调下降。在最简单的情况下，假设已知函数是凹函数且处处连续、处处可导，那么当\(x\)在某个点\(x_0\)的一阶导数大于0时，由于函数递增，那么为了向极值点（这里是极小值点）靠近，\(x\)应该向左移动，慢慢变小；当当\(x\)在某个点\(x_0\)的一阶导数小于0时，由于函数递减，那么为了向极值点靠近，\(x\)应该向右移动，慢慢变大。综合这两种情况，对足够小的\(\epsilon\)，总有 \[ f(x-\epsilon\cdot {\rm sign}(f'(x))) < f(x) \] 也就是说，无论如何，总可以把\(x\)往导数的反方向移动一小步来减小\(f(x)\)。经过足够多步的迭代，在\(\epsilon\)设置适当的情况下，\(x\)最后总能到达极小值点。此时\(f'(x) = 0\)。不过需要注意的是，极值点在很多情况下不是最值点，有可能只是一个局部最优解
上述过程就是梯度下降在一元函数情况下的介绍，相对比较容易理解。当函数的输入时多维的向量时，要稍微复杂一些。前面在讲述一元函数一阶导数的时候有一点没有提到，一元函数\(f(x)\)在\(x_0\)点的导数的另一个意义是变量在该点做微小移动时，函数值的变化率。这个意义可以扩展到多元函数的领域里：假设函数\(f(\boldsymbol{x})\)的参数\(\boldsymbol{x} \in \mathbb{R}^n\)，那么当\(\boldsymbol{x}\)的\(n-1\)个维度上的分量都不变，仅对第\(i\)个维度上的分量做微小移动时，函数值的变化率就是这个函数在\(x_i\)轴上的偏导数，记为\(\frac{\partial }{\partial x_i}f(\boldsymbol{x})\)。换句话说，函数\(f\)的偏导数是函数沿着某个坐标轴的变化率。在此之上，可以定义梯度为 \[ \nabla_{\boldsymbol{x}}f(\boldsymbol{x}) = \left[\begin{array}{c}\frac{\partial f}{\partial x_1} & \cdots & \frac{\partial f}{\partial x_i} & \cdots &\frac{\partial f}{\partial x_n}\end{array}\right]^\mathsf{T} \] 有了这些概念，接着就可以看什么是方向导数。直观地讲，可以想象在三维空间里想象一个图像形状为碗型的二元函数，自变量由x轴和y轴确定，z轴为因变量。在碗壁上的任何一个点，都可以向360度不同的方向滑动，另一方面，自变量的微小移动使得函数在360度的方向上都会有不同的变化率，在单位向量\(\boldsymbol{u}\)方向上的变换率就是\(f\)在\(\boldsymbol{u}\)方向上的方向导数，其定义为\(\boldsymbol{u}^\mathsf{T}\nabla_{\boldsymbol{x}}f(\boldsymbol{x})\)。其中，使得方向导数最小的方向，是函数变化量最大的方向，因此 \[ \begin{align*} &\min_{\boldsymbol{u}, \boldsymbol{u}^\mathsf{T}\boldsymbol{u} = 1} \boldsymbol{u}^\mathsf{T}\nabla_{\boldsymbol{x}}f(\boldsymbol{x}) \\ = &\min_{\boldsymbol{u}, \boldsymbol{u}^\mathsf{T}\boldsymbol{u} = 1} \|\boldsymbol{u}\|_2\|\nabla_\boldsymbol{x}f(\boldsymbol{x})\|_2\cos\theta \end{align*} \] 其中\(\theta\)是梯度方向与单位向量之间的夹角。由于\(\boldsymbol{u}\)是单位向量，因此\(\|\boldsymbol{u}\|_2 = 1\)，且梯度的模长与\(\boldsymbol{u}\)无关，因此上式等价于最小化\(\cos \theta\)，这个值在\(\theta = \pi\)时取得，此时\(\boldsymbol{u}\)指向梯度方向的反方向。因此在输入为向量的情况下，梯度下降的更新公式为 \[ \boldsymbol{x}^{t+1} = \boldsymbol{x}^{t} - \epsilon \nabla_{\boldsymbol{x}}f(\boldsymbol{x}^t) \] (本部分的叙述顺序基本参考了花书的顺序，但是这样使得某些概念的引出顺序与因果顺序相反。例如，梯度的几何意义就是函数下降最快方向的反方向，但是这里梯度的定义先于方向导数的定义给出。在这点上，国内的讲述方法可能更符合因果，但是理解起来难度会大一些。此外，这些概念结合图看可能更好理解，可以参考知乎讨论如何直观形象的理解方向导数与梯度以及它们之间的关系？和可汗学院的讲授视频梯度与方向导数)
将这个公式套用到前面“损失函数”一节中的定义，可以知道log-linear语言模型的参数更新方式为 \[ \boldsymbol{\theta}^{t+1} = \boldsymbol{\theta}^t - \epsilon \frac{\partial\ell(e_{t-n+1}^t, \boldsymbol{\theta})}{\partial\boldsymbol{\theta}} \] 其中\(\epsilon\)更通常情况下被写为\(\eta\)，称作学习率。直观地看，\(\eta\)的大小决定了梯度下降每次向前走的步长大小，它的选取应该慎重：如果\(\eta\)太大，则算法会出现震荡（步子迈得太大，直接越过了极值点，如此反复），难以收敛；如果\(\eta\)太小，算法收敛得会太慢，或者陷入不好的局部最优解。通常的做法是随着训练的持续慢慢调小学习率。其它比较好的工程实践还包括提前停止（保留一部分数据做验证集，算法在验证集上效果变差时终止迭代）和随机打乱原始数据顺序等（避免连续看到同一类型的数据，影响模型效果）
此外，上面给出的更新方式是每看到一个样本更新一次，这种做法通常也称为在线学习法（online learning）。另外一种方法是将所有数据的梯度都计算出来，然后求均值，这种方法称为全批量（full-batch）梯度下降。在线学习的问题是一个样本的梯度方向可能不是最优方向（不过在样本量足够大，迭代次数足够多的情况下也能收敛到比较好的极值点）；而全批量梯度下降的问题是深度学习使用的数据集通常比较大，计算起来耗费资源太多。因此真正广泛应用的是小批量（mini-batch）随机梯度下降法，即随机选取若干样本，计算梯度的均值
在SGD之上，还有一些衍生的优化算法，例如动量（momentum）法、AdaGrad和Adam等等。这些算法将在之后的文章中做总结
损失函数对参数的偏导数
通过上面的讲述，可知更新模型参数的关键是要求出损失函数对参数的偏导数。将上面的式子整理可得 \[ \begin{align*} \boldsymbol{s} &= \sum_{j: x_j \not= 0}\boldsymbol{W}_{., j}x_j + \boldsymbol{b} \\ \boldsymbol{p} &= {\rm softmax}(\boldsymbol{s}) \\ \ell &= -\log p_{e_t} \end{align*} \] 因此有 \[ \begin{align*} \frac{\partial \ell}{\partial \boldsymbol{W}_{.,j}} &= \frac{\partial \ell}{\partial p_{e_t}} \cdot \frac{\partial p_{e_t}}{\partial \boldsymbol{s}} \cdot \frac{\partial \boldsymbol{s}}{\partial \boldsymbol{W}_{.,j}} \\ \frac{\partial \ell}{\partial \boldsymbol{b}} &= \frac{\partial \ell}{\partial p_{e_t}} \cdot \frac{\partial p_{e_t}}{\partial \boldsymbol{s}} \cdot \frac{\partial \boldsymbol{s}}{\partial \boldsymbol{b}} \end{align*} \] 可以看出两者都需要求\(\frac{\partial \ell}{\partial p_{e_t}} \cdot \frac{\partial p_{e_t}}{\partial \boldsymbol{s}} = \frac{\partial \ell}{\partial \boldsymbol{s}}\)。由于有 \[ p_{e_t} = \frac{e^{s_t}}{\sum_ue^{s_u}} \] 因此 \[ \ell = -\log p_{e_t} = -\log \frac{e^{s_t}}{\sum_ue^{s_u}} = -s_t + \log\sum_ue^{s_u} \] 由标量对向量的求导法则，得出一个同样维度的向量，其中每个分量是标量对原向量中该分量的导数（详细可见Towser大神整理的文章机器学习中的矩阵、向量求导），即假设\(a\)为标量，\(\boldsymbol{x}\)为向量，且\(\boldsymbol{x} = \left[\begin{array}{ccc}x_1 & \cdots & x_n\end{array}\right]^\mathsf{T}\)，则有 \[ \frac{\partial a}{\partial \boldsymbol{x}} = \left[\begin{array}{c}\frac{\partial a}{\partial x_1} \\ \cdots \\ \frac{\partial a}{\partial x_n} \end{array}\right]^\mathsf{T} \] 而且有 \[ \frac{\partial \ell}{\partial s_v} = \begin{cases}-1 + \frac{e^{s_v}}{\sum_ue^{s_u}} & {\rm if\ }v = t \\ \frac{e^{s_v}}{\sum_ue^{s_u}} & {\rm elsewhere}\end{cases} \] 进一步简化，可知 \[ \frac{\partial \ell}{\partial \boldsymbol{s}} = \boldsymbol{p} - {\rm onehot}(e_t) \] 因此， \[ \begin{align*} \frac{\partial \ell}{\partial \boldsymbol{W}_{.,j}} &= x_j (\boldsymbol{p} - {\rm onehot}(e_t))\\ \frac{\partial \ell}{\partial \boldsymbol{b}} &= \boldsymbol{p} - {\rm onehot}(e_t) \end{align*} \] 另外补充一下，分类问题更常用的是交叉熵损失函数。假设真实类标签分布向量为\(\boldsymbol{q}\)，分类器预测出来的分布向量为\(\boldsymbol{p}\)，则交叉熵损失函数的值\(\ell_{\rm CE}\)为 \[ \ell_{\rm CE} = -\sum_i^C q_i\log p_i \] 其中\(C\)是类别标签的个数。如果把语言模型问题看作是\(|V|\)元分类问题，那么交叉熵损失函数也适用，其中\(\boldsymbol{q}\)是一个独热编码向量。不难看出此时\(\ell_{\rm CE}\)和前面提到的损失函数\(\ell\)是等价的
