730-在压缩句法森林的有效推理

1、1a compact forest for scalable inference over entailment and paraphrase rulesroy bar-haim, jonathan berant, ido dagan 2009 acl and afnlp speaker: guanghui luo2大纲大纲l介绍（介绍（introduction)l推理框架(inference framework)l在压缩句法森林的有效推理 (efficient inference over compact parse forests)l实践评价(empirical evaluation)l相

2、关工作(related work)l结论(conclusion)3介绍（introduction)引入原因： 最近的大量研究：通过可应用的推理知识得到的知识及其应用。 通过这些知识从而获取蕴含规则（应用在句法表示）。 在这些规则上进行有效的推理成为最基本的问题。 作者从蕴含规则应用的形式上出发，提出一种新的数据结构和算法。 4几个概念：lentailment rulesthey are rules where the left hand side(lhs) specifies some knowledge which entails the knowledge expresend in the

3、 rhs of the rule, with some degree of confidence.lexample: children are fond of candies.lentailment rules: childrenkids、candiessweets、x is fond of y x likes y 5ltextual entailment it has been proposed recently as a generic framework for modeling semantic variability in many nlp application, such as

4、question answering, information extraction, information retrival and document.l参考：building a large-scale repository of textual entailment rules6l可应用语义推理的关注点：从文本中获取目标意思。l文本蕴含框架(textual entailment framework) 减少从源文本中获取文本意思的推理过程。l传统的做法： 传统形式的语义方法完成从源文本中获取逻辑形式上的推理。7lnlp实践应用方面：在nlp方面，相比而言应用较浅，如：语法树(parse

5、trees)；还可能应用在：有限的语义信息方面，如：命名实体、语义规则等。l通常的应用领域 推理的产生：在树和图上应用一些转换或替代方法去表示文本。-这种过程也被认为是：entailment (inference) rules. 作用：1)获取意译(paraphrases)、同义词(synonyms)、下位词(hyponyms)、句法变换等等。 2)人工手动产生。如：wordnet、自动学习。 8前期的工作前期的工作llearning paraphrases and entailment rules lin and pantel, 2001 shinyama et al., 2002 szpe

6、ktor et al., 2004 bhagat and ravichandran,2008l identifying appropriate contexts for their application (pantel et al., 2007) and utilizing them for inference (de salvo braz et al., 2005; bar-haim et al., 2007).9l性能分析： 当前基于规则的应用仍然具有噪音和不完整性。 但是，对于文本理解应用方面有越来越多的价值。 比如：1)问答系统的知识和推理 2)rte-5( the planned

7、evaluation of knowledge resources in the forthcoming 5-th recognizing textual entailment challenge)10l许多可应用系统通过在一些推理规则上利用语义知识，有如下特点：有限性、特定的应用领域、启发性。l正规化这些做法对于应用语义推理研究似乎有重要作用，类似的对于句法和机器翻译方面，形成良成好的模型也有重要作用。 比如：bar-haimet al. (2007) 在句法树上介绍了一种通用的形式用于语义推理。 过程：这种形式使用蕴含规则为各种各样的推理知识生成一个统一的表达方式，同样也允许统一推理。11

8、l分析： 规则应用是清晰的、直观的表明了产生一个句子分析以及源文本句子的语义需求。 接下来的推理需要更多的规则应用等等，在实践中，每个结果将会明确地生成一棵单独的树。 12l举例：children are fond of candies. entailment rules:childrenkids、 candiessweets、 x is fond of yx likes y 则推导出来的句子将有：23(棵).实践中发现这种可扩展性比较差的。 直观地更趋向于在一大堆的句子表示中，为每个规则应用(rule application)加入蕴含部分(entailed part),比如：kids13所以

9、：需要构造一个 the resulting structure 去表示一个蕴含句子集(entailed sentences)，而不是一大堆的语义不清晰的句子片段。 作者在先前的工作当中仅仅给出了部分解决方案，在这篇论文里提出了一种新的数据结构，作者称为 压缩森林(compact forest),并给出了一种相应的推理算法，这种算法在保持每个独立部分的特性上，能够有效地产生和表示所有的结果。 作者提到：灵感源于先前的工作，如：句法分析，生成(generation)以及机器翻译。14推理框架推理框架(inference framework)主要简单介绍“树转换推理形式”。源于：bar-haim e

10、t al. (2007). 主要过程：提供一篇源文本、语法解析(syntactically parsed)、以及一个用于表示树转换的蕴含规则集(a set of entailment rules)，形式(formalism)定义成：由使用规则的文本所转换的结果集合。每个结果是通过一系列的规则应用的序列，每个生成式是一棵中间解析树(an intermediate parse tree),类似于 logic的证明过程。15l具体指：具体指： 每个句子由一颗依存树每个句子由一颗依存树(dependency trees)表示，表示，在这颗依存树上，结点由词目在这颗依存树上，结点由词目(lemma)和词

