周国栋命名实体间语义关系抽取研究课件.ppt

1、命名实体间语义关系抽取研究命名实体间语义关系抽取研究1目录1.引言和相关工作2.研究内容和方法2.1 指导性关系抽取 2.2 弱指导关系抽取 2.3蛋白质相互作用关系抽取3.工作展望21.引言和相关工作 关系抽取的定义 在许多自然语言理解系统中，不但要识别文本中的实体，而且要根据上下文确定和抽取这些实体之间的各种语义关系，即实体间语义关系抽取（简称语义关系抽取或关系抽取）。关系抽取的例子 句子“Microsoft Corp.is based in Redmond,WA”表达了“Microsoft Corp”(ORG)和“Redmond”(GPE)之间的“GPE-AFF.Based”关系。关系抽

2、取的意义 实体间语义关系的抽取不仅是信息抽取中的重要环节，而且在蛋白质相互作用(PPI)抽取、问答系统、知识获取和自然语言接口等应用中也非常重要。31.引言和相关工作 关系抽取的研究方法 基于规则的方法 基于机器学习的方法 指导性方法 弱指导方法 无指导方法4 指导性关系抽取 实现方法：将关系实例转换成高维空间中的特征向量或直接用离散结构来表示，在标注语料库上使用学习器来生成分类模型，然后再抽取语义关系。基于特征向量方法：最大熵模型(Kambhatla 2004)和支持向量机(Zhao等2005；Zhou等2005;Jiang等2007)等；基于核函数的方法：浅层树核（Zelenko 等 20

3、03)、依存树核（Culotta 等 2004)、最短依存树核（Bunescu等 2005)、卷积树核（Zhang等 2006；Zhou 等 2007）。1.引言和相关工作5 指导性关系抽取 研究重点 基于特征向量：如何获取各种有效的词法、语法、语义等特征，并把它们有效地集成起来，从而产生描述实体语义关系的各种局部特征和简单的全局特征。基于核函数：如何有效（准确和简洁）捕获反映语义关系本质的结构化信息及如何有效计算结构化信息之间的相似度。1.引言和相关工作6 指导性关系抽取 存在问题 基于特征向量的方法：1）由于难于进一步挖掘出有效的平面特征，因此基于特征向量的方法很难取得性能上的提高；2）不

4、过，如果要构造一个实用的关系抽取系统，则基于特征向量的方法是一个首选。基于核函数的方法：1）目前所使用的结构化信息往往包含了不必要的噪音信息，同时也丢失了一部分关键信息；2）目前普遍采用卷积树核函数（CTK）来计算两个树形对象之间的相似度，不考虑上下文相关性。1.引言和相关工作7 弱指导关系抽取 与指导性学习方法不同，弱指导学习方法以小规模的高质量标注语料库为基础，有效利用大规模的未标注语料，期望取得与指导性学习方法相当的性能。代表性工作 自举算法(Brin 1998;Agichtein等2000)协同训练(Zhang 2004)标注传播算法(Chen等2006)等。存在的问题 如何合理选取初

5、始种子集，使之既有典型性，又有多样性，因而能代表语料库中关系实例的自然簇结构；如何选择适合于像关系抽取这样复杂任务的弱指导算法。1.引言和相关工作8 指导性关系抽取探索适合于语义关系的结构化信息：利用语言学方面的理论，探索自动获取结构化句法信息的自动抽取方案，以确保抽取出的结构化信息既涵盖关键的结构化句法信息，又能减少不必要的噪音；探索新颖的结构化信息相似度计算方法：考虑句法树中的上下文相关信息，设计新颖的卷积树核函数，以充分体现关系实例之间的相似度；研究路线9 弱指导关系抽取探索弱指导关系抽取的种子选取策略：针对不同的弱指导学习方法（如自举算法和标注传播算法），采用相应的初始种子选取策略（如

