知识图谱学习笔记（五）——实体识别（1）

实体识别（信息抽取）

1. 信息抽取概述

信息抽取定义：从自然语言文本中抽取指定类型的实体、关系、事件等事实信息，并形成结构化数据输出的文本处理技术。（Grishman，1997）
信息抽取的主要任务：实体识别与抽取、实体消歧、关系抽取、事件抽取

2. 信息抽取的基础：分词和词性标注

2.1中文分词

中文以字为基本书写单位，词语之间没有明显的区分标记
中文分词就是要由机器在中文文本中词与词之间加上标记。
和中文分词相比，英语切分问题相对容易。

2.2词性标注

Part-of-speech（POS） tagging（词性标注）：消除词性兼类歧义，即确定当前上下文每个词是名词、动词、形容词或其他词性的过程。
eg：名词和动词的兼类：爱好，把握，报道。

2.3中文分词的难点：

汉语中，字、词、词素和词组的界限模糊：吃饭、吃鱼、吃羊肉、吃羊肉串
歧义切分字段处理：
1.交集型歧义：对于汉字串ABC，AB，BC同时成词：研究生物，从小学起等
2.组合型歧义：对于汉字串AB，A、B、AB同时成词：门/把/手/弄/坏/了。门/把手/弄/坏/了。
3.真歧义：歧义字段在不同的语境中确实有多种切分形式：乒乓球拍/卖/完了。乒乓球/拍卖/完了。
未登录词（未登录词即没有被收录在分词词表中但必须切分出来的词）识别：
1.实体名词和专有名词：eg.中国人名，中国地名，翻译人名，翻译地名，机构名，商标字号。
2.专业术语和新词语：专业术语、缩略语、新词语。

2.4中文分词结果的评价：

封闭测试和开放测试
开方测试指的是测试样本不属于训练样本集合，否则称为封闭测试；
封闭测试相当于考试试题都出自于学习过的书本，实际上，通过机械记忆小样本的封闭测试取得100%的精度不存在问题。
专项测试和总体测试
专项测试是对特定领域或者特定类型的样本进行测试，反之成为总体测试。
总体测试能反映分词系统的综合效果，专项测试可以反映分词系统针对某个特定领域或者特定类型文本的效果。
评价指标：
真确率：测试结果中正确切分或标注的个数占系统所有输出结果的比例。P
召回率：测试结果中正确结果的个数占标准答案总数的比例。R
F值：正确率与召回率的综合值。
$F1 = \frac{2 \times P \times R}{P + R}$

在这里插入图片描述

2.5基于字典的分词方法

方法概述：按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。
典型方法：
1.正向最大匹配法
2.反向最大匹配法
3.最短路径法（最少分词法）
eg.
句子：中医治白癜风词典：中、医、治、中医、医治、白癜风
正向最大匹配法：中医/治/白癜风
反向最大匹配法：中/医治/白癜风
最短路径法：
独立自主/和平/等/互利/的/原则
独立自主/和/平等互利/的/原则
正向最大匹配（Forward Maximum Matching, FMM）
1.令i=0，当前指针 $P_i$ 指向输入字串的初始位置，执行下面的操作：
2.计算当前指针 $P_i$ 到字串末端的字数（即未被切分字串的长度）n，如果n=1，转第4步，结束算法。否则，令m=字典中最长单词的字数，如果 $n<m$ ，令m=n；
3.从当前 $P_i$ 起取m个汉字作为词 $w_i$ ，判断：
（1）如果 $w_i$ 确实是词典中的词，则在 $w_i$ 后添加一个切分标志，转（3）；
（2）如果 $w_i$ 不是词典中的词且 $w_i$ 的长度大于1，将 $w_i$ 从右端去掉一个字，转（1）步；否则（ $w_i$ 的长度等于1），则在 $w_i$ 后添加一个切分标志，将 $w_i$ 作为单字词添加到词典中，执行（3）；
（3）根据 $w_i$ 的长度修改指针 $P_i$ 的位置，如果 $P_i$ 指向字串末端，转第4步，否则， $i = i + 1$ ，返回（2）；
4.输出切分结果，结束分词程序
最短路径法
1.相邻节点 $V_{k-1}, V_k$ 之间建立有向边 $<V_{k-1}, V_k>$ ，边对应的词默认为 $C_k (k = 1, 2, ..., n)$ 。
2.如果 $w = C_i C_{i+1}... C_{j} (0<i<j<=n)$ 是一个词，则节点 $V_{i-1}，V_j$ 之间建立有向边 $<V_{i-1}, V_j>$ ，边对应的词为w。

