[自然语言处理-入门]四、序列标注基础（1）

学习路线参考：

本节学习使用工具&阅读文章：

https://juejin.cn/post/7099256855255318541#t1

http://fancyerii.github.io/books/sequential_labeling/#%E8%AF%8D%E6%80%A7%E6%A0%87%E6%B3%A8part-of-speechpos-tagging

https://zhuanlan.zhihu.com/p/29938926

https://spaces.ac.cn/archives/5542

https://zhuanlan.zhihu.com/p/29989121

词性标注

词性标注是一个典型的序列标注问题，输入是一个词序列，输出是对应的词性序列。

词性标注难题：
- 歧义，消除歧义需要依赖与上下文的信息
- 新词，很多词在训练数据中从来没有出现过，那要“猜测”新词的词性

HMM简介

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列。序列的每一个位置又可以看作是一个时刻。
- $Q=\{q_1,q_2,……,q_N\}$ ：所有可能的隐藏状态的集合，共有N个。
- $V=\{v_1,v_2,……,v_M\}$ ：所有可能的观测状态的集合，共有M个。
对于一个长度为 $T$ 的序列，
- $I=\{i_1,i_2,……,i_T\}$ ：对应的状态序列，任意 $i_t∈Q$ 。
- $O=\{o_1,o_2,……,o_T\}$ ：对应的观察序列，任意 $o_t∈V$ 。
两个重要假设：
- 齐次马尔科夫链假设：即任意时刻的隐藏状态只依赖于它前一个隐藏状态。（实际的时候，某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者是前三个）
  
  如果在时刻 $t$ 的隐藏状态是 $i_t=q_i$ ，在时刻 $t+1$ 的隐藏状态是 $i_{i+1}=q_j$ ，则从时刻 $t$ 到时刻 $t+1$ 的HMM状态转移概率 $a_{ij}$ 可以表示为： $a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$ 。
  
  这样 $a_{ij}$ 可以组成马尔科夫链的状态转移矩阵 $A=[a_{ij}]_{N*N}$
- 观测独立性假设：即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态。
  
  如果在时刻 $t$ 的隐藏状态是 $i_t=q_j$ ，而对应的观察状态为 $o_t=v_k$ ，则该时刻观察状态 $v_k$ 在隐藏状态 $q_j$ 下生成的概率 $b_j(k)$ 满足： $b_j(k)=P(o_t=v_k|i_t=q_j)$
  
  这样 $b_j(k)$ 可以组成观测状态生成的概率矩阵 $B=[b_j(k)]_{N*M}$
- 除此之外，还需要一组在 $t=1$ 时刻的隐藏状态概率分布 $\Pi$ ： $\Pi=[\pi(i)]_N$ ，其中 $\pi(i)=P(i_1=q_i)$
一个HMM模型由隐藏状态初始概率分布 $\Pi$ ，状态转移矩阵 $A$ 和观测状态概率矩阵 $B$ 决定。 $\Pi$ 和 $A$ 决定状态序列， $B$ 决定观测序列。

HMM模型可以由一个三元组 $\lambda = [A,B,\Pi]$ 表示。

HMM的评估问题

给定模型 $\lambda=(A,B,\Pi)$ 和观测序列 $O$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$ 。
1. 直接计算法
  
  首先，任意一个隐藏序列 $I$ 出现的概率是 $P(I|\lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}……a_{i_{T-1}i_{t}}$
  
  对于固定的状态序列 $I^*$ ，我们要求的观察序列 $O^*={o_1,o_2,……,o_T}$ 出现的概率是： $P(O|I^*,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)……b_{i_T}(o_T)$
  
  由条件概率公式： $P(I^*|\lambda)={P(I^*\lambda)\over P(\lambda)}$ ， $P(O|I^*,\lambda)={P(OI^*\lambda)\over P(I^*\lambda)}$
  
  则 $P(O,I^*|\lambda)=P(I^*|\lambda)P(O|I^*,\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)a_{i_2i_3}……b_{i_{T-1}}(o_{T-1})a_{i_{T-1}i_{t}}b_{i_T}(o_T)$
  
  则待求概率 $P(O|\lambda)=\sum_IP(O,I^*|\lambda)$ ，即计算 $I^*$ 所有可能的排列组合条件下对应的边缘概率分布再求和。该算法的时间复杂度很高，耗时很大。