6、分层抽样和自举加权支持矢量）来提高种子集的代表性，同时降低弱指导学习算法的开销。将语义关系抽取的研究成果应用于生物医学文本挖掘 将新闻领域（ACE）上的关系抽取研究成果应用到蛋白质相互作用关系（PPI）抽取中，提高PPI的抽取性能。研究路线10目录1.引言和相关工作2.研究内容和方法2.1 指导性关系抽取 2.2 弱指导关系抽取 2.3蛋白质相互作用关系抽取3.工作展望112.1 指导性关系抽取 基于特征向量的关系抽取 基于树核函数的关系抽取 结构化信息和实体语义特征的复合 平面特征和结构化特征的复合12 特征选取：从自由文本及其语法结构中抽取出各种表面特征以及结构化特征的平面形式。实体词汇及

7、其上下文特征实体类型及其组合特征 实体参照方式 交叠特征 基本短语块特征 依存树特征 句法树特征 2.1 指导性关系抽取:特征向量方法13数据分析 词汇信息、实体类型信息等特征在ACE 2004上的语义关系抽取中比较有效；实体参照方式、交叠信息等特征有一定作用；其它结构化特征仅能略微提高关系抽取的性能。实验结论 基于特征向量的方法可以使用一些成本较低的特征达到一定的性能；结构化信息在基于特征的方法中不能很好被利用，并非是它们本身没有作用。因此结构化信息的探索和利用成为关系抽取的研究重点。特征P(%)R(%)F1词汇信息52.036.242.6+实体类型65.251.857.7+参照方式65.0

8、53.058.4+交叠信息66.054.359.6+短语块65.854.959.8+依存树67.055.260.5+句法树67.355.260.7ACE RDC 2004关系大类2.1 指导性关系抽取:特征向量方法14 卷积核函数：用两个结构之间的公共子结构的数目来衡量它们之间的相似度。句法树核（Collins和Duffy 2001）字符串核（Lodhi等2002）图形核（Suzuki等2003）卷积树核函数优点：能有效捕获离散数据对象中的结构化信息，在自然语言处理领域中取得了广泛的应用，如语义角色标注（Moschitti 2004）、关系抽取和指代消解等。缺点：计算效率较低。2.1 指导性关

