隐马尔科夫模型及在Query拼写纠错中的应用


人清(陈如山) renqing.crs@taobao.com 隐马尔科夫模型及在Query拼写 纠错中的应用 自我介绍 • 花名:人清 • 真名:陈如山 • 邮箱:renqing.crs@taobao.com • 职位:广告算法-基础研究(自然语言处理) 主要内容  Markov Model (马尔科夫模型)  Hidden Markov Model (隐马尔科夫模型)  Forward-backward Algorithm(前向后向算法)  参数估计  计算观测序列概率  得到最优状态序列  HMM 在 Query 纠错中的应用 Markov Model Markov model • 未来只取决于现在,而跟过去无关 Markov model • 未来只取决于现在,而跟过去无关 • 通常用于处理序列事件 – 天气预测 – 经济形势预测 – 语言模型 –…… What is the end of this ____ ? Markov model • 未来只取决于现在,而跟过去无关 • 通常用于处理序列事件 – 天气预测 – 经济形势预测 – 语言模型 –…… What is the end of this ____ ? Markov model • 给定一个随机变量序列 S1, S2, S3, ...... 1 1 1 2 2 1( | , ,..., )( | )t t t t t tPS sSsSs Ss PS sSs       Markov model • 给定一个随机变量序列 S1, S2, S3, ...... • 对于一个序列事件 1 1 1 2 2 1( | , ,..., )( | )t t t t t tPS sSsSs Ss PS sSs       S1 S2 S3 ST... ... 1 2 1 2 1 1( ... ) ( ) ( | )...... ( | )TTTPsss PsPss Pss  Markov Model • Markov Model 参数 – initial probability (初始概率) – transition probability (转换概率) 1( ) k = 1, 2, ..., Mk P S k  ,1( | ) k,l = 1, 2, ..., Mk l t ta P S l S k   k ,kla S1 S2 S3 ST... ...1S 1,TTSSa 12,SSa 23,SSa 34,SSa Markov model • 一周经济形势预测 – 三个状态 Bull Market, Bear Market, Recession – 转换概率 P(Bull Market | Bull Market) = 0.9 P(Bear Market | Bull Market) = 0.075 ... ... Markov model • 但是有时我们不能直接得到状态序列 比如:语音识别,我们只能得到声波信号: 而我们要的是“他到底说了什么” 这时候就需要用到 Hidden Markov Model Hidden Markov Model Hidden Markov Model • 处理这样的序列事件 o1o2...oT:可以观测到的数据 s1 s2 ... sT:隐藏于观测数据乊后的状态转换序列 其中 st 只依赖于 st-1,ot 只依赖于 st S1 S2 S3 ST... ... O1 O2 O3 OT Hidden Markov Model • 联合概率 HMM 的参数 – initial probability (初始概率) – transition probability(转换概率) – emission probability(发射概率) 1 2 1 2 1 1 1 2 1 2 2 1 ( ... ... ) ()( | )( | )( | )...... ( | )( | ) TT TTTT P o o o s s s PsPosPssPos Ps sPos Hidden Markov Model • 联合概率 • HMM 的参数 – initial probability (初始概率) – transition probability(转换概率) – emission probability(发射概率) 1 2 1 2 1 1 1 2 1 2 2 1 ( ... ... ) ()( | )( | )( | )...... ( | )( | ) TT TTTT P o o o s s s PsPosPssPos Ps sPos 1( ) k = 1,2,...,Mk P S k  ,1( | ) k,l = 1,2,...,Mk l t ta P S l S k   k ,kla ( ) ( | ) u=1,2,...,N k=1,2,...,Mk t tb u P O u S k   ()kbu Hidden Markov Model S1 S2 S3 ST... ... O1 O2 O3 OT 1S 12,SSa 23,SSa 34,SSa 1,TTSSa  1 1()SbO 2 2()SbO 3 3()SbO ()TSTbO Hidden Markov Model S1 S2 S3 ST... ... O1 O2 O3 OT 1S 12,SSa 23,SSa 34,SSa 1,TTSSa  1 1()SbO 2 2()SbO 3 3()SbO ()TSTbO 11 1: 1: 1 1 1 2 1 1 1 11 ( , ) ()( |)( |)......(| )( |) ( )i i i t t t t t t tt s s s s i ii Pos PsPosPss Pss Pos a b o        Hidden Markov Model • 三个基本问题 – 给定观测序列,模型参数怎么估计 = M 个 + M*M 个 + M*N 个 (其中 N 和 M 是给定的) – 给定 ,计算一个观测序列出现的概率 – 给定 和观测序列 O,找到最优的隐藏状态序列 k ,kla ()kbu Hidden Markov Model • 三个基本问题 – 给定观测序列,模型参数怎么估计 = M 个 + M*M 个 + M*N 个 (其中 N 和 M 是给定的) – 给定 ,计算一个观测序列出现的概率 – 给定 和观测序列 O,找到最优的隐藏状态序列 k ,kla ()kbu ()PO Hidden Markov Model • 三个基本问题 – 给定观测序列,模型参数怎么估计 = M 个 + M*M 个 + M*N 个 (其中 N 和 M 是给定的) – 给定 ,计算一个观测序列出现的概率 – 给定 和观测序列 O,找到最优的隐藏状态序列 k ,kla ()kbu ()PO * arg max ( | ) S SPSO 概率基础知识(aside) ()(,) y P X x P X x Y y    (,)( | ) () P X x Y yP X x Y y P Y y     (,|) (|)(|,)PXYZPXZPYXZ ( | , ) ( | ) if , ZPXYZPXZXY 给定 相互独立 Forward-backward Algorithm • 前向概率 • 后向概率 S1 S2 k ST... ... O1 O2 Ot OT ... ... St-1 Ot-1 St+1 Ot+1 1:()(,)t t tk P o S k  Forward-backward Algorithm • 前向概率 • 后向概率 S1 S2 k ST... ... O1 O2 Ot OT ... ... St-1 Ot-1 St+1 Ot+1 S1 S2 k ST... ... O1 O2 Ot OT ... ... St-1 Ot-1 St+1 Ot+1 1:()(,)t t tk P o S k  1:( ) ( | )t t T tk P o S k  前向概率 • 简单方法 已知 1: 1 1: 1: 1: 1 ()(,) ( , , ) t t t t t t t s k P o S k P o s S k      1: 1:(,)ttP o s k ST... ... O1 O2 Ot OTOt-1 St+1 Ot+1 MM... ... M M-1 M-1 ... ... M-1 1 1 ... ... 1 前向概率 • 时间复杂度 共有 个不同的 不可接受 !! 1: 1ts  1tM  1( ) for ( ) ( ) for all [1, ] ( ) for all [1, ], t t t T O M k O M k M O M k M t T    前向概率 • 时间复杂度 共有 个不同的 不可接受 !! 1: 1ts  1tM  1( ) for ( ) ( ) for all [1, ] ( ) for all [1, ], t t t T O M k O M k M O M k M t T    前向概率 • Dynamic Programming (DP) 能不能重用 ?1( ) [1, ]t l l M   S1 S2 k ST... ... O1 O2 Ot OT ... ... l Ot-1 St+1 Ot+1 前向概率 • Dynamic Programming (DP) 1: 1: 1 1 1: 1 1 1: 1 1 1 1:1 1 1:11 1:11 1 1 1: 1 1 ()(,) (,,) ( | , , ) ( , , ) (|, , )( |, )(, ) ( | ) ( | ) ( , t t t M t t t l M t t t t t t t l M t t t t t t t t t l t t t t t t k P o S k P o S k S l Poo S kS lPo S kS l Poo SkS lPSko S lPo S l PoS kPS kS lPo S                                          1 ,1 1 ) ()() M l M k t l k t l l b o a l         前向概率 • 时间复杂度 • 前向概率计算公式 2 2 ( ) for ( ) ( ) for all [1, ] ( ) for all [1, ], [1, ] tO M k O M k M O T M k M t T      前向概率 • 时间复杂度 • 前向概率计算公式 2 2 ( ) for ( ) ( ) for all [1, ] ( ) for all [1, ], [1, ] tO M k O M k M O T M k M t T      1 ,1 1 ( ) if t =1 () ( ) ( ) otherwise kk M t k t l k t l bo k b o a l         后向概率 • Dynamic Programming • 后向概率计算公式 1: 2: 1 1 1 1 1 1 1 , 1 ( ) ( | ) ( | ) ( | ) ( | ) ()() t t T t M t T t t t t t l M t l t k l l k P o S k Po S lPo S lPS lSk l b o a                       后向概率 • Dynamic Programming • 后向概率计算公式 1: 2: 1 1 1 1 1 1 1 , 1 ( ) ( | ) ( | ) ( | ) ( | ) ()() t t T t M t T t t t t t l M t l t k l l k P o S k Po S lPo S lPS lSk l b o a                       1 1 , 1 1 if t = T () ( ) ( ) otherwise M t t l t k l l l l b o a       其他变量 • 位置 t 出现状态 k 的概率 • t 存在 k 到 l 转换的概率 ( ) ( | )ttk P S k o  S1 S2 k ST... ... O1 O2 Ot OT ... ... St+1 Ot+1 其他变量 • 位置 t 出现状态 k 的概率 • t 存在 k 到 l 转换的概率 ( ) ( | )ttk P S k o  1( , ) ( , | )t t tk l P S k S l o    S1 S2 k ST... ... O1 O2 Ot OT ... ... St+1 Ot+1 S1 S2 k ST... ... O1 O2 Ot OT ... ... l Ot+1 其他变量 • 计算 1: 1: 1: 1: 1: 1: 1: (,)(,,) ( | , ) ( , ) ( | ) ( , ) ()() t t t t T t T t t t t t T t t t tt P S k o P S k o o P o S k o P S k o P o S k P S k o kk              1 1 1 11 ( ) ( | ) (,)(,)()() () (,)()() tt t t t t MM kk k P S k o P S k o P S k o k k Po P S k o k k          ()t k 其他变量 • 计算 另外从定义可以得知: (,)t kl 1 1 , 1 11 1 ()()()( , ) ( , | ) ()() t l t k l t t t t M k l b o a kk l P S k S l o kk           1 1 1: 1 2: 2: 1 1 1 1 1: 1 1 , ( , , ) (,,,,) (| )(| )( | )(, ) ()()() tt t t t t t T t T t t t t t t t t l t k l t P S k S l o P S k S l o o o Po S lPo S lPS lS kPoS k l b o a k                      1 ()(,) M tt l k k l    参数估计 • 极大似然估计(MLE) • 两种情况 – S 已标注 训练语料:D = {(O1, S1), (O2, S2), ..., (On, Sn)} (Oi , Si ) 表示第 i 个标注序列 – S 未标注 训练语料:D = {O1, O2, ..., On)} * arg max ( | )PD   参数估计 • 极大似然估计(MLE) • 两种情况 – S 已标注 训练语料:D = {(O1, S1), (O2, S2), ..., (On, Sn)} (Oi , Si ) 表示第 i 个标注序列 – S 未标注 训练语料:D = {O1, O2, ..., On)} * arg max ( | )PD   参数估计 • 极大似然估计(MLE) • 两种情况 – S 已标注 训练语料:D = {(O1, S1), (O2, S2), ..., (On, Sn)} (Oi , Si ) 表示第 i 个标注序列 – S 未标注 训练语料:D = {O1, O2, ..., On} * arg max ( | )PD   参数估计(S已标注) • 训练语料:D = {(O1, S1), (O2, S2), ..., (On, Sn)} 每个标注序列是这样的: 这种情况下,训练的过程非常简单 以 ak,l 的计算为例 S1 S2 ST... ... O1 O2 OT ... ... St Ot 参数估计(S已标注) • 训练语料:D = {(O1, S1), (O2, S2), ..., (On, Sn)} 每个标注序列是这样的: 这种情况下,训练的过程非常简单 以 ak,l 的计算为例 S1 S2 ST... ... O1 O2 OT ... ... St Ot S1 S2 ST... ... O1 O2 OT ... ... k Oj k Oi ... ... S1 S2 ST... ... O1 O2 OT ... ... k Ot l Ot+1 , ()( | ) ()kl c k la P l k ck  (*) c 表示出现频次 参数估计(S已标注) • 另一种表示 • 另两个参数(同理) 1 1 11 , 11 (,) () nT tt it kl nT t it I S k S l a I S k          1 if x is true() 0 otherwiseIx    参数估计(S已标注) • 另一种表示 • 另两个参数(同理) 1 1 () n i k I S k n     1 1 11 , 11 (,) () nT tt it kl nT t it I S k S l a I S k          11 11 (,) () () nT tt it k nT t it I S k O u bu I S k        1 if x is true() 0 otherwiseIx    参数估计(S未标注) • Expectation Maximization (EM) 通常用于训练数据不完整的情况下做 MLE choose initial while i = 0, 1, 2, ... until convergence E -step: M-step: • 暂时考虑 O 只包含一个序列的情况 参数估计(S未标注) • Expectation Maximization (EM) 通常用于训练数据不完整的情况下做 MLE choose initial while i = 0, 1, 2, ... until convergence E -step: M-step: • 暂时考虑 O 只包含一个序列的情况 (,) (log (,)| ,)iiQ E P O S O o   0 1 arg max ( , )iiQ      参数估计(S未标注) • Expectation Maximization (EM) 通常用于训练数据不完整的情况下做 MLE choose initial while i = 0, 1, 2, ... until convergence E -step: M-step: • 暂时考虑 O 只包含一个序列的情况 (,) (log (,)| ,)iiQ E P O S O o   0 1 arg max ( , )iiQ      参数估计(S未标注) •E-step 11 11 21 21 (log ( , ) | , ) (log log log ( ) | , ) ( | , )(log log log ( )) t t t t t t i TT S s s s t i tt TT i S s s s t s t t E P O S O o E a b o O o P s o a b o                     参数估计(S未标注) 1 1 1 1 1 1 1 (|,)log (|,) ( )log log ( | , ) ( ) log ( ) M i S i k s s k M ki ks M k k P s o P s o I S k P s o I S k k                  参数估计(S未标注) 1 1 1 1 1 1 1 (|,)log (|,) ( )log log ( | , ) ( ) log ( ) M i S i k s s k M ki ks M k k P s o P s o I S k P s o I S k k                  1 1 , 1 2 1 1 11 (,) log () (,)log ( )log ( ) MTMM i k t k l k t k l TM t k t tk Q k k l a k b o                   参数估计(S未标注) •M-step constrains: 对各个参数求偏导即可。 1 arg max ( , )iiQ      , 1 1 1 1 1 ( ) 1 MMN k k l k k l u a b u         参数估计(S未标注) • 对于训练语料包含多个序列的情况 1 1 ()() () () T tt t k T t t k I O u bu k         1()k k 1 1 , 1 1 (,) () T t t kl T t t kl a k          参数估计(S未标注) • 对于训练语料包含多个序列的情况 1 1 ()() () () T tt t k T t t k I O u bu k         ()()()()(log(,)| ,) (log( , )| ,)d d d d ii d E POSOo E POS O o   1()k k 1 1 , 1 1 (,) () T t t kl T t t kl a k          观测序列概率 • 给定模型 ,计算一个观测序列 O 的概率 P(o) easy,之前已经计算过  S1 S2 ST... ... O1 O2 OT ... ... St Ot 观测序列概率 • 给定模型 ,计算一个观测序列 O 的概率 P(o) easy,之前已经计算过  1:()(,)t t tk P o S k  1: 11 ()(,)() MM TTT kk P o P o S k k     S1 S2 ST... ... O1 O2 OT ... ... St Ot 最优状态序列 • 给定观测序列 O 和 , 得到最优状态序列 S* * arg max ( | ) S SPSO  最优状态序列 • 给定观测序列 O 和 , 得到最优状态序列 S* * arg max ( | ) S SPSO S O  最优状态序列 • 简单方法 遍历所有的 S,算出一个最大的 时间复杂度 MT,丌可接受! • DP,在 t+1 位置重用 t 的结果 任一到达 t+1 状态的路径必然经过 t 的某一状态, 因此到 t+1 状态的最优路径必然经过 t 的某一状态 的最优路径 最优状态序列 • 简单方法 遍历所有的 S,算出一个最大的 时间复杂度 MT,丌可接受! • DP,在 t+1 位置重用 t 的结果 任一到达 t+1 状态的路径必然经过 t 的某一状态, 因此到 t+1 状态的最优路径必然经过 t 的某一状态 的最优路径 最优状态序列 • 递归公式 1: 1 1: 1: 1( ) max ( , , ) t t t t ts k P o s s k   最优状态序列 • 递归公式 1: 1 1: 1: 1( ) max ( , , ) t t t t ts k P o s s k   1: 1: 1 1: 1 1: 1 1: 1 1: 1 1: 1 1: 1 11 1 1 1 1: 1: 11 1 1 11 ( ) max ( , , ) max(max ( , , , , )) max(max( | )( | )(, , )) max( ( | ) ( | ) max t t t t t t t ts t t t t tl M s t t t t t t tl M s t t t tl M s k P o s s k P o o s s l s k Po s kPs kslPos sl P o s k P s k s l                               1 1: 1: 1 ,11 ( , , )) max( ( ) ( )) t t t t l k k tlM P o s s l l a b o        HMM 在 Query 纠错中的应用 Overview • 所谓的 Query 纠错就是对错误的 query 进行纠正,如“韩 度依舍”纠正为“韩都衣舍” • Query 纠错与 HMM 的对应关系 • 对 Query 进行纠错 == HMM 寻找最优状态序列 Overview • 所谓的 Query 纠错就是对错误的 query 进行纠正,如“韩 度依舍”纠正为“韩都衣舍” • Query 纠错与 HMM 的对应关系 • 对 Query 进行纠错 == HMM 寻找最优状态序列 HMM Query 纠错 Hidden state 任一汉字,如“韩都衣舍” 中的“都” Observation 原始 query 中的每个字,如“韩度依舍”的“度” 状态序列 任一可能的纠错结果,如“韩都衣舍” ”韩独一社” 观测序列 原始 query,如“韩度依舍” Language Model Error Model k ,kla ()kbu Overview • 所谓的 Query 纠错就是对错误的 query 进行纠正,如“韩 度依舍”纠正为“韩都衣舍” • Query 纠错与 HMM 的对应关系 • 对 Query 进行纠错 == HMM 寻找最优状态序列 HMM Query 纠错 Hidden state 任一汉字,如“韩都衣舍” 中的“都” Observation 原始 query 中的每个字,如“韩度依舍”的“度” 状态序列 任一可能的纠错结果,如“韩都衣舍” ”韩独一社” 观测序列 原始 query,如“韩度依舍” Language Model Error Model k ,kla ()kbu Overview C* 表示最优纠错结果 C 表示任一纠错候选 Ci 表示纠错候选中的第 i 个字 Q 表示原始 query l 表示 query 长度 11 * 1 11 (,)arg max ( | ) arg max arg max ( , )() arg max( ( ))i i i CCC ll C C C C i C ii PCQCPCQPCQPQ a b Q         Overview • Language Model 表示纠错候选 C 出现的可能性大小 • Error Model 表示 C 被错写成 Q 的可能性大小 11 1 1 () ii l CCC i P C a      Overview • Language Model 表示纠错候选 C 出现的可能性大小 • Error Model 表示 C 被错写成 Q 的可能性大小 11 1 1 () ii l CCC i P C a      1 ( | ) ( )i l Ci i P Q C b Q    Language Model • 训练语料 query log ( ) ( |)( | )( | )( | )(| ) P PPPPP 韩都衣舍 韩 都 韩 衣 都 舍 衣 舍 Error Model • 训练语料 用户的 query session 底腰小脚裤  低腰小脚裤 篇 片|0.41935483871 翩|0.209677419355 偏|0.12903225806 编|0.112903225806 骗|0.04838709677 …… Error Model • 训练语料 用户的 query session 底腰小脚裤  低腰小脚裤 篇 片|0.41935483871 翩|0.209677419355 偏|0.12903225806 编|0.112903225806 骗|0.04838709677 …… ( | ) (|)(|)(|)(|) P PPPP 韩度依舍 韩都衣舍 韩 韩 度 都 依 衣 舍 舍 得到纠错结果 韩 都 衣 舍 韩 度 依 舍 实际系统 • 使用三元语言模型 • 使用 rerank(针对 HMM 的 top-n 个结果) 这样可以引入更多特征,如上下文,基于分词的 语言模型 ( ) ( |)( | )( | ) ( | ) ( | ) P PPP PP  韩都衣舍 韩 都 韩 衣 韩都 舍 都衣 衣舍 实际系统 • 使用三元语言模型 • 使用 rerank(针对 HMM 的 top-n 结果) 这样可以引入更多特征,如上下文,基于分词的 语言模型 ( ) ( |)( | )( | ) ( | ) ( | ) P PPP PP  韩都衣舍 韩 都 韩 衣 韩都 舍 都衣 衣舍 纠错结果 • good case • bad case 芙维她洗手液 芙维他洗手液 谩步者音箱 漫步者音箱 奶粉 蒙牛 啊啦 奶粉 蒙牛 阿拉 处理 鱼干 处理 鱼竿 旅行化妆瓶 旅行化妆品 音响钢板网 音箱钢板网 夏装韩版女下装 夏装韩版女夏装 解决方法 • 引入同义词表 • 降低 error model 中字的错写概率 总结 • Markov Model 简介及其限制 • Hidden Markov Model 介绍 – Forward-backward Algorithm(前向后向算法) – 参数估计 – 计算观测序列概率 – 得到最优状态序列 • 具体应用 Query 纠错 谢 谢 !
还剩78页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 18 人已下载

下载pdf