哈工大人工智能课件chpt9.ppt_163文库

资源描述

1、 9.1 语言与通讯9.2 句法分析与语法9.3 概率语言模型9.4 信息检索9.5 信息抽取9.6 统计机器翻译参考书目第9章自然语言理解简介9.1 概述9.1.1 语言与通讯9.1.2 自然语言处理第9章自然语言理解简介4 通讯是一种通过产生和感知信号带来的有意图的信息交换 / 信号来自一个由约定信号组成的共用系统人类区别于其他动物的特征是语言复杂的结构化信息系统对智能体而言，产生语言的行动称为言语行为 “言语”=“言论自由”中的言论第9章自然语言理解简介5 通过言语行为达成联合规划：询问其他智能体关于世界的信息提问相互通知关于世界的信息陈述请求其他智能体行动指令(包括礼貌

2、的间接言语行为、命令等) 应答请求承诺或提出计划宣言式言语行为对世界有更直接的影响诸如“现在我宣布”第9章自然语言理解简介6 人类语言产生的目的认知和通讯 / 典型的通讯情节说话者S用词语集合W将关于命题P的信息通知聆听者H，包括7个过程意图S要把P告诉H 生成P用W表示，H可判定P 合成物理实现语音/文字等感知H通过语音/文字识别等获知P 分析可分为3部分：句法/语义/语用解释排歧H推断S的含义P 合并H决定是否相信P第9章自然语言理解简介7第9章自然语言理解简介8 分析分为3个子过程(人为划定是否就是人类理解语言的过程？) 句法分析为输入字符串建立句法分析树语义解释表示为

3、某种表达式，如谓词逻辑 / 可能有歧义此时存在多个表达式语用解释考虑到同样词语集合在不同情境下有不同含义 / 语用能为一个语句的最终解释给出更大贡献有了3个子过程，分析仍然可能给出几个解释，排歧就是选择其中最好的一个第9章自然语言理解简介9.1.2 自然语言处理第9章自然语言理解简介10What is NLP? 什么是自然语言处理（Natural Language Processing，NLP）是用计算机通过可计算的方法对人类语言进行转换、传输、存贮、分析等加工处理的理论和方法。构造计算模型，用于自然语言的分析、转换、生成。其他名称：计算语言学（Computation Ling

4、uistics）自然语言理解（Natural Language Understanding，NLU）人类语言技术（Human Language Technology）相关名称：中文信息处理（Chinese Information Processing）网络信息处理（Web Information Processing）11基本概念什么是自然语言自然语言指人类使用的语言，如汉语、英语等。语言是思维的载体，是人际交流的工具。语言的两种属性文字和声音人类历史上以语言文字形式记载和流传的知识占知识总量的80以上。12基本概念什么是处理处理是指对信息的接收、存储、转化、传送和发布

5、等等操作分级：字级处理、概念处理和智能处理智能处理的主要研究领域：自然语言理解、计算机视觉、机器人学及知识工程智能的未来发展，将会对知识库、专家系统、推理系统和神经网络等综合应用，达到能够模拟人类比较复杂的思维和行为13为什么要研究自然语言处理？信息时代到了！语言是信息的载体。提高计算机的智能：能理解和处理大量语言信息。14机器能够理解人的语言吗？很难，但是没有证据表明不行。什么是理解？结构主义：机器的理解机制与人相同。问题在于谁也说不清自己理解语言的步骤。功能主义：机器的表现与人相同。图灵测试：如果通过自然语言问答，一个人无法识别和他对话的是人还是机器，那么就应该承认机

6、器具有智能。15一个NLP的例子：英汉翻译输入英文句子： Miss Smith put two books on this table. 形态分析(Morphological Analysis) 词形还原（Lemmatization）：将词还原为词典中的原型。词汇符号化（Tokenization）：相当于中文分词。分析结果：MissSmithputtwobook+sonthistable.16 句法分析（Syntactic Analysis）：分析句子的结构。17 词汇转换Miss 小姐Smith 史密斯put (+ed) 放two 两book+s 书on 在上面this 这dining