9、系抽取:树核函数方法15 卷积数核函数计算两棵树T1和T2之间的相似度为两者之间的公共子树的目。其中N1和N2分别为T1和T2的结点集合，用来计算以n1和n2为根结点的两棵子树之间的相似度，它可以通过下列递归的方法得出：1)如果和的产生式（采用上下文无关文法）不同，则 ；否则转2；2)如果和是词性（POS）标记，则 ；否则转3；3)递归计算：其中 (0 1)则是衰减因子，用来防止子树的相似度过度依赖于子树的大小。2211,2121),(),(NnNnCTKnnTTK)(#121211),(),(1(),(nchkknchknchnn12(,)0n n12(,)n n12(,)1n n 2.1

10、指导性关系抽取:树核函数方法16 标准卷积树核函数（CTK）在计算两棵子树的相似度时，只考虑子树本身，不考虑子树的上下文信息。上下文相关卷积树核函数（CS-CTK）在计算子树相似度量，同时考虑子树的祖先信息，如子树根结点的父结点、祖父结点信息，并对不同祖先的子树相似度加权平均。2211),(),(21121NnNnimiiCSCTKnnwTTK2.1 指导性关系抽取:树核函数方法172.1 指导性关系抽取:树核函数方法18 常用结构化表示 最小完全树MCT(Minimal Complete Tree)包含两个实体的最小完整树；最短路径包含树 SPT(Shortest Path-enclosed

11、 Tree)由句法树中连接两个实体的最短路径所包含的部分(Zhang等2006)；上下文相关的最短路径包含树 CS-SPT(Context-Sensitive Shortest Path-enclosed Tree)在SPT的基础上扩充相关的谓词链接路径(Zhou等2007)2.1 指导性关系抽取:树核函数方法19 常用结构化表示：存在问题 包含不必要的噪音 MCT、SPT和CS-SPT仍然包含对关系抽取来说不必要的噪音。例如，句子“bought one of towns two meat-packing plants”中的划线部分；丢失部分关键信息 CS-SPT仅包含了与谓词连接有关的上下文

12、相关信息，还有一部分与关系抽取相关的上下文信息没有恢复出来。例如句子“bought one of towns two meat-packing plants”中的划线部分。2.1 指导性关系抽取:树核函数方法20 成分依存与动态关系树 研究动机 依存关系（Culotta和Sorensen,2004;Bunescu和Mooney,2005）为关系实例提供了一个高效的表示方法，但是由于这两种方法需要依存树之间的精确匹配，因此尽管获得了较好的识别准确率，召回率还相当低。成分依存 上下文无关文法（CFG）的每一个内部推导规则均可表示为P LnL1 H R1Rm 其中P 是父结点，H 是中心子结点，Ln

13、L1 和 R1Rm 分别是中心结点的左右修饰语，而 n 和 m 则是它们的长度。即 LnL1 和 R1Rm 都依存于H，我们称这种成分之间的依存关系为成分依存成分依存。2.1 指导性关系抽取:树核函数方法21 动态关系树（DRT，Dynamic Relation Tree）假设：句法树中语义关系由两个实体间最短路径上的结点以及它们的中心子结点所决定，这些结点及其上下层关系构成了动态关系树。DRT的生成：从最小完全树（MCT）出发，沿着连接两个实体的最短路径上的每一个结点，根据成分依存规则保留相关的结构化信息（即路径上的结点及其中心部分），同时逐步去除其余噪音，最终得到动态关系树。2.1 指导性

14、关系抽取:树核函数方法22 动态关系树的生成 成分依存关系 基本名词短语内的修饰：本身不包含名词短语的名词短语；实体中心词前的内容可删除，中心词及其后面内容要保留。对名词短词的修饰 即包含名词短语的名词短语，如：NP NP SBAR relative clause NP NP VPreduced relative NP NP PP PP attachment 右边的成分可归约为左边单一的成分。2.1 指导性关系抽取:树核函数方法23 动态关系树的生成论元/附属语对动词的修饰关系 在上下文无关方法的推导规则中，左边往往含有S,SBAR或VP等成分。包含在路径中的论元和附属语都依赖于动词，因此把它

15、们从树中删去，一般不会影响到语义关系，如图(d)所示。并列连接关系 在并列连接结构中，大都是名词并列结构，各个并列部分之间的作用是相同的，因此只需要保留路径穿过的那个并列部分并进行归约，如图(e)所示。对其它成分的修饰关系 除了上述四种类型，对其余成分（如 PP、ADVP和PRN等）的修饰关系。不过，这一部分所占的比例较少，影响也很小。2.1 指导性关系抽取:树核函数方法24(a)Removal of constituents before the headword in base-NP(b)Keeping of constituents after the headword in base-

16、NPNNoneINofDTtheNNtownPOSsE-FACNNplantstwoCDNNoneINofNNtownPOSsE-FACNNplantsmeat-packingJJNNonePPINofNPDTtheNNtownPOSsNNplantstwoCDNNoneINofNNplantsmeat-packingJJNNoneINofRBaboutQPCD500NNSpeople.nominatedVBNforINVPPP.E2-PERNNoneINofNNSpeopleNNpropertyPRPheVPVBZINinNPPPstateNNStheNPJJrentalSownsDTNNp

17、ropertyPRPheVPVBZownsgovernorsfromconnecticutNNSINNPE-GPENNP,southNPE-GPENNPdakotaNNP,andCCmontanaNNPgovernorsfromNNSINmontanaNNP(c)Reduction of modification to NP(d)Removal of arguments to verb(e)Reduction of conjuncts for NP coordinationE-GPENPPPE1-FACNPE2-FACNPE1-FACNPNPNPNPE2-FACE1-PERNPNPPPNPNP

18、NPE1-PERPPNPE2-PERNPSBARE2-PERSNPNPE1-FACPPNPNPE1-PERNPE2-GPENPE1-PERPPNPNPNPE2-GPENPE1-FACE2-PERNPNPSBARNPNPE1-FACPPNPNPE2-GPENPNPE1-PERPPNPNPE2-GPE动态关系树例子25动态关系树中修饰关系的应用模式M1独立模式：每一种依存关系都独立地应用到最小完全树上；M2累加模式：每一种依存关系按照潜在的重要性依次逐一应用。动态关系树性能分析DRT最终的P/R/F性能为 77.4%/65.4%/70.9，F指数比MCT增加了8.2；前两个修饰关系对抽取性能的提高

19、最明显，F指数分别增加了4.4/2.3，而其余的作用就较小；表明修饰关系离实体越低，效果越明显，从而证实了实体关系的局部性。依存关系 PRFMCT(基准)75.153.862.7基本名词短语内的修饰76.5(76.5)59.8(59.8)67.1(67.1)对名词短词的修饰77.0(76.2)63.2(56.9)69.4(65.1)论元/附属语对动词的修饰关系77.1(76.1)63.9(57.5)69.9(65.5)并列连接关系77.3(77.3)65.2(55.1)70.8(63.8)对其它成分的修饰关系77.4(75.0)65.4(53.7)70.9(62.6)2.1 指导性关系抽取:树

20、核函数方法ACE RDC 2004关系大类26 结构特征和实体语义特征的复合 实体语义特征对语义关系抽取非常重要 实体语义特征如何同结构化信息结合起来？集成在统一的结构树中 复合核函数的利用 哪些实体语义特征及其组合是重要的？实体类型、小类、引用类型和实体类别等 一元、二元或多元特征2.1 指导性关系抽取:树核函数方法27语义实体树 特征列表树（Bag Of Features，BOF）：所有的结点都统一挂在根结点下。特征匹配树（Feature-Paired Tree，FPT）：同一个关系中的两个实体的同一特征先挂到一个父结点上，然后再统一挂到根结点上。实体匹配树（Entity-Paired T

21、ree，EPT）：一个实体的所有特征先合并到“E1”或“E2”结点，然后再挂到根结点上。TP2TP1(a)Bag Of Features(BOF)ENTST2ST1MT2MT1PVB(c)Entity-Paired Tree(EPT)ENTE1E2(b)Feature Paired Tree(FPT)ENTTPSTMTST1TP1MT1TP2ST2MT2PVBTP1TP2ST1ST2MT1MT2PVBPERnullPROGPEPop.PRObePERnullPROGPEPop.PRObePERGPEnullPop.PROPRObe2.1 指导性关系抽取:树核函数方法28TP2TP1PERGPE

22、T4:DRT-ToppresidentofmexicoNNINNNPPPNPE2NPE1NPTPTPPERGPET2:DRT-BottompresidentofmexicoNNINNNPPPNPE2NPE1NPT3:DRT-EntitypresidentofmexicoNNINNNPPPNPE2-GPENPE1-PERNPT1:DRTpresidentofmexicoNNINNNPPPNPE2NPE1NP合一句法和实体语义树DRT-BottomDRT-TopDRT-Entity29合一句法和实体语义树加入实体类型特征的动态关系树，其抽取性能的F指数平均提高了10。将实体语义特征挂到根结点上的D

23、RT-TopNode，其F指数分别比另外两种超过0.6和0.3。实体类型特征插入位置P（%）R（%）F1DRT（基准）68.753.560.6DRT-BottomNode76.264.470.3DRT-EntityNode77.164.370.6DRT-TopNode76.465.270.92.1 指导性关系抽取:树核函数方法ACE RDC 2004关系大类30合一句法和实体语义树实体小类和引用两个特征也能明显提高了性能，F指数分别提高了1.4和1.8；另外四种实体特征不但没有提升抽取性能，F指数反而分别降低了0.4、0.3、1.0和1.0；将谓词原形移动到根结点下，召回率得到了提高，因而F指

24、数提升了0.7。结论：实体类型、小类、引用类型和谓词原形等在结构化信息中的作用最大。#实体语义信息P(%)R(%)F1DRT(基准)68.753.560.62+实体类型76.465.270.93+实体小类78.266.372.24+引用类型80.068.174.05 实体类别80.267.873.96 GPE角色79.867.773.77 中心词80.067.573.68 LDC类型80.067.773.79+谓词原形80.269.274.7ACE RDC 2004关系大类2.1 指导性关系抽取:树核函数方法31合一句法和语义树（UPSTUnified Parse and Semantic T

25、ree）所有三种配置的合一动态语义关系树均比仅包含实体类型的动态语义树性能明显提高，F指数平均提高幅度约为4。Tree SetupsPRFDRT-Top77.465.470.9UPST(BOF)80.469.774.7UPST(FPT)80.170.775.1UPST(EPT)79.970.274.82.1 指导性关系抽取:树核函数方法ACE RDC 2004关系大类32 动机 同时捕获关系实例的平面特征和结构化特征 复合方式 线性复合：K1(R1,R2)=KL(R1,R2)+(1-)KP(R1,R2)多项式复合：K2(R1,R2)=KPL(R1,R2)+(1-)KP(R1,R2)其中KL 和

26、 KP 分别表示基于平面特征的线性核函数和基于结构化句法信息的卷积树核函数，是两者的复合系数。2.1 指导性关系抽取:复核函数方法33 多项式复合核函数能显著提高关系抽取的性能，验证了平面特征和结构化特征之间的互补性。核函数P(%)R(%)F合一句法和语义树（UPST）80.170.775.1Zhou等（2005）基于特征向量的线性核函数82.862.171.0多项式复合（d=2,=0.3）83.072.077.12.1 指导性关系抽取指导性关系抽取:复核函数方法复核函数方法ACE RDC 2004关系大类34 采用复合核函数的方法取得了目前最好的性能Systems(composite)PRF

27、Systems(single)PRFOurs:Composite kernel 83.072.077.1Ours:CTK with UPST80.170.775.1Zhou等(2007):Composite kernel 82.270.275.8Zhou等(2007):CS-CTK with CS-SPT 81.166.773.2Zhang等(2005):Composite kernel 76.168.472.1Zhang等(2005):CTK with SPT 74.162.467.7Zhao and GrishmanComposite kernel 69.270.570.42.1 指导性关

28、系抽取:复核函数方法ACE RDC 2004关系大类35目录1.引言和相关工作2.研究内容和方法2.1 指导性关系抽取 2.2 弱指导关系抽取 2.3蛋白质相互作用关系抽取3.工作展望362.2 弱指导关系抽取 自举学习:种子选取策略 标注传播算法:支撑矢量自举策略37自举学习基本原理 通过利用不断增长的标注实例训练所得的模型来对未标注实例进行分类，并且将正确分类可信度较高的实例加到标注数据集中，不断重复以上迭代过程。存在问题初始种子集的选取：目前采用随机采样方法，由于数量较小，结果不稳定。迭代过程的控制等。2.2 弱指导关系抽取:自举学习38 分层采样策略首先对所有未标注实例按照一定标准进行

29、分层，然后再在每层中按比例选择实例组成初始数据集，再进行手工标注。通过这种选择方法，一方面保证了所选择的实例具有较高的代表性，另一方面也考虑了关系实例在初始种子集上数据分布的多样性。2.2 弱指导关系抽取:自举学习39ACE RDC 2004关系类别分布关系大类关系小类训练集%测试集%Located59317.214516.9Near702172Part-Whole2998.7799.2小计96227.924128Business1343.9394.5Family1012.9202.3Other441.3111.3小计2798.1708.1Employ-Executive38811.31011

30、1.7Employ-Staff42712.411213Employ-Undetermine661.9121.4Member-of-Group1524.4394.5Subsidiary1694.9374.3Partner100.320.2Other641.9161.9小计12763731937.1EMP-ORGPHYSPER-SOC关系大类关系小类训练集%测试集%User-or-Owner1604.6404.7Inventor-or-Man.80.210.1Other1010.1小计1694.9424.9Ethnic310.980.9Ideology391.191Other431.2111.3小

31、计1133.3283.3Citizen-or-Residence2266.6475.5Based-In1654.8505.8Other310.980.9小计42212.310512.2DISC2236.5566.5合计3444100860100ARTOTHER-AFFGPE-AFF2.2 弱指导关系抽取:自举学习40随着层数的增加，初始性能和最高性能均同步增长，当使用小类类别（含逆向关系）作为分层标准时，两者达到最好高值，F值分别比大类分层提高了1.5和1.8。结论：层次越多，层内数据的差异性减小，层间的差异性增加，因此抽取出的实例具有更高的代表性和多样性。初始种子选取策略层数初始值最高值P(

32、%)R(%)F1P(%)R(%)F1大类分层769.166.567.771.066.968.8大类分层（含逆向关系）1369.367.368.271.667.069.2小类分层3069.867.768.772.767.870.1小类分层（含逆向关系）3969.968.569.272.968.470.62.2 弱指导关系抽取:自举学习ACE RDC 2004关系大类41 同类系统 Bootproject(Zhang 2004)随机抽样产生种子集，特征投影，互助学习。LP-js(Chen等2006)随机抽样产生种子集，标注传播算法。结论 分层自举比两者的F指数分别提高了5.9/4.1，主要得益于种

33、子集的选取。PRFPRFPRFROLE78.569.773.88174.777.774.786.380.1PART65.634.144.970.141.652.266.44755AT6184.870.974.279.176.674.966.170.2NEAR-13.712.5131002.95.6SOC4757.451.74559.15165.27971.4Average67.967.467.673.669.470.973.873.373.5RelationtypesBootprojectLP-jsStratified Bootstrapping2.2 弱指导关系抽取:自举学习ACE RDC

34、2003关系大类42 基于聚类的种子选取策略 思想：首先将所有实例按相似度采用某一聚类算法进行聚类，然后根据某一簇的大小选取一定数量的实例进行标注，构造种子集，利用自举算法进行弱指导语义关系抽取。簇内采样 从某一簇中选取一定数量的实例；首先选取该簇的中心Ci，然后使用KDN(K-diverse neighbors)方法选取其它实例，使得每次加入的实例和原有的实例保持足够的差异性。2.2 弱指导关系抽取:自举学习43GOLD 以类别作为聚类依据RAND 随机采样SEQ 顺序采样聚类 KM：K中值 HAC：分层聚类 SC：谱聚类 AP：仿射传播聚类SamplingstrategiesP(P)R(R

35、)F1(F1)GOLD79.5(7.8)72.7(2.1)76.0(4.8)RAND*71.9(3.7)69.7(0.1)70.8(1.8)SEQ*71.9(2.6)65.2(0.1)69.3(1.3)KM*73.6(2.1)72.3(0.3)72.9(1.2)HAC79.0(10.2)73.0(1.1)75.9(5.6)SC*72.3(2.1)72.1(0.4)72.2(1.2)AP75.7(2.5)72.0(0.4)73.7(1.4)*表示做10次测试的平均值2.2 弱指导关系抽取:自举学习ACE RDC 2004关系大类44 标注传播算法（LP，Label Propagation）基本原

36、理一种基于图的弱指导学习方法，将标注实例和未标注实例表示为连通图中的结点。将标注信息从任意一个结点通过它的邻接边传递到它的邻接结点，并不断重复以上迭代过程，最后当传播过程聚合时就可以推断出未标注实例的标注信息。LP算法存在问题对数据不平衡比较敏感，即不同类的实例数目相差比较大时，性能会大大下降；计算成本和内存需求较大（特别是语料规模巨大的时候）2.2 弱指导关系抽取:标注传播算法45 基于自举矢量的LP算法动机：利用自举算法产生关键实例 在SVM二元分类器中，支撑矢量作为关键实例决定了超平面位置，而其余矢量对目标函数则没有影响。策略 选择SVM这一基本分类器从已标注实例和未标注实例中找出一定数

37、量的加权支撑矢量。假设这些关键实例能够很好地保留所有已标注和未标注实例的自然簇结构。从所有已标注和未标注实例中自举产生的加权支撑矢量加权支撑矢量以及留在未标注实例中的难于可靠分类的困难实例困难实例2.2 弱指导关系抽取:标注传播算法46基于协同训练的关键实例产生算法BEGINREPEATFOR i=1 to P DO从原始特征集 F 产生投影特征空间 Fi;将 L 和 U 映射到特征空间 Fi，从而产生 Li 和 Ui;在 Li 上为每一个关系类型 rj 一个训练SVM分类器 SVMij;在 Ui 上对每一个关系类型 rj 应用分类器所学到的模型 SVMij;END FOR在 U 中找出具有最

38、高分类一致性（阈值为70%）和最高平均置信度（阈值为1.0）的（最多）S 个实例;将这些实例从 U 移到 L;UNTIL 没有足够多（小于10）的实例从中可靠地识别出;返回最后一次训练时分类器 SVMij 所得到的支撑矢量（包括正例和负例）及其它们的权值信息（a*y 的绝对值），这些自举产生的支撑矢量集作为LP算法的标注实例;返回 U 中剩余的实例（即不能够被自举学习可靠识别出的困难实例）作为LP算法中的未标注实例；END L:标注数据集U:未标注数据集S:每次迭代加入的数据集大小（设为100）P:视图数（特征投影）r:类型数（包括所有关系小类和无关系）2.2 弱指导关系抽取:标注传播算法47

39、采用关键实例的标注传播算法 :一个 标记矩阵,其中 表示顶点 具有标记 （包括没有关系）的概率;:的上面 个已标注的实例;:的下面 个未标注的实例;:一个 矩阵,其中每个元素 表示从结点 跳转到结点 的概率;BEGIN初始化:1)设置迭代索引 ;2)使 成为每一个结点的软标记（可介于0和1之间）;3)使 与标注数据中的标记（包括大类/小类以及没有关系）相容，其中 =表示自举产生的支撑矢量 具有标记 或者是 0 的归一化权值;4)初始化 ;REPEAT计算 ，将每一个结点的标记传播到邻近结点;重置标注数据，即用 代替 ;UNTIL 收敛（比如 收敛于 ）;对每一个未标注实例 ，赋予标记cj=;E

