《机器翻译理论和技术.ppt》由会员分享，可在线阅读，更多相关《机器翻译理论和技术.ppt（126页珍藏版）》请在三一办公上搜索。
1、机器翻译理论和技术,主要内容,机器翻译概述机器翻译的历史机器翻译与自然语言处理机器翻译所涉及的学科机器翻译基本策略和实现方法机器翻译的难点机器翻译的现状,传统的（基于规则）机器翻译方法（理性方法）词法分析词性标注分词（汉语、日语）句法分析基于CFG（上下文无关文法）的句法表示及其分析技术基于扩充的CFG（复杂特征集、合一运算）的句法表示及其分析技术语义分析词义及句义表示基于格语法的句义分析转换、生成技术,主要内容（续1）,基于语料库的机器翻译方法（经验方法）基于统计的机器翻译方法语言模型（N元文法）HMM模型与词性标注PCFG文法与句法分析统计机器翻译模型（SMT）基于实例的机器翻译方法基于混
2、合策略的机器翻译方法,主要内容（续2）,所需的前导知识,形式语言与自动机编译技术概率与统计,参考书籍,赵铁军等，机器翻译原理，哈尔滨工业大学出版社，2000刘群等译，自然语言理解（第二版），电子工业出版社，2005苑春法等译，统计自然语言处理基础，电子工业出版社，2005冯志伟等译，自然语言处理综论，电子工业出版社，2005范明等译，统计学习基础-数据挖掘、推理与预测，电子工业出版社，2004王小捷等，自然语言处理技术基础，北京邮电大学出版社,2002刘颖，计算语言学，清华大学出版社，2002姚天顺，自然语言理解一种让机器懂得人类语言的研究（第2版），清华大学出版社，2002黄昌宁等，语料库语
3、言学，商务印书馆，2002冯志伟，计算语言学基础，商务印书馆，2001余士文，计算语言学概论，商务印书馆，2003,Bonnie J.Dorr,et al,Survey of Current Paradigms in Machine Translation，Technical Report LAMP-TR-027,Language and Media Processing Lab,University of Maryland.Hutchins WJ,Machine Translation:Past,Present,Future.Chichester:Ellis Horwood,1986Artu
4、ro Trujillo,Translation Engines:Techniques for Machine Translation,Springer-Verlag London Limited 1999Peter F.Brown,et al.,A Statistical Approach to MT,Computational Linguistics,1990,16(2)P.F.Brown,et al.,The Mathematics of Statistical Machine Translation:Parameter Estimation,Computational Linguisti
5、cs,1993,19(2),Makoto Nagao,A Framework of a Mechanical Translation between Japanese and English by Analog Principle,In A.Elithorn and R.Banerji(Eds.),Artificial and Human Intelligence.NATO Publications,1984James Allen,Natural Language Understanding,The Benjamin/Cummings Publishing Company,Inc.1987Ch
6、ristopher D.Manning&Hinrich Schutze,Foundations of Statistical Natural Langugae Processing,Massachusetts Institute of Technology,1999Daniel Jurafsky&James H.Martin,Speech and Language Processing,Prentice-Hall,2000Trevor Hastie,et al.,The Elements of Statistical Learning-Data Mining,Inference,and Pre
7、diction,Springer-Verlag,New York,2001,课程考核,Projects提交要求（每个project）报告（说明基本做法）源程序及可运行的程序,机器翻译概述,机器翻译（Machine Translation，简称MT）是指利用计算机实现自然语言（英语、汉语等）之间的自动翻译。文本机器翻译语音机器翻译机器辅助翻译（Machine Aided Translation或Computer Aided Translation，简称MAT或CAT）翻译记忆体（Translation Memory，简称TM）双语对照的文本编辑.,机器翻译历史,1947，Warren Weave
8、rs memo1954，第一个公开展示的俄英MT原型系统1966，美国科学院的ALPAC报告宣告机器翻译走入低谷1970s，Systran（1970），Meteo（1976），Early 1980s，复苏，Eurotra，MuLate 1980searly 1990s，商品化系统投入市场，语音翻译，统计机器翻译Late 1990s，Internet，MAT，EBMT,I have a text in front of me which is written in Russian but I am going to pretend that it is really written in Eng
9、lish and that it has been coded in some strange symbols.All I need do is strip off the code in order to retrieve the information contained in the text,机器翻译与自然语言处理,自然语言处理（NLP）是指用计算机对语言信息进行处理的方法和技术。与NLP相近的两个研究领域：自然语言理解(NLU)：强调对语言含义和意图的深层次解释计算语言学(CL)：强调可计算的语言理论,NLP技术的应用,机器翻译自动摘要文本分类信息检索信息抽取自动问答情感分析.,自动
10、摘要（Text Summarization）,利用计算机自动地从原始文档中提取全面准确地反映该文档中心内容的简单连贯的短文。压缩比,文本分类（Text Classification）,利用计算机将一篇文章归于预先给定的某一类或某几类的过程。文本表示相似度计算可用于信息过滤（Information Filtering）,信息检索（Information Retrieval，IR）,主题相关的文本获取。google、百度、.（基于关键词的）倒排文档,信息抽取（Information Extraction，IE）,主题相关的信息获取信息抽取是指从非结构化或半结构化的自然语言文本中提取出与某个主题相关
11、的结构化信息。IE对数据挖掘的支持,新华社北京月日电（记者李术峰）:中国农工民主党第十二届中央常务委员会第一次会议今天在北京召开。会议研究通过了贯彻落实“两会”精神的有关决定，审议通过了中国农工民主党中央年工作要点（草案），并任命了中央副秘书长。农工民主党中央主席蒋正华主持了会议，他说，农工民主党有多名党员作为代表和委员参加了今年的“两会”，各位党员要认真履行代表和委员的职责，开好会，在年的工作中认真贯彻“两会”精神，加强农工民主党的自身建设，推动事业进一步发展，为建设有中国特色社会主义事业作出新的贡献。会前，农工民主党中央邀请参加“两会”的来自全国各省、自治区、直辖市的农工民主党党员进行了联
12、谊活动。,信息抽取实例:会议报道(人民日报1998-03-09),信息抽取的结果,自动问答（Question Answering，QA）,针对用户提出的问题，给出具体的答案。问句理解和答案生成。,情感分析（Sentiment Analysis或 Opinion Analysis）,分析文章对某个对象的态度是正面还是负面。应用于：市场决策、公共关系、.,自然语言处理的主要任务,语言分析词法分析：形态还原、词性标注、命名实体识别、分词（汉语）等句法分析：完全句法分析、组块分析、依存分析语义分析：词义、句义（依存、格关系、.）、篇章（上下文分）（指代、实体关系）语言生成多语言处理：对齐、转换不同的应
13、用对上述任务有不同的要求。MT是NLP技术的典型应用，它几乎涵盖了NLP各个任务。,自然语言处理所涉及的学科,计算语言学：各种语法、语义理论计算机科学（包括人工智能）数学：逻辑、概率与统计、信息论，等哲学心理学,直译（Direct）：从原文句子的表层（词、词组或短语）出发，直接转换成译文（必要的词序调整）。转换（Transfer）：对源语言进行分析，得到一个基于源语言的中间表示；然后，把这个中间表示转换成基于目标语言的中间表示；从基于目标语言的中间表示生成目标语言。中间语（Interlingua）：对源语言进行分析，得到一个独立于源语言和目标语言的、基于概念的中间表示；从这个中间表示生成目标语
14、言。,机器翻译的基本策略,中间语言,源语言,目标语言,分析,生成,词汇转换,句法转换,语义转换,(词法、句法、语义),(词法、句法、语义),机器翻译的实现方法,基于语言规则的理性方法（Rationalist approach）基于以规则形式表达的语言知识（词、句法、语义以及转换）进行推理。（Rule-based MT）又称传统的翻译方法，强调人对语言知识的理性整理。Chomsky：先天语言能力，主宰19601985基于语料库的经验方法（Empiricist approach）以大规模语料库（单语和双语）为语言知识基础。包括：基于统计的方法（SMT）利用统计学习方法自动获取和运用隐含在语料库中的
15、知识翻译知识的获取在翻译之前完成，体现为一系列统计数据（参数）基于实例的方法（EBMT）基于类比原理，通过相似度计算，在语料库中找出最相似的句子翻译知识的获取在翻译之前没有全部完成,翻译过程中还需要语料库,混合方法理性方法的优、缺点相应的语言学理论基础好描述精确效率高知识获取困难（高级劳动）鲁棒性（适应性）差：不完备的规则系统将导致推理的失败知识扩充困难，很难保证规则之间的一致性经验方法的优、缺点知识获取容易（低级劳动）鲁棒性好：概率大的作为结果扩充容易、一致性容易维护相应的语言学理论基础差缺乏对语言学知识的深入利用，过于机械效率低利用各家之长，相互融合,机器翻译的难点,歧义处理：有限的词汇和
16、规则表达复杂的、无限的语言语言知识的表示、获取和运用成语和惯用型的处理对语言的灵活性和动态性的处理灵活性：同一个意图的不同表达，甚至包含错误的语法等动态性：语言在不断的变化，如：新词等上下文和世界知识（语言无关）的利用和处理,汉语处理的难点,缺乏计算语言学的句法/语义理论，大都借用基于西方语言的句法/语义理论词法分析分词词性标注难句法分析主动词识别难词法分类与句法结构对应差语义分析句法结构与句义对应差时体态确定难（汉语无形态变化）资源（语料库）缺乏,机器翻译的现状,目前，机器翻译主要在一些简单的翻译任务中起到了一定的效果：对翻译质量要求不高的领域，如：网页浏览等子语言辅助翻译（后编辑）任意文本
17、的高质量的全自动翻译目前还很难实现。,传统的（基于规则）机器翻译方法,又称理性方法强调对语言知识的理性整理受计算语言学理论指导注重语言分析，翻译过程体现为“分析（转换）生成”基于规则的知识表示和推导翻译规则（数据）与程序分离翻译程序体现为规则语言的解释器！,翻译的基本任务,源语言分析词法分析句法分析语义分析转换不同层次词序、结构、语义的调整译词选择目标语言生成词形变化增/删词,自然语言的分类（基于形态结构）,分析型语言词形变化很少没有表示词的语法功能的附加成分，由词序和虚词表示词之间的语法关系汉语、藏语等黏着型语言有词形变化词的语法意义（功能）由附加成分表达芬兰语、日语等屈折型语言有词形变化词
18、的语法意义由词的形态变化来表示英语、德语、法语等另外，还可以按SVO型（主动宾）、VSO型（动主宾）和SOV 型(主宾动)分类,词法分析,形态还原（针对英语、德语、法语等）把句子中的词还原成基本词形，作为词的其它信息（词典、个性规则）的索引。词性标注为句子中的词标上预定义类别集合（标注集）中的类。分词（针对汉语、日语等）识别出句子中的词。命名实体识别人名地名机构名,形态还原（英语）,构词特点屈折变化：词尾和词形变化，词性不变。如：study,studied,studied,studyingspeak,spoke,spoken,speaking派生变化：加前缀和后缀，词性发生变化。如：frien
19、d,friendly,friendship,.复合变化：多个单词以某种方式组合成一个词。还原规则通用规则：变化有规律个性规则：变化无规律,形态还原规则举例,英语“规则动词”还原*s-*(SINGULAR3)*es-*(SINGULAR3)*ies-*y(SINGULAR3)*ing-*(VING)*ing-*e(VING)*ying-*ie(VING)*?ing-*?(VING)*ed-*(PAST)(VEN)*ed-*e(PAST)(VEN)*ied-*y(PAST)(VEN)*?ed-*?(PAST)(VEN),英语不规则动词还原went-go(PAST)gone-go(VEN)sat-s
20、it(PAST)(VEN),形态还原算法,输入一个单词如果词典里有该词，输出该词及其属性，转4，否则，转3如果有该词的还原规则，并且，词典里有还原后的词，则输出还原后的词及其属性，转4，否则，调用如果还有单词，转(1)，否则，结束。Proj.1 实现一个英语单词还原工具。（词典：）,词性标注,为句子中的词标上预定义类别集合（标注集）中的类，为后续的句法/语义分析提供必要的信息。标注体系标注方法,词性标注体系,词的分类按形态和句法功能（句法相关性）按表达的意思（语义相关性）兼顾上述二者为什么要分类？分类带来的问题？兼类词一个词具有两个或者两个以上的词性英文的Brown语料库中，10.4%的词是兼
21、类词。例如：The back doorOn my backPromise to back the bill汉语兼类词，例如：把门锁上，买了一把锁他研究.，研究工作汉语词的兼类更多？与所采用的分类体系是否有关？,英语词的分类,开放类（open class）Nouns句法上：可有限定词、可作物主、有复数形式语义上：人名、地名和物名Verbs句法上：几种词形变化语义上：动作、过程（一系列动作）Adjectives句法上：修饰Nouns等语义上：性质Adverbs句法上：修饰Verbs等语义上：方向、程度、方式、时间,封闭类（closed class，function words）Determiner
22、sPronounsPrepositionsConjunctionsAuxiliary verbsParticlesNumerals,词性标注方法,规则方法词典和规则提供候选词性消歧规则进行消歧统计方法选择最可能的标注训练用语料库（已标注）HMM标注等方法基于转换学习的方法统计学习规则用规则方法进行标注,汉语分词（切分）,词是语言中最小的能独立运用的单位，也是语言信息处理的基本单位。分词是指根据某个分词规范，把一个“字”串分成“词”串。分词规范难以确定何谓汉语的“词”单字词与语素的界定：猪肉、牛肉词与短语（词组）的界定：黑板、黑布信息处理用现代汉语分词规范：GB-13715（1992）具体系统可
23、根据各自的需求制定规范,分词方法,一般通过分词词典和分词规则库进行分词。主要方法有：正向最大匹配(FMM)或逆向最大匹配(RMM)从左至右(FMM)或从右至左(RMM)，取最长的词会忽略“词中有词”的现象：“幼儿园 地 节目”双向最大匹配分别采用FMM和RMM进行分词如果结果一致，则认为成功；否则，采用消歧规则进行消歧（交集型歧义）：正向最大、逆向最小匹配发现组合型歧义逐词遍历匹配在全句中取最长的词，去掉之，对剩下字符串重复该过程 设立切分标记收集词首字和词尾字，把句子分成较小单位，再用某些方法切分 全切分获得所有可能的切分，选择最大可能的切分,切分歧义及歧义字段的种类,交集型歧义字段ABC切
24、分成AB/C或A/BC如：“和平等”“独立/自主/和/平等/独立/的/原则”“讨论/战争/与/和平/等/问题”组合型歧义字段AB切分成AB或A/B如：“马上”“他/骑/在/马/上”“马上/过来”混合型歧义由交集型歧义和组合型歧义嵌套与交叉而成如：“太平、太平淡”“这/篇/文章/写/得/太/平淡/了”“这/墙/抹/得/太/平/了”“即使/太平/时期/也/不/应该/放松/警惕”,南京市长江大桥.,南京市长江二桥.,伪歧义与真歧义伪歧义字段指在任何情况下只有一种切分“为人民”只有一种切分：“为/人民”，如：“为/人民/服务”根据歧义字段本身就能消歧真歧义字段指在不同的情况下有多种切分“从小学”可以有
25、多种切分：“从小/学”，如：“从小/学/电脑”（“从小”是切分成“从小”还是“从/小”要根据分词规范！）“从/小学”，如：“他/从/小学/毕业/后”根据歧义字段的上下文来消歧,基于规则的歧义字段消歧方法,利用歧义字串、前驱字串和后继字串的句法、语义和语用信息：句法信息“阵风”：根据前面是否有数词来消歧。“一/阵/风/吹/过/来”、“今天/有/阵风”语义信息“了解”：“他/学会/了/解/数学/难题”（“难题”一般是“解”而不是“了解”)语用信息“拍卖”：“乒乓球拍卖完了”，要根据场景（上下文）来确定规则的粒度基于词（个性规则）基于词类、词义（共性规则）Proj.2 实现一个基于词典与规则的汉语自
26、动分词系统。(词典：http:/,基于词的转换翻译,翻译过程译词选择词序调整形态（词形变化）生成翻译所基于的知识对译（双语）词典及规则调序规则形态生成规则问题没有句法结构和语义分析的指导，转换很难很好地进行，特别是对句法/语义结构相差很大的语言。译词选择和词序调整工作可用的信息太少（利用原句中的局部信息和已得到的译词信息）。,句法分析（Parsing）,句法分析的目的判断句子的合法性（句子识别）确定句子的结构（句子中单词相互关联的方式）从机器翻译角度：比词一级的转换提供更多的信息基于上下文无关语法（CFG）的表示CFG能描述大部分的自然语言结构可以构造高效的基于CFG的句法分析器通常采用树形结
27、构来表示句法分析的结果,一个简单的产生式语法（英语）,1.S-NP VP2.VP-V NP3.NP-NAME4.NP-ART N5.NAME-John6.V-ate7.ART-the8.N-cat9.产生式59属于词法规则，一般由词典与词性标注算法来描述,John ate the cat的句法分析结果,S,NP,VP,NAME,John,V,NP,ate,ART,N,the,cat,优秀语法的特征,通用性能正确分析句子的范围选择性能判断出错误句子的范围可理解性自身的简易程度*鲁棒性对不合法句子的容忍度：He love her.通用性与选择性矛盾的处置，如：忽略主谓一致性检查将导致无法区分下面句
28、子的不同含义（歧义）Flying planes are dangerous.Flying planes is dangerous.,基于产生式的CFG分析器,自顶向下利用产生式，从S开始，尝试将S改写/推导成与输入句子相匹配的终结符号序列。自底向上利用产生式，尝试将输入句子规约到S。回溯从一个错误的尝试（改写或规约）返回，进行下一个尝试。保留改写或规约的历史回溯需要输出正确的分析结果也需要,一个简单的自顶向下句法分析算法,语法1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N4.VP-V 5.VP-V NP位置计数器1 The 2 dogs 3 cried 4状态由符号表和
29、当前位置构成，如：(NP VP)1)表示从位置1开始寻找NP，且NP后面是VP。初始状态为：(S)1)状态转换如果符号表的第一个符号是词法符号（词性），并且句子中当前词属于该词法类，则删除符号表中第一个符号，并更新当前位置(加1)，得到新的状态。否则，如果符号表的第一个符号是句法符号，则依据语法获得改写该符号的所有产生式，把它们的右部作为符号表与当前位置构成状态；选择其中一个作为新的状态，其它作为后备状态（在回溯时使用）。回溯从后备状态中取一个作为当前状态，继续分析,算法1.取(S)1)作为当前状态（初始状态），后备状态为空。2.若当前状态为空，则失败，算法结束，3.否则，若当前状态符号表为空
30、，(1)当前位置处于句子末尾，则成功，算法结束(2)当前位置处于句子中间，转54.否则，进行状态转换，若转换成功，则转25.否则，回溯，转2。,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程（续）,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,搜索策略,深度优先后备状态采用“栈”后备状态少，存储效率高面临“左递归
31、”问题广度优先后备状态采用“队列”后备状态多，存储效率不高,基于图的自底向上句法分析(chart parsing),简单的自底向上句法分析效率不高，常常会重复尝试相同的匹配操作（回溯之前已匹配过）。一种基于图的句法分析，采用一个数据结构来存储已经匹配过的结果，今后需要时可直接使用它们，不必重新匹配。（动态规划）图的构成结点表示句子中词之间的位置数字边分为：非活动边和活动边非活动边：已匹配的词法符号或句法符号活动边：未完全匹配的产生式，用加小圆圈标记（）的产生式来表示，如：NP-ART ADJ NNP-ART N,Chart Parsing句法分析算法,chart（非活动边）记录分析中规约成功所
32、得到的所有词法和句法符号activearcs（活动边集）记录活动边agenda（待处理表）记录等待加入chart的匹配成功的词法和句法符号上面的活动边、非活动边以及词法和句法符号都带有“始/终结点号”,重复下面的操作直到agenda为空并且输入中没有下一个词若agenda为空，则把句子中下一个词的各种词法符号（词性）加入进来，从agenda中取一个元素（设为C，位置为：p1-p2)对下面形式的每个规则：X-CX1.Xn，在activearcs中增加一条活动边：X-C X1.Xn，位置为：p1-p2；X-C，把X加入agenda，位置为：p1-p2边扩展将C加入到chart的位置p1-p2对每个
33、形式为：X-X1.C.Xn的活动边，若它在p0-p1之间，则在activearcs中增加一条活动边：X-X1.C.Xn，位置:p0-p2对每个形式为：X-X1.Xn C的活动边，若它在p0-p1之间，则在agenda中增加一个成分：X，位置为：p0-p2,Chart Parsing句法分析算法（续）,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程(算法),1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.
34、VP-V NP,ART(1,2),agenda,5,6,a,mouse,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程(算法),1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,N(2,3),agenda,5,6,a,mouse,N,NP(1,3),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程(算法),1,2,3,4,The,cat,caught,AR
35、T,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,NP(1,3),S-NP VP,NP,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,
36、V(3,4),S-NP VP,NP,VP-V NP,VP(3,4),V,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,VP(3,4),V,VP,S(1,4),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,T
37、he,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,V,VP,S(1,4),S,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5
38、.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,V,VP,ART(4,5),S,NP-ART N,NP-ART ADJ N,ART,“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,V,VP,N(5,6),S,NP
39、-ART N,NP-ART ADJ N,ART,N,NP(4,6),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,V,VP,S,NP-ART N,NP-ART ADJ N,ART,N,NP(4,6),S-NP VP,NP,VP(3,6),“1 The 2 ca
40、t 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,V,VP,S,NP-ART N,NP-ART ADJ N,ART,N,S-NP VP,NP,VP(3,6),VP,S(1,6),“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程,1,2,3,4,The,
41、cat,caught,ART,NP-ART N,NP-ART ADJ N,活动边,非活动边,1.S-NP VP 2.NP-ART N 3.NP-ART ADJ N 4.VP-V 5.VP-V NP,agenda,5,6,a,mouse,N,S-NP VP,NP,VP-V NP,V,VP,S,NP-ART N,NP-ART ADJ N,ART,N,S-NP VP,NP,VP,S(1,6),S,Proj.3 实现一个基于简单英语语法的chart句法分析器。,基于递归转移网络的语法表示,除了CFG的产生式规则外，递归转移网络（Recusive Transition Network，简称RTN）是另一
42、种表示自然语言语法的形式化手段。一个RTN是由结点和有向边组成：结点表示状态，起始状态对应于产生式规则中的一个句法符号。有向边可以是以下类型：CAT：词法符号（词性）WRD：词PUSH（句法符号）：转向其它转移网络的名POP：成功结束当前网络JUMP：无条件转移一个RTN相当于一个不确定的下推自动机,一个基于RTN的英语语法表示,NP,NP1,NP2,NP：,ART,N,pop,ADJ,S,S1,NP（push）,V,NP,S2,S:,pop,PRON,NUM,1,2,3,1,2,1,2,返回,基于RTN的自顶向下句法分析,状态(当前结点,当前输入位置,返回结点栈)起始状态(S,1,NIL)终
43、止状态(NIL,n,NIL)n为句子的终止位置后备状态回溯,状态转换按下面满足条件的边进行转换，若有多个满足条件的边，则选其中一条边的转换结果作为新的当前状态，其它边的转换结果作为后备状态。如果当前边为词类（词法符号）并且句子中下一个词属于该词类更新输入位置（+1）更新当前结点为当前边的目标结点如果当前边为PUSH（设为句法符号N）将当前边的目标结点加入返回结点栈更新当前结点为N的起始结点如果当前边是POP且返回结点栈非空取返回结点栈元素作为当前结点如果当前边是POP、返回结点栈为空且句子没有剩余的词句法分析成功回溯后备状态不为空，从中取一个，继续进行前面的转换否则，失败,句子“1One 2s
44、aw 3the 4man 5”的分析过程,句法分析与逻辑程序设计,逻辑程序设计是把程序组织成一组事实和一组推理规则，它基于谓词演算（Predicate Calculus）进行计算，计算过程由实现系统给出。可以把语法写成PROLOG的事实（公理）和子句（规则）形式（由谓词构成），推理过程由PROLOG的执行机制自动完成。,一个CFG语法的PROLOG表示,语法规则可表示成：s(P1,P3):-np(P1,P2),vp(P2,P3)np(P1,P3):-art(P1,P2),n(P2,P3)np(P1,P3):-name(P1,P3)pp(P1,P3):-p(P1,P2),np(P2,P3)vp(
45、P1,P2):-v(P1,P2)vp(P1,P3):-v(P1,P2),np(P2,P3)vp(P1,P3):-v(P1,P2),pp(P2,P3)n(P1,P2):-word(W,P1,P2),isnoun(W)art(P1,P2):-word(W,P1,P2),isart(W)v(P1,P2):-word(W,P1,P2),isverb(W)name(P1,P2):-word(W,P1,P2),isname(W),词典可表示成：isart(the)isname(john)isverb(ate)isnoun(cat).,输入句子“John ate the cat”可表示成：word(john
46、,1,2)word(ate,2,3)word(the,3,4)word(cat,4,5)通过查询谓词s(1,5)的真假来识别句子“John ate the cat”：?-s(1,5)标准PROLOG的搜索策略与自顶向下的深度优先分析方法一致。,CFG在描述自然语言时存在的问题,1.S-NP VP 4.VP-V2.NP-ART N 5.VP-V NP3.NP-ART ADJ N上面的语法描述了英语的一个子集，同时，它又会生成一些不合法的英语句子，如：The student solve the problemThe teacher disappeared the problem,一种可能的解决方案
47、增加句法符号,把NP分为NP-S和NP-P；把VP分成VP-S和VP-P：S-NP-S VP-SS-NP-P VP-P把N分成N-S和N-P：NP-S-ART N-SNP-S-ART ADJ N-SNP-P-ART N-PNP-P-ART ADJ N-P把V分成V-S-I、V-S-T、V-P-I和V-P-T：VP-S-V-S-IVP-S-V-S-T NP-S VP-S-V-S-T NP-PVP-P-V-P-IVP-P-V-P-T NP-SVP-P-V-P-T NP-P,增加句法符号带来的问题,增加了规则的数量和潜在的冗余类似的规则缺乏关联性对语言结构描述缺乏深度,基于特征的扩展CFG,不增加原
48、CFG中的句法符号给每个句法符号增加特征，例如：NP(PER 3,NUM s)VP(PER 3,NUM s,VAL itr)特征由特征名和特征值构成。一系列特征构成了一个特征结构（复杂特征集）。特征值可以是普通值（原子），也可以是另一个特征结构，例如：NP(AGR（PER 3,NUM s)简写为：NP(AGR 3s)一个特征的特征值可以有多个，表示成：N(ROOT fish,AGR 3s,3p),特征值也可以是变量，例如：NP(AGR?a)S-NP(AGR?a)VP(AGR?a)表示NP与VP的AGR特征值一致一个规则如果包含特征值为变量的成分，则该规则代表了一组规则。可以对变量形式的特征值限
49、定范围（受限变量），例如：NP(AGR?a3s,3p),一个基于特征结构的CFG语法,S-NP(AGR?a)VP(AGR?a)NP(AGR?a)-ART N(AGR?a)NP(AGR?a)-ART ADJ N(AGR?a)VP(AGR?a)-V(AGR?a,VAL itr)VP(AGR?a)-V(AGR?a,VAL tr)NP,基于特征CFG的chart parsing,句子语法成分与规则匹配时，要对各个特征进行匹配和泛化处理。若规则包含特征值为变量的成分，匹配时需要实例化这个规则，例如：对于规则：NP(AGR?a)-ART(AGR?a)N(AGR?a)若有下面的语法成分需要匹配：ART(RO
50、OT a,AGR 3s)则需要实例化规则中的?a：NP(AGR 3s)-ART(AGR 3s)N(AGR 3s)它与ART(ROOT a,AGR 3s)匹配后扩展为：NP(AGR 3s)-ART(AGR 3s)N(AGR 3s)若句子中还有N(ROOT dog,AGR 3s)需要匹配，则进一步扩展为：NP(AGR 3s)-ART(AGR 3s)N(AGR 3s),如果待匹配的语法成分的特征值中包含受限变量，则实例化后的规则中的取值范围为两者的交集，例如：实例化前的规则：NP(AGR?a)-ART(AGR?a)N(AGR?a)要匹配的语法成分：ART(ROOT the,AGR?a3s,3p)实例
