1、 基于 句法 结构特征 分析及分类技术 的答案提取算法 胡宝顺 1, 王大玲 2+, 于戈 2, 马婷 2 1(东北大学软件学院计算机科学与技术专业 ,辽宁省沈阳市 110004) 2(东北大学信息科学与工程学院计算机软件与理论研究所 ,辽宁省沈阳市 110004) 摘 要 : 由于中文自然语言处理的特点和困难，以及相应的语言处理基础资源的相对缺乏，使得国外一些成熟技术和研究成果不能直接应用到中文问答系统中。为此， 针对中文事实型问答系统，提出一种新的基于 句法 结构特征分析 及分类技术 的 答案提取算法，该方法将答案提取问 题看成是候选答案的分类问题，即将候选答案分类为正确和错误两类。首先，
2、该方法根据与问题类型所对应的候选答案的类型信息，从文本片断中提取出候选答案及其在句子中的 简单 特征 和句法结构特征 ；然后利用这些特征训练 分类器 ；最后用训练得到的 分类器判别候选答案是否为正确答案。 针对中文事实性问题，该方法与目前典型的 基于模式匹配的 中文答案提取算法相比，准确率提升 6.2%， MRR提升 9.7%。 关键词 : 句法依存分析 ;分类 ;答案提取 ;中文问答系统 ;事实性问题 中图法分类号 TP391 1 引言 和国内外研究现状 随着互联网的普及，搜索引 擎已经成为人们快速查找信息和资源的重要手段。但 目前的搜索引擎 主要采用基于 关键字 的 查询 ，而关键字的简单
3、组合不能明确表述用户的查询意图 ，这一 问题 已 成为制约搜索引擎性能提高的瓶颈 之一 。 问答式检索系统（简称问答系统） 正 是 为克服传统搜索引擎的 这一 弊端应运而生 的 。与基于关键字的传统搜索引擎不同，问答系统允许用户以自然语言形式提问，并将准确简短的答案 、 而非大量的相关文本和网页返回给用户。比如：用户提问 “第三届亚洲政党国际会议是由哪个政党主办的？ ”，问答系统就可以将 “中国共产党 ”的答案返回给用户。因此可以说，问答系统是更高 效、更人性化的新一代搜索引擎。同时也是集自然语言处理、信息检索、信息抽取、机器学习等多学科技术于一体的复杂系统。 一般来说，问答系统主要包括问题分
4、析、信息检索和答案提取三个部分。其中，问题分析的主要工作包括确定问题类型 和 提取问题 中的关键字等；信息检索部分的任务是利用 问题 关键字 生 成查询条件， 然后 利用文档库或提交 给 Web 搜索引擎 进行 检索，返回 相关的文档或段落；答案提取部分的任务则是从候选的文档或段落中提取 出 正确 答案。作为问答系统中一个关键环节，答案提取部分性能的优劣直接影响整个问答系统的性能 。 Dan Moldovan1等人 关于 问答系统错误 的 分析结果表明，约 18.7%的回答错误是由诸如候选答案识别错误、答案排序错误等导致的。因此，答案提取算法的研究对提高问答系统整体性能 具有重要 的意义。 近
5、几年来， 国外很多科研院所和著名公司如 IBM、 Microsoft、 ISI、 MIT、 University Of Cambridge等都积极投入到问答技术的研究中， 多个问答系统评测平台如 TREC、 NTCIR、 CLEF的成功举办也极大的推动了该领域的快速发展。 目前，国外已经有一些相对成熟的问答系统问世，同时也不乏研究人员提出了很多效果 理 本课题得到国家自然科学 基金 (60573090)资助 .作者简介 :胡宝顺 ,男 ,1981 年生 ,硕士研究生 ,主要研究领域为信息检索技术 ;王大玲 ,女 ,1962 年生 ,博士 ,教授 ,主要研究领域为搜索引擎技术 ;于戈 ,男 ,1
6、962 年生 ,博士 ,博士生导师 ,主要研究领域为数据库及相关技术 ; 马婷 , 女 ,1981 年生 , 硕士研 究生 , 主 要研究 领域为 文本 挖掘技 术 . 联系 人 : 王大 玲 , 电话 :+86-24-8368-7776, E-mail: 2 想的答案提取算法。 同时 近些年 ，国内从事问答系统相关研究的机构不断增加 ， 其中中国科学院自动化研究所 、 哈尔滨工业大学 、 复旦大学 、 清华大学和 沈阳航空工业学院等都在该领域做 了很多研究工作 2,3,4。 但相对而言，中文问答技术的研究尚处于初级阶段，与国外存在较大差距。 一方面，由于中文自然语言处理的特点和困难，目前这
7、方面的各种底层技术还不够成熟和完善；另一方面，相应的语言处理基础资源如知识库、语料库等也相对缺乏，这使得国外一些成熟技术和研究成果不能直接应用到中文问答系统中。 基于此，本文提出一种应用于中文问答系统的基 于句法 结构特征 分析及分类技术的答案提取算法。 本文其余部分的组织结构如下： 第二部分简单介绍答案提取算法的相关研究工作； 第三部分 简要介绍 我们 提出的 算法的 总体 实现步骤； 第四部分 论述 提取句子句法特征时 应用 的关键技术 ：基于句法依存分析的路径相似度计算 ； 第 五 部分 阐述 候选答案的特征提取 及 分类问题；第 六 部分 给出 实验的具体步骤和实验结果；第 七 部分是
8、总结和展望。 2 相关工作 目前中文问答系统的 答案提取算法主要包括三类： (1) 基于信息检索和信息抽取的问答技术 5,6,7； (2) 基于模式匹配的问答技术 2,8,9,10,11,12,13； (3) 基于机器学习的答案提取技术 3,4。 文献 6描述了一个典型的基于信息抽取的答案提取算法。该算法的 主要思想是，在信息检索模块返回的前 几个 相关的句子的基础上， 进行更细化（ fine-grained）的命名实体识别 ， 将问题类型对应的命名实体作为候选答案，然后 将与 匹配词距离 最近 的候选答案 作为 正确答案。该文献提出的系统的整体性能良好，但是 仅就 答案提取 而言 ，算法 显
9、得 有些简单， 且 仅使用了匹配词与候选答案词的距离这一个特征。 文献 13提出了一种基于表面 文本 模式（ surface text pattern） 匹配 的答案提取算法。 该算法首先人工标注问题的标准答案 ； 然后 根据 搜索引擎检索含有问 题中的焦点词 和正确 答案 的句子，利用广义后缀树（ generalized suffix tree）算法提取出这些句子的公共字符串 ； 对公共字符串 经过过滤和准确性评估后，将 保留下的 字符串中的焦点词和标准答案替换为插槽词（ slot word）生成答案模板 ； 最后 利用答案模板来进行答案提取。 该方法在问题类型为询问生日、发明者、发现者、定
10、义、成名原因、地点时有很好的效果。 但是 解答 其他的问题类型 时 性能 不佳 ，且不能处理焦点词和正确答案之 间长距离的依存关系。 文献 2中提出了一种基于无监督学习的问答模式抽取技术。并通过实验证明应用问答模式提取答案是有效的。该算法无需用户提供 对作为训练集，只需用户提供每种提问类型两个或以上的提问实例。算法即可通过 Web 检索、主题划分、模式提取、垂直聚类和水平聚类等步骤完成该类型提问的答案模式的学习。该算法存在的问题是：需要对问题类型进行详细的划分，针对每一个问题类型均需要从互联网中学习相应的问答模式。该算法针对只有一个 “提问焦点词 ”的问题的性能较好。针对有多个必需限定词的问题
11、，该算法只能通过增 加问题模式类型来解决。如： “中国最长的河流是什么？ ”，该问题中的 “中国 ”和 “最长 ”均为必需的限定词。按照该算法，问题的 “提问焦点词 ”为 “河流 ”。这就导致了该算法的扩展性受到制约。 Ang Sun3将答案 句子 提取 问题 视为分类问题， 即 将候选答案句子分类为正确或是错误。 他们通过提取问题和候选答案句子的特征训练最大熵模型，然后利用得到的模型提取答案，并通过实验证明该方法的有效性。受到该文章的启发，我们提出了这个 基于分类技术 的答案提取算法。 我们的方法与 Ang Sun12的方法 的 不同之处在于， 我们的方法可以直接 提取出精确的答案词，而不是
12、答案所在的句子。 文献 4中提出了一种基于实例的答案提取算法。该算法利用问题及其对应的正确答案句子 、 错误答案句子和正确答案词中提取得到的特征作为分类算法最大熵模型（ Maximum Entropy Model）的训练特征。该文章主要提取了 以 下三个特征： (1) 查询词与句子的匹配情况； (2) 问题句子中的词与句子中的词的匹配情况； (3) 疑问词与句子中的词的匹配情况，即句子中是否含有与问题答案相同词性的词。以上三个特征均为布尔型值，即： “真 ”（ TRUE）或者 “假 ”（ FALSE）。该文 章仅对地点（国家）和实体（语言）型问题进行了性能测试，没有与其他答案提取算法进行性能对
13、比实验。该算法提取的分类特征比较简单，且均为布尔类型。没有考虑词之间的语义特征，所以在分类性能上将会受到一定的制约。 胡宝顺 等 :基于句法 结构特征分析及分类技术的答案提取算法 3 3 基 于 分类技术 的 答案提取算法 因为 本文 的重点是 答案提取算法， 问题分析和 信息检索 非本文的重点 ， 所以 我们将问题 类型 信息视为已知信息。 对于 信息检索模块 ， 我们简单 地 使用 Google 搜索引擎检索得到的文本片断 （ snippet） 作为答案提取的来源。 3.1 生成查询词 生成查询词是文本片断检索的基础。我们 借鉴了文献 7中系统的 查询词生成算法 并 加以 改 进 ， 具体
14、 算法如下 ： (1) 根据 问题集，生成一个疑问词列表。疑问词 为 形如： “谁 ”、 “哪 ”、 “什么 ”等等 的词 ； (2) 对问 题进行分词和词性标注，将问题中出现的疑问词及 其后面的量词或数量词 均 作为疑问词 剔除 ；如： “哪一年 ”这样的由疑问词和数量词构成的词将 作为疑问词 被 剔除 ； (3) 去 除 停用词。如： “的 ”、 “在 ”、 “于 ”等等 。同时 去 除 介词、助词和标点符号 ； (4) 将 剩余的 词 作为 关键词 ， 构成 查询条件 （关键词之间简单 地 以空格分隔，构成一个 “布尔或 ”查询） 。 3.2 训 练 分类器 训练 分类器 的目的在于：找
15、 出候选答案所在的句子的特征与候选答案是否为正确答案的一种潜在的映射关系，是实现候选答案分类的基础，具体实现步骤如下： (1) 将上面生成的查询 条件 提交给 Google 搜索引擎，保存 检索返回 的 前 100 个 文本片断 ； (2) 根据问题的类型， 利用命名实体 （人名、地名、机构名、时间词、数量词） 识别技术， 识别出 与问题 类型 对应 的命 名实体作为候选答案， 然后 计算候选答案 在所在句子中 的各个 特征 值 ， 最后 根据问题对应的标准答案，给候选答案加上类别标签（ 0：候选答案为非正确答案； 1：候选答案为正确答案） ； (3) 重复执行上面两个步 骤， 得到候选答案训
16、练 样本 集 ， 从而可以 利用 相应的分类器训练算法，训练得到用于分类的分类模型。 3.3 答案提取 答案提取是我们最后的目标，具体步骤如下： (1) 将问题查询词提交给搜索引擎，取得搜索引擎返回的前 30 个文本片断 ； (2) 根据问题类型，识别出每个文本片断中的候选答案 ， 并计算候选答案 所在句子的各特征值 ； (3) 利用训练好的 分类器 ， 预测 各个候选答案 的分类 ，并返回前 5 个结果。 4 基于句法依存 分析 的 路径 相似度计算 本 节详细阐述提取句子句法特征时所要使用的关键技术：基于句法依存分析的路径相似度计算 。 4.1 句法依存分析 句法分析（ parsing）是
17、自然语言处理领域研究的关键问题之一，属于浅层语义分析中的重要内容，在机器翻译、信息抽取和自动问答等多个领域中有着广泛而重要的应用，而基于依存语法的句法分析（简称句法依存分析）是目前句法分析的主要方法之一。 依存语法是 1959 年由法国语言学家 L. Tesiniere 在其著作结构句法基础一书中提出的。此语法的核心思想是：句子中述语动词是支配其它成分的中心，而它本身却不受其它任何成分的支配，所有的受支配成分都以某种依存关系从属于其支配者。依存语法的句法结构的主要元素是依存关系 （ dependency relat ionship） ，即句子中词对的二元关系，其中一个记为核心词 （ head）
18、 ，另一个记为依存词 （ dependent） 。依存关系反映的是核心词和依存词之间语义上的依赖关系。 对于事实性问题 “中国是在哪一年恢复了在联合国的合法席位？ ”，利用哈尔滨工业大学信息检索研究室提供的汉语句法依存分析器进行解析的结果如图 1 所示 。 4 Fig.1 An Example of Syntax Dependency Parsing 图 1 句法依存分析的一个例子 句子进行解析后得到的结果，我们将其简称为依存 树，其中的词称为依存树的结点。 如果两个 词 之间有弧相连，则表示它们之间存在依存关系。弧的方向是由核心词指向依存词，弧上的标记表示依存关系的类型。在哈尔滨工业大学自然
19、语言实验室开发的句法依存分析器中，依存关系类型共 有 24 种 14， 如表 1 所示。 Table 1 24 Kinds of Dependency Relations Defined in Hit-Irlab Dependency Parser 表 1 哈工大的依存分析器中定义的 24种句法关系 关系 描述 关系 描述 CNJ 关联结构 BA “把”字结构 IS 独立结构 BEI “被”字结构 HED 核心 DEI “得”字结构 RAD 后附加关系 DE “的”字结构 POB 介宾关系 DI “地”字结构 VV 连动结构 SIM 比拟关系 LAD 前附加关系 QUN 数量关系 COO 并列
20、关系 APP 同位关系 ATT 定中关系 DC 依存分句 VOB 动宾关系 MT 语态结构 CMP 动补结构 SBV 主谓关系 IC 独立分句 ADV 状中结构 4.2 路径提取 我们将依存树中两个结点 W1 和 Wn 之间的 “路径 ”定义为：从 W1 开始，到 Wn 结束中 间所经过的一系列依存关系和词（不包括开始词和结束词），我们可以将其表示为下面的表达式Path1,n:=，其中 Reli (1in-1)表示其中的第 i 个单一的依存关系； posj 表示第 j 个词的词性； 或者 表示依存关系的方向； Wi表示第 i 个词；因路径不包含开始词和结束词，所以在上面的定义表示中没有出现 W
21、1 和 Wn。也就是说，关系路径描述依存树中两个结点之间依存关系和词的一个遍历。虽然在对句子进行解析时， 其依存关系都是有向的，但由于在问题和候选答案句子中，某个词语作为支配者和被支配者的角色经常是可以互换的，因此，我们在提取关系路径时将其方向忽略。 路径两端的位置被称作插槽（ slot），而在此位置上的具体填充词被称为插槽词（ slot word）。在一个插槽中可能出现不同的填充词，插槽词不属于路径的一部分。 提取得到的路径可以 用于衡量 问题句子和候选答案句子之间的相似度。 因为 目前直接利用句子的依存树解析结果进行句子间的相似度计算比较困难，所以我们从依存树中提取出线性的路径。每一个依存
22、关系链接表示一个直接的语义关系 ，而一个关系路径允许我们表示两个词语之间非直接的语义关系。因为路径是整个句子的一部分，所以可以通过不同句子间对应的关系路径的相似度来计算出句子间的相似度。 胡宝顺 等 :基于句法 结构特征分析及分类技术的答案提取算法 5 关系路径 定义和 提取方法参考 了 文献 8中的内容 ，但提取关系路径时所 进行的预处理 和提取 规则有所不同， 具体 规则如下： 规则 1：对依存关系树中多个连续的时间词进行合并，使其成为一个时间词，同时 剔除 各个时间词内部的依存关系，只保留其与外部的依存关系。例如，句子 “1984 年 4 月 26 日至 5 月 1 日，美国总统罗纳德
23、里根访问中国。 ”的原始依存树解析结果 如图 2： Fig.2 Year/Month/Day is Seperated in Dependency Tree 图 2 依存树中年 /月 /日被分开 从图 2 可见，经过分词后，一个完整的时间词 “1984 年 4 月 26 日至 5 月 1 日 ”被分成 “1984年 /4 月 /26 日 /至 /5 月 /1 日 ”。且从图 2 可以看出，这个完整的时间词与其他词之间只有一个依存关系 “访问 ADV至 ”。我们将时间词合并，将时间词内部的关系 “ATT”、 “ADV”和 “POB”合并，只保留 “至 ”与 “访问 ”的依存关系。经过处理后，我们
24、得到图 3 的解析结果。 Fig.3 Combination of Year/Month/Day in Dependency Tree 图 3 年 /月 /日合并后的依存树 规则 2：对 “的 ”字结构（依存关系为 “DE”）， “地 ”字结构（依存关系为 “DI”）， “得 ”字结构（依存关系为 “DEI”）三个依存关系进行变换。删除句子中出现的 “的 ”、 “地 ”和 “得 ”（三个字必须均为助词词性，且对应依存关系须是 “DE”， “DI”， “DEI”），同时将删掉的助词的父节点直接指向删掉的助词的孩子节点，同时将依存关系修改为被删掉的词。如果该助词的父亲节点不唯一，不能进行转换。例
25、如句子 “我的名字是张三。 ”的原始依存树解析结果如图 4 所示： Fig.4 The Original Dependency Tree of“My Name is ZhangSan” 图 4 “我的名字是张三 ”的原依存树 6 从图 4 可以看出， “的 ”字的父亲节点为 “名字 ”，它的孩子节点为 “我 ”，并且只有一个父亲节点。符合我们的转换要求，我们将其转换，即将助词 “的 ”删掉，直接连接 “的 ”所关联的两个词 “名字 ”和 “我 ”。同时，将 “的 ”作为 “名字 ”和 “我 ”之间的依存关系 （如图 5 所示） 。 Fig.5 The Dependency Tree of “M
26、y Name is ZhangSan”After Deleting“DE” 图 5“我的名字是张三 ”删掉 “的 ”字后的依存树 类似 地 ，对“地”字结构和“得”字结构 ，也进行同样的处理 。 规则 3： 根据词性标注，将一些虚词删除，对依存关系进行变换。 方法与上面的步骤类似 ，如果被删除的词没有父节点，那么直接删除该词。表 2 中列举了被删除虚词的 词性 ， 词性 标注标准使用的是哈工大分词模块的词性标注标准。 Table 2 the Part of Speech of Words Should Be Deleted 表 2 将被删除的词的词性 词性 标注 e wp u p c o 含义
27、 叹词 标点符号 助词 介词 连词 拟声词 规则 4：规定一个关系路径中至少包括两个结点。 规则 5：关系路径中的依存关系数量最多为 9 个，即关系路径中包含的词的个数最多为 8 个。这是因为在实验中发现，我们所使用的依存句法分析器对于长距离的词之间的依存关系分析不够准确。另外，对路径的长度进行限定，也可提升系统提取路径的效率。 规则 6：限定关系路径两端的插槽词必须为实词。具体的词性如表 3 所示 。 Table 3 the Part of Speech of Slot Words of Two Ends in Relation Path 表 3 关系路径两端的插槽词的词性 a d m n
28、nd nh ni nl ns nt nz q r v 形容词 副词 数词 普通名词 方位名词 人名 机构名 处所名词 地名 时间词 其他专名 量词 代词 动词 规则 7：不提取与已提取的路径的词顺序相反的路径。这里我们在提取关系路径的时候，与文献 5中的规则不同。 规则 8：仿照规则 1，将分词时疑问词被分开的词进行合并。同时将疑问词的词性标注为 “iw”，我们新 追加的词性，不是词性标注标准中的标准词性。 Fig.6 Combination of Interrogative Words in Dependency Tree 图 6 合并疑问词后的依存树 例如： “中国是在哪一年恢复了在联合国
29、的合法席位？ ”的原始依存分析结果如图 1 所示。该句子中 “哪一胡宝顺 等 :基于句法 结构特征分析及分类技术的答案提取算法 7 年 ”为一个完整的疑问词，但分词时被分开为 “哪 ”、 “一 ”、 “年 ”三个词 ， 且除了这三个词之间的 “内部关系 ”外，只有 “年 ”与其他词有一个 “外部关系 ”，所以可以将这三个词合并，合并后的依存分析结果如图 6 所示。 下面举一个利用我们的 关系路径提取规则提取路径的例子。 例如从问题 “中国是在哪一年恢复了在联合国的合法席位？ ”中提取得到的 关键词之间的 路径为： (1) （中国） ns:SBV:v是 v:VOB:v （恢复） (2) （中国）
30、 ns:SBV:v是 v:VOB:v恢复 v:在 :n （席位） (3) （中国） ns:SBV:v是 v:VOB:v恢复 v:在 :n席位 n:的 :ni （联合国） (4) （中国） ns:SBV:v是 v:VOB:v恢复 v:在 :n席位 n:ATT:a （合法） (5) （恢复） v:在 :n （席位） (6) （恢复） v:在 :n席位 n:的 :ni （联合国） (7) （恢复） v:在 :n席位 n:ATT:a （合法） (8) （联合国） ni:的 :n （席位） (9) （联合国） ni:的 :n席位 n:ATT:a （合法） (10) （合法） a:ATT:n （席位） 疑
31、问词与关键词之间的路径为： (1) （中国） ns:SBV:v是 v:VOB:v恢复 v:ADV:iw （哪一年） (2) （是） v:VOB:v恢复 v:ADV:iw （哪一年） (3) （哪一年） iw:ADV:v （恢复） (4) （哪一年） iw:ADV:v恢复 v:在 :n （席位） (5) （哪一年） iw:ADV:v恢 复 v:在 :n席位 n:的 :ni （联合国） (6) （哪一年） iw:ADV:v恢复 v:在 :n席位 n:ATT:a （合法） 4.3 路径间相似度的计算 这一节将具体介绍如何计算两个路径 间 的相似度。我们首先分别找到路径 各自 所对应的最相似的 “语料
32、路径 ”（ 从文本语料中提取得到的路径），然后 利用文献 8中提出的算法计算路径间的相似度。 计算一对儿路径的相似度计算公式如下： ),(),(),(),( sssqqqsq p I n fps i m Lp I n fp I n fs i m Ip I n fps i m Lpps i m P (1) 其中， pq 与 ps表示 两个 路径。 pInfq表示与 pq最相似的某 个语料路径；类似 地 ， pInfs 表示与 ps 最相似的某个语料路径。 simL(pq, pInfq)表示利用 Lucene 全文检索工具，得到的 pq和 pInfq的相似度；类似 地 ， simL(ps, pIn
33、fs)表示利用 Lucene 全文检索工具，得到的 ps 和 pInfs 的相似度；如果 pq和 pInfq 完全相同 ，那么 simL(pq, pInfq)=1；类似 地 ，如果 ps和 pInfs 完全 相同 ，则 simL(ps, pInfs)=1。 simI(pInfq, pInfs)表示路径 pInfq与 pInfs的相似度。计算方法使用文献 8中 提出的互信息计算方法，我们将在下一节对该计算方法进行概要的阐述 。 这里 simL(pi, pInfi)的计算方法是简单将路径中的依存关系和词看作 “词袋 ”，利用 Lucene 的默认检索算法（向量空间模型算法的一种变形）计算得到的相似
34、度。 这里用上面问题 例子 中 提取得到的路径 “ns:SBV:v是 v:VOB:v”介绍 如何使用 Lucene 全文检索工具检索与该路径最相似的语料路径。 首先，将该路径进行 “分词 ”。即将该路径按照 “”或者 “”进行分词。经过分词后将得到下面的字符串：“ns:SBV:v”、 “是 ”和 “v:VOB:v”。根据这些字符串生成查询关键词为 “ns:SBV:v 是 v:VOB:v”，即将这些被分开的 “词 ”以空格为分隔，在 Lucene 的检索语法中，这些关键词之间是 “或 ”的关系。 然后，利用预先建立好的语料路径字符串的 Lucene 索引检索得到最相似的路径。建立索引时 “分词
35、”方法8 与上面描述的分词方法相同。 4.4 语料路径相似度计算 文献 8提出了一种有效的 “推理规则 ”提取算法。 “推理规则 ”是指两个语义非常相近的路径，在它们出现的上下文中通常可以进行互换。文献 5提出的算法的一个显著优点是可以根据大规模语料自动提取 出句子的路径，并利用互信息来计算路径间的相似度。从而可以得到 “推理规则 ”。因为我们提出的基于依存关系的片段检索方法中使用了该算法计算一对儿路径间相似度，所以下面将对该算法进行简单介绍。 文献 8提取推理规则时，使用了扩展的分布假设（ Extended Distribut ional Hypothesis）。该假设来源于分布假设（ Di
36、stributional Hypothesis），是 Harris 在 1985 提出的 ，其 主要思想为： “倾向于在相同的上下文中出现的词，倾向于具有相似的含义。 ”。对该假设进行扩展后，得到 了文献 8中使用的扩展的分布假设： “如果两个路径倾向于出现在相同的上下文中，那么这两个路径的含义相似。 ”。对于路径来说，它的上下文即路径两端的插槽词。即：如果两个路径倾向于含有越多的相同的插槽词，则这两个路径在语义上就更相似。 为了计算路径之间的相似度， 需要收集 路径的插槽词 的出现频数 。对于一个给定的路径实例 p， 如果 p连接了两个词 w1 和 w2，那么 增加两个三元组 和 的频数。称
37、 ( SlotX, w1 )和 ( SlotY, w2 )是 p 的特征。直觉上，两个路径 共享越多的特征，它们就越相似。 可以利用三元组数据库来统计路径的特征的频数。 下面列出了一个路径三元组数据情况： n:SBV:v有利于 v:VOB:n SlotX： 层次 1 6.52309； 定义 1 5.78463； 方面 1 4.36296； 含量 1 4.95354；环境 2 4.46362； 建筑物 1 5.9377； 局面 1 7.35556； 力 1 5.51887；模式 1 5.5289； 摩擦力 1 8.065； 肉品 1 8.58684； 水流 1 6.58845 SlotY： 产品
38、 1 3.71832； 多样性 1 7.40526； 方面 1 4.16996； 公众 1 7.14094；化学 1 5.47494； 环境 1 3.64685； 角度 2 6.36831； 结构 1 3.59716；金属 1 4.86052； 巨头 1 9.40908； 霉菌 1 8.7318； 体 1 4.72731 上面例子中的第一列数字表示该行的插槽词在该插槽出现的频数。第二列数字表示该插槽与该词的互信息，即该词与该插槽连接的紧密程度。插槽词与对应的插槽的互信息的计算公 式为： )|()|()( ),(lo g),( S l o twPS l o tpPS l o tP wS l o
39、tpPwS l o tpmi (2) 这里 p 表示一个路径， Slot 为 SlotX 或者 SlotY， w 是一个插槽词， P(x)表示概率。在计算时，利用频数来计算相应的概率。 利用 | p, SlotX, w |表示三元组 ( p, SlotX, w )的出现频数； |p, SlotX, *|表示 Ww w,SlotX,p，即路径 p 的 SlotX的所有插槽词的频数和； |*,*,*|表示 wSlotp wSlotp, |,|，即所有路径，所有插槽对应的所有词的频数和。那么一个三元组 ( p, SlotX, w )的互信息可以用下面的公式计算： |,*,|,*,|,*,|,|l o
40、 g|,*,|,*,|,*,|,*,|* , * , *|,*,| |* , * , *|,|l o g),( wS l o tS l o tp S l o twS l o tpS l o twS l o tS l o tS l o tpS l o twS l o tpwS l o tpmi (3) 当三元组数据库创建之后，两个路径之间的相似度就可以用与计算两个词相似度相同的方式进行计算。胡宝顺 等 :基于句法 结构特征分析及分类技术的答案提取算法 9 一对儿插槽 Slot1=(p1,s)和 Slot2=(p2,s)的相似度利用下面的公式进行计算： )s,p(Tw )s,p(Tw)s,p(T)
41、s,p(Tw )w,s,p(mi)w,s,p(mi )w,s,p(mi)w,s,p(mi)S l o t,S l o t(s i m 1 221 21 2121 (4) 这里 p1和 p2表示两个路径， s 表示 一个插槽， T(pi, s)表示路径 pi的 s 插槽词的集合。 两个路径 p1和 p2的相似度利用 SlotX 和 SlotY 相似度的几何平均值来定义： ),(),(),( 212121 S l o t YS l o t Ys i mS l o t XS l o t Xs i mppS (5) 其中， SlotXi或者 SlotYi分别是路径 pi 的两个插槽。 我们 在实验中
42、使用 863 文本语料作为提取路径的语料库，它包含了 3599 个文本文件，大小为 20.4M，使用 上面 4.2 节提出的 更适合汉语特点的路径提取规则，我们从该语料中提取了 13,992,467 个路径（在后续章节 中，我们将这些路径称为 “语料路径 ”）用于计算一对儿路径间的相似度。 5 候选答案的特征提取 、 约简 及分类 5.1 特征约简 特征约简可以理解为，在保证分类或决策能力不变的条件下，删除冗余特征。粗糙集（ Rough Set）理论是一种具有模糊边界的数据挖掘方法，主要用于特征约简、决策规则生成以及预测等方面。著名的 Rosetta（ http:/www.idi.ntnu.n
43、o/aleks/rosetta/） 就是一个基于粗糙集理论框架的表格逻辑数据工具，它提供了多种数据预处理功能如决策表补齐、决策表离散化等及其算法，同时提供了粗 糙集中常见的约简和规则的获取算法，支持从数据预处理到预测和分析规则的全过程，是一个很好的粗糙集理论软件和实验平台。 我们在实验中利用 Rosetta 软件对预想的 32 个特征进行约简， 最后保留了 18 个，保留的特征 将 在 5.2 节详细 介绍。 由于本文用到的特征都是连续型实数，所以 在特征约简前 先要做数据离散化处理，我们选择的离散化算法为 Entropy/MDL， 并选择遗传算法（ Genetic algorithm） 用于
44、 特征 约简。 5.2 候选答案所在句子的特征提取 通常情况下，一个句子可以完整 地 表达 一个 较完整的 事实。 所以我们假设 候选答 案所在的句子的相关特征能够有效 地 反映出 该候选答案是否为正确答案。 特征主要分为数量 类、距离类 、 顺序类 和句法结构类特征 。下面 结合具体例子 详细介绍。 例 ： 自然语言问题为： “中国是在哪一年恢复了在联合国的合法席位？ ”， 查询词为： “中国 恢复 联合国 合法 席位 ”， 得到的文本片断为 （ 查询词用黑体标出，候选答案用黑斜体标出 ） ： 经过分词和词性标注后的结果 为 （ /*表示词性标注）： ： 中国 /ns 是 /v 在 /p 哪
45、 /r 一年 /mq 恢复 /v 了 /u 在 /p 联合国 /nt 的 /u 合法 /v 席位 /n ？ /w ：李肇星 /nr 撰文 /v 纪念 /v 中国 /ns 恢复 /v 联合国 /nt 合法 /v 席位 /n 35 周年 /mq -/w -/w 1971 年 10 月 25 日 /t ， /w 第二十六届 /mq 联合国大会 /nz 以 /p 压倒性 /b 多数 /mq 通过 /p 第 2758号 /mq 决议 /n ， /w 决定 /v 恢复 /v 新 /a 中国 /ns 在 /p 联合国 /nt 的 /u 合法 /v 席位 /n 。 /w 这个 /r 决议 /n 草案 /n 是
46、 /v 由 /p 阿尔巴尼亚 /ns 、 /w 阿尔及利亚 /ns 、 /w 缅甸 /ns 、 /w 锡兰 /ns (/w 今 /n 斯里兰卡 /ns )/w 、 /w 古巴 /ns 、 /w 赤道几内亚 /ns 、 /w 几内亚 /ns 、 /w 伊拉克 /ns 、 /w 马里/ns 、 /w 毛里塔尼亚 /ns 、 /w 尼泊尔 /ns 、 /w 巴基斯坦 /ns 、 /w ./w ：李肇星撰文纪念 中国恢复联合国合法席位 35 周年 - 1971 年 10 月 25 日 ，第二十六届联合国大会以压倒性多数通过第 2758 号决议，决定 恢复 新 中国 在 联合国 的 合法席位 。这个决议
47、草案是由阿尔巴尼亚、阿尔及利亚、缅甸、锡兰 (今斯里兰卡 )、古巴、赤道几内亚、几内亚、伊拉克、马里、毛里塔尼亚、尼泊尔、巴基斯坦、 . 10 此处我们 利用 一些 启发式规则 将连续的时间词以及表示日期范围的词合并 ，因为它们结合在一起才表示一个完整的时间 。例如： “1984 年 4 月 26 日至 5 月 1 日 ”直接分词后的结果为： “1984年 /t 4 月 /t 26 日 /t 至 /p 5月 /t 1 日 /t”， “/t”是时间词的词性标注 、 “/p”表示介词。 经过我们的合并处理后，将得到 “1984年 4 月 26 日至5 月 1 日 /t”。 这个例子所匹配的启发式规
48、则 为 , 其中 表示词性标注向量，m 和 n 表示时间词的个数 ， 合并处理后将得到 “1984年 4 月 26日至 5 月 1 日 /t”。 上面这个例子中，查询关键词的个数为 5；得到的文本片断的句子数为 3（文本片断的标题也当作一个句子）；问题类型为时间类型，该类型对应的答案应为 表示 时间 的词 。在上述例子中只有 “1971 年 10 月 25 日 ”的词性符合要求， 即 候选答案词只有一个，提取的特征为第二个句子所含有的特征。 5.2.1 数量 类 特征 数量类特征包括： (1) 句子中 匹配词的个数 占 查询词个数 的 比例 。 该特征反映该候选答案所在 的 句子与问题在词汇匹配层面的相似度 。 针对上面的例子，句子中出
