当前位置:   article > 正文

UCAS - AI学院 - 自然语言处理专项课 - 第6讲 - 课程笔记_ucas自然语言处理git

ucas自然语言处理git

隐马尔可夫模型与条件随机场

马尔可夫模型

  • 马尔可夫模型描述:如果一个系统有 N N N个状态 S i S_i Si,随着时间的推移,该系统从某一个状态转移到另一个状态。如果 t t t时刻的状态变量为 q t q_t qt,则 t t t时刻状态值为 S j S_j Sj的概率取决于前面所有时刻的状态,即 p ( q t = S j ∣ q t − 1 = S i , …   ) p(q_t = S_j | q_{t - 1} = S_i, \dots) p(qt=Sjqt1=Si,)
  • 离散一阶马尔可夫链: t t t时刻状态只与 t − 1 t - 1 t1时刻状态有关,即 p ( q t = S j ∣ q t − 1 = S i ) p(q_t = S_j | q_{t - 1} = S_i) p(qt=Sjqt1=Si)
  • 马尔可夫模型:满足不动性假设,状态与时间无关(但是与前一时刻状态有关), p ( q t = S j ∣ q t − 1 = S i , …   ) = a i j p(q_t = S_j | q_{t - 1} = S_i, \dots) = a_{ij} p(qt=Sjqt1=Si,)=aij
  • 状态转移概率约束条件
    • a i j ≥ 0 a_{ij} \ge 0 aij0
    • ∑ j a i j = 1 \sum_j a_{ij} = 1 jaij=1
  • 可以把马尔可夫模型视为随机的有限状态自动机,状态转换对应一个相应的概率
  • 计算一个状态序列的概率:

p ( S 1 , … , S T ) = p ( S 1 ) ⋅ p ( S 2 ∣ S 1 ) ⋅ p ( S 3 ∣ S 1 , S 2 ) ⋅ … ⋅ p ( S T ∣ S 1 , … , S T − 1 ) = p ( S 1 ) ⋅ p ( S 2 ∣ S 1 ) ⋅ p ( S 3 ∣ S 2 ) ⋅ … ⋅ p ( S T ∣ S T − 1 ) = π S 1 ∏ t = 1 T − 1 a S t S t + 1 p(S1,,ST)=p(S1)p(S2|S1)p(S3|S1,S2)p(ST|S1,,ST1)=p(S1)p(S2|S1)p(S3|S2)p(ST|ST1)=πS1T1t=1aStSt+1 p(S1,,ST)=p(S1)p(S2S1)p(S3S1,S2)p(STS1,,ST1)=p(S1)p(S2S1)p(S3S2)p(STST1)=πS1t=1T1aStSt+1

