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

1大纲介绍（Introduction)推理框架(InferenceFramework)在压缩句法森林的有效推理

(EfficientInferenceoverCompactParseForests)实践评价(EmpiricalEvaluation)相关工作(RelatedWork)结论(Conclusion)第1页/共39页第一页，共40页。2介绍（Introduction)引入原因：最近的大量研究：通过可应用的推理知识得到的知识及其应用。通过这些知识从而获取蕴含规则（应用在句法表示）。在这些规则上进行有效的推理成为最基本的问题。作者从蕴含规则应用的形式上出发，提出一种新的数据结构和算法。

第2页/共39页第二页，共40页。3几个概念：Entailmentrules—Theyareruleswherethelefthandside(LHS)specifiessomeknowledgewhichentailstheknowledgeexpresendintheRHSoftherule,withsomedegreeofconfidence.Example:Childrenarefondofcandies.Entailmentrules:childrenkids、candiessweets、XisfondofYXlikesY

第3页/共39页第三页，共40页。4TextualEntailment–IthasbeenproposedrecentlyasagenericframeworkformodelingsemanticvariabilityinmanyNLPapplication,suchasQuestionAnswering,InformationExtraction,InformationRetrivalandDocument.参考：《BuildingaLarge-ScaleRepositoryofTextualEntailmentRules》第4页/共39页第四页，共40页。5可应用语义推理的关注点：从文本中获取目标意思。文本蕴含框架(textualentailmentframework)

减少从源文本中获取文本意思的推理过程。传统的做法：传统形式的语义方法完成从源文本中获取逻辑形式上的推理。第5页/共39页第五页，共40页。6NLP实践应用方面：在NLP方面，相比而言应用较浅，如：语法树(parsetrees)；还可能应用在：有限的语义信息方面，如：命名实体、语义规则等。通常的应用领域

推理的产生：在树和图上应用一些转换或替代方法去表示文本。---这种过程也被认为是：entailment(inference)rules.

作用：1)获取意译(paraphrases)、同义词(synonyms)、下位词(hyponyms)、句法变换等等。

2)人工手动产生。如：WordNet、自动学习。

第6页/共39页第六页，共40页。7前期的工作learningparaphrasesandentailmentrulesLinandPantel,2001Shinyamaetal.,2002Szpektoretal.,2004BhagatandRavichandran,2008identifyingappropriatecontextsfortheirapplication(Panteletal.,2007)andutilizingthemforinference(deSalvoBrazetal.,2005;Bar-Haimetal.,2007).第7页/共39页第七页，共40页。8性能分析：当前基于规则的应用仍然具有噪音和不完整性。但是，对于文本理解应用方面有越来越多的价值。比如：1)问答系统的知识和推理

2)RTE-5(theplannedevaluationofknowledgeresourcesintheforthcoming5-thRecognizingTextualEntailmentchallenge)第8页/共39页第八页，共40页。9许多可应用系统通过在一些推理规则上利用语义知识，有如下特点：有限性、特定的应用领域、启发性。正规化这些做法对于应用语义推理研究似乎有重要作用，类似的对于句法和机器翻译方面，形成良成好的模型也有重要作用。比如：Bar-Haimetal.(2007)在句法树上介绍了一种通用的形式用于语义推理。过程：这种形式使用蕴含规则为各种各样的推理知识生成一个统一的表达方式，同样也允许统一推理。第9页/共39页第九页，共40页。10分析：

规则应用是清晰的、直观的表明了产生一个句子分析以及源文本句子的语义需求。接下来的推理需要更多的规则应用等等，在实践中，每个结果将会明确地生成一棵单独的树。

第10页/共39页第十页，共40页。11举例：Childrenarefondofcandies.entailmentrules:childrenkids、candiessweets、XisfondofYXlikesY

则推导出来的句子将有：2^3(棵).实践中发现这种可扩展性比较差的。直观地更趋向于在一大堆的句子表示中，为每个规则应用(ruleapplication)加入蕴含部分(entailedpart),比如：kids第11页/共39页第十一页，共40页。12所以：需要构造一个theresultingstructure去表示一个蕴含句子集(entailedsentences)，而不是一大堆的语义不清晰的句子片段。作者在先前的工作当中仅仅给出了部分解决方案，在这篇论文里提出了一种新的数据结构，作者称为压缩森林(compactforest),并给出了一种相应的推理算法，这种算法在保持每个独立部分的特性上，能够有效地产生和表示所有的结果。作者提到：灵感源于先前的工作，如：句法分析，生成(generation)以及机器翻译。第12页/共39页第十二页，共40页。13推理框架(InferenceFramework)主要简单介绍“树转换推理形式”。源于：Bar-Haimetal.(2007).

