自然语言处理NaturalLanguageProcessingNLP课件.ppt

1、自然语言处理Natural Language Processing(NLP)陈家骏，戴新宇主要内容（1）p自然语言处理概述n什么是自然语言处理n自然语言处理技术的应用n自然语言处理的基本策略和实现方法n自然语言处理的难点n自然语言处理所涉及的学科(http:/ (IBM Model等)n.（基于神经网络的深度学习方法）主要内容（3）所需的前导知识p编译技术p概率与统计参考书籍p宗成庆，统计自然语言处理统计自然语言处理，清华大学出版社，2008p刘群等译，自然语言理解（第二版）自然语言理解（第二版），电子工业出版社，2005p苑春法等译，统计自然语言处理基础统计自然语言处理基础，电子工业出版社，

2、2005p冯志伟等译，自然语言处理综论自然语言处理综论，电子工业出版社，2005p黄昌宁等，语料库语言学语料库语言学，商务印书馆，2002p冯志伟，计算语言学基础计算语言学基础，商务印书馆，2001p余士文，计算语言学概论计算语言学概论，商务印书馆，2003p姚天顺，自然语言理解一种让机器懂得人类语言的研究（第自然语言理解一种让机器懂得人类语言的研究（第2版）版），清华大学出版社，2002p赵铁军等，机器翻译原理机器翻译原理，哈尔滨工业大学出版社，2000p宗成庆等译，统计机器翻译统计机器翻译，电子工业出版社，2012pPeter F. Brown, et al., A Statistical

3、 Approach to MT, Computational Linguistics, 1990,16(2)课程考核pProjectsn提交报告（说明基本做法）和源程序及可运行的程序p期末笔试 自然语言处理概述什么是自然语言处理p充分利用信息将会给人们带来巨大的收益，而大量的信息以自然语言自然语言（英语、汉语等）形式存在。p如何有效有效地获取和利用以自然语言形式自然语言形式出现的信信息？息？n自然语言处理自然语言处理（Natural Language Processing，简称NLP）是指用计算机对语言信息进行处理的方法和技术。p与NLP相近的两个研究领域：n自然语言理解自然语言理解(Natu

4、ral Language Understanding, NLU)：强调对语言含义和意图的深层次解释n计算语言学计算语言学(Computational Linguistics, CL)：强调可计算的语言理论NLP技术的应用p机器翻译p自动摘要p文本分类与信息过滤p信息检索p信息抽取与文本挖掘p情感分析p自动问答p.机器翻译（Machine Translation）p机器翻译（Machine Translation，简称MT）是指利用计算机实现自然语言（英语、汉语等）之间的自动自动翻译。n是最早的计算机应用之一n分为：文本机器翻译和语音机器翻译p机器辅助辅助翻译（Machine Aided Tra

5、nslation或Computer Aided Translation，简称MAT或CAT）n翻译记忆体（Translation Memory，简称TM）n双语对照的文本编辑n.自动摘要（Text Summarization）p利用计算机自动地从原始文档中提取全面准确地反映该文档中心内容的简洁、连贯的短文。p指标：压缩比、. 文本分类（Text Classification）p将一篇文档归于预先给定的一个类别集合中的某一类或某几类。p可用于n图书馆的图书分类n信息过滤n.信息检索（Information Retrieval，IR）p主题相关的文本获取。n基于关键词，从某文档集合中检索出相关的文

6、档。n关键技术：倒排索引、.pgoogle、百度、. 信息抽取（Information Extraction，IE）p主题相关的信息获取。n基于某个主题模板，从非结构化或半结构化的自然语言文本中提取出相关的结构化信息。p对机器翻译、自动问答、数据挖掘（文本挖掘）等提供支持。新华社北京月日电（记者李术峰）: 中国农工民主党第十二届中央常务委员会第一次会议今天在北京召开。会议研究通过了贯彻落实“两会”精神的有关决定，审议通过了中国农工民主党中央年工作要点（草案），并任命了中央副秘书长。农工民主党中央主席蒋正华主持了会议，他说，农工民主党有多名党员作为代表和委员参加了今年的“两会”，各位党员要认真履

7、行代表和委员的职责，开好会，在年的工作中认真贯彻“两会”精神，加强农工民主党的自身建设，推动事业进一步发展，为建设有中国特色社会主义事业作出新的贡献。会前，农工民主党中央邀请参加“两会”的来自全国各省、自治区、直辖市的农工民主党党员进行了联谊活动。信息抽取实例信息抽取实例:会议报道(人民日报1998-03-09)信息抽取的结果会 议 时 间 Time 年3月8日会 议 地 点 Spot 北京会议召集者/主持人Convener个人姓名/团体名称 Name蒋正华机 构 、 职 位 Org/Post主席，农工民主党中央会议名/标题Conf-Title 中国农工民主党第十二届中央常务委员会第一次会议

8、情感分析（Sentiment Analysis或 Opinion Analysis ）p分析文章（评论）对某个对象（社会热点事件、产品或者服务）的态度（正面还是负面）。n政府舆情分析：热点事件发现、预警n企业市场决策：产品意见调查、产品推荐n消费者购买决策n.自动问答（Question Answering，QA）p针对用户提出的问题，给出具体的答案。pApple的Siri、IBM的Watson机器人、百度的“知道”、自然语言处理的主要任务（工作）p语言分析：分析语言表达的结构和含义n词法分析：形态还原、词性标注、命名实体识别、分词（汉语、日语等）等n句法分析：组块分析、结构分析、依存分析n语义

9、分析：词义、句义（逻辑、格关系、.）、篇章（上下文）（指代、实体关系）p语言生成：从某种内部表示生成语言表达p多语言处理（机器翻译、跨语言检索）：语言之间的对应、转换p不同的应用对上述任务有不同的要求。自然语言的分类（基于形态结构）p分析型语言n词形变化很少n没有表示词的语法功能的附加成分，由词序和虚词表示词之间的语法关系n汉语、藏语等p黏着型语言n有词形变化n词的语法意义（功能）由附加成分表达n日语、芬兰语等p屈折型语言n有词形变化n词的语法意义由词的形态变化来表示n英语、德语、法语等p另外，还可以按SVO型（主动宾）、VSO型（动主宾）和SOV 型(主宾动) 分类自然语言处理的实现方法p基

10、于规则的理性方法（Rationalist approach）n基于以规则形式表达的语言知识（词、句法、语义以及转换、生成）进行推理。n强调人对语言知识的理性整理。n受Chomsky主张的人具有先天语言能力观点的影响，主宰19601985p基于语料库的经验方法（Empiricist approach）n以大规模语料库（单语和双语）为语言知识基础。n利用统计学习和基于神经网络的深度学习方法自动获取和运用隐含在语料库中的知识。n学习到的知识体现为一系列模型参数。p混合方法n理性方法的优、缺点p相应的语言学理论基础好p语言知识描述精确p处理效率高p知识获取困难（高级劳动）p系统鲁棒性（适应性）差：不完

11、备的规则系统将导致推理的失败p知识扩充困难，很难保证规则之间的一致性n经验方法的优、缺点p知识获取容易（低级劳动）p系统鲁棒性好：概率大的作为结果p知识扩充容易、一致性容易维护p相应的语言学理论基础差p缺乏对语言学知识的深入描述和利用，过于机械p处理效率低n利用各家之长，相互融合自然语言处理的难点p歧义处理n有限的词汇和规则表达复杂、多样的对象p语言知识的表示、获取和运用p成语和惯用型的处理p对语言的灵活性和动态性的处理n灵活性：同一个意图的不同表达，甚至包含错误的语法等n动态性：语言在不断的变化，如：新词等p上下文和世界知识（常识，语言无关）的利用和处理汉语处理的难点p缺乏计算语言学的句法/

12、语义理论，大都借用基于西方语言的句法/语义理论p词法分析n分词n词性标注难p句法分析n主动词识别难n词法分类与句法功能对应差p语义分析n句法结构与句义对应差n时体态确定难 （汉语无形态变化）p资源（语料库）缺乏自然语言处理所涉及的学科p计算语言学：各种语法、语义理论p计算机科学（包括人工智能、机器学习）p数学：逻辑、概率与统计、信息论等p哲学（认知学）p心理学p. 基于规则的自然语言处理方法 （理性方法，传统方法）概述p强调对语言知识的理性整理（知识工程）p受计算语言学理论指导p基于规则的知识表示和推导（符号计算）p语言处理规则（数据）与程序分离，程序体现为规则语言的解释器！词法分析p形态还原

13、（针对英语、德语、法语等）n把句子中的词还原成基本词形。p词性标注n为句子中的词标上预定义类别集合（标注集）中的类。p命名实体识别n人名n地名n机构名p分词（针对汉语、日语等）n识别出句子中的词。形态还原（英语）p把句子中的词还原成原形，作为词的其它信息（词典、个性规则）的索引。p构词特点n屈折变化：词尾和词形变化，词性不变。如：pstudy, studied,studied,studyingpspeak,spoke,spoken,speakingn派生变化：加前缀和后缀，词性发生变化。如：pfriend,friendly,friendship,.n复合变化：多个单词以某种方式组合成一个词。p

14、还原规则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)(VEN)n*?ed - *? (PAST)(VEN)p英语不规则动词还原nwent - go (PAST)ngone - go (

15、VEN)nsat - sit (PAST) (VEN)形态还原算法1.输入一个单词2.如果词典里有该词，输出该词及其属性，转4，否则，转33.如果有该词的还原规则，并且，词典里有还原后的词，则输出还原后的词及其属性，转4，否则，调用4.如果输入中还有单词，转(1)，否则，结束。Proj. 1 实现一个英语单词还原工具。（词典：http:/ class）nNounsp句法上：可作物主、可有限定词、有复数形式p语义上：人名、地名和物名nVerbsp句法上：作谓语、有几种词形变化p语义上：动作、过程（一系列动作）nAdjectivesp句法上：修饰Nouns等p语义上：性质nAdverbsp句法上：