隐马尔可夫模型

  • 双重随机过程,不知道具体状态序列,只知道状态转移的概率,可观察事件的随机过程是隐蔽状态转换过程的随机函数
  • HMM组成
    • 模型中状态数为 N N N
    • 每一个状态可能输出的符号数 M M M
    • 状态转移概率矩阵 A A A a i j = p ( q t + 1 = S j ∣ q t = S i ) a_{ij} = p(q_{t + 1} = S_j | q_t = S_i) aij=p(qt+1=Sjqt=Si)
    • 状态到输出概率矩阵 B B B b j ( k ) = p ( O t = v k ∣ q t = S j ) b_j(k) = p(O_t = v_k | q_t = S_j) bj(k)=p(Ot=vkqt=Sj)
    • 初始概率分布 π \pi π π i = p ( q 1 = S i ) \pi_i = p(q_1 = S_i) πi=p(q1=Si)
    • 记为五元组 ( N , M , A , B , π ) (N, M, A, B, \pi) (N,M,A,B,π)
  • 从HMM到观察序列:开始状态——状态转移——输出——状态转移
  • 给定HMM和观察序列,求序列概率 p ( O ∣ μ ) p(O | \mu) p(Oμ)
    • 前向算法
      • 定义前向变量 α t ( i ) = P ( O 1 … O t , q t = S i ∣ μ ) \alpha_t(i) = P(O_1 \dots O_t, q_t = S_i | \mu) αt(i)=P(O1Ot,qt=Siμ)
      • α 1 ( i ) = π i b i ( O 1 ) \alpha_1(i) = \pi_i b_i(O_1) α1(i)=πibi(O1)
      • α t + 1 ( j ) = [ ∑ i α t ( i ) ⋅ a i j ] ⋅ b j ( O t + 1 ) \alpha_{t + 1}(j) = [\sum_i \alpha_t(i) \cdot a_{ij}] \cdot b_j(O_{t + 1}) αt+1(j)=[iαt(i)aij]bj(Ot+1)
      • p ( O ∣ μ ) = ∑ i α T ( i ) p(O|\mu) = \sum_i \alpha_T(i) p(Oμ)=iαT(i)
      • 时间复杂度 O ( N 2 T ) O(N^2T) O(N2T)
    • 后向算法
      • 定义后向变量 β t ( i ) = p ( O t + 1 … O T ∣ q t = S i , μ ) \beta_t(i) = p(O_{t + 1} \dots O_T | q_t = S_i, \mu) βt(i)=p(Ot+1OTqt=Si,μ)
      • β T ( i ) = 1 \beta_T(i) = 1 βT(i)=1
      • β t ( i ) = ∑ j a i j b j ( O t + 1 ) ⋅ β t + 1 ( j ) \beta_t(i) = \sum_j a_{ij} b_j(O_{t + 1}) \cdot \beta_{t + 1}(j) βt(i)=jaijbj(Ot+1)βt+1(j)
      • p ( O ∣ μ ) = ∑ i β 1 ( i ) ⋅ π i ⋅ b i ( O 1 ) p(O | \mu) = \sum_i \beta_1(i) \cdot \pi_i \cdot b_i(O_1) p(Oμ)=iβ1(i)πibi(O1)
      • 时间复杂度 O ( N 2 T ) O(N^2T) O(N2T)
  • 给定HMM和观察序列,发现最优状态序列
    • 最优:每个时刻 γ t ( i ) = p ( q t = S i ∣ O , μ ) \gamma_t(i) = p(q_t = S_i |O, \mu) γt(i)=p(qt=SiO,μ)最大的 q t q_t qt
      • p ( q t = S i , O ∣ μ ) = α t ( i ) β t ( i ) p(q_t = S_i, O| \mu) = \alpha_t(i) \beta_t(i) p(qt=Si,Oμ)=αt(i)βt(i)
      • p ( O ∣ μ ) = ∑ i α t ( i ) β t ( i ) p(O|\mu) = \sum_i \alpha_t(i) \beta_t(i) p(Oμ)=iαt(i)βt(i)
      • γ t ( i ) = α t ( i ) β t ( i ) ∑ i α t ( i ) β t ( i ) \gamma_t(i) = \frac {\alpha_t(i) \beta_t(i)}{\sum_i \alpha_t(i) \beta_t(i)} γt(i)=iαt(i)βt(i)αt(i)βt(i)
      • 最佳状态 q ^ t = arg ⁡ max ⁡ i γ t ( i ) \hat q_t = \arg \max _i \gamma_t(i) q^t=argmaxiγt(i)
      • 问题:单独状态最优不一定整个状态序列最优
    • 最优:最大概率的状态序列 Q ^ = arg ⁡ max ⁡ Q p ( Q ∣ O , μ ) \widehat Q = \arg \max_Q p(Q| O, \mu) Q =argmaxQp(QO,μ)
      • Viterbi算法, δ t ( i ) = max ⁡ p ( q 1 … q t = S i , O 1 … O t ∣ μ ) \delta_t(i) = \max p(q_1 \dots q_t = S_i, O_1 \dots O_t | \mu) δt(i)=maxp(q1qt=Si,O1Otμ),到达 S i S_i Si,输出 O O O的最大概率
      • δ 1 ( i ) = π i b i ( O 1 ) \delta_1(i) = \pi_i b_i(O_1) δ1(i)=πibi(O1),路径变量 Ψ 1 ( i ) = 0 \Psi_1(i) = 0 Ψ1(i)=0
      • δ t + 1 ( i ) = max ⁡ j [ δ t ( j ) ⋅ a j i ] ⋅ b i ( O t + 1 ) \delta_{t + 1}(i) = \max_j [\delta_t(j) \cdot a_{ji}] \cdot b_i(O_{t + 1}) δt+1(i)=maxj[δt(j)aji]bi(Ot+1) Ψ t + 1 ( i ) = arg ⁡ max ⁡ j [ δ t ( j ) ⋅ a j i ] ⋅ b i ( O t + 1 ) \Psi_{t + 1}(i) = \arg \max_j [\delta_t(j) \cdot a_{ji}] \cdot b_i(O_{t + 1}) Ψt+1(i)=argmaxj[δt(j)aji]bi(Ot+1)
      • Q ^ T = arg ⁡ max ⁡ j δ t ( j ) \widehat Q_T = \arg \max_j \delta_t(j) Q T=argmaxjδt(j) p ^ ( Q ^ T ) = max ⁡ j δ T ( j ) \hat p(\widehat Q_T) = \max_j \delta_T(j) p^(Q T)=maxjδT(j)
      • 时间复杂度 O ( N 2 T ) O(N^2T) O(N2T)
      • 提升搜索速度,剪枝策略
        • 只选择大于某一阈值的 δ \delta δ
        • 限制路径的个数(类似Beam Search)
      • 连乘溢出——取对数
  • 给定观察序列,训练HMM参数,使得 p ( Q ∣ μ ) p(Q | \mu) p(Qμ)最大——BW算法
    • 大量样本
      • π ˉ i = δ ( q 1 , S i ) \bar \pi_i = \delta(q_1, S_i) πˉi=δ(q1,Si)
      • a ˉ i j = ∑ t δ ( q t , S i ) ⋅ δ ( q t + 1 , S j ) ∑ t δ ( q t , S i ) \bar a_{ij} = \frac {\sum_t \delta(q_t, S_i) \cdot \delta(q_{t + 1}, S_j)}{\sum_t \delta(q_t, S_i)} aˉij=tδ(qt,Si)tδ(qt,Si)δ(qt+1,Sj)
      • δ ( x , y ) \delta(x, y) δ(x,y)为Kronecker函数,只在 x = y x = y x=y是取1,否则取0
      • b ˉ j ( k ) = ∑ t δ ( q t , S j ) ⋅ δ ( O t , v k ) ∑ t δ ( q t , S j ) \bar b_j(k) = \frac {\sum_t \delta(q_t, S_j) \cdot \delta(O_t, v_k)}{\sum_t \delta(q_t, S_j)} bˉj(k)=tδ(qt,Sj)tδ(qt,Sj)δ(Ot,vk)
    • 样本不足——EM算法
      • 满足非负和归一化性质的随机初始化
      • E步,计算期望
      • ξ t ( i , j ) = p ( q t = S i , q t + 1 = S j ∣ O , μ ) = p ( q t = S i , q t + 1 = S j , O ∣ μ ) p ( O ∣ μ ) = α t ( i ) a i j b i ( O t + 1 ) β t + 1 ( j ) ∑ i ∑ j α t ( i ) a i j b i ( O t + 1 ) β t + 1 ( j ) \xi_t(i, j) = p(q_t = S_i, q_{t + 1} = S_j | O, \mu) = \frac {p(q_t = S_i, q_{t + 1} = S_j, O | \mu)}{p(O | \mu)} = \frac {\alpha_t(i) a_{ij} b_i(O_{t + 1})\beta_{t + 1}(j)}{\sum_i \sum_j \alpha_t(i) a_{ij} b_i(O_{t + 1})\beta_{t + 1}(j)} ξt(i,j)=p(qt=Si,qt+1=SjO,μ)=p(Oμ)p(qt=Si,qt+1=Sj,Oμ)=ijαt(i)aijbi(Ot+1)βt+1(j)αt(i)aijbi(Ot+1)βt+1(j)
      • γ t ( i ) = ∑ j ξ t ( i , j ) \gamma_t(i) = \sum_j \xi_t(i, j) γt(i)=jξt(i,j)
      • M步,重新估计
      • π i = γ 1 ( i ) \pi_i = \gamma_1(i) πi=γ1(i)
      • a i j = ∑ t ξ t ( i , j ) γ t ( i ) a_{ij} = \frac {\sum_t \xi_t(i, j)}{\gamma_t(i)} aij=γt(i)tξt(i,j)
      • b j ( k ) = ∑ t γ t ( j ) ⋅ δ ( O t , v k ) ∑ t γ t ( j ) b_j(k) = \frac{\sum_t \gamma_t(j) \cdot \delta(O_t, v_k)}{\sum_t \gamma_t(j)} bj(k)=tγt(j)tγt(j)δ(Ot,vk)
      • 小数溢出——放大系数

