N元语法
N-1个单词预测下面一个单词
- type(V): 语料库中不同单词的数目或词汇容量的大小
token(N)：使用中全部单词的数目 - disfluencies : fragment, e.g. mainly -- main mainly
filled pauses, e.g. uhs,ums - chain rule of probability - > 二元语法（Markov assumption）
P(wn|wn-1) = C(wn-1wn)/C(wn-1) - training on the test set: 避免测试数据出现在训练数据当中
- unknown word,OOV
在测试集中出现的表外词OOV的百分比称为表外词率(OOV rate)
pseudo-word <UNK>
困惑度(perplexity)
- 测试集上的困惑度(PP)
对于测试集W = w1w2....wN,PP(W) = P(w1w2wN)-1/N
只有当两个模型使用相同的词汇，才能比较性能
平滑
Laplace smoothing(add-one smoothing)
e.g. 一元语法
- p(wi) = ci/N → (ci+1)/(N+V)
- adjusted count c* = ci + 1 → *归一化因子 N/(N+V)
- 平滑看成打折(discounting),把非0的计数降下来，折合到零的计数上，相对折扣dicount dc = c*/c
Good-Turing
- idea:看到过一次的事物计数来帮助估计从来没有看到过的事物的计数
definition: 出现次数为c的N元语法数看成频率c出现的频率，即Nc = Σx:count(x)=c 1
c* = (c+1)Nc+1/Nc
P*GT(训练中从没有见过的事物) = N1/N - 二元语法
假定每个二元语法都是二项式
对于Nc+1=0的，先对Nc进行平滑，替换在所有序列中的零值
插值法
idea:回退法：阶数较高的N元语法存在零计数时，回退到阶数较低的N元语法中；插值法：将不同的N元语法加权插值，即 P(wn|wn-2wn-1)= λ1P(wn|wn-2wn-1) + λ2P(wn|wn-1)+λ3P(wn) and Σi λi = 1
基于类别的N元语法
- IBM聚类
P(wi|wi-1) = P(ci|ci-1) * P(wi|ci)
长距离信息的使用
- 基于主题的语言模型
p(w|h) = Σt p(w|t)p(t|h)
t:topic h:history - 可变n元语法
交叉熵
把某个m作为p的一个模型(m作为p的近似)，m对于p的交叉熵为 H(p,m) = lim-1/n*Σp(w1,.....wn)logm(w1,...wn);
Shannon-McMillan-Breiman 定理 H(p,m) = lim-1/n*Σm(w1,..wn)
- 在单词序列W 上的模型困惑度(perplexity) P定义为Perplexity(W) = 2H(w)
语言和复杂度
- 抽吸引理：
正则语言：设L是一个有限的正则语言。那么必定存在符号串x,y,z，使得对于n >= 0，有 y!=ε且xynz ∈L - DLT
