《自然语言处理NaturalLanguageProcessing(NLP).ppt》由会员分享，可在线阅读，更多相关《自然语言处理NaturalLanguageProcessing(NLP).ppt（117页珍藏版）》请在三一文库上搜索。
1、自然语言处理 Natural Language Processing(NLP),主要内容（1）,自然语言处理概述 什么是自然语言处理 自然语言处理的典型应用 自然语言处理的基本任务 自然语言处理的基本策略和实现方法 自然语言处理的难点 自然语言处理所涉及的学科 (http:/ 基于词典和规则的形态还原（英语）、词性标注以及分词（汉语、日语） 基于CFG（上下文无关文法）和扩充的CFG（复杂特征集、合一运算）的句法表示及其分析技术 基于逻辑形式和格语法的句义分析 基于规则的机器翻译 (http:/ 语言模型（N元文法） 分词、词性标注（序列化标注模型） 句法分析（概率上下文无关模型） 文本分类（
2、朴素贝叶斯模型、最大熵模型） 机器翻译 (IBM Model等) （基于神经网络的深度学习方法）,主要内容（3）,所需的前导知识,编译技术 概率与统计,参考书籍,宗成庆，统计自然语言处理，清华大学出版社，2008 刘群等译，自然语言理解（第二版），电子工业出版社，2005 苑春法等译，统计自然语言处理基础，电子工业出版社，2005 冯志伟等译，自然语言处理综论，电子工业出版社，2005 黄昌宁等，语料库语言学，商务印书馆，2002 冯志伟，计算语言学基础，商务印书馆，2001 余士文，计算语言学概论，商务印书馆，2003 姚天顺，自然语言理解一种让机器懂得人类语言的研究（第2版），清华大学出版
3、社，2002 赵铁军等，机器翻译原理，哈尔滨工业大学出版社，2000 宗成庆等译，统计机器翻译，电子工业出版社，2012 Peter F. Brown, et al., A Statistical Approach to MT, Computational Linguistics, 1990,16(2),课程考核,Projects 提交报告（说明基本做法）和源程序及可运行的程序 期末笔试,自然语言处理概述,什么是自然语言处理,充分利用信息将会给人们带来巨大的收益，而大量的信息以自然语言（英语、汉语等）形式存在。 如何有效地获取和利用以自然语言形式出现的信息？ 自然语言处理（Natural La
4、nguage Processing，简称NLP）是指用计算机对自然语言信息进行处理的方法和技术。 与NLP相近的两个研究领域： 自然语言理解(Natural Language Understanding, NLU)：强调对语言含义和意图的深层次解释 计算语言学(Computational Linguistics, CL)：强调可计算的语言理论,NLP技术的典型应用,机器翻译 自动摘要 文本分类与信息过滤 信息检索 自动问答 信息抽取与文本挖掘 情感分析 ,机器翻译（Machine Translation）,机器翻译（Machine Translation，简称MT）是指利用计算机实现自然语言之
5、间的自动翻译。 是最早的计算机应用之一 分为：文本机器翻译和语音机器翻译 机器辅助翻译（Machine Aided Translation或Computer Aided Translation，简称MAT或CAT） 翻译记忆体（Translation Memory，简称TM） 双语对照的文本编辑 .,自动摘要（Text Summarization）,利用计算机自动地从原始文档中提取全面、准确地反映该文档中心内容的简洁、连贯的短文。 应对信息过载 分为单文档摘要和多文档摘要,文本分类（Text Classification）,将一篇文档归于预先给定的一个类别集合中的某一类或某几类。 图书馆的图书
6、分类 信息过滤 ,信息检索（Information Retrieval，IR）,基于关键词，从某文档集合中检索出相关的文档。 google、百度、. 主题相关的文本获取。,自动问答（Question Answering，QA）,针对用户提出的问题，给出具体的答案。 Apple的Siri、IBM的Watson机器人、百度的“知道”、 提高信息获取的效率,信息抽取（Information Extraction，IE）,基于某个主题模板，从非结构化或半结构化的自然语言文本中提取出相关的结构化信息。 主题相关的信息获取。 对机器翻译、自动问答、数据挖掘（文本挖掘）等提供支持。,新华社北京月日电（记者李
7、术峰）: 中国农工民主党第十二届中央常务委员会第一次会议今天在北京召开。 会议研究通过了贯彻落实“两会”精神的有关决定，审议通过了中国农工民主党中央年工作要点（草案），并任命了中央副秘书长。 农工民主党中央主席蒋正华主持了会议，他说，农工民主党有多名党员作为代表和委员参加了今年的“两会”，各位党员要认真履行代表和委员的职责，开好会，在年的工作中认真贯彻“两会”精神，加强农工民主党的自身建设，推动事业进一步发展，为建设有中国特色社会主义事业作出新的贡献。 会前，农工民主党中央邀请参加“两会”的来自全国各省、自治区、直辖市的农工民主党党员进行了联谊活动。,信息抽取实例:会议报道(人民日报1998-
8、03-09),信息抽取的结果,情感分析（Sentiment Analysis或 Opinion Analysis ）,分析文章（评论）对某个对象（社会热点事件、产品或者服务）的态度（正面还是负面）。 政府舆情分析：热点事件发现、预警 企业市场决策：产品意见调查、产品推荐 消费者购买决策 , 只要处理对象涉及自然语言的都需要NLP！,自然语言处理的基本任务,语言分析：分析语言表达的结构和含义 词法分析：形态还原、词性标注、命名实体（人名、地名、机构名）识别、分词（汉语、日语等）等 句法分析：组块分析、结构分析、依存分析 语义分析：词义、句义（逻辑、格关系、）、篇章（上下文）（指代、实体关系、）
9、语言生成：从某种内部表示生成语言表达 词、句子、篇章的生成 多语言处理（机器翻译、跨语言检索）：语言之间的对应、转换 不同的应用对上述任务有不同的要求。,自然语言处理的实现方法,基于规则的理性方法（Rationalist approach） 基于以规则形式表达的语言知识（词、句法、语义以及转换、生成）进行符号推理，从而实现信息处理。 强调人对语言知识的理性整理。 受Chomsky主张的人具有先天语言能力观点的影响，主宰19601985 基于语料库的经验方法（Empiricist approach） 以大规模语料库（单语和双语）为语言知识基础。 利用统计学习和基于神经网络的深度学习方法自动获取隐
10、含在语料库中的知识，学习到的知识体现为一系列模型参数。 基于学习到的参数和相应的模型进行语言信息处理。,混合方法 理性方法的优、缺点 相应的语言学理论基础好 语言知识描述精确 处理效率高 知识获取困难（高级劳动） 系统鲁棒性差：不完备的规则系统将导致推理的失败 知识扩充困难，很难保证规则之间的一致性 经验方法的优、缺点 知识获取容易（低级劳动） 系统鲁棒性好：概率大的作为结果 知识扩充容易、一致性容易维护 相应的语言学理论基础差 缺乏对语言学知识的深入描述和利用，过于机械 处理效率低 利用各家之长，相互融合?,自然语言的分类（基于形态结构）,分析型语言 没有或很少有词形变化 没有表示词的语法功
11、能的附加成分，由词序和虚词表示词之间的语法关系 如：汉语 黏着型语言 有词形变化 词的语法意义（功能）由附加成分表达 如：日语 屈折型语言 有词形变化 词的语法意义由词的形态变化来表示 如：英语 另外，还可以按SVO型（主动宾）、VSO型（动主宾）和SOV 型(主宾动) 分类,自然语言处理的难点,歧义处理 有限的词汇和规则表达复杂、多样的对象 语言知识的表示、获取和运用 成语和惯用型的处理 对语言的灵活性和动态性的处理 灵活性：同一个意图的不同表达，甚至包含错误的语法等 动态性：语言在不断的变化，如：新词等 上下文和常识知识（与语言无关）的利用和处理,汉语处理的难点,缺乏计算语言学的句法/语义
12、理论，大都借用基于西方语言的句法/语义理论 词法分析 分词 词性标注难 句法分析 主动词识别难（特别对于流水句） 词法分类与句法功能对应差（例如：他喜欢走） 语义分析 句法结构与句义对应差（例如：老头晒太阳） 时体态确定难 （汉语无形态变化） 资源（语料库）缺乏,自然语言处理所涉及的学科,语言学：各种语法、语义理论 计算机科学（包括人工智能、机器学习） 数学：逻辑、概率与统计、信息论等 哲学（认知学） 心理学 ,基于规则的自然语言处理方法 （理性方法，传统方法）,概述,强调对语言知识的理性整理（知识工程） 受计算语言学理论指导 基于规则的知识表示和推导（符号计算） 语言处理规则（数据）与程序分
13、离，程序体现为规则语言的解释器！,词法分析,形态还原（针对英语、德语、法语等） 把句子中的词还原成它们的基本词形。 词性标注 为句子中的词标上预定义类别集合（标注集）中的类。 命名实体识别 人名 地名 机构名 分词（针对汉语、日语等） 识别出句子中的词。,形态还原（英语）,把句子中的词还原成原形，作为词的其它信息（词典、个性规则）的索引。 构词特点 屈折变化：词尾和词形变化，词性不变。如： study, studied,studied,studying speak,spoke,spoken,speaking 派生变化：加前缀和后缀，词性发生变化。如： friend,friendly,frien
14、dship,. 复合变化：多个单词以某种方式组合成一个词。 还原规则 通用规则：变化有规律 个性规则：变化无规律,形态还原规则举例,英语“规则动词”还原 *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),英语不规则动词
15、还原 went - go (PAST) gone - go (VEN) sat - sit (PAST) (VEN),形态还原算法,输入一个单词 如果词典里有该词，输出该词及其属性，转4，否则，转3 如果有该词的还原规则，并且，词典里有还原后的词，则输出还原后的词及其属性，转4，否则，调用 如果输入中还有单词，转(1)，否则，结束。 Proj. 1 实现一个英语单词还原工具。 （词典：http:/ 标注体系的确定 标注方法,词性标注体系,词的分类 按形态和句法功能（句法相关性） 按表达的意思（语义相关性） 兼顾上述二者,英语词的分类,开放类（open class） Nouns 句法上：可作物主
16、、可有限定词、有复数形式 语义上：人名、地名和物名 Verbs 句法上：作谓语、有几种词形变化 语义上：动作、过程（一系列动作） Adjectives 句法上：修饰Nouns等 语义上：性质 Adverbs 句法上：修饰Verbs等 语义上：方向、程度、方式、时间,封闭类（closed class，function words） Determiners Pronouns Prepositions Conjunctions Auxiliary verbs Particles（if、not、.） Numerals,为什么要分类？分类带来的问题？ 兼类词 一个词具有两个或者两个以上的词性 英文的Br
17、own语料库中，10.4%的词是兼类词。例如： The back door On my back Promise to back the bill 汉语兼类词，例如： 把门锁上， 买了一把锁 他研究.， 研究工作 汉语词的兼类更多？与所采用的分类体系是否有关？,词性标注方法,规则方法 词典和规则提供候选词性 消歧规则进行消歧 统计方法 选择最可能的词性 训练用语料库（已标注词性） 基于转换学习的方法 统计学习得到规则 用规则方法进行词性标注,汉语分词（切分）,词是语言中最小的能独立运用的单位，也是语言信息处理的基本单位。 分词是指根据某个分词规范，把一个“字”串划分成“词”串。 问题：难以确定
18、何谓汉语的“词” 单字词与语素的界定：猪肉、牛肉 词与短语（词组）的界定：黑板、黑布 信息处理用现代汉语分词规范：GB-13715（1992） 具体应用系统可根据各自的需求制定规范 分词带来的问题 丢失信息、错误的分词、不同的分词规范,切分歧义及歧义字段的种类,交集型歧义字段 ABC切分成AB/C或A/BC 如：“和平等” “独立/自主/和/平等/独立/的/原则” “讨论/战争/与/和平/等/问题” 组合型歧义字段 AB切分成AB或A/B 如：“马上” “他/骑/在/马/上” “马上/过来” 混合型歧义 由交集型歧义和组合型歧义嵌套与交叉而成 如：“得到达”（交集型、组合型） “我/今晚/得/
19、到达/南京” “我/得到/达克宁/了 ” “我/得/到/达克宁/公司/去”,南京市长江大桥.,南京市长江二桥.,伪歧义与真歧义 伪歧义字段指在任何情况下只有一种切分 “挨批评”只有一种切分 根据歧义字段本身就能消歧 真歧义字段指在不同的情况下有多种切分 “从小学”可以有多种切分： “从小/学” ，如：“从小/学/电脑” （“从小”是切分成“从小”还是“从/小”要根据分词规范！） “从/小学”，如：“他/从/小学/毕业/后” 根据歧义字段的上下文来消歧,分词方法,一般通过分词词典和分词规则库进行分词。主要方法有： 正向最大匹配(FMM)或逆向最大匹配(RMM) 从左至右(FMM)或从右至左(RM
20、M)，取最长的词 “幼儿园 地 节目”或“幼儿 园地 节目” 双向最大匹配 分别采用FMM和RMM进行分词 如果结果一致，则认为成功；否则， 采用消歧规则进行消歧（交集型歧义）： 正向最大、逆向最小匹配 发现组合型歧义 逐词遍历匹配 在全句中取最长的词，去掉之，对剩下字符串重复该过程 设立切分标记 收集词首字和词尾字，把句子分成较小单位，再用某些方法切分 全切分 获得所有可能的切分，选择最大可能的切分,基于规则的歧义字段消歧方法,利用歧义字串、前驱字串和后继字串的句法、语义和语用信息： 句法信息 “阵风”：根据前面是否有数词来消歧。“一/阵/风/吹/过/来”、“今天/有/阵风” 语义信息 “了
21、解”：“他/学会/了/解/数学/难题”（“难题”一般是“解”而不是“了解”，另外，还有“学会”) 语用信息 “拍卖”：“乒乓球拍卖完了”，要根据场景（上下文）来确定 规则的粒度 基于具体的词（个性规则） 基于词类、词义类（共性规则） Proj. 2 实现一个基于词典与规则的汉语自动分词系统。 (词典：http:/ 词、短语以及它们之间的关系 句法分析任务的类型 组块分析（浅层句法分析、部分句法分析）： 基本短语（非递归的核心成分）识别 组成分分析（结构分析，完全句法分析） 词如何构成短语、短语如何构成句子 依存分析 词之间的依赖（或支配）关系,“John ate the cat“的组成分分析,
22、S,NP,VP,NAME,John,V,NP,ate,ART,N,the,cat,“John ate the cat“的依存分析,John ate the cat,sub,obj,mod,句法分析-组成分分析,句法分析的目的 判断句子的合法性（句子识别） 确定句子的结构（句子中单词相互关联的方式） 基于上下文无关语法（CFG）的表示 CFG能描述大部分的自然语言结构 可以构造高效的基于CFG的句法分析器 通常采用树形结构来表示句法分析的结果,优秀语法的特征,通用性 能正确分析的句子的范围 选择性 能判断出错误句子的范围 可理解性 自身的简易程度 *鲁棒性 对不合法句子的容忍度（通用性）：He
23、love her. 通用性与选择性矛盾的处置，如：忽略主谓一致性检查将导致无法区分下面句子的不同含义（歧义） Flying planes are（be） dangerous. Flying planes is（be） dangerous.,一个简单的基于CFG的英语语法,1. S - NP VP 2. VP - V NP 3. NP - NAME 4. NP - ART N 5. NAME - John 6. V - ate 7. ART - the 8. N - cat 9. 产生式59属于词法规则，一般由词典、词形还原以及词性标注算法来描述 。 产生式14属于句法规则。,基于CFG的分析器
24、,自顶向下 利用产生式，从S开始，尝试将S改写/推导成与输入句子相匹配的终结符号序列。 自底向上 利用产生式，尝试将输入句子与产生式右部进行匹配，最后规约到S。 回溯 在改写或规约的某一步可能有多个产生式供选择。 从一个错误的尝试（改写或规约）返回，进行下一个尝试。 保留改写或规约的历史 回溯需要 输出正确的分析结果也需要,一个简单的自顶向下句法分析算法,语法 1. S - NP VP 2. NP - ART N 3. NP - ART ADJ N 4. VP - V 5. VP - V NP 位置计数器 1 The 2 dogs 3 cried 4 状态 由符号表和当前位置构成，如：(NP
25、VP) 1) 表示从位置1开始寻找NP，且NP后面是VP。初始状态为： (S) 1) 分为当前状态和后备状态。 状态转换 当前状态的符号表的第一个符号是词法符号（词性），并且句子中当前词属于该词性，则删除符号表中第一个符号，并更新当前位置(加1)，得到新的当前状态。 当前状态的符号表的第一个符号是句法符号，则依据语法获得所有以该符号为左部的产生式，用它们的右部替换符号表中的该符号，从而得到一批新的状态，选择其中一个作为新的当前状态，其它作为后备状态。 回溯 从后备状态中取一个作为当前状态，继续分析,算法 1. 取 (S) 1)作为当前状态（初始状态），后备状态为空。 2. 若当前状态为空，则失
26、败，算法结束， 3. 否则，若当前状态的符号表为空， (1)位置计数器值处于句子末尾，则成功，算法结束 (2)位置计数器值处于句子中间，转5 4. 否则，进行状态转换，若转换成功，则转2 5. 否则，回溯，转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
27、. VP-V NP,搜索策略,深度优先 后备状态采用“栈”结构 后备状态少，存储效率高 面临“左递归”问题 广度优先 后备状态采用“队列”结构 后备状态多，存储效率不高,自底向上句法分析,简单的自底向上句法分析效率不高，常常会重复尝试相同的匹配操作（回溯之前已匹配过）。 一种基于图的句法分析技术（Chart Parsing）被提出，它把已经匹配过的结果保存起来，今后需要时可直接使用它们，不必重新匹配。（动态规划）,Chart Parsing的数据表示,图（chart）的结点表示句子中词之间的位置数字 非活动边集（chart的核心，常直接就被称为chart） 记录分析中规约成功所得到的所有词法/
28、句法符号 活动边集 未完全匹配的产生式，用加小圆圈标记（）的产生式来表示，如： NP - ART ADJ N NP - ART N 待处理表（agenda） 记录等待加入chart的已匹配成功的词法/句法符号 上面的活动边、非活动边以及词法/句法符号都带有“始/终结点”位置信息,“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-
29、V NP,N(2,3),agenda,5,6,a,mouse,重复下面的操作，直到agenda为空并且输入中没有下一个词 若agenda为空，则把句子中下一个词的各种词法符号（词性）和它们的位置加入进来， 从agenda中取一个元素（设为C，位置为：p1-p2) 对下面形式的每个规则增加活动边： X-CX1.Xn，增加一条活动边：X-C X1.Xn，位置为：p1-p2； X-C，把X加入agenda，位置为：p1-p2 将C作为非活动边加入到chart的位置p1-p2 对已有活动边进行边扩展 对每个形式为：X-X1. C.Xn的活动边，若它在p0-p1之间，则增加一条活动边：X-X1. C .
30、Xn，位置:p0-p2 对每个形式为： X-X1. Xn C的活动边，若它在p0-p1之间，则把X加入agenda ，位置为：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. VP-V NP,ART(1,2),agenda,5,6,a,mouse,“1 The 2 cat 3 c
31、aught 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,ART,NP - ART N,NP - ART ADJ N,活动边,非活动边,1. S
32、-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,V(3,4),S - NP VP,
33、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
34、,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(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. N
35、P-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,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,a
36、genda,5,6,a,mouse,N,S - NP VP,NP,VP - V NP,V,VP,N(5,6),S,NP - 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
37、- 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 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
38、 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,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,AR
39、T,N,S - NP VP,NP,VP,S(1,6),S,Proj. 3 实现一个基于简单英语语法的chart句法分析器。 agenda采用栈or队列？ 可能会有无用（不可能用到）的活动边，影响效率。,句法分析与逻辑程序设计,逻辑程序设计是把程序组织成一组事实（谓词）和一组推理规则，计算（推理）过程由实现系统自动给出，它基于谓词演算（Predicate Calculus）进行计算。 PROLOG是一个逻辑程序设计语言，在程序中，用子句（clause）描述事实和推理规则，推理过程由PROLOG的执行机制自动完成。 对句法分析而言， 事实：句子中每个词的词性以及词在句子中的位置等 推理规则：文法（
40、产生式）,一个基于CFG的PROLOG句法分析器,词典、词形还原以及词性标注结果可表示成事实： isart(the) isname(john) isverb(ate) isnoun(cat) 输入句子“John ate the cat”可表示成事实： word(john,1,2) word(ate,2,3) word(the,3,4) word(cat,4,5),语法规则可表示成推理规则： 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)
41、,np(P2,P3) vp(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),通过查询谓词s(1,5)的真假来识别句子“John ate the cat”： ?- s(1,5) 标准PROLOG的处理策略与深度优先的
42、自顶向下分析方法一致。,传统CFG在描述自然语言时存在的问题,1. S - NP VP 4. VP - V 2. NP - ART N 5. VP - V NP 3. NP - ART ADJ N 上面的CFG描述了英语的一个子集，同时，它又会生成一些不合法的英语句子，如： The student solve the problem.（主谓不一致） The teacher disappeared the problem.（不及物动词）,一种可能的解决方案 增加句法符号和规则,把NP分为NP-S和NP-P；把VP分成VP-S和VP-P： S-NP-S VP-S S-NP-P VP-P 把N分成N
43、-S和N-P： NP-S-ART N-S NP-S-ART ADJ N-S NP-P-ART N-P NP-P-ART ADJ N-P 把V分成V-S-I、V-S-T、V-P-I和V-P-T： VP-S-V-S-I VP-S-V-S-T NP-S VP-S-V-S-T NP-P VP-P-V-P-I VP-P-V-P-T NP-S VP-P-V-P-T NP-P,增加句法符号和规则带来的问题,增加了规则的数量和潜在的冗余 类似的规则缺乏关联性 对语言结构描述缺乏深度（表层）,基于特征的扩展CFG,不增加原CFG中的句法符号 给每个句法符号增加特征（属性），例如： NP(PER 3,NUM s)
44、 /第三人称单数 VP(PER 3,NUM p) /第三人称复数 特征由特征名和特征值构成。一系列特征构成了一个特征结构（复杂特征集）。 特征值可以是普通值（原子），也可以是另一个特征结构，例如： NP(AGR（PER 3, NUM s)，可简写为： NP(AGR 3s) 一个特征的特征值可以有多个，表示成： N(ROOT fish, AGR 3s,3p),特征值也可以是变量，表示取值可以任意，例如： NP(AGR ?a) 表示NP的AGR特征值可取任意值 可以对变量形式的特征值限定范围（受限变量），例如： NP(AGR ?a3s,3p) 同名的变量表示它们的值要相同，例如： S-NP(AGR
45、 ?a) VP(AGR ?a) 表示NP与VP的AGR特征值要一致（取同样的值，主谓一致） 一个规则如果包含特征值为变量的成分，则该规则代表了一组规则（规则模板）。例如，上述规则代表： S-NP(AGR 3s) VP(AGR 3s) S-NP(AGR 3p) VP(AGR 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)
46、NP,合一文法,一个文法可以表示成一系列特征结构间的约束关系所组成的集合，这样的文法称为合一文法（Unification Grammar，UG），它为基于特征的CFG文法提供了一个形式描述基础。 例如： UG中特征结构X0、X1和X2之间的约束关系： X0-X1 X2 (CAT0=S,CAT1=NP,CAT2=VP, AGR0=AGR1=AGR2,VFORM0=VFORM2) 可以描述下面的一条基于特征的CFG中的规则： S-NP(AGR ?a) VP(AGR ?a) 特征结构的合一运算构成了合一文法的基本操作，其作用有两个： 检查特征结构间的相容性以确定多个特征结构是否可以合并（规约） 创建新的特征结构（规约的结果）,合一运算,特征结构“相容” (f)表示特征结构的特征f的值 若、为特征结构，对于所有的特征f（属于或）： 若(f)=a，(f)=b，a、b都是原子，和是相容的当且仅当a=b 若(f)、(f)均为特征结构，和是相容的当且仅当(f)与(f)相容（递归） 特征结构“合一运算”： 如果a、b都是原子,若a=b，则ab=a，否则ab= 若、均为特征结构，则 若(f)=v，但(f)未定义，则f=v属于 若(f)=v，但(f)未定义，则f=v属于 若(f)=v1，(f)=v2，且v1与v2相容，则f=