自然语言理解形式化句法课件.ppt

自然语言理解形式化句法第1页，此课件共64页哦形式化语法理论Grammar Formalism上海交通大学陈玉泉第2页，此课件共64页哦内容提要n概述（语法和语言）n乔姆斯基（Chomsky）语法理论n基于合一（Unification）的语法理论n其它一些的语法理论（不基于上下文无关文法）第3页，此课件共64页哦一、概述第4页，此课件共64页哦什么是语法？nA mathematic systemnDefine a languagenGive syntax(structure)to a sentence(string)第5页，此课件共64页哦人工语言及其语法n基于符号n无歧义或简单歧义n高效第6页，此课件共64页哦从可计算角度分类n0,1,2,3Unrestricted GrammarTuring Machine？Context Sensitive GrammarTuring Machine？Context Free GrammarPushdown AutomatonO(n3)Regular ExpressionFinite State AutomatonO(n)第7页，此课件共64页哦自然语言及其语法n复杂n歧义n多样第8页，此课件共64页哦形式化语法理论的目标n判断一句句子是否合法n给出该句子唯一合法的结构n给出该句子中各成分（词）之间的关系第9页，此课件共64页哦形式化语法理论应具备的特性nlinguistically adequaten准确描述自然语言nexpressiven对语言世界用数学方法描述ncomputational effectiven可计算，并且高效第10页，此课件共64页哦主要流派n乔姆斯基语法理论n基于合一的语法理论n其它（不基于上下文无关文法）第11页，此课件共64页哦二、乔姆斯基语法理论第12页，此课件共64页哦Noam ChomskynAmerican linguist,writer,teacher,and political activist nPublicationsnSyntactic StructuresnAspects of the Theory of Syntax nAmerican Power and the New Mandarins n Peace in the Middle East n Lectures on Government and Binding nThe Fateful Triangle n Deterring Democracy nThe Minimalist Program第13页，此课件共64页哦发展过程n转换生成语法（1957）nSyntactic Structure.The Hague:Moutong&Co.n管辖与约束理论（1981）nLectures on Government and Binding.Foris,Dordrechtn最简方案（1992）nA Minimalist Program for Linguistics Theory,MIT Occasional Papers in Linguistics,#1第14页，此课件共64页哦GB之前SurfaceStructureDeepStructureRules&LexiconTransfor-mationsSemanticInterpretationUtterance第15页，此课件共64页哦GB之后SurfaceStructureDeepStructureRules&LexiconLogical FormPhonologicalFormmove a aX-Bar-SyntaxSubcategorizationSelectional RestrictionsCase Theoryq-CriterionBinding Principle第16页，此课件共64页哦短语结构phrasal structuren句子的结构是层次化的（hierarchical）nTreen范畴（Category）nCommon categorial membership is evidenced by intersubstitutivityn中心词（Head of a phrase）n决定短语行为的词nRecursiven某个类型可以包含在它自身中第17页，此课件共64页哦Intersubsitutivity and headLondon,the woman,the old man,the proud young child-is known to methe proud young childthe proud childthe young child -child is the head第18页，此课件共64页哦X-Bar理论nVP V nVP V NPnVP AD VnVP V PPnX-BarnX2 X1nX1 X0 nN 的complements是形容词，specifier 是冠词nV 的complements是宾语，specifier 是主语n这样，V0表示单个动词，V1 表示动词结构，V2表示句子n01,12第19页，此课件共64页哦X-Bar理论（cont.）V1V1V0likeshis visitthis weekin ShanghaiN2N2P2V1第20页，此课件共64页哦题元理论q-Criterion n题元理论研究各词项之间的题元关系，即传统语，即传统语法中用施事、受事、工具等术语表示的概念范畴题元理论以动词为中心，认为每一个题元角色都是由动词分配的。nagent:john reads a bookninstrument:the key opens the doornlocation:the book contains good ideasn句中的每一个成分都必须有一个题元角色（coherence），同时，中心动词的所有题元角色都已被分配（completeness）。第21页，此课件共64页哦格理论（Case Theory）n与语言相关。n一般地，动词，介词赋格，名词N2接受格nX0 向 N2赋格第22页，此课件共64页哦管辖GovernmentnC-Command:a c-commands b(a b)iffnevery branching node g,which dominates a,also dominates bna does not dominate bnExample:nY c-commands Z,C,D,EnZ c-commands A,BnA c-commands BnB c-commands AnC c-commands D,EXEDCBAZY第23页，此课件共64页哦管辖GovernmentnM-Command:x m-command y iff neither of x and y dominates the other,and every maximal projection that dominates x also dominates y.nN0 dose not c-commands Detnbut m-commands DetXN0N1DetBAN2Y第24页，此课件共64页哦管辖GovernmentnGovernment:nx governs y iffnx=X0nx m-commands y,and if ex.z m-commands y,z m-command x or y m-command z.nHead always govern their complements and specifiers.n动词管辖主语和宾语，但主语不管辖宾语第25页，此课件共64页哦约束理论Binding Principlen解决问题：n指称关系nComplete Functional Complex(CFC):nA constituent a is a CFC,if it is complete and coherent(q-criterion)n原则n照应词在CFC内受约束，即它的先行词必定在CFC内。n代名词在CFC内是自由的。n指称词总是自由的。n其中，n照应词：包括反身代词myself，yourself，相互代词each other等。n代名词：指传统语法中的人称代词，如he,him等。n指称词：就是通常所说的名词短语，如the man，john等。第26页，此课件共64页哦约束理论Binding PrinciplenJohn wants Tom to criticize himself.nhimself 只能是Tom，不可能是Johnn原则一nJohn wants Tom to criticize him.nhim 不能是Tom，但可能是Johnn原则二第27页，此课件共64页哦TransformationnSentencenWhat did you give to John?nD-Structure:n?you Tense give what to JohnnS-StructurenWhati do+Tensej you tj give ti to John第28页，此课件共64页哦转换类型nPassivizationnsurface structure:the book is given to linda by janndeep structure:jan gives the book to lindanAgent-Deletionnsurface structure:the book is given to lindandeep structure:someone gives the book to lindanEqui-NP-Deletionnsurface structure:jan promises linda to comendeep structure:jan promises linda that jan comes第29页，此课件共64页哦转换类型nRaisingnsurface structure:jan seems to comendeep structure:(it)seems that jan comesnAnaphorsnsurface structure:jani washes himselfindeep structure:jan washes jannQuestion-Formationnsurface structure:what does jan read?ndeep structure:?jan reads whatnImperatives(Agent-Deletion)nsurface structure:give the toy to herndeep structure:somone gives the toy to her第30页，此课件共64页哦转换动作nSubstitutionnDisplace and elementnAdjunctionnY XnY Xi Y tinExample:nS NP the boy VP v broke NP the windownThe boy broke the window.nThe window was broken(t)by the boy.nMovements:nReplacing subject NP by object;nPostposing the subjuct,add bynIntroduce new tense第31页，此课件共64页哦三、基于合一的语法第32页，此课件共64页哦基于合一的语法n功能合一语法 FUGn广义短语结构语法 GPSGn中心词驱动短语结构语法 HPSGn词汇功能语法 LFGn共同特点：引入特征和特征的合一第33页，此课件共64页哦特征结构n特征：属性：值n特征结构：特征的集合，其中任何两个属性不能相同n一个特征结构的例子：Num :pl|sgPer :3第34页，此课件共64页哦复杂特征集n嵌套的特征结构（nest），允许重入（reentrance）Cat:vSub:Cat:rLex:heNum:sgCat:vPer:3(1)Sub:Cat:rPer:(1)Lex:he第35页，此课件共64页哦复杂特征集的图形表示nDAG3hervperpercatcatlexsub第36页，此课件共64页哦合一n合一是定义在两个特征结构之间的一种操作n合一成功：则原来的两个独立的特征结构成为同一个特征结构n合一失败：不产生新的特征第37页，此课件共64页哦合一（cont）n合一运算可递归定义为:n如果a、b都是原子值，若a和b相等，则ab=a，否则a、b合一失败n如果a、b均为特征结构，则对于a、b中的每一个特征f：n若f(a)=v，但f(b)的值未经定义，则属于abn若f(b)=v，但f(a)的值未经定义，则属于abn若f(a)=v1，f(b)=v2，v1和v2相容，则属于ab，如果v1和v2不相容，则合一失败n*相容（consistent）针对两个特征结构而言，指存在另一个特征结构，同时包含(subsume)这两个结构:n包含:D1 D2 f dom(D1):f(D1)f(D2)&(p,q dom(D1)*:p(D1)=q(D1)p(D2)=q(D2)第38页，此课件共64页哦合一的算法描述nD1,D2 and D are considered as setsnD:=;while(D1!=)D1:=D1/(f=v);if(f dom(D2)D2:=D2/(f=v);D:=D f=v v;else D:=D f=v;D:=D D2;第39页，此课件共64页哦合一的例子Cat:vNum:sgCat:vNum:sgPer:3Cat:vNum:sgPer:3第40页，此课件共64页哦合一的例子（cont）Cat:vNum:sgCat:vNum:plPer:3第41页，此课件共64页哦合一的特性n交换率n结合率第42页，此课件共64页哦LFGn词汇功能语法（Lexical Functional Grammar）nRonald M.Kaplan,Joan BresnanLexical Functional Grammar-A Formal System for Grammatical Representationin:Joan Bresnan(ed.),The Mental Representa-tion of Grammatical Relations,MIT Press,Cambridge(MA)1982第43页，此课件共64页哦表示层次nLexical StructurenC-structure(Constituent Structure)nF-structure(Functional Structure)第44页，此课件共64页哦Lexical Structurenthe:Det,(spec)=def(per)=3nman:N,(pred)=man(per)=3(num)=sgnreads:V,(pred)=read(subj,obj)(subj per)=3(subj num)=sgna:Det,(spec)=indef(num)=sgnbook:N,(pred)=book(per)=3(num)=sg第45页，此课件共64页哦C-structure and F-structureSNPmanNVPDettheVNPbookNDetareadssubjpredread(subj,obj)objspecdefper3numsgpredmanspecdefper3numsgpredbook第46页，此课件共64页哦如何计算?n词典+上下文无关规则+f描述nS NP(subj)=VP =nVP V=NP(obj)=nNP Det =N =指父节点，指当前节点第47页，此课件共64页哦例子n演示 the man reads a book*the man read a book第48页，此课件共64页哦Coherence&CompletenessnPA-StructurenCoherence:任何有意义的语义结构都必须在PA-Structure 中出现nCompleteness:PA-Structure 中出现的值都必须有与其对应的语义结构第49页，此课件共64页哦PP Attachmentsubjpredgive(subj,obj,to obj)objto specdefper3numsgpredmanspecdefper3numsgpredbookpreptoobjspecdefper3numsgpredwomansubjpredsee(subj,obj)objwith specdefper3numsgpredwomanspecdefper3numsgpredmanprepwithobjspecdefper3numsgpredteles.The man gives the book to the woman.the woman sees the man with the telescope第50页，此课件共64页哦FUGnFunctional Unification Grammarn功能合一语法nMartin Kay,1979,Functional Grammar,InProceedings of the 4th Annual Meeting of theBerkeley Linguistics Society.nMartin Kay,1985,Parsing in Functional Grammar,In D.Dowty,L.Karttunen,and A.Zwicky eds,Natural Language Parsing,Cambridge University Press,Cambridge,1985.第51页，此课件共64页哦GPSGnGeneralized Phrase Structure Grammarn广义短语结构语法nGerald Gazdar,Ewan Klein,Geoffrey Pullum,Ivan Sag Generalized Phrase Structure GrammarBasil Blackwell,Oxford 1985第52页，此课件共64页哦HPSGnHead-Driven Phrase Structure Grammarn中心词驱动短语结构语法nPollard,Carl and Ivag A.Sag.1987.Information Based Syntax and Semantics.CSLI Lecture Notes,No.13,The University of Chicago Press,Chicago.nPollard,Carl and Ivag A.Sag.1994.Head-Driven Phrase Structure Grammar.The University of Chicago Press,Chicago.第53页，此课件共64页哦四、其它语法（非CFG）第54页，此课件共64页哦TAGnTree Adjoining Grammarn树粘接语法nA.Joshi,L.Levy,&M.Takahashi,1975,Tree Adjunct Grammar,Journal of Computer&System Science,1975,10(1):pp136-163.第55页，此课件共64页哦TAG(cont.)n初始树n辅助树n替换n粘接第56页，此课件共64页哦TAG(cont.)第57页，此课件共64页哦TAG替换第58页，此课件共64页哦TAG粘接第59页，此课件共64页哦TAG的可计算性nCFG TAG CSGnO(n6)第60页，此课件共64页哦链语法 nDaniel Sleator and Davy Temperley,Parsing English with a Link Grammar,Carnegie Mellon University Computer Science technical report CMU-CS-91-196,October 1991.nhttp:/www.link.cs.cmu.edu/link/第61页，此课件共64页哦链语法第62页，此课件共64页哦链语法 链接失败第63页，此课件共64页哦Thank you!第64页，此课件共64页哦