7、 table. 餐桌短语转换小姐史密斯放两书在上面这餐桌史密斯小姐放两书在这餐桌上面18 生成史密斯小姐放两书在这桌子上面。史密斯小姐（把）两（本）书放在这（张）桌子上面。最终翻译结果英文： Miss Smith put two books on the table. 中文：史密斯小姐把两本书放在这张桌子上面。19机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理文本采集文本格式转换：PDF、Office、HTML纯文本文本编码识别、转换：GB、Big5、Unicode。20机

8、器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理句子边界识别例如：Mr. Wang likes swimming, dancing and reading.21机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理研究构词方法，词的有意义的组合。构词的基本单位：词素（词根、前缀、后缀、词尾）例如：老虎老虎；图书馆图书馆例如： work + er worker do + in

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

10、语用分析篇章分析海量文档处理分析句子的组成结构，句子结构成分之间的相互关系。判定一个句子的合法性25机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理研究给句子的词标注正确的词义。例如：这个人真牛。/牛：动物了不起。26机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理研究如何从一个语句中词的意义，以及这些词在该语句的句法结构中的作用来推导出该语句的意义。语言和世界的映射关系施

11、事、受事、工具等27机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理为什么要说这句话研究不同语境中的语句的应用，及语境对语句理解的作用语言交际目的：主题、述体、焦点28机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理分析篇章的结构、主题、观点、摘要、有用信息主题分析观点分析自动文摘信息抽取信息过滤29机器如何理解自然语言？机器理解自然语言的步骤文本预处理句子切分形态分析

12、分词词性标注句法分析词义消岐语义分析语用分析篇章分析海量文档处理信息检索搜索引擎、数字图书馆文本分类、聚类分类检索、聚类检索话题探测与追踪30NLP的研究内容（基础研究）31NLPNLP的研究内容（应用研究）的研究内容（应用研究）32NLP的不同层次应用系统数字图书馆、电子商务、搜索引擎电子政务、远程教育、语言学习基础研究分词、词性标注、短语切分、句法分析、语义分析、篇章理解等应用技术研究自动问答、机器翻译、信息检索、文本挖掘、自动校对、信息抽取资源建设语料库资源建设语言学知识库建设语言学家NLP研究者软件企业33NLP的学科特点（交叉性学科）语言学：语言学基础知识。语言学

13、理论：形式语言文法语言学资源：词典、语料库、知识库数学语料库语言学的数学基础：概率论、统计学、信息论。模型：自动机、Markov模型、HMM等。计算机科学机器学习：机器的学习算法人工智能（问题求解,知识表示,状态空间图搜索算法）心理语言学：研究人类理解自然语言的机制。9.2 句法分析与语法9.2.1 语言的基本原理9.2.2 句法分析过程第9章自然语言理解简介35 形式语言(人造语言)被定义为一个字符串集合 / 字符串由终结符(词汇)串联而成 / 都有严格的定义自然语言却没有严格定义却被一个说话者群体所使用考虑用处理形式语言的方式处理自然语言自然语言可以用不同的但是相互

14、联系的几组符号来表示包括语法、语义、语用等 / 尽可能采用形式化表示第9章自然语言理解简介36 符号系统的核心是语义表示语义的基础是词汇自然语言中的终结符号，由它们依据一定规则构成有效字符串 / 不能“让人听不明白” 语义必须保证其表示能够在智能体之间有效地进行通讯与有效的字符串结合 / 予以需要借助于语法进行表示语法是详细说明一种语言的有限规则集合自然语言没有正式语法 / 语言学家试图通过科学调查发现语言的特性，并编纂语法 / 还没有一个完全成功第9章自然语言理解简介37 语义离不开具体的通讯环境 / 理解一个字符串的语用很重要语用是在一个特定情境(通讯环境)下表达出的字符串的实

