词类标注(part of speech, POS)

• 手写规则[基于规则的标注]
• 统计方法[HMM ，基于转换的标注]

（大多数）英语词的分类

• 封闭类(虚词) 介词
• 开放类 名词、动词、形容词、副词
  给句子指派一个词类标记序列，对包含n个标记的wⁿ₁选择最大可能的标记序列tⁿ₁
  tⁿ₁ = argmax P(tⁿ₁|wⁿ₁)

HMM

• HMM 假设

• 单词出现的概率只与它本身的词类标记有关 P(wⁿ₁|tⁿ₁) = ∏P(w_i|t_i)
• 标记出现的概率只与它前一个标记有关 P(tⁿ₁) = ∏ P(t_i|t_i-1)

• 算法的形式化

Q = q₁q₂...q_N; N个状态(state)的集合
A = a₁₁a₁₂...a_n1..a_mn:状态转移矩阵(transition probability matrix) A
O = o₁o₂...o_T:T个观察(observations)序列,每个观察来自词汇V = v₁v₂...v_v
B = b_i(o_i):观察似然度(observation likehoods)的序列，又称发射序列。每个观察似然度表示从状态i生成的观察值o_i的概率
q₀,q_r:特定的开始和特定的终结状态

A 对应先验概率(prior)
B 对应似然度(likelihood)

• Viterbi算法
  取一个单独的HMM和所观察的单词序列O = (o₁o₂...o_t)作为输入，返回概率最大的状态/标记序列Q = (q₁q₂...q_T)以及它们的概率作为输出

v_t(j) = max v_t-1(i)a_ijb_j(o_t)

TBL

三阶段：
1.每个单词标记
2.检查每一个可能的转换，选择最大程度改善标注的转换
3.根据这个规则对数据进行重新标注

隐马尔科夫和最大熵模型

马尔可夫链

不能表示固有的歧义问题
其他表示方法：

π = π₁,π₂,...π_N 在状态上的初始概率分布
QA = |q_x,q_y,... | 合法的接收状态集合

HMM

假设1、特定状态只与前一状态有关
假设2、输出观察只与产生该观察的状态有关

• 三个基本问题

似然度问题：给定HMM λ(A,B)和一观察序列O，确定似然度P(O|λ)
解码问题: 给定一观察序列和HMM λ(A,B)找出隐藏状态序列
学习问题：给定一观察序列和状态集合，学习HMM λ(A,B)

问题1

对于特定的隐藏状态序列Q： q₁,q₂,....q_T以及
O: o₁,o₂,......o_T观察序列的似然度
P(O|Q) = ∏P(o_i|q_i)
联合概率：P(O,Q) = P(O|Q) X P(Q) = ∏ P(o_i|q_i) x ∏P(q_i|q_i-1)
去除特定条件：
P(O) = ∑P(O,Q) = ∑P(O|Q)P(Q)

• 向前算法：O(N^T) -- O(N²T)

α _t(j) 表示对于给定的自动机λ,在看了前t个观察之后，在状态j的概率,α _t(j)=P(o₁o₂..o_tq_t=j|λ)(注：这里的状态是给出前t个观察之后，处于qj的观察状态，附带观察)

α_t(j) = ∑α_t-1(j) a_ijb_j(o_t)

前向算法图

问题2

• Viterbi算法

v_t(j) 表示对于给定的自动机λ,HMM在看了前t个观察并通过了概率最大的状态序列q₀,q₁,...q_t-1之后在状态j的概率。v_t(j) = maxP(q₀q₁...q_t-1,o₁,o₂,...o_t,q_t= j|λ)

v_t(j) = maxv_t-1(i)a_ijb_j(o_t)

问题3

• 向前-向后算法
  在状态i和状态j之间的一个特定的转移概率a_ij的最大似然估计通过转移次数来计算，a_ij = C(i→j)/∑C(i→q)

• 反复地估计所得的计数，从转移概率和观察概率的估计值开始，反复地使用这些估计概率来推出越来越好的概率
• 对于一个观察，计算它二点前向概率，从而得到
  估计概率，把该估计量对前向概率有贡献的所有不同路径平摊

向后概率β表示对于给定的自动机λ，在状态i和时刻t观察从时刻t+1到终点的观察概率。β_t(i) = P(o_t+1,o_t+2,...o_T|q_t = i,λ)

a_ij = 从状态i转移到状态j的期望/从状态i转移的期望数
ξ_t(i,j) = P(q_t=i,q_t+1=j|O,λ)
not-quite-ξ_t(i,j) = P(q_t=i,q_t+1=j,O|λ) = α_t(i)a_ijb_j(o_t+1)β_t+1(j)
=> P(X|Y,Z) = P(X,Y|Z)/P(Y|Z)
P(O|λ) = α_T(N) = β_T(1) = ∑_jα_t(j)β(j)

a_ij = ∑_tξ_t(i,j)/∑_t∑_jξ_t(i,j)

b_i(v_k) 表示在给定状态j，观察V中的一个给定的符号v_k的概率， = 观察词汇V中的一个给定的符号v_k的期望数/状态j的期望次数

γ_t(j) = P(q_t = j | O,λ) = P(q_t=j,O|λ) / P(O|λ) = α_t(j)β_t(j)/P(O|λ)

EM算法

最大熵

与HMM不同之处： 直接比较后验概率,不使用似然度与先验分离的模型
T = argmaxP(T|W) = argmax ∏P(tag_i|word_i,tag_i-1)

HMM:
针对给定观察的状态序列概率：
P(Q|O) = ∏P(o_i|q_i) x ∏P(q_i|q_i-1)
MEMM:
P(Q|O) = ∏P(q_i|q_i-1,o_i)
p(q|q',o) = exp(∑w_if_i(o,q))/Z(o,q')

MEMM的解码和训练

对于状态j在时间t的Viterbi值
v_t(j) = max v_t-1(i)a_ijb_j(o_t) , 1 <= j <= N, 1 < t <= T