基于叙词表的领域知识图谱初始种子集自动生成算法

韩其琛,赵亚伟,姚 郑,付立军

(中国科学院大学 大数据分析技术实验室，北京 100049)

0 引言

随着互联网的快速发展，网络上的数据变得越来越庞大，伴随而来的就是对于庞大数据的管理问题。同时传统的文档网页组织方式造成了大量数据资源浪费，也加大了人们从互联网中查询信息的难度。知识图谱作为一种用实体及其语义关系来表达知识的有向图，可以将传统互联网中由庞大信息组成的文档(网页)万维网变为包含大量描述各种实体和实体之间丰富关系的数据万维网。因此，自动构建图谱的算法成为目前的研究热点。

Bootstrapping算法是目前开放域信息抽取中比较常见的一种方法，通过模板生成和实例抽取两个阶段不断迭代，进而不断扩充关系实例。由于Bootstrapping的使用并不需要引入句法分析等深度语言分析工具，因此具有很强的跨领域通用性和鲁棒性。但是Bootstrapping的效果往往取决于种子的选取和设置[1]。在Bootstrapping方法中，自动化的种子生成主要利用现有的知识库如知识图谱或本体，从知识库中已经确定的实体和关系类型中抽取种子[2]。这种方法在构建通用知识图谱时产生了很好的效果，但是在垂直行业领域，由于领域本体和图谱均尚未成熟，实体和关系类型粒度过粗，导致该方法难以利用。与之相对的是，目前很多行业领域都有自己较成熟的叙词表。

叙词表是一个相对完善并且发展成熟的受控词表，最早用于传统文献标引工作，其内部蕴含丰富的语义关系。叙词表中的关系有相等关系、等级关系和相关关系三种，其中除了相等关系和等级关系，其余的所有关系都用相关关系命名。作为一个受控词表，叙词表并没有显式地表达出实体类型和关系类型。针对这一问题，本文提出两个假设，即一元关系种子假设和二元关系种子假设，利用假设可以从叙词表内部结构中提取实体类型和关系类型，进而提出了一种基于叙词表的自动生成高质量种子的方法。在实验中，利用由叙词表自动生成的种子作为初始种子进行抽取工作，通过对抽取结果进行分析，发现利用叙词表得到的初始种子可以取得同人工设计种子比较接近的效果。

1 相关工作

在关于开放域无/弱监督信息抽取的研究中，除了Bootstrapping方法外，主流方法有开放域抽取[3-5]和远程监督方法[6-8]。开放域抽取方法虽然可以在无监督的条件下从句子中抽取关系，但无法明确定义关系类别；而远程监督方法则需要一个具有一定规模且关系种类多的知识库，因此在垂直领域难以应用。

Bootstrapping方法最早由Blum等人于1998年提出[9]，Wang和Cohen进一步完善该方法，提出了用于抽取一元关系和二元关系的SEAL算法[10-11]，这也是目前Bootstrapping算法的基本形式。Carlson等人利用SEAL及其改进方法构建一个NELL(toward never ending language learning)系统[2,12]，利用一个初始的本体得到需要抽取的实体和关系类型，并通过人来手工构造种子。Bootstrapping方法面临的一个主要问题是在迭代过程中会引入噪声实例和噪声模板，这一问题称为语义漂移问题[13]，这也是导致算法准确度下降的主要原因。为了解决这一问题，文献[14]通过建模不同抽取关系之间的约束，寻找最大化满足这些约束的抽取结果；文献[15]通过引入负实例来限制语义漂移，以上均是在抽取的过程中进行改进。Wang和Cohen等人在其研究中证实良好的种子设计同样可以大大提高算法的准确度[16]。这也说明，高质量的种子可以在算法迭代的初始阶段有效地避免语义漂移问题的发生。

