N元語法

N-1個單詞預測下面一個單詞

• type(V): 語料庫中不同單詞的數(shù)目或詞匯容量的大小
  token(N)：使用中全部單詞的數(shù)目
• 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: 避免測試數(shù)據(jù)出現(xiàn)在訓練數(shù)據(jù)當中
• unknown word,OOV
  在測試集中出現(xiàn)的表外詞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的計數(shù)降下來，折合到零的計數(shù)上，相對折扣dicount d_c = c^*/c

Good-Turing

• idea:看到過一次的事物計數(shù)來幫助估計從來沒有看到過的事物的計數(shù)
  definition: 出現(xiàn)次數(shù)為c的N元語法數(shù)看成頻率c出現(xiàn)的頻率，即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:回退法：階數(shù)較高的N元語法存在零計數(shù)時，回退到階數(shù)較低的N元語法中；插值法：將不同的N元語法加權(quá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