自然语言处理NaturalLanguageProcessingNLP.ppt

《自然语言处理NaturalLanguageProcessingNLP.ppt》由会员分享，可在线阅读，更多相关《自然语言处理NaturalLanguageProcessingNLP.ppt（112页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自然语言处理NaturalLanguageProcessingNLP Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望主要内容（1）p自然语言处理概述n什么是自然语言处理n自然语言处理技术的应用n自然语言处理的基本策略和实现方法n自然语言处理的难点n自然语言处理所涉及的学科p基于规则的自然语言处理方法（理性方法理性方法，传统方法）n基于词典和规则的分词（汉语、日语）n基于CFG（上下文无关文法）的句法表示及其分析技术n基于扩充的CFG（复杂特征集、合一运算）的句法

2、表示及其分析技术n词义及句义表示：基于逻辑形式和格语法的句义分析n基于规则的机器翻译主要内容（2）p基于语料库和统计学习的自然语言处理方法（经验经验方法方法）n语言模型（N元文法）n分词、词性标注（序列化标注模型）n句法分析（概率上下文无关模型）n文本分类（朴素贝叶斯模型、最大熵模型）n机器翻译 (IBM Model)主要内容（3）所需的前导知识p编译技术p概率与统计参考书籍p刘群等译，自然语言理解（第二版）自然语言理解（第二版），电子工业出版社，2005p苑春法等译，统计自然语言处理基础统计自然语言处理基础，电子工业出版社，2005p冯志伟等译，自然语言处理综论自然语言处理综论，电子工业出版

3、社，2005p黄昌宁等，语料库语言学语料库语言学，商务印书馆，2002p冯志伟，计算语言学基础计算语言学基础，商务印书馆，2001p余士文，计算语言学概论计算语言学概论，商务印书馆，2003p姚天顺，自然语言理解一种让机器懂得人类语言的研究（第自然语言理解一种让机器懂得人类语言的研究（第2版）版），清华大学出版社，2002p宗成庆，统计自然语言处理统计自然语言处理，清华大学出版社，2008p王小捷等，自然语言处理技术基础自然语言处理技术基础，北京邮电大学出版社,2002p刘颖，计算语言学计算语言学，清华大学出版社，2002pBonnie J. Dorr, et al, Survey of Cu

4、rrent Paradigms in Machine Translation，Technical Report LAMP-TR-027, Language and Media Processing Lab, University of Maryland.pHutchins WJ, Machine Translation: Past, Present, Future. Chichester: Ellis Horwood, 1986pArturo Trujillo, Translation Engines: Techniques for Machine Translation, Springer-

5、Verlag London Limited 1999pPeter F. Brown, et al., A Statistical Approach to MT, Computational Linguistics, 1990,16(2)pP.F. Brown, et al., The Mathematics of Statistical Machine Translation: Parameter Estimation, Computational Linguistics, 1993, 19(2)p赵铁军等，机器翻译原理机器翻译原理，哈尔滨工业大学出版社，2000p宗成庆等译，统计机器翻译统计

6、机器翻译，电子工业出版社，2012课程考核pProjectsp提交要求（每个project）n报告（说明基本做法）n源程序及可运行的程序 自然语言处理概述什么是自然语言处理p充分利用信息将会给人们带来巨大的收益，而大量的信息以自然语言自然语言形式（英语、汉语等）存在。p如何有效地获取和利用以自然语言形式出现的信如何有效地获取和利用以自然语言形式出现的信息？息？p自然语言处理（Natural Language Processing，简称NLP）是指用计算机对语言信息进行处理的方法和技术。p与NLP相近的两个研究领域：n自然语言理解(NLU)：强调对语言含义和意图的深层次解释n计算语言学(CL)：

7、强调可计算的语言理论NLP技术的应用p机器翻译p自动摘要p文本分类p信息检索p信息抽取p自动问答p情感分析p.机器翻译（Machine Translation）p机器翻译（Machine Translation，简称MT）是指利用计算机实现自然语言（英语、汉语等）之间的自动翻译。n文本机器翻译n语音机器翻译p机器辅助翻译（Machine Aided Translation或Computer Aided Translation，简称MAT或CAT）n翻译记忆体（Translation Memory，简称TM）n双语对照的文本编辑n.自动摘要（Text Summarization）p利用计算机自动