2. 前向算法
  
  定义前向概率：时刻 $t$ 时隐藏状态为 $q_i$ 、观测状态的序列为 $o_1,o_2,……,o_t$ 的概率。记为 $\alpha_t(i)=P(o_1,o_2,……,o_t,i_t=q_i|\lambda)$ 。
  
  利用动态规划的思想，假设已经找到了 $t$ 时刻各个隐藏状态的前向概率，现在需要递推出 $t+1$ 时各个隐藏状态的前向概率。该递推式为： $\alpha_{t+1}(i)=[\sum^N_{j=1}\alpha_t(j)a_{ji}]b_i(o_{t+1})$
  
  由于 $\alpha_T(i)$ 表示观测序列 $O$ 在 $T$ 时刻隐藏状态为 $q_i$ 的概率，则只要将所有隐藏状态对应的概率相加，就得到了在 $T$ 时刻观测序列必定为 $O$ 的概率。
  
  因此 $P(O|\lambda)=\sum^N_{i=1}\alpha_T(i)$
3. 后向算法
  
  与前向算法类似，但使用了后向概率。

HMM的解码问题

给定模型 $\lambda=(A,B,\Pi)$ 和观测序列 $O$ ，求给定观测序列 $O$ 条件下，最可能出现的对应的状态序列 $I^*$ ，即 $P(I^*|O)$ 要最大化。
1. 解码问题的近似解法
  
  求出观测序列 $O$ 在每个时刻 $t$ 最可能的隐藏状态 $i^*_t$ ，然后得到一个近似隐藏状态序列。给定 $\lambda$ 和 $O$ ，计算在 $t$ 时刻处于隐藏状态 $q_i$ 的概率可以用前向后向算法计算。
  
  近似算法很简单，但是却不能保证预测的状态序列的整体是最可能的状态序列，因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。
2. 维特比算法
  - 局部状态 $\delta_t(i)$ ：在时刻 $t$ 隐藏状态为 $i$ 所有可能的状态转移路径中的概率最大值。
    
    $\delta_t(i)=max_{i_1,i_2,……,i_{t-1}} P(i_t=i,i_1,i_2,……,i_{t-1},o_t,o_{t-1},……,o_1|\lambda), i = 1, 2, ……, N$
    
    则 $\delta_t(i)$ 的递推表达式为： $\delta_t(i)=max_{1≤j≤N}[\delta_t(j)a_{ji}]b_i(o_{t+1})$
  - 局部状态 $\psi_t(i)$ ：在时刻 $t$ 隐藏状态为 $i$ 的所有可能的状态转移路径中概率最大的转移路径中第 $t-1$ 个节点的隐藏状态为 $\psi_t(i)$ 。
    
    则 $\delta_t(i)$ 的递推表达式为： $\psi_t(i)=arg max_{1≤j≤N}[\delta_{t-1}(j)a_{ji}]$ 。可以看得出这是一个用于回溯的状态。
  维特比算法流程：
  - 输入： $\lambda，O$
  - 输出：最有可能的观测序列 $I^*=\{i_1^*,i_2^*,……,i^*_T\}$
  1. 初始化局部状态：
  2. 进行动态规划递推 $t=2,3,……,T$ 时刻的局部状态
  3. 计算时刻 $T$ 最大的 $\delta_T(i)$ 即为最可能隐藏状态序列出现的概率， $\psi_t(i)$ 即为时刻 $T$ 最可能的隐藏状态
  4. 利用局部状态 $\psi(i)$ 开始回溯。对于 $t=T-1,T-2,……,,1$ ，有 $i^*_t=\psi_{t+1}(i^*_{t+1})$
  5. 最终得到最有可能的隐藏状态序列 $I^*$

