哈工大人工智能课件chpt9

人工智能原理

第9章

自然语言理解简介

1

本章内容

9.1语言与通讯

9.2句法分析与语法

9.3概率语言模型

9.4信息检索

9.5信息抽取

9.6统计机器翻译

参考书目第9章自然语言理解简介29.1概述

9.1.1语言与通讯

9.1.2自然语言处理第9章自然语言理解简介3语言与通讯通讯是一种通过产生和感知信号带来的有意图的信息交换/信号来自一个由约定信号组成的共用系统人类区别于其他动物的特征是语言—复杂的结构化信息系统对智能体而言，产生语言的行动称为言语行为“言语”=“言论自由”中的言论第9章自然语言理解简介4言语行为的目的通过言语行为达成联合规划：询问其他智能体关于世界的信息—提问相互通知关于世界的信息—陈述请求其他智能体行动—指令(包括礼貌的间接言语行为、命令等)应答请求承诺或提出计划宣言式言语行为—对世界有更直接的影响—诸如“现在我宣布……”第9章自然语言理解简介5通讯的组成步骤人类语言产生的目的—认知和通讯/典型的通讯情节—说话者S用词语集合W将关于命题P的信息通知聆听者H，包括7个过程意图—S要把P告诉H生成—P用W表示，H可判定P合成—物理实现—语音/文字等感知—H通过语音/文字识别等获知P分析—可分为3部分：句法/语义/语用解释排歧—H推断S的含义P合并—H决定是否相信P第9章自然语言理解简介6通讯过程第9章自然语言理解简介7分析过程分析分为3个子过程(人为划定—是否就是人类理解语言的过程？)句法分析—为输入字符串建立句法分析树语义解释—表示为某种表达式，如谓词逻辑/可能有歧义—此时存在多个表达式语用解释—考虑到同样词语集合在不同情境下有不同含义/语用能为一个语句的最终解释给出更大贡献有了3个子过程，分析仍然可能给出几个解释，排歧就是选择其中最好的一个第9章自然语言理解简介89.1.2自然语言处理

第9章自然语言理解简介9WhatisNLP?什么是自然语言处理（NaturalLanguageProcessing，NLP）是用计算机通过可计算的方法对人类语言进行转换、传输、存贮、分析等加工处理的理论和方法。构造计算模型，用于自然语言的分析、转换、生成。其他名称：计算语言学（ComputationLinguistics）自然语言理解（NaturalLanguageUnderstanding，NLU）人类语言技术（HumanLanguageTechnology）相关名称：中文信息处理（ChineseInformationProcessing）网络信息处理（WebInformationProcessing）10基本概念什么是自然语言自然语言指人类使用的语言，如汉语、英语等。语言是思维的载体，是人际交流的工具。语言的两种属性－文字和声音人类历史上以语言文字形式记载和流传的知识占知识总量的80％以上。11基本概念什么是处理处理是指对信息的接收、存储、转化、传送和发布等等操作分级：字级处理、概念处理和智能处理智能处理的主要研究领域：自然语言理解、计算机视觉、机器人学及知识工程智能的未来发展，将会对知识库、专家系统、推理系统和神经网络等综合应用，达到能够模拟人类比较复杂的思维和行为12为什么要研究自然语言处理？信息时代到了！语言是信息的载体。提高计算机的智能：能理解和处理大量语言信息。13机器能够理解人的语言吗？很难，但是没有证据表明不行。什么是理解？结构主义：机器的理解机制与人相同。问题在于谁也说不清自己理解语言的步骤。功能主义：机器的表现与人相同。图灵测试：如果通过自然语言问答，一个人无法识别和他对话的是人还是机器，那么就应该承认机器具有智能。14一个NLP的例子：英汉翻译输入英文句子：MissSmithputtwobooksonthistable.形态分析(MorphologicalAnalysis)词形还原（Lemmatization）：将词还原为词典中的原型。词汇符号化（Tokenization）：相当于中文分词。分析结果：MissSmithputtwobook+sonthistable.15句法分析（SyntacticAnalysis）：分析句子的结构。16词汇转换Miss

小姐Smith

史密斯put(+ed)

放two

两book+s

书on

在…上面this

这diningtable.

餐桌短语转换小姐史密斯放两书在上面这餐桌史密斯小姐放两书在这餐桌上面17生成史密斯小姐放两书在这桌子上面。史密斯小姐（把）两（本）书放在这（张）桌子上面。最终翻译结果英文：MissSmithputtwobooksonthetable.中文：史密斯小姐把两本书放在这张桌子上面。18机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理文本采集文本格式转换：PDF、Office、HTML纯文本文本编码识别、转换：GB、Big5、Unicode。19机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理句子边界识别例如：Mr.Wanglikesswimming,dancingandreading.20机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理研究构词方法，词的有意义的组合。构词的基本单位：词素（词根、前缀、后缀、词尾）例如：老虎←老＋虎；图书馆←图＋书＋馆例如：work+er→workerdo+ing→doing21机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理将句子切分为词序列例如：钓鱼岛/是/中国/的/领土/。

22机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理给句子的词标注正确的词性例如：钓鱼岛n/是v/中国n/的de/领土n/。

