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(w_n|w_n-1) = C(w_n-1w_n)/C(w_n-1)
• training on the test set: 避免测试数据出现在训练数据当中
• unknown word,OOV
  在测试集中出现的表外词OOV的百分比称为表外词率(OOV rate)
  pseudo-word <UNK>

困惑度(perplexity)

• 测试集上的困惑度(PP)
  对于测试集W = w₁w₂....w_N,PP(W) = P(w₁w₂w_N)^-1/N
  只有当两个模型使用相同的词汇，才能比较性能

平滑

Laplace smoothing(add-one smoothing)
e.g. 一元语法

• p(w_i) = c_i/N → (c_i+1)/(N+V)
• adjusted count c^* = c_i + 1 → *归一化因子 N/(N+V)
• 平滑看成打折(discounting),把非0的计数降下来，折合到零的计数上，相对折扣dicount d_c = c^*/c

Good-Turing

• idea:看到过一次的事物计数来帮助估计从来没有看到过的事物的计数
  definition: 出现次数为c的N元语法数看成频率c出现的频率，即N_c = Σ_x:count(x)=c 1
  c^* = (c+1)N_c+1/N_c
  P^*_GT(训练中从没有见过的事物) = N₁/N
• 二元语法
  假定每个二元语法都是二项式
  对于N_c+1=0的，先对N_c进行平滑，替换在所有序列中的零值

插值法

idea:回退法：阶数较高的N元语法存在零计数时，回退到阶数较低的N元语法中；插值法：将不同的N元语法加权插值，即 P(w_n|w_n-2w_n-1)= λ₁P(w_n|w_n-2w_n-1) + λ₂P(w_n|w_n-1)+λ₃P(w_n) and Σ_i λ_i = 1

基于类别的N元语法

• IBM聚类
  P(w_i|w_i-1) = P(c_i|c_i-1) * P(w_i|c_i)

长距离信息的使用

• 基于主题的语言模型
  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(w₁,.....w_n)logm(w₁,...w_n);
Shannon-McMillan-Breiman 定理 H(p,m) = lim-1/n*Σm(w₁,..w_n)

• 在单词序列W 上的模型困惑度(perplexity) P定义为Perplexity(W) = 2^H(w)

语言和复杂度

• 抽吸引理：
  正则语言：设L是一个有限的正则语言。那么必定存在符号串x,y,z，使得对于n >= 0，有 y!=ε且xyⁿz ∈L
• DLT