16、修饰Verbs等p语义上：方向、程度、方式、时间p封闭类（closed class，function words）nDeterminersnPronounsnPrepositionsnConjunctionsnAuxiliary verbsnParticles（if、not、.）nNumeralsp为什么要分类？分类带来的问题？p兼类词n一个词具有两个或者两个以上的词性n英文的Brown语料库中，10.4%的词是兼类词。例如：pThe back doorpOn my backpPromise to back the billn汉语兼类词，例如：p把门锁上， 买了一把锁p他研究.， 研究工作n汉

17、语词的兼类更多？与所采用的分类体系是否有关？词性标注方法p规则方法n词典和规则提供候选词性n消歧规则进行消歧p统计方法n选择最可能的词性n训练用语料库（已标注词性）p基于转换学习的方法n统计学习得到规则n用规则方法进行词性标注汉语分词（切分）p词是语言中最小的能独立运用的单位，也是语言信息处理的基本单位。p分词是指根据某个分词规范，把一个“字”串划分成“词”串。n难以确定何谓汉语的“词”p单字词与语素的界定：猪肉、牛肉p词与短语（词组）的界定：黑板、黑布n信息处理用现代汉语分词规范：GB-13715（1992）n具体应用系统可根据各自的需求制定规范p分词带来的问题n丢失信息、错误的分词、不同的