23机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理分析句子的组成结构，句子结构成分之间的相互关系。判定一个句子的合法性24机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理研究给句子的词标注正确的词义。例如：这个人真牛。//牛：动物｜了不起。25机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理研究如何从一个语句中词的意义，以及这些词在该语句的句法结构中的作用来推导出该语句的意义。语言和世界的映射关系施事、受事、工具等26机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理为什么要说这句话研究不同语境中的语句的应用，及语境对语句理解的作用语言交际目的：主题、述体、焦点27机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理分析篇章的结构、主题、观点、摘要、有用信息主题分析观点分析自动文摘信息抽取信息过滤28机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理信息检索搜索引擎、数字图书馆文本分类、聚类分类检索、聚类检索话题探测与追踪29NLP的研究内容（基础研究）30NLP的研究内容（应用研究）31NLP的不同层次[应用系统]数字图书馆、电子商务、搜索引擎电子政务、远程教育、语言学习[基础研究]分词、词性标注、短语切分、句法分析、语义分析、篇章理解等[应用技术研究]自动问答、机器翻译、信息检索、文本挖掘、自动校对、信息抽取[资源建设]语料库资源建设语言学知识库建设语言学家NLP研究者软件企业32NLP的学科特点（交叉性学科）语言学：语言学基础知识。语言学理论：形式语言文法语言学资源：词典、语料库、知识库数学语料库语言学的数学基础：概率论、统计学、信息论。模型：自动机、Markov模型、HMM等。计算机科学机器学习：机器的学习算法人工智能（问题求解,知识表示,状态空间图搜索算法）心理语言学：研究人类理解自然语言的机制。339.2句法分析与语法

9.2.1语言的基本原理

9.2.2句法分析过程第9章自然语言理解简介349.2.1语言的基本原理形式语言(人造语言)被定义为一个字符串集合/字符串由终结符(词汇)串联而成/都有严格的定义自然语言却没有严格定义却被一个说话者群体所使用考虑用处理形式语言的方式处理自然语言自然语言可以用不同的但是相互联系的几组符号来表示—包括语法、语义、语用等/尽可能采用形式化表示第9章自然语言理解简介35自然语言的符号系统(1)符号系统的核心是语义表示语义的基础是词汇—自然语言中的终结符号，由它们依据一定规则构成有效字符串/不能“让人听不明白”语义必须保证其表示能够在智能体之间有效地进行通讯—与有效的字符串结合/予以需要借助于语法进行表示语法是详细说明一种语言的有限规则集合自然语言没有正式语法/语言学家试图通过科学调查发现语言的特性，并编纂语法/还没有一个完全成功第9章自然语言理解简介36自然语言的符号系统(2)语义离不开具体的通讯环境/理解一个字符串的语用很重要语用是在一个特定情境(通讯环境)下表达出的字符串的实际含义由于语义相对于语法是深层结构，而语法作为表层结构其规则经过了很长时间的研究形成了相对稳定的体系—更多的结构表示来自语法合乎语法的字符串→子串—短语结构第9章自然语言理解简介37自然语言的符号系统(3)短语结构是语言结构中的基础部分—构成自然语言语句的字符串是由来自不同范畴的称为短语的字串构成/短语通常对应自然语言语义元素NP—名词短语，指代世界中的事物/VP—动词短语，描述事物的行为或状态/其他短语—介词短语、形容词短语、副词短语、数量短语、其他短语符号和句子符号S统称为非终结符—语法系统使用产生式规则形式来定义这些符号，规则也叫重写规则第9章自然语言理解简介38语言文法语言文法：四元组：G=(VN,VT,R,S)VN：非终结符的集合，表示句子结构分析的中间成分VT：终结符的集合，相当于词汇表。R：规则集：基本形式： 。其中：，。S

：初始符号，代表语言的句子。例如：句子：Themanatetheapple.39形式化语法的类型Chomsky在1957提出了形式化语法的4种类型，其描述语言的能力可以按序递增—由相应文法产生的语言分别叫做该文法语言正则文法—约束最强，表示能力越弱上下文无关文法—至少有些自然语言不是上下文无关的上下文有关文法—其约束可以写成在相同的前后符号中，非终结符符号重写递归可枚举文法—无约束的重写规则第9章自然语言理解简介40句法分析层次句法分析是为一个词汇字符串建立句法分析树的过程—句法分析有一个专门的术语parsing(parse=V/N,parser=句法分析器)句法分析有不同的分析层次—浅层分析(shallowparsing)和完全分析(fullparsing)浅层分析—把句子划分为几个具有不同功能的部分完全分析—给出句子的层次结构第9章自然语言理解简介419.2.2句法分析过程句法分析的前提是词典和语法词典—词汇及其相关信息的集合/关于词汇的相关信息中最重要之一是词性(Part-Of-Speech，简称POS)词性把词汇划分为若干类—开放类和封闭类语法—关于短语结构(包括S)如何生成的规则/有不同的语法规则体系—句法分析选定一种体系，依据该体系的符号生成句法树中每个节点语法的来源—语言学家观察大量的语言现象从中归纳/人工标注树库，然后自动抽取第9章自然语言理解简介42搜索句法分析树句法分析看作是搜索句法分析树的过程通常有2种方法—自顶向下(Top-Down)和自底向上(Bottom-Up)自顶向下—从S出发，搜索一棵以指定词汇为叶子节点的句法树自底向上—从给定的词汇出发，搜索一棵以S为根节点的树这两种方法都可以用搜索问题的4个组成部分来描述(初始状态/后继函数/目标检测，但是通常不涉及路径耗散)第9章自然语言理解简介43自顶向下搜索过程初始状态—根节点+未知子节点[S:?]后继函数—选择未知子节点中最左节点，然后在语法规则中尝试匹配根标记出现在规则左部的那些规则；一旦匹配成功，“？”位置上产生后继状态即“？”被相应的规则右部代替/例如[S:?]可以被[S:[NP:?][VP:?]]代替/随后，[NP:?]继续扩展，生成多个后继状态，直到匹配叶子节点等等目标测试—检验句法树的叶子节点是否符合输入的字符串/若符合，说明自顶向下的句法分析成功第9章自然语言理解简介44自底向上搜索过程初始状态—输入字符串中全部词汇，形成一个列表(看作节点序列)后继函数—对于列表中的每个节点i和句法规则中每条规则的右部，检查列表中起始于节点i的子序列是否与规则右部相匹配/如果匹配，则该子序列被新的树替代，其子树根节点为规则左部符号，子节点就是原序列目标测试—检查某个状态是否包含一棵以S为根节点的树自底向上分析的例子见下页图第9章自然语言理解简介45自底向上分析的例子第9章自然语言理解简介46句法分析中的遇到的问题自顶向下分析中的“左递归”问题形如“X→X”的规则—采用深度优先搜索，就会陷入无限循环；采用广度优先搜索则会因为输入的语句是非法语句而陷入无限搜索空间自底向上分析可能生成不完全句法分析由于短语组合的多样性，自顶向下和自底向上句法分析都存在分析效率低的问题，因为它们都会对和生成句法树不相关的部分而浪费时间—提高效率第9章自然语言理解简介479.3概率语言模型