8、地从原始文档中提取全面准确地反映该文档中心内容的简单连贯的短文。p压缩比 文本分类（Text Classification）p利用计算机将一篇文章归于预先给定的某一类或某几类的过程。p可用于信息过滤（Information Filtering）信息检索（Information Retrieval，IR）p主题相关的文本获取。pgoogle、百度、.（基于关键词的）信息抽取（Information Extraction，IE）p主题相关的信息获取p信息抽取是指从非结构化或半结构化的自然语言文本中提取出与某个主题相关的结构化信息。pIE对数据挖掘的支持新华社北京月日电（记者李术峰）: 中国农工民主

9、党第十二届中央常务委员会第一次会议今天在北京召开。会议研究通过了贯彻落实“两会”精神的有关决定，审议通过了中国农工民主党中央年工作要点（草案），并任命了中央副秘书长。农工民主党中央主席蒋正华主持了会议，他说，农工民主党有多名党员作为代表和委员参加了今年的“两会”，各位党员要认真履行代表和委员的职责，开好会，在年的工作中认真贯彻“两会”精神，加强农工民主党的自身建设，推动事业进一步发展，为建设有中国特色社会主义事业作出新的贡献。会前，农工民主党中央邀请参加“两会”的来自全国各省、自治区、直辖市的农工民主党党员进行了联谊活动。信息抽取实例信息抽取实例:会议报道(人民日报1998-03-09)信息抽

10、取的结果会 议 时 间 Time 年3月8日会 议 地 点 Spot 北京会议召集者/主持人Convener个人姓名/团体名称 Name蒋正华机 构 、 职 位 Org/Post主席，农工民主党中央会议名/标题Conf-Title 中国农工民主党第十二届中央常务委员会第一次会议 自动问答（Question Answering，QA）p针对用户提出的问题，给出具体的答案。pApple的Siri、IBM的Watson机器人、百度的“知道”、情感分析（Sentiment Analysis或 Opinion Analysis ）p分析文章对某个对象的态度是正面还是负面。n公共关系：舆情分析n市场决策：

11、产品意见调查n.自然语言处理的主要任务p语言分析：分析语言表达的结构和含义n词法分析：形态还原、词性标注、命名实体识别、分词（汉语）等n句法分析：组块分析、结构分析、依存分析n语义分析：词义、句义（逻辑、格关系、.）、篇章（上下文分）（指代、实体关系）p语言生成：从内部表示生成语言表达p多语言处理：语言之间的对齐、转换p不同的应用对上述任务有不同的要求。n机器翻译需要NLP各方面的方法和技术支持，是NLP的典型应用，它几乎涵盖了NLP各个任务。自然语言处理的实现方法p基于语言规则的理性方法（Rationalist approach）n基于以规则形式表达的语言知识（词、句法、语义以及转换、生成）

12、进行推理。n强调人对语言知识的理性整理。nChomsky：先天语言能力，主宰19601985p基于语料库和统计学习的经验方法（Empiricist approach）n以大规模语料库（单语和双语）为语言知识基础。n利用统计学习方法自动获取和运用隐含在语料库中的知识n知识体现为一系列统计数据（参数）p混合方法n理性方法的优、缺点p相应的语言学理论基础好p描述精确p效率高p知识获取困难（高级劳动）p鲁棒性（适应性）差：不完备的规则系统将导致推理的失败p知识扩充困难，很难保证规则之间的一致性n经验方法的优、缺点p知识获取容易（低级劳动）p鲁棒性好：概率大的作为结果p扩充容易、一致性容易维护p相应的语

13、言学理论基础差p缺乏对语言学知识的深入利用，过于机械p效率低n利用各家之长，相互融合自然语言处理的难点p歧义处理n有限的词汇和规则表达复杂的、无限的语言p语言知识的表示、获取和运用p成语和惯用型的处理p对语言的灵活性和动态性的处理n灵活性：同一个意图的不同表达，甚至包含错误的语法等n动态性：语言在不断的变化，如：新词等p上下文和世界知识（语言无关）的利用和处理汉语处理的难点p缺乏计算语言学的句法/语义理论，大都借用基于西方语言的句法/语义理论p词法分析n分词n词性标注难p句法分析n主动词识别难n词法分类与句法功能对应差p语义分析n句法结构与句义对应差n时体态确定难 （汉语无形态变化）p资源（语