18、分词规范切分歧义及歧义字段的种类p交集型歧义字段nABC切分成AB/C或A/BCn如：“和平等”p“独立/自主/和/平等/独立/的/原则”p“讨论/战争/与/和平/等/问题”p组合型歧义字段nAB切分成AB或A/Bn如：“马上”p“他/骑/在/马/上”p“马上/过来”p混合型歧义n由交集型歧义和组合型歧义嵌套与交叉而成n如：“得到达”（交集型、组合型）p“我/今晚/得/到达/南京” p“我/得到/达克宁/了 ” p“我/得/到/达克宁/公司/去”南京市长江大桥.南京市长江二桥.p伪歧义与真歧义n伪歧义字段指在任何情况下只有一种切分p“挨批评”只有一种切分p根据歧义字段本身就能消歧n真歧义字段指

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

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

21、Proj. 2 实现一个基于词典与规则的汉语自动分词系统。(词典：http:/ ate the cat的组成分分析SNPVPNAMEJohnVNPateARTNthecatJohn ate the cat的依存分析John ate the catsubobjmod句法分析-组成分分析p句法分析的目的n判断句子的合法性（句子识别）n确定句子的结构（句子中单词相互关联的方式）p基于上下文无关语法（CFG）的表示nCFG能描述大部分的自然语言结构n可以构造高效的基于CFG的句法分析器p通常采用树形结构来表示句法分析的结果优秀语法的特征p通用性n能正确分析的句子的范围p选择性n能判断出错误句子的范围p

22、可理解性n自身的简易程度p*鲁棒性n对不合法句子的容忍度（通用性）：He love her.n通用性与选择性矛盾的处置，如：忽略主谓一致性检查将导致无法区分下面句子的不同含义（歧义）pFlying planes are dangerous.pFlying planes is dangerous.一个简单的基于CFG的英语文法1. S - NP VP2. VP - V NP3. NP - NAME4. NP - ART N5. NAME - John6. V - ate7. ART - the8. N - cat9. .p产生式59属于词法规则，一般由词典、词形还原以及词性标注算法来描述 。p产

23、生式14属于句法规则。基于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由符号

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

25、状态后备状态为空。2. 若当前状态为空，则失败，算法结束，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)