9.3.1概率语言模型的建立

9.3.2概率上下文无关语法第9章自然语言理解简介48语料库语言学语料库语言学在20世纪90年代初期崛起，随即成为自然语言处理的主流语料库(corpus/plural=corpora)—大规模的文本集合—语料库方法意味着使用统计和学习的方法来利用语料库/通过学习(使用统计手段)从数据中获得概率语言模型对于大多数任务来说，大量数据可以补偿较简单的语言模型带来的问题第9章自然语言理解简介49统计语言模型什么是统计语言模型(LanguageModel)统计语言模型试图捕获自然语言的统计规律以改善自然语言应用系统的性能一个概率模型，对各种语言单位如字、词、句子或文章进行概率分布的估计。广泛地应用于语音识别、手写体识别、机器翻译、音字转换、信息检索。。。。。。50完美的语言模型对于词序列（或其他语言单位）如何计算概率分布？根据链式规则：即使对于很小的m，上面的理想公式也很难计算，因为参数太多。51例子52Markov链有限的记忆能力不考虑太“旧”的历史只记住前n-1个词，称为n-1阶Markov链近似53例子（Bigram,Trigram）54N-gram模型：相当于n-1阶Markov链。“n-gram”=n个词构成的序列，Unigram n=1;Bigram n=2;Trigram n=3;模型结构模型：由一组模型参数组成。

每个N-gram模型参数：n-gram及其频度信息，形式为： 或这里：模型作用：计算概率。模型训练：在训练语料库中统计获得n-gram的频度信息N-gram模型55参数训练系统

56N的选择：可靠性vs.辨别力“我 正在 ________”

讲课?图书馆?听课?学习?借书?……“我 正在图书馆 ________”

学习?借书?……57可靠性vs.辨别力更大的

n:对下一个词出现的约束性信息更多，更大的辨别力更小的n:在训练语料库中出现的次数更多，更可靠的统计结果，更高的可靠性

可靠性和可区别性成反比，需要折中。58N的选择

词表中词的个数|V|=20,000词n所有可能的n-gram的个数2(bigrams)400,000,0003(trigrams)8,000,000,000,0004(4-grams)1.6x101759N-gram模型应用-音字转换给定拼音串：tashiyan

jiu

sheng

wude可能的汉字串踏实研究生物的他实验救生物的他使烟酒生物的他是研究生物的……60音字转换计算公式61可能的转换结果，分词结果踏实研究生物的：踏实/研究/生物/的他实验救生物的：他/实验/救生/物/的他使烟酒生物的：他/使/烟酒/生物/的他是研究生物的：他/是/研究/生物/的

……如果使用Bigram计算：P(踏实研究生物的)=P(踏实)×P(研究|踏实)×P(生物|研究)×P(的|生物)P(他实验救生物的)=P(他)×P(实验|他)×P(救生|实验)×P(物|救生))×P(的|物)P(他是研究生物的)=P(他)×P(是|他)×P(研究|是)×P(生物|研究

)×P(的|生物)选择概率最大的句子，作为转换结果62N-gram模型应用-中文分词给定汉字串：他是研究生物的。可能的分词结果：1)他|是|研究生|物|的2)他|是|研究|生物|的63统计分词计算公式

64采用Bigram计算P(他/是/研究生/物/的)=P(他)×P(是|他)×P(研究生|是)×P(物|研究生)×P(的|物)×P(的)P(他/是/研究/生物/的)=P(他)×P(是|他)×P(研究|是)×P(生物|研究)×P(的|生物)×P(的)65模型参数估计——模型训练两个概念训练语料：用于建立模型的给定语料。最大似然估计：用相对频率计算概率的方法。66模型参数估计——模型训练67零概率问题大量的低频词，无论训练数据的规模如何扩大，其出现频度仍旧很低甚至根本不出现。如果采用MLE估算它们的概率分布，将出现大量的，从而导致的情况，这种情况大大削弱了该模型的描述能力。68例子假设我们使用Trigram模型如果某个那么P(S)=0这就是数据稀疏问题(零概率问题)必须保证从而使