14、料库）缺乏自然语言处理所涉及的学科p计算语言学：各种语法、语义理论p计算机科学（包括人工智能）p数学：逻辑、概率与统计、信息论，等p哲学（认知学）p心理学p. 基于规则的自然语言处理方法 （ 理性方法，传统方法）概述p强调对语言知识的理性整理（知识工程）p受计算语言学理论指导p基于规则的知识表示和推导p语言处理规则（数据）与程序分离，程序体现为规则语言的解释器！自然语言的分类（基于形态结构）p分析型语言n词形变化很少n没有表示词的语法功能的附加成分，由词序和虚词表示词之间的语法关系n汉语、藏语等p黏着型语言n有词形变化n词的语法意义（功能）由附加成分表达n芬兰语、日语等p屈折型语言n有词形变化

15、n词的语法意义由词的形态变化来表示n英语、德语、法语等p另外，还可以按SVO型（主动宾）、VSO型（动主宾）和SOV 型(主宾动) 分类词法分析p形态还原（针对英语、德语、法语等）n把句子中的词还原成基本词形，作为词的其它信息（词典、个性规则）的索引。p词性标注n为句子中的词标上预定义类别集合（标注集）中的类。p分词（针对汉语、日语等）n识别出句子中的词。p命名实体识别n人名n地名n机构名形态还原（英语）p构词特点n屈折变化：词尾和词形变化，词性不变。如：pstudy, studied,studied,studyingpspeak,spoke,spoken,speakingn派生变化：加前缀和

16、后缀，词性发生变化。如：pfriend,friendly,friendship,.n复合变化：多个单词以某种方式组合成一个词。p还原规则n通用规则：变化有规律n个性规则：变化无规律形态还原规则举例p英语“规则动词”还原n*s - * (SINGULAR3)n*es - * (SINGULAR3)n*ies - *y (SINGULAR3)n*ing - * (VING)n*ing - *e (VING)n*ying - *ie (VING)n*?ing - *? (VING)n*ed - * (PAST)(VEN)n*ed - *e (PAST)(VEN)n*ied - *y (PAST)(V

17、EN)n*?ed - *? (PAST)(VEN)p英语不规则动词还原nwent - go (PAST)ngone - go (VEN)nsat - sit (PAST) (VEN)形态还原算法p输入一个单词p如果词典里有该词，输出该词及其属性，转4，否则，转3p如果有该词的还原规则，并且，词典里有还原后的词，则输出还原后的词及其属性，转4，否则，调用p如果输入中还有单词，转(1)，否则，结束。Proj. 1 实现一个英语单词还原工具。（词典：http:/ back doorpOn my backpPromise to back the billn汉语兼类词，例如：p把门锁上， 买了一把锁p他

18、研究.， 研究工作n汉语词的兼类更多？与所采用的分类体系是否有关？p为什么要分类？分类带来的问题？英语词的分类p开放类（open class）nNounsp句法上：可有限定词、可作物主、有复数形式p语义上：人名、地名和物名nVerbsp句法上：几种词形变化p语义上：动作、过程（一系列动作）nAdjectivesp句法上：修饰Nouns等p语义上：性质nAdverbsp句法上：修饰Verbs等p语义上：方向、程度、方式、时间p封闭类（closed class，function words）nDeterminersnPronounsnPrepositionsnConjunctionsnAuxili

19、ary verbsnParticles（if、not、.）nNumerals词性标注方法p规则方法n词典和规则提供候选词性n消歧规则进行消歧p统计方法n选择最可能的标注n训练用语料库（已标注）p基于转换学习的方法n统计学习规则n用规则方法进行标注汉语分词（切分）p词是语言中最小的能独立运用的单位，也是语言信息处理的基本单位。p分词是指根据某个分词规范，把一个“字”串分成“词”串。p分词规范n难以确定何谓汉语的“词”p单字词与语素的界定：猪肉、牛肉p词与短语（词组）的界定：黑板、黑布n信息处理用现代汉语分词规范：GB-13715（1992）n具体系统可根据各自的需求制定规范切分歧义及歧义字段的种

