Language Model (语言模型)
Noisy Channel Model
\[p(text|source) \propto p(source|text)p(text) \]\(\propto\)符号表示成正比，公式根据Bayes定理得出，目标是找到使得\(p(text|source)\)概率最大的text。
应用场景：语音识别，机器翻译，拼写纠错，OCR，密码破解。
这些应用场景的共同点：给定一个信号source，把这些信号转换成文本text。
Language Model, LM
语言模型用来判断：一句话从语法上是否通顺。
比较：
今天是周日 vs 今天周日是
全民AI是趋势 vs 趋势全民AI是
一个训练好的语言模型是通过计算句子的概率来进行比较的：
\[P_{LM}(今天是周日) \gt P_{LM}(今天周日是) \\ P_{LM}(全民AI是趋势) \gt P_{LM}(趋势全民AI是) \]Chain Rule and Markov Assumption
Recap: Chain Rule
联合概率计算公式：
\[p(x_1,x_2)=p(x_1) \cdot p(x_2|x_1) \]当\(n=4\)，Chain Rule：
\[\begin{aligned} p(x_1, x_2, x_3, x_4) &= p(x_3x_2x_1) \cdot p(x_4|x_3x_2x_1) \\ &= p(x_2x_1) \cdot p(x_3|x_2x_1) \cdot p(x_4|x_3x_2x_1) \\ &= p(x_1) \cdot p(x_2|x_1) \cdot p(x_3|x_2x_1)\cdot p(x_4|x_3x_2x_1) \end{aligned} \]通项式：
\[p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) = p(w_1) \cdot p(w_2|w_1) \cdot p(w_3|w_1w_2) \cdot p(w_4|w_1w_2w_3) \cdot p(w_5|w_1w_2w_3w_4) \cdots p(w_n|w_1w_2w_3 \cdots w_{n-1}) \]Chain Rule for Language Model
p(今天，是，春节，我们，都，休息)：
\[p(今天,是,春节,我们,都,休息) = p(今天) \cdot p(是|今天) \cdot p(春节|今天, 是) \cdot p(我们|今天, 是, 春节) \cdot p(都|今天, 是, 春节, 我们) \cdot p(休息|今天, 是, 春节, 我们, 都) \]在训练语言模型时，相当于提前把式子中的条件概率都计算好，然后在计算句子的概率时直接计算即可。
假如我们有这样一篇训练文档：
我们根据句子在文章中的出现情况计算概率，那么，我们可以计算出条件概率：
\[p(休息|今天, 是, 春节, 我们, 都) = \frac{1}{2} \\ p(运动|今天, 是, 春节, 我们, 都) = 0 \]可以发现，采用这种计算方法，对于比较长的句子基本上都是找不到的，那么大多数的条件概率都是0，这也会出现稀疏性（sparsity）。
Markov Assumption
为了解决稀疏性问题，需要使用马尔可夫假设。有时候一个概率很难计算，那么我们就可以通过马尔可夫假设来近似的估计概率。
条件概率的马尔可夫假设
计算条件概率：\(p(休息|今天, 是, 春节, 我们, 都)\)
\(1^{st}\) order markov assumption：
\[p(休息|今天, 是, 春节, 我们, 都) \approx p(休息|都) \]\(2^{rd}\) order markov assumption：
\[p(休息|今天, 是, 春节, 我们, 都) \approx p(休息|我们,都) \]\(3^{rd}\) order markov assumption：
\[p(休息|今天, 是, 春节, 我们, 都) \approx p(休息|春节, 我们, 都) \]计算句子概率的马尔可夫假设
计算句子概率：\(p(w_1,w_2,w_3,w_4,w_5 \cdots w_n)\)
\(1^{st}\) order markov assumption：
\[\begin{align} p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) & \approx p(w_1) \cdot p(w_2|w_1) \cdot p(w_3|w_2) \cdots p(w_n|w_{n-1}) \\ &= p(w_1) \prod_{i=2}^n p(w_i|w_{i-1}) \end{align} \]\(2^{rd}\) order markov assumption：
\[\begin{align} p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) & \approx p(w_1) \cdot p(w_2|w_1) \cdot p(w_3|w_1,w_2) \cdot p(w_4|w_2,w_3) \cdots p(w_n|w_{n-2},w_{n-1}) \\ &= p(w_1)\cdot p(w_2|w_1) \prod_{i=3}^n p(w_i|w_{i-2},w_{i-1}) \end{align} \]\(3^{rd}\) order markov assumption：
\[\begin{align} p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) & \approx p(w_1) \cdot p(w_2|w_1) \cdot p(w_3|w_1,w_2) \cdot p(w_4|w_1, w_2,w_3) \cdot p(w_5|w_2, w_3,w_4) \cdots p(w_n|w_{n-3}, w_{n-2},w_{n-1}) \\ &= p(w_1)\cdot p(w_2|w_1) \cdot p(w_3|w_1,w_2) \prod_{i=4}^n p(w_i|w_{i-3}, w_{i-2},w_{i-1}) \end{align} \]Language Model (Use First Order)
假如我们已经训练好的语言模型如下：
比较：
今天是周日 vs 今天周日是
显然，\(P_{LM}(今天 是 周日) \gt P_{LM}(今天 周日 是)\)。
Unigram, Bigram, N-gram
Language Model: Unigram
Unigram比\(1^{st}\) order markov assumption还要简单。
\[\begin{align} & p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) \\ = & p(w_1) \cdot p(w_2) \cdot p(w_3) \cdot p(w_4) \cdot p(w_5) \cdots p(w_n) \end{align} \]示例：
\[\begin{align} & p(今天, 是, 春节, 我们, 都, 休息) \\ = & p(今天) \cdot p(是) \cdot p(春节) \cdot p(我们) \cdot p(都) \cdot p(休息) \end{align} \] \[\begin{align} & p(今天, 春节, 是, 都, 我们, 休息) \\ = & p(今天) \cdot p(春节) \cdot p(是) \cdot p(都) \cdot p(我们) \cdot p(休息) \end{align} \]我们希望一个好的语言模型能够得出：\(p(今天, 是, 春节, 我们, 都, 休息) \gt p(今天, 春节, 是, 都, 我们, 休息)\)，而Unigram计算结果两者是相等的，显然是无法得到这个结果的，因为Unigram是和单词顺序无关的。
Language Model: Bigram
Bigram来源于\(1^{st}\) order markov assumption。
\[\begin{align} & p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) \\ = & p(w_1) \cdot p(w_2|w_1) \cdot p(w_3|w_2) \cdots p(w_n|w_{n-1}) \\ = & p(w_1) \prod_{i=2}^n p(w_i|w_{i-1}) \end{align} \]示例：
\[\begin{align} & p(今天, 是, 春节, 我们, 都, 休息) \\ = & p(今天) \cdot p(是|今天) \cdot p(春节|是) \cdot p(我们|春节) \cdot p(都|我们) \cdot p(休息|都) \end{align} \] \[\begin{align} & p(今天, 春节, 是, 都, 我们, 休息) \\ = & p(今天) \cdot p(春节|今天) \cdot p(是｜春节) \cdot p(都|是) \cdot p(我们|都) \cdot p(休息|我们) \end{align} \]Bigram考虑了两个单词的顺序。
注：最常用的其实就是Bigram模型。
Language Model: N-gram
\(n>2\)的时候语言模型就称为N-gram。
当\(n=3\)时，
\[\begin{align} & p(w_1,w_2,w_3,w_4,w_5 \cdots w_n) \\ = & p(w_1) \cdot p(w_2|w_1) \cdot p(w_3|w_1,w_2) \cdot p(w_4|w_2,w_3) \cdots p(w_n|w_{n-2},w_{n-1}) \\ = & p(w_1)\cdot p(w_2|w_1) \prod_{i=3}^n p(w_i|w_{i-2},w_{i-1}) \end{align} \]Estimating Probability
前面讲解的内容都是已经有了语言模型的概率之后的事情，下面主要介绍如何估算概率，创建语言模型。
Unigram: Estimating Probability
假设在一篇文档中，“我们”这个单词出现的次数是\(C(我们)=100\)，整篇文章的单词数是\(V=10^5\)，那么\(P(我们) = \frac{C(我们)}{V} = \frac{100}{10^5}\)。在Unigram模型中，每个单词的概率都可以这样计算出来。
示例：
可以看到，由于没有进行平滑处理，第二个句子中出现了语料库中不存在的单词“没有”，就会导致整个句子的概率为0，这其实是非常不好的结果。
Bigram: Estimating Probability
Bigram下条件概率的计算方法如下：
示例：
N-gram: Estimating Probability
以N=3为例：
Evaluation of Language Model
Q: 训练出来的语言模型效果好还是坏？
理想情况下，
- 假设有两个语言模型A，B
- 选定一个特定的任务，比如拼写纠错
- 把两个模型A，B都应用在此任务中
- 最后比较准确率，从而判断A，B的表现
这种评估方式的缺点在于过于复杂。
Perplexity
核心思路
我们可以让训练出来的语言模型做填空题（单词预测），以此来评估模型的优劣。
Perplexity计算公式
\[Perplexity = 2^{-(x)} \]\(x\): average log likelihood.
Perplexity越小越好。
示例：
计算所有词组的条件概率，然后取对数（这里选择以10为底数），对所有结果求均值，即可得到\(x\)，也就得到了perplextiy。
一般情况下更高维度的N-gram的Perplexity更小，但是同时也会有过拟合的倾向。
Smoothing (平滑)
Smoothing有4种方法：
- Add-one Smoothing（最简单）
- Add-K Smoothing
- Interpolation
- Good-Turning Smoothing
Add-one Smoothing (Laplace Smoothing)
Not smoothed:
\[P_{MLE}(w_i|w_{i-1}) = \frac{c(w_{i-1}, w_i)}{c(w_i)} \]Add-one Smoothing:
\[P_{Add-1}(w_i|w_{i-1}) = \frac{c(w_{i-1}, w_i) + 1}{c(w_i) + V} \]\(V\): 词典的大小（排除了重复项）。
示例：
同时也可以得出为什么分母是加V而不是加其他数值。
但是为1有什么意义呢？
Add-K Smoothing (Laplace Smoothing)
Add-1 Smoothing是Add-K Smoothing的特例。
Add-K Smoothing:
\[P_{Add-1}(w_i|w_{i-1}) = \frac{c(w_{i-1}, w_i) + k}{c(w_i) + kV} \]\(k\)是我们可以调的参数。
怎么选择\(k\)？
把\(k\)作为一个参数，优化\(f(k)\)，直到找到最好的\(k\)。
首先在训练集语料库中，我们可以得到语言模型，然后使用已经得到的语言模型，计算验证集语料库的perplexity，我们把\(k\)当作一个变量，也就是对于不同的\(k\)，会得到不同的perplexity，即\(perplexity = f(k)\)。我们的目标就是最小化perplextiy，即最小化\(f(k)\)，最终得到的\(k\)就是最好的\(k\)。
Interpolation
Q: 为什么会提出 Interpolation 这套方法？
要回答这个问题，我们需要考虑之前的方法有什么缺点。
在上面的例子中，\(p(kitchen | in \space the) = p(arboretum| in \space the)\)，这样合理吗？这显然是不合理的。因为虽然两者都没有出现在语料库中，但是由于\(p(kitchen)\)明显大于\(p(arboretum)\)，所以我们认为\(p(kitchen | in \space the)\)应该是大于\(p(arboretum| in \space the)\)才是合理的。
核心思路
在计算Trigram概率时同时考虑Unigram，Bigram，Trigram出现的频次。
\[\begin{align} p(w_n|w_{n-1},w_{n-2}) &= \lambda_1p(w_n|w_{n-1},w_{n-2}) \\ &+ \lambda_2p(w_n|w_{n-1}) \\ &+ \lambda_3p(w_n) \end{align} \]其中，\(\lambda_1 + \lambda_2 + \lambda_3 = 1\)。
Good-Turning Smoothing
引入
假设你在钓鱼，已经钓到18条鱼：10条鲤鱼，3条黑鱼，2条刀鱼，1条鲨鱼，1条草鱼，1条鳗鱼......
Q1: 下一个钓到的鱼是鲨鱼的概率是多少？
根据之前钓鱼的情况进行估计，\(\frac{1}{18}\)。
在这里隐含的假设是6种鱼占据了整个概率空间，即\(p(6种已知鱼)=1\)。
Q2: 下一条鱼是新鱼种（之前没有出现过）的概率是多少？
一种近似的求解方法就是，用目前为止钓到的1条的鱼来近似新鱼种的概率，\(\frac{3}{18}\)。
概率空间中留了一部分给新鱼种，\(p(6种已知鱼)+p(新鱼种)=1\)。
Q3: 既然如此，重新想一下，下一个钓到的鱼是鲨鱼的概率是多少？
之前在Q1中我们认为是\(\frac{1}{18}\)，这个假设的前提是所有鱼都已经出现过，但是现在我们考虑了新鱼种，相当于已知鱼的概率空间减小了，所以鲨鱼出现的概率应该是小于\(\frac{1}{18}\)。
具体概率是多少，Good-Truning算法提供了计算方法。
Good-Turning Smoothing
首先定义一个参数：\(N_c\) 出现c次的单词的个数。
例: Sam I am I am Sam I do not eat
Sam: 2
I: 3
am: 2
do: 1
not: 1
eat 1
所以，\(N_3 = 1, N_2=2,N_1=3\)。
Good-Turning Smoothing算法分为两个部分
-
没有出现过的单词
\[P_{GT} = \frac{N_1}{N} \] -
出现过的单词
\[P_{GT} = \frac{(c+1)N_{c+1}}{N_cN} \]
示例：
关于Good-Turning的一个统计表格：
-
第一列：单词出现次数\(r\)；
-
第二列：\(N_r\)，出现r次的单词的个数；
-
第三列：Good-Turning计算出来的概率；
-
第四列：是在测试集中出现r次对应的频率；
可以发现有非常多的是单词是没出现在词典库的，同时第三列和第四列在数值上非常接近，说明Good-Turning Smoothing进行估算的有效性。
Q: Good-Turning方法的缺点是什么？怎么解决？
从上面的统计表格以及公式我们都可以发现，要计算出现\(c\)次的单词的\(P_{GT}\)，我们需要知道\(N_c\)和\(N_{c+1}\)。而当\(c\)比较大的时候，比如\(c=100\)，那么很可能我们是不知道\(N_{101}\)的。
这种时候我们就需要先通过机器学习的方法（比如回归），先拟合出一个分布曲线，填充所\(N_c\)的缺失值，然后采用使用Good-Turning Smoothing。
Use Language Model to Generate Sentence (利用语言模型生成句子)
语言模型是一个生成模型，生成模型的意思是指我们训练出来这个模型之后，这个模型是可以帮我们生成新的数据，比如图片、音乐、文本等。
首先，假设我们生成的是Unigram Model。
我们根据词典库中每个单词的概率进行选择（选中的概率就是下面的概率）。由于Unigram Model是不考虑上下文的，因此最后生成的句子大概率是不合语法的。
接下来看Bigram Model。
BIgram Model生成的其实就是类似于左下角的矩阵：
说明：这里考虑了终止符号。
假设我们随机生成的第一个单词是“I”，那么接下来就可以去“I”行进行选择，由于是按照概率进行选择的，所以有非常大的概率选中“like”单词，以此类推，直到遇到终止符号，则说明句子生成结束。
假如语言模型训练的比较好，那么采用Bigram Model我们基本上能够生成比较合理的句子，虽然也不一定完全符合语法句法。