关于叙词表的应用，同本文类似的研究为叙词表到本体的转化。与本文只需要从叙词表中提取实体和关系类型不同，该研究最终需要得到一个符合OWL等相关规范的具有完整体系的本体。由于本体同叙词表的结构有着很大的差异[17]，因此，该类研究通常需要先手工构建对应领域的本体框架，随后将叙词表中的关系转化到对应的框架中。文献[18]发现大部分转换方法只针对特定叙词表，缺乏通用性的转换方法。文献[19]给出了从领域叙词表转化为领域本体的完整方法，使得在保留原有语义的同时能够具有本体特有的语义信息如推理等，但是依旧需要人工来制定本体的基本结构以及转化规则。

2 相关定义

叙词表一般可表示为一个三元组G={PT,VT,R}，PT为叙词集合，也称为优选术语集合，是所有关系的基础，VT为非叙词集合，与优选术语定义等价，所有词的集合为WT=PT∪VT。R为词间关系，可表示为一个五元组R=D,S,F,C,Z，其中有三种关系为建立在PT内部的对应，对于任一叙词x∈PT，S(x)表示x的上位词，F(x)表示x下位词，C(x)表示x的相关词。D为建立在PT子集到VT之间的对应，对于任一叙词x∈PT，D(x)代表x的同义词。Z为建立在PT到TT的映射，对于任一叙词x∈PT，Z(x)代表x的族首词，其中TT={x∈PT|Sx=∅∧Fx≠∅}。

定义1(叙词表概念树) 在叙词表中，对于∀z∈TT，集合y∈PT|Zy=z为一个由有限节点组成的具有层次关系的集合，根据树的定义，该集合可以用多叉树表示，该集合T称为叙词表概念树。树中的节点N称为叙词节点。对于每一个节点N所对应的叙词y，若D(y)不为空集，那么D(y)中的非叙词也在节点中存储。每个叙词节点对应一个实体。

叙词表概念树的形式如图1所示。

图1 叙词表概念树

定义2(叙词森林) 对于集合TT={z1,z2,...,zn}，根据定义1将族首词zi转化为叙词表概念树ti。 所有ti构成的集合称为叙词森林。

根据前两个定义，可以将整个叙词表转化为一个叙词森林。值得注意的是，在每棵叙词表概念树T的内部，只存在等级和等价两种关系，相关关系存在于树与树之间。为了得到更多的相关关系，对叙词表中原有的相关关系做了扩充。

定义3(相关关系) 相关关系CP=C∪CI，若x,y存在相关关系，那么CP(x,y)为真。其中，叙词表中所规定的相关关系C称为直接相关关系，本文拓展得到的相关关系CI称为间接相关关系。

定义4(间接相关关系) 假设两个节点对应的叙词yi,yj存在相关关系C，那么存在式(1)。

为了筛选出运行性能最好的种子，引入有效候选实体(对)和语义范围的概念进行种子筛选，从而得到抗语义漂移能力强且更加具体的种子。一般来说，一个一(二)元种子包含两个实体词(对)，因此规定一个一元种子为集合useed=s1,s2，一个二元种子为集合bseed=px1,py1,px2,py2。

定义5(有效候选实体) 对于∀useed进行一轮迭代，对于返回的候选实体t，若满足t∈{y|s1,s2,y∈T}，其中，T为一棵叙词表概念树，则t称为有效候选实体。

定义6(实体类型集合) 设USi={useed1,useed2}为自动生成的第i个实体类型的种子，规定对USi进行扩充后的实体词集合为ETi=bstuseed1∪bstuseed2∪Ti。 其中，Ti为种子所在的叙词表概念树，bstuseed指对种子useed进行限轮次的迭代得到的实体集合。将所有实体类别分别进行扩展得到的ETS={ET1,ET2,...,ETn}称为实体类型集合。

定义7(有效候选实体对) 对∀bseed进行一轮迭代，对于返回的候选实体对(x,y)，若满足x,y∈{x,y|y,py1,py2∈ETi∧x,px1,px2∈ETj}，则称(x,y)为有效候选实体对。

定义8(语义范围) 在叙词表概念树T中，对于任意节点N，其语义范围定义为式(2)。