11、性表示和词性表示(part-of-speech), 边集是由依存关系表示。边集是由依存关系表示。 例：例：lr：它主要是由二个模板组成，分别命：它主要是由二个模板组成，分别命名为：名为：left-hand-side(l) 和和 right-hand-side(r) 每个模板全是依存子树每个模板全是依存子树(dependency subtree)，依存子树可能包含词性标记变量依存子树可能包含词性标记变量(pos-tagged variables), 同时匹配任何一个词目同时匹配任何一个词目(lemma)16l例子例子(被动到主动的转换规则被动到主动的转换规则)17l例子例子(被动到主动的转换规则

12、的应用被动到主动的转换规则的应用)18如何产生派生树如何产生派生树(a derived tree)l如何从一个文本中应用规则应用产生一棵派生树。具体步骤如下： 1)l的匹配（l matching） 2)r的实例化(r instantiation) 3)产生导出树(derived tree generation)191) l 匹配匹配(l matching)变量变量v匹配动词匹配动词see,n1匹配名词匹配名词mary,n2匹配名词匹配名词john202) r实例化实例化(r instantiation) part 1原理：原理：r复本的产生以及变量的初始化是根据他们在左端的匹复本的产生以及变量

13、的初始化是根据他们在左端的匹配结点而言的。另外：一个规则可能是指定的对齐，定义为从配结点而言的。另外：一个规则可能是指定的对齐，定义为从左结点到右结点。左结点到右结点。 故：一个对齐表明，对于源文本中的每一个修饰语故：一个对齐表明，对于源文本中的每一个修饰语m 并并不是规则结构的一部分。在不是规则结构的一部分。在m中的子树应该作为目标结点的修中的子树应该作为目标结点的修饰部分。为了定义明确的对齐，在饰部分。为了定义明确的对齐，在l中的每一个变量隐含对应中的每一个变量隐含对应r的相对应的部分。的相对应的部分。212) r实例化实例化(r instantiation) part 2动词动词v的对齐

14、表明：修饰的对齐表明：修饰see的的yesterday应该复制生成句子。应该复制生成句子。而修饰而修饰mary的的beautiful复制到复制到n1223)产生导出树产生导出树(derived tree generation)两种方法：两种方法： 1）substitution rules 如：如：buy purchase 2) introduction rules 233、在压缩句法森林的有效推理在压缩句法森林的有效推理1)压缩森林的数据结构压缩森林的数据结构2)推理过程推理过程 (1)森林的初始化森林的初始化 (2)规则应用规则应用 a) l 匹配匹配 b)产生导出树产生导出树 c)变量的初

15、始化变量的初始化 d)对齐共享对齐共享 e)双叶子变量的对齐共享双叶子变量的对齐共享243-2-1 森林初始化森林初始化(黑色部分黑色部分)253-2-2(b) l 匹配匹配给出一组压缩表示：给出一组压缩表示：children/kids are fond of candies/swets 规则规则:x is fond of y x likes y故仅匹配：故仅匹配：1次次 而不是而不是4次次263-2-2(c) 产生导出树产生导出树两种方法：两种方法： 1）substitution rules 如：如：buy purchase 2) introduction rules273-2-2(d) 变

16、量实例化变量实例化依存树中，动词变量依存树中，动词变量v实例化为实例化为:see283-2-2(c) 对齐共享对齐共享(alignment sharing)关系：关系：如：右图依存树中如：右图依存树中的的 yesterday293-2-2(d) 双重叶子变量共享双重叶子变量共享 (dual leaf variable sharing)如：子树如：子树 beautiful mary和和 john 分别被变量分别被变量n1 和和 n2 共享共享303.3 正确性正确性(correctness)313.4 复杂性复杂性(complexity)详细解释了为什么压缩森林会减少时间和空间的详细解释了为什么

17、压缩森林会减少时间和空间的复杂度。复杂度。 举例：单棵树，拥有条独立的规则举例：单棵树，拥有条独立的规则一般情况：时间和空间复杂度为一般情况：时间和空间复杂度为-压缩森林：空间复杂度压缩森林：空间复杂度- 时间复杂度时间复杂度- (其中：是森林其中：是森林, r为规则为规则)324 实践评价实践评价4.1 compact vs. explicit inference334 实践评价实践评价4.2 rts 系统上的应用系统上的应用(the bar-ilan rte system)344 实践评价实践评价4.2 rts 系统上的应用系统上的应用(the bar-ilan rte system)354 实践评价实践评价4.2 rts 系统上的应用系统上的应用(the bar-ilan rte system)364 实践评价实践评价4.2 rts 系统上的应用系统上的应用(the bar-ilan rte system)375 相关工作相关工作主要介绍的是：在主要介绍的是：在rte 系统上应用基于知识转系统上