北京大学人工智能.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Lecture 10:Natural Language Processing,2026/3/4 周三,2,大纲,简介,语言处理中的知识,歧义,模型和算法,语言、思维和理解,学科现状与近期发展,语言处理简史,句法分析,统计方法,2026/3/4 周三,3,自然语言,Dave Bowman:Open the pod bay doors,HAL.,HAL:Im sorry Dave.Im afraid I cant do that.,2026/3/4 周三,4,语言处理中的知识,自然语言处理,把处理口语和书面语（统称为,“,语言,”,）的计算技术称为语音和语言处理，简称自然语言处理,自然语言处理和其他处理系统的区别,是否使用语言知识,例如：,unix,系统中的,wc,应用程序,wc,用来计算文本文件中的字节数、词数或行数,2026/3/4 周三,5,语言处理中的知识,Open the pod bay doors,HAL.,I,m sorry Dave.I,m afraid I can,t do that.,语音学,（,phonetics,）和,音系学,（,phonology,）的知识：,帮助我们建立词如何在话语中发音的模型,2026/3/4 周三,6,语言处理中的知识,Open the pod bay,doors,HAL.,I,m,sorry Dave.,I,m,afraid I,can,t,do that.,形态学,（,morphologic,）方面的知识：,能够产生并识别单词的这样或那样的变体，需要形态学方面的知识，这些知识能够反映关于上下文中词的形态和行为的有关信息。,2026/3/4 周三,7,语言处理中的知识,Open the pod bay doors,HAL.,I,m sorry Dave.I,m afraid I can,t do that.,I,m I do,，,sorry that afraid Dave I,m can,t.,句法,（,syntax,）：关于组词成句的知识。,2026/3/4 周三,8,语言处理中的知识,Open the pod bay doors,HAL.,I,m sorry Dave.I,m afraid I can,t do that.,词汇语义学,（,lexical semantics,）：,为了理解,Dave,的请求事实上是关于要求关闭分离舱门的一个命令，而不是讲关于当天中饭的菜单的事情，就要有复合词的语义知识、词汇语义学的知识。,2026/3/4 周三,9,语言处理中的知识,Open the pod bay doors,HAL.,I,m sorry,Dave.,I,m afraid,I can,t do that.,这种礼貌和委婉语言的用法属于,语用学,（,pragmatics,）的研究领域。,2026/3/4 周三,10,语言处理中的知识,Open the pod bay doors,HAL.,I,m sorry Dave.I,m afraid I can,t,do that,.,正确地把这样的会话组织成结构，需要,话语规约,（,discourse convention,）的知识。,2026/3/4 周三,11,语言处理中的知识,语音学与音系学,研究语言的语音,形态学,研究词的有意义的组合,句法学,研究词与词之间的结构关系,语义学,研究意义,语用学,研究如何用语言来达成一定的目的,话语学,研究大于段的语言单位,2026/3/4 周三,12,歧义,语言信息处理的绝大多数或者全部研究都可以看成是在其中某个层面上的消解歧义,I made her duck,I cooked waterfowl for her.,（我给她烹饪鸭子）,I cooked waterfowl belonging to her.,（我烹饪属于她的鸭子）,I created the(plaster?)duck she owns.,（我把她的石膏,(?),鸭子作了创新）,I caused her to quickly lower her head or body.,（我使她很快地把她的头或身体放低一些）,I waved my magic wand and turned her into undifferentiated waterfowl.,（我挥动魔杖把她变成了一只人们一点儿也看不出破绽的鸭子）,2026/3/4 周三,13,模型和算法,状态机（,state machine,）,包括状态、状态之间的转移、输入表示等,形式规则系统（,formal rule system,）,正则语法、正则关系、上下文无关语法,逻辑（,logic,）,逻辑表达方法是处理语义学、语用学和话语分析等方面知识的选择工具,概率论（,probability theory,）,其他的各种模型都可以使用概率得到进一步提高,也是一种机器学习（,machine learning,）的模型,2026/3/4 周三,14,语言、思维和理解,图灵测试,计算机对于语言的使用情况来作为判断计算机是否能进行思维的依据,参加测试者：两个人，一台计算机,ELIZA,（,1966,年）,用户：你看起来有些像我的父亲,ELIZA,：你认为我那些特点像你的父亲呢？,2026/3/4 周三,15,学科现状与近期发展,目前的研究领域,信息检索,机器翻译,文语转换,近期发展,数字图书馆,电子学习,残疾人帮助,2026/3/4 周三,16,语言信息处理简史,基础研究：,20,世纪,40,年代,50,年代,两个阵营：,1957,年,1970,年,四个范型：,1970,年,1983,年,经验主义和有限状态模型的复苏：,1983,年,1993,年,不同领域的合流：,1994,年,2026/3/4 周三,17,基础研究：,20,世纪,40,年代,50,年代,自动机的研究,图灵（,Turing,）提出了,自动机理论,现代计算机科学的基础,McCulloch-Pitts,的神经元（,neuron,）理论,Kleene,关于有限自动机和正则表达式的研究,Shannon,把离散马尔可夫过程的概率模型应用于描述语言的自动机,Chomsky,把有限状态自动机作为一种工具来刻画语言的语法，把有限状态语言定义为由有限状态语法生成的语言,2026/3/4 周三,18,基础研究：,20,世纪,40,年代,50,年代,概率或信息论模型的研究,Shannon,用于语音和语言处理的概率算法的研制,把通过诸如通信信道或声学语音这样的媒介传输语言的行为比喻为噪声信道（,noisy channel,）或解码（,decoding,）。,利用术语,“,熵,”,（,entropy,）来作为测量信道的信息能力或者语言的信息量的一种方法。,2026/3/4 周三,19,两个阵营：,1957,年,1970,年,符号派（,symbolic,）,Chomsky,等形式语言理论和生成句法研究,人工智能的研究,随机派（,stochastic,）,贝叶斯方法开始用于解决最优字符识别问题,2026/3/4 周三,20,四个范型：,1970,年,1983,年,随机范型（,stochastic paradigm,）,隐马尔可夫模型和比喻为噪声信道与解码的模型,基于逻辑的范型（,logic-based paradigm,）,基于自然语言理解的范型（,Natural Language Understanding,）,话语模型范型（,discourse model paradigm,）,2026/3/4 周三,21,经验主义和有限状态模型的复苏：,1983,年,1993,年,过去,chomsky,对于,Skinner,的,“,言语行为,”,（,Verbal Behavior,）的很有影响的评论在这时遭到了理论上的反对,受,IBM,的,Thomas J.Watson,研究中心的语音识别概率模型的影响，提出了语音和语言处理的概率模型。,2026/3/4 周三,22,不同领域的合流：,1994,年,概率和数据驱动的方法几乎成为了自然语言处理的标准方法,由于计算机的速度和存储量的增加，使得在语音和语言处理的一些子领域，有可能进行商品化的开发,Web,的发展使得进一步加强基于语言的信息检索和信息抽取的需求变得更加突出,2026/3/4 周三,23,主要的会议和杂志,ACL,（,A,ssociation for,C,omputational,L,inguistics,）,美国计算语言学会,COLING,（,International Conference on Computational Linguistics,）,国际计算语言学会议,句法分析,2026/3/4 周三,25,内容提要,什么是句法分析,与形式语言句法分析的比较,上下文无关语法的分析策略,自顶向下分析法,自底向上分析法,左角分析法,2026/3/4 周三,26,内容提要（续）,上下文无关语法的分析算法,移进归约算法,Marcus,确定性分析算法,CYK,算法,Earley,算法,Tomita,算法,Chart,算法,概率上下文无关语法,组块分析与部分分析,2026/3/4 周三,27,什么是句法分析,句法分析（,Parsing,）和句法分析器（,Parser),句法分析是从单词串得到句法结构的过程；,不同的语法形式，对应的句法分析算法也不尽相同；,由于短语结构语法（特别是上下文无关语法）应用得最为广泛，因此以短语结构树为目标的句法分析器研究得最为彻底；,很多其他形式语法对应的句法分析器都可以通过对短语结构语法的句法分析器进行简单的改造得到。,本讲将主要介绍上下文无关语法的句法分析器。,2026/3/4 周三,28,与形式语言句法分析的比较,形式语言一般是人工构造的语言，是一种确定性的语言，即对于语言中的任何一个句子，只有唯一的一种句法结构是合理的，即使语法本身存在歧义，也往往通过人为的方式规定一种合理的解释。,如程序语言中的,if,thenif,then,else,结构，往往都人为规定,else,子句与最接近的,if,子句配对；,而在自然语言中，歧义现象是天然地大量存在着的，而且这些歧义的解释往往都有可能是合理的，因此，对歧义现象的处理是自然语言句法分析器最本质的要求。,由于要处理大量的歧义现象，导致自然语言句法分析器的复杂程度远高于形式语言的句法分析器。,2026/3/4 周三,29,句法结构歧义的消解,人们正常交流中所使用的语言，放在特定的环境下看，一般是没有歧义的，否则人们将无法交流（某些特殊情况如幽默或双关语除外）,如果不考虑语言所处的环境和语言单位的上下文，将会发现语言的歧义现象无所不在；,结论：一般来说，语言单位的歧义现象在引入更大的上下文范围或者语言环境时总是可以被被消解的。句法分析的核心任务就是消解一个句子在句法结构上的歧义。,2026/3/4 周三,30,句法结构的歧义消解（续）,我是县长。,我是县长派来的。,咬死了猎人的狗跑了。,就是这条狼咬死了猎人的狗。,小王和小李的妹妹结婚了。,小王和小李的妹妹都结婚了。,2026/3/4 周三,31,例子语法,小王和小李的妹妹结婚了,2026/3/4 周三,32,例子分析结果之一,2026/3/4 周三,33,例子分析结果之二,2026/3/4 周三,34,另一个例子,我是县长派来的,2026/3/4 周三,35,另一个例子分析结果,2026/3/4 周三,36,句法分析的基本策略,句法分析通常采用的策略有：,自顶向下分析法；,自底向上分析法；,左角分析法；,其他策略。,2026/3/4 周三,37,上下文无关语法的分析算法,常见的上下文无关语法的句法分析算法：,CYK,算法；,移进归约算法；,Marcus,确定性分析算法；,Earley,算法；,Tomita,算法（,GLR,算法、富田算法）；,Chart,算法（图分析算法、线图分析算法）；,2026/3/4 周三,38,自顶向下和自低向上分析法,1,句法分析的过程也可以理解为句法树的构造过程,所谓自顶向下分析法也就是先构造句法树的根结点，再逐步向下扩展，直到叶结点；,所谓自底向上分析法也就是先构造句法树的叶结点，再逐步向上合并，直到根结点。,2026/3/4 周三,39,自顶向下和自低向上分析法,2,自顶向下的方法又称为基于预测的方法,，也就是说，这种方法是先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环节上预期出了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所,“,反驳,”,，那就说明待分析的字符串不可能是一个合法的句子，分析失败。,自底向上的方法也叫基于归约的方法,。就是说，这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层归约为可能的成分。如果整个待分析字符串被归约为开始符号,S,，那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串归约为句子的方案，那么就需要回溯。,2026/3/4 周三,40,自顶向下分析法示例,1,2026/3/4 周三,41,自顶向下分析法示例,2,2026/3/4 周三,42,自顶向下分析法示例,3,2026/3/4 周三,43,自顶向下分析法示例,4,2026/3/4 周三,44,自顶向下分析法示例,5,2026/3/4 周三,45,自顶向下分析法示例,6,2026/3/4 周三,46,自顶向下分析法示例,7,2026/3/4 周三,47,自顶向下分析法示例,8,2026/3/4 周三,48,自顶向下分析法示例,9,2026/3/4 周三,49,自顶向下分析法示例,10,2026/3/4 周三,50,自顶向下分析法示例,11,2026/3/4 周三,51,自顶向下分析法示例,12,2026/3/4 周三,52,自顶向下分析法示例,13,2026/3/4 周三,53,自顶向下分析法示例,14,2026/3/4 周三,54,自顶向下分析法示例,15,2026/3/4 周三,55,自顶向下分析法示例,16,2026/3/4 周三,56,自顶向下分析法示例,17,2026/3/4 周三,57,自顶向下分析法示例,18,2026/3/4 周三,58,自顶向下分析法示例,19,2026/3/4 周三,59,自顶向下分析法示例,20,2026/3/4 周三,60,自底向上分析法示例,1,2026/3/4 周三,61,自底向上分析法示例,2,2026/3/4 周三,62,自底向上分析法示例,3,2026/3/4 周三,63,自底向上分析法示例,4,2026/3/4 周三,64,自底向上分析法示例,5,2026/3/4 周三,65,自底向上分析法示例,6,2026/3/4 周三,66,自底向上分析法示例,7,2026/3/4 周三,67,自底向上分析法示例,8,2026/3/4 周三,68,自底向上分析法示例,9,2026/3/4 周三,69,自底向上分析法示例,10,2026/3/4 周三,70,自底向上分析法示例,11,2026/3/4 周三,71,自底向上分析法示例,12,2026/3/4 周三,72,自底向上分析法示例,13,2026/3/4 周三,73,自底向上分析法示例,14,2026/3/4 周三,74,自底向上分析法示例,15,2026/3/4 周三,75,自底向上分析法示例,16,2026/3/4 周三,76,左角分析法概述,左角分析法是一种自顶向下和自底向上相结合的方法,所谓,“,左角,(Left Corner),”,是指任何一个句法子树中左下角的那个符号,比较：,2026/3/4 周三,77,左角分析法示例,1,2026/3/4 周三,78,左角分析法示例,2,2026/3/4 周三,79,左角分析法示例,3,2026/3/4 周三,80,左角分析法示例,4,2026/3/4 周三,81,左角分析法示例,5,2026/3/4 周三,82,左角分析法示例,6,2026/3/4 周三,83,左角分析法示例,7,2026/3/4 周三,84,左角分析法示例,8,2026/3/4 周三,85,左角分析法示例,9,2026/3/4 周三,86,左角分析法示例,10,2026/3/4 周三,87,左角分析法示例,11,2026/3/4 周三,88,左角分析法示例,12,2026/3/4 周三,89,左角分析法示例,13,2026/3/4 周三,90,左角分析法示例,14,2026/3/4 周三,91,左角分析法示例,15,2026/3/4 周三,92,左角分析法示例,16,2026/3/4 周三,93,左角分析法示例,17,2026/3/4 周三,94,左角分析法示例,18,2026/3/4 周三,95,左角分析法示例,19,2026/3/4 周三,96,左角分析法示例,20,2026/3/4 周三,97,左角分析法示例,21,2026/3/4 周三,98,左角分析法示例,22,2026/3/4 周三,99,左角分析法示例,23,2026/3/4 周三,100,左角分析法示例,24,2026/3/4 周三,101,左角分析法示例,25,2026/3/4 周三,102,左角分析法示例,26,2026/3/4 周三,103,左角分析法示例,27,2026/3/4 周三,104,左角分析法示例,28,2026/3/4 周三,105,左角分析法示例,29,2026/3/4 周三,106,左角分析法示例,30,2026/3/4 周三,107,左角分析法示例,31,2026/3/4 周三,108,左角分析法示例,32,2026/3/4 周三,109,左角分析法示例,33,2026/3/4 周三,110,左角分析法示例,34,2026/3/4 周三,111,左角分析法示例,35,2026/3/4 周三,112,左角分析法示例,36,2026/3/4 周三,113,左角分析法示例,37,2026/3/4 周三,114,左角分析法示例,38,2026/3/4 周三,115,左角分析法示例,39,2026/3/4 周三,116,左角分析法示例,40,2026/3/4 周三,117,左角分析法示例,41,2026/3/4 周三,118,左角分析法示例,42,2026/3/4 周三,119,左角分析法示例,43,2026/3/4 周三,120,左角分析法示例,44,2026/3/4 周三,121,左角分析法示例,45,2026/3/4 周三,122,左角分析法示例,46,2026/3/4 周三,123,左角分析法示例,47,2026/3/4 周三,124,左角分析法示例,48,2026/3/4 周三,125,左角分析法示例,49,2026/3/4 周三,126,左角分析法示例,50,2026/3/4 周三,127,左角分析法示例,51,2026/3/4 周三,128,左角分析法示例,52,2026/3/4 周三,129,左角分析法示例,53,2026/3/4 周三,130,左角分析法示例,54,2026/3/4 周三,131,左角分析法示例,55,2026/3/4 周三,132,左角分析法示例,56,2026/3/4 周三,133,左角分析法示例,57,2026/3/4 周三,134,左角分析法示例,58,2026/3/4 周三,135,左角分析法示例,59,2026/3/4 周三,136,左角分析法示例,60,2026/3/4 周三,137,左角分析法示例,61,2026/3/4 周三,138,移进归约算法：概述,移进归约算法：,Shift-Reduce Algorithm,移进归约算法类似于下推自动机的,LR,分析算法,移进归约算法的基本数据结构是堆栈,移进归约算法的四种操作：,移进：从句子左端将一个终结符移到栈顶,归约：根据规则，将栈顶的若干个符号替换成一个符号,接受：句子中所有词语都已移进到栈中，且栈中只剩下一个符号,S,，分析成功，结束,拒绝：句子中所有词语都已移进栈中，栈中并非只有一个符号,S,，也无法进行任何归约操作，分析失败，结束,2026/3/4 周三,139,移进归约算法：举例,2026/3/4 周三,140,移进归约算法：冲突,移进归约算法中有两种形式的冲突：,移进归约冲突：既可以移进，又可以归约,归约归约冲突：可以使用不同的规则归约,冲突解决方法：回溯,回溯导致的问题：,回溯策略：对于互相冲突的各项操作，给出一个选择顺序,断点信息：除了在堆栈中除了保存非终结符外，还需要保存断点信息，使得回溯到该断点时，能够恢复堆栈的原貌，并知道还可以有哪些可选的操作,2026/3/4 周三,141,移进归约算法：示例,1,回溯策略：,移进归约冲突：先归约，后移进,归约归约冲突：规则事先排序，先执行排在前面的规则,断点信息：,当前规则：标记当前归约操作所使用的规则序号,候选规则：记录在当前位置还有哪些规则没有使用（由于这里规则是排序的，所以这一条可以省略）,被替换结点：归约时被替换的结点，以便回溯时恢复,2026/3/4 周三,142,移进归约算法：示例,2,给规则排序并加上编号：,2026/3/4 周三,143,移进归约算法：示例,3,2026/3/4 周三,144,移进归约算法：示例,4,2026/3/4 周三,145,移进归约算法：示例,5,2026/3/4 周三,146,移进归约算法：示例,6,2026/3/4 周三,147,移进归约算法：示例,7,2026/3/4 周三,148,移进归约算法：特点,移进归约算法是一种自底向上的分析算法,为了得到所有可能的分析结果，可以在每次分析成功时都强制性回溯，直到分析失败,可以看到，采用回溯算法将导致大量的冗余操作，效率非常低,2026/3/4 周三,149,移进归约算法的改进,如果在出现冲突（移进归约冲突和归约归约冲突）时能够减少错误的判断，将大大提高分析的效率,引入规则：通过规则，给出在特定条件（栈顶若干个符号和待移进的单词）应该采取的动作,引入上下文：考虑更多的栈顶元素和更多的待移进单词来写规则,引入缓冲区（,Marcus,算法）：是一种确定性的算法，没有回溯，但通过引入缓冲区，可以延迟作出决定的时间,2026/3/4 周三,150,CYK,算法概述,CYK,算法：,Cocke-Younger-Kasami,算法,CYK,算法是一种并行算法，不需要回溯；,CYK,算法建立在,Chomsky,范式的基础上,Chomsky,范式的规则只有两种形式：,A,BC A,x,这里,A,B,C,是非终结符，,x,是终结符,由于后一种形式实际上就是词典信息，在句法分析之前已经进行了替换，所以在分析中我们只考虑形如,A,BC,形式的规则,由于任何一个上下文无关语法都可以转化成符合,Chomsky,范式的语法，因此,CYK,算法可以应用于任何一个上下文无关语法,2026/3/4 周三,151,Earley,算法概述,Earley,算法也是一种并行算法，不需要回溯；,类似于,CYK,算法，,Earley,算法中也通过一个二维矩阵来存放已经分析过的结果；,Earley,算法的一个重要贡献是引入了点规则，进一步减少了规则匹配中的冗余操作；,Earley,算法是一种自顶向下的分析算法,