20、类p交集型歧义字段nABC切分成AB/C或A/BCn如：“和平等”p“独立/自主/和/平等/独立/的/原则”p“讨论/战争/与/和平/等/问题”p组合型歧义字段nAB切分成AB或A/Bn如：“马上”p“他/骑/在/马/上”p“马上/过来”p混合型歧义n由交集型歧义和组合型歧义嵌套与交叉而成n如：“太平淡”（组合型、交集型）p“这/墙/抹/得/太/平/了”（组合型）p“即使/太平/时期/也/不/应该/放松/警惕”（组合型）p“这/篇/文章/写/得/太/平淡/了”（交集型）南京市长江大桥.南京市长江二桥.p伪歧义与真歧义n伪歧义字段指在任何情况下只有一种切分p“为人民”只有一种切分：“为/人民”，

21、如：“为/人民/服务”p根据歧义字段本身就能消歧n真歧义字段指在不同的情况下有多种切分p“从小学”可以有多种切分： “从小/学” ，如：“从小/学/电脑” （“从小”是切分成“从小”还是“从/小”要根据分词规范！） “从/小学”，如：“他/从/小学/毕业/后”p根据歧义字段的上下文来消歧分词方法一般通过分词词典和分词规则库进行分词。主要方法有：p正向最大匹配(FMM)或逆向最大匹配(RMM)n从左至右(FMM)或从右至左(RMM)，取最长的词n会忽略“词中有词”的现象：“幼儿园 地 节目”p双向最大匹配n分别采用FMM和RMM进行分词n如果结果一致，则认为成功；否则，n采用消歧规则进行消歧（交

22、集型歧义）：p正向最大、逆向最小匹配n发现组合型歧义p逐词遍历匹配n在全句中取最长的词，去掉之，对剩下字符串重复该过程 p设立切分标记n收集词首字和词尾字，把句子分成较小单位，再用某些方法切分 p全切分n获得所有可能的切分，选择最大可能的切分基于规则的歧义字段消歧方法p利用歧义字串、前驱字串和后继字串的句法、语义和语用信息：n句法信息p“阵风”：根据前面是否有数词来消歧。“一/阵/风/吹/过/来”、“今天/有/阵风”n语义信息p“了解”：“他/学会/了/解/数学/难题”（“难题”一般是“解”而不是“了解”，另外，还有“学会”)n语用信息p“拍卖”：“乒乓球拍卖完了”，要根据场景（上下文）来确定

23、p规则的粒度n基于词（个性规则）n基于词类、词义（共性规则）Proj. 2 实现一个基于词典与规则的汉语自动分词系统。(词典：http:/ ate the cat的组成分分析SNPVPNAMEJohnVNPateARTNthecatJohn ate the cat的依存分析John ate the catsubobjmod句法分析（Parsing）p句法分析的目的n判断句子的合法性（句子识别）n确定句子的结构（句子中单词相互关联的方式）p基于上下文无关语法（CFG）的表示nCFG能描述大部分的自然语言结构n可以构造高效的基于CFG的句法分析器p通常采用树形结构来表示句法分析的结果一个简单的产生

24、式语法（英语）1. S - NP VP2. VP - V NP3. NP - NAME4. NP - ART N5. NAME - John6. V - ate7. ART - the8. N - cat9. .p产生式59属于词法规则，一般由词典与词性标注算法来描述 优秀语法的特征p通用性n能正确分析句子的范围p选择性n能判断出错误句子的范围p可理解性n自身的简易程度p*鲁棒性n对不合法句子的容忍度：He love her.n通用性与选择性矛盾的处置，如：忽略主谓一致性检查将导致无法区分下面句子的不同含义（歧义）pFlying planes are dangerous.pFlying pla

25、nes is dangerous.基于产生式的CFG分析器p自顶向下n利用产生式，从S开始，尝试将S改写/推导成与输入句子相匹配的终结符号序列。p自底向上n利用产生式，尝试将输入句子规约到S。p回溯n在改写或规约的某一步可能有多个选择。n从一个错误的尝试（改写或规约）返回，进行下一个尝试。p保留改写或规约的历史n回溯需要n输出正确的分析结果也需要一个简单的自顶向下句法分析算法p语法n1. S - NP VP 2. NP - ART N 3. NP - ART ADJ Nn4. VP - V 5. VP - V NPp位置计数器n1 The 2 dogs 3 cried 4p状态n由符号表和当前

26、位置构成，如：(NP VP) 1) 表示从位置1开始寻找NP，且NP后面是VP。n分为当前状态和后备状态。p状态转换n当前状态符号表的第一个符号是词法符号（词性），并且句子中当前词属于该词法类，则删除符号表中第一个符号，并更新当前位置(加1)，得到新的当前状态。n当前状态符号表的第一个符号是句法符号，则依据语法获得改写该符号的所有产生式，把它们的右部作为符号表与当前位置构成状态；选择其中一个作为新的当前状态，其它作为后备状态（在回溯时使用）。p回溯n从后备状态中取一个作为当前状态，继续分析p算法1. 取 (S) 1)作为当前状态（初始状态），后备状态为空。2. 若当前状态为空，则失败，算法结束