15、际含义由于语义相对于语法是深层结构，而语法作为表层结构其规则经过了很长时间的研究形成了相对稳定的体系更多的结构表示来自语法合乎语法的字符串子串短语结构第9章自然语言理解简介38 短语结构是语言结构中的基础部分构成自然语言语句的字符串是由来自不同范畴的称为短语的字串构成 / 短语通常对应自然语言语义元素 NP名词短语，指代世界中的事物 / VP动词短语，描述事物的行为或状态 / 其他短语介词短语、形容词短语、副词短语、数量短语、其他短语符号和句子符号S统称为非终结符语法系统使用产生式规则形式来定义这些符号，规则也叫重写规则第9章自然语言理解简介39语言文法语言文法：四元组：G=(V

16、N ,VT ,R,S) VN：非终结符的集合，表示句子结构分析的中间成分 VT ：终结符的集合，相当于词汇表。 R ：规则集：基本形式：。其中：，。 S ：初始符号，代表语言的句子。例如：句子：The man ate the apple.TNVVVV*V40 Chomsky在1957提出了形式化语法的4种类型，其描述语言的能力可以按序递增由相应文法产生的语言分别叫做该文法语言正则文法约束最强，表示能力越弱上下文无关文法至少有些自然语言不是上下文无关的上下文有关文法其约束可以写成在相同的前后符号中，非终结符符号重写递归可枚举文法无约束的重写规则第9章自然语言理解简介41 句法分

17、析是为一个词汇字符串建立句法分析树的过程句法分析有一个专门的术语parsing (parse=V/N, parser=句法分析器) 句法分析有不同的分析层次浅层分析(shallow parsing)和完全分析(full parsing) 浅层分析把句子划分为几个具有不同功能的部分完全分析给出句子的层次结构第9章自然语言理解简介42 句法分析的前提是词典和语法词典词汇及其相关信息的集合 / 关于词汇的相关信息中最重要之一是词性(Part-Of-Speech，简称POS) 词性把词汇划分为若干类开放类和封闭类语法关于短语结构(包括S)如何生成的规则 / 有不同的语法规则体系句法分析选定一种

18、体系，依据该体系的符号生成句法树中每个节点语法的来源语言学家观察大量的语言现象从中归纳 / 人工标注树库，然后自动抽取第9章自然语言理解简介43 句法分析看作是搜索句法分析树的过程通常有2种方法自顶向下(Top-Down)和自底向上(Bottom-Up) 自顶向下从S出发，搜索一棵以指定词汇为叶子节点的句法树自底向上从给定的词汇出发，搜索一棵以S为根节点的树这两种方法都可以用搜索问题的4个组成部分来描述(初始状态/后继函数/目标检测，但是通常不涉及路径耗散)第9章自然语言理解简介44 初始状态根节点+未知子节点S:? 后继函数选择未知子节点中最左节点，然后在语法规则中尝试匹配根标记

19、出现在规则左部的那些规则；一旦匹配成功，“？”位置上产生后继状态即“？”被相应的规则右部代替 / 例如S:?可以被S:NP:?VP:?代替 / 随后，NP:?继续扩展，生成多个后继状态，直到匹配叶子节点等等目标测试检验句法树的叶子节点是否符合输入的字符串 / 若符合，说明自顶向下的句法分析成功第9章自然语言理解简介45 初始状态输入字符串中全部词汇，形成一个列表(看作节点序列) 后继函数对于列表中的每个节点i和句法规则中每条规则的右部，检查列表中起始于节点i的子序列是否与规则右部相匹配 / 如果匹配，则该子序列被新的树替代，其子树根节点为规则左部符号，子节点就是原序列目标测试检查某个状态