其中，ln为以节点N为根节点的子树所包含的叶子节点数目，lN为T所包含的全部叶子节点数目。

3 种子自动生成算法

3.1 一元关系种子自动生成

当Bootstrapping进行一元关系扩展时，其主要接受少部分词作为种子，在文本中找到适用于这些种子的共同模板，利用这些共同模板从文本中抽取新的候选实体，从中优选出合适的实体词加入到种子集合中，从而达到一元关系扩展的目的。本算法首先提出一个判断叙词表内部任意两个词是否属于同一个实体类型的假设，随后利用该假设提出USAG(unary seed auto-generation)算法。首先，本文提出假设1，如下文所示。

假设1(一元关系种子假设) 在叙词表中，对于任意两个词∀w1,w2∈WT，若存在一个叙词表概念树T，满足w1∈T∧w2∈T，那么w1,w2具有相同的实体类型，否则，w1,w2具有不同的实体类型。

例如，在地质领域叙词表中有两个族首词分别为金属元素和金属矿，由这两个族首词所形成的两棵叙词表概念树分别代表地质领域两种常见的实体类型。

根据假设1，可以将叙词森林中的每一棵树转化为一个实体类型集合。为了选择更加合适的种子，提出一元种子评分函数。种子评分函数的设计主要考虑两方面要素。首先是指代明确，种子中的实体词应表示明确的实体，这样才能找到更多有效的实体；其次是防止语义漂移的能力，如果一个种子在初始阶段会发生严重的语义漂移现象，那么后续的准确率将无法保证。对于一个一元种子useed=s1,s2迭代三到五轮，其评分uscore定义如式(3)所示。

其中，q为每轮迭代返回候选实体的平均数，p为每轮迭代有效候选实体的平均数，α为调节因子。

在评分公式中，返回的有效实体比例越大，该种子的防止语义漂移的能力越强；两个实体的语义范围越小，该种子中的实体词更加明确具体。

算法1 USAG算法伪代码输入: 叙词森林TF=T1,T2,…,Tn 输出: TOP1,TOP2,…,TOPm ,TOPm指第m个实体类型的种子1. 根据假设1构建实体类型集合,size表示集合元素的个数。ETS=ETi|sizeETi >2 ,ETi={y|y∈Ti};2. 对于ETS中的每个元素ETi,执行步骤3;3. 将ETi中的元素两两组合,利用Bootstrapping算法进行迭代,并根据公式(3)计算uscore,选取得分最高的前两个种子加入TOPi

3.2 二元关系种子自动生成

当Bootstrapping进行二元关系扩展时，其主要接受少部分实体对作为种子，主要的步骤和方法同一元关系类似，最终将优选的实体对加入到种子集合中。在设计种子时，需要预先定义好所有的关系类型，从而根据关系的类型来选取合适的实体对作为种子。本算法首先提出一个判断叙词表中任意两个实体词对是否具有同一个关系类型的假设，随后利用该假设提出BSAG(binary seed auto-generation)算法。本文提出的假设2如下所示。

假设2(二元关系种子假设) 在叙词表中，对于两个具有相关关系的实体词对{x1,y1,x2,y2|CPx1,y1∧CPx2,y2}，若存在两棵叙词表概念树T1,T2，满足y1,y2∈T1∧x1,x2∈T2，那么x1,y1,x2,y2具有相同的关系类型，否则，x1,y1,x2,y2具有不同的关系类型。

文献[20]中曾提出一个假设: 如果关系已经确定，那么关系前后的实体类别就可以确定。本文所提出假设可以视为该假设的反向结论，但是需要一个前提，就是在同一个领域叙词表中。在叙词表中，由于族的划分非常细致，实体类型粒度足够小，因此，利用关系前后主体和客体的实体类别基本可以限定一个关系。例如，叙词表中含有两个族首词为金属元素和金属矿，那么如果一个具有相关关系的实体对包括一个金属元素和一个金属矿，其描述的关系可以确定为是一种包含关系。