27、，3. 否则，若当前状态符号表为空，(1)当前位置处于句子末尾，则成功，算法结束(2)当前位置处于句子中间，转54. 否则，进行状态转换状态转换，若转换成功，则转25. 否则，回溯回溯，转2。步骤步骤当前状态当前状态后备状态后备状态备注备注1(S) 1)初始状态2(NP VP) 1)规则1改写3(ART N VP) 1)(ART ADJ N VP) 1)规则2、3改写4(N VP) 2)(ART ADJ N VP) 1)ART匹配the5(VP) 3)(ART ADJ N VP) 1)N匹配cat6(V) 3)(V NP) 3)(ART ADJ N VP) 1)规则4、5改写7() 4)(V

28、NP) 3)(ART ADJ N VP) 1)V匹配caught“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步骤步骤当前状态当前状态后备状态后备状态备注备注8(V NP) 3)(ART ADJ N VP) 1)回溯9(NP) 4)(ART ADJ N VP) 1)V匹配caught10(ART N) 4)(ART ADJ N) 4)(ART ADJ N VP) 1)规则2、3改写11(N) 5)(ART ADJ N) 4)(ART ADJ N

29、VP) 1)ART匹配a12() 6)(ART ADJ N) 4)(ART ADJ N VP) 1)N匹配mouse13结束“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搜索策略p深度优先n后备状态采用“栈”n后备状态少，存储效率高n面临“左递归”问题p广度优先n后备状态采用“队列”n后备状态多，存储效率不高基于图的自底向上句法分析(chart parsing)p简单的自底向上句法分析效率不高，常常会重复尝试相同的匹配操作（回溯之前已匹配过

30、）。p一种基于图的句法分析，采用一个数据结构来存储已经匹配过的结果，今后需要时可直接使用它们，不必重新匹配。（动态规划）Chart Parsing句法分析p结点表示句子中词之间的位置数字pchart（非活动边）n记录分析中规约成功所得到的所有词法和句法符号pactivearcs（活动边集）n未完全匹配的产生式，用加小圆圈标记（）的产生式来表示，如：pNP - ART ADJ NpNP - ART Npagenda（待处理表）n记录等待加入chart的匹配成功的词法和句法符号p上面的活动边、非活动边以及词法和句法符号都带有“始/终结点号”重复下面的操作直到agenda为空并且输入中没有下一个词p

31、若agenda为空，则把句子中下一个词的各种词法符号（词性）加入进来，p从agenda中取一个元素（设为C，位置为：p1-p2)p对下面形式的每个规则：nX-CX1.Xn，在activearcs中增加一条活动边：X-C X1.Xn，位置为：p1-p2；nX-C，把X加入agenda，位置为：p1-p2p将C加入到chart的位置p1-p2p边扩展n对每个形式为：X-X1. C.Xn的活动边，若它在p0-p1之间，则在activearcs中增加一条活动边：X-X1. C .Xn，位置:p0-p2n对每个形式为： X-X1. Xn C的活动边，若它在p0-p1之间，则把X加入agenda ，位置为

32、：p0-p2Chart Parsing句法分析算法（续）“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程 (算法)1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPART(1,2)agenda56amouse“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程 (算法)1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1

33、. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPN(2,3)agenda56amouseNNP(1,3)“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程 (算法)1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNNP(1,3)S - NP VPNP“1 The 2 cat 3 caught 4 a 5 mo

34、use 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNV(3,4)S - NP VPNPVP - V NPVP(3,4)V“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4.