69模型中的可能元素设词典中有15000个词语，则这些词语产生的可能词对数量就是二元模型中具有的元素个数=150002=2.25*108而Russell的这本厚达700页的书包含的英语词语数目=5*105，远远无法覆盖建立一个二元模型所需的词对/其中99.8%的词对出现的概率=0但是，我们并不希望这些词对出现的数量为0，否则无法计算相关的概率第9章自然语言理解简介70解决数据稀疏问题概率为0的问题就是所谓数据稀疏问题—解决方法—平滑(smoothing)最简单的方法—加1平滑—语料库中有n个词语/b个可能的词对，则每个实际次数为c的二元组的估计概率=(c+1)/(n+b)线性插值平滑—把一元模型/二元模型/三元模型结合起来^P(wi|wi-2wi-1)=c3P(wi|wi-2wi-1)+c2P(wi|wi-1)+c1P(wi)其中c3+c2+c1=1各种估计方法/特别是如何为那些当前语料库中为0的部分预留概率第9章自然语言理解简介71平滑的效果数据平滑的效果与训练语料库的规模有关数据平滑技术是构造高鲁棒性语言模型的重要手段训练语料库规模越小,数据平滑的效果越显著,训练语料库规模越大,数据平滑的效果越不显著,甚至可以忽略不计72模型的评价N元模型的评价标准考察模型在测试语料库上的概率—往往因为对于长的字符串的概率过小而引起计算问题模型混乱度(perplexity)取代概率其中N是words的个数(二元模型就是二元对的个数)/P(words)是该模型下所有words的概率乘积混乱度越低，则模型越好第9章自然语言理解简介739.4信息检索

9.4.1

信息检索模型

9.4.2检索结果评价与表示

9.4.3信息检索系统实现

9.4.4信息抽取第9章自然语言理解简介74基本概念信息检索(InformationRetrieval,IR)：在一个文档集合中找出与用户需要的信息相关的文档，也称为特定信息的检索问题(ad-hocretrievalproblem)信息检索和数据库检索的区别检索对象不同数据库检索：结构化数据（数据库记录）。信息检索：非结构文本（网页、自然语言文本）75IR处理对象检索对象非结构化文本自然语言文本：新闻、文献资料等网页：HTML、XML多媒体信息：图像、视频、图形、音频检索范围互联网图书馆文献资料库局域网网站76IR系统77IR任务给定文档集合（documentcollection）用户查询（Query）用户特定的信息需求（informationneed）检索式：关键词序列、布尔表达式、自然语言问句

检索查找所有与用户Query相匹配的文档计算Query与它们之间的相关性（relevance）根据相关性排序（rank），输出78信息检索系统的体系结构文本数据库数据库管理建索引索引查询操作搜索排序排序后的文档用户反馈文本操作用户界面检出的文档用户需求文本提问逻辑视图倒排文档分词删除停用词Stemming（提取词干）为文档建立倒排索引表根据倒排索引表检索出与提问相关的文档将检索出的文档根据相关性排序Query输入和文档输出相关反馈结果的可视化对query进行变换，以改进检索结果79IR系统的组件用户接口管理和用户的交互过程，包括：提问输入和文档输出相关反馈结果的可视化用户查询文本操作&文档文本操作

过滤停用词（stopword）词形还原（stemming）转换为机器内部的文档表示格式用户查询处理将用户查询进行同义词扩充根据用户信息偏好对查询进行限制。80IR系统的组件索引

建立文档集合的倒排索引数据库管理文档数据库的维护搜索根据用户查询，借助于倒排索引表和数据库管理模块从数据库中抽取出包含用户查询中关键字的文档

相关性排序计算用户query与文档的相关性根据文档的相关性排序819.4.1信息检索模型如何表示一个文档(文本)—把文档中的每个词(或字)当作一个特征，每个文档构成一个特征向量主要有3种模型布尔模型—特征出现于文档中取值为1/否则为0，返回包含查询向量的文档向量空间模型(VectorSpaceModel)—计算文档向量和查询向量之间的距离，返回最近距离的文档概率模型—给定文档条件下，计算查询概率句法分析技术并没有应用于IR系统中第9章自然语言理解简介82布尔模型描述文档表示一个文档被表示为关键词的集合查询式表示查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序匹配一个文档当且仅当它能够满足布尔查询式时，才将其检索出来检索策略基于二值判定标准83举例Q=病毒AND（计算机OR电脑）ANDNOT医文档：D1:…据报道计算机病毒最近猖獗D2：小王虽然是学医的，但对研究电脑病毒也感兴趣…D3：计算机程序发现了艾滋病病毒传播途径上述文档哪一个会被检索到？84IR模型(2)布尔模型的优点：简单易行缺点：相关度只用0/1表示，无法对相关文档排序查询结果改进比较难改进：使用基于词语频率的统计模型词语频率如何计算：词条权重—tf-idf公式/向量空间模型文档和查询之间概率关系如何：推导概率模型第9章自然语言理解简介85向量空间模型(VectorSpaceModel)词表：若干独立的词项被选作索引项(indexterms)or词表vocabulary索引项(term)集合，可以给每个词项附加权重。Query和文档表示索引项(Term)及其权重组成的n维向量表示。未加权的词项:Q=〈database;text;information〉加权的词项:Q=〈database0.5;text0.8;information0.2〉查询和文档进行向量的相关性计算：夹角余弦或者内积优点：简洁直观缺点：标引项之间的独立性假设与实际不符。86词语的权重常用的3种权重第9章自然语言理解简介度量符号定义词条频度tfi,j单词wi在文档dj中出现次数文档频度dfi出现单词wi的文档数收集频度cfi单词wi出现的总次数tf=termfrequencydf=documentfrequency dfi