算法2 BSAG算法伪代码输入: 叙词森林TF=T1,T2,…,Tn 输出: TOP1,TOP2,…,TOPi ,TOPi指第i个关系类型的种子1. 根据假设2构建关系类型集合RTS={RTi|sizeRTi >2},RTi={x,y |x∈Ti∧y∈Tj∧CPx,y };2. 对于RTS中的每个元素RTi,执行步骤3;3. 将RTi中的元素两两组合,利用Bootstrapping算法进行迭代,并根据公式(4)计算bscore,选取得分最高的前两个种子加入TOPi

借助假设2，可以将叙词表中的相关关系根据前后实体类型的不同转化为不同的关系。利用有效实体对和语义范围的定义，对于一个二元种子bseed=px1,py1,px2,py2迭代三到五轮，其评分bscore定义如式(4)所示。

其中，q为每轮迭代之后返回候选实体对的平均数，p为每轮迭代有效候选实体对的平均数，β为调节因子，sc为scover函数的简写。在评分公式中，返回的有效实体对比例越大，该种子的防止语义漂移的能力越强；关系的前后实体的语义范围越小，该种子中的关系也更加明确具体。

种子自动生成整体框架如图2所示。

图2 种子自动生成框架

4 实验

4.1 实验数据和评价指标的选取

为了更好地验证方法的通用性，本文利用由中国地质图书馆提供的地质领域叙词表(总词数为10 511，族首词数为431)，以及从中国林业信息网得到的林业叙词表(总词数为38 521，族首词数为93)作为实验的叙词表资源，通过抓取搜索引擎的每条检索结果对应的网页得到。实验采用百度搜索作为搜索引擎。

本文选取文献[11]中的SEAL算法实现作为实验的Bootstrapping算法。在SEAL中，每一轮算法会返回一个排序后的候选实体列表。因此，本文采用信息检索的方式来对种子抽取的效果进行评估。平均准确率(MAP)是在信息检索领域常用的评价指标，该指标融合了准确率和召回率的衡量，而且对于排序的位置非常敏感。在MAP公式的设置上，为了更加合理的对比，本文采用文献[11]中的设计方式，具体如式(5)所示。

其中，L为抽取候选实例的列表；cn表示正确实例的个数；prec(r)为截止r之前的准确率，若r位置的实例不正确，则为0；isfresh(r)是一个二值函数，判断同义的实例是否在之前出现过，如果出现，则为0，否则，为1。对于关系类型抽取得到的实体对，也按照式(5)进行检验，每一个实体对作为一个关系实例来判断是否正确。

4.2 类型抽取检验

为了验证算法中所提出的两个假设的准确性，根据两个假设的内容，从两个不同领域的叙词表中提取各自的实体类型和关系类型，通过人工评测的方式找到其中的有效实体(关系)类型。这里有效的标准在于类型表达的含义明确而且和其他类型可以明确区分。由于叙词表的编排相对比较随意，这里保留至少有10个实例的实体类型和至少有七个实例的关系类型作为最终的类型。实验结果如表1所示。

表1 类型抽取测试

从表1中看出，实体类型的有效比例要好于关系类型，这是由于叙词表中族首词的划分本身就是由领域专家指定，相对来说比较规范；地质领域的效果普遍好于林业领域，这是由于不同叙词表虽然遵循同样的标准，但是其质量还是取决于人工制定的质量。通过对于无效类型的分析，主要的问题在于由于族首词划分过细导致类型之间会互相覆盖。

4.3 种子质量实验

为了检验算法中自动生成的种子的质量，从两个领域各自抽取八个实体(关系)类型，选取的类型如表2第二列所示。

对于每个实体(关系)类型分别得到两个种子，分别利用SEAL迭代至10轮，对于第10轮返回的候选实例列表进行MAP的测试。实验结果如表3所示。

表2 实例展示