在这里插入图片描述

3.重复步骤2，直到没有新路径（词序列）产生。
4.从产生的所有路径中，选择路径最短的（词数最少的）作为最终分词结果。

2.6基于统计的分词方法

基于统计的方法需要标注训练语料训练模型，可分为生成式统计分词和判别式统计分词

2.6.1 生成式方法

原理：首先建立学习样本的生成模型，再利用模型对预测结果进行间接推理。

马尔可夫模型
存在一类重要的随机过程（马尔可夫过程）：如果一个系统有N个状态 $S_1, S_2, ..., S_N$ ，随着时间的推移，该系统从某一个状态转移到另一状态。如果用 $q_t$ 表示系统在时间t的状态变量，那么t时刻的状态取值为 $S_j (1<=j<=N)$ 的概率取决于前t-1个时刻的状态，该状态的概率为：
$P(q_t = S_j | q_{t-1} = S_i, q_{t-2} = S_k, ...)$

假设1：一阶马尔可夫假设
如果在特定情况下，系统在时间t的状态只与其在时间t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链。
$P(q_t = S_j | q_{t-1} = S_i, q_{t-2} = S_k, ...) = P(q_t = S_j | q_{t-1} = S_i)$
假设2：不动性假设
如果只考虑上述公式独立于时间t的随机过程，状态与时间无关，那么：
$P(q_t = S_j | q_{t-1} = S_i) = a_{ij}, \quad\quad 1<=i,j<=N$
$a_{ij}>=0 \quad\quad\quad \sum_{j=1}^N a_{ij} = 1$
马尔可夫模型状态表示：马尔可夫链可以表示成状态图（转移弧上有概率的非确定的有限状态自动机）
- 零概率的转移弧省略
- 每个节点上所有发生弧的概率之和等于1
  
  在这里插入图片描述
马尔可夫模型状态序列的概率
状态序列 $S_1, ..., S_T$ 的概率：
$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})$
$不动性假设 = \pi_{S_1}\prod_{t=1}^{T-1} a_{S_t S_{t+1}}$ 其中， $\pi = P(q_1 = S_i)$ 为初始状态的概率。

在这里插入图片描述

隐马尔可夫模型
隐马尔可夫模型是关于时序的概率模型，是一个双重随机过程。其描述由一个隐藏的马尔可夫链随机生成不可观察的状态随机序列，再由各个状态生成一个观察，从而产生随机观察序列的过程，序列的每一个位置又可以看作是一个时刻。
wiki定义：隐马尔可夫模型是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。
示例：
房间里有N个盒子，每个盒子中有M种不同颜色的球。一实验员进入房间根据某一概率分布选择一个盒子，然后根据盒子中不同颜色球的概率分布随机取出一个球，并向房间外的人报告该球的颜色。
对房间外的人：可观察的过程是不同颜色球的序列，而盒子的序列是不可观察的。
每只盒子对应HMM中的一个状态；球的颜色对应于HMM中状态的输出。
[图片上传失败...(image-7990b9-1577174074124)]
图解

在这里插入图片描述
HMM的组成
- 状态集合：模型中的状态数为N（盒子的数量）
- 观察集合：从每一个状态可能输出的不同的符号数M（不同颜色球的数目）
- 状态转移概率矩阵： $A = a_{ij}$ （ $a_{ij}$ 为实验员从一个盒子（状态 $S_{i}$ ）转向另一个盒子（状态 $S_{j}$ ）取球的概率）。其中：
  $A = [a_{ij}]_{N \times N}$
  $a_{ij} = P(q_{t+1} = S_j | q_t = S_i) \quad\quad i = 1,2,...,N; j = 1,2,...,N$
  $a_{ij}>=0 \quad\quad \sum_{j=1}^N a_{ij} = 1$