≤cficf=collectionfrequency ∑tfi,j

=cfi87权重的含义计算前提：假设文档集合总存在词条频度tfi,j—反映词条在给定文档中的重要程度，越大说明对该文档越重要该值通常平滑—开平方或取对数(相关性不是倍数的关系)文档频度dfi—反映词条的信息度信息量大的词集中于一或几篇文档，在所有文档中均匀分布的词属于非核心词第9章自然语言理解简介88Idf

计算示例89权重计算公式将tfi,j和dfi结合在一个公式中其中的log(N/dfi)称为倒排文档频度(inversedocumentfrequency)或idf权重当dfi=1时，某个词条全部集中于1个文件，idf最大当dfi=N时，某个词条均匀分布于全部文档，idf最小，w=1第9章自然语言理解简介90查询式的词项权重如果词项出现在查询式中，则该词项在查询式中的权重为1，否则为0也可以用用户指定查询式中词项的权重一个自然语言查询式可以被看成一个文档查询式：“有没有周杰伦的歌？”

会被转换为:

<周杰伦,歌>查询式：

“请帮我找关于俄罗斯和车臣之间的战争以及车臣恐怖主义首脑的资料”

会被转换为:

<俄罗斯2,车臣

2,战争1,恐怖主义1,首脑1>

过滤掉了：“请帮我找”，“和”，“之间的”，“以及”，“的资料”两个文档之间的相似度可以同理计算91由索引项构成向量空间2个索引项构成一个二维空间，一个文档可能包含0,1或2个索引项di=0,0 (一个索引项也不包含)dj=0,0.7 (包含其中一个索引项)dk=1,2

(包含两个索引项)类似的，3个索引项构成一个三维空间，n个索引项构成n维空间一个文档或查询式可以表示为n个元素的线性组合92文档集

–

一般表示向量空间中的N个文档可以用一个矩阵表示矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该词项不在文档中出现。

T1T2….

TtD1d11d12…d1tD2

d21d22…d2t

::::

::::Dndn1dn2…dnt93图示举例:D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T37325D1比D2更接近Q吗？怎样衡量相似程度？夹角还是投影94相似度计算相似度是一个函数，它给出两个向量之间的相似程度，查询式和文档都是向量，各类相似度存在于：两个文档之间（文本分类，聚类）两个查询式之间（常问问题集）一个查询式和一个文档之间（检索）人们曾提出大量的相似度计算方法，因为最佳的相似度计算方法并不存在。95相似度度量–内积(InnerProduct)文档D

和查询式Q

可以通过内积进行计算:sim(D

,Q)=

(dik

qk)dik

是文档di中的词项k

的权重，qk

是查询式Q中词项k的权重对于二值向量,内积是查询式中的词项和文档中的词项相互匹配的数量对于加权向量,内积是查询式和文档中相互匹配的词项的权重乘积之和96内积的特点内积值没有界限不象概率值，要在(0,1)之间对长文档有利内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。97余弦(Cosine)相似度度量余弦相似度计算两个向量的夹角余弦相似度是利用向量长度对内积进行归一化的结果2t3t1t2D1D2Q1CosSim(Di,Q)=D1=2T1+3T2+5T3CosSim(D1

,Q)=5/38=0.81D2=3T1+7T2+T3CosSim(D2

,Q)=1/59=0.13

Q=0T1+0T2+2T3用余弦计算，D1

比

D2

高6倍；用内积计算，D1

比

D2

高5倍98其它相似度度量方法存在大量的其它相似度度量方法JaccardCoefficient:D1=2T1+3T2+5T3Sim(D1

,Q)=10/(38+4-10)=10/32=0.312D2=3T1+7T2+T3Sim(D2

,Q)=2/(59+4-2)=2/61=0.033

Q=0T1+0T2+2T3D1

比

D2