20、是否包含一棵以S为根节点的树自底向上分析的例子见下页图第9章自然语言理解简介46第9章自然语言理解简介47 自顶向下分析中的“左递归”问题形如“XX”的规则采用深度优先搜索，就会陷入无限循环；采用广度优先搜索则会因为输入的语句是非法语句而陷入无限搜索空间自底向上分析可能生成不完全句法分析由于短语组合的多样性，自顶向下和自底向上句法分析都存在分析效率低的问题，因为它们都会对和生成句法树不相关的部分而浪费时间提高效率第9章自然语言理解简介9.3 概率语言模型9.3.1 概率语言模型的建立9.3.2 概率上下文无关语法第9章自然语言理解简介49 语料库语言学在20世纪90年代初期崛起

21、，随即成为自然语言处理的主流语料库(corpus / plural=corpora)大规模的文本集合语料库方法意味着使用统计和学习的方法来利用语料库 / 通过学习(使用统计手段)从数据中获得概率语言模型对于大多数任务来说，大量数据可以补偿较简单的语言模型带来的问题第9章自然语言理解简介50统计语言模型什么是统计语言模型(Language Model) 统计语言模型试图捕获自然语言的统计规律以改善自然语言应用系统的性能一个概率模型，对各种语言单位如字、词、句子或文章进行概率分布的估计。广泛地应用于语音识别、手写体识别、机器翻译、音字转换、信息检索。12121121( )()()(|)