隐马尔可夫模型的应用

  • 汉语自动分词和词性标注
    • 考虑的问题
      • HMM的状态、观察的数目
      • 参数估计
    • 思路
      • 汉语分词的结果作为观察序列 O ^ = arg ⁡ max ⁡ O p ( O ∣ μ ) \widehat O = \arg \max_O p(O | \mu) O =argmaxOp(Oμ)
      • 词性标注作为状态序列 Q ^ = arg ⁡ max ⁡ Q p ( Q ∣ O , μ ) \widehat Q = \arg \max_Q p(Q | O, \mu) Q =argmaxQp(QO,μ)
    • 过程
      • 估计模型参数
      • 对于可能的输出序列,找到最大概率 p ( O ∣ μ ) p(O | \mu) p(Oμ)候选
      • 快速选择最优状态序列
    • 参数
      • 观察序列:单词序列
      • 状态序列:词类标记序列
      • 状态数目:词类标记符号个数
      • 输出符号数:每个状态可输出不同词汇的个数
    • 参数估计
      • 无任何语料:无指导学习方法
        • 获取词类个数
        • 获取对应每种词类的词汇数
        • EM迭代
      • 存在大规模语料:有指导学习方法
        • 最大似然估计
    • 获取观察序列
      • 借助其他分词工具获得nbest的可能切分
    • 错误驱动修正参数
      • 一部分语料——训练模型
      • 模型——标注一部分新的语料
      • 新的语料标注——人工校对
      • 校对好的语料——训练模型
      • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qDHqv4Uj-1587384099332)(assets/image-20200401014753740.png)]