关于超参数的设定，从表2的16个类型中，每个领域分别选择两个实体类型和两个关系类型共计八个用于测试超参数取值。利用网格搜索方法确定两个超参数α和β的取值，具体方法为，令α和β的取值区间均为[0, 10]，设定步长(本文设为0.5)，以第10轮返回的候选实例列表的MAP值作为最终的评价指标。最终确定最优的超参数的取值，本实验获得的最优超参数α的值为1，β的值为1.5。

表3 种子质量测试

这里利用三种方法对于两个领域的类型进行了测试。

(1) 随机选择种子是从类型当中随机抽取两个作为种子进行测试，对于关系类型，由于百度结果本身较少，有可能存在随机抽取得到的种子没有找到任何候选是实体对，那么以第一个有结果的种子作为结果记录。

(2) 自动生成种子就是利用本文提出的两个算法得到。

(3) 人工构造种子由人工来设计多个种子，最终选择效果最好的种子作为结果记录，基本可以认为是最好的结果。

SEAL平均得分是对于通用领域的人工设计种子进行的测试，相比于专业领域，通用领域所涉及的信息在互联网上更加全面丰富。

从实体类型的结果来看，自动生成的种子相比随机选择得到的种子效果有了大幅度的提升，取得了近似于人工构造种子的效果；林业领域的效果要略好于地质领域，但是基本上比较接近，这说明算法的跨领域通用性。

从关系类型的结果来看，相比于一元关系种子，通过三种方法得到的二元关系种子的准确率有一定程度的下降。其主要原因在于二元关系限制较多，从互联网中得到同时包含多个专业领域实体的文档数量会快速下降，在没有足够语料保障的情况下，候选种子的准确率会快速下降。

4.4 样例展示

为了更好地展示抽取效果，在表2第三列展示用于实验的实体类型和关系类型的前十个抽取结果。根据SEAL算法的规定，同4.3节中用于评估MAP的第10轮候选实例列表不同，这里的抽取结果是由每一轮迭代返回的候选列表中评分最高且非重复实例组成。为了方便进行错误的分析，在表2中利用黑体加框表示抽取错误。

通过观察表2，可以发现抽取的结果大部分都是符合其对应的类型名称，对于某些实例有限的类型例如育种培养和湖泊地貌，基本覆盖了常见的全部实例，这说明本文算法的有效性。

针对错误的实例，可以发现少量的实体类型错误，主要原因是由于实体范围有限或者语义漂移导致。例如，黄土地貌类型下，由于实体范围有限，前九个实体基本涵盖了所有常见的黄土地貌，所以第十个会出现错误；而在育种培养中，花器官作为植物繁殖器官同其他育种实体有着比较大的语义关系，这种情况会导致语义漂移的现象出现。

关系类型存在比较明显的语义漂移现象，例如，交代作用—变质岩以及显生宙—地壳运动中的错误，这是由于通用搜索引擎的领域性不强所导致，在没有足够语料保障的情况下，会出现一些错误；表中其他的关系类型错误主要是由于关系中实体类型不准确导致，例如，乌姆赖萨斯考古遗址并不属于国家公园，热带草原不属于森林等。

4.5 模型通用性分析

经过几十年的发展，叙词表的编制方法得到不断改善，最终形成了一系列的国际标准。国际标准有1974年发布的ISO 2788和1985年发布的ISO 5964, 中国目前的现行标准为 1991 年发布的GB/T 13190。在这些标准中均明确规定了叙词表的结构以及词间关系。本文所利用的叙词表的结构以及词间关系在现行任何符合标准的叙词表中均是存在的，因此本文所提出的算法具有较强的通用性。

5 结束语

由于Bootstrapping算法的性能很大程度上依赖于种子设计的质量，本文利用叙词表中所蕴含的语义信息，提出了从叙词表内部结构中提取实体类型和关系类型的两个假设，并设计了一种基于叙词表的自动生成高质量种子的方法，实验表明，该方法取得了同人工设计种子比较接近的效果。由于叙词表的通用性，本文模型同样适合其他的行业领域。该方法为构建领域知识图谱提供了一个新的研究思路。在今后的研究中可以从引入第三方监督进行联合建模等方面进行改进和完善。