高9.5倍99示例100向量空间优点术语权重的算法提高了检索的性能部分匹配的策略使得检索的结果文档集更接近用户的检索需求可以根据结果文档对于查询串的相关度通过CosineRanking等公式对结果文档进行排序101不足标引词之间被认为是相互独立随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大隐含语义索引模型是向量空间模型的延伸1029.4.2检索结果评价与表示设有100篇文档，检索结果如下表第9章自然语言理解简介在结果集合中不在结果集合中相关3020无关1040准确率=结果集合中实际相关文档所占比例 =30/(30+10)=0.75误判率=1-0.75=0.25召回率=结果集合中相关文档在所有相关文档中所占比例=30/(30+20)=0.60漏报率=1-0.60=0.40103104相关文本检索出的文本全部文本集合检出且相关未检出且相关检出且不相关未检出且不相关检出未检出相关不相关准确率和召回率（查全率和查准率）召回率(Recall)=检出的相关文档数/相关文档数准确率(Precision)=检出的相关文档数/检出文档数假设：文本集中所有文献已进行了检查104检索结果评价(1)在互联网的搜索中，具有超大规模文档集合，召回率很难计算采样估计召回率只计算精确率精确率和召回率不能兼顾，需要折中第9章自然语言理解简介105检索结果评价(2)面向互联网的评价—对于精确率和召回率并不关心，而关心立刻得到结果第一个相关结果的平均排序倒数(reciprocalrank)第一个结果排序=1，则RR=1；排序=2，则RR=0.5……应答时间还可以考虑：检索结果集合topn中相关结果的个数第9章自然语言理解简介106检索结果的效用与表示消除检索结果中内容相同或者太近似的返回—提高效用，涉及到结果表示允许相关反馈—用户判定之后获得与之相关的相似结果的集合文档分类—事先确定主题/有指导的学习文档聚类—没有事先确定的主题，从无到有地建立类别树/无指导的学习第9章自然语言理解简介107K均值聚类k-meansclustering产生恰好k个类别的均匀集合(1)随机挑选k个文档表示k个类别(2)将每篇文档分配到最近的类别中(3)计算每簇(每个类别)的中心，并用k个均值表示k个类的新值(4)重复(2)(3)步骤直到收敛为止(类内文档不再变化)算法复杂性O(n)/准确性稍差类别的表示—代表性词语/文档标题第9章自然语言理解简介108层次聚类基本算法(1)初始状态N个文档各表示1个类别(2)计算两两类别相似度；(3)合并相似度最大的类别对形成新的类别，更新类别列表(4)重复(2)(3)步骤直到最终只剩一个类别或者满足某一限定条件，算法停止算法复杂性O(n2)/准确性强于划分聚类。第9章自然语言理解简介1099.4.3信息检索系统实现对于一个IR系统来说，2个关键数据结构文档集合中所有词语的词典每个词语在文档集合中出现位置的倒排索引词典—结构=Hash表或其他允许快速查询的数据结构(排序)去掉停用词—信息量很少的“功能词”倒排索引—词语-文档命中表每个词语在各文档中的位置及频率列表=<文档，频率>&位置列表第9章自然语言理解简介110对文档进行索引索引结构:hashing,B+-trees,tries.可以进行部分匹配:’%comput%’可以进行短语搜索:查找包含“computergraphics”的文档文档索引D1D2D3computerD1,23,97,104D3,43graphicsD2,5D3,44“computer”在D1中出现的位置111倒排文档组成倒排文档一般由两部分组成：词汇表（vocabulary）和记录表（postinglist）词汇表是文本或文本集合中所包含的所有不同单词的集合。对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表112一般的倒排索引索引文件可以用任何文件结构来实现索引文件中的词项是文档集合中的词表architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3索引项/词表索引/索引文件/索引数据库Postings列表Q=term1,term2,term3,...附加信息例如：词位置，出现次数113查询过程输入=单词输出=含该单词的文档集合获得命中表地址提取文档集合中文档并检查词语在该文档中出现频率保持集合中文档数目=R，按照频率从高到低顺序查询时间=O(H+R*logR)/H=命中表中文档数如果查询中有n个词语，需要合并n个命中表，则为O(nH+R*logR)第9章自然语言理解简介114IR系统的可改进方面词语的相关性与计算机关联—电脑/computer/PC机大小写同一处理(casefolding)词干处理(stemming)可提高召回率(英语2%)对准确率有不良影响—如stocking→stock/通过查词典综合解决同义词处理—有合并也有区别元数据—文档之外的数据用于改进系统第9章自然语言理解简介115IR系统的国际评测TREC(TextREtrievalConference)—国际IR系统的评测会议，由美国NIST主办认识典型IR任务的数量级75万篇文档，存储量=2GB词典=50万/经过取词干和大小写同一处理，存储量=7~10MB<文档，频率>倒排索引=324M/可压缩到83M支持短语查询—索引达到1200M第9章自然语言理解简介116Web搜索的规模Web上的文档数(页面数)=近100亿Google收集网页=80亿+中文网页=44亿(今年1月数据)倒排索引规模是TREC检索的几千上万倍(书中提及3000倍，2002)单台计算机不可操作，索引分为k段查询并行地送往各计算机，k个结果合并成单一结果显示给用户查询的并发处理—每秒钟有上千个查询第9章自然语言理解简介1179.5信息抽取

9.5.1信息抽取技术特点

9.5.2互联网信息抽取

9.5.3ACE会议

