《2017-知识图谱导论-实体识别2资料》由会员分享，可在线阅读，更多相关《2017-知识图谱导论-实体识别2资料（141页珍藏版）》请在金锄头文库上搜索。
1、实 体 识 别 2017-2018学年-秋季学期: 知识图谱导论 赵 军 （jzhao ） 中国科学院自动化研究所 模式识别国家重点实验室 基于统计的分词方法：判别式方法 原理： 在有限样本条件下建立对于预测结果的判别函数，直接 对预测结果进行判别 由字构词的分词理念，将分词问题转化为判别式分类问 题 典型算法： Maxent SVM CRF Perceptron 基于统计的分词方法 判别式分词 流程： 把分词问题转化为确定句中每个字在词中位置问题 每个字在词中可能的位置可以分为以下三种 词首B（日本占领 了 东三省） 词中M（游泳 比赛 菲尔普斯 独占鳌头） 词尾E（中国队 抢占了 风头）
2、独字S （男生占全班 人数 的 百分之八十） 分词结果展示： 分词结果：毛/B 新/M 年/E 2/B 0/M 0/M 0/M 年/E 毕/B 业/E 于/S 东/B 北/M 大/M 学/E 最大熵模型：熵 什么是熵？ 什么是熵？ 没有什么问题在科学史的进程中曾被更为频 繁地讨论过 （比利时物理化学家，诺贝尔奖，普里高津） 熵定律是自然界一切定律中的最高定律 （里夫金 1 , , 2 , 1 , , KlKkixys Kkixyyt ixyyf il iik iik 特征的分段函数特征的分段函数 Kkixyyfxyf n i iikk , 2 , 1 , 1 1 条件随机场的简化形式 用wk表
3、示特征fk（x，y）的权值，即 于是，条件随机场可以表示为: 21 1 , 2 , 1 ; , , 2 , 1 , KllKk Kk w l k k y K k kk K k kk xyfwxZ xyfw xZ xyP 1 1 ,exp ,exp 1 i,l ill i,k iikk ,x,iys,x,i,yyt xZ xyP 1 exp 1 权重的分段函数权重的分段函数 条件随机场的简化形式 若w表示权值向量： 以F(y,x)表示全局特征向量，即 条件随机场写成内积： T K wwww, 21 T K xyfxyfxyfxyF, 11 y w w w xyFwxZ xZ xyFw xyP ,
4、exp ,exp y K k kk K k kk xyfwxZ xyfw xZ xyP 1 1 ,exp ,exp 1 把把 上上 面面 公公 式式 中中 的的 求求 和和 转转 变变 为为 内内 积积 形形 式式 条件随机场的矩阵形式 以上是CRF的参数化及其简化形式，为了计算方便，可以表示 为矩阵形式 首先引进特殊的起点和终点状态标记Y0=start, Yn+1=stop， 这时Pw(y|x)可以通过矩阵形式表示 需要对观察序列x的每一个位置i=1,2,n+1，定义一个m阶矩 阵(m是标记Yi取值的个数) 直观上，直观上，Mi表示从位置表示从位置i-1到位置到位置i时，状态从时，状态从yi
5、-1转移到转移到yi的概率的概率 该概率由一组（该概率由一组（K）转移特征、状态特征和对应的权重决定。）转移特征、状态特征和对应的权重决定。 条件随机场的矩阵形式 例子： 假设假设y可以取可以取N和和V两种标签，如公式所示，两种标签，如公式所示，y1取取N，y2取取N的概率是由的概率是由K个个 特征函数决定的，其中有特征函数决定的，其中有K1个转移特征，个转移特征，K2个状态特征。个状态特征。 2 = exp( =1 (1,x,)2( ) 2( )2( ) i=2时 条件随机场的矩阵形式 定义为矩阵形式之后，条件概率Pw(y|x)： Zw(x)为规范化因子，是n+1个矩阵的乘积的(start,
6、 stop)元素 。具体地，规范化因子Zw(x)是以start为起点stop为终点通过 状态的所有路径y1y2y3yn的非规范化概率之和 1 1 1, 1n i iii w w xyyM xZ xyP stopstartnw xMxMxMxZ ,121 乘积的形式，方便递推计算乘积的形式，方便递推计算 条件随机场的矩阵形式：例子 给定一个下图所示的线性链条件随机场，观测序列x，状态序 列y，i=1,2,3, n=3，标记yi1,2，假设y0=start=1， y4=stop=1，各个位置的随机矩阵M1(x)， M2(x)， M3(x)， M4(x)分别是： 试求状态序列y以start为起点st
7、op为终点所有路径的非规范概 率及规范化因子 条件随机场的矩阵形式：例子 首先计算图中从start到stop对应于y=（1,1,1），y=（1,1,2 ）,y=(2,2,2)各路径的非规范化概率分别是： 通过计算矩阵乘积M1(x) M2(x) M3(x)M4(x)可知，其第一行第 一列的元素如下，恰好等于从start到stop的所有路径的非规 范化概率之和 条件随机场：概率计算问题 问题描述：给定条件随机场P(Y|X)，输入序列x和输出序列y 计算条件概率： 为了提高计算效率，像HMM那样，引进前向-后向向量，进 行递推计算（前向后向算法） xyYyYP XYP iiii i , 11 标记序
8、列在位置标记序列在位置i为为yi的概率的概率 标记序列在位置标记序列在位置i-1为为yi-1且在且在 位置位置i为为yi概率概率 CRF：概率计算问题 前向-后向算法： 对每个位置i=0,1,n+1 , 定义前向向量 递推公式： 表示：在位置i的标记是yi，且到位置i的前部分标记序列(y0y1y2yi-1) 的非规范化概率 又可表示为： 因为yi可取的值m个，所以是m维列向量 x i 否则 , 0 , 1 0 starty xy 1, 2 , 1 , 111 nixyyMxyxy iiii T ii T i xMxx i T i T i1 x i 1 1 1, 1n i iii w w xyy
9、M xZ xyP 一个值一个值 一个一个m维的维的 列向量列向量 条件随机场的概率计算问题 前向-后向算法： 同样，对每个指标i=0,1,n+1 , 定义后向向量 表示：在位置i的标记是yi，且从位置i+1到n+1的后部分标记序列(yi+1 yi+2yn+1)的非规范化概率 又可表示为： x i 否则 , 0 , 1 1 11 stopy xy n nn xyxyyMxy iiiiiii1111 , xxMx iii11 1 1 1 TT n Z xxx 条件随机场：概率计算问题 条件随机场：解码问题 问题描述：给定条件随机场P(Y|X)和输入序列(观察序列)x，求 条件概率最大的输出序列(标
10、记序列)y* Viterbi算法： xZ xyFw xyP w w ,exp xyFw xyFw xZ xyFw xyPy y y w y w y ,maxarg ,expmaxarg ,exp maxarg maxarg * 条件随机场：解码问题 Viterbi 搜索算法 3T21 Time, t S1 S2 S3 SN States 条件随机场：解码问题 根据上述公式，条件随机场的预测问题成为求非规范化概率最 大的最优路径问题 其中，路径表示标记序列，其中 T K wwww, 21 T K xyfxyfxyfxyF, 11 Kkixyyfxyf n i iikk , 2 , 1 , 1 1
11、 01函数函数 条件随机场的解码问题 注意，为了提高计算效率，只需计算非规范化概率，而不必计 算概率，于是，为了求解最优路径，上述式子可以写成如下形 式 其中 每个位置的各种特征，每一个是一个每个位置的各种特征，每一个是一个01函数函数 条件随机场：解码算法 Viterbi算法： 初始化：首先求出位置1的各个标记j=1,2m的非规范化概 率： 递归计算： ,m, jj,xstart,yyFwj ii 21 10 ,m, ll,xj,yyFwjl ,m, ll,xj,yyFwjl iiii mf i iiii mf i 21maxarg 21max 11 1 11 1 条件随机场：解码算法 Vi
12、terbi算法： 终止：直到i=n时终止，这时求得非规范化概率的最大值为 回溯路径： jxyFw n mjy 1 max,max jy n mj n 1 * maxarg 121 11 ,nn, iyy * ii * i T n yyyy * 2 * 1 * , 条件随机场：解码算法的例子 输入观测为：X=(X1,X2,X3)，输出标记为Y=(Y1,Y2,Y3)，Y1, Y2, Y3取值于1,2 假设特征和对应权值，只注明特征取值为1，为0省略 对给定的观测序列x，求对应的最优输出序列 条件随机场：解码算法的例子 解： 利用Viterbi算法求最优路径问题 初始化 条件随机场：解码算法的例子
13、解： 递推 条件随机场：解码算法的例子 解： 递推 条件随机场：解码算法的例子 解： 终止 返回 最优标记序列 条件随机场：学习问题 拟牛顿法： 学习的优化目标函数： 梯度函数： 参考参考统计机器学习统计机器学习附录附录 有监督的学习有监督的学习 HMM vs ME vs CRF HMM是一种生成式模型，利用转移矩阵和生成矩阵建模相 邻状态的转移概率和状态到观察的生成概率。无法利用复 杂特征（只有两个矩阵建模） ME是一种判别式模型，可以使用任意的复杂特征（特征函 数），但是ME只能建模观察序列和某一状态的关系，状态 之间的关系无法得到充分利用。 CRF是一种判别式模型，可以使用任意的复杂特征（特征函 数）（虽然每个位置有一个矩阵，但是矩阵的元素是由特 征函数和权重计算得到，我们可以任意地定义特征函数从 而考虑各种特征），可以建模观察序列和多个状态的关系 ，考虑了状态之间的关系。 CRF工具 参考项目：python-crfsuite 安装： pip install python-crfsuite CRF工具 参考任务(Chunking)： https:/www.clips.uantwerpen.be/conll2000/chunking/ 示例：He reckons the current account deficit