26、(ART ADJ N VP) 1)规则4、5改写7() 4)(V 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改写

27、11(N) 5)(ART ADJ N) 4)(ART ADJ N 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后备状态多，存储效率不高自底向上句法分析p简单的自底向上句法分析效率不高，常常会重复

28、尝试相同的匹配操作（回溯之前已匹配过）。p一种基于图的句法分析技术（Chart Parsing）被提出，它把已经匹配过的结果保存起来，今后需要时可直接使用它们，不必重新匹配。（动态规划）Chart Parsing的数据表示p图（chart）的结点表示句子中词之间的位置数字p非活动边集（chart的核心，常直接就被称为chart）n记录分析中规约成功所得到的所有词法/句法符号p活动边集n未完全匹配的产生式，用加小圆圈标记（）的产生式来表示，如：pNP - ART ADJ NpNP - ART Np待处理表（agenda）n记录等待加入chart的已匹配成功的词法/句法符号p上面的活动边、非活动边

29、以及词法/句法符号都带有“始/终结点”位置信息“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 NPN(2,3)agenda56amouse重复下面的操作，直到agenda为空并且输入中没有下一个词p若agenda为空，则把句子中下一个词的各种词法符号（词性）和它们的位置加入进来，p从agenda中取一个元素（设为C，位置为：p1-p2)p对下面形式

30、的每个规则增加活动边：nX-CX1.Xn，增加一条活动边活动边：X-C X1.Xn，位置为：p1-p2；nX-C，把X加入agenda，位置为：p1-p2p将C作为非活动边非活动边加入到chart的位置p1-p2p对已有活动边已有活动边进行边扩展边扩展n对每个形式为：X-X1. C.Xn的活动边，若它在p0-p1之间，则增加一条活动边活动边：X-X1. C .Xn，位置:p0-p2n对每个形式为： X-X1. Xn C的活动边，若它在p0-p1之间，则把X加入agenda ，位置为：p0-p2Chart Parsing句法分析算法“1 The 2 cat 3 caught 4 a 5 mous