9.5.4命名实体识别第9章自然语言理解简介1189.5.1信息抽取技术特点信息抽取(InformationExtraction:IE)的目标—把文本里包含的信息进行结构化处理，变成表格一样的组织形式输入信息抽取系统的是原始文本，输出的是固定格式的信息点,以统一形式存储信息以统一形式集成在一起—优点方便检查和比较—例如比较不同的招聘和商品信息能对数据作自动化处理—例如用数据挖掘方法发现和解释数据模型第9章自然语言理解简介119信息抽取技术的特点信息抽取技术并不试图全面理解整篇文档，只是对文档中包含相关信息的部分进行分析/至于哪些信息是相关的，由系统设计时定下的领域范围而定应用对象：信息抽取技术对于从大量的文档中抽取需要的特定事实来说是非常有用的互联网—存在海量文档(页面)/网上同一主题的信息分散存放在不同网站上，表现的形式也各不相同若能将这些信息收集在一起，用结构化形式储存，那将是有益—成功的信息抽取系统将把互联网变成巨大的数据库第9章自然语言理解简介120IR与IEIR和IE的不同—IR从文档库中检索相关的文档，而IE是从文档中取出相关信息点/互补技术—结合起来可以为文本处理提供强大的工具IR已有很长的历史，而自动信息抽取技术则是近十年来发展起来的/IE的前身是文本理解，但整篇文档的精确理解是极其困难的，一直也未能实现推动IE发展的两个因素在线和离线文本数量的几何级数增加“消息理解研讨会”(MUC,MessageUnderstandingConference)/ACE近十几年来对该领域的关注和推动

第9章自然语言理解简介121信息抽取方法IE系统设计主要有两大方法知识工程方法(KnowledgeEngineeringApproach)自动训练方法(AutomaticTrainingApproach)知识工程方法—主要靠手工编制规则使系统能处理特定知识领域的信息抽取问题自动训练方法—系统主要通过学习已经标记好的语料库获取规则或参数任何对该知识领域比较熟悉的人都可以根据事先约定的规范标记语料库经训练后的系统能处理没有见过的新文本方法实现快，但需要足够数量的训练数据，才能保证其处理质量第9章自然语言理解简介122文本形式(1)信息抽取面对的3种格式文本自由式文本结构化文本半结构化文本自由式文本：没有固定格式从自由文本中抽取有限的主要信息—例如，从报道恐怖袭击活动的新闻中析取袭击者、所属组织、地点、受害者等信息处理自由文本的IE系统主要处理步骤包括：句法分析、语义标注、专有对象的识别（如人物、公司）和抽取规则信息抽取技术确实可行，因为需要搜索的模式类型有很强的限定第9章自然语言理解简介123文本形式(2)结构化文本：是一种数据库里的文本信息或者是根据事先规定的严格格式生成的文本从这样的文本中抽取信息是非常容易的，准确度也高半结构化文本：一种界于自由文本和结构化文本之间的数据，通常缺少语法也没有严格的格式对于半结构化文本不能使用传统的IE技巧/抽取模式通常依赖字符和象html标记那样的分隔标志互联网信息源—往往是半结构化的，虽然中间夹杂着结构化和自由文本第9章自然语言理解简介1249.5.2互联网信息抽取互联网上存在一个被称为“暗藏网”(thehiddenweb)的网上数据库系统有人估计因特网上80%的内容存在于这种看不见的因特网中/搜索引擎的“网络爬虫”抓不到这些网页需要一种独立的工具从这些网页中收集数据—即“分装器”(Wrapper或译“包装器”)的程序完成分装器接受针对特定信息源的查询请求，并从该信息源中找出相关的网页，然后把需要的信息提取出来返回给用户—由一系列抽取规则组成/一个分装器只能处理一种特定的信息源第9章自然语言理解简介125分装器的实现手工构造的IE系统难于适应处理对象所属领域的变化，而这正是互联网的特点半自动化生成分装器使用向导让用户告诉系统那些信息是需要抽取的—通过图形界面标示出需要抽取的区域/用这种方法也需要对新站点进行重新学习全自动分装器利用机器学习，主要是归纳学习方法生成抽取规则—人工给出例子，学习算法从例子中归纳出规则第9章自然语言理解简介1269.5.3ACE会议信息抽取的大规模发展，主要得益于美国DARPAR推出的两大评测会议的推动MUC(MessageUnderstandingConference)1987~1998共举行了7届ACE(AutomaticContentExtraction)2000年开始，取代了MUC，目前为止共举行了6届目标—促进自动内容抽取技术的发展具体研究目标包括—实体检测与跟踪(EDT)；关系检测与识别(RDR)；事件检测与识别(VDR)

第9章自然语言理解简介127ACE会议特点强调自然文本形式的处理/提供标注大纲、语料库和语言学资源/支持TIDES项目的抽取评测语料库支持的语种有：英文、中文、阿拉伯文，数据来源：广播、新闻专线、报纸等强调对文本基本意义或者基本概念的刻画评测任务分成了几项子任务/如ACE05的任务有：1)实体的检测(发现)和识别 2)关系的检测和识别3)事件的检测与识别4)数值的识别 5)时间的检测和识别第9章自然语言理解简介128各种识别子任务(1)实体发现与识别(EntityDetectionandRecognition,EDR)

关系发现和识别(RelationDetectionandRecognition,RDR)—发现数据流中特定类型的关系，识别这些关系的相关信息，并将这些信息组合成统一的格式输出涉及关系的属性和论元的识别关系属性(地理位置,雇佣关系等等)relationargument—有关系的两个实体的角色分别称为Arg-1和Arg-2，每个角色中只能有一个实体relationmention—提及关系的句子或短语第9章自然语言理解简介129各种识别子任务(2)事件发现和识别(EventDetectionandRecognition,VDR)—发现信息流中特定类型的事件，并且识别该事件的相关信息，并且组织成统一的格式输出一个ACE事件是指包含0个或多个ACE实体、值以及时间表达式的事件—输出包括属性/论元/范围第9章自然语言理解简介130各种识别子任务(3)值的发现和识别(ValueDetectionandRecognition,VAL)—发现数据流中特定类型的值(value)，识别这些值的相关信息，并将这些信息组合成统一的格式输出。主要包括两类Contact-Info:E-mail,Phone-number,URLNumeric:Money,Percent