- 观察概率矩阵B，处于状态 $S_i$ 的条件下生成观察 $v_k$ 的概率：
  $B = [b_j(k)]_{N \times N}$
  $b_j(k) = P(o_t = v_k | q_t = S_j) \quad\quad k = 1,2,...,M; j = 1,2,...,N$
  $b_j(k) >= 0 \quad\quad \sum_{k=1}^{M} b_j(k) = 1$
- 初始状态的概率分布 $\pi$ ：
  $\pi_i = P(q_1 = S_i), \quad\quad i = 1,2,...,N$
  $\pi_i >= 0, \quad\quad \sum_{i=1}^{N} \pi_i = 1$
假设
- 参数集合
  为了方便，一般将HMM记为： $\mu = (A, B, \pi)$ 或者 $\mu = (S, O, A, B, \pi)$
- 基本假设
  一阶马尔可夫性假设：隐马尔可夫链t的状态只和t-1状态有关
  [图片上传失败...(image-5c93de-1577174074124)]
  观察独立性假设：观察值和当前时刻状态有关：
  [图片上传失败...(image-f201c-1577174074124)]
生成观察序列
- 给定模型 $\mu = (A, B, \pi)$ ，生成观察序列 $O = O_1 O_2 ... O_T$
  （1）令t=1
  （2）按照初始状态分布 $\pi$ 产生状态 $q_1 = S_i$
  （3）按照状态 $S_t$ 的观察概率 $b_i(k)$ 分布生成 $o_t$
  （4）按照状态 $S_t$ 的状态转移概率 ${a_{ij}}$ 分布产生状态 $q_{t+1} = S_j$
  （5）令t = t+1；如果t<T，转步骤（3）；否则，终止
三个问题：
- 概率计算问题：在给定模型 $\mu = (A, B, \pi)$ 和观察序列 $O = O_1 O_2 ... O_T$ 的情况下，怎样快速计算概率 $P(O | \mu)$ ？
- 预测问题：在给定模型 $\mu = (A, B, \pi)$ 和观察序列 $O = O_1 O_2 ... O_T$ 的情况下，如何选择在一定意义下“最优”的状态序列 $Q = q_1 q_2 ... q_T$ ，使得该状态序列“最好地解释”观察序列 $O = O_1 O_2 ... O_T$ ？
- 学习问题：给定一个观察序列 $O = O_1 O_2 ... O_T$ ，如何根据最大似然估计求模型的参考值？即如何调节模型 $\mu = (A, B, \pi)$ 的参数，使得 $P(O | \mu)$ 最大？
1. 概率计算问题
对于给定的状态序列 $Q = q_1 q_2 ... q_T$ ，求 $P(O | \mu)$ ？
[图片上传失败...(image-cdb52-1577174074124)]
在公式里，我们需要遍历所有满足条件的Q，即遍历所有路径。
一阶马尔可夫假设:

在这里插入图片描述

观察独立假设：

在这里插入图片描述

在这里插入图片描述

可以看出，如果模型 $\mu = (A, B, \pi)$ 有N个不同的状态，时间长度为T，那么有 $N^T$ 个可能的状态序列，搜索路径成指数级组合爆炸。
可以通过动态规划，利用地推算法提高计算效率
概率计算问题——前向算法

在这里插入图片描述

在这里插入图片描述
- 前向算法计算过程：
  - 初始化：
    $\alpha_1(i) = \pi_i b_i(O_1), \quad 1<=i<=N$
  - 循环计算：
    $\alpha_{t+1}(j) = [\sum_{i=1}^{N} \alpha_t(i)\alpha_{ij}] \times b_j(O_{t+1}), \quad 1<=t<=T-1$
  - 结束，输出：
    $P(O | \mu) = \sum_{i=1}^{N}\alpha_T(i)$