35、VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVP(3,4)VVPS(1,4)“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVVPS(1,4)S“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程

36、1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVVPART(4,5)SNP - ART NNP - ART ADJ NART“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP

37、-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVVPN(5,6)SNP - ART NNP - ART ADJ NARTNNP(4,6)“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVVPSNP -

38、 ART NNP - ART ADJ NARTNNP(4,6)S - NP VPNPVP(3,6)“1 The 2 cat 3 caught 4 a 5 mouse 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVVPSNP - ART NNP - ART ADJ NARTNS - NP VPNPVP(3,6)VPS(1,6)“1 The 2 c

39、at 3 caught 4 a 5 mouse 6”的分析过程1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动边非活动边1. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVVPSNP - ART NNP - ART ADJ NARTNS - NP VPNPVPS(1,6)SProj. 3 实现一个基于简单英语语法的chart句法分析器。句法分析与逻辑程序设计p逻辑程序设计是把程序组织成一组事实和一组推理规则，它基于谓词演

40、算（Predicate Calculus）进行计算，计算过程由实现系统给出。p可以把语法写成PROLOG的子句（clause）：谓词（事实）和规则形式，推理过程由PROLOG的执行机制自动完成。一个CFG语法的PROLOG表示p语法规则可表示成：ns(P1,P3):-np(P1,P2),vp(P2,P3)nnp(P1,P3):-art(P1,P2),n(P2,P3)nnp(P1,P3):-name(P1,P3)npp(P1,P3):-p(P1,P2),np(P2,P3)nvp(P1,P2):-v(P1,P2)nvp(P1,P3):-v(P1,P2),np(P2,P3)nvp(P1,P3):-v

41、(P1,P2),pp(P2,P3)nn(P1,P2):-word(W,P1,P2),isnoun(W)nart(P1,P2):-word(W,P1,P2),isart(W)nv(P1,P2):-word(W,P1,P2),isverb(W)nname(P1,P2):-word(W,P1,P2),isname(W)p词典可表示成：nisart(the)nisname(john)nisverb(ate)nisnoun(cat)n.p输入句子“John ate the cat”可表示成：nword(john,1,2)nword(ate,2,3)nword(the,3,4)nword(cat,4,5)

42、p通过查询谓词s(1,5)的真假来识别句子“John ate the cat”：n?- s(1,5)p标准PROLOG的搜索策略与自顶向下的深度优先分析方法一致。CFG在描述自然语言时存在的问题1. S - NP VP 4. VP - V2. NP - ART N 5. VP - V NP3. NP - ART ADJ Np上面的短语结构语法描述了英语的一个子集，同时，它又会生成一些不合法的英语句子，如：nThe student solve the problem.（主谓不一致）nThe teacher disappeared the problem.（不及物动词）一种可能的解决方案增加句法符

43、号p把NP分为NP-S和NP-P；把VP分成VP-S和VP-P：nS-NP-S VP-SnS-NP-P VP-Pp把N分成N-S和N-P：nNP-S-ART N-SnNP-S-ART ADJ N-SnNP-P-ART N-PnNP-P-ART ADJ N-Pp把V分成V-S-I、V-S-T、V-P-I和V-P-T：nVP-S-V-S-InVP-S-V-S-T NP-S nVP-S-V-S-T NP-PnVP-P-V-P-InVP-P-V-P-T NP-SnVP-P-V-P-T NP-P增加句法符号带来的问题p增加了规则的数量和潜在的冗余p类似的规则缺乏关联性p对语言结构描述缺乏深度（表层）基于

44、特征的扩展CFGp不增加原CFG中的句法符号p给每个句法符号增加特征（属性），例如：nNP(PER 3,NUM s)nVP(PER 3,NUM s,VAL itr)p特征由特征名和特征值构成。一系列特征构成了一个特征结构（复杂特征集）。p特征值可以是普通值（原子），也可以是另一个特征结构，例如：nNP(AGR （PER 3, NUM s)，可简写为：nNP(AGR 3s)p一个特征的特征值可以有多个，表示成：nN(ROOT fish, AGR 3s,3p)p特征值也可以是变量，例如：nNP(AGR ?a)nS-NP(AGR ?a) VP(AGR ?a) 表示NP与VP的AGR特征值一致（取同样