22、(|)mmmP SP SwwwP wP wwP wwww51完美的语言模型对于词序列（或其他语言单位）如何计算概率分布？根据链式规则：即使对于很小的m，上面的理想公式也很难计算，因为参数太多。12121121( )()()(|)(|)mmmP SP Sw wwP wP wwP ww wwmwwwS21)(SP52例子()(,)()(|)(|,)(|,)(|,)ppppppp我是一个学生我是一个学生我是我一我是个我是一学生我是一个53Markov链有限的记忆能力不考虑太“旧”的历史只记住前n-1个词，称为n-1阶Markov链近似12111(

23、)()(|)mmiii niP SP SwwwP w w 54例子（Bigram,Trigram）)|()|()|()|()(),()(个学生一个是一我是我学生个一是我我是一个学生ppppppp),|(),|(),|()|()(),()(个一学生一是个是我一我是我学生个一是我我是一个学生ppppppp55 N-gram模型：相当于n-1阶Markov链。 “n-gram” = n个词构成的序列， Unigramn = 1; Bigramn = 2; Trigram n = 3; 模型结构模型：由一组模型参数组成。每个N-gram模型参数：n-gram及其频度信息，形式为：或这里：模型作

24、用：计算概率。模型训练：在训练语料库中统计获得n-gram的频度信息N-gram模型).(),.(2121nnwwwcwww).().().|(12121121nnnnwwwcwwwcwwwwPnwww.21)(,gramnfgramn数。在训练语料库中出现次为)(C56参数训练系统语料库分词语料参数估计语言模型分词系统词表 57N的选择：可靠性的选择：可靠性 vs. 辨别力辨别力“我正在 _ ”讲课?图书馆?听课?学习?借书?“我正在图书馆 _”学习? 借书? 58可靠性可靠性 vs. 辨别力辨别力更大的 n: 对下一个词出现的约束性信息更多，更大的辨别力更小

25、的n: 在训练语料库中出现的次数更多，更可靠的统计结果，更高的可靠性可靠性和可区别性成反比，需要折中。59N的选择词表中词的个数 |V| = 20,000 词n所有可能的n-gram的个数2 (bigrams)400,000,0003 (trigrams)8,000,000,000,0004 (4-grams)1.6 x 101760N-gram模型应用-音字转换给定拼音串：ta shi yan jiu sheng wu de 可能的汉字串踏实研究生物的他实验救生物的他使烟酒生物的他是研究生物的 61 音字转换计算公式)(maxarg)()|(maxarg)()()|(maxarg

27、为转换结果63N-gramN-gram模型应用模型应用- -中文分词中文分词给定汉字串：他是研究生物的。可能的分词结果： 1) 他|是|研究生|物|的 2) 他|是|研究|生物|的64 统计分词计算公式 65 采用Bigram计算P(他/是/研究生/物/的) =P(他)P(是|他)P(研究生|是)P(物|研究生)P(的|物)P(的)P(他/是/研究/生物/的) = P(他)P(是|他)P(研究|是)P(生物|研究)P(的|生物)P(的)miiimmwwPwwwPwwwPSegP112121)|(),()/(66模型参数估计模型参数估计模型训练模型训练两个概念训练语料：用于建立模型的给定

28、语料。最大似然估计：用相对频率计算概率的方法。67模型参数估计模型参数估计模型训练模型训练68零概率问题零概率问题大量的低频词，无论训练数据的规模如何扩大，其出现频度仍旧很低甚至根本不出现。如果采用MLE估算它们的概率分布，将出现大量的，从而导致的情况，这种情况大大削弱了该模型的描述能力。 0)|(1iiwwp0)(sp69例子例子假设我们使用Trigram模型如果某个那么P(S)=0 这就是数据稀疏问题(零概率问题) 必须保证从而使 )|().|()|()()(12213121nnnwwwpwwwpwwpwpSP0)()()|(121212iiiiiiiiwwcwwwcwww

29、p0c0P70 设词典中有15000个词语，则这些词语产生的可能词对数量就是二元模型中具有的元素个数=150002=2.25*108 而Russell的这本厚达700页的书包含的英语词语数目=5*105，远远无法覆盖建立一个二元模型所需的词对 / 其中99.8%的词对出现的概率=0 但是，我们并不希望这些词对出现的数量为0，否则无法计算相关的概率第9章自然语言理解简介71 概率为0的问题就是所谓数据稀疏问题解决方法平滑(smoothing) 最简单的方法加1平滑语料库中有n个词语/b个可能的词对，则每个实际次数为c的二元组的估计概率=(c+1)/(n+b) 线性插值平滑把一元模型/二元模型/

30、三元模型结合起来 P(wi|wi-2wi-1)=c3P(wi|wi-2wi-1)+c2P(wi|wi-1) +c1P(wi)其中c3+c2+c1=1 各种估计方法/特别是如何为那些当前语料库中为0的部分预留概率第9章自然语言理解简介72平滑的效果数据平滑的效果与训练语料库的规模有关数据平滑技术是构造高鲁棒性语言模型的重要手段训练语料库规模越小,数据平滑的效果越显著, 训练语料库规模越大,数据平滑的效果越不显著,甚至可以忽略不计73 N元模型的评价标准考察模型在测试语料库上的概率往往因为对于长的字符串的概率过小而引起计算问题模型混乱度(perplexity)取代概率其中N是word

31、s的个数(二元模型就是二元对的个数) / P(words)是该模型下所有words的概率乘积混乱度越低，则模型越好第9章自然语言理解简介)(log122)(wordsPNwordsPerplexity9.4 信息检索9.4.1 信息检索模型9.4.2 检索结果评价与表示9.4.3 信息检索系统实现9.4.4 信息抽取第9章自然语言理解简介75基本概念基本概念信息检索(Information Retrieval, IR)：在一个文档集合中找出与用户需要的信息相关的文档，也称为特定信息的检索问题(ad-hoc retrieval problem) 信息检索和数据库检索的区别检索对象不同

32、数据库检索：结构化数据（数据库记录）。信息检索：非结构文本（网页、自然语言文本） 76IRIR处理对象处理对象检索对象非结构化文本自然语言文本：新闻、文献资料等网页：HTML、XML 多媒体信息：图像、视频、图形、音频检索范围互联网图书馆文献资料库局域网网站77IRIR系统系统78IR任务给定文档集合（document collection ）用户查询（Query）用户特定的信息需求（information need）检索式：关键词序列、布尔表达式、自然语言问句检索查找所有与用户Query相匹配的文档计算Query与它们之间的相关性（relevance）根

33、据相关性排序（rank），输出 79信息检索系统的体系结构文本数据库数据库管理建索引索引查询操作搜索排序排序后的文档用户反馈文本操作用户界面检出的文档用户需求文本提问逻辑视图倒排文档分词分词删除停用词删除停用词Stemming（提取词（提取词干）干）为文档建立为文档建立倒排索引表倒排索引表根据倒排索引根据倒排索引表检索出与提表检索出与提问相关的文档问相关的文档将检索出的文将检索出的文档根据相关性档根据相关性排序排序Query输入和文档输入和文档输出输出相关反馈相关反馈结果的可视化结果的可视化对对query进行变进行变换，以改进检索换，以改进检索结果结果80IR系统的组件用户接口管理和用户的

34、交互过程，包括：提问输入和文档输出相关反馈结果的可视化用户查询文本操作&文档文本操作过滤停用词（stop word）词形还原（stemming）转换为机器内部的文档表示格式用户查询处理将用户查询进行同义词扩充根据用户信息偏好对查询进行限制。81IR系统的组件索引建立文档集合的倒排索引数据库管理文档数据库的维护搜索根据用户查询，借助于倒排索引表和数据库管理模块从数据库中抽取出包含用户查询中关键字的文档相关性排序计算用户query与文档的相关性根据文档的相关性排序82 如何表示一个文档(文本)把文档中的每个词(或字)当作一个特征，每个文档构成一个特征向量主要有3种

35、模型布尔模型特征出现于文档中取值为1/否则为0，返回包含查询向量的文档向量空间模型(Vector Space Model)计算文档向量和查询向量之间的距离，返回最近距离的文档概率模型给定文档条件下，计算查询概率句法分析技术并没有应用于IR系统中第9章自然语言理解简介83布尔模型描述文档表示一个文档被表示为关键词的集合查询式表示查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序匹配一个文档当且仅当它能够满足布尔查询式时，才将其检索出来检索策略基于二值判定标准84举例 Q=病毒AND（计算机OR电脑）ANDNOT医文档：D1:

36、据报道计算机病毒最近猖獗D2：小王虽然是学医的，但对研究电脑病毒也感兴趣D3：计算机程序发现了艾滋病病毒传播途径上述文档哪一个会被检索到？85 布尔模型的优点：简单易行缺点：相关度只用0/1表示，无法对相关文档排序查询结果改进比较难改进：使用基于词语频率的统计模型词语频率如何计算：词条权重tf-idf公式 / 向量空间模型文档和查询之间概率关系如何：推导概率模型第9章自然语言理解简介86向量空间模型(Vector Space Model) 词表：若干独立的词项被选作索引项( index terms) or 词表vocabulary 索引项(term)集合，可以给每个词项附加权

37、重。 Query和文档表示索引项(Term)及其权重组成的n维向量表示。未加权的词项: Q = database; text; information 加权的词项: Q = database 0.5; text 0.8; information 0.2 查询和文档进行向量的相关性计算：夹角余弦或者内积优点：简洁直观缺点：标引项之间的独立性假设与实际不符。),.,(, 2, 1jNjjjwwwd ),.,(, 2, 1qNqqwwwq 87 常用的3种权重第9章自然语言理解简介度量符号定义词条频度tfi,j单词wi在文档dj中出现次数文档频度dfi出现单词wi的文档数收集频度cfi单

38、词wi出现的总次数 tf = term frequency df = document frequencydfi cfi cf = collection frequencytfi,j = cfi88 计算前提：假设文档集合总存在词条频度tfi,j反映词条在给定文档中的重要程度，越大说明对该文档越重要该值通常平滑开平方或取对数(相关性不是倍数的关系) 文档频度dfi反映词条的信息度信息量大的词集中于一或几篇文档，在所有文档中均匀分布的词属于非核心词第9章自然语言理解简介89Idf 计算示例90 将tfi,j和dfi结合在一个公式中其中的log(N/dfi)称为倒排文档频度(invers

39、e document frequency)或idf权重当dfi=1时，某个词条全部集中于1个文件，idf最大当dfi=N时，某个词条均匀分布于全部文档， idf最小，w=1第9章自然语言理解简介,1 log()log1( , )00i ji jii jNtftfdfweight i jtf91查询式的词项权重如果词项出现在查询式中，则该词项在查询式中的权重为1，否则为0 也可以用用户指定查询式中词项的权重一个自然语言查询式可以被看成一个文档查询式：“有没有周杰伦的歌？” 会被转换为: 查询式： “请帮我找关于俄罗斯和车臣之间的战争以及车臣恐怖主义首脑的资料” 会被转换为: 过滤掉了

40、：“请帮我找”，“和”，“之间的”，“以及”，“的资料” 两个文档之间的相似度可以同理计算92由索引项构成向量空间由索引项构成向量空间 2个索引项构成一个二维空间，一个文档可能包含0, 1 或2个索引项 di = 0, 0 (一个索引项也不包含) dj = 0, 0.7 (包含其中一个索引项) dk = 1, 2 (包含两个索引项) 类似的，3个索引项构成一个三维空间，n个索引项构成n维空间一个文档或查询式可以表示为n个元素的线性组合93文档集文档集一般表示一般表示向量空间中的N个文档可以用一个矩阵表示矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该

41、词项不在文档中出现。 T1 T2 . TtD1 d11 d12 d1tD2 d21 d22 d2t : : : : : : : :Dn dn1 dn2 dnt94图示举例:D1 = 2T1 + 3T2 + 5T3D2 = 3T1 + 7T2 + T3Q = 0T1 + 0T2 + 2T3T3T1T2D1 = 2T1+ 3T2 + 5T3D2 = 3T1 + 7T2 + T3Q = 0T1 + 0T2 + 2T37325 D1比D2更接近Q吗？怎样衡量相似程度？夹角还是投影95相似度计算相似度计算相似度是一个函数，它给出两个向量之间的相似程度，查询式和文档都是向量，各类相似度存在于：两个文

42、档之间（文本分类，聚类）两个查询式之间（常问问题集）一个查询式和一个文档之间（检索）人们曾提出大量的相似度计算方法，因为最佳的相似度计算方法并不存在。96相似度度量内积(Inner Product) 文档D 和查询式Q 可以通过内积进行计算:sim ( D , Q ) = (dik qk) dik 是文档di中的词项k 的权重，qk 是查询式Q中词项k的权重对于二值向量, 内积是查询式中的词项和文档中的词项相互匹配的数量对于加权向量, 内积是查询式和文档中相互匹配的词项的权重乘积之和kt197内积的特点内积值没有界限不象概率值，要在(0,1)之间对长文档有利内积用于衡量有多

43、少词项匹配成功，而不计算有多少词项匹配失败长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。98余弦(Cosine)相似度度量余弦相似度计算两个向量的夹角余弦相似度是利用向量长度对内积进行归一化的结果2t3t1t2D1D2Q1CosSim(Di, Q) =tktktkkikqdqdkik11221)(D1 = 2T1 + 3T2 + 5T3 CosSim(D1 , Q) = 5 / 38 = 0.81D2 = 3T1 + 7T2 + T3 CosSim(D2 , Q) = 1 / 59 = 0.13 Q = 0T1 + 0T2 +

44、2T3用余弦计算，D1 比 D2 高6倍；用内积计算， D1 比 D2 高5倍99其它相似度度量方法存在大量的其它相似度度量方法tktkkiktktkkikqdqdqdkik111221)()(Jaccard Coefficient:D1 = 2T1 + 3T2 + 5T3 Sim(D1 , Q) = 10 / (38+4-10) = 10/32 = 0.312D2 = 3T1 + 7T2 + T3 Sim(D2 , Q) = 2 / (59+4-2) = 2/61 = 0.033 Q = 0T1 + 0T2 + 2T3nD1 比 D2 高9.5倍100示例101向量空间优点术语权重的算法

45、提高了检索的性能部分匹配的策略使得检索的结果文档集更接近用户的检索需求可以根据结果文档对于查询串的相关度通过Cosine Ranking等公式对结果文档进行排序102不足标引词之间被认为是相互独立随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大隐含语义索引模型是向量空间模型的延伸103 设有100篇文档，检索结果如下表第9章自然语言理解简介在结果集合中不在结果集合中相关3020无关1040 准确率=结果集合中实际相关文档所占比例=30/(30+10)=0.75 误判率=1-0.75=0.25 召回率=结果

46、集合中相关文档在所有相关文档中所占比例=30/(30+20)=0.60 漏报率=1-0.60=0.40104104相关文本相关文本检索出的检索出的文本文本全部文本集合全部文本集合检出且相关未检出且相关检出且不相关未检出且不相关检出未检出相关不相关准确率和召回率（查全率和查准率）召回率(Recall)=检出的相关文档数/相关文档数准确率(Precision)=检出的相关文档数/检出文档数假设：文本集中所有文献已进行了检查105 在互联网的搜索中，具有超大规模文档集合，召回率很难计算采样估计召回率只计算精确率精确率和召回率不能兼顾，需要折中第9章自然语言理解简介RPRPF2106 面向互联

47、网的评价对于精确率和召回率并不关心，而关心立刻得到结果第一个相关结果的平均排序倒数(reciprocal rank) 第一个结果排序=1，则RR=1；排序=2，则RR=0.5 应答时间还可以考虑：检索结果集合top n中相关结果的个数第9章自然语言理解简介107 消除检索结果中内容相同或者太近似的返回提高效用，涉及到结果表示允许相关反馈用户判定之后获得与之相关的相似结果的集合文档分类事先确定主题 / 有指导的学习文档聚类没有事先确定的主题，从无到有地建立类别树 / 无指导的学习第9章自然语言理解简介108 k-means clustering产生恰好k个类别的均匀集合(1)随机挑

48、选k个文档表示k个类别(2)将每篇文档分配到最近的类别中(3)计算每簇(每个类别)的中心，并用k个均值表示k个类的新值(4)重复(2)(3)步骤直到收敛为止(类内文档不再变化) 算法复杂性O(n) / 准确性稍差类别的表示代表性词语 / 文档标题第9章自然语言理解简介109 基本算法(1)初始状态N个文档各表示1个类别(2)计算两两类别相似度；(3)合并相似度最大的类别对形成新的类别，更新类别列表(4)重复(2)(3)步骤直到最终只剩一个类别或者满足某一限定条件，算法停止算法复杂性O(n2) / 准确性强于划分聚类。第9章自然语言理解简介110 对于一个IR系统来说，2个关键数据结构

49、文档集合中所有词语的词典每个词语在文档集合中出现位置的倒排索引词典结构=Hash表或其他允许快速查询的数据结构(排序) 去掉停用词信息量很少的“功能词” 倒排索引词语-文档命中表每个词语在各文档中的位置及频率列表= & 位置列表第9章自然语言理解简介111对文档进行索引索引结构: hashing, B+-trees, trieshashing, B+-trees, tries. 可以进行部分匹配: %comput% 可以进行短语搜索:查找包含“computer graphics”的文档文档索引D1D2D3computerD1, 23, 97, 104D3, 43graphicsD2

50、, 5D3, 44“computer”在D1中出现的位置112倒排文档组成倒排文档组成倒排文档一般由两部分组成：词汇表（vocabulary）和记录表（posting list）词汇表是文本或文本集合中所包含的所有不同单词的集合。对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表113一般的倒排索引索引文件可以用任何文件结构来实现索引文件中的词项是文档集合中的词表architecturecomputerdatabaseretrieval.D1, a1D1, a2D1, a3索引项索引项/词表词表索引索引/索引文件索引文件/索

展开阅读全文