条件随机场及其应用

  • 基本思路:给定观察序列 X X X,输出标识序列 Y Y Y,通过计算 P ( Y ∣ X ) P(Y | X) P(YX)求解最优标注序列

  • 定义:设无向图 G = ( V , E ) G=(V, E) G=(V,E) V V V中每个结点对应一个随机变量 Y v Y_v Yv,其取值范围为集合 { y } \{y\} {y}。如果以 X X X为条件,每个随机变量都满足马尔可夫特性:

    • $$

$$

  • 其中 w ∼ v w \sim v wv表示二者邻近,那么 ( X , Y ) (X, Y) (X,Y)就是一个条件随机场

  • 序列问题就可以建模为简单的链式结构图,结点对应标记序列 Y Y Y中的元素

  • 理论上如果具备一定的条件独立性,图结构可以是任意的

  • 相比于HMM,内结点并不生成外结点,而是对外结点的标记,且可以受任意邻近结点的影响

  • 给定观察序列,特定标记序列的概率定义为:
    $$

p(Y|X) = \exp \left( \sum_j \lambda_j t_j(y_{i - 1}, y, X, i) + \sum_k \mu_k s_k (y_i, X, i) \right)
$$

  • 其中
    • t j ( y i − 1 , y , X , i ) t_j(y_{i - 1}, y, X, i) tj(yi1,y,X,i)为转移函数, i i i i − 1 i - 1 i1位置上的标记的转移概率
    • s k ( y i , X , i ) s_k (y_i, X, i) sk(yi,X,i)为状态函数, i i i位置上的标记概率
    • λ \lambda λ μ \mu μ分别为权重
  • 定义一组关于观察序列的二值特征 b ( X , i ) b(X, i) b(X,i),表示训练样本特征的分布,当 i i i位置为某一特定词时记1,否则记0
  • 对转移函数,如果 y i − 1 y_{i - 1} yi1 y i y_i yi满足某种搭配条件,记 b ( X , i ) b(X, i) b(X,i),否则记0
  • 状态函数改写 s k ( y i , X , i ) = s k ( y i − 1 , y i , X , i ) s_k (y_i, X, i) = s_k (y_{i - 1}, y_i, X, i) sk(yi,X,i)=sk(yi1,yi,X,i)
  • 特征函数统一表示为 F j ( Y , X ) = ∑ i f j ( y i − 1 , y i , X , i ) F_j(Y, X) = \sum _i f_j(y_{i - 1}, y_i, X, i) Fj(Y,X)=ifj(yi1,yi,X,i)
    • 局部特征函数表示状态特征或转移函数
    • 概率形式 p ( Y ∣ X , λ ) = 1 Z ( X ) exp ⁡ ( ∑ j λ j F j ( Y , X ) ) p(Y | X, \lambda) = \frac 1 {Z(X)} \exp(\sum_j \lambda_j F_j(Y, X)) p(YX,λ)=Z(X)1exp(jλjFj(Y,X))——类似最大熵!
    • Z ( X ) Z(X) Z(X)是对 Y Y Y的归一化因子
  • 解决问题
    • 特征选取
    • 参数训练
    • 解码
  • 应用:由字构词(基于字标注)的分词方法
    • 基本思想:字的分类,每个字在构词时由构词位置(词首B、词中M、词尾E、单独成词S)
    • 对所有子根据预定义特征进行词位特征学习,获得一个概率模型,在待切分串上,根据字间紧密程度,获得分类结果,最后根据词位定义直接获得最终的分词结果
    • 特征选择
      • 一元特征(状态函数):当前字
      • 二元特征(转移函数):前一个字到当前字
    • 参数训练
      • 使用训练语料训练权重,寻找标记序列,使 P ( Y ∣ X ) P(Y|X) P(YX)最大
      • BP?损失函数 L ( λ ) − log ⁡ p ( Y ∣ X , λ ) + ϵ 2 λ 2 L(\lambda) - \log p(Y | X, \lambda) + \frac \epsilon 2 \lambda^2 L(λ)logp(YX,λ)+2ϵλ2
    • 解码
      • Viterbi算法,寻找最优路径
      • 路径得分
        • 一元特征权重 W W W W 1 B W_1^B W1B表示第1个字被标记为B的权重
        • 路径得分 R R R R 2 B R_2^B R2B表示第二个字被标记为B时的路径得分
        • 转移特征权重 T T T T B M T_BM TBM表示由B转移到M的权重
      • 迭代计算
        • R i + 1 B = max ⁡ { T E B × R i E , T S B × R i S } × W i + 1 B R_{i + 1}^B = \max \{T_{EB} \times R_i^E, T_{SB} \times R_i^S\} \times W_{i + 1}^B Ri+1B=max{TEB×RiE,TSB×RiS}×Wi+1B
        • 以此类推
        • W W W包含当前状态特征以及前后的转移特征
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/751362
推荐阅读
相关标签
  

闽ICP备14008679号