45、的值）p一个规则如果包含特征值为变量的成分，则该规则代表了一组规则。（规则模板）p可以对变量形式的特征值限定范围（受限变量），例如：nNP(AGR ?a3s,3p)一个基于特征结构的CFG语法pS-NP(AGR ?a) VP(AGR ?a)pNP(AGR ?a) - ART N(AGR ?a)pNP(AGR ?a) - ART ADJ N(AGR ?a)pVP(AGR ?a) - V(AGR ?a,VAL itr)pVP(AGR ?a) - V(AGR ?a,VAL tr) NP基于合一的语法p一个文法可以表示成一系列特征结构间的约束关系所组成的集合。这样的文法称为合一文法（Unificati

46、on Grammar）。例如：n特征结构X0、X1和X2之间的约束关系：pX0-X1 X2 (CAT0=S,CAT1=NP,CAT2=VP, AGR0=AGR1=AGR2,VFORM0=VFORM2)n它描述了基于特征的CFG中的一条规则：pS-NP(AGR ?a) VP(AGR ?a)p合一文法为其它的基于特征的文法提供了一个形式描述基础。p特征结构的合一运算构成了合一文法的基本操作，其作用有两个：n创建新的特征结构（规约的结果）n检查特征结构间的相容性以确定多个特征结构是否可以合并（规约）合一运算p复杂特征集“相容”n(f)表示复杂特征集的特征f的值n若、为复杂特征集，则和相容，当且仅当：

47、p若(f)=a，(f)=b，a、b都是原子，和是相容的当且仅当a=bp若(f)、(f)均为复杂特征集，和是相容的当且仅当(f)与(f)相容p复杂特征集“合一运算”：n如果a、b都是原子,若a=b，则ab=a，否则ab=n若、均为复杂特征集，则p若(f)=v，但(f)未定义，则f=v属于p若(f)=v，但(f)未定义，则f=v属于p若(f)=v1，(f)=v2，且v1与v2相容，则f=(v1v2)属于，否则，= 合一运算举例p(CAT V, ROOT cry)与(CAT V, VFORM pres)可以合一为：(CAT V, ROOT cry, VFORM pres)p(CAT V, AGR 3

48、s)与(CAT V, AGR 3p)不能合一p(CAT N,ROOT fish, AGR 3s,3p)与(CAT N, AGR 3s)可以合一为： (CAT N,ROOT fish, AGR 3s)基于特征CFG的chart parsingp句子语法成分与规则匹配时，要对各个特征进行匹配和泛化处理。p若规则包含特征值为变量的成分，匹配时需要实例化这个规则，例如：n对于规则：pNP(AGR ?a)- ART(AGR ?a) N(AGR ?a)n若有下面的语法成分需要匹配：pART(ROOT a, AGR 3s)n则需要实例化规则中的?a：pNP(AGR 3s)- ART(AGR 3s) N(AG

49、R 3s)n它与ART(ROOT a, AGR 3s)匹配后扩展为：pNP(AGR 3s)- ART(AGR 3s) N(AGR 3s)n若句子中还有N(ROOT dog, AGR 3s)需要匹配，则进一步扩展为：pNP(AGR 3s)- ART(AGR 3s) N(AGR 3s) p如果待匹配的语法成分的特征值中包含受限变量，则实例化后的规则中的取值范围为两者的交集，例如：n实例化前的规则：pNP(AGR ?a)- ART(AGR ?a) N(AGR ?a)n要匹配的语法成分：pART(ROOT the, AGR ?a3s,3p)n实例化后的规则为：pNP(AGR ?a3s,3p)- ART

50、(AGR ?a3s,3p) N(AGR ?a3s,3p)n匹配扩展后为：pNP(AGR ?a3s,3p)- ART(AGR ?a3s,3p) N(AGR ?a3s,3p)n再与N(ROOT dog, AGR 3s)匹配后扩展为：pNP(AGR 3s)- ART(AGR 3s) N(AGR 3s) 句义分析p句义分析的目的是给出句子的含义或意义(meaning)。句子的意义分为：n上下文无关意义n上下文有关意义p“Do you know what gate you are going to?”的意义是什么？p句义分析的作用：n更好地进行翻译：Tom ran the machine.n句法结构消歧