HMM的缺点
- 由于观测独立性假设（任意时刻的观测只依赖于该时刻的马尔可夫链的状态），很难融入更多的特征（如上下文）以表示复杂的关系。
- HMM是生成式模型，优化目标和实际预测不匹配。（我们训练学习的是联合概率分布，但是我们预测是却只使用条件概率分布。）
- label bias问题：算法倾向于选择分支较少的状态，这是由于齐次马尔科夫假设使得在计算转移概率时做了局部归一化。

CRF简介

给定一组输入随机变量条件下，另一组输出随机变量条件的概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。
- 马尔科夫随机场：假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关，和与其不相邻的位置的赋值无关。
CRF假设马尔科夫随机场中只有 $X、Y$ 两种变量， $X$ 一般是给定的，而 $Y$ 一般是在给定 $X$ 的条件下的输出。在词性标注的例子中， $X$ 是词， $Y$ 是词性。

数学语言描述：设 $X=\{x_1,x_2,……,x_n\}$ 与 $Y=\{y_1,y_2,……,y_n\}$ 是随机变量， $P(Y|X)==P(y_1,y_2,……,y_n|x_1,x_2,……,x_n)$ 是给定 $X$ 时 $Y$ 的条件概率分布，若随机变量 $Y$ 构成的是一个马尔科夫随机场，则称条件概率分布 $P(Y|X)$ 是条件随机场。

为了得到这个概率的估计，CRF做了两个假设：
- 假设一：该分布是指数族分布。这表明存在函数 $f(y_1,y_2,……,y_n;X)$ 使得 $P(y_1,y_2,……,y_n|X)={1\over Z(x)}exp(f(y_1,y_2,……,y_n;X))$ 。其中 $Z(x)$ 是归一化因子，因为这个是条件分布，所以归一化因子跟 $X$ 有关。这个 $f$ 函数可以视为一个打分函数，打分函数取指数并归一化后就得到概率分布。
- 假设二：输出之间的关联仅发生在相邻位置，并且关联是指数加性的。这个假设意味着 $f$ 可以进一步简化为 $f(y_1,…,y_n;X)=h(y_1;X)+g(y_1,y_2;X)+h(y_2;X)+g(y_2,y_3;X)+h(y_3;X)+⋯+g(y_{n−1},y_n;X)+h(y_n;X)$
  
  其中， $h$ 与 $g$ 是分别定义在 $y$ 当前节点的节点特征函数和 $y$ 上下文的局部特征函数，无论是节点特征函数还是局部特征函数，它们的取值只能是0或者1。即满足特征条件或者不满足特征条件。同时，我们可以为每个特征函数赋予一个权值，用以表达我们对这个特征函数的信任度。
  
  也就是说，现在我们只需要对每一个标签和每一个相邻标签对分别打分，然后将所有打分结果求和得到总分。

线性链CRF

考虑函数 $g$ 跟 $X$ 无关，那么 $f(y_1,…,y_n;X)=h(y_1;X)+g(y_1,y_2)+h(y_2;X)+g(y_2,y_3)+h(y_3;X)+⋯+g(y_{n−1},y_n)+h(y_n;X)$

概率分布变为 $P(y_1,y_2,……,y_n|X)={1\over Z(X)}exp(h(y_1;X)+∑_{t=1}^{n−1}[g(y_t,y_{t+1})+h(y_{t+1};X)])$

其中， $Z(X)$ 为规范化因子： $Z(X)=\sum_yexp(h(y_1;X)+∑_{t=1}^{n−1}[g(y_t,y_{t+1})+h(y_{t+1};X)])$

为了训练CRF模型，我们用最大似然方法，也就是用 $-logP(y_1,y_2,……,y_n|X)$ 作为损失函数。

由于这是一个从 $k^n$ 条路径中选最优的问题，而因为马尔可夫假设的存在，在模型训练完成之后，它可以转化为一个动态规划问题，用维特比算法解决。

最后编辑于：2023.03.09 19:54:09

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,525评论 6赞 507
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,203评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,862评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,728评论 1赞 294
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,743评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,590评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,330评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,244评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,693评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,885评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,001评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,723评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,343评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,919评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,042评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,191评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,955评论 2赞 355

[自然语言处理-入门]四、序列标注基础（1）

推荐阅读更多精彩内容