机器学习笔记之条件随机场(三)MEMM的标注偏置问题

发布于:2022-11-09 ⋅ 阅读:(13) ⋅ 点赞:(0) ⋅ 评论:(0)

引言

上一节介绍了隐马尔可夫模型(Hidden Markov Model,HMM)向最大熵马尔可夫模型(Maximum Entropy Markov Model,MEMM)的演化过程。本节将针对MEMM模型的缺陷,并介绍 条件随机场(Condition Random Field,CRF)。

回顾:最大熵马尔可夫模型

最大熵马尔可夫模型的 观测状态 O \mathcal O O 可分为全局影响(Global)和局部影响(Local)两种:

  • 全局影响意味着 将所有观测变量 o 1 , ⋯   , o T o_1,\cdots,o_T o1,,oT视为一个结点。对应概率图描述如下:
    基于全局影响的MEMM概率图表示
    对应建模对象 P ( I ∣ O ; λ ) \mathcal P(\mathcal I \mid \mathcal O;\lambda) P(IO;λ)表示如下:
    P ( I ∣ O ; λ ) = P ( i 1 ∣ O ; λ ) ⋅ ∏ t = 2 T P ( i t ∣ i t − 1 , O ; λ ) \mathcal P(\mathcal I \mid \mathcal O;\lambda) = \mathcal P(i_1 \mid \mathcal O;\lambda) \cdot \prod_{t=2}^T \mathcal P(i_t \mid i_{t-1},\mathcal O ;\lambda) P(IO;λ)=P(i1O;λ)t=2TP(itit1,O;λ)
  • 局部影响意味着 各时刻的观测变量 o t o_t ot与对应时刻的隐变量 i t i_t it进行关联,但各时刻的观测变量独立性被打破。对应概率图描述如下:
    基于局部影响的MEMM概率图表示
    对应建模对象 P ( I ∣ O ; λ ) \mathcal P(\mathcal I \mid \mathcal O;\lambda) P(IO;λ)表示如下:
    P ( I ∣ O ; λ ) = P ( i 1 , ⋯   , i T ∣ o 1 , ⋯   , o T ; λ ) = P ( i 1 ∣ o 1 ; λ ) ⋅ ∏ t = 2 T P ( i t ∣ i t − 1 , o t ; λ ) \begin{aligned} \mathcal P(\mathcal I \mid \mathcal O;\lambda) & = \mathcal P(i_1,\cdots,i_T \mid o_1,\cdots,o_T;\lambda) \\ & = \mathcal P(i_1 \mid o_1;\lambda) \cdot \prod_{t=2}^{T} \mathcal P(i_t \mid i_{t-1},o_t;\lambda) \end{aligned} P(IO;λ)=P(i1,,iTo1,,oT;λ)=P(i1o1;λ)t=2TP(itit1,ot;λ)

最大熵马尔可夫模型的优点

隐马尔可夫模型相比,最大熵马尔可夫模型的优点体现在两个方面:

  • 最大熵马尔可夫模型概率判别模型,在解码任务(Decoding)中,相比于隐马尔可夫模型,使用更少的计算量对最优隐状态序列进行求解:
    I ^ = arg ⁡ max ⁡ I P ( I ∣ O ; λ ) = arg ⁡ max ⁡ i 1 P ( i 1 ∣ O ; λ ) ⋅ ∏ t = 2 T arg ⁡ max ⁡ i t P ( i t ∣ i t − 1 , O ; λ ) \begin{aligned} \hat {\mathcal I} & = \mathop{\arg\max}\limits_{\mathcal I} \mathcal P(\mathcal I \mid \mathcal O;\lambda) \\ & = \mathop{\arg\max}\limits_{i_1} \mathcal P(i_1 \mid \mathcal O;\lambda) \cdot \prod_{t=2}^T \mathop{\arg\max}\limits_{i_t} \mathcal P(i_t \mid i_{t-1},\mathcal O;\lambda) \end{aligned} I^=IargmaxP(IO;λ)=i1argmaxP(i1O;λ)t=2TitargmaxP(itit1,O;λ)
    相比之下,马尔可夫模型使用维特比算法(Viterbi)使用联合概率分布的迭代方式求解最优状态序列
    δ t ( k ) = max ⁡ i 1 , ⋯   , i t − 1 P ( o 1 , ⋯   , o t , i 1 , ⋯   , i t − 1 , i t = q k ; λ ) δ t + 1 ( j ) = max ⁡ i 1 , ⋯   , i t P ( o 1 , ⋯   , o t + 1 , i 1 , ⋯   , i t , i t + 1 = q j ; λ ) δ t + 1 ( j ) = δ t ( k ) ⋅ a k j ⋅ b j ( o t + 1 ) \begin{aligned} \delta_t(k) & = \mathop{\max}\limits_{i_1,\cdots,i_{t-1}} \mathcal P(o_1,\cdots,o_t,i_1,\cdots,i_{t-1},i_t = q_k;\lambda) \\ \delta_{t+1}(j) & = \mathop{\max}\limits_{i_1,\cdots,i_{t}} \mathcal P(o_1,\cdots,o_{t+1},i_{1},\cdots,i_{t},i_{t+1} = q_j;\lambda) \\ \delta_{t+1}(j) & = \delta_t(k) \cdot a_{kj} \cdot b_j(o_{t+1}) \end{aligned} δt(k)δt+1(j)δt+1(j)=i1,,it1maxP(o1,,ot,i1,,it1,it=qk;λ)=i1,,itmaxP(o1,,ot+1,i1,,it,it+1=qj;λ)=δt(k)akjbj(ot+1)
    但是,含隐变量联合概率分布的计算代价要明显高于条件概率的计算。
  • 最大熵马尔可夫模型打破了观测独立性假设,它使得观测变量间存在关联关系,相比观测独立性假设在序列标注任务(解码任务)中更加合理。