31、e 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. S-NP VP 2. NP-ART N 3. NP-ART ADJ N 4. VP-V 5. VP-V NPN(2,

32、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 mouse 6”的分析过程(算法)1234ThecatcaughtARTNP - ART NNP - ART ADJ N活动

33、边非活动边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. VP-V 5. VP-V NPagenda56amouseNS - NP VPNPVP - V NPVP

34、(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”的分析过程(算法)1234ThecatcaughtARTNP - ART NNP - ART ADJ N活

35、动边非活动边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-ART ADJ N 4. VP-V 5. VP-V NPagenda56amo

36、useNS - 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 - ART NNP - ART ADJ NARTNNP(4,6)S - N

37、P 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 cat 3 caught 4 a 5 mouse 6”的分析过程(

38、算法)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句法分析器。nagenda采用栈or队列？n可能会有无用（不可能用到）的活动边，影响效率。句法分析与逻辑程序设计p逻辑程序设计是把程序组织成一组事实（谓词

39、）和一组推理规则，计算（推理）过程由实现系统自动给出，它基于谓词演算（Predicate Calculus）进行计算。pPROLOG是一个逻辑程序设计语言，在程序中，用子句（clause）描述事实和推理规则，推理过程由PROLOG的执行机制自动完成。p对句法分析而言，n事实：句子中每个词的词性以及词在句子中的位置等n推理规则：文法（产生式）一个基于CFG的PROLOG句法分析器p词典、词形还原以及词性标注结果可表示成事实：nisart(the)nisname(john)nisverb(ate)nisnoun(cat)n.p输入句子“John ate the cat”可表示成事实：nword(j

40、ohn,1,2)nword(ate,2,3)nword(the,3,4)nword(cat,4,5)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(P1,P2),pp(P2,P3)nn(P1,P2):-word(W,P1,P2),isnoun(W)nart(P1,

41、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通过查询谓词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上面的CFG描述了英语的一个子集，同时，它又会生成一些不合法的英语句子，如

42、：nThe student solve the problem.（主谓不一致）nThe teacher disappeared the problem.（不及物动词）一种可能的解决方案增加句法符号和规则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

43、-PnVP-P-V-P-InVP-P-V-P-T NP-SnVP-P-V-P-T NP-P增加句法符号和规则带来的问题p增加了规则的数量和潜在的冗余p类似的规则缺乏关联性p对语言结构描述缺乏深度（表层）基于特征的扩展CFGp不增加原CFG中的句法符号p给每个句法符号增加特征特征（属性），例如：nNP(PER 3,NUM s) /第三人称单数nVP(PER 3,NUM p) /第三人称复数p特征由特征名和特征值构成。一系列特征构成了一个特征特征结构结构（复杂特征集）。p特征值可以是普通值（原子），也可以是另一个特征结构，例如：nNP(AGR（PER 3, NUM s)，可简写为：nNP(AGR

44、3s)p一个特征的特征值可以有多个，表示成：nN(ROOT fish, AGR 3s,3p)p特征值也可以是变量，表示取值可以任意，例如：nNP(AGR ?a) 表示NP的AGR特征值可取任意值p可以对变量形式的特征值限定范围（受限变量），例如：nNP(AGR ?a3s,3p)p同名的变量表示它们的值要相同，例如：nS-NP(AGR ?a) VP(AGR ?a) 表示NP与VP的AGR特征值要一致（取同样的值，主谓一致）p一个规则如果包含特征值为变量的成分，则该规则代表了一组规则（规则模板）。例如，上述规则代表：nS-NP(AGR 3s) VP(AGR 3s)nS-NP(AGR 3p) VP(

45、AGR 3p)n.一个基于特征结构的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一个文法可以表示成一系列特征结构间的约束关系所组成的集合。这样的文法称为合一文法（Unification Grammar）。例如：n特征结构X0、X1和X2之间的约束关系：pX0-X1 X2 (CAT0=S,CAT1=NP,CAT2=VP, AGR0=

46、AGR1=AGR2,VFORM0=VFORM2)n它描述了基于特征的CFG中的一条规则：pS-NP(AGR ?a) VP(AGR ?a)p合一文法为基于特征的CFG文法提供了一个形式描述基础。p特征结构的合一运算构成了合一文法的基本操作，其作用有两个：n检查特征结构间的相容性以确定多个特征结构是否可以合并（规约）n创建新的特征结构（规约的结果）合一运算p特征结构“相容”n(f)表示特征结构的特征f的值n若、为特征结构，对于所有的特征f（属于或）：p若(f)=a，(f)=b，a、b都是原子，和是相容的当且仅当a=bp若(f)、(f)均为特征结构，和是相容的当且仅当(f)与(f)相容（递归）p特征

47、结构“合一运算”：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 3s)与(CAT V, AGR 3p)不能合一p(CAT N,ROOT fish, AGR 3s,3p)与(CAT N, AGR 3s)可以合一为：

48、(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(AGR 3s)n它与ART(ROOT a, AGR 3s)匹配后扩展为：pNP(AGR 3s)- ART(AGR 3s) N(AGR 3s)n若句子中还

49、有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(AGR ?a3s,3p) N(AGR ?a3s,3p)n匹配扩展后为：pNP(AGR ?a3s,3p)- ART(AGR ?a3s,3p) N(A

50、GR ?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先句法后语义n句法语义一体化n完全语义分析（无句法分析）词汇语义p句子的意义由句子中词汇的语义组合而成。句义分析首先需要解决词汇的语义表示和分析。p词汇的语义表示：n义项（义位）n语义类 n义素组合义项（义位）p一个词往