- 算法的时间复杂性：
  
  在这里插入图片描述
  
  递推计算中，每一次计算可以直接饮用前一个时刻的计算结果，避免了重复计算。
示例
共有3个盒子，每个盒子里分别有红、白两种球，对应的状态转移概率矩阵、观察概率矩阵和初始状态概率分布如下所示：

在这里插入图片描述

（1）计算前向向量的初值：

在这里插入图片描述

（2）递推计算：

在这里插入图片描述

（3）终止：

在这里插入图片描述
概率计算问题——后向算法

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
后向算法——算法描述
- 初始化：
  
  在这里插入图片描述
- 循环计算：
  
  在这里插入图片描述
- 结束：
  
  在这里插入图片描述
- 时间复杂度：
  
  在这里插入图片描述
2. 隐马尔可夫模型——预测问题
- 预测问题：在给定模型 $\mu = (A, B, \pi)$ 和观察序列 $O = O_1 O_2 ... O_T$ 的情况下，如何选择在一定意义下“最优”的状态序列 $Q = q_1 q_2 ... q_T$ ，使得该状态序列“最好地解释”观察序列 $O = O_1 O_2 ... O_T$ ？
  [图片上传失败...(image-19a1a3-1577174074124)]
- 关于“最优”，有两种解释。
  - 一种解释：状态序列中的每个状态都单独地具有概率，针对每个时刻t都找到具有最大概率的状态，顺序连接每个时刻具有最大概率的状态，进而得到最优状态序列。（该解释可能存在的问题是：每一个状态单独最优不一定使整体的状态序列最优，额能两个最优的状态之间的转移概率为0。）
  - 另一种解释：不单独考虑每个时刻的状态，而是考虑到达t时刻的状态序列的概率，从不同的状态序列中找到具有最大概率的状态序列，呢绒得到最优状态序列。
针对第二种解释，可使用Viterbi 算法：动态搜索最优状态序列

在这里插入图片描述
Viterbi算法

在这里插入图片描述

在这里插入图片描述
示例：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
3. 隐马尔科夫模型——学习问题
- 学习问题：给定一个观察序列 $O = O_1 O_2 ... O_T$ ，如何根据最大似然估计求模型的参考值？即如何调节模型 $\mu = (A, B, \pi)$ 的参数，使得 $P(O | \mu)$ 最大？
有监督学习的方法：假设训练数据是包括观测序列O和对应的状态序列Q，则可以利用最大似然估计来计算模型的参数。

在这里插入图片描述

在这里插入图片描述
无监督学习方法
- 假设训练数据中只包括观测序列O，没有对应的状态序列Q，此时只能利用期望值最大化算法（Expectation-Maximizatiion，EM）
- 基本思想：初始化时随机地给模型的参数赋值（遵循限制规则，如：从某一状态处罚的转移概率总和为1，得到模型 $\mu_0$ ），然后可以从 $\mu_0$ 得到从某一状态转移到另一状态的期望次数，然后以期望次数代替公式中的次数，得到模型参数的新估计，由此得到新的模型 $\mu_1$ ，从 $\mu_1$ 又可得到模型中隐变量的期望值，由此重新估计模型参数。循环这一过程，收敛于最大似然估计值。
  
  在这里插入图片描述
无监督学习方法
- 定义：给定模型 $\mu$ 和观察序列 $O = O_1O_2...O_T$ ，那么，在时间t位于状态 $S_i$ ,时间t+1位于状态 $S_j$ 的概率：
  
  在这里插入图片描述
  
  在这里插入图片描述
  
  在这里插入图片描述
Baum-Welch算法（前向后向算法）描述：
- 初始化：随机地给 $\pi_i, a_{ij}, b_j(k)$ 赋值
  
  在这里插入图片描述
  
  由此得到模型 $\mu_0$ ，令i = 0.
- 执行EM算法：
  
  在这里插入图片描述

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