40、ND Yrn*ijy)1(nixi)1(rjrjLY0YluUY0YTnn*ijtixjx0t0Y0LY0ijyixjr0UYttYTY10LY1tLYY1tLY0LY)(nilxijijymaxarg2.2 弱指导关系抽取:标注传播算法48分析自举加权支撑矢量和加权矢量相比，小类关系抽取的F指数分别提高了3.6。采用所有训练实例的LP算法要比仅采用已标注实例的LP算法，F性能要高多3.4。困难实例在捕获自然簇结构方面很有用，F指数可提高2.1。采用自举加权支撑矢量的LP算法其性能大大高于采用所有训练数据的LP算法，F指数高于2.6。结论加权SVM自举支撑矢量能显著提高LP算法的性能。已标注数

41、据类型关系检测大类抽取小类抽取加权支撑矢量64.956.046.2自举加权支撑矢量66.558.549.8自举加权支撑矢量和困难实例67.759.851.9所有已标注实例64.655.645.9所有训练实例65.958.349.3ACE RDC 2004（正例400个，负例等比例）2.2 弱指导关系抽取:标注传播算法49基于SVM自举的LP的性能优于标准的SVM和LP算法基于SVM自举的LP通过增加训练时间来减少算法的实际运行时间 虽然基于SVM自举的LP算法的训练时间相当长，但其测试时间同SVM却在同一个水平上，且训练过程只需要一次，因而SVM自举是值得的。弱指导学习方法大类抽取F值训练时间

42、(分)测试时间(分)基于SVM自举的 LP58.14813.0标准 LP55.6022SVM51.32.51.9基于SVM自举的BootProject54.348117ACE RDC 2004关系小类抽取时间(正例400个，负例等比例)2.2 弱指导关系抽取:标注传播算法50目录1.引言和相关工作2.研究内容和方法2.1 指导性关系抽取 2.2 弱指导关系抽取 2.3蛋白质相互作用关系抽取3.工作展望512.3 PPI抽取 基于特征向量的PPI抽取 基于树核函数的PPI抽取52 特征抽取 词汇特征 交叠特征 基本短语块特征 句法树特征 依存关系特征(DependencySet1)蛋白质到LCA

43、的路径，蛋白质之间的依存关系等 动词的依存关系(DependencySet1)蛋白质前后的动词、其它动词，动词的数量等2.3 PPI抽取:特征向量方法53语料库：AIMed 177篇Medline摘要有PPI关系 48篇Medline摘要没有PPI关系 4,084个蛋白质引用 大约1,000个PPI标注实例结论 词汇特征最有效 基本短语块和依存信息较有效 交叠特征和句法树特征贡献有限特征P(%)R(%)F1词汇信息59.440.647.6+交叠特征60.439.947.4+基本短语块59.244.550.6+句法树60.944.851.4+DependencySet162.948.053.9+

44、DependencySet263.448.854.72.3 PPI抽取:特征向量方法AIMed54 研究难点 句子复杂，句法树庞大，噪音较多，难以取得好的性能，因此这方面的研究工作较少。基本对策 对句法树进行裁剪 手工制定规则裁剪句法树的缺点 手工制定规则费时费力，而且不易扩充到其它领域；成分依存关系分为五大类，粒度太粗，无法适应不同的依存关系。自动裁剪句法树？2.3 PPI抽取:树核函数方法55 基于依存关系的句法树自动裁剪方法 研究动机 最短依存路径对蛋白质关系抽取具有重要的作用（Airola等2008;Miyao等2008;Miwa等2009）句法树在语义关系抽取中取得了较好的性能(Zh

45、ang等2006；Zhou等2007)。基本思想 利用最短依存路径来指导蛋白质关系抽取中的句法树裁剪。自动裁剪方法 以两个蛋白质之间的最短依存路径为出发点，将这些词汇在句法树中的对应结点及它们的相关结点加入到句法树中，其余结点从句法树中删除，最终得到由最短依存路径指导的成分句法树（SDP-CPT，Shortest Dependency Path-Constituent Parse Tree)。2.3 PPI抽取:树核函数方法56例句(c):Association between PROT1 and cyclin B1/PROT2 was detected in the HeLa cells.(

46、d):Interestingly,PROT1 and phospheratidylinositol-3(PI-3)kinas can simultaneously bind distinct tyrosine regions on the same PROT2 molecule.2.3 PPI抽取:树核函数方法57TreesetupsAIMed BioInferHPRD50IEPALLL Ratio ofPOS/NEG1000/48342534/7119163/270335/482164/166MCT31.8(78.0)53.8(76.7)48.0(73.4)62.3(78.6)77.1(73

47、.4)SPT(baseline)47.1(79.9)54.2(73.7)61.3(81.6)66.6(82.2)79.4(86.1)CS-SPT46.5(80.2)54.5*(74.5)63.6*(79.9)66.8*(81.0)80.1*(86.0)DSPT50.0*(77.8)58.3*(78.5)66.0*(80.3)68.6*(80.9)77.3(79.3)SDP-CPT58.1*(83.3)62.4*(83.6)68.8*(83.4)69.8*(82.0)84.6*(89.2)2.3 PPI抽取:树核函数方法58PPI extraction systemsP(%)R(%)F1Our