最大熵马尔可夫模型的缺陷

MEMM的缺陷是:造成标注偏置问题(Label Bias Problem)的出现。

标注偏置问题

如果使用一句话描述该问题:在状态转移的过程中,条件概率分布的熵值越低,那么状态转移过程越忽视观测变量

本来是通过观测变量的差异性 来描述隐变量的条件概率结果;但如果熵值过低,导致观测变量的差异性几乎没有对条件概率结果产生影响,最终使状态转移结果与给定观测结果不匹配

标注偏置问题示例

假设存在如下词语数据集
D = { ′ r o b ′ , ′ r o b ′ , ′ r o b ′ , ′ r i b ′ } \mathcal D = \{'rob','rob','rob','rib'\} D={rob,rob,rob,rib}

  • 正常情况下,学习过程中 概率图结构表示如下:
    这个MEMM概率图结构并不严谨,详细见下面红字。
    请添加图片描述
    学习过程(Learning)中,从初始状态 i 1 i_1 i1经过第一次观测进行状态转移,最终得到状态 i 2 i_2 i2。状态 i 2 i_2 i2的条件概率结果表示如下:
    由于四个单词的‘首字母’均相同,均为 r r r。因此,无论是哪个样本,第一次观测的结果均是同一结果。
    P ( i 2 ∣ i 1 , o 2 = r ) = 4 4 = 1 \mathcal P(i_2 \mid i_1,o_2=r) = \frac{4}{4} =1 P(i2i1,o2=r)=44=1
    以此类推,在状态 i 2 i_2 i2的条件下,经过第二次观测,状态转移至 i 3 , i 4 i_3,i_4 i3,i4的条件概率结果分别表示如下:
    四个样本在第二次观测中, o o o占了三个, i i i占了一个,根据概率的频率定义,其状态转移的条件概率取决于当前时刻观测变量出现的频率。
    P ( i 3 ∣ i 2 , o 3 = i ) = 1 4 P ( i 4 ∣ i 2 , o 4 = o ) = 3 4 \begin{aligned} \mathcal P(i_3 \mid i_2,o_3=i) = \frac{1}{4} \\ \mathcal P(i_4 \mid i_2,o_4=o) = \frac{3}{4} \end{aligned} P(i3i2,o3=i)=41P(i4i2,o4=o)=43
    最终的第三次观测,所有样本点的观测结果均是 b b b。因此有:
    P ( i 5 ∣ i 3 , o 5 = b ) = P ( i 5 ∣ i 4 , o 5 = b ) = 1 \mathcal P(i_5 \mid i_3,o_5=b) = \mathcal P(i_5 \mid i_4,o_5=b) = 1 P(i5i3,o5=b)=P(i5i4,o5=b)=1
    上述状态转移过程中,条件概率结果与观测变量的差异性之间存在密切关系。在解码任务(Decoding)中,假设给定 观测序列 r i b rib rib,对应的 P ( I ∣ O ; λ ) \mathcal P(\mathcal I \mid \mathcal O;\lambda) P(IO;λ)表示如下:
    真正的开始是从 i 2 i_2 i2,而 i 3 , i 4 i_3,i_4 i3,i4并不是两个独立的隐变量,而是同一个隐变量在不同概率下的转移结果。这里为了表述方便,将其分成两个部分。但在公式表达中需要将其合并。
    P ( i 4 ∣ i 2 , o 4 = i ) = 0 \mathcal P(i_4 \mid i_2,o_4 = i) = 0 P(i4i2,o4=i)=0恒成立。因为 o 4 o_4 o4选择不了 i i i
    I ^ = arg ⁡ max ⁡ I P ( I ∣ O = r i b ; λ ) = arg ⁡ max ⁡ I P ( i 2 , i 3 , i 4 , i 5 ∣ O = r i b ) = arg ⁡ max ⁡ i 2 P ( i 2 ∣ i 1 , o 2 = r ) ⋅ arg ⁡ max ⁡ i 3 , i 4 [ P ( i 3 ∣ i 2 , o 3 = i ) , P ( i 4 ∣ i 2 , o 4 = i ) ] ⋅ arg ⁡ max ⁡ i 5 [ P ( i 5 ∣ i 3 , o 5 = b ) , P ( i 5 ∣ i 4 , o 5 = b ) ] = P ( i 2 ∣ i 1 , o 2 ) ⋅ P ( i 3 ∣ i 2 , o 3 ) ⋅ P ( i 5 ∣ i 3 , o 5 ) \begin{aligned} \hat {\mathcal I} & = \mathop{\arg\max}\limits_{\mathcal I}\mathcal P(\mathcal I \mid \mathcal O=rib;\lambda) \\ & = \mathop{\arg\max}\limits_{\mathcal I}\mathcal P(i_2,i_3,i_4,i_5 \mid \mathcal O=rib)\\ & = \mathop{\arg\max}\limits_{i_2}\mathcal P(i_2 \mid i_1,o_2=r) \cdot \mathop{\arg\max}\limits_{i_3,i_4}\left[\mathcal P(i_3 \mid i_2,o_3=i),\mathcal P(i_4 \mid i_2,o_4=i)\right] \cdot \mathop{\arg\max}\limits_{i_5}\left[\mathcal P(i_5 \mid i_3,o_5=b),\mathcal P(i_5 \mid i_4,o_5=b)\right]\\ & = \mathcal P(i_2 \mid i_1,o_2) \cdot \mathcal P(i_3 \mid i_2,o_3) \cdot \mathcal P(i_5 \mid i_3,o_5) \end{aligned} I^=IargmaxP(IO=rib;λ)=IargmaxP(i2,i3,i4,i5O=rib)=i2argmaxP(i2i1,o2=r)i3,i4argmax[P(i3i2,o3=i),P(i4i2,o4=i)]i5argmax[P(i5i3,o5=b),P(i5i4,o5=b)]=P(i2i1,o2)P(i3i2,o3)P(i5i3,o5)
    至此,找到最优路径 I ^ = { i 1 , i 2 , i 3 , i 5 } \hat {\mathcal I} = \{i_1,i_2,i_3,i_5\} I^={i1,i2,i3,i5}
  • 基于相同的数据集合,学习过程将概率图结构修改成如下形式
    标注偏置问题-示例
    该图和上图正常情况之间的区别在于:该图是从路径的角度进行划分,而上图是从时刻的角度进行划分
    学习过程中,初始状态 i 0 i_0 i0第一次观测后进行状态转移,分别转移至 i 1 , i 2 i_1,i_2 i1,i2的条件概率表示如下:
    不同于正常情况,此时 i 0 i_0 i0存在两条路径,虽然观测结果全部是 r r r,但从路径的角度观察,存在 3 4 \frac{3}{4} 43概率是样本 r o b rob rob中的 r r r,而仅有 1 4 \frac{1}{4} 41概率是样本 r i b rib rib中的 r r r
    P ( i 2 ∣ i 0 , o 2 = r ) = 3 4 P ( i 1 ∣ i 0 , o 1 = r ) = 1 4 \begin{aligned} \mathcal P(i_2 \mid i_0,o_2 = r) = \frac{3}{4} \\ \mathcal P(i_1 \mid i_0,o_1 = r) = \frac{1}{4} \end{aligned} P(i2i0,o2=r)=43P(i1i0,o1=r)=41
    核心步骤:无论是 i 1 i_1 i1还是 i 2 i_2 i2,它均只存在唯一一条路径 i 1 → i 3 , i 2 → i 4 i_1 \to i_3,i_2 \to i_4 i1i3,i2i4,没有其他选择。这样会导致在该时刻的观测变量无论是什么,都不影响其唯一路径的选择。也就是说,此时的观测变量并不对状态转移过程产生影响
    在路径被确定的条件下, i 1 i_1 i1的概率分布(出度)只有一种选择。
    P ( i 3 ∣ i 1 , o 3 = i ) = P ( i 3 ∣ i 1 ) = 1 P ( i 4 ∣ i 2 , o 4 = o ) = P ( i 4 ∣ i 2 ) = 1 \mathcal P(i_3 \mid i_1,o_3 = i) = \mathcal P(i_3 \mid i_1) = 1 \\ \mathcal P(i_4 \mid i_2,o_4 = o) = \mathcal P(i_4 \mid i_2) = 1 P(i3i1,o3=i)=P(i3i1)=1P(i4i2,o4=o)=P(i4i2)=1
    同理,后续结点由于路径的确定同样也被确定,对应结果如下:
    相比于上一步骤的影响差了很多,因为无论哪条路径,其最后的观测结果都是 b b b
    P ( i 5 ∣ i 3 , o 5 = b ) = P ( i 5 ∣ i 3 ) = 1 P ( i 5 ∣ i 4 , o 5 = b ) = P ( i 5 ∣ i 4 ) = 1 \mathcal P(i_5 \mid i_3,o_5 = b) = \mathcal P(i_5 \mid i_3) = 1 \\ \mathcal P(i_5 \mid i_4,o_5 = b) = \mathcal P(i_5 \mid i_4) = 1 P(i5i3,o5=b)=P(i5i3)=1P(i5i4,o5=b)=P(i5i4)=1
    如果此时给定观测序列 r i b rib rib,再次观察最优路径
    I ^ = arg ⁡ max ⁡ I P ( I ∣ O = r i b ; λ ) = arg ⁡ max ⁡ I [ P ( i 2 ∣ i 0 , o 2 = r ) ⋅ P ( i 4 ∣ i 2 , o 4 = o ) ⋅ P ( i 5 ∣ i 4 , o 5 = b ) ] , [ P ( i 1 ∣ i 0 , o 1 = r ) ⋅ P ( i 3 ∣ i 1 , o 3 = i ) ⋅ P ( i 5 ∣ i 3 , o 5 = b ) ] = P ( i 2 ∣ i 0 , o 2 = r ) ⋅ P ( i 4 ∣ i 2 , o 4 = o ) ⋅ P ( i 5 ∣ i 4 , o 5 = b ) \begin{aligned} \hat {\mathcal I} & = \mathop{\arg\max}\limits_{\mathcal I} \mathcal P(\mathcal I \mid \mathcal O = rib;\lambda) \\ & = \mathop{\arg\max}\limits_{\mathcal I}\left[\mathcal P(i_2 \mid i_0,o_2 = r) \cdot \mathcal P(i_4 \mid i_2,o_4 = o) \cdot \mathcal P(i_5 \mid i_4,o_5 = b)\right],\\ & \left[\mathcal P(i_1 \mid i_0,o_1 = r) \cdot \mathcal P(i_3 \mid i_1,o_3 = i) \cdot \mathcal P(i_5 \mid i_3,o_5 = b)\right] \\ & = \mathcal P(i_2 \mid i_0,o_2 = r) \cdot \mathcal P(i_4 \mid i_2,o_4 = o) \cdot \mathcal P(i_5 \mid i_4,o_5 = b) \end{aligned} I^=IargmaxP(IO=rib;λ)=Iargmax[P(i2i0,o2=r)P(i4i2,o4=o)P(i5i4,o5=b)],[P(i1i0,o1=r)P(i3i1,o3=i)P(i5i3,o5=b)]=P(i2i0,o2=r)P(i4i2,o4=o)P(i5i4,o5=b)
    最优路径 I ^ = { i 0 , i 2 , i 4 , i 5 } \hat {\mathcal I}= \{i_0,i_2,i_4,i_5\} I^={i0,i2,i4,i5},但这个最优路径描述的观测序列 r o b rob rob,与给定序列不符合。

熵的角度观察观测变量存在差异性的部分

  • 正常情况下:
    3 4 log ⁡ 4 3 + 1 4 log ⁡ 4 ≈ 0.5623 \frac{3}{4}\log \frac{4}{3} + \frac{1}{4} \log 4 \approx 0.5623 43log34+41log40.5623
  • 标注偏置现象:
    0 log ⁡ 0 + 1 log ⁡ 1 = 0.0 0 \log 0 + 1 \log 1 = 0.0 0log0+1log1=0.0

标注偏置现象使得观测变量存在差异的部分熵更小,在最大熵思想一节中熵值小意味着概率分布相差较大,距离“等可能”的效果越远,此时状态转移过程概率分布可能已经内定给概率结果大的隐状态,而当前时刻的观测值作用很小,甚至没有作用

下一节将介绍条件随机场

相关参考:
机器学习-条件随机场(3)-MEMM VS CRF