Ch04 N 元语法
N 元语法模型（N-gram model）是概率模型。
2 元语法（bigram）是包含 2 个单词的序列；
3 元语法（trigram）是包含 3 个单词的序列；
语言模型（Language Models，LM）是单词序列的概率模型。
语料库中单词数目的计算
自然语言中统计计算需要依赖于语料库（单数：corpus，复数：corpora）。
语料库是计算机可读的文本或者口语的集合体。
阻断（disfluencies）：切断和有声停顿。
切断（fragment）：一个单词在中间被拦腰切开就形成切断。
有声停顿（filled pauses）：也称为过滤成分（filters）。单词的停顿。
词目（lemma）：具有相同的词干和相同的词义并且主要的词类也相同的词汇形式
词形（wordform）：是一个单词的全部的屈折或者派生形式。
语言的“型”（type）和“例”（token）。“型”就是语料库中不同单词的数目，或者是词汇容量的大小，记为 V；“例”就是使用中的全部单词数目，记为 N。
简单的（非平滑的）N 元语法
计算某个单词的概率，只考虑最接近该单词的若干个单词，近似地逼近该单词的历史，这是 N 元语法模型的直觉解释。
一个单词的概率只依赖于它前面单词的概率的这种假设称为马尔可夫假设（Markov
assumption）
使用最大似然估计（Maximum Likelihood Estimation，MLE）估计 N 元语法模型的概率。
从语料库中得到的计数加以归一化（normalize）。
用前面符号串（prefix）的观察频率来除这个特定单词序列的观察频率，就得到 N 元语法概率的估计值，这个比值称为相对频率（relative frequency）。
训练集与测试集
训练集（training set）或者训练语料库（training corpus）：
测试集（test set）或者测试语料库（test corpus）：
保留集（held-out set）
初始的测试集又称为调试测试集，又称为开发集（development test set，devset）。
在一些数据上训练，在另一些数据止测试，还可以用来评估不同 N 元语料的总体结构。
N 元语法及其对训练语料库的敏感性
确保训练语料库与测试语料库有相似性。
未知词：开放词汇和封闭词汇
未知词（unknown words），或者表外词（Out Of Vocabulary，OOV），没有在系统中看到的单词。
在测试集中出现的表外词 OOV 的百分比称为表外词率（OOV rate）。
在封闭词汇（closed vocabulary）系统中，假定不存在未知词。
在开放词汇（open vocabulary）系统中，给测试集加上一个伪词（pseudo-word）来给这些潜在的未知词建模，这个未知词的模型称为：<UNK\>。
N 元语法的评测：困惑度
端到端（end-to-end）的评测称为外在评测（extrinsic evaluation），也称为现实评测（in vivo evaluation）或者叫体内评测，将语言模型嵌入到某种应用中，并测试这个应用的总体性能。
内在评测（intrinsic evaluation）：的度量就是一种与任何应用无关的模型质量的评测方法。
困惑度（perplexity，PP）：是对于 N 元语法模型的一种最常见的内在评测的度量指标。困惑度可以用来快速地检验算法，困惑度的改进也可以由端对端的评测来加以确认。
在一个测试集上语言模型的困惑度是该语言模型指派给测试集的概率的函数。
对于测试集，困惑度就是用单词数归一化之后的测试集的概率。
语言的加权平均转移因子（weighted average branching factor）是语言中的任何一个单词后面可能接续的单词的数目。
N 元语法的平滑算法
最大似然估计过程的主要问题就是训练 N 元语法的参数，而最大似然估计是建立在特定的训练数据集上，因此会产生数据稀疏（sparse data）问题。
“平滑”（smoothing）是用来填补零计数的概率导致的概率计算问题。
Laplace 平滑
Laplace 平滑（smoothing）或 Laplace 定律（law）：也称为加一平滑（add-one
smoothing）。取语法模型的计数矩阵，先把所有的计数加 1，再对概率进行归一化。在实际应用中，效果不是很好。
Good-Turing 打折法
各种打折算法（Good-Turing 打折法，Witten-Bell 打折法，Kneser-Ney 平滑法）都是利用看过一次的事物的计数来帮助估计从来没有看到过的事物的计数。
只出现过一次的单词或者 N 元语法（或者任何事件）都可以称为单元素（singleton），或者称为罕用语（hapax
legomenon），即只出现过一次的单词。
Good-Turing 打折法就是使用单元素的频率作为零计数的一元语法的频率来重新估计概率量的大小。
Good-Turing 估计
在对 N 元语法进行打折时，不仅使用 Good-Turing 打折法，还需要使用回退和插值算法。
N 元语法的插值法
使用“有层次”的 N 元语法的两种途径：
- 回退法（back off）：当高阶语法计数存在零概率值时，就回退到低阶的 N 元语法中，使用非零概率值进行计算。
- 插值法（interpolation）：把所有的 N 元语法估计中的概率值混合起来，即一元语法、二元语法、……、N 元语法的计数进行加权插值。
N 元语法的回退法
Katz 回退法是使用了 Good-Turing 打折法的回退法。
实际问题：工具包和数据格式
回退 N 元语法模型一般用 ARPA 格式存储。
建立语言模型的工具包：
SRILM 工具包
Cambridge-CMU 工具包
语言模型建模中的高级专题
Kneser-Ney 平滑法
Kneser-Ney 平滑法基于绝对折扣（absolute discounting）的打折方法。
Kneser-Ney 打折法使用更加精致的方法分摊回退值，从而提升绝对折扣
Kneser-Ney 算法使用插值的形式比使用回退的形式效果更好。
基于类别的 N 元语法
基于类别的 N 元语法（class-based N-gram）或聚类 N 元语法（cluster N-gram）是使用单词的类别信息或者聚类信息的 N 元语法的变体。
基于类别的 N 元语法对于处理训练集中的数据稀疏问题效果很好。
IBM 聚类 N 元语法，是一种硬聚类模型；
语言模型的自适应
语言模型的自适应（adaptation）：当某个领域内只有数量很少的训练数据，但是其他领域又存在大量数据时，就会面临语言模型的自适应问题。可以使用领域之外的大量的数据集进行训练，设法使训练得到的模型与某个领域内的小量数据产生自适应。
长距离信息的使用
N 元语法建模中，长距离的上下文信息基本没用。为了更好地利用长距离的上下文信息，可以使用隐藏语言模型（cache
language model）。
跳跃式的 N 元语法（skip N-grams）：上下文可以“跳跃过”某些中间的单词。
可变长的 N 元语法（variable-length N-gram）。
语言模型中结合语言结构的方法参考基于统计剖析的句法结构的语言模型（Ref：Ch14）
基于对话中言语行为的语言模型（Ref：Ch24）
信息论背景
困惑度是建立在信息论（information theory）中关于交叉熵（cross-entropy）概念的基础上。
熵（entropy）是信息量的度量。
可以度量在一个特定的语法中的信息量的多少
可以度量给定语法和给定语言的匹配程度的大小
可以预测一个给定的 N 元语法中下一个单词是什么
计算序列（sequences）的熵。
熵率（entropy rate）：用单词数来除序列的熵所得的值，即每个单词的熵。
平稳（stationary）的随机过程：随着时间的推移，随机过程指派给序列的概率是不变的。
用于比较模型的交叉熵
交叉熵（cross-entropy）。
单词序列 W 上的模型的困惑度形式地定义为交叉熵的指数。
英语的熵和熵率均衡性
英语的熵为概率语法试验提供了可靠的下界；英语的熵帮助信息量最大的内容。
计算英语熵值的方法：
Shannon 计算的是英语中每个字母的熵，熵值偏低；
使用随机模型，在很大的语料库上训练模型，使用很长的英语序列指派对数概率
4.12 小结
N 元语法概率是一个单词在前面给定的 N – 1 个单词的条件下的条件概率。
N 元语法概率可以通过在语料库中简单地计数，并且使之归一化的方法进行计算（最大似然估计 MLE），或者也可以通过更加复杂的算法计算
N 元语法的优点是可以使用丰富的词汇知识
N 元语法的缺点是对训练语料库的依赖太强
平滑算法为 N 元语法概率的估计提供了比最大似然估计更好的解决办法
- 依赖于低阶 N 元语法计数的常用的 N 元语法的平滑算法是回退法和插值法
常用的打折算法
Kneser-Ney 打折法
Witten-Bell 打折法
Good-Turing 打折法
评测 N 元语法的语言模型时，要把语料库分为训练集和测试集两个部分
训练集用于训练模型，测试集用于评测模型
测试集上语言模型的困惑度用于对不同的语言模型进行比较