48、SDP-CPT kernel59.157.658.1Dependency path:Kim et al.(2010)61.453.356.7Dependency graph:Airola et al.(2008)52.961.856.4Word subsequence:Bunescu et al.(2005a)65.046.454.2Constituent parse tree:Tikk et al.(2010)39.231.934.6BOW+Dependency path:Stre et al.(2007)64.344.152.0BOW+Constituent parse tree:Miya

49、o et al.(2008)50.956.153.0Global+Local context:Giuliano et al.(2006)60.957.259.0Dependency+Predicate Argument Structure:Miyao et al.(2008)54.965.559.5BOW+Shortest Path+Depencency graph:Miwa et al.(2009)-64.2AIMed 2.3 PPI抽取:树核函数方法59目录1.引言和相关工作2.研究内容和方法2.1 指导性关系抽取 2.2 弱指导关系抽取 2.3蛋白质相互作用关系抽取3.工作展望603.工

50、作展望 理论：篇章结构和篇章话题 复杂语义关系抽取 开放式信息抽取 命名实体间语义关系网络 蛋白质交互作用网络61跨文本信息抽取 基础研究 中文分词、命名实体识别 句法分析 语义分析：语义角色标注 篇章理解 单文本指代消解 跨文本指代消解 篇章结构标注 应用研究 实体间语义关系抽取、信息融合62跨文本信息抽取 基础研究 中文分词、命名实体识别 句法分析 语义分析：语义角色标注 篇章理解 单文本指代消解 跨文本指代消解 篇章结构标注 应用研究 实体间语义关系抽取、信息融合63跨文本信息抽取 基础研究 中文分词、命名实体识别 句法分析 语义分析：语义角色标注 篇章理解 单文本指代消解 跨文本指代消