主要过程：提供一篇源文本、语法解析(syntacticallyparsed)、以及一个用于表示树转换的蕴含规则集(asetofentailmentrules)，形式(formalism)定义成：由使用规则的文本所转换的结果集合。每个结果是通过一系列的规则应用的序列，每个生成式是一棵中间解析树(anintermediateparsetree),类似于logic的证明过程。第13页/共39页第十三页，共40页。14具体指：每个句子由一颗依存树(dependencytrees)表示，在这颗依存树上，结点由词目(lemma)和词性表示(part-of-speech),边集是由依存关系表示。例：LR：它主要是由二个模板组成，分别命名为：left-hand-side(L)和right-hand-side(R)

每个模板全是依存子树(dependencysubtree)，依存子树可能包含词性标记变量(POS-taggedvariables),同时匹配任何一个词目(lemma)第14页/共39页第十四页，共40页。15例子(被动到主动的转换规则)第15页/共39页第十五页，共40页。16例子(被动到主动的转换规则的应用)第16页/共39页第十六页，共40页。17如何产生派生树(aderivedtree)如何从一个文本中应用规则应用产生一棵派生树。具体步骤如下：

1)L的匹配（Lmatching）2)R的实例化(Rinstantiation)3)产生导出树(Derivedtreegeneration)第17页/共39页第十七页，共40页。181)L匹配(Lmatching)变量V匹配动词see,N1匹配名词Mary,N2匹配名词John第18页/共39页第十八页，共40页。192)R实例化(Rinstantiation)–part1原理：R复本的产生以及变量的初始化是根据他们在左端的匹配结点而言的。另外：一个规则可能是指定的对齐，定义为从左结点到右结点。故：一个对齐表明，对于源文本中的每一个修饰语m并不是规则结构的一部分。在m中的子树应该作为目标结点的修饰部分。为了定义明确的对齐，在L中的每一个变量隐含对应R的相对应的部分。第19页/共39页第十九页，共40页。202)R实例化(Rinstantiation)–part2动词V的对齐表明：修饰see的yesterday应该复制生成句子。而修饰Mary的beautiful复制到N1第20页/共39页第二十页，共40页。213)产生导出树(Derivedtreegeneration)两种方法：

1）substitutionrules

如：buypurchase2)introductionrules

第21页/共39页第二十一页，共40页。223、在压缩句法森林的有效推理1)压缩森林的数据结构2)推理过程

(1)森林的初始化

(2)规则应用

a)L匹配b)产生导出树

c)变量的初始化

d)对齐共享

e)双叶子变量的对齐共享第22页/共39页第二十二页，共40页。233-2-1森林初始化(黑色部分)第23页/共39页第二十三页，共40页。243-2-2(b)L匹配给出一组压缩表示：{Children/kids}arefondof{candies/swets}

规则:XisfondofYXlikesY故仅匹配：1次而不是4次第24页/共39页第二十四页，共40页。253-2-2(c)产生导出树两种方法：

1）substitutionrules

如：buypurchase2)introductionrules第25页/共39页第二十五页，共40页。263-2-2(d)变量实例化依存树中，动词变量V实例化为:see第26页/共39页第二十六页，共40页。273-2-2(c)对齐共享(Alignmentsharing)关系：如：右图依存树中的yesterday第27页/共39页第二十七页，共40页。283-2-2(d)双重叶子变量共享

(Dualleafvariablesharing)如：子树

beautifulMary和John分别被变量N1和N2共享第28页/共39页第二十八页，共40页。293.3正确性(Correctness)第29页/共39页第二十九页，共40页。303.4复杂性(Complexity)详细解释了为什么压缩森林会减少时间和空间的复杂度。举例：单棵树Ｔ，拥有Ｋ条独立的规则一般情况：时间和空间复杂度为----压缩森林：空间复杂度----

时间复杂度---(其中：Ｆ是森林,r为规则)第30页/共39页第三十页，共40页。314实践评价

4.1Compactvs.ExplicitInference第31页/共39页第三十一页，共40页。324实践评价

4.2RTS系统上的应用(theBar-IlanRTEsystem)第32页/共39页第三十二页，共40页。334实践评价

4.2RTS系统上的应用(theBar-IlanRTEsystem)第33页/共39页第三十三页，共40页。34