时间的发现和识别(TimeDetectionandRecognition,TERN)—识别数据流中的特定类型的时间表达式，包括绝对时间和相对时间第9章自然语言理解简介1319.5.4命名实体识别信息抽取的主要任务之一是命名实体识别(NamedEntityRecognition,NER)或实体识别发现数据流中特定类型的实体，识别这些实体的相关信息，并将这些信息组合成统一的格式输出评测输出包括实体的属性和实体的提及(mention)即提及实体的句子或短语其中属性包括实体类型(type)，实体子类型(subtype)，实体类别(class)，表示实体的名称(name)/每个实体只能有一种类别，一种子类和一个class第9章自然语言理解简介132实体的类型和子类第9章自然语言理解简介TypeSubtypesFAC(Facility)Airport,Building-Grounds,Path,Plant,Subarea-FacilityGPE(Geo-PoliticalEntity)Continent,County-or-District,GPE-Cluster,Nation,Population-Center,Special,State-or-ProvinceLOC(Location)Address,Boundary,Celestial,Land-Region-Natural,Region-General,Region-International,Water-BodyORG(Organization)Commercial,Educational,Entertainment,Government,Media,Medical-Science,Non-Governmental,Religious,SportsPER(Person)Group,Indeterminate,IndividualVEH(Vehicle)Air,Land,Subarea-Vehicle,Underspecified,WaterWEA(Weapon)Biological,Blunt,Chemical,Exploding,Nuclear,Projectile,Sharp,Shooting,Underspecified133实体的类别ACE中实体类别Class定义(4种)Specific(SPC，指特殊的唯一存在的实体)Generic（GEN，一类实体）negativelyquanitified(NEG，中文中不包含这项，英文中主要指nobody等)Underspecified(USP，不是一类，也不是特指)例子建立[一支与打赢未来战争相适应的人才指挥部队

](GEN)[高科技部队]如果没有[高素质人才

]支撑,再先进的装备也是一堆废铁。(GEN)对于长时间耽误请求外援的作法，[人们]尤其感到愤怒。(USP)[您]现在收听的是美国之音的《时事经纬》节目。(USP)第9章自然语言理解简介134提及的方式ACE定义实体的mention：在文本中可以用名称(NAM)，普通名词/短语(NOM)，或代词(PRO)表示实体例子：北京奥申委常务副主席刘敬民在接受记者采访时表示，此行达到了他预想效果。NameMention:刘敬民NominalMention:北京奥申委常务副主席PronounMention:他第9章自然语言理解简介135名实体识别方法将名实体的识别看作分类问题是/否名实体—二值分类是哪一类名实体—多分类问题识别方法—各种统计学习方法/模式识别方法难点：在不同领域、场景下，命名实体的外延有差异；数量巨大，不能枚举，难以全部收录在词典中；某些类型的实体名称变化频繁，并且没有严格的规律可以遵循；表达形式多样；首次出现后往往采用缩写形式；

第9章自然语言理解简介1369.6统计机器翻译

9.6.1机器翻译的层次

9.6.2统计机器翻译模型

9.6.3翻译参数学习

9.6.4统计机器翻译的发展第9章自然语言理解简介1379.6.1机器翻译的层次机器翻译从语言分析角度可以分为4个层次(自底向上)：词法/句法/语义/中间语言第9章自然语言理解简介EnglishWordsJohnlovesMaryEnglishSyntaxS(NP(John),VP(loves,NP(Mary)))EnglishSemanticsLoves(John,Mary)FrenchWordsJeanaimeMarieFrenchSyntaxS(NP(Jean),VP(aime,NP(Marie)))FrenchSemanticsAime(Jean,Marie)InterlinguaSemanticsAttraction(NameJohn,NameMary,High)138语言分析和转换的层次两种语言的翻译可以在不同层次实现，依赖于对源语言分析的深度无任何处理：查询已翻译的实例库→翻译转化为检索/目前的方法：基于记忆的翻译(translationmemory—TM)最底层—词法：词汇级分析与翻译中间层—句法：句法分析，然后结构转换中间层—语义：语义分析，获得源语言深层结构，在此基础上进行转换最高层—中间语言：对语言完全理解之后再行翻译/n种语言只要2n对转换第9章自然语言理解简介139目前机器翻译的用途机器翻译的应用前景不可限量由于目前机器翻译系统性能的限制，应用也就被限制目前可用之处：信息浏览—对于完全不懂的语言，糟糕的翻译比没有翻译还是好：网页浏览源语言受限翻译—成功的例子：天气预报翻译系统TAUM-METEO/其他如命名实体翻译预编辑翻译—源语言人工预编辑+多语言翻译第9章自然语言理解简介1409.6.2统计机器翻译模型统计方法在机器翻译中应用很早就提出来了能否像翻译密码一样进行语言翻译语言翻译必须涉及语言的含义，而密码不需要20世纪90年代开始重提统计机器翻译，已经成为主流方法利用大规模语料库统计出相关参数根据参数寻