自然语言处理课件

meke

贡献于2016-03-06

字数:0 关键词: 数据挖掘

自然语言处理概述 Introduction to Natural Language Processing 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月NLP概述 2 本课重要性 „ 计算机最重要的应用之一是对语言文字的处理 „ 随着互联网的广泛普及,文字信息处理日益重 要 „ 与最新应用密切结合:信息检索、信息安全、 情报分析、决策支持等 „ 中文信息处理技术的进步,对推动中国信息产 业的发展、促进国际文化交流、繁荣中国传统 文化都具有重要现实意义NLP概述 3 目标 „ 掌握自然语言处理特别是中文语言(信 息)处理的主要方法和基本理论,了解自 然语言处理技术的国内外发展现状、主 要研究对象及所面临的问题,接触语言 处理技术的前沿课题,具备运用基本原 理和方法解决科学研究和工程开发中实 际问题的能力。同时为学习机器翻译、 信息检索等后续课程奠定扎实基础。NLP概述 4 什么是自然语言处理 „ Natural Language Processing, NLP „ 是用计算机通过可计算的方法对自然语 言的各级语言单位(字、词、语句、篇 章等等)进行转换、传输、存贮、分析 等加工处理的理论和方法NLP概述 5 相关提法 „ 中文信息处理(Chinese Information Processing) „ 自然语言理解(Natural Language Understanding) „ 计算语言学(Computational Linguistics) „ 人类语言技术(Human Language Technology)NLP概述 6 什么是自然语言 „ 语言是人类交际的工具,是人类思维的 载体 „ 以语音为物质外壳,由词汇和语法两部 分组成的符号系统 „ 是约定俗成的,有别于程序设计语言等 人工语言NLP概述 7 什么是中文? „ 中文是联合国六种工作语言之一 „ 是中国56个民族所使用的主语言 „ 世界上五分之一以上人口的主语言 „ 中文汉字是中国30种文字中使用最广的文字 „ 方块汉字是其基本表现形式 „ 汉字是象形字 „ 汉字代表一种文化NLP概述 8 汉字是一个大字符集 《说文解字》(东汉):9353字 《玉篇》(南朝)收录16,917字 《广韵》(宋代)收字26,194字 《字汇》(明朝)收录33,197字 《康熙字典》(清朝)收录47,043字 《汉语大字典》(1992年)5.6万 《中华字海》(1994年) 8.6万NLP概述 9 汉字的个数和频度 „ GB2312-80:6763 汉字频度表 ────────┰─────────┰────────┰───────── 按频度排列前 N字┃占总出现字数百分比┃按频度排列前 N字┃占总出现字数百分比 ────────╂─────────╂────────╂───────── N=1 ┃ 4% ┃ N=2048 ┃ >98% N=20 ┃ >16.7% ┃ N=3072 ┃ 99.7% N=32 ┃ >21% ┃ N=3838 ┃ 99.9% N=300 ┃ >65% ┃ N=5177 ┃ 99.99% N=600 ┃ >81% ┃ N=6209 ┃ 99.993% ────────┸─────────┸────────┸───────── NLP概述 10 汉字的音 „ 汉字的读音一般可以分为声母和韵母, 声母21个,韵母35个 „ 5种声调,分别为阴平(─),阳平 (/),上声(ˇ),去声(\), 以 及轻声 „ 汉字的字音或音节共有400多种 „ 一千二百多个音调节 „ 同音字现象普遍NLP概述 11 汉字的字形 „ 二维图形结构 „ 三个层次:汉字-部件-笔划 „ 笔划通常分5类:点、横、竖(直)、撇、折?(弯) „ 各种字典由于检索法不同,部首的个数也不同,从一 百多个到六百多个都有。部首的判断也存在着二义性 „ 部首及笔划构成汉字的方法可分为三类: „ 离:例如“旦、八、阳、音”等 „ 接:例如“人、且、石、刀”等 „ 交:例如“力、右、内”等 „ 一般汉字编码部件拆分的优先顺序为离、接、交NLP概述 12 汉语的特点 „ 汉语是大字符集的意音文字 „ 汉语词与词之间没有空格 „ 汉语的同音词较多 „ 汉语没有形态变化 „ 汉语的语法研究尚未规范化 „ 汉语的语言学知识的量化与形式化工作 滞后NLP概述 13 什么是处理 „ 处理是指对信息的接收、存储、转化、传送和 发布等等操作 „ 分级:字级处理、概念处理和智能处理 „ 智能处理的主要研究领域:自然语言理解、计 算机视觉、机器人学及知识工程 „ 智能的未来发展,将会对知识库、专家系统、 推理系统和神经网络等综合应用,达到能够模 拟人类比较复杂的思维和行为NLP概述 14 语言处理的两个层次 „ 字符处理(输入、存储、输出等) „ 内容处理(词语切分,词性标注,结构 分析,意义理解,推理,翻译……等 等)NLP概述 15 内容层的信息处理 „ 形态丰富的语言(inflecting language):处理难 „ 形态不丰富的语言(analytic language):处理更难 汉语 英语 老师都来了 All professors came here. 张老师都来了 Even Professor Zhang came here. 编辑工作很难 Editing is very difficult. 如何当好编辑 How to become a good editor?NLP概述 16 内容层的信息处理NLP概述 17 内容层处理对符号层处理的反作用 „ 连续语音识别 „ 语句级汉字智能键盘输入NLP概述 18 计算机能够理解人的语言吗? „ 结构主义:追求机器的理解机制与人相 同 „ 问题:人类尚不清楚自身理解语言的机制 „ 功能主义:机器的表现与人相同即可 „ 图灵测试:如果通过自然语言的问答,一个人无法 识别和他对话的是人还是机器,那么就应该承认机 器具有智能 „ 如果机器无法像人一样真正理解语言,那么它能够 像人一样表现吗?NLP概述 19 自然语言处理的作用 „ 人机接口 „ 智能拼音键盘输入 „ 语音识别与合成 „ 手写输入 „ 信息处理 „ 文本分类 „ 自动文摘 „ 情报分析 „ 信息安全NLP概述 20 NLP的历史 „ 20世纪50年代起步 „ 提出机器翻译等重要问题 „ 50-60年代采用模式匹配和文法分析方法 „ 对基于理解和基于统计方法的讨论 „ 60年代后期衰落 „ 70-80年代采用了面向受限域的深入理解方法 „ 80年代后期至今统计方法占据主流 „ 大规模语料可用,计算机性能大幅提高 „ 互联网的迅速发展为NLP提供了实验数据来源和新的应用场景NLP概述 21 发展现状 „ 缺乏理论基础和完整体系 „ 浅层问题尚未解决好,已开始挑战深层次问题 „ 面向语音识别和汉字智能键盘输入等基于大规 模真实语料的统计语言建模得到成功应用 „ 面向机器翻译和问答系统等的深层次语言理解 仍不乐观 „ 统计模型与深层次语言知识的结合受到重视 „ 互联网的迅速发展为NLP提出新的挑战:开放 域问题处理,保证时空效率等NLP概述 22 主要困难 „ 歧义(Ambiguity) „ 病构(Ill-Formedness)NLP概述 23 歧义 „ 注音歧义:快乐(le4),音乐(yue4) „ 分词歧义 „ 乒乓球/拍卖/完/了 „ 乒乓球拍/卖/完/了 „ 短语歧义 „ [咬死猎人]的狗 „ 咬死[猎人的狗]NLP概述 24 歧义 „ 词义歧义 „ [打]乒乓球 „ [打]毛衣 „ [打]电话 „ 语用歧义 „ “你真讨厌!”NLP概述 25 病构 „ 未登录词(Unknown Words, Out-of-Vocabulary Words) „ 已知词的新用法 „ 不合乎语法的句子 „ 他非常男人。 „ 不合乎语义约束的搭配 „ My car drinks gasoline like water。 „ 由于疏忽造成的错误NLP概述 26 技术路线 „ 一种是以基于知识的方法为代表的理性主义方 法,该方法以语言学理论为基础,强调语言学 家对语言现象的认识,采用非歧义的规则形式 描述或解释歧义行为或歧义特性 „ 一种是以基于语料库的统计分析为基础的经验 主义方法,该方法更注重用数学方法,从能代 表自然语言规律的大规模真实文本中发现知 识,抽取语言现象或统计规律NLP概述 27 二者区别—研究对象不同 „ 理性主义主要研究人的语言知识结 构,实际的语言数据只提供了这种 内在知识的间接证据。 „ 对经验主义而言,其直接研究对象 就是这些实际的语言数据。NLP概述 28 二者区别—理论基础不同 „ 理性主义的方法通常是基于乔姆斯基的 语言理论的。它通过语言所必须遵守的 一系列原则来描述语言,以此来判断一 个句子是正确的(遵循了语言原则)还是 错误的(违反了语言原则)。 „ 经验主义的方法通常是基于香农 (Shannon)的信息论的。它将语言事件 赋予概率,作为其可信度,由此来判断 一个句子是常见的还是罕见的。NLP概述 29 二者区别—范围不同 „ 理性主义的方法通常是通过对一些特定 领域或范围内的语言现象的研究来得到 对人的语言能力的认识,而这些语言现 象在实际应用中可能并不常见。 „ 经验主义的方法则偏重于对语料库中人 们实际使用的普通语言现象的统计表 述。NLP概述 30 二者区别—方法不同 „ 理性主义的具体方法是一个符号处理系 统,是认知心理学家作为人的认知模型 而提出的,在计算语言学中得到广泛的 应用。 „ 经验主义的方法是语料库语言学研究的 主要内容。NLP概述 31 NLP的主要研究内容及分层NLP概述 32 NLP的性质 „ NLP需要的知识非常复杂 „ 理解语言的过程是动态的,不是静态的 „ NLP需要的知识大多是归纳的,不是演绎的 „ 人也不一定能够出一致的理解结果--存在上限 „ NLP是一个非确定性过程 „ 对歧义的限制和系统的覆盖率矛盾 „ 领域词典不充分NLP概述 33 NLP系统的主要任务 „ 知识表示 „ 产生式、谓词逻辑、语义网络、概念从属理论 (CD理论) „ 知识控制策略 „ 知识的冲突 „ 知识集成 „ 从多个知识源获取的不同层面、不同性质的知识 如何融合在一起 „ 知识获取 „ 恳谈式、内省式、机器学习NLP概述 34 NLP的瓶颈 „ 知识获取(Knowledge Acquisition) „ 知识获取和知识表示相关联 „ 规则:人工知识 „ 参数:适合机器学习 „ 混合方法(Hybrid Approach) „ 人设计模型 „ 机器训练参数NLP概述 35 自然语言处理的发展趋势 „ 客观需求 „ 信息产品的多样化 „ 互联网的迅速发展 „ 应对措施 „ 积累更多基础资源 „ 开发更多应用系统 „ 内容层的处理将受到越来越多的重视 „ 注重面向真实文本的评测NLP概述 36 本课主要内容 „ 概述 „ NLP数学基础 „ NLP语言学基础 „ 汉字编码和输入输出 „ 汉语分词和名实体识别 „ 统计语言建模 „ 隐马尔可夫模型 „ 词法 „ 语法 „ 音字转换 „ 统计对齐和机器翻译 „ 信息检索NLP概述 37 本讲义主要参考文献(1) „ 王晓龙,关毅等,计算机自然语言处理,清华大学出版社, 2005.4 „ 苑春法等译,统计自然语言处理基础,电子工业出版社,2005.1 „ Christopher D. Manning, Hinrich Schütze, Foundations of Statistical Natural Language Processing, MIT Press, 1999 „ 冯志伟,孙乐译,自然语言处理综论,电子工业出版社,2005.6 „ Daniel Jurafsky, James H.Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall Press, 2000 „ 王晓龙等,《计算机汉字处理实用技术》,哈工大出版社, 1993.12 „ 翁富良,王野翊,计算语言学导论,中国社会科学出版社, 1998.9NLP概述 38 本讲义参考文献(2) „ 关毅,《中文信息处理》讲义,哈工大自然 语言处理实验室 „ 刘挺,《统计自然语言处理》讲义,哈工大 信息检索实验室 „ 詹卫东,中文信息处理与汉语研究—现状和 发展,北京大学 „ 宗成庆,《自然语言理解》讲义,中科院自动 化所 „ 徐从富,《隐马尔可夫模型》讲义,浙江大 学人工智能研究所NLP概述 39 本讲义参考文献(3) „ 王晓明,ISO/IEC 10646/Unicode 最新进展及其实现 „ Unicode标准网站:http://www.unicode.org/ „ 微软公司核心技术书库,《国际化软件开发》第二 版,机械工业出版社,2003.8 „ 《信息技术—信息交换用汉字编码字符集基本集的 扩充》,中华人民共和国国家标准,国家质量技术 监督局,2000.3 „ Summary,Explanations,And Remarks:GB 18030-2000, from Unicode 网站,作者email:dmeyer@adobe.com „ 纳讯中文信息处理技术网站:http://naxun.sjtu.edu.cn/谢谢!NLP数学基础 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月NLP数学基础 2 NLP数学基础 „ 概率论与数学统计 „ 信息论 „ 建模方法 „ 最优化方法NLP数学基础 3 概率论 „ 概率 „ 最大似然估计 „ 条件概率 „ 贝叶斯公式 „ 二项式分布 „ 期望 „ 方差NLP数学基础 4 概率(Probability) )(AP 为事件 A 的概率, Ω 是实验的样本空间,则概率函数必 须满足如下公理: 公理 1: 0)( ≥AP ; 公理 2: 1)( =ΩP ; 公理 3:如果对任意的i 和 j ( ji ≠ ),事件 iA 和 jA 不相交 ( Φ=∩ ji AA ),则: ∑ ∝ = ∝ = = 00 )()( i i i i APAP U 。 NLP数学基础 5 最大似然估计(Maximization likelihood estimation, MLE) 一个试验的样本空间是{ 1s , 2s ,… , ns },在相同情况下重复试验 N 次,观 察到样本 ks ( nk ≤≤1 )的次数为: )( kN sn ,则 ks 的 相对频率为: N snsq kN kN )()( = , ∵ ∑ = = n k kN Nsn 1 )( , ∴ ∑ = = n k kN sq 1 1)( 当 N 越来越大时,相对频率 )( kN sq 就越来越接近 ks 的概率 )( ksP : )()(lim kkN N sPsq = →∝ ,因此相对频率常被用作概率的估计值,这种估计方 法称为最大似然估计。 NLP数学基础 6 现代汉语字频统计结果: 前20个最高频汉字及其频率 汉字 频率 汉字 频率 汉字 频率 汉字 频率 的 0.040855 了 0.008470 中 0.006012 国 0.005406 一 0.013994 有 0.008356 大 0.005857 我 0.005172 是 0.011758 和 0.007297 为 0.005720 以 0.005117 在 0.010175 人 0.006821 上 0.005705 要 0.004824 不 0.009034 这 0.006557 个 0.005488 他 0.004685NLP数学基础 7 条件概率(conditional probability) 如果 A 和 B 是样 本空间 Ω 上的两个事件 , 0)( >BP ,那么在给定 B 时 A 的条件概率 )|( BAP 为: )( )()|( BP BAPBAP ∩= , 一般地 , )()|( APBAP ≠ 。 NLP数学基础 8 例 „ 当预测“大学”一词出现的概率时,如果 已经知道出现在它前面的两个词是“哈尔 滨”和“工业”,“大学”一词出现的概率会 大大增加NLP数学基础 9 全概率公式 设 Ω 为实验的样本空间, 1B , 2B ,…, nB 为Ω 的一组两两互斥的事 件,且每次试验中至少发生一个,则称 1B , 2B ,…, nB 为样本空间 Ω 的一 个划分。 如果 A 为样本空间Ω 的事件, 1B , 2B ,…, nB 为样本空间Ω 的一个 划分,且 0)( >iBP ( ni ,,2,1 L= ),则全概率公式为: ∑∑ === ==∪= n i n i iiii n i BAPBPABPABPAP 111 )|()()()()( NLP数学基础 10 贝叶斯定理(Bayes’ Theorem) 如果 A 为样本空间 Ω 的事件, 1B , 2B ,…, nB 为样本空间 Ω 的一个划分,且 0)( >AP , 0)( >iBP ( ni ,,2,1 L= ),则: ∑ = = n j jj ii i BAPBP BAPBPABP 1 )|()( )|()()|( , 当 1=n 时, )( )()|()|( AP BPBAPABP = NLP数学基础 11 先验概率、后验概率 „ 先验概率(Prior probability):不考虑先决 条件(信息或者知识)而得到的该事件 的概率:一般在试验前已知,常常是以 往经验的总结 „ 后验概率(Posterior probability):在具备 该事件出现的信息或者知识的条件下得 到的该事件的概率:反映了试验之后对 各种原因发生的可能性大小的新知识NLP数学基础 12 例 例:输入语音信号 A ,找到对应的语句 S ,使 得 )|( ASP 最大,则 )|(maxarg ^ ASPS S = ,根据贝叶斯公式, )( )|()(maxarg ^ AP SAPSPS S = ,由于 )( AP 在 A 给定时是归一化 常数,因而, )|()(maxarg ^ SAPSPS S = 。 其中 )|( SAP 为语音识别中的声学模型, )(SP 为语言模 型。 NLP数学基础 13 例 „ 假设某一种特殊的句法结构很少出现,平均大 约每100,000个句子中才可能出现一次。我们 开发了一个程序来判断某个句子中是否存在这 种特殊的句法结构。如果句子中确实含有该特 殊句法结构时,程序判断结果为“存在”的概率 为0.95。如果句子中实际上不存在该句法结构 时,程序错误地判断为“存在”的概率为0.005。 那么,这个程序测得句子含有该特殊句法结构 的结论是正确的概率有多大?NLP数学基础 14 解 假设G表示事件“句子确实存在该特殊句法结构”,T 表示事件“程 序判断的结论是存在该特殊句法结构”。那么: 00001.0100000 1)( ==GP , 99999.0100000 1100000)( =−=GP , 95.0)|( =GTP , 005.0)|( =GTP 求解: ?)|( =TGP 002.099999.0005.000001.095.0 00001.095.0 )()|()()|( )()|()|( ≈×+× ×= + = GPGTPGPGTP GPGTPTGP NLP数学基础 15 二项式分布 (binomial distribution) 当重复一个只有两种输出(假定为 A 和 A )的试验(伯努利试验), A 在一次实验中发生的概率为 p ,现将实验独立地重复 n 次,如果用 X 表示 A 在这 n 次实验中发生的次数,那么, nX ,,1,0 L= 。则 n 次独立实验中 成功的次数为 r 的概率为: rnrr nr ppCp −−= )1( ,其中, !)!( ! rrn nC r n −= , nr ≤≤0 。此时 X 所遵从的概率分布称为二项式分布,并记为: ),(~ pnBX 。 自然语言处理中常以句子为处理单位,一般假设一个语句独立于它前面 的其他语句,句子的概率分布近似地认为符合二项式分布。 NLP数学基础 16 期望(Expectation) 期望值是一个随机变量所取值的概率平均。设 X 为 一随机变量,其分布为 kk pxXP == )( , L,2,1=k , 若级数∑ ∝ =1k kk px 绝对收敛,那么随机变量 X 的数学期望 或概率平均值为: ∑ ∝ = = 1 )( k kk pxXE 。 NLP数学基础 17 方差(Variance) 一个随机变量的方差描述的是该随机变量的值偏 离其期望值的程度。设 X 为一随机变量,其方差为: )()()))((()( 222 XEXEXEXEXVar −=−=NLP数学基础 18 信息论 „ 1948年美国Shannan香农“通信的数学理论”, 用概率测度和数理统计的方法,系统地讨论了 通信的基本问题,奠定了信息论的基础 „ 什么是信息? „ 信息的度量有三个基本方向:结构的、统计的 和语义的 „ 香农所说的信息是狭义的信息,是统计信息, 依据是概率的不确定性度量NLP数学基础 19 内容 „ 熵 „ 联合熵 „ 互信息 „ 相对熵 „ 交叉熵 „ 迷惑度 „ 噪声信道模型NLP数学基础 20 熵(Entropy) 熵表示信息源 X 每发一个符号所提 供的平均信息量。 熵也可以被视为描述一个随机变量 的不确定性的数量。一个随机变量的熵越 大,它的不确定性越大,正确估计其值的 可能性就越小。越不确定的随机变量越需 要大的信息量用以确定其值。 NLP数学基础 21 熵的定义 如果 X 是一个离散型随机变量,其概率分布为: )()( xXPxp == , Xx∈ ,则 X 的熵 )(XH 为: ∑ ∈ −= Xx xpxpXH )(log)()( 2 ,其中约定 00log0 = 。 )(XH 也可以写为 )(pH ,通常熵的单位为二进制位比 特(bit)。 NLP数学基础 22 抛非均匀硬币事件的熵值 横轴表示硬币正面朝上的概率,纵轴表示抛一次硬币试验的熵值NLP数学基础 23 英语字母的熵-等概率情况 70.426log)26 1log26 1(26 )(log)()( 22 2 ==−×= −= ∑ ∈Xx xpxpXHNLP数学基础 24 英语字母的熵-实际出现情况 „ 例:考察英语中特定字母出现的频率。 当观察字母的个数较少时,频率有较大 幅度的随机波动,但当观察数目增大 时,频率即呈现出稳定性,有人统计了 438023个字母得到如下表所示的数据。 „ 根据熵的定义计算,每收到一个英文信 号的不确定程度是4.1606比特。NLP数学基础 25 特定英语字母的出现频率 字母 频率 字母 频率 字母 频率 E 0. 1268 L 0.03 94 P 0.0186 T 0. 0978 D 0.0389 B 0.0156 A 0.0788 U 0.0280 V 0.0102 O 0. 0776 C 0.0268 K 0.0060 I 0. 0707 F 0.0256 X 0.0016 N 0. 0706 M 0.0244 J 0.0010 S 0. 0634 W 0.0214 Q 0.0009 R 0. 0594 Y 0.0202 Z 0.0006 H 0. 0573 G 0.0187 NLP数学基础 26 比较 „ 考虑了英文字母实际出现的概率后,英 文信源的平均不确定性,比把字母看作 等概率出现时英文信源的平均不确定性 要小 „ 均衡分布的熵最大NLP数学基础 27 汉字的熵 „ 中文有6000多个常用字,经中国冯志伟 等人测算,汉字的信息熵随着汉字个数 的增加而增加,当汉字的个数达到12366 个汉字时,汉字的信息熵值为9.65比 特。因此,汉字机内码必须用两个字节 才能表示一个汉字。NLP数学基础 28 联合熵(Joint Entropy) 如果 X 、Y 是一对离散型随机变量,其联合 概率分布密度函数为 ),( yxp ,X 、Y 的联合熵定 义为: ∑∑ ∈∈ −= XxYy yxpyxpYXH ),(log),(),( 2 。 联合熵就是描述一对随机变量平均所需要的 信息量。 NLP数学基础 29 条件熵(Conditional Entropy) 如果离散型随 机变 量( X , Y )的联合概率分 布密 度函数 为 ),( yxp ,已 知 随 机 变 量 X 的情况 下随机变 量 Y 的条件 熵定义为: ∑∑ ∑∑ ∑ ∈∈ ∈∈ ∈ −= −= == XxYy XxYy Xx xypyxp xypxypxp xXYHxpXYH )|(log),( ])|(log)|()[( )|()()|( 条件熵 表示的是在已知 X 的情况下,传输 Y 额外所 需的平均 信息量 。 NLP数学基础 30 熵的连锁规则 )|()(),( XYHXHYXH += ),|()|()(),( 111211 −+++= nnn XXXHXXHXHXXH LLL NLP数学基础 31 熵的连锁规则 证明: )|()( ))|((log))((log ))|(log)((log )))|()((log( )),((log),( ),()( ),( ),( ),( XYHXH xypExpE xypxpE xypxpE yxpEYXH yxpxp yxp yxp yxp += −−= +−= −= −=NLP数学基础 32 互信息(Mutual Information) 如 果 离散 型随 机 变 量 ( X , Y )的联合概 率分 布密度 函 数为 ),( yxp , X ,Y 之间的 互信 息定 义为 : )|()();( YXHXHYXI −= , 展 开得 到: ∑∑ ∈∈ = XxYy ypxp yxpyxpYXI )()( ),(log),();( 2 互信息 );( YXI 是在知道 了 Y 的值后 X 的不确定 性 的减少 量。 即 Y 的值透 露 了多少关 于 X 的信息 量 。 NLP数学基础 33 互信息(Mutual Information) ∵ 0)|( =XXH , ∴ );()|()()( XXIXXHXHXH =−= 这一方面说明了为什么熵又称自信息,另一 方面说明了两个完全相互依赖的变量之间的互信 息并不是常量,而是取决于他们的熵。 NLP数学基础 34 互信息与熵之间的关系 )|( YXH )|( XYH );( YXI )(XH )(YH ),( YXHNLP数学基础 35 相对熵(Relative Entropy or Kullback-Leibler Divergence) 两个概率分布 )( xp 和 )( xq 的相对熵定义为: ∑ ∈ = Xx xq xpxpqpD )( )(log)()||( , 其中约定 =∝= )0/log(,0)/0log(0 ppq 。 相对熵常被用以衡量两个随机分布的差距。 0)||( ≥qpD ,当 且仅当两个随机分布相同时,其相对熵为 0,当两个随机分布的差 别增加时,其相对熵也增加。 )||()||( pqDqpD ≠ 。 NLP数学基础 36 交叉熵(Cross Entropy) 如果一个随机变量 X 的概率分布为 )(xp , )(xq 为用于近似 )(xp 的概率分布,那么随机变量 X 和模型 q 之间的交叉熵定义为: ∑−= += x xqxp qpDXHqXH )(log)( )||()(),( 交叉熵的概念是用来衡量估计模型与正式概率 分布之间差异的。 NLP数学基础 37 语言与其模型的交叉熵 概率分布为 )(xp 的语言 )( iXL = 与其模型 q 的交 叉 熵定义 为: ∑→∝ −= nx nn n xqxpnqLH 1 )(log)(1lim),( 11 其中, n n xxx ,,11 L= 为语 言 L 的语句 ; )( 1 nxp 为 L 中语 句 nx1 的概率 ; )( 1 nxq 为模型 q 对 nx1 的概率 估计 。 NLP数学基础 38 语言与其模型的交叉熵 假设在理想情况下,即 n 趋于无穷大时,其全部“单词” 的概率和为 1。即根据信息论的定理:假定语言 L 是稳态 (stationary)ergodic 随机过程, L 与其模型 q 的交叉熵计算 公式就变为: )(log1lim),( 1 n n xqnqLH →∝ −= 。 因此可以根据模型 q 和一个含有大量数据的 L 的样本来 计算交叉熵。在设计模型 q 时,目的是使交叉熵最小,从而使 模型最接近真实的概率分布 )(xp 。 NLP数学基础 39 迷惑度(复杂度,困惑度,Perplexity) 在设计语言模型时,通常用迷惑度来代替交 叉熵衡量语言模型的优劣。给定语言 L 的样本 n n lll L11 = , L 的迷惑度定义为: nnl nqLH q lqPP n 1 1 )log(1 ),( )]([22 1 =≈= 。 语言模型设计的任务就是寻找迷惑度最小 的模型,使其最接近真实的语言。 NLP数学基础 40 信源信道模型 „ 信源-信道模型 : „ I:语言文本;O:声音信号、字符图像信号、 拼音输入等 „ 语言模型: )|()(maxarg)( )|()(maxarg))|((maxargˆ IOpIpOp IOpIpOIpI III === )(Ip i1i2i3…in o1o2o3…on 离散信道模型 谢谢!NLP语言学基础 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月NLP语言学基础 2 语言学基础(英文为主) „ 词性与词法 „ 短语结构 „ 语义和语用 „ 其他研究领域NLP语言学基础 3 词性和词法 „ 语言学家将词按照相似的语法结构行为 和典型的语义类型聚成不同的类,称为 词性(parts of speech,句法类或语法类) „ 词性分类 „ 开放类(词汇类):名词、动词、形容词 „ 封闭类(功能类):介词、限定词 (of,on,the,a等) „ 词性兼类NLP语言学基础 4 词性和词法 „ 词法(构词过程) „ 变形:对词根形式进行系统的修改,通过加前缀 或后缀来指明语法结构的不同,如单数和复数。 并不显著改变词语的类别和语义,但修改一些特 征,如时态、数目等。 „ 派生:缺乏系统化,通常导致语法类别的根本变 化,且涉及含义的变化:wide→widely, difficult→difficultly(×) „ 复合:两个或多个词合成一个新词,如:college degree, overtake, mad cow diseaseNLP语言学基础 5 英语主要词性 „ 名词和代词 „ 名词附属词:限定词(the,a)和形容词 „ 动词:主语数、主语人称、时态、体 态、情态、分词、语态 „ 副词、介词 „ 连词NLP语言学基础 6 短语结构 „ 特定的词语集合的行为类似于一个语法 成分 „ 语法成分可以通过看他们是否能够出现 在不同的位置,并且表现出一致的语法 扩展的可能性而检测到NLP语言学基础 7 位置扩充 „ I put the bagels in the freezer. „ The bagels, I put in the freezer. „ I put in the fridge the bagels (that John had given me)NLP语言学基础 8 短语扩充 She The woman The tall woman The very tall woman The tall woman with sad eyes ⋯ him the man the short man the very short man the short man with red hair ⋯ saw NLP语言学基础 9 短语结构 S NP VP That man VBD NP PP caught the butterfly IN NP with a net NLP语言学基础 10 名词短语 „ 名词短语(NP)是句子中名词信息聚集起 来的句法结构单位。名词是名词短语的 中心词,是决定这个短语语法性质的核 心成分。 „ The homeless old man in the park that I tried to help yesterdayNLP语言学基础 11 介词短语 „ 介词短语(PP)以介词开始并且包含一个 名词短语补语。它们可以出现在其他所 有主要短语类型中,特别是在名词短语 和动词短语中用来表示空间、时间、位 置以及其他属性。 „ In the morning, to the west, at the same place, etc.NLP语言学基础 12 动词短语 „ 动词短语(VP)以动词为中心词,通常在 句法结构上依靠动词来组织起句子的所 有元素 „ Getting to school on time was a struggle. „ He was trying to keep his temper. „ That woman quickly showed me the way to hide.NLP语言学基础 13 形容词短语 „ AP,复杂形容词短语较少见。 „ She is very sure of herself. „ He seemed a man who was quite certain to succeed.NLP语言学基础 14 短语结构语法 „ 词语顺序规则经常被表述成重写规则 „ 形式:类别→类别 „ 左边的符号序列可以重写为右边的符号 序列 „ 生成语言的一个句子,以初始符‘S’开始NLP语言学基础 15 重写规则举例(上下文无关文法) S → NP VP NP → AT NN S | AT N N | N P PP VP → VP PP | VBD | VBD NP PP → IN NP AT → the NNS → children | students | mountains VBD → slept | ate | saw IN → in | of NN → cake NLP语言学基础 16 派生句子 S → NP VP → AT NNS VBD → The children slept S → NP VP → AT NNS VBD NP → AT NNS VBD AT NN → The children ate the cake NLP语言学基础 17 短语结构表示:树 „ 叶结点作为终结结点,内部结点作为非 终结结点 „ 每个非终结结点和它的直接子结点或局 部树对应重写规则的一个应用 „ 子结点的顺序生成了句子中词语的顺序 „ 树只有一个根结点,是语法的开始符 „ 分析树对应句子的派生NLP语言学基础 18 短语结构表示:带标记的括号 „ 括号集合划出了各成分并且通过加标记 表示了非终结符的类别。 „ [S[NP[AT The][NNS children]][VP[VBD ate][NP[AT the][NN cake]]]]NLP语言学基础 19 递归:重写规则被使用多次 S NP VP D T NNS VBD NP the s tudents ate NP PP DT NN IN NP t he c ake o f NP PP DT NN I N NP the c hildren i n DT NN the m o untains NLP语言学基础 20 远距离依存关系 „ The women who found the wallet were given a reward. „ Which book should Peter buy? „ 远距离依存关系对很多统计NLP方法都是 一个挑战,如N-gram模型 „ 怎样包含必要的依存关系是概率分析的 一个中心议题NLP语言学基础 21 句法分析和短语结构歧义 „ 句法分析是指给出一个特殊的词语序列,重构 它的派生或者短语结构树的过程 „ 根据句子构建的一棵短语结构树称为一个分析 „ 多数情况下,对一个特定的词语序列可以给出 多个不同的短语结构树;一个基于英语中完全 语法的句法分析器通常能找到一个句子的上百 个分析。这种现象称为短语结构歧义或句法结 构歧义。NLP语言学基础 22 例子 „ Our company is training workers. „ 多种分析结果NLP语言学基础 23 分析树a S NP VP Our company Aux VP is V NP traini ng w orkers NLP语言学基础 24 分析树b S NP VP Our company V NP is VP V NP training w orkers NLP语言学基础 25 分析树c S NP VP Our company V NP is AdjP N training workers NLP语言学基础 26 附着(Attachment)歧义 „ The children ate the cake with a spoon. „ 发生在可以被两个不同结点生成的短语 中 „ 不同的附着有不同的含义 „ 解决附着歧义对于找到正确的语义解释 非常重要NLP语言学基础 27 分析树a S NP VP AT NNS VP PP The children VBD NP IN NP ate AT NN with AT NN the cake a spoon NLP语言学基础 28 分析树b S NP VP AT NNS VBD NP The children ate N P PP AT NN I N NP t he c ake w ith AT NN a sp oon NLP语言学基础 29 Garden Pathing „ The horse raced past the barn fell. „ 分析1:理解为 The horse ran past the barn,此时 fell无法加入到分析中 „ 分析2:回溯到raced,理解为 The horse fell after it had been raced past the barn „ Garden Pathing是一种进入可疑分析后不 得不回溯尝试重新构造正确分析的现象NLP语言学基础 30 歧义原因 „ 语法歧义 „ 根本找不到对应的句法分析 „ 语法中缺少或没有所用的规则 „ 该句子不合乎语法,或语法结构本身不完整:Slept children the. „ 区分“不合乎语法”与“语义异常” „ Colorless green ideas sleep furiously „ The cat barkedNLP语言学基础 31 语义 „ 语义研究词语的含义、结构和说话的方 式 „ 研究单个词的语义(词义) „ 单个词的含义怎样联合起来组成句子(或更大的单 位)的含义NLP语言学基础 32 词义 „ 研究词义之间怎样相互联系 „ 上下位 (hypernymy)关系:动物—猫 „ 反义词(antonym) „ 部分—整体 (meronymy)关系:轮胎—汽车 „ 整体—部分(holonym)关系 „ 同义词(synonym):意义相同或相近 „ 同形异义词(homonym):suit (lawsuit, set of garment),bank (river bank, financial institution) „ 多义词(polyseme): branch,多个意思相关 „ 同音异义词(homophony):同样写法,同样发音,bass(分别指一种鱼 和一种低音时是同形异义词,但不是同音异义词) „ 词汇歧义涉及到同形异义词和多义词NLP语言学基础 33 词语搭配 „ 词white在不同环境下涉及不同颜色 „ white paper:白色的 „ white hair:灰色的 „ white skin:带红点的 „ white wine:黄色的 „ 整体含义是指各部分含义之和加上一些不能从 各部分推导出来的额外的语义信息 „ 成语:kick the bucket (dying), carriage return, 词语含义与短语含义之间关系很远NLP语言学基础 34 作用范围 „ 数量词和操作的作用范围可以超越一个 或多个短语或句子 „ 例:Everyone didn’t go to the movie. „ 可以把数量词everyone的范围定在否定词not上 (没有一个人去看电影) „ 也可把否定范围定在数量词上(至少有一个人没有 去看电影) „ 需根据上下文确定正确含义NLP语言学基础 35 语用 „ 篇章(discourse)分析:阐明文本中句 子之间隐含的关系,是语用论研究的 重要部分 „ 语用论:研究世界知识和语言习惯是 怎样与字面含义相互影响的 „ 语用论的两个重要领域: „ 指代关系消解 „ 对话中的语言行为建模?NLP语言学基础 36 指代消解 „ 指代关系发生在涉及到同一个人或物的多个名 词短语之间,是一种语用现象,受世界知识的 约束 „ 对信息抽取至关重要:识别、跟踪事件中的参 与者及其他信息 „ 例:Hurricane Hugo destroyed 20000 Florida homes. At an estimated cost of one billion dollars, the disaster has been the most costly in the state’s history. „ 要解决例文中的指代关系,就必须知道 hurricane是一种disasterNLP语言学基础 37 句法、语义、语用的关系 „ 句法结构相同,语义不同 „ “吃苹果”,“吃食堂” „ 句法:动宾结构 „ 语义分别为:动作-对象关系,动作-地点关系 „ 语义相同,句法结构不同 „ “吃了苹果”,”苹果吃了” „ 语义:动作-对象 „ 句法分别为:动宾关系和主谓关系 „ 语用 „ 语义相同,语用有别 „ 主席台上摆着鲜花(主席台是旧信息,鲜花是新信息) „ 鲜花摆在主席台上(主席台是旧信息,鲜花是新信息)NLP语言学基础 38 语言理解的步骤 „ 文本预处理 „ 句子切分 „ 形态分析(Morphological Analysis) „ 分词 „ 词性标注(Part-of-Speech Tagging) „ 句法分析 „ 词义消歧(Word Sense Disambiguation) „ 语义关系分析 „ 指代消解(Anaphora Resolution) „ 逻辑形式(Logic Form)NLP语言学基础 39 其他研究领域 „ 特殊研究领域 „ 社会语言学:研究社会组织和语言之间的相互作用 „ 历史语言学:研究语言如何随时代变迁而变化 „ 语言分类学:研究语言对语言学工具的不同使用, 以及它们是怎样基于所用工具的方式被分成不同类 的 „ 语言获取:研究儿童如何学习语言 „ 心理语言学:研究实时语言的产生和语言理解问 题,以及语言展现在脑海里的方式 „ 数理语言学: 实现一些使用非定量数学思想的方法谢谢!汉字编码和输入输出 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月汉字编码和输入输出 2 汉字编码 „ 现状 „ 主要编码标准和规范 „ 国标码 „ Unicode „ Windows对Unicode的支持 „ GB18030汉字编码和输入输出 3 汉字编码现状及其根源 „ 多种编码方案共存,不利于交流和共享 „ 新旧标准同台使用,需相互转换 „ 统一标准正在形成 „ 中、日、韩、新等多国同时使用汉字 „ 简繁体汉字并存 „ 地区、国家间的文化、政治差异增加了汉字统 一编码的难度汉字编码和输入输出 4 主要汉字(文字)编码标准与规范 „ ASCII(英文) „ GB2312 „ GBK „ GB13000 „ GB18030 „ BIG5 „ Shift_JIS „ ISO/IEC 10646 „ Unicode汉字编码和输入输出 5 汉字的几种通行名称 „ Hanzi, Hantsu, 汉字 „ Ideographic character,表意字符,中文 字符 „ Kanji-日文中的叫法 „ Hanja-朝鲜文中的叫法 „ CJK-中日韩通用字符集 „ Unihan汉字编码和输入输出 6 ASCII码 „ 美国信息交换标准编码(“美标”) „ 用从0到127的128个数字来代表信息的规 范编码 „ 包括33个控制码,一个空格码,和94个 形象码 „ 形象码中包括了英文大小写字母,阿拉 伯数字,标点符号等 „ 国际上大部分电脑的通用编码汉字编码和输入输出 7 文本文件与二进制文件 „ 字符大都是用一个八位二进制数字表示,美标 只规定了128个编码,剩下的另外128个数码没 有规范,美标中的33个控制码,各厂家用法也 不尽一致 „ 文本文件(ASCII Text Files) :美标形象码或空 格码组成,通常可在不同电脑系统间直接交换 „ 二进制文件(Binary Files) :含有控制码或非美 标码的文件,通常不能在不同电脑系统间直接 交换汉字编码和输入输出 8 国标、区位、“准国标” 、机内码 „ 国标:中华人民共和国国家标准信息交换用汉 字编码 „ 国标(GB2312-80)表(基本表)把七千余汉 字、以及标点符号、外文字母等,排成一个94 行、94列的方阵 „ 每一横行叫一个“区”,每个区有九十四个“位” „ 一个汉字在方阵中的坐标,称为该字的“区位 码” „ 例如“中”字在方阵中处于第54区第48位, 它的区位码就是5448汉字编码和输入输出 9 区位码表 „ 区位码来源于信息交换用汉字编码字符集(基本集)国家标准 (GB2312-80),该标准收汉字6763个,第一级3755个,位于16至55 区,55区的最后5个字符没有定义;第二级3008个,位于56至87区 „ 第一级汉字按照汉语拼音字母顺序排列,同音字以笔形顺序横 (一)、直(丨)、撇(丿)、点(丶)、折(乙)为序。起笔 相同按第二笔,依次类推。 „ 第二级汉字按部首排序,本标准采用的部首与一般字典用的部首 基本相同,略有改并。部首次序及同部首字按笔划数排列,同笔 划数的字以笔形顺序横(一)、直(丨)、撇(丿)、点 (丶)、折(乙)为序。起笔相同按第二笔,依次类推。 „ 查表时先查区号,再查行、列,例如:“、”是0102,“蔼”是 1610。汉字编码和输入输出 10 例 01 区 1 2 3 4 5 6 7 8 9 02 区 1 2 3 4 5 6 7 8 9 0 、 。 · ˉ ˇ ¨ 〃 々 0 ⅰ ⅱ ⅲ ⅳ ⅴ ⅵ ⅶ ⅷ ⅸ 1 — ~ ‖ ⋯ ‘ ’ “ ” 〔 〕 1 ⅹ             ⒈ ⒉ ⒊ 2 〈 〉 《 》 「 」 『 』 〖 〗 2 ⒋ ⒌ ⒍ ⒎ ⒏ ⒐ ⒑ ⒒ ⒓ ⒔ 3 【 】 ± × ÷ ∶ ∧ ∨ ∑ ∏ 3 ⒕ ⒖ ⒗ ⒘ ⒙ ⒚ ⒛ ⑴ ⑵ ⑶ 4 ∪ ∩ ∈ ∷ √ ⊥ ∥ ∠ ⌒ ⊙ 4 ⑷ ⑸ ⑹ ⑺ ⑻ ⑼ ⑽ ⑾ ⑿ ⒀ 5 ∫ ∮ ≡ ≌ ≈ ∽ ∝ ≠ ≮ ≯ 5 ⒁ ⒂ ⒃ ⒄ ⒅ ⒆ ⒇ ① ② ③ 6 ≤ ≥ ∞ ∵ ∴ ♂ ♀ ° ′ ″ 6 ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩     ㈠ 7 ℃ $ ¤ ¢ £ ‰ § № ☆ ★ 7 ㈡ ㈢ ㈣ ㈤ ㈥ ㈦ ㈧ ㈨ ㈩   8 ○ ● ◎ ◇ ◆ □ ■ △ ▲ ※ 8   Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ Ⅸ 9 → ← ↑ ↓ 〓 9 Ⅹ Ⅺ Ⅻ     汉字编码和输入输出 11 例 09 区 1 2 3 4 5 6 7 8 9 0       ─ ━ │ ┃ ┄ ┅ 1 ┆ ┇ ┈ ┉ ┊ ┋ ┌ ┍ ┎ ┏ 2 ┐ ┑ ┒ ┓ └ ┕ ┖ ┗ ┘ ┙ 3 ┚ ┛ ├ ┝ ┞ ┟ ┠ ┡ ┢ ┣ 4 ┤ ┥ ┦ ┧ ┨ ┩ ┪ ┫ ┬ ┭ 5 ┮ ┯ ┰ ┱ ┲ ┳ ┴ ┵ ┶ ┷ 6 ┸ ┹ ┺ ┻ ┼ ┽ ┾ ┿ ╀ ╁ 7 ╂ ╃ ╄ ╅ ╆ ╇ ╈ ╉ ╊ ╋ 8                     9 汉字编码和输入输出 12 例 16 区 1 2 3 4 5 6 7 8 9 17 区 1 2 3 4 5 6 7 8 9 0 啊 阿 埃 挨 哎 唉 哀 皑 癌 0 薄 雹 保 堡 饱 宝 抱 报 暴 1 蔼 矮 艾 碍 爱 隘 鞍 氨 安 俺 1 豹 鲍 爆 杯 碑 悲 卑 北 辈 背 2 按 暗 岸 胺 案 肮 昂 盎 凹 敖 2 贝 钡 倍 狈 备 惫 焙 被 奔 苯 3 熬 翱 袄 傲 奥 懊 澳 芭 捌 扒 3 本 笨 崩 绷 甭 泵 蹦 迸 逼 鼻 4 叭 吧 笆 八 疤 巴 拔 跋 靶 把 4 比 鄙 笔 彼 碧 蓖 蔽 毕 毙 毖 5 耙 坝 霸 罢 爸 白 柏 百 摆 佰 5 币 庇 痹 闭 敝 弊 必 辟 壁 臂 6 败 拜 稗 斑 班 搬 扳 般 颁 板 6 避 陛 鞭 边 编 贬 扁 便 变 卞 7 版 扮 拌 伴 瓣 半 办 绊 邦 帮 7 辨 辩 辫 遍 标 彪 膘 表 鳖 憋 8 梆 榜 膀 绑 棒 磅 蚌 镑 傍 谤 8 别 瘪 彬 斌 濒 滨 宾 摈 兵 冰 9 苞 胞 包 褒 剥 9 柄 丙 秉 饼 炳 汉字编码和输入输出 13 例 54 区 1 2 3 4 5 6 7 8 9 55区 1 2 3 4 5 6 7 8 9 0 帧 症 郑 证 芝 枝 支 吱 蜘 0 住 注 祝 驻 抓 爪 拽 专 砖 1 知 肢 脂 汁 之 织 职 直 植 殖 1 转 撰 赚 篆 桩 庄 装 妆 撞 壮 2 执 值 侄 址 指 止 趾 只 旨 纸 2 状 椎 锥 追 赘 坠 缀 谆 准 捉 3 志 挚 掷 至 致 置 帜 峙 制 智 3 拙 卓 桌 琢 茁 酌 啄 着 灼 浊 4 秩 稚 质 炙 痔 滞 治 窒 中 盅 4 兹 咨 资 姿 滋 淄 孜 紫 仔 籽 5 忠 钟 衷 终 种 肿 重 仲 众 舟 5 滓 子 自 渍 字 鬃 棕 踪 宗 综 6 周 州 洲 诌 粥 轴 肘 帚 咒 皱 6 总 纵 邹 走 奏 揍 租 足 卒 族 7 宙 昼 骤 珠 株 蛛 朱 猪 诸 诛 7 祖 诅 阻 组 钻 纂 嘴 醉 最 罪 8 逐 竹 烛 煮 拄 瞩 嘱 主 著 柱 8 尊 遵 昨 左 佐 柞 做 作 坐 座 9 助 蛀 贮 铸 筑 9 汉字编码和输入输出 14 例 56 区 1 2 3 4 5 6 7 8 9 57 区 1 2 3 4 5 6 7 8 9 0 亍 丌 兀 丐 廿 卅 丕 亘 丞 0 佟 佗 伲 伽 佶 佴 侑 侉 侃 1 鬲 孬 噩 丨 禺 丿 匕 乇 夭 爻 1 侏 佾 佻 侪 佼 侬 侔 俦 俨 俪 2 卮 氐 囟 胤 馗 毓 睾 鼗 丶 亟 2 俅 俚 俣 俜 俑 俟 俸 倩 偌 俳 3 鼐 乜 乩 亓 芈 孛 啬 嘏 仄 厍 3 倬 倏 倮 倭 俾 倜 倌 倥 倨 偾 4 厝 厣 厥 厮 靥 赝 匚 叵 匦 匮 4 偃 偕 偈 偎 偬 偻 傥 傧 傩 傺 5 匾 赜 卦 卣 刂 刈 刎 刭 刳 刿 5 僖 儆 僭 僬 僦 僮 儇 儋 仝 氽 6 剀 剌 剞 剡 剜 蒯 剽 劂 劁 劐 6 佘 佥 俎 龠 汆 籴 兮 巽 黉 馘 7 劓 冂 罔 亻 仃 仉 仂 仨 仡 仫 7 冁 夔 勹 匍 訇 匐 凫 夙 兕 亠 8 仞 伛 仳 伢 佤 仵 伥 伧 伉 伫 8 兖 亳 衮 袤 亵 脔 裒 禀 嬴 蠃 9 佞 佧 攸 佚 佝 9 羸 冫 冱 冽 冼 汉字编码和输入输出 15 例 86 区 1 2 3 4 5 6 7 8 9 87 区 1 2 3 4 5 6 7 8 9 0 觥 觫 觯 訾 謦 靓 雩 雳 雯 0 鳌 鳍 鳎 鳏 鳐 鳓 鳔 鳕 鳗 1 霆 霁 霈 霏 霎 霪 霭 霰 霾 龀 1 鳘 鳙 鳜 鳝 鳟 鳢 靼 鞅 鞑 鞒 2 龃 龅 龆 龇 龈 龉 龊 龌 黾 鼋 2 鞔 鞯 鞫 鞣 鞲 鞴 骱 骰 骷 鹘 3 鼍 隹 隼 隽 雎 雒 瞿 雠 銎 銮 3 骶 骺 骼 髁 髀 髅 髂 髋 髌 髑 4 鋈 錾 鍪 鏊 鎏 鐾 鑫 鱿 鲂 鲅 4 魅 魃 魇 魉 魈 魍 魑 飨 餍 餮 5 鲆 鲇 鲈 稣 鲋 鲎 鲐 鲑 鲒 鲔 5 饕 饔 髟 髡 髦 髯 髫 髻 髭 髹 6 鲕 鲚 鲛 鲞 鲟 鲠 鲡 鲢 鲣 鲥 6 鬈 鬏 鬓 鬟 鬣 麽 麾 縻 麂 麇 7 鲦 鲧 鲨 鲩 鲫 鲭 鲮 鲰 鲱 鲲 7 麈 麋 麒 鏖 麝 麟 黛 黜 黝 黠 8 鲳 鲴 鲵 鲶 鲷 鲺 鲻 鲼 鲽 鳄 8 黟 黢 黩 黧 黥 黪 黯 鼢 鼬 鼯 9 鳅 鳆 鳇 鳊 鳋 9 鼹 鼷 鼽 鼾 齄 汉字编码和输入输出 16 国标、区位、“准国标”、机内码 „ 94:美标中形象码的总数,33--126 „ 汉字区、位码各加上32,就会与美标形象码的 范围重合,称为该字的“国标码”,与其相对应的 两个美标符号,为该字的“国标符” „ 如何区分国标符与美标符:国标码的两个数字 各加上128,称“准国标”或“机内码” „ 机内码=(区位码)H + 8080H +2020H汉字编码和输入输出 17 BIG5码 „ 针对繁体汉字的编码,在台湾、香港的 电脑系统中得到普遍应用 第一字节 第二字节 A1~A2 40~7E/A1~FE A3 40~7E/A1~E0 C6 A1~FE 非汉字 C7~C8 40~7E/A1~FE A4~C5 40~7E/A1~FE 一级汉字 C6 40~7E C9~F8 40~7E/A1~FE 二级汉字 81~A0 40~7E/A1~D5 汉字编码和输入输出 18 ISO/IEC 10646 „ 一个国际标准编号,国际标准化组织 (ISO)1993年正式颁布 „ 英文全称:Information technology - Universal Multiple - Octet Coded Character Set,简称UCS „ 中文全称:信息技术--通用多八位编码 字符集,亦称大字符集 „ 宗旨:全球所有文种统一编码汉字编码和输入输出 19 Unicode „ 英文Universal Code的缩略语 „ 统一编码 „ 是对国际标准ISO/IEC 10646编码的一种称谓 „ 是一个企业联盟集团的名称,由美国的HP、 Microsoft、IBM、Apple等几家知名的大型计 算机企业所组成,成立该集团的宗旨就是要推 进多文种的统一编码 „ 就内容而言,Unicode和ISO/IEC 10646是一致 的,并行的汉字编码和输入输出 20 CJK-中日韩统一汉字 „ 把中国、日本与韩国的英文称谓的首字 母用于ISO/IEC 10646中的中、日、韩统 一编码汉字的简称 „ Unihan „ CJKV或许更准确,V代表越南汉字编码和输入输出 21 ISO/IEC 10646 的体系结构 „ 四维的编码空间 „ 总体上分为128个三维组(group), group的值范围是 从00到7F „ 每一组包含256个平面(plane),每一个平面包含256行 (row),每一行包含256个字位(cell),又称为 “列”,plane、row、cell的值范围都是从00到FF全编码 „ 整个编码字符集的每个字符都是由4个八位序列表 示,(按照组八位、面八位、行八位、列八位的顺序) „ 可编码空间为:128*256*256*256=32K*64K汉字编码和输入输出 22 ISO/IEC 10646体系结构图 Group 7F Plane 00 of 7F Group 01 Group 00 Plane FF of Group 00 Plane 02 of Group 00 Plane 01 of Group 00 Plane 00 of Group 00 BMP 汉字编码和输入输出 23 基本多文种平面 „ 第一个平面(00组中的00平面)称作 Basic Multilingual Plane(基本多文种 平面),简称BMP,并在其上规定了双八 位形式,它可以作为双八位编码字符集 使用,即在此平面上仅用行、列两个八位 就可以表示一个编码字符汉字编码和输入输出 24 BMP的最新概貌 „ A-Zone(00至4D行) :拼音文字编码区,拉丁文、阿拉伯 文、日文的平假名及片假名、数学符号等都在此区域 编码 „ CJK Unified Ideographs,Extension A(3400-4DB5)(6000 多码位 ) „ CJK Unified Ideographs(4E00-9FA5)(20902个编码汉字 ) „ 韩文 (AC至D7这44行(44*256=11264)) „ S-ZONE (D8至DF行)for UTF-16 „ R-Zone(E0至FF行):限制使用区,一些兼容字符、字符 的变形显现形式、特殊字符等均放在此区汉字编码和输入输出 25 ISO/IEC 10646空间分配现状 „ 00平面:BMP,被用于全球现已规范语种 的基本文字编码,编码空间已基本饱和 „ 01平面:作为拼音文字辅助平面 „ 02平面:作为汉字辅助平面,CJK Extension B即将放入该平面 „ E0至FF平面:作为该标准的专用平面来使 用 „ 其它空间尚未分配汉字编码和输入输出 26 ISO/IEC 10646中CJK汉字组成 „ CJK统一编码汉字(20902) „ CJK扩充集A(6585) „ CJK扩充集B(4万--)汉字编码和输入输出 27 Unicode编码点的变形 „ 编码点(code point)(或编码单元,code element):(1)表示待处理或交换的已编码 文本单元的最小位组合(2)代码页或 Unicode标准的索引 „ 多种不同技术可以二进制格式表示每个 Unicode编码点,以此区分三种不同 Unicode编码:UTF-8、UTF-16、UTF-32汉字编码和输入输出 28 什么是UTF? „ Unicode transformation format „ UCS transformation format „ 从Unicode码点到唯一字节序列的映射算 法,一一映射,保证无损转换汉字编码和输入输出 29 UTF-16 „ Unicode标准的16位编码形式 „ 为每个字符指定一个16位的值 „ 编码形式与ISO/IEC 10646中的定义形式 相同 „ 以一个16位的值来编码映射到不大于 65535数值的字符,映射到大于65535的 数值的字符则被编码成一组16位的值 (代用对)汉字编码和输入输出 30 UTF-8 „ 为满足面向字节、基于ASCII码系统的需要而 制定(主要用于数据传输、互联网) „ 用最多达4个字节的序列来表示每个字符,为 有效分析字符串,用第一个字节指明某个多字 节序列中的字节数 „ 通常用于数据交换 Unicode 编码点和 UTF-8 编码字符之间的关系 Unicode 范围 UTF-8 编码的字节 0x00000000-0x0000007F 0xxxxxxx 0x00000080-0x000007FF 110xxxxx 10xxxxxx 0x00000800-0x0000FFFF 1110xxxx 10xxxxxx 10xxxxxx 0x00010000-0x001FFFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 汉字编码和输入输出 31 UTF-32 „ 每个字符都表示成一个32位的整数 „ 码长相等,便于某些特殊情况的处理 „ Unix系统使用汉字编码和输入输出 32 字节顺序标记(BOM) „ 指示处理器怎样把连续的文本放到一个字节序 列中 „ 权值最低的字节位于开头叫做“little-endian”, 权值最高的字节位于开头叫做“big-endian” „ 可用作识别文本文件编码形式的依据 特定编码的字节顺序标记的十六进制表示 编码 编码后的 BOM UTF-16 big-endian FE FF UTF-16 little-endian FF FE UTF-8 EF BB BF 汉字编码和输入输出 33 代理对(Surrogate pair) „ ISO/IEC 10646 在BMP定义了一个代理区(Surrogate Zone)(D800至DFFF) „ 将这个区域平分为前后两个各容纳1024(1K)个编码的 区域(D800-DBFF及DC00-DFFF),分别称作高半代理 (high surrogate)及低半代理(low surrogate)区域 „ 从这两个区域分别各取一个编码,分别称为高半代理键 (high surrogate key)及低半代理键(low surrogate key),组合成一个4 bytes代理对(surrogate pair) 来表示一个编码字符 „ 由surrogate机制可对应到一百万个字符 (1024x1024),这一百万个字符分别对应到ISO 10646 中00组的00至0F这16个字面(plane) (其他平面如何处 理?)汉字编码和输入输出 34 Windows对Unicode的支持 „ Windows 3.1, Windows NT 4, Windows 2000, Windows XP支持Unicode.如果在这些操作系统 上运行非Unicode编码程序,在处理之前,操 作系统在其内部将应用程序的文本转化为 Unicode编码的文本,在把信息传回应用程序 之前,操作系统把Unicode编码的文本转化回 所希望的代码页编码形式。 „ Windows 95, Windows 98, Windows Me不是 基于Unicode的,它们只提供了基于Windows NT的Windows版本所提供的Unicode支持的一 个子集汉字编码和输入输出 35 创建Win32 Unicode应用程序 „ WCHAR,一种16位的数据类型 用于8位(ANSI)和双字节字符: typedef char CHAR; typedef CHAR TCHAR; 用于Unicode(宽)字符: typedef unsigned short WCHAR; typedef WCHAR TCHAR;汉字编码和输入输出 36 创建Win32 Unicode应用程序 „ Win32 API的W函数原型 //windows.h #ifdef UNICODE #define SetWindowText SetWindowTextW #else #define SetWindowText SetWindowTextA #endif //UNICODE汉字编码和输入输出 37 创建Win32 Unicode应用程序 „ Unicode文本宏 LPWSTR str = L”This is a Unicode string”; …… #ifdef UNICODE #define TEXT(string) L#string #else #define TEXT(string) string #endif //UNICODE …… LPWSTR str = TEXT(”This is a Unicode string”);汉字编码和输入输出 38 创建Win32 Unicode应用程序 „ C运行库扩展 处理字符串的C运行库函数举例 通用CRT 8位字符集 Unicode _tcscpy strcpy wcscpy _tcscmp strcmp wcscmp 等价的Win32 API函数 通用Win32 8位字符集 Unicode lstrcpy lstrcpyA lstrcpyB lstrcmp lstrcmpA lstrcmpB汉字编码和输入输出 39 GBK „ 汉字内码扩展规范,Rules/Specifications defining the extensions of internal codes for Chinese ideograms „ 为了推进Unicode的实施,同时也是为了向下 兼容,由电子部与国家技术监督局联合颁布 „ 在保持GB2312原貌的基础上,将其字汇扩充与 ISO 10646中的CJK等量,同时也包容了台湾的 工业标准Big5码汉字,此外还为用户留了1894 个码位的自定义区汉字编码和输入输出 40 GB18030-2000 „ 信息技术-信息交换用汉字编码字符集-基 本集的扩充,Information technology- Chinese ideograms coded character set for information interchange-Extension for the basic set „ GBK的替代、超集汉字编码和输入输出 41 GB18030-2000 „ 完全包含CJK(Unihan) Extension A „ 与GBK完全兼容(code- and character- compatible)的同时,为所有其它Unicode 码点提供了空间 „ 定义了4字节编码机制汉字编码和输入输出 42 GB18030-2000码位范围分配表 字节数 码位空间 第一字节 第二字节 双字节 0x81—0xFE 0x40—0x7E, 0x80—0xFE 第一字节 第二字节 第三字节 第四字节 四字节 0x81—0xFE 0x30—0x39 0x81—0xFE 0x30—0x39 „ 2字节编码共23940个码位 „ 4字节编码共超过150万个码位汉字编码和输入输出 43 ISO 10646/Unicode的实现及其重要意义 „ 在全球范围内建立起实时、无障碍的信息交换 模式 „ 推动了汉字典籍的数字化 „ 为数字化图书馆的建立铺平了道路 „ 为弘扬汉字文化提供了舞台 „ Single Binary技术的诞生:同一套基本程序 用于多个语言环境的技术 „ 使汉字关联活起来:正-异关联、中-日关联、 繁-简关联,正-讹关联以及古今、新旧字形关 联汉字编码和输入输出 44 汉字输入输出 „ 汉字输入 „ 汉字输出 „ 中文字处理和精密汉字编辑排版系统 „ 操作系统的汉化汉字编码和输入输出 45 计算机汉字系统的构成 ┎────┒ ┎────┒ ┎────┒ ┃键盘输入┠┒ ┃汉 字 库┃┎→┃语音输出┃ ┖────┚┃ ┎─────┒ ┖─┰──┚┃ ┖────┚ ┎────┒┃机内码┃系统软件和┃ 机内码 ┎─┸──┒┃ ┎────┒ ┃语音输入┠╂──→┃应用软件进┠───→┃输出控制┃╂→┃汉字显示┃ ┖────┚┃ ┃行信息处理┃ ┖─┰──┚┃ ┖────┚ ┎────┒┃ ┖─────┚ ┎─┸──┒┃ ┎────┒ ┃文字识别┠┚ ┃磁盘存储┃┖→┃汉字打印┃ ┖────┚ ┖────┚ ┖────┚汉字编码和输入输出 46 汉字输入方式的分类汉字编码和输入输出 47 现状与趋势 „ 目前中文输入以键盘输入为主,最快可 达275字/分 „ 未来的一段时间,改进后的智能化键盘 输入方式仍将占据主导地位 „ 识别输入方式在不断完善自身技术的前 提下,也将获得稳步的增长 „ 多元化的格局正在形成之中汉字编码和输入输出 48 键盘输入方案 „ 整字键盘—大键盘:主辅式、感应式 „ 通用组合键盘—小键盘 „ 字: 记忆代码:电报、区位、军码等 拼音:全拼、双拼、简拼、智能ABC、新拼、自然 拼形:五笔形、郑码、表形码 音形结合:李码、全息码 笔划或部件:魏码 „ 词:联想,高频先见(上),用过提前,词、短语和熟句均可 „ 句:微软拼音、智能狂拼 „ 数字键盘:手机、智能家电 „ 趋势:朝着易学习、易记忆、编码长度要短、重码要少、智能化 的方向发展汉字编码和输入输出 49 字形识别系统 „ 印刷体 „ 单字型 „ 字型混排,北信 „ 中英混排,清华紫光 „ 手写体 „ 脱机 „ 联机:汉王笔、蒙恬第一笔、中华第一笔、神调笔 和杨友博士笔汉字编码和输入输出 50 性能与难点 „ 性能:北京捷通软件技术有限公司的录易全能版的扫 描识别速度60-100字/秒,OCR(汉字印刷体识别)识 别率高,对印刷文稿的识别率在99%以上。它的手写 系统可识别简、繁、英文、数字等,可保留亲笔签字 的原迹,笔迹符号代文。全屏书写,一次可连续书写 20多个字不停笔。自学习功能强,电脑能记住笔迹。 „ 提高识别性能的难点 „ 汉字类别多 „ 汉字字形结构复杂 „ 汉字集合中相似字较多,有些汉字的差别仅为一点或一个笔 画汉字编码和输入输出 51 语音输入分类 „ 特定人孤立语音 „ 非特定人孤立语音 „ 特定人连续语音 „ 非特定人连续语音汉字编码和输入输出 52 语音输入现状 „ 中文语音输入技术已经基本成熟 „ 语音输入市场的主角依旧是以IBM为首的国外厂商 „ IBM Via Voice占据了国内语音输入法大半壁江山 „ 不久前成立了中国语音创业联盟,以期联合国内众多 从事语音输入产品研发的企业共同推动国内语音输入 技术的进步 „ 中文之星公司在语音识别方面的研究也进入到了产品 化的阶段 „ 中文的地方语音体系主要有:广东话,闽南话,吴语 等 „ 苹果电脑的中文语音输入系统是全球第一套广东话语 音输入系统,能够将广东语转换成繁体或简体中文汉字编码和输入输出 53 中文混合输入系统 „ 比利时L&H语音产品有限公司的汉语知音(SPK):针对中文输入 的完全一体化的解决方案,可以采用听写、手写或键盘输入方 式,并可以在这些输入方法之间随意切换; 用户无需改变自己的 语音或书写习惯;可以实现语音导航,用语音控制应用程序;可 以实现整句智能输入 „ 北京捷通软件技术有限公司的录易全能版:集识(汉字印刷体识 别)、写(联机手写识别)、说(语音输入)、听(语音输出校 稿)、校(语义、语法校对)为一体 „ 北京汉王科技公司的汉王听写输入系统是口说手写输入中文,汉 王笔与IBM ViaVoice98语音识别核心的完美集成。语音输入与手 写输入无缝链接,方便了编辑修改,每分钟可输入150字以上汉字编码和输入输出 54 汉字的输出 „ 磁盘存储 „ 屏幕显示 „ 纸上印字 „ 语音输出-语音合成技术汉字编码和输入输出 55 汉字库 „ 汉字的点阵式存储 0 1 2 3 4 5 6 7 8 9 101112131415 0 □□□□□■■■■■■■□□□□ 1 □□□□□□□□■□□□□□□□ 2 □□□□□□□□■□□□□□□□ 0 1 2 3 4 5 6 7 3 □□□□□□□□■□□□□□□□ 0 □□□■■■□□ 4 □□□□□□□□■□□□□□□□ 1 □□■□□□■□ 5 □□□□□□□□■□□□□□□□ 2 □■□□□□□□ 6 □■■■■■■■■■■■■■■□ 3 ■□□□□□□□ 7 □□□□□□□□■□□□□□□□ 4 ■□□□□□□□ 8 □□□□□□□■□■□□□□□□ 5 □■□□■■■■ 9 □□□□□□□■□■□□□□□□ 6 □□■□□□■□ 10 □□□□□□■□□□■□□□□□ 7 □□□■■■□□ 11 □□□□□■□□□□□■□□□□ 12 □□□□■□□□□□□□■□□□ 13 □□□■□□□□□□□□□■□□ 14 □□■□□□□□□□□□□□■□ 15 □□□□□□□□□□□□□□□□ 英文字母“G ”和汉字“天”的点阵表示 汉字编码和输入输出 56 点阵数和存储量 ───────┰──────┰────┰───────── ┃ 点阵 ┃ 字数 ┃ 存储量(字节) ───────╂──────╂────╂───────── 简易型汉字 ┃ 16*16 ┃ 87*94 ┃ 261, 696 ───────╂──────╂────╂───────── 普通型字库 ┃ 24*24 ┃ 87*94 ┃ 588, 816 ┃ 32*32 ┃ 87*94 ┃ 1, 046, 784 ───────╂──────╂────╂───────── ┃ 64*64 ┃ 87*94 ┃ 4, 187, 136 精密型字库 ┃ 96*96 ┃ 87*94 ┃ 9M ┃ 128*128 ┃ 87*94 ┃ 16M ┃ 256*256 ┃ 87*94 ┃ 64M ───────┸──────┸────┸───────── 汉字编码和输入输出 57 汉字库的压缩 „ 字根式压缩法 „ 矢量字库 „ 哈夫曼压缩法汉字编码和输入输出 58 哈夫曼压缩法 „ 将汉字的点阵图形看作由多个子点阵构 成 „ 统计组成所有汉字的子点阵的概率 „ 根据子点阵的概率进行哈夫曼编码,从 而得出所有汉字的哈夫曼编码 „ 用这些子点阵的编码作为汉字库汉字编码和输入输出 59 2*2点阵的16种状态 ┎──┒┎──┒┎──┒┎──┒┎──┒┎──┒┎──┒┎──┒ ┃ 。。┃┃ 。。┃┃ 。。┃┃ 。。┃┃ 。.┃┃ 。.┃┃ 。.┃┃ 。.┃ ┃ 。。┃┃ 。.┃┃ .。┃┃ ..┃┃ 。。┃┃ 。.┃┃ .。┃┃ ..┃ ┖──┚┖──┚┖──┚┖──┚┖──┚┖──┚┖──┚┖──┚ P0 P1 P2 P3 P4 P5 P6 P7 ┎──┒┎──┒┎──┒┎──┒┎──┒┎──┒┎──┒┎──┒ ┃ .。┃┃ .。┃┃ .。┃┃ .。┃┃ ..┃┃ ..┃┃ ..┃┃ ..┃ ┃ 。。┃┃ 。.┃┃ .。┃┃ ..┃┃ 。。┃┃ 。.┃┃ .。┃┃ ..┃ ┖──┚┖──┚┖──┚┖──┚┖──┚┖──┚┖──┚┖──┚ P8 P9 P10 P11 P12 P13 P14 P15 汉字编码和输入输出 60 16种状态的统计概率和相应编码 ┎──┰────┰───────┰──┰────┰───────┒ ┃状态┃ 概 率 ┃ 编 码 ┃状态┃ 概 率 ┃ 编 码 ┃ ┠──╂────╂───────╂──╂────╂───────┨ ┃ P0 ┃ 0.438 ┃ 1 ┃ P8 ┃ 0.011 ┃ 011101 ┃ ┃ P1 ┃ 0.050 ┃ 00000 ┃ P9 ┃ 0.024 ┃ 000010 ┃ ┃ P2 ┃ 0.011 ┃ 0111000 ┃ P10┃ 0.148 ┃ 001 ┃ ┃ P3 ┃ 0.041 ┃ 00010 ┃ P11┃ 0.023 ┃ 000011 ┃ ┃ P4 ┃ 0.032 ┃ 01100 ┃ P12┃ 0.025 ┃ 01111 ┃ ┃ P5 ┃ 0.132 ┃ 010 ┃ P13┃ 0.002 ┃ 01110010 ┃ ┃ P6 ┃ 0.032 ┃ 00011 ┃ P14┃ 0.015 ┃ 011010 ┃ ┃ P7 ┃ 0.014 ┃ 011011 ┃ P15┃ 0.001 ┃ 01110011 ┃ ┖──┸────┸───────┸──┸────┸───────┚ 汉字编码和输入输出 61 压缩结果 „ 平均码长 =0.438*1+0.050*5+0.011*7+...+0.001 *8=2.8 „ 压缩前子点阵码长为4 „ 压缩率为30%汉字编码和输入输出 62 字形的变换(放大、缩小、旋转、平滑) □□□□■■ □□□□■■ □□■ □□□□■■ □□□□■■ □■□ => □□■■□□ => □□□■■□ ■□□ □□■■□□ □□■■□□ ■■□□□□ □■■□□□ ■■□□□□ ■■□□□□ (a) (b) (c) 字形放大的失真与平滑 汉字编码和输入输出 63 汉字屏幕显示 ┎───────┒ ┃ 汉 字 库 ┃ ┖───────┚ ↓ ┎────┒ ┎───────┒ ┎────┒ ─→ ┃ 接 口 ┃ ─→ ┃CRT 控制(CRTC)┃ ─→ ┃ C R T ┃ ┖────┚ ┖───────┚ ┖────┚ ↓ ┎───────┒ ┃ 显示缓冲区 ┃ ┖───────┚ 汉字编码和输入输出 64 汉字印字 „ 绝大多数是点阵式印字方式 „ 点阵式印字机主要有针式打印机、喷墨 式印字机、激光印字机等汉字编码和输入输出 65 中文字处理和精密汉字编辑排版系统 „ 中文编排要比西文编排复杂:横排、竖 排、分栏、插图、表格等 „ 字模分辨率:国产(方正)系统30线/毫 米,国外高级出版系统40-80线/毫米 „ 字模数目:中文6763以上,英文大小写 字母加上符号总共不超出100个 „ 字体数目:中文--宋、仿、黑、楷,美 术字体、变形字体、古籍书中多种字体汉字编码和输入输出 66 主要系统 „ 北大方正 „ 四通4S高级中文编排系统 „ WPS—桌面排版系统汉字编码和输入输出 67 方正排版系统 „ 国际上,最早使用书版和报版的整版编 排系统,尤其是报纸的整版编排 „ 缺点在于它的开放性较差和与其它系统 的兼容性不太好(人为原因)--它的照排控 制器、照排机,必须配备由它自己生 产,或委托其它协作单位生产的产品汉字编码和输入输出 68 操作系统的汉化 „ 外挂式中文操作系统(中文外挂平台): CCDOS、UCDOS、天汇、中文之星、RichWin „ 内核汉化的中文操作系统:微软中文DOS、 Windows 3.2及其后续版本 „ 自有知识产权的操作系统:COSIX „ 基于Linux的自主操作系统:Turbo Linux简体 中文版 6.0、蓝点 Linux 2.0 、Tom Linux 1.0 、红旗 Linux 桌面版 2.0谢谢!汉语分词和名实体识别 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月分词和名实体识别 2 主要内容 „ 分词歧义 „ 分词规范 „ 主要分词方法 „ 名实体识别分词和名实体识别 3 分词的提出和定义 „ 汉语文本是基于单字的,汉语的书面表 达方式也是以汉字作为最小单位的,词 与词之间没有显性的界限标志,因此分 词是汉语文本分析处理中首先要解决的 问题 „ 添加合适的显性的词语边界标志使得所 形成的词串反映句子的本意,这个过程 就是通常所说的分词分词和名实体识别 4 分词的意义 „ 正确的机器自动分词是正确的中文信息处理的 基础 „ 文本检索 „ 和服 | 务 | 于三日后裁制完毕,并呈送将军府中。 „ 王府饭店的设施 | 和 | 服务 | 是一流的。 如果不分词或者“和服务”分词有误,都会导致荒谬的检索 结果。 „ 文语转换 „ 他们是来 | 查 | 金泰 | 撞人那件事的。(“查”读音为cha) „ 行侠仗义的 | 查金泰 | 远近闻名。(“查”读音为zha)分词和名实体识别 5 分词面临的主要难题 „ 如何面向大规模开放应用是汉语分词研 究亟待解决的主要问题 „ 如何识别未登录词 „ 如何低廉地获取语言学知识 „ 词语边界歧义处理 „ 实时性应用中的效率问题分词和名实体识别 6 分词歧义 „ 交集型切分歧义 „ 组合型切分歧义分词和名实体识别 7 交集型切分歧义 „ 汉字串AJB被称作交集型切分歧义,如果满 足AJ、JB同时为词(A、J、B分别为汉字串)。 此时汉字串J被称作交集串。 „ [例] “美国会通过对台售武法案” „ [例] “乒乓球拍卖完了” „ [例] “结合成分子” „ 结合 | 成分|子 | „ 结合|成|分子| „ 结 | 合成 |分子|分词和名实体识别 8 组合型切分歧义 „ 汉字串AB被称作组合型切分歧义,如果满足 条件:A、B、AB同时为词 „ [例]组合型切分歧义:“起身” „ 他站 | 起 | 身 | 来。 „ 他明天 | 起身 | 去北京。分词和名实体识别 9 “真歧义”和“伪歧义” „ 真歧义指存在两种或两种以上的可实现 的切分形式,如句子“必须/加强/企业/中 /国有/资产/的/管理/”和“中国/有/能力/ 解决/香港/问题/”中的字段“中国有”是一 种真歧义 „ 伪歧义一般只有一种正确的切分形式, 如“建设/有”、“中国/人民”、“各/地方”、 “本/地区”等分词和名实体识别 10 未登录词 „ 虽然一般的词典都能覆盖大多数的词语,但有 相当一部分的词语不可能穷尽地收入系统词典 中,这些词语称为未登录词或新词 „ 分类: „ 专有名词:中文人名、地名、机构名称、外国译名、 时间词 „ 重叠词:“高高兴兴”、“研究研究” „ 派生词:“一次性用品” „ 与领域相关的术语:“互联网”分词和名实体识别 11 分词规范 „ 词是自然语言的一种客观存在 „ 汉语书写过程中并不分词连写,对词组和词、 单字语素和单字词的划分因人而异,甚至因时 而异 „ 汉语信息处理现在需要制订统一的分词标准, 否则将严重影响计算机的处理 „ 《信息处理用现代汉语分词规范及自动分词方 法》:结合紧密、使用频繁分词和名实体识别 12 具体的分词标准实例 „ 1 二字或三字词,以及结合紧密、使用稳定的: 发展 可爱 红旗 对不起 自行车 青霉素 „ 2 四字成语一律为分词单位:胸有成竹 欣欣 向荣 四字词或结合紧密、使用稳定的四字词组:社会 主义 春夏秋冬 由此可见 „ 3 五字和五字以上的谚语、格言等,分开后如 不违背原有组合的意义,应予切分: 时间/就/是/生命/ 失败/是/成功/之/母分词和名实体识别 13 具体的分词标准实例 „ 4 结合紧密、使用稳定的词组则不予切分:不管 三七二十一 „ 5 惯用语和有转义的词或词组,在转义的语言 环境下,一律为分词单位: 妇女能顶/半边天/ 他真小气,象个/铁公鸡/ „ 6 略语一律为分词单位:科技 奥运会 工农业 „ 7 分词单位加形成儿化音的“儿” :花儿 悄悄儿 玩儿分词和名实体识别 14 具体的分词标准实例 „ 8 阿拉伯数字等,仍保留原有形式:1234 7890 „ 9 现代汉语中其它语言的汉字音译外来 词,不予切分:巧克力 吉普 „ 10 不同的语言环境中的同形异构现象, 按照具体语言环境的语义进行切分: 把/手/抬起来 这个/把手/是木制的分词和名实体识别 15 常见的动词分词规范 „ 1 动词前的否定副词一律单独切分:不/写不/ 能没/研究 未/完成 „ 2 用肯定加否定的形式表示疑问的动词词组一 律切分,不完整的则不予切分:说/没/说看/不 /看相信/不/相信 „ 3 动宾结构的词或结合紧密、使用稳定的:开会 跳舞 解决/吃饭/问题 孩子该/念书/了 „ 4 结合不紧密或有众多与之相同结构词组的动 宾词组一律切分:吃/鱼学/滑冰 写/信分词和名实体识别 16 常见的动词分词规范 „ 5 动宾结构的词或词组如中间插入其它成分, 则应予切分:吃/两/顿/饭跳/新疆/舞 „ 6 动补结构的二字词或结合紧密、使用稳定的 二字动补词组,不予切分:打倒 提高 加长 做 好 „ 7 “2十1,1”或“1十2”结构的动补词组一律切分: 整理/好说/清楚 解释/清楚 打/得/倒提/不/高 „ 8 偏正结构的词,以及结合紧密的词不予切分: 胡闹 瞎说 死记分词和名实体识别 17 常见的动词分词规范 „ 9 复合趋向动词一律为分词单位:出去 进来 当插入“得、不”时应予切分:出/得/去进 /不/来 „ 10 动词与趋向动词结合的词组一律切分: 寄/来跑/出去 „ 11 多字动词无连词并列,一律切分:调查 /研究 宣传/鼓动分词和名实体识别 18 主要的分词方法 „ 简单的模式匹配:正向最大匹配、逆向 最大匹配法、双向匹配法 „ 基于规则的方法:最少分词算法 „ 基于统计的方法:统计语言模型分词、 串频统计和词形匹配相结合的汉语自动 分词、无词典分词分词和名实体识别 19 正向最大匹配分词(Forward Maximum Matching method, FMM) „ 基本思想 „ 基本过程: „ 1.设自动分词词典中最长词条所含汉字个数为I; „ 2.取被处理材料当前字符串序数中的I个字作为匹配字 段,查找分词词典。若词典中有这样的一个I字词,则 匹配成功,匹配字段作为一个词被切分出来,转6; „ 3.如果词典中找不到这样的一个I字词,则匹配失败; „ 4.匹配字段去掉最后一个汉字,I--; „ 5.重复2-4,直至切分成功为止; „ 6.I重新赋初值,转2,直到切分出所有词为止。分词和名实体识别 20 分析 „ “市场/中国/有/企业/才能/发展/” „ 对交叉歧义和组合歧义没有什么好的解 决办法 „ 错误切分率为1/169 „ 往往不单独使用,而是与其它方法配合 使用分词和名实体识别 21 逆向最大匹配分词(Backward Maximum Matching method, BMM法) „ 分词过程与FMM方法相同,不过是从句 子(或文章)末尾开始处理,每次匹配不成 功时去掉的是前面的一个汉字 „ “市场/中/国有/企业/才能/发展/ „ 实验表明:逆向最大匹配法比最大匹配 法更有效,错误切分率为1/245分词和名实体识别 22 双向匹配法(Bi-direction Matching method, BM法) „ 比较FMM法与BMM法的切分结果,从而 决定正确的切分 „ 可以识别出分词中的交叉歧义分词和名实体识别 23 最少分词问题 „ 分词结果中含词数最少 „ 等价于在有向图中搜索最短路径问题 发 展 中 国 家 1 2 3 4 5 6 分词和名实体识别 24 最少匹配算法(Fewest Words Matching,FWM) ) „ 分段 „ 逐段计算最短路径(Dijkstra算法) „ 得到若干分词结果 „ 统计排歧 发展\中\国家 发展\中国\家 „ 算法复杂性与FMM相当分词和名实体识别 25 基于统计的词网格分词 „ 第一步是候选词网格构造:利用词典匹配,列 举输入句子所有可能的切分词语,并以词网格 形式保存 „ 第二步计算词网格中的每一条路径的权值,权 值通过计算图中每一个节点(每一个词)的一 元统计概率和节点之间的二元统计概率的相关 信息 „ 根据图搜索算法在图中找到一条权值最大的路 径,作为最后的分词结果分词和名实体识别 26 字串“中华人民共和国”的切分词网格 字节点 中 华 人 民 共 和 国 词节点 中华 人民 共和国 华人 共和 时 间 分词和名实体识别 27 分析 „ 可利用不同的统计语言模型计算最优路 径 „ 具有比较高的分词正确率 „ 算法时间、空间复杂性较高分词和名实体识别 28 一种基于N-gram信息的生词获取 „ 基本思想:N元对→词频过滤→互信息过 滤→校正→生词获取 „ 词频 „ 互信息(Mutual Information) „ 词频与互信息的关系 „ 候选生词的校正 )()( ),(log);( 21 21 21 wpwp wwpwwI ×=分词和名实体识别 29 一些抽取出的新词(三元组) 字数 抽取出的新词 3 阿拉伯(地名)、艾滋病、白求恩(人名)、独联体(组织名)、洞庭湖(地名)、工商局(机 构名)、摄氏度(计量单位)、世乒赛(缩略名)、塔利班(组织名) 4 标本|兼|治(成语)、求|真|务实、萨|马兰|奇(人名)、神|州|大地、升|旗|仪式、体制|转|轨、政 企分开、通|货|膨胀(术语)、玩|忽|职守、新闻|媒|体、音|像|制品、优胜|劣|汰 5 奥地利|先|令(货币名)、波|黑|穆斯林(地名)、抽样|合格|率(术语)、电视|连续|剧 6 反|法西斯|战争、高|新技术|产业、工商|行政|管理、股份|有限|公司、国民|生产|总值(术语) 7 农村|剩余|劳动力、全国|人大|常委会(机构名)、香港|特别|行政区(地名)、常驻|联合国|代表 分词和名实体识别 30 一些抽取出的新词(二元组) 字数 抽取出的新词 2 芭蕾、搬迁、北约(组织缩略名)、波黑(地名)、车臣(地名)、扶贫、乔石(人名)、印度 (地名)、空调、欧盟(组织缩略名)、环保、媒体、拚搏、研讨 3 菜|篮子、反应|堆、党|组织、房|地产、副|主席(职位名)、国库|券、核|电站、价值|观、乒乓| 球、食用|菌、实验|室、市|政府(机构名)、舒|马赫(人名)、消费|者、许可|证 4 百货|大楼、博士|学位、长篇|小说、犯罪|分子、改革|开放、高速|公路、国有|资产、绿色|食品、 外汇|储备、知识|产权 5 供销|合作社(机构名)、天安门|广场(地名)、珠江|三角洲(地名)、最惠国|待遇、博士生|导 师(职位名)、赤道|几内亚(地名)、钢筋|混凝土、三军|仪仗队、唯物|辩证法 6 辩证|唯物主义、工农业|总产值、国务院|副总理(职位名)、外交部|发言人、义勇军|进行曲、 犹太人|定居点、计划经济|体制、联合国|安理会(机构名)、内蒙古|自治区(地名) 7 劳动人民|文化宫、塞尔维亚|共和国(地名)、无产阶级|革命家、中共中央|政治局(机构名) 分词和名实体识别 31 生词的统计特征--统计构词能力 )( )()( cCount cCountcWFP 的多字词含= ⎪⎩ ⎪⎨ ⎧ > =− = ∏ ∈wc iWFP i wcWFP wcWFP wP )1(|C| ),( )1(|C| ),(1 )( 是多字词 是单字词分词和名实体识别 32 生词的统计特征--汉字构词模式 )( ))(()|)(( 位于多字词cCount cpttnCountccpttnPr = ∏ = = l i iirpttn ccpttnPwP 1 )|)(()(分词和名实体识别 33 生词的统计特征--字对的亲合力 )|)(( 11 ++ = iiBiir cctcctP )|)(( 11 ++ = iiNiir cctcctP分词和名实体识别 34 人名识别 „ 规则方法:利用语言规则来进行人名识别。优点:识 别较准确;缺点:很难列举所有规则,规则之间往往 会顾此失彼,产生冲突,系统庞大、复杂,耗费资源 多但效率却不高 „ 统计方法:一种是仅从字、词本身来考虑,通过计算 字、词作人名用的概率来实现,另一种结合基于统计 的汉语词语边界划分来实现。统计方法占用的资源少、 速度快、效率高,但准确率较低。其合理性、科学性 及所用统计源的可靠性、代表性、合理性难以保证。 搜集合理的有代表性的统计源的工作本身也较难。 „ 混合方法:取长补短分词和名实体识别 35 一种基于统计和规则的人名识别方法 „ 中文姓名用字特点(82年人口普查结果) „ 729个姓氏用字 „ 姓氏分布很不均匀,但相对集中 „ 有些姓氏可用作单字词 „ 名字用字分布较姓氏要平缓、分散 „ 名字用字涉及范围广 „ 某些汉字既可用作姓氏,又可用作名字用字分词和名实体识别 36 人名识别系统资源 „ 语料库:95、96两年的人民日报语料全 集。共约4000万字。 „ 人名库:包含共约31000多个人名。是95、 96两年人民日报语料的所有人名的集合。 „ 人名库和语料库的一致性对保证统计数 据的准确性至关重要。分词和名实体识别 37 人名识别系统知识库 „ 姓氏用字频率库和名字用字频率库:653 个单姓氏,15个复姓,1894个名字用字 的总出现次数 用作姓氏的次数作为姓氏 c ccp =)( 的总出现次数 用作名字用字的次数作为名字用字 c ccp =)(分词和名实体识别 38 人名识别系统知识库 „ 名字常用词表 朝阳 劲松 爱国 建国 立新 黎明 宏伟 朝晖 向阳 海燕 爱民 凤山 雪松 新民 剑峰 建军 红旗 光明分词和名实体识别 39 人名识别系统知识库 „ 称谓库 „ 三种类型 „ 只能用于姓名之前,如:战士、歌星、演员等; „ 只能用于姓名之后,如:阁下、之流等; „ 姓名前后皆可,如:先生、主席、市长等。 „ 称谓前缀表:“副”、“总”、“代”、“代理”、 “助理”、“常务”、“名誉”、“荣誉”等分词和名实体识别 40 人名识别系统知识库 „ 简单上下文 „ 指界词表:约110个词 „ 动词:说、是、指出、认为、表示、参加等; „ 介词:在、之、的、被、以等; „ 正在、今天、本人、先后等。 „ 标点符号集 „ 人名出现在句首或句尾(包括分句)的机会比较大,标点 符号可用来帮助判断人名的边界。 „ 顿号一边是人名时,另一边的候选人名的可靠性高。分词和名实体识别 41 人名识别系统知识库 „ 非名字用词表:有些双字词,如:时间、 奖励、纬度等不作名字用词,但因为组 成它们的单字可作为名字用字,如果跟 在姓氏后面,往往会将其与可作姓氏的 字一起误判为姓名。 例: “做\这\件\事\花\了\我们\一\段\时间\。 \”分词和名实体识别 42 中文人名识别过程 待处理 文本 潜在姓 名表 切分预 处理 校 正 识别 结果 系统资源表 知识库 中文人 名识别分词和名实体识别 43 人名识别的具体实现 „ →姓氏判别 „ →名字识别 „ →概率判断 候选字符串为人名的概率为: P = 姓氏部分为姓氏的概率P1 * 余下部分的汉字作名字用字 的概率P2*P3(单名时,为P2) 分词和名实体识别 44 校正(对潜在人名的后处理) „ 当两个已辨识的人名相似时,需要检查 是否要更正 „ C1C2C3与C1C2C4同时存在,C1C2正确; „ C1C2C3 与 C1C2C4 同时存在,C1C2C3 正 确; „ C1C2C3与C1C2同时存在,C1C2正确; „ C1C2C3与C1C2同时存在,C1C2C3正确分词和名实体识别 45 校正(对潜在人名的后处理) „ 自动校正: „ 如果两个潜在人名相似,考察它们的权值。 „ 一高一低时,将低权值的潜在人名清除(李文常、 李文); „ 都为高权值时,两者都认为是人名(刘文军、刘文 俊); „ 都是低权值时,则各自通过第三个字作名字用字的 概率大小来判断。概率够高,识别为人名。否则将 第三个字去掉(李文常、李文及) 。 „ 人工校正分词和名实体识别 46 人名识别结果与分析 „ 实验结果:8个测试样本,共22000多字,共有 中文人名270个。系统共识别出中文人名330 个,其中267个为真正人名。 召回率=文本中的中文人名辨识正确的比例 =267/270*100% =98.89% 准确率=真正辨识正确的人名的比例 =267/330*100% =80.91% 准确率和召回率是互相制约的,可通过概 率阈值的调整来调节二者的关系。分词和名实体识别 47 人名识别结果与分析 „ 产生错误的主要原因 „ 被未识别的地名干扰。“湖北\英\山\县\詹\家\河\乡\ 陶\家\河\村\,\ ” „ 受非中式人名的干扰。“司\马\义\·\艾\买\提\ ” „ 分词结果不理想。“为\迎接\香港\回\归\送\贺\礼\” „ 规则不准确。“南\宋\大\诗人\杨\万\里\“\惊\如\汉\ 殿\三\千\女\,\ ” „ 其他。“全世界\每年\影片\产量\高\达\两\三\千\部 \,\ ”分词和名实体识别 48 改进措施 „ 采用更好的分词系统 „ 构建更准确的姓名用字库、指界词库等 „ 识别时结合一些语法、语义知识 „ 采用更合理的大规模人名语料进行训练, 使阈值确定得更合理 „ 增加一些校正措施谢谢!统计语言建模 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月统计语言建模 2 主要内容 „ 定义 „ 构造方法 „ 数据稀疏 „ 评价标准 „ 主要统计语言模型 „ 统计语言模型的作用统计语言建模 3 统计语言模型(Statistical Language Model) „ Statistical Language Model „ 统计语言模型试图捕获自然语言的统计规律以 改善各种自然语言应用系统的性能 „ 广泛地应用于语音识别、手写体文字识别、机 器翻译、键盘输入、信息检索等领域 „ 统计语言建模(Statistical Language Modeling) 相当于对各种语言单位如字、词、句子或整篇 文章进行概率分布的估计统计语言建模 4 定义 给定所有可能的句子 s (还可以是其他语言单位),统计 语言模型就是一个概率分布 )(sp 。 迄今为止,几乎所有的语言模型将一个句子的概率分解为 条件概率的乘积: ∏ = == n i iin hwpwwpsp 1 1 )|(),,()( L 这里 iw 是句中的第i 个词, },,{ 121 −= ii wwwh L 称为历史。 统计语言建模 5 例子 ),,,|( ),,|( ),|( )|( )( ),,,,( )( 个一是我学生 一是我个 是我一 我是 我 学生个一是我 我是一个学生 p p p p p p p ⋅ ⋅ ⋅ ⋅= =统计语言建模 6 N-gram模型 实际应用中,由于严重的数据稀疏和系统处理能 力的限制,统计语言建模只能考虑有限长度的历史。 通过将语言模拟成 1−N 阶马尔科夫源,N-gram 模型减少了参数估计的维数: ),,|()|( 11 −+−≈ iNiiii wwwphwp L N 值的选择要考虑参数估计的稳定性和描述能力的 折衷。Trigram 和 Bigram 是通常的选择。 统计语言建模 7 例子(Bigram,Trigram) )|( )|( )|( )|( )( ),,,,( )( 个学生 一个 是一 我是 我 学生个一是我 我是一个学生 p p p p p p p ⋅ ⋅ ⋅ ⋅= = ),|( ),|( ),|( )|( )( ),,,,( )( 个一学生 一是个 是我一 我是 我 学生个一是我 我是一个学生 p p p p p p p ⋅ ⋅ ⋅ ⋅= =统计语言建模 8 基于词类的N-gram模型 设 iC 为词 iw 所属的类,多种基于类的 模型结构可被使用。典型地,一个Trigram 可选择如下计算方法: ),|()|(),|( 21333213 CCCpCwpwwwp ⋅= 统计语言建模 9 类模型提出的意义 „ 降低模型参数的规模 „ 数据稀疏问题的一种解决方式统计语言建模 10 构造方法 „ 采用语言学家构造的词的语法分类体 系,按词性(Part-of-Speech)进行词 类划分,借助于词性标注技术,构造基 于词性的N-POS模型 „ 采用词的自动聚类技术,自动构造基于 词的自动聚类的类N-gram模型统计语言建模 11 几种模型的比较 „ 基于词的N-gram模型对近邻的语言约束关系的 描述能力最强,应用程度最为广泛。一般 N<=3,难以描述长距离的语言约束关系 „ N-POS模型的参数空间最小,一般不存在数据 稀疏问题,可以构造高元模型,用于描述长距 离的语言约束关系。但由于词性数目过少,过 于泛化,因此又限制了语言模型的描述能力 „ 自动聚类生成的词类数量介于词和词性的数量 之间,由此建立的类N-gram模型,既不存在严 重的数据稀疏问题,又不存在过于泛化问题统计语言建模 12 SLM的参数学习 1.有指导的参数学习 是一个基于完全数据的极大似然性估计(Maximum Likelihood Estimation, MLE)。 设 )(xCount 为模型所预测的一个事件 x 在训练语料中出现的次数, )( yCount 为语料中所有入选的相应的条件事件 y 的观察数,则模型所描述的事件 x 的概率可 以由下式估计: )( )()()( yCount xCountxfxp == ,式中, )(xf 为相对频度函数。 2.无指导的参数学习 是一个具有隐含变量的参数训练过程。与有指导的参数学习方法相比,无指 导方法所依赖的训练集可以是不完全数据(incomplete data),因而不需事先进行人 工加工。 统计语言建模 13 参数训练系统 语料 库 分词 语料 参数 估计 语言 模型分词 系统 词表统计语言建模 14 N-gram模型的概率估计 „ 极大似然估计 )( )( )( )()|( 11 1 1 1 11 −+− +− +− +− −+− = = ∑ iNi iNi w iNi iNi iNii wwc wwc wwc wwcwwwp i L L L LL P(朋友|漂亮)=c(漂亮,朋友)/c(漂亮)统计语言建模 15 数据稀疏 由于语言模型的训练文本T 的规模及其分布存在着一定 的局限性和片面性,许多合理的语言搭配现象没有出现在T 中。例如:一个词串 iNi ww L1+− 没有出现在训练文本T 中, 该词串对应的上下文条件概率 )|( 11 −+− iNii wwwp L =0,从而 导致该词串所在的语句 S 的出现概率 0)( =Sp 。 这种情况通常被称作数据稀疏问题(Data Sparseness)或 零概率问题。 统计语言建模 16 N-gram模型的数据稀疏 假设模型训练的词表为V ,采用 N 元模型, 则理论上的参数空间大小为 NV || ,如果 20000|| =V , 3=N ,则 NV || 的值将达到 12108 × ,需要至少上万 G 的空间来存储。而实 际应用中,模型的大小要远远小于这个理想值。统计语言建模 17 N-gram语言模型的一种存储结构 1 2 3 . . . |V| 一元 频率 一元 频率 第二词队 列首地址 第二词队 列首地址 二元 频率 二元 频率 Word ID Word ID 第三词队 列首地址 第三词队 列首地址 一元 频率 第二词队 列首地址 第二词队 列首地址 一元 频率 … … …… Word ID 二元 频率 第三词队 列首地址 …… …… …… …… …… …… 统计语言建模 18 Zipf统计定律 „ 对于大量的低频词(N元对)来说,无论训 练语料库的规模如何扩大,其出现频度 依然很低或根本不出现,无法获得其足 够的统计特性,用于可靠的概率估计。 „ 直接根据频度对N-gram概率进行极大似 然性估计是不可取的统计语言建模 19 数据平滑(Smoothing) „ 平滑:对根据极大似然估计原则得到的概率分 布进一步调整,确保统计语言模型中的每个概 率参数均不为零,同时使概率分布更加趋向合 理、均匀 „ 数据平滑技术 „ 加法平滑 „ Good-Turing估计 „ 回退平滑(Backing-off Smoothing) „ 线性插值(Linear Interpolation) „ 类模型、变长N-gram模型等统计语言建模 20 加法平滑 为了避免零概率问题,将 N-gram 模型中每个 N 元对的出现次数加上一个常数 δ ( 10 ≤< δ ),相 应 的 N-gram 模型参数 )|( 1 1 − +− i niiadd wwp 计算如下: ∑ + += +− +−− +− iw i ni i nii niiadd Vwc wcwwp ||)( )()|( 1 11 1 δ δ 统计语言建模 21 Good-Turing估计 对于 N-gram 模型中出现r 次的 N 元对 i niw 1+− ,根据 Good-Turing 估计公式, 该 N 元对的出现次数为 *r : r r n nrr 1* )1( ++= ,其中, rn 表示 N-gram 的训练集 中实际出现r 次的 N 元对的个数。那么,对于 N-gram 中出现次数为r 的 N 元对 i niw 1+− 的出现概率为: ∑ ∞ = +− = 0 * * 1)( r i niGT r rwp 。 rn 不能为零,本身需要平滑。 Good-Turing 估计公式中缺乏利用低元模型对高元模型进行插值的思想,它通 常不单独使用,而作为其他平滑算法中的一个计算工具。 统计语言建模 22 N-gram模型参数的统计结果 (53.7MB语料,词典59461个词 ) 各级 N-gram 模型的出现次数=r 的 N 元对的个数 rn 出现次数 r 1-gram 2-gram 3-gram 4-gram 5-gram 6-gram 7-gram 1 22490 1342337 3474704 4343780 4411786 4158005 3789897 2 21633 585321 811778 629939 449441 324290 50817 3 20785 367848 377958 229827 131690 79959 25215 4 19971 272266 237503 129336 69213 40707 15460 5 19177 215650 168119 85473 44068 25408 10869 6 18441 179525 129037 62726 31841 18097 8255 7 17762 153201 103248 48466 24230 13790 6605 8 17171 133921 85647 39180 19583 11153 5364 9 16620 118833 72637 32571 16109 9179 4433 10 16147 106975 62718 27638 13664 7732 1230 20 12802 52520 24236 9775 4800 2456 594 30 10957 34059 13840 5487 2771 1269 215 50 8723 19421 6683 2532 1148 496 36 100 6226 8601 2392 796 298 93 1 500 2312 1056 223 65 21 5 0 1000 1314 368 62 18 6 0 0 5000 242 21 2 0 0 0 0 10000 101 4 0 0 0 0 0 20000 42 2 0 0 0 0 0 50000 9 0 0 0 0 0 0 100000 4 0 0 0 0 0 0 200000 3 0 0 0 0 0 0 统计语言建模 23 回退平滑 当一个 N 元对 i niw 1+− 的出现次数 )( 1 i niwc +− 足够大时, )|( 1 1 − +− i niiML wwp 是 i niw 1+− 可靠 的概率估计。而当 )( 1 i niwc +− 不是足够大时,采用 Good-Turing 估计对其平滑,将其部分概 率折扣给未出现的 N 元对。当 )( 1 i niwc +− =0 时,模型回退到低元模型,按着 )|( 1 2 − +− i niikatz wwp 比例来分配被折扣给未出现的 N 元对的概率: )0)(( ))(1( ))(( )|( )|( )|( )|( 1 1 1 1 2 1 1 1 1 1 1 = <≤ ≥ ⎪⎩ ⎪⎨ ⎧ ⋅ ⋅= +− +− +− − +− − +− − +− − +− i ni i ni i ni i niikatz i niiGT i niiML i niikatz wcif kwcif kwcif wwp wwp wwp wwp β α 其中, )|( 1 1 − +− i niiML wwp 为最大似然估计模型。 )|( 1 1 − +− i niiGT wwp 为 Good-Turing 概率估计。 阈值 k 为一个常量。参数 α 和 β 保证模型参数概率的归一化约束条件,即 1)|( 1 1 =∑ − +− iw i niikatz wwp 。 统计语言建模 24 线性插值平滑 利用低元 N-gram 模型对高元 N-gram 模型进行线性插值。 平滑公式: )|()1()|()|( 1 2int 1 1 1 1int 1 1 1 1 − +− − +− − +− ⋅−+⋅= − +− − +− i niierpw i niiMLw i niierp wwpwwpwwp i ni i ni λλ N-gram 模型可以递归地定义为由最大似然估计原则得到的 N-gram 模型 和(N-1)-gram 模型的线性插值。为了结束以上的递归定义:可以令 Unigram 模型为最大似然估计模型,或者令 0-gram 模型为一个均匀分布模型 || 1)( Vwp io =阶 。 插值系数 1 1 − +− i niwλ ,可以采用 Baum-Welch 算法估计出来,也可根据经验 人工给出。 统计语言建模 25 统计语言模型的评价标准 „ 模型评价标准是模型选择或优化时的目标函数 „ 评价一个语言模型的优劣最终要看模型对实际应用系 统性能的影响,但实际中很难采用这种评价标准 „ 得到应用系统的一个可靠的测试需要处理大规模的数据,十 分费时,测试结果易受很多非线性因素的影响 „ 一般不可能找到一个描述系统性能指标和语言模型参数值间 关系的方法。而且不同的测试过程和结论也缺乏横向比较的 标准 „ 语言模型的不确定性可以用信息熵来衡量,模型的不 确定性越大,正确估计语言现象的可能性就越小 „ 一般不直接采用基于应用系统性能评价的标准,而采 用信息熵(entropy)或模型复杂度(perplexity)概念统计语言建模 26 熵(Entropy) „ 消息中所含的信息量的度量 ∑−= i ii ppH log „ 当取以2为底的对数时,熵值为表示若干 个信息所需的最少比特数统计语言建模 27 语言的熵 语言的熵反映语言中每个字或词的平均信息量。对 语言 L ,用 n n xxxx ,,, 211 L= 表示 L 中长为 n 的字串或 词串, )( 1 nxp 是 nx1 的概率。根据信息论原理,若语言 L 是各态遍历的、平稳的随机过程,则熵由下式计算: )(log1)( 1lim n n xpnLH →∝ −= 统计语言建模 28 语言的熵 通常分布 )( 1 nxp 是未知的,熵的计算是对 某种语言模型进行的: ∑ ⋅−= x logp(x)p(x))(LH 统计语言建模 29 交叉熵(Cross Entropy) 通常使用交叉熵来衡量一个模型的质量,以此评估语言模型 Mp 和真实文本(测试文本)分布 Tp 的相似程度: ∑ ⋅−= x MTMT xpxpppH )(log)();(' 对 N-gram 语言模型 p ,模型的交叉熵可由下式计算: ∑ = − +−+−−≈ LL Nn n Nnn xxpNLLpLH )|(log1 1),(' 1 1 其中 LL 表示训练语料的长度。 统计语言建模 30 复杂度(迷惑度,Perplexity) 复杂度是熵的变形。语言模型 MP 的复杂度定义为 );('2)( MT PPH M TPP = 模型的复杂度从信息论角度描述一个语言分支数的几何平 均,即一个语言表示在平均意义上的可能的分析。直观地,利用 一个语言模型预测文本,给定一段历史,当前字或词平均只可能 有 MPP 种选择。复杂度越大,模型的语言约束能力越小。因此, 一个约束能力强的语言学模型一般应具有较低的复杂度。这样语 言模型研究的任务就是寻找复杂度最小的模型。 统计语言建模 31 其他语言模型 „ 各种变长、远距离N-gram模型 „ 决策树模型 „ 链文法模型 „ 最大熵模型 „ 整句模型 „ 动态自适应模型统计语言建模 32 动态自适应模型 1.基于缓存(Cache)的自适应技术 )|()1()|()|( hwphwphwp cachestaticadaptive λλ −+= 2.主题适应的自适应技术 ∏∑ = −+− = = T i iNiik m k kTmix wwwpwwwp 1 11 0 21 )|()( LL λ 统计语言建模 33 统计语言模型的作用 „ 信源-信道模型 : „ I:语言文本;O:声音信号、字符图像信号、 拼音输入等 „ 语言模型: )|()(maxarg)( )|()(maxarg))|((maxargˆ IOpIpOp IOpIpOIpI III === )(Ip i1i2i3…in o1o2o3…on 离散信道模型 统计语言建模 34 统计语言模型的不足之处 „ 统计语言建模技术很少使用真实的语言 知识 „ 跨领域的适应能力差 „ 不能很好地处理长距离语言约束 „ 与西方语言相比,汉语的结构更复杂, 并且存在独特的分词和生词处理问题谢谢!隐马尔可夫模型 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月隐马尔可夫模型 2 主要内容 „ 马尔可夫模型 „ 隐马尔可夫模型 „ 隐马尔可夫模型的三个基本问题 „ 隐马尔可夫模型的基本算法 „ 隐马尔可夫模型的应用隐马尔可夫模型 3 马尔可夫链 一个系统有 N 个状态 NSSS ,,, 21 L ,随着时间推移,系统从 某一状态转移到另一状态,设 tq 为时间t 的状态,系统在时间t 处 于状态 jS 的概率取决于其在时间 1-t,1,2,L 的状态,该概率为: ),Sq,Sq|SP(q k2-ti1-tjt L=== 如果系统在t 时间的状态只与其在时间 1−t 的状态相关,则该 系统构成一个离散的一阶马尔可夫链(马尔可夫过程): )Sq|SP(q),Sq,Sq|SP(q i1-tjtk2-ti1-tjt ====== L隐马尔可夫模型 4 马尔可夫模型(Markov Model) 如果只考虑独立于时间t 的随机过程: ji,i1-tjt a)Sq|SP(q === , Nji,1 ≤≤ 其中状态转移概率 ji,a 必须满足 0a ji, ≥ 且 1a N 1j ji, =∑ = ,则该随机过程称为马尔可夫模型。隐马尔可夫模型 5 马尔可夫模型可视为随机有限状态自动机 „ 该有限状 态自动机 的每一个 状态转换 都有一相 应概率, 表示自动 机采用这 一状态转 换的可能 性隐马尔可夫模型 6 例 假 定一段 时间 内的气 象可由 一三状 态 马 尔 可夫 模型 M 描述: 1S :雨 , 2S :多云, 3S :晴, 转移 概率 矩阵 为: 8.01.01.0 2.06.02.0 3.03.04.0 ][ == ijaA 隐马尔可夫模型 7 例(续) 如果第一天为晴天,根据这一模型,在今后七天中天气为 ""晴晴雨雨晴云晴=O 的概率为: 4 23321311313333 233213 113133333 32311333 10536.1 )2.0)(1.0)(3.0)(4.0)(1.0)(8.0)(8.0( 1 )|()|()|( )|()|()|()|()( )|,,,,,,,( )|( −×= = ⋅⋅⋅⋅⋅⋅⋅= ⋅⋅ ⋅⋅⋅⋅⋅= = aaaaaaa SSPSSPSSP SSPSSPSSPSSPSP MSSSSSSSSP MOP隐马尔可夫模型 8 隐马尔可夫模型 (Hidden Markov Model, HMM) „ 在MM中,每一个状态代表一个可观察的 事件 „ 在HMM中观察到的事件是状态的随机函 数,因此该模型是一双重随机过程,其 中状态转移过程是不可观察(隐蔽)的 (马尔可夫链),而可观察的事件的随机过 程是隐蔽的状态转换过程的随机函数(一 般随机过程)。隐马尔可夫模型 9 实例 一房间有 N 只瓮,每只瓮中有 M 种不同颜色的球。 根据某一概率分布随机地选择一个初始瓮,根据不同颜色 球的概率分布从中随机取出一个球,并报告球的颜色。然 后根据某一概率分布随机地选择另一只瓮,再根据不同颜 色球的概率分布从中随机取出一个球,并报告球的颜 色,⋯。对房间外的观察者,可观察的过程是不同颜色球 的序列,而瓮的序列是不可观察的。 这里每只瓮对应 HMM 模型中的状态,球的颜色对应 于状态的输出符号,从一只瓮转向另一只瓮对应于状态转 换,从一只瓮中取球对应于从一状态输出观察符号。 隐马尔可夫模型 10 实例(续) Observed Ball Sequence Urn 3 Urn 1 Urn 2 Veil隐马尔可夫模型 11 实验中的几个要点 „ 不能直接观察瓮间的转移 „ 从瓮中所选取的球的颜色和瓮并不是一 一对应的 „ 每次选取哪个瓮由一组转移概率决定隐马尔可夫模型 12 HMM的组成 五元组: ),,,,( πλ BAMN= 简记为: ),,( πλ BA= N :状态数目 M :可能的观察值数目 A :与时间无关的状态转移概率矩阵 B :给定状态下,观察值概率分布 π :初始状态空间的概率分布 隐马尔可夫模型 13 状态转移概率矩阵 ijaA = )|( 1 itjtij SqSqPa === − , Nji ≤≤ ,1 0≥ija , 1 1 =∑ = N j ija 隐马尔可夫模型 14 观察值概率分布矩阵 从状态 jS 观察到符号 kv 的概率分布矩阵: )(kbB j= )|()( jtktj SqvOPkb === , Nj ≤≤1 , Mk ≤≤1 0)( ≥kbj , 1)( 1 =∑ = M k j kb 隐马尔可夫模型 15 初始状态概率分布 iππ = )( 1 ii SqP ==π , Ni ≤≤1 0≥iπ , 1 1 =∑ = N i iπ 隐马尔可夫模型 16 观察序列产生步骤 给定模 型 ),,( πλ BA= ,观 察 序 列 TOOOO ,,, 21 L= 可由 以下步 骤产生: 1.根据初始状态概率分布 iππ = 选择一 初始状态 iSq =1 ; 2.设 1=t ; 3.根据状态 iS 的输出概率分布 )(kb j ,输出 kt vO = ; 4.根据状态转移概率分布 ija ,转移 到新状态 jt Sq =+1 ; 5.设 1+= tt ,如果 Tt < ,重复步骤 3、4,否则结束。 隐马尔可夫模型 17 HMM中的三个基本问题 问题 1:给定观察序列 TOOOO ,,, 21 L= ,以及模型 ),,( πλ BA= , 如何计算 )|( λOP ? 问题 2:给 定 观 察 序 列 TOOOO ,,, 21 L= 及模型 ),,( πλ BA= ,如 何选择一个对应的状态序列 TqqqS ,,, 21 L= ,使得 S 能够最为合理地 解释观察序列O ? 问题 3:如何调整模型参数 ),,( πλ BA= ,使得 )|( λOP 最大? 隐马尔可夫模型 18 解决问题1 直接计算: ∑∑ == QQ QOPQPQOPOP ),|()|()|,()|( λλλλ 其中: TOOOO ,,, 21 L= , TqqqQ ,,, 21 L= TT qqqqqqq aaaQP 132211 )|( − = Lπλ )()()(),|( 21 21 Tqqq ObObObQOP TL=λ 困难:穷尽所有可能的状态序列,复杂度 )( TNO ,指数爆炸。 有效方法:向前算法,动态规划,复杂性 )( 2TNO 。 隐马尔可夫模型 19 动态规划(Dynamic Programming) „ 也称为动态时间弯曲(Dynamic Time- Wraping) „ 常用于有序数字的最优求解问题,例如 无向图中两点之间的最短距离问题或者 语料库对齐中基于长度的对齐都采用了 动态规划算法。隐马尔可夫模型 20 HMM的网格结构隐马尔可夫模型 21 向前算法 思想:高效递归地计算向前变量,以求得最终结果 向前变量: )|,()( 21 λα ittt SqOOOPi == L , Tt ≤≤1 算法: 1.出始化: )()( 11 Obi iiπα = , Ni ≤≤1 2.递归: )(])([)( 1 1 1 + = + ∑= tj N i ijtt Obaij αα , 11 −≤≤ Tt , Nj ≤≤1 3.终结: ∑ = = N i T iOP 1 )()|( αλ 隐马尔可夫模型 22 向前变量图示 S 1 ○ S 2 ○ S 3 ○ ○ S j : : S N ○ t t+1 )(itα )(1 jt +α 向前变 量 : )(])([)( 1 1 1 + = + ∑= tj N i ijtt Obaij αα 隐马尔可夫模型 23 向后算法 思想:与向前算法类似,可用于解决问题 1,3 向后变量: )|,()( 21 λβ itTttt SqOOOPi == ++ L , 11 −≤≤ Tt 算法: 1.出始化: 1)( =iTβ , Ni ≤≤1 2.递归: ∑ = ++= N j ttjijt jObai 1 11 )()()( ββ , NiTt ≤≤−≤≤ 1,11 3.终结: ∑ = = N i iOP 1 1 )()|( βλ 隐马尔可夫模型 24 向后变量图示 ○ S1 ○ S2 Si ○ ○ S3 : : ○ SN t t+1 )(itβ )(1 jt+β 向前变 量: ∑ = ++= N j ttjijt jObai 1 11 )()()( ββ 隐马尔可夫模型 25 解决问题2:Viterbi算法 目标:给定一个观察序列和 HMM 模型,如何有效选择“最优”状态序 列,以“最好地解释”观察序列? “最优”→概率最大: ),|(maxarg* λOQPQ Q = 思想:利用动态规划求解,复杂性 )( 2TNO Viterbi 变量: )|,,,,,(max)( 2121,,, 121 λδ titqqqt OOOSqqqPi t LLL == − 递归关系: )(])(max[)( 11 ++ = tiijtjt Obaji δδ 记忆变量: )(itϕ 纪录概率最大路径上当前状态的前一个状态 隐马尔可夫模型 26 Viterbi算法 初始化: )()( 11 Obi iiπδ = , 0)(1 =iϕ , Ni ≤≤1 递归: )(])([max)( 1 1 tjijt Ni t Obaij − ≤≤ = δδ , NjTt ≤≤≤≤ 1,2 )(])([maxarg)( 1 1 tjijt Ni t Obaij − ≤≤ = δϕ , NjTt ≤≤≤≤ 1,2 终结: )])([max 1 * ip TNi δ ≤≤ = , )]([maxarg 1 * iq T Ni T δ ≤≤ = 路径回溯: )( * 11 * ++= ttt qq ϕ , 1,...,2,1 −−= TTt 隐马尔可夫模型 27 解决问题3:HMM参数估计 给定观察序列 TOOOO ,,, 21 L= 作 为训练数据,参数估计的目的是估计模型 λ 中的 iπ , ija , )(kb j ,使 得 观 察 序 列 O 的概率 )|( λOP 最大。 隐马尔可夫模型 28 状态序列已知情况 可以由最大似然估计来估计 HMM 的参数: ),(ˆ 1 ii Sqδπ = ∑ ∑ = = +× == 1-T 1 it 1-T 1 j1tit )S,(q )S,(q)S,(q )( ˆ t t ii ji ij qqQ qqQa δ δδ 的次数本身包括转移到另一状态中从状态 的次数转移到中从状态 ∑ ∑ = = × == T 1 jt T 1 ktjt )S,(q )v,(O)S,(q )(ˆ t t j kj j qQ vqQkb δ δδ 的次数到达 的次数输出中由状态 其中, ⎩ ⎨ ⎧ ≠ == yx yxyx , , 0 1),(δ 隐马尔可夫模型 29 EM(Expectation-Maximization)算法 „ 由于HMM中的状态序列是观察不到的(隐变量),以 上的最大似然估计不可行。EM算法可用于含有隐变量 的统计模型的最大似然估计。 „ EM算法是一个由交替进行的“期望(E过程)”和“极大似 然估计(M过程)”两部分组成的迭代过程: „ 对于给定的不完全数据和当前的参数值,“E过程”从条件期望 中相应地构造完全数据的似然函数值,“M过程”则利用参数的 充分统计量,重新估计概率模型的参数,使得训练数据的对 数似然最大。 „ EM算法的每一次迭代过程必定单调地增加训练数据的 对数似然值,于是迭代过程渐进地收敛于一个局部最 优值。隐马尔可夫模型 30 向前向后算法(Baum-Welch算法) 1.初始化:随机 地给 iπ , ija , )(kb j 赋值(满足概率条 件),得到 模 型 0λ ,设 0=i 。 2.EM 步骤: E 步骤:由 iλ 根据公 式(1)和(2),计算期望值 ),( jitξ 和 )(itγ 。 M 步骤: 用 E 步骤所得的期望值,根据公式 (3)重新估计 iπ , ija , )(kb j ,得到 模型 1+iλ 。 3.循环设计: 1+= ii ;重 复 EM 步骤,直至 iπ , ija , )(kb j 值收敛 。隐马尔可夫模型 31 期望值(1) 给定 HMM 和观察序列,在时间 t 位于状态 i , 时间 1+t 位于状态 j 的概率: ∑∑ == ++ ++ ++ + + = = === === N i N j ttjijt ttjijt ttjijt jtit jtitt jObai jObai OP jObai OP OSqSqP OSqSqPji 11 11 11 11 1 1 )()()( )()()( )|( )()()( )|( )|,,( ),|,(),( βα βα λ βα λ λ λξ 隐马尔可夫模型 32 图示隐马尔可夫模型 33 期望值(2) 给定HMM 和观测序列, 在时间t 位于状态i 的概率: ∑ = = N j tt jii 1 ),()( ξγ 隐马尔可夫模型 34 重估公式(3) )(S 1i1 iqi γπ == 的概率为 ∑ ∑ = === 1-T 1 t 1-T 1 t (i) j)(i, )( t t ii ji ij qqQ qqQa γ ξ 的期望次数本身包括转移到另一状态中从状态 的期望次数转移到中从状态 ∑ ∑ = = × == T 1 T 1 kt (j) )v,(O(j) )( t t t t j kj j qQ vqQkb γ δγ 的期望次数到达 的期望次数输出中由状态 隐马尔可夫模型 35 HMM的应用领域 „ 语音识别 „ 语言处理 „ 机器视觉 „ 人脸检测 „ 机器人足球 „ 图像处理 „ 图像去噪 „ 图像识别 „ 生物医学分析 „ DNA/蛋白质序列分析隐马尔可夫模型 36 在NLP中的应用 „ 词性标注(POS Tagging) „ 基于类的N-gram模型 „ 线性插值HMM语言模型 „ ……谢谢!词法 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月词法 2 主要内容 „ 搭配 „ 语义消歧 „ 词汇获取词法 3 搭配(collocation) „ 定义 „ 研究意义 „ 应用场合 „ 识别方法词法 4 定义 „ 搭配是由两个或两个以上的词所组成的语言表 示 „ Firth:一个特定的词的搭配就是对这个词的惯 用位置的描述 „ 例 „ 名词短语:strong tea, weapons of mass destruction „ 动词短语:to make up „ 固定短语:the rich and powerful词法 5 微妙关系 „ “a stiff breeze” vs. “a stiff wind” (而 “a strong breeze”和“a strong wind”都对) „ “broad daylight” vs. “bright daylight” and “narrow darkness”词法 6 复合构词法(compositionality) „ 自然语言中,如果可以从各组成部分的意思推 测出整体表述的意思,则称这个语言表述是复 合构成的。 „ 搭配不完全是复合构成的:strong tea „ 极端:成语—to kick the bucket „ 大部分搭配显示了比较温和的非复合构词法的 结构: „ international best practice,意思接近每部分的组 合,但通常是指管理效率词法 7 相似概念 „ 术语(term) „ 技术术语(technical term) „ 专有名词短语(terminological phrase) „ 它们通常指在技术领域中抽取到的搭配 (此过程又称术语识别) „ term在信息检索中指词或短语词法 8 搭配研究的意义 „ 传统结构语言学专注于对词组和句子属 性的一般化抽象 „ 上下文理论(Contextual Theory of Meaning)强调上下文的重要性 „ 社会背景上下文 „ 口语和文本篇章的上下文 „ 上下文的环境词,“知其伴,观其意”词法 9 应用 „ 自然语言生成(natural language generation) „ 保证输出自然结果 „ 避免类似to take a decision这样的错误 „ 计算词典编撰学(computational lexicography) „ 自动识别词典条目中重要的搭配 „ 句法分析(parsing) „ 含自然搭配的分析结果可被优先选择 „ 语料库语言学研究(corpus linguistic research) „ 通过语言对某些社会现象进行研究 „ 信息检索(Information Retrieval) „ 用户查询和文档的相似度用搭配来确定,检索准确率会更高词法 10 搭配识别方法 „ 使用频率信息的方法 „ 基于均值和方差的方法 „ 基于互信息的方法词法 11 频率 „ 单纯依赖频率:仅选择最频繁出现的二 元组 „ 启发式规则:词性过滤器—只允许可能 是“短语”的模式通过词法 12 单纯依赖频率的搭配发现词法 13 搭配过滤器的词性标记模式词法 14 加词性过滤器的搭配发现词法 15 模式‘strong w’和‘powerful w’中 最常出现的名词w词法 16 讨论 „ 结果很准确 „ 局限 „ ‘man’和‘force’都可以和以上两个词联合使 用,但未完全统计出来 „ 一些简单的计量技术和一些语言学知识 结合起来非常有效 „ 还可使用停用词过滤等辅助方法词法 17 均值和方差 „ 处理关系灵活的搭配词法 18 将搭配扩展到一定距离的二(N)元组上词法 19 计算两个词之间偏移量的均值和方差 „ 均值是简单的平均偏移量 „ 方差衡量单独的偏移量偏离均值的距离 „ 低的偏差值意味两个词通常会以大致相同的 距离出现 „ 方差是关于一个词相对于其他词分布峰 值情况的量度词法 20 strong相对于opposition的位置词法 21 strong相对于support的位置词法 22 strong相对于for的位置词法 23 基于均值和方差的搭配发现词法 24 讨论 „ 如果均值接近1并且偏差较低,此类短语 也可用基于频率的方法来发现 „ 如果均值远大于1,则一个低偏差预示了 感兴趣的短语 „ 高偏差则预示着词对的两个词之间不存 在感兴趣的联系词法 25 互信息 „ 点互信息(pointwise mutual information):由 于事件[y’]的发生与事件[x’]的发生相关联而提 供的信息量词法 26 搭配发现:按互信息大小排列的 出现20次的10个二元组词法 27 例词法 28 极端情况 „ 完全依赖:出现次数减少时,互信息增加 „ 完全独立词法 29 讨论 „ 互信息是衡量独立性的一种很好的方法 „ 但不是衡量依赖性的一种很好的方法 „ 对于依赖性来说,互信息的值由单独词的频率决定 „ 其他条件相等的情况下,由低频词组成的二元组的 互信息更大 „ 纠正对低频词的偏爱词法 30 语义消歧 „ 定义 „ 预备知识 „ 有监督消歧 „ 基于词典的消歧 „ 无监督消歧词法 31 定义 „ 语义歧义:很多词语具有几个意思或语 义,如果将这样的词从上下文中独立出 来,就会产生语义歧义 „ 语义消歧:确定一个歧义词的哪一种语 义在一个特殊的使用环境中被调用 „ 典型歧义词:具有多种稍微有些联系的 语义,且不清楚是否使用和在哪里使用 这些语义词法 32 例:bank词法 33 例:title词法 34 应用 „ 英德翻译 „ bank的第一个语义→Ufer „ bank 的第二个语义→Bank (financial institution) „ 信息检索 „ 查询:financial bank, „ 返回:使用第二个语义的文档词法 35 与词性标注(消歧)的关系 „ 联系 „ 同一词汇的不同词性的识别可以被看成一个语义消 歧问题 „ 语义识别也可看成是一种标注问题,但要使用语义 标记而不是词性标记 „ 区别 „ 本质区别 „ 处理方法 „ 大部分词性标注模型简单地使用当前上下文(结构信息) „ 语义消歧模型通常使用范围广泛一些的上下文中的实词词法 36 预备知识 „ 有监督和无监督学习 „ 伪词 „ 算法性能的上界和下届词法 37 有监督和无监督学习 „ 有监督学习 „ 训练数据已知(语义标注) „ 分类任务(classification task) „ 函数拟合(function-fitting):基于一些数据点推断出函数的形态 „ 无监督学习 „ 训练数据的分类未知 „ 聚类任务(clustering task) „ 现实情况 „ 从未标注数据中学习 „ 使用多种知识源 „ 建立种子集→从未标注数据中学习→扩大种子集→获取大规 模标注语料词法 38 伪词 „ 在测试数据难以得到的情况下,可方便地产生 一些人工数据,用来比较和提高算法性能,在 语义消歧的情况下,这些人工数据称为伪词 „ 创建伪词 „ 合并两个或多个自然词汇 „ 例:创建伪词banana-door,在语料库中用其代替所有出现 的banana和door „ 意义:既回避了手工标注的困难,又可以为消 歧问题轻松创建大规模的训练和测试数据 „ 带有伪词的文本作为歧义源文本,最初的文本作为 消歧后的文本词法 39 算法性能的上界和下界 „ 算法效能评估:任务的困难程度 „ 上界(upper bound):通常指人工效能 „ 在相同上下文限制的情况下,通过和人工效能相比 较,可以得到系统效能的评测 „ 下界和底线(baseline):可能的最简单算法的效 能-将所有上下文中的语义指定为使用最频繁的 语义 „ 简单的准确度数字并不能真实说明某个词消歧处理 的难度词法 40 有监督消歧 (Supervised Disambiguation) „ 贝叶斯分类:将上下文看作一个无结构词 集,整合上下文中众多的词汇信息 „ 基于信息论的方法:仅仅考虑上下文中 的一个信息特征,其可以灵敏地反映上 下文结构,但需要谨慎地选取此特征词法 41 符号约定词法 42 贝叶斯分类 „ 原理:在一个大的上下文窗口中考虑歧 义词周围的词的信息 „ 每个实词都含有潜在的有用信息 „ 要求语料库中的歧义词都事先被正确地进行 语义标注 „ 贝叶斯决策规则:最小化错误概率词法 43 为w指定语义s’词法 44 朴素贝叶斯分类器 (Naïve Bayes Classifier) „ 将分类所基于的状态空间描述成一系列特征 „ 根据特征词描述上下文 „ 朴素贝叶斯假设 „ 语义消歧中,朴素贝叶斯假设的两个推论 „ 上下文中的所有结构和词语顺序可被忽略:一个可 有重复的单词集模型(bag of words model) „ 每个词互相独立词法 45 修正的分类决策规则 „ 其中词法 46 贝叶斯消歧算法词法 47 贝叶斯消歧算法(续)词法 48 结果 „ 对Hansard语料库中6个歧义名词(duty, drug, land, language, position, sentence) 的消歧正确率可达90% „ Drug的两个语义线索词法 49 一种基于信息论的方法 „ 寻找单一上下文特征,使之可以可靠地指示出 歧义词的哪种语义被使用 „ 三个法语歧义词的信息指示器词法 50 信息的量值规范化: Flip-Flop算法(暂处理两个语义的歧异) ti是歧义词的语义或翻译,xi是指示器可能的取值词法 51 消歧 „ 结果:应用到机器翻译系统中时,系统 性能可提高约20%(100个句子中正确的 句子由37个增加到45个)词法 52 基于词典的消歧 „ 基于语义定义的消歧 „ 基于类义辞典的消歧 „ 在第二语言语料库翻译基础上的消歧 „ 每篇文本一个语义,每个搭配一个语义词法 53 基于语义定义的消歧 „ 词典中词条本身的定义就可以作为判断其语义 的一个很好的依据条件 „ 设cone的两个定义如下 „ a mass of ovule-bearing or pollen-bearing scales of bracts in trees of the pine family or in cycads that are arranged usually on a somewhat elongated axis, „ something that resembles a cone in shape: as…a crisp cone- shaped wafer for holding ice cream „ 如果tree或ice和cone 出现在相同上下文中,可 以说明cone的语义就是那个包含着该词的辞典 定义语义:tree对应语义1,ice对应语义2词法 54 算法词法 55 例:ash的语义词法 56 消歧结果词法 57 结果 „ 准确率50%-70% „ 改进 „ 在文本中迭代几次算法:可以不使用vj定义中出现 的所有词Evj的联合,而仅仅使用上一次算法迭代已 经确定的语义定义 „ 通过类义词典中的同义词列表来扩展上下文中的每 个词词法 58 基于类义词典的消歧 „ 语义范畴(semantic categorization)信息: 由类义词典或类似Longman的带有主题 范畴(subject categories)的词典提供 „ 原理:上下文中词汇的语义范畴大体上 确定了此上下文的语义范畴,且上下文 的语义范畴可以反过来确定词汇的哪一 个语义被使用词法 59 一个简单消歧算法词法 60 结果 „ 准确率50%左右(测试词:interest、 point、power、state、terms) „ 问题 „ 一般的主题范畴并不适合于特殊领域 „ 在类义词典中mouse有两个语义范畴:哺乳动物和电子器 件,但在计算机手册中很少会出现范畴“哺乳动物” „ 一般的主题领域也会有覆盖面的问题 „ 在1960’年代的任何类义词典中均找不到Navratilova这个 词,但它的出现对范畴“sports”是一个很好的指示词法 61 改进算法-增加对语料库的主题分类 „ 将语料库中ti类上下文中频繁出现的词加 到了ti类里 „ 例:Navratilova在sports类文本里的出现次 数要远大于其他类文本,所以可以把它加到 sports类中 „ 提出贝叶斯分类器的变种算法来完成消 歧处理词法 62 算法 „ 在Yarowsky的实验中,一 个上下文就是以歧义词 为中心的100个词的窗口词法 63 算法续词法 64 算法续词法 65 结果:三个歧义词的语义消歧词法 66 分析 „ 语义之间的主题独立性(topic-independent distinctions) „ 当类义词典中的范畴和语义与主题很好地吻合时, 准确率很高 „ 当语义涉及到几个主题时,效果很差 „ 例 „ interest的advantage语义(如self-interest)不是一个 特殊的主题,self-interest可以出现在音乐、娱乐、 空间探索和金融等多种领域 „ 因而基于主题的分类法在这个语义上效果很差词法 67 在第二语言语料库翻译基础上的消歧 „ 使用双语词典中的对应词 „ 需消歧的语言称为第一语言 „ 双语词典中的目标语言称为第二语言词法 68 使用第二语言语料库对interest消歧词法 69 算法词法 70 每篇文本一个语义,每个搭配一个语义 „ Yarowsky提出语义消歧的两个约束 „ 每篇文本一个语义 „ 在任意给定的文本中目标词语义有很强的一致性 „ 每个搭配一个语义 „ 根据和目标词之间的相对距离、次序和句法关 系,相邻词提供了可用于判断目标词语义的很多 线索信息词法 71 每篇文本一个语义 „ 每篇文本一个语义的约束可以抵消信息不足和 误导信息带来的影响词法 72 每个搭配一个语义 „ 基本假设 „ 大部分统计消歧研究都要依赖的条件:语义 和某些上下文特征有很强的联系 „ 根据一个强特征消歧 „ 无需对不同特征进行混合词法 73 算法(混合两种约束) „ Fk包含特征搭配,Ek是歧义词w(当前被指定为 语义sk)的上下文词法 74 算法(续)词法 75 算法(续) „ 结果 „ 准确率:90.6%-96.5% „ 不需要标注训练事例词法 76 无监督算法 „ 特殊领域中缺少我们需要的词汇资源信 息 „ 外部信息源对于消歧的可用性并不大 „ 针对语义标注的完全无监督的语义消歧 是不可能的(需特征描述),但语义辨别 (sense discrimination)可以在完全无监督 的形式下实现词法 77 EM(Expectation-Maximization)算法 „ EM算法是一个由交替进行的“期望(E过程)”和 “极大似然估计(M过程)”两部分组成的迭代过 程: „ 对于给定的不完全数据和当前的参数值,“E过程” 从条件期望中相应地构造完全数据的似然函数值, “M过程”则利用参数的充分统计量,重新估计概率 模型的参数,使得训练数据的对数似然最大。 „ EM算法的每一次迭代过程必定单调地增加训练 数据的对数似然值,于是迭代过程渐进地收敛 于一个局部最优值。词法 78 分组上下文判别(context-group discrimination)-EM算法词法 79 算法(续)词法 80 算法(续)词法 81 语义数目的确定 „ 通过在一定的语义数目K内运行算法,可以选择歧义词 语义分类的粒度: „ 如果似然对数值增加幅度明显,则这个新的语义数目是可取 的 „ 确定语义数目的简单方法 „ 在语义数目和可用训练数据的规模之间建立依赖关系 „ 无监督消歧的一大优点 „ 适合区分有细微差别的语义用法,这些细微差别在词典中找 不到 „ 如:bank的语义在bank robberies的上下文中是银行实体,在 corporate mergers的上下文中是抽象团体,二者之间区别很 小,甚至在词典中没有反映出来词法 82 结果:10个带有不同EM算法初始 条件实验的平均准确率和标准差词法 83 词汇获取(Lexical Acquisition) „ 一般性目的:通过考察大型文本语料库中词汇 的出现模式,设计一种算法和统计技术来填补 现有电子词典的不足 „ 一个重要任务是在传统词典中增加数量信息 „ 词典信息和非词典信息之间没有明显的界限 „ 一种认识:所有关于语言的知识都可以在词典 (lexicon)中体现出来,因此无需把语法作为一个独立 的实体 „ 通常,在单个词的级别上可以简单概念化的属性都 能包含在词汇获取中词法 84 内容 „ 评价方法 „ 动词子范畴 „ 附着歧义 „ 选择倾向 „ 语义相似性词法 85 语义相似性 „ 词汇获取的最高目标是词义的获取:但怎样表 述词义并为自动系统所用尚未解决 „ 如何计算语义相似性是现实的任务 „ 定义 „ 某种程度上,语义相似性是近义词的扩展 „ 通常指来自于相同语义领域和主题的两个词 „ 语义相似的判断可以通过上下文可换性的程度来解 释 „ 所有的语义相似概念都含有歧义问题:应用到歧义 词时,语义相似通常意味着和一个适合的语义相似词法 86 应用 „ 文本一般化 „ Susan had never eaten a fresh durian before „ 可以把durian的语义相似性建立在语义最近似的词 汇上(mango),也可建立在几种最近似语义词汇的 组合上 „ 信息检索中用来处理查询扩展(query expansion) „ K近邻法(K nearest neighbors)分类:根据k个近 邻为一个新的元素(词汇)指定一个最可能的类 别(新闻报道中的主题范畴:financial、 agriculture、politics)词法 87 语义相似性度量方法 „ 向量空间度量方法 „ 概率度量方法词法 88 向量空间度量方法 „ 映射为向量相似性的度量 „ 几个多维空间的例子 „ 计算行间相似性或列间相似性词法 89 文本-词汇矩阵词法 90 词汇-词汇矩阵词法 91 中心词-修饰词矩阵词法 92 二元向量的相似性度量方法词法 93 实值向量空间的余弦度量法 „ 给定两个n维向量,其余弦值: „ 如果向量有单位长度,称该向量是归一化的: „ 对归一化向量,余弦值可简化为:词法 94 一些结果(纽约时报语料) „ 对应左栏的每一个词,右栏为与其最相似的词 „ 数字为余弦相似度词法 95 余弦度量法分析 „ 缺点:同现信息不能反映词序和语法依 存关系,所以这种方法不能反映语法差 别(fallen和fell) „ 优点:简洁直观,计算简单词法 96 概率度量方法 „ 向量空间法的问题 „ 多数基于二值数据 „ 余弦法须度量欧式距离,不适合处理概率和 计数向量 „ 可转化为条件概率矩阵,使语义相似性 问题转换为两个概率分布相似性(或不相 似性)问题词法 97 由91页表计算得到的条件概率词法 98 概率分布不相似性的度量方法词法 99 概率方法分析 „ 优点:理论上更加严谨 „ 缺点:需要将非相似性转化为相似性才 能用来一般化文本词法 100 词汇获取的下一步工作 „ 努力寻求更多先验知识 „ Wordnet、Hownet中的信息 „ 语言学理论 „ 百科全书、类义词典、地名词表、技术词表、 等等谢谢!语法 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月语法 2 主要内容 „ 词性标注 „ 概率上下文无关文法 „ 概率句法分析 „ 浅层句法分析 „ 语料库及其多级加工语法 3 词性标注 „ 简介 „ 词性分类体系 „ 标注中的信息源 „ 主要标注方法语法 4 简介 „ 任务:为句子中的每个词标上一个合适的词性 „ 标注是一种有限语法消歧问题 „ 目前最高准确率:96%-98% „ 应用 „ 信息抽取 „ 问题回答 „ 浅层句法分析 „ 名词短语识别语法 5 词性分类体系 „ 依据 „ 形态标准 „ 意义标准 „ 分布标准--根据词在句法结构里所担当的语法功能分类,适合 汉语的分类 „ 确定原则 „ 标准性:尽量采纳当前已经成为或正在成为词性标准的分类 体系和标记符号 „ 兼容性:尽量使标注集的表示与已经存在的标注集可以相互 进行转化 „ 扩展性:对未解决的遗留问题或是未来可能的技术发展方向 充分加以考虑,以便加以扩充和修改语法 6 语言学界的分类 „ 名词、时间词、处所词、方位词、动词、 形容词、状态词、区别词、数词、量词、 代词、介词、副词、连词、助词、语气 词、象声词、叹词、前缀、后缀、成语、 简称、习用语等语法 7 北京大学的汉语词性标注集 词性标记 词性 词性标记 词性 词性标记 词性 n 名词 z 状态词 h 前接成分 t 时间词 b 区别词 k 后接成分 s 处所词 d 副词 g 语素 f 方位词 p 介词 x 非语素字 m 数词 c 连词 i 成语 q 量词 u 助词 l 习用语 r 代词 y 语气词 j 简称略语 v 动词 o 拟声词 w 标点符号 a 形容词 e 叹词 语法 8 英语标注中常用的一些词性语法 9 标注中的信息源 „ 邻近上下文中的其他词的标注 „ 很多词性序列很常见 „ 某些词性序列基本不可能 „ 词本身提供的信息 „ Dumb标注器:简单地把最常用的标注分配给 每个词,达90%准确率-基准性能 „ 现代标注器都结合使用了结构语段信息 和词汇信息语法 10 主要方法 „ 马尔可夫模型标注器 „ 隐马尔可夫模型标注器 „ 基于转换的标注语法 11 马尔可夫模型标注器 „ 将文本中的标记序列看成一条马尔可夫链语法 12 符号标记语法 13 问题求解语法 14 表达式简化 „ 两个假设 „ 词语之间独立 „ 词语的出现只依赖于它本身的标注语法 15 确定一个句子的最优标注语法 16 模型训练算法语法 17 Brown语料库中一些标记转移的计数语法 18 Brown语料库中一些词和标记共现的计数语法 19 标注算法(Viterbi算法)语法 20 与隐马尔可夫模型区别 „ 训练时构造了“显”马尔可夫模型 „ 标注时当作了隐马尔可夫模型语法 21 其他问题 „ 未登录词 „ 三元语法标注器 „ 插值和可变记忆 „ 平滑语法 22 隐马尔可夫标注器 „ HMM标注过程与VMM相同 „ 差别在于怎样训练模型 „ HMM的初始化是关键所在语法 23 HMM的初始化 „ 随机地初始化HMM的所有参数:使得标 注难以约束 „ 使用词典信息限制模型参数:如果对应 的词语-标记对未在词典中列出,则将词 语生成概率设为0 „ 将词语聚集到词语等价类中,使得所有 同一类的词语允许同样的标注语法 24 基于转换的标注学习 „ 利用更大范围的词汇和语法结构规则 „ 标注器需要的决策量比估计大量的马尔 可夫模型参数要少一个数量级语法 25 主要思想 „ 给定一个标注好的语料库和词典 „ 用最常用的标记标注训练语料中的每个 词 „ 构建一个转换的序列表,它将初始标注 转化为接近正确的标注 „ 使用转换序列表标注新的文本: „ 初始化新的文本,用最常用的标记来标注 „ 应用转换语法 26 基于转换的标注器中的触发环境语法 27 学习到的一些转换例子语法 28 触发条件 „ 词语触发 „ 标记触发 „ 联合触发 „ 形态触发:处理未登录词语法 29 基于转换的标注学习算法语法 30 分析 „ 准确率:95%-96% „ 能将标注决策建立在更丰富的事件集合 上 „ 转换比概率标注中的转移和词语生成更 容易修改 „ 基于转换的学习也被应用于句法分析、 介词短语附着、语义消歧上语法 31 其他标注方法 „ 神经元网络 „ 决策树 „ K近邻方法 „ 最大熵模型语法 32 标注准确率 „ 影响标注性能的因素 „ 可以获得的训练数据量:通常越多越好 „ 标记集:标记集越大,潜在歧义越多,标注 越困难 „ 训练语料库及词典与应用语料库的差别 „ 未登录词语法 33 概率标注器中常见的错误例子语法 34 词性标注混乱矩阵的一部分语法 35 概率上下文无关文法 „ 定义 „ 句子概率的计算 „ PCFG的特点 „ PCFG的三个基本问题语法 36 概率上下文无关文法简介 „ Probabilistic (Stochastic) Context Free Grammars, PCFG „ 对于树结构来说是最简单、最自然的概 率模型 „ 其算法是HMM所使用算法的一个自然发 展语法 37 概率上下文无关文法G的定义语法 38 一个句子的概率由下式给出语法 39 例 „ 句子:astronomers saw stars with ears „ 给定语法:语法 40 分析树1语法 41 分析树2语法 42 句子的概率语法 43 模型假设 „ 位置不变性:一棵子树的概率并不依赖于词串 中他所支配的词语所处的位置 „ 上下文无关性:子树与不被子树支配的词无关 „ 祖先无关性:子树的概率与子树之外的祖先节 点无关语法 44 证明:树的概率为所用规则概率的乘积语法 45 PCFG的特点 „ 给出了一个计算不同分析的合理度的思 路 „ 鲁棒性:赋予不合适的句子低概率 „ 给出了一个概率语言模型 „ 其预测能力比具有相同参数的有限状态 语法强 „ 偏置问题:其他条件相同的情况下,一 棵小树的概率比一棵大树大语法 46 PCFG的三个基本问题语法 47 解决方法 „ 词串概率计算:内部算法(inside algorithm),外部算法(outside algorithm) „ 确定最佳分析结果:内部算法,动态规 划-Viterbi风格算法 „ PCFG参数训练:EM算法-内部-外部算法语法 48 概率句法分析 „ 目的和作用 „ 举例 „ 树库 „ 词汇化 „ 依存语法 „ 句法分析器语法 49 目的和作用 „ 句法分析的目的 „ 使用句法结构进行语义解释 „ 识别短语语块,为信息检索系统的索引服务 „ 构建一个概率句法分析器作为优于n元语法的语言 模型 „ 概率句法分析的作用 „ 利用概率来确定句子 „ 利用概率来加速语法分析 „ 利用概率来选择句法分析结果(消歧)语法 50 确定正确的分析树 „ The post office will hold out discounts and service concessions as incentives语法 51 分析树a语法 52 分析树b语法 53 分析树c语法 54 分析树d语法 55 分析树e语法 56 树库(treebank) „ 分析树的集合 „ 用于构建统计句法分析器语法 57 Penn树库的一个例子语法 58 Penn树库中短语类别及缩写语法 59 词汇化语法 60 扩展VP所用规则强依赖于动词本身特性语法 61 依存语法 „ 不管是哪个学派的语法学说,都不得不正视句 子中词与词之间的句法、语义联系 „ 反映动词对名词性成分的支配能力的概念,是 哪一种语法理论也回避不了的 „ 依存语法表述词与词之间一种最基本的联系 „ 在一般应用的时候,都是以动词作为一个句子 的中心,支配其他的成分。所有受支配成分都 以某种依存关系从属于支配成分语法 62 句子的依存语法表示 她 是 我 小的 伙伴 语法 63 依存关系的四大公理 „ 一个句子中只有一个成分是独立的,不受任何 成分支配 „ 其他成分直接依存于另外的某一个成分 „ 任何一个成分都不能直接依存于两个或两个以 上的其他成分 „ 如果A成分直接依存于B成分,而C成分在句中 位于A成分和B成分之间的话,那么,C或者直 接依存于A,或者直接依存于B,或者直接依存 于A和B之间的某一成分语法 64 依存语法的主要特点 „ 表示方法简洁,易懂 „ 依存语法生成的句法树不含非终结符,一个具 有N个词的句子,生成的依存句法树只有N个结 点和(N-1)条边。而利用短语结构语法得到的句 法树由于含有非终结符,结点数大大超过N,大 大超过(N-1)条边 „ 注重词与词的语义的依存关系,而不是在句中出 现的顺序关系语法 65 短语结构表示的句法树 她是我 小的 伙伴 NP NP DE V S 语法 66 构造句法分析器-搜索算法 „ 栈解码算法 „ A*搜索语法 67 浅层句法分析(shallow parsing) „ 亦称部分句法分析(partial parsing) 或语块分析(chunk parsing) „ 近年来自然语言处理领域出现的一种新的语言处理策略 „ 不要求得到完全的句法分析树,只要求识别其中的某些结 构相对简单的成分,如非递归的名词短语、动词短语等 „ 识别出来的结构通常被称作语块(chunk),和短语概念通常 可以换用 „ 浅层句法分析将句法分析分解为两个子任务:(1)语块的 识别和分析;(2)语块之间的依附关系(attachment)分析 „ 使句法分析的任务简化,同时也利于句法分析技术在大规 模真实文本处理系统中迅速应用语法 68 语料库及其多级加工 „ 语料库语言学 „ 语料库介绍 „ 语料库多级加工 „ 语料库的应用语法 69 语料库语言学(Corpus Linguistics) „ 语料库语言学:以语料库为基本知识源来研究自 然语言规律的学科,其中语料库加工的理论、 方法和工具与基于语料库的知识获取是语料库 语言学研究的主要内容 „ 语料库(Corpus) :按照一定的原则组织在一起 的真实的自然语言数据(包括书面语和口语)的 集合,主要用于研究自然语言的规律,特别是 统计语言学模型的训练以及相关系统的评价和 测试。语法 70 国外的语料库 „ 布朗语料库(Brown Corpus,BC, W.N. Francis and H. Kucera, Brown University) :1961年诞 生 „ LOB(London-Oslo-Bergen Corpus, LOB)语料库 „ Penn树库 „ 语料库建设已从单一的研究行为转向有计划的 工程行为,如美国的ACI/DCI计划,欧共体的 ECI计划等,并向更大规模、更深的加工层次 发展语法 71 汉语语料库 „ 1990’s年代国内开始建立 „ 清华大学5000万汉字的原始语料库 „ 台湾中央研究院的200万词次的带有词性标注 的汉语平衡语料库 „ 国内外主要组织: „ 台湾中央研究院的中文信息处理组 „ 马里兰大学CLIP实验室的汉森林(Chinese Forest) „ 美国宾夕法尼亚大学XTAG计划语法 72 语料库的多级加工 „ 语料库标注或加工就是对电子语料(包括书面语和口 语)进行不同层次的语言学分析,并添加相应的“显性” 的解释性的语言学信息过程 „ 没有任何标注的叫做原始语料库,也叫做生语料库 „ 经过加工的语料叫做熟语料 „ 加工层次越高,所能获取的语言学知识越丰富,但加 工难度越大 „ 与不同层次的自然语言分析相对应,语料库的加工主 要包括词性标注、句法标注、语义标注、言语标注和 语用标注等,汉语的语料加工还包括分词语法 73 英语和汉语语料库标注情况对比 语言层 英语标注情况 汉语标注情况 词性(Part of speech) 基本实用化 迅速发展 句法(syntactic) 迅速发展 大多在发展 语义(semantic) 存在一些,大多在发展 起步 言语(discourse) 很少,起步 无 语用(pragmatic) 很少,起步 无 语法 74 语料库加工的三种主要方式 „ 人工:非常昂贵,需要大量的人力资源 „ 自动:自动加工不完全准确 „ 人机结合的半自动方式:兼顾两者的优点 „ 一种方式是先由计算机对待加工的语料进行自动加 工,然后由人工校对 „ 另一种则是由计算机自动选择语料库中需要人干预 的自动加工不能解决的部分,从而减少人的工作语法 75 歧义消解与语料库加工的关系 „ 一方面,高性能的歧义消解技术是实现语料库 加工自动化的关键。某种意义上讲,语料库的 多级加工实际是一个面向真实文本的自然语言 多级歧义消解过程 „ 另一方面,语料库特别是经过加工的语料库又 为歧义消解提供了资源支持。语料库加工的层 次越高,所能提供的语言学信息越丰富,越有 利于歧义消解水平的提高语法 76 图示 汉语语料库多级加工与标注 词性 标注 歧义消解 词语 边界 歧义 词 性 兼 类 结 构 歧 义 语 义 歧 义 照 应 歧 义 深 层 歧 义 词语边 界划分 句法 标注 语义 标注 言语 标注 深层 标注 生语料 熟语料 信息库 知识获取语法 77 语料库的应用 „ 经过标注和预处理的语料库可以为所有的基于 统计的自然语言理解提供统计的数据资源,是 基于统计的自然语言处理技术的基础 „ 语料库自动加工技术,如分词、词性标注、句 法分析等自动加工技术是具体应用的基础.对 于信息检索来说,分词是必不可少的;对于机 器翻译来说,必须加工到句法分析层次谢谢!音字转换技术 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月音字转换技术 2 主要内容 „ 语音输入 „ 汉字智能键盘输入 „ 音字转换的主要方法音字转换技术 3 音字转换 „ 音字转换技术就是利用计算机这个工具 采用人工智能、统计学、语言学等方法 充分利用各种语言单位的上下文关系处 理汉语语音音节串或拼音串到对应汉字 串的自动转换。 „ 应用 „ 汉语语音输入 „ 拼音键盘输入音字转换技术 4 汉语语音输入 „ 语音识别阶段:把自然的声音信号转换 为机器可以处理的数字表达的音节形式 (或拼音形式) „ 语音理解阶段或音字转换阶段:把音节 转换为汉字形式音字转换技术 5 语音识别 „ 语音识别单位 „ 单音节(字识别) „ 多音节(词识别) „ 单音节语音识别多被采用 „ 汉语是单音节语言,口语中,词与词之间很少有清晰的停 顿,主要是单音节之间有间隔,单音节输入较易为人们接受 „ 汉语中音节只有400个,音调节也只有1200个,词是由音节组 合成,只要音节可以正确输入,则这些音节能构成无限的词 组和语句。况且语音输入训练时只训练单音节是比较容易 的,而在大词汇量(如几万个)情况下训练词的输入是难以 让用户接受的 „ 单音节输入比多音节输入变化范围小,对系统资源的要求较 低音字转换技术 6 语音理解阶段 „ 字处理:把语音识别器给出的和输入音节相近的几个 音所包含的近音字在计算机屏幕上显示出来,让用户 选择所需的汉字 „ 词处理:通过用户读入音节停顿时间的不同确定词的 长短,再和系统词库进行近音匹配,把近音词在屏幕 上显示出来让用户选择。字词停顿难以控制 „ 语句级处理:明显优于字词输入形式 „ 从操作心理学上看,操作人员倾向于按有一定意义的短语或 句子为单位进行短时记忆 „ 从信息论角度讲,汉字的多维熵要少于一维熵,语句输入法 比字词输入法需要较少的输入信息音字转换技术 7 声音语句输入分阶段处理 声音语句 多个音节候选 汉字语句 语音识别 语音理解音字转换技术 8 对“今天是星期五” 语音识别给出的音节候选向量 Y 0 1 2 3 4 5 6 X jin 033 jing 035 jian 039 ji 089 qin 289 xin 453 xun 562 qun 787 jun 886 jian 076 tian 076 gan 087 qing 433 jin 556 qin 559 ting 876 xin 890 jun 987 shi 121 chun 135 shun 190 chi 344 sen 456 shen 490 ci 580 zi 590 ping 621 xing 324 qing 354 xin 566 qin 677 xong 698 shen 790 seng 834 xun 932 shuan 998 qi 022 ji 056 xi 056 xie 078 xin 145 xing 180 qie 230 xian 286 zhi 341 wu 201 hu 222 fu 342 gu 389 mu 450 pu 489 wo 564 zhu 621 gong 840 音字转换技术 9 音字候选三维向量 Y 金 间 是 星 七 五 今 渐 事 兴 期 武 仅 件 时 姓 奇 午 3 斤 简 视 行 欺 侮 惊 天 春 轻 鸡 虎 精 田 唇 清 急 乎 迳 殄 蠢 情 几 扈 2 京 添 纯 请 技 唬 Z 间 干 顺 新 西 妇 渐 竿 瞬 信 晰 服 谏 绀 舜 昕 息 伏 1 件 甘 吮 心 媳 付 0 1 2 3 4 5 6 X 音字转换技术 10 语音理解 „ 模拟人们听写行为的思维过程,运用多 种知识排除歧义性,在音字候选向量中 找到一条沿X轴方向从1到N的最佳路径作 为输出音字转换技术 11 声音语句输入的系统实现 语音信号 N N 汉字输出 Y Y 语音识别 近音词自动切分 查找知识库,给出同音 字、词的候选集以及相 关规则集,据词法、语 法、语义知识进行推理 路径大于一条? 概率推理 句子输出正确? 拼音内码转为汉字内码 语音库 词典 句法知识 语义知识 语用知识 知识库 机器 学习 音字转换技术 12 汉字智能拼音键盘输入 „ 基于字形的输入法:重码率低,难以掌 握,适合专职打字员 „ 基于拼音的输入法:易学,字词输入法重 码率高,输入速度慢 „ 智能输入:通常基于拼音,机器自动处 理重码选择,易学,快速,输入过程更 符合人的思维规律,适合广大非专职打 字员音字转换技术 13 拼音输入的多种表达形式 „ 拼音助学和提示输入:声母提示、拼音 提示 „ 拼音的压缩表达(简拼、双拼、三拼、 声母输入) „ 用户自定义简拼 „ 模糊拼音输入 „ 逐渐提示输入 „ 面向数字键盘的数字拼音输入音字转换技术 14 拼音输入预处理-拼音流的切分 „ 手工切分 „ 自动切分 „ 自动切分,人工干预 „ 统计语言模型 „ 切分规则(实用、有效)音字转换技术 15 拼音输入预处理-拼音纠错 „ 引起错误的原因 „ 与人们日常使用语言文字的习惯有关 „ 不同地域的人的发音存在着一定的差异 „ 用户真正关心的是转换后汉字的正确,一般情况下并不对输入拼音 的正确与否进行检查 „ 对键盘的熟练程度 „ 拼写自动修改方法 „ 通过对用户输入过程中所犯各种错误的分析,建立一种有效可行的 打字模型,通过收集用户真实输入的数据,统计得到用户打字模型 的参数 „ 同时基于大量的中文文本,训练得到一个强大的中文语言模型,并 与中文的打字模型相结合,采用类似语音识别的技术,修改用户输 入中的各种错误,并得到最合适的汉字 „ 拼写纠正不仅可以进行用户自适应,而且还适用于各种语言音字转换技术 16 音字转换(键盘输入)的实现方法 „ 基于理解的方法 „ 基于语用统计的方法 „ 基于模板匹配的方法音字转换技术 17 基于理解的方法 „ 利用汉语语法知识来消化同音字、词,以及化 解歧义分词 „ 学科分类中属于人工智能的自然语言理解分支 „ 根据自动分词得到同音字、词的候选集,查找 知识库得到相关的规则,再经过归约推理,得 出转换结果 „ 特点:优点-系统正确率比较稳定。缺点-语言 覆盖面较小,当输入语句的语法不规范时,不 能有效处理;建立知识库时知识表达和知识获 取均非常困难音字转换技术 18 基于语用统计的方法 „ 主要利用语用统计的数据来消化同音字、词,以及化 解歧义分词 „ 通过汉语字与字或词与词之间的同现概率来完成汉语 语用统计库的构造 „ 根据拼音输入构造词网格 „ 通过概率计算求得词网格中的最佳路径 „ 为减少状态空间的搜索时间,必须采用有效的搜索方 法,比如采用动态规划的Viterbi算法或各种A*算法 „ 特点:转换率较高,是主流方法,对不同领域文本具 有偏向性 „ 基于理解和基于语用统计相结合的方法:实现两种方 法的取长补短音字转换技术 19 N-gram模型实现音字转换 的系统结构图 拼音流 汉字流 机器学习 词网格 生成 系统词 典 N-gram 模型 统计库 最优路 径搜索音字转换技术 20 词网格示意图 观测序列 o0 o1 o2 o3 o4 候 选 词 w11 w21 w31 w41 w51 w12 w22 w42 w52 w32 w43 w53 音字转换技术 21 Viterbi最优路径搜索 Viterbi 算法可以在给定的 Markov 模型 MA=< >π, 的情况下,从词网格中求出一在该模 型下最可能的状态序列qqq qT ∗ ,...,= 12 。定义 δ t i()为时刻 t 时,从起始结点到当前时刻第 i 个 候选 w i 的最佳路径的权值。 音字转换技术 22 Viterbi算法 1·初始化 δπ1 ()i i= , φ 1 0()i = , 1 1≤≤iN 2·递归 δδt iN tijjmax ia t () ()=⋅ ≤≤ − −1 1 1 φδt iN tijjargmax ia t () ()=⋅ ≤≤ − −1 1 1 2 ≤≤tT, 1 ≤≤jNt 3·终结 pmaxi iN T T ∗ ()= ≤≤1 δ qargmaxiT iN T T ∗ ()= ≤≤1 δ 4·状态序列求解 qqttt ∗∗()= ++φ 11, tT T=− −121, ,..., 其中 N t 为结束于时刻 t 的候选词的个数。 音字转换技术 23 基于模板匹配的方法 „ 寓汉语语法知识于巨量的短语串中,进而利用这些短 语串来消化同音字、词,以及化解歧义分词。这种短 语串通常称之为“模板词”。 „ 根据分词后的输入语句查找模板词库和句法规则库, 然后进行匹配处理。如果匹配结果唯一,则不必再用 概率推理;若存在两个以上的候选结果时,则根据句 法规则或概率推理进一步判定,选出一个最有希望的 可能结果作为输出。 „ 特点:对于已经搜索过模板词的或者具有相同类型的 领域,系统的转换正确率比较高。但由于模板词数量 巨大,对计算机存储空间要求较高。谢谢!机器翻译 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月机器翻译 2 主要内容 „ 机器翻译简介 „ 统计对齐 „ 统计机器翻译机器翻译 3 机器翻译(Machine Translation) „ 自动将文本或谈话内容从一种语言翻译 为另一种语言,为NLP最重要的应用领域 之一机器翻译 4 《红楼梦》片断翻译 „ 源文:黛玉自在床上感念宝钗……,又听见窗 外竹梢焦叶之上,雨声淅沥,清寒透幕,不觉 又滴下泪来。 „ 译文:As she lay there alone, Dai-yu’s thoughts turned to Bao-chai ……,Then she listened to the insistent rustle of the rain on the bamboos and plantains outside her window. The coldness penetrated the curtains of her bed. Almost without noticing it she had begun to cry.机器翻译 5 文学翻译涉及哪些问题? „ 中文人名的翻译 „ 主要人名音译 „ 其他人意译:Aroma(袭人),Skybright(晴雯) „ 中文没有动词时态和语态变化 „ 透→penetrated „ 幕→curtains of her bed „ 其他 „ 竹梢焦叶→bamboos and plantains机器翻译 6 MT的难度和要求 „ 高质量的翻译问题难以实现:对源语言和输入 文本具有博大精深的理解,能够老练地、富有 诗意地、创造性地支配目标语言 „ 当前的计算模型可以胜任一些较简单的任务 „ 粗略翻译就足够的任务 „ 互联网中的“信息采集” „ 人工编辑后可用于提高MT输出的任务 „ 机助翻译 „ 能够产生高质量译文的受限子语言领域的任务 „ 天气预报、航空旅行查询、约会安排、设备维护手册机器翻译 7 MT的不同策略机器翻译 8 直接翻译法:词-词对齐翻译 „ 从源语言的表层句子出发,将词或固定 词组直接置换成目标语言的对应成分 „ 问题:对MT过程的认识过于简单 „ 不同语言之间可能不存在一一对应的映射关 系 „ 词的歧义 „ 语言中的次序机器翻译 9 句法转换法 „ 解决了词序问题,一定程度上确保了翻 译结果的句法准确性 „ 问题:句法的正确性不等于语义的正确 性 „ 德文短句“Ich esse gern(I like to eat)”直译到 英语结果为“I eat readily”,英语中没有类似的 “动词-副词”结构能表达“I like to eat”的概 念,所以句法转换不能解决翻译中的所有问 题机器翻译 10 语义转换法 „ 将原文转化为语义表示形式,在此基础 上生成译文 „ 能解决句法结构不匹配问题 „ 问题:即使字面意思翻译完全准确,但 最后译文对用户来说可能还是不易理解 的机器翻译 11 中间语言法 „ 中间语言:独立于任何语言的知识表达形式 „ 优点:进行多语种翻译时,只需对每种语言分 别开发一个分析模块和一个生成模块 „ 缺点: „ 中间语言设计难度大:每种语言转化为中间语言都 存在歧义 „ 语言本身的完备性构建也很困难机器翻译 12 MT的主要方法 „ 基于统计的方法(本章主要讨论内容) „ 统计与规则相结合的方法 „ 基于实例的方法机器翻译 13 统计对齐 „ 文本对齐 „ 词对齐机器翻译 14 文本对齐 „ 统计机器翻译的基础 „ 相同的文字内容存在不同的语言版本 „ 平行语料库(parallel corpus) „ 官方文件:某些国家或地区具有多种官方语言(加拿 大、瑞士、香港) „ 数量大 „ 准确性高 „ 文学作品、宗教书籍 „ 文本对齐:确定原文和译文句子或段落间的对 应关系机器翻译 15 句子和段落对齐 „ 应用 „ 建立双语字典 „ 机器翻译 „ 多语言语料库的使用 „ 语义消歧 „ 多语言信息检索 „ 对象:语言风格迥异、意译法等造成的 不对齐现象(下页例子)机器翻译 16 对齐文本: 中间和右 边两列分 别是法文 和英文句 子,箭头 标明了他 们之间的 对应关 系,左边 斜体字部 分是从法 文直译得 到的英文 翻译机器翻译 17 句子对齐 „ 定义:从句子内容出发,将源语言中的一组句 子和目标语言中的一组句子对应的过程 „ 每组句子可以为空,也可人为加入对应源语言 中不存在的句子,或删除原有的句子 „ 两组对应的句子为一个句珠(bead) „ 对齐方式:1:1(90%)、1:n、n:1、m:n „ 每个句子能且只能出现在一个句珠中 „ 处理交叉依赖(cross dependency)问题机器翻译 18 基于长度的对齐 „ 基本原理:假设源语言和目标语言的句 子长度存在比例关系 „ 句子长度:定义为句子中单词或字符的 个数 „ 特点:简单、忽略很多其他可利用信 息;效果好、效率高机器翻译 19 统计对齐的目标 „ 求概率最大的对齐 „ 将对齐文本分解为句珠序列,各句珠之 间独立分布 „ 在句珠内的句子已知的情况下,估算某 一类句珠的概率值机器翻译 20 一种基于长度的对齐算法 源语言: ),,,( 21 IsssS L= ,目标语言: ),,,( 21 JtttT L= 对齐方式: A ,句珠序列: ),,,( 21 KBBB L ji, 代表两组句子 isss ,,, 21 L 和 jttt ,,, 21 L 最小耗费函数: ),( jiD = 句子长度: 1l 、 2l ,两组句子的距离量度: δ 两组句子之间的耗费计算函数:cost() 机器翻译 21 实例: 利用句子长度评估两组句子的对齐程度 „ 句子长度用其字符数表示 „ 前提:段落对齐 „ 假设只存在以下几类句珠模式: {1:1,1:0,0:1,2:1,1:2,2:2} „ 利用动态规划寻找双语文本之间的“最短 距离” „ 利用递归法反复计算最小耗费函数,找 到其中的具备最小耗费的D(I,J)机器翻译 22 最小耗费函数计算机器翻译 23 计算对齐耗费的例子机器翻译 24 确定每类对齐的耗费 耗费的计算基于句珠中每一种语言句子的 长度 1l 和 2l ,同时把一种语言中的每个字符相对 于另一种语言对应出现的字符数作为随机变量, 假设其服从正态分布,且满足独立同分布。从实 际语料中估计这些参数,以均值 µ 为例,其值 大概为 1,其方差 2s 用长度差值的平方近似。机器翻译 25 耗费计算函数 „ 一个句珠内两组句子的距离度量 „ 耗费计算函数 其中 alignα 代表某种可能的对齐模式,取负使得出的概率值和 距离成反比;上式可通过贝叶斯公式计算,即 )|()( alignPalignP αδα , )( alignP α 相当于对齐模式的先验概率。机器翻译 26 实验结果 „ 此算法尽可能地在长度相近的句子之间 建立了对齐关系 „ 在UBS (Union Bank of Switzerland)语料 库上进行实验 „ 一般错误率4% „ 改进后达到0.7% „ 在“1:1”对齐模型上性能最好机器翻译 27 其他方法 „ 基于信号处理技术的偏移位置对齐算法 „ 在平行文本中利用位置偏移量的概念 „ 源文本中一定位置的文本和目标语言中一定位置的 文本是大致对齐的 „ 可有效地处理噪声文本 „ 句子对齐的词汇方法 „ 使用词语级别的部分对齐来推导出句子级别的对齐 的最大似然估计方法,同时能反过来优化词语对齐 „ 假设:如果两个词语的分布相同,则它们是对应的 „ 不需要更高级别的段落对齐机器翻译 28 词对齐 „ 利用词对出现的频率 „ 利用关联度量的方法 „ EM算法 „ 更多地利用先验知识机器翻译 29 统计机器翻译 „ 噪声信道模型(法文→英文翻译)机器翻译 30 三个部分 „ 语言模型 „ 翻译模型 „ 解码器 „ 任务:参数值估计机器翻译 31 语言模型(Language Model) „ 语言模型给出了英文句子的生成概率P(e) „ 假定事先已经有一个定义良好的语言模 型(n元语法模型,概率句法分析模型等)机器翻译 32 翻译模型(Translation Model) „ 一个简单的基于词对齐的翻译模型 其中:e 代表英文句子,l 是按词计算的句子长度; f 是法文句子, m 是其长度; jf 是 f 的第 j 个词, ja 是 e 中与 jf 对齐的词的位置; jae 是 e 中与 jf 对齐的词; )|( ef wwP 是翻译概率,即在已知 ew 在英文句 子里的条件下, fw 出现在对应法文句子里的概率, Z 是归一化常数。机器翻译 33 基本思想 „ 它累加了法语单词对齐英语单词所有情况的概 率,aj 等于0表示法语句子中的第j个单词在英 文中没有对齐成分 „ 每个英文单词可以对应于多个法语单词,但每 个法语单词至多仅和一个英文单词对应 „ 各个单词的翻译之间是无关的 „ 句子对齐后,对所有m个对齐概率求乘积作为 对齐模式的概率机器翻译 34 例 „ 计算下面两句子的对齐概率 „ 只需将三个单独的概率值相乘机器翻译 35 解码器(Decoder) „ 启发式搜索算法 „ 栈搜索法:渐进地构建英文句子,算法过程中 随时保持一个局部的翻译,每次在这个局部翻 译的基础上增加少数单词和对齐模式。如果当 前扩展正确的可能性很小,可以通过剪裁栈返 回以前的状态。 „ 特点:效率高,但不能保证找到全局的最优翻 译机器翻译 36 翻译概率(Translation Probabilities) „ 用EM算法估计翻译模型的参数(假设句子 已对齐) „ 基本思路:解决信任度分配问题。如果 某个词和目标语言中的某个特定词对齐 的可能性很大,则完全可以绑定它们, 从而避免“1:2”或“1:3”的对齐模式及过多 的没有对齐的词机器翻译 37 简化算法 1. 随机设定 )|( ef wwP 的初始值 2. E 步骤:设 ew 已知,计算 fw 在法语句子中出现次数的期望值: ∑ ∈∈ = fwewtsfe efww fe ef wwPz ,..),( , )|( (简单起见,假设一个词在句子中仅出现一次) 3. M 步骤:重新估计翻译模型参数: ∑ v wv ww ef e ef z z wwP , ,)|( 机器翻译 38 实验结果 „ 解码器导致的错误 „ 语法结构解码错误机器翻译 39 噪声信道模型面临的问题 „ “富余度”的不对称性 „ 富余度:一种语言中一个单词对应另一种语 言中单词的数目 „ 独立性假设 „ 对训练数据的敏感性 „ 算法效率机器翻译 40 另外一些问题 „ 没有引入短语概念 „ 非局部依存 „ 词态变化。模型中具备词态变化的词被 区分为不同的词,需单独学习 „ 数据稀疏问题机器翻译 41 讨论 „ 问题根源所在:很少考虑自然语言领域 本身的知识 „ 统计翻译模型研究的未来重点:如何将 语言中内在的语言规律性知识融入到模 型中 „ 其他非语言学模型在词对齐方面被证明 也是有效的谢谢!信息检索技术 刘秉权 哈工大智能技术与自然语言处理研究室 2006年11月信息检索技术 2 主要内容 „ 信息检索综述 „ 信息检索的统计模型 „ 信息检索中的自然语言处理方法 „ 文本自动分类技术信息检索技术 3 信息检索(Information Retrieval) „ 信息检索,是指将信息按一定的方式组织和储存起 来,并根据用户的查询字串,从表示信息的非结构化 数据,特别是非结构化的文本数据中找到与查询字串 相关信息的过程 „ 1952提出IR的概念 „ 分类 „ 光盘数据库检索 „ 网络数据库检索 „ 互联网信息检索 „ 随着国际互联网技术的普及和发展,信息检索技术与 网络通讯技术和语言处理技术彼此融合,成为空前活 跃的研究热点之一。信息检索技术 4 信息检索的定义与术语 „ 信息检索是指从非结构化的数据记录,特别是 包含自由格式的自然语言文本的数据记录中获 取与用户的信息需求相关的数据记录的系统、 方法与过程 „ 文档(Document):在当前信息检索的研究 中,非结构化的数据记录通常特指自然语言文 本数据记录,又称文档 „ 数据全集(Collection):将大量非结构化的数 据记录,按照一定的方式组织和存储起来而构 成的数据记录的集合信息检索技术 5 信息检索的定义与术语 „ 信息检索过程:根据用户特定的信息需求 (Information Need),在数据全集中获取所有或仅有 的与用户信息需求相关的文档,并将这些文档按照相 关性(Relevance)的大小由大到小地排列(Rank) „ 查询(Query):是反映用户信息需求的字符串,这个 字符串可以是关键字序列,一个布尔表达式,或者直 接用自然语言表达的问句 „ 相关性:信息检索结果符合用户信息需求的程度。它 不仅与查询和数据全集有关,而且与信息检索结果的 正确性、现实性和权威性有关,甚至与用户个人的主 观判断有关信息检索技术 6 信息检索系统的系统结构 文档数据库 相关度排序 后的文档 用户接口 文档 查询 倒排文件 用户反 馈 用户需 求 用户查询处理 搜索 相关度排序 建立索引 索引 检索到 的文档 用户查询文本 操作 文档文本操作 数据库管理语义词 典 信息检索技术 7 信息检索系统 „ 八个基本处理模块:用户接口模块,用户查询 文本操作,文档文本操作,用户查询处理模 块,建立索引模块,数据库管理模块,搜索模 块,相关度排序模块 „ 两大部分: „ 检索子系统 „ 信息存储管理子系统 „ 两大系统资源: „ 语义词典(Thesaurus):系统词汇及其语法语义信息,还包 括停用词表(Stoplist)和词形转换表等,整个系统公用 „ 网络数据库信息检索技术 8 模块描述 „ 用户接口模块:与信息检索系统的用户交互信 息--接受用户的查询,根据用户对信息检索结 果的反馈调整信息检索系统的有关参数,显示 用户查询的结果等。 „ 用户查询文本操作模块:对用户的查询字串进 行过滤停用词(Stop Word)、词干抽取 (Stemming)等处理,并转换为机器内部的用 户查询表示格式 „ 停用词:因不具有确切语义而未列入索引词表的高频词 „ 词干抽取:将一个词的各种不同的词形变化替换为称为该词 的词干(Stem)的统一形式的过程信息检索技术 9 模块描述 „ 用户查询处理模块:将用户查询进行同义词扩 充或者根据用户对信息检索的倾向性对查询进 行转换处理 „ 文档文本操作:对文档数据库中的文档进行过 滤停用词、词干抽取等处理,并转换为机器内 部的文档表示格式供建立索引模块处理 „ 建立索引模块:建立从词汇到该词汇出现的文 档(编号)的倒排索引表(Inverted Index),从而对用户查询中的词汇进行快速 定位信息检索技术 10 模块描述 „ 数据库管理模块:将文档以数据库的格式存储、 管理、编辑和访问,通常采用基于SQL的开放 式大型关系数据库管理系统,如Oracle, Sybase „ 搜索模块:根据用户查询,借助于倒排索引表 和数据库管理模块从数据库中抽取出包含用户 查询中关键字的文档 „ 相关度排序模块:逐一计算用户查询与搜索模 块返回文档的相关度,最后将这些文档按照相 关度由大到小的顺序排序信息检索技术 11 信息检索系统的评价 „ 精确率:检索获取的与用户查询相关的数据记 录个数与检索获得的所有数据记录个数的比 值;或者给定一个检索获取的数据记录,它与 用户查询相关的概率。反映了系统能够返回与 用户查询高度相关的数据记录的能力 „ 召回率:检索获取的与用户查询相关的数据记 录的个数与数据全集中所有与用户查询相关的 数据记录的个数的比值;或者一个相关数据记 录能被检索系统获取的概率。反映了系统能够 找到全部相关数据记录的能力信息检索技术 12 二者的关系 A R A∩R 数据全集 任意给定用户查询 q ,A 为信 息检索系统获取的数据记录 的集合,R 为数据全集中所有 与用户查询相关的数据记录 的集合 A RAprecision ∩= R RArecall ∩= 信息检索技术 13 精确率-召回率曲线 (Precision-Recall Curve) 0 0.2 0.4 0.6 0.8 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Recall Precision A 系统 B系统信息检索技术 14 例: 设有一查询q ,在数据全集中所有与该查询相关的文档为 },,,,,,,,,{ 123897156443925953 ddddddddddR = ,信息检索结果按相关度由大到小是(□标志与q 相关的文档): 1、 123d □ 6、 39d □ 11、 9d 2、 84d 7、 48d 12、 511d 3、 56d □ 8、 250d 13、 129d 4、 6d 9、 133d 14、 187d 5、 8d 10、 3d □ 15、 25d □ 可见,当召回率为 10%时,精确度为 100%;当召回率为 20%时,精确度为 67%(2/3); 当召回率为 30%时,精确度为 50%。 信息检索技术 15 E(Effectiveness)量度 RP E 1)1()1( 11 αα −+ −≈信息检索技术 16 F量度 RP RP2F + ⋅⋅=信息检索技术 17 信息检索简史(1) „ 起源于人们为方便查询和访问文献资料而将它们重新整理与分类的手工 劳动 „ 现代信息检索技术产生于1950’s年代 „ 1950年,美国学者Calvin N. Mooers首创“信息检索”这一术语 „ 1958年,美国学者Luhn提出了统计信息检索的基本理论和方法 „ 1960年,Marson和Kuhns提出了信息检索的概率模型 „ 1965年,美国康奈尔大学的Gerard Salton教授及其学生,创立了信息检索向量空间模型 „ 1966年,在Cranfield项目中,信息检索系统的评价方法被首次提出 „ 1968年,Rocchio和Salton共同提出了查询扩展的方法 „ 1972年,Lockheed公司推出了DIALOG系统,成为世界首例商用在线信息查询服务系统。 „ 这一阶段的卓越工作为信息检索技术奠定了坚实的理论基础 „ 1980’s年代,信息检索技术的发展进入了一个相对沉寂的时期。典型的 理论成果包括模糊集、模糊推理、线性回归技术、通用向量空间模型等信息检索技术 18 信息检索简史(2) „ 1990’s年代国际互联网技术的诞生和随之而来的网络信息的爆炸式增 长,使信息检索技术进入了一个崭新的发展时期 ,代表性的理论成果包括 潜在语义索引技术,贝叶斯网络和神经网技术等,基于国际互联网的大型 搜索引擎大量涌现,如Google,infoseek,Lycos等 „ 当前趋势: „ 深度上,进一步提高信息自动管理和自动加工的能力,如探索自动抽词、自 动索引、自动检索、自动文摘、自动分类、自动翻译等 „ 广度方面,正由文本信息检索向全文文本、多媒体、跨语言等新型信息检索 发展 „ 信息存储技术正在向着信息资源的网络化和分布化方向发展 „ 信息检索技术研究领域中,基于概念、超文本信息和多媒体信息检索技术的 研究最为活跃,并已取得了突破性发展 „ 专业化、个性化检索 „ 国际互联网技术的发展给信息检索技术提供了空前广阔的舞台信息检索技术 19 主要信息检索技术 „ 基于统计的方法:主要根据用户查询与 数据全集中的数据的统计量度计算相关 性--占主流的地位 „ 基于语义的方法:对用户查询和数据全 集中的数据进行一定程度的语法语义分 析,在对用户查询和数据全集内容理解 的基础上进行两者的相关性计算信息检索技术 20 信息检索模型 一个信息检索模型 IRM 是一个三元组 ),,( RQDIRM = ,其中: D 是文档的集合; Q 是用户需求的集合; →× QDR : R,是 集 合 D 与 Q 的笛卡尔乘积到实数集 R 的一个映射, 对每个用户查询 Qq ∈ ,每个文档 Dd ∈ ,映射 R 将 ),( qd 映射为一个实 数,称为用户查询 q 与文档 d 的相关度。 因此,一个信息检索模型必须确定文档的表示,用户查询的表示以及用 户查询与文档之间相关度计算的方法。 信息检索技术 21 信息检索的统计模型 „ 布尔模型 „ 扩展布尔模型 „ 向量空间模型 „ 概率模型信息检索技术 22 统计模型的基本表示方法 „ 文档被表示为关键词(Keyword)的集合,这 一表示方式又称为文档的平面结构(Flat Structure) „ 关键词又称为索引词(Index Term),是指除 停用词之外的代表文档内容的词汇,大多数是 名词 „ 词汇的权重(Weight):一个词汇在表示文档 内容时所起到的作用的大小,即重要性信息检索技术 23 统计模型的基本表示方法 令 N 表示整个信息检索系统中关键词的总数,令 ik 表示一 个关键词;令 jd 表示一个文档;对每个 ),( ji dk ,令 0, ≥jiw 表 示关键词 ik 在表示文档 jd 时的权重,若 0, =jiw ,表示关键词 ik 不在文档 jd 中出现,则文档 jd 可以由一个 N 维向量表示为 ),...,,( ,,2,1 jNjjj wwwd = 。 信息检索技术 24 统计模型的基本表示方法 „ 统计信息检索模型通常假设出现在文档 中的词汇彼此独立,它还假设词汇在文 档中的出现没有二义性 „ 西文的信息检索系统都包含一个词干抽 取的模块对词形进行归一化处理,中文 系统没有这一模块 „ 中文系统存在分词问题,影响系统的精 度信息检索技术 25 布尔模型 文档中索引词的权重只有0和1两种取值,分别表示文档中包含和不 包含该索引词。用户查询是由标准逻辑操作符AND,OR,NOT将索引 词连接起来构成布尔表达式。 用户查询与文档的相关度计算的方法是:对用户查询中的每个索引 词 ik ,构造一个文档集合 iDk ,使得该集合内的每一个文档都包含索引 词 ik : }1|{ , == jiji wdDk ,将用户查询中布尔表达式中的操作符 AND, OR,NOT 替换为集合运算符∩ 、 ∪ 、¬ ,于是用户查询中的布尔表达 式转换为集合之间的操作。 信息检索的返回结果是一个集合,在集合中的文档是相关文档,否 则是无关文档。 信息检索技术 26 例: 设关键词为 821 ,...,, kkk ,数据全集中的文档为 621 ,...,, DDD ,其中: },,,,{ 543211 kkkkkD = ; },,,{ 43212 kkkkD = ; },,,{ 86423 kkkkD = ; },,,{ 75314 kkkkD = ; },,,,{ 876545 kkkkkD = ; },,,{ 43216 kkkkD = 。 用户查询为 1k AND( 2k OR NOT( 3k ))。 那么,查询结果为 }),{},,,({},,,{ 5363216421 DDDDDDDDDD ∪∩ },,{ 621 DDD= 。 信息检索技术 27 特点 „ 优点:机制简单,检索的效率很高,在 早期的商用系统中得到了普遍的应用 „ 缺点:分类能力有限,仅能够将文档划 分为相关和不相关两大类,而不能给出 相关性大小的数值,经常会出现高度相 关的文档排序靠后的现象信息检索技术 28 向量空间模型 令 N 表示系统中关键词的总数,文档为由索引词的权重构成的 N 维向 量: ),...,,( ,,2,1 jNjjj wwwd = , jiw , 为索引词i 在文档 jd 中的权重,如果为0, 表示该词在 jd 中不出现。用户查询也表示为由用户查询中的索引词的权重构 成的 N 维向量: ),...,,( ,,2,1 qNqq wwwq = , qiw , 为用户给定的索引词i 的权重。 用户查询与文档的相关度计算的方法是:对于用户查询q 和数据全集中 的每个文档 jd ,计算相似度 ),( jdqSimilarity , Similarity 值越高,表示用户 查询与文档的相关度越大。 选择相似度大于某特定阈值的所有文档或者具有较高相似度的前n 个文 档作为检索结果输出。 信息检索技术 29 向量空间模型的两个关键问题 „ 索引词权重的计算 „ 用户查询与文档的相似度计算信息检索技术 30 索引词权重的计算 “ 词频与倒文档频度”( Term frequency* inverse document frequency, 简写为 tf*idf): ijiji idftfw ⋅= ,, 词频: jiji freqtf ,, = , jifreq , 表示索引词 ik 在文档 jd 中的频度,反 映了一个词在特定文档中的局部统计特征 倒文档频度: )log( i i n nidf = , n 为数据全集中文档的总数, in 为包 含索引词i 的文档的总数,反映了包含该索引词的文档区别于其它文档的 程度,是一个索引词在整个数据全集中的重要性的全局性统计特征。 不足之处:没有考虑文档中索引词的总数 信息检索技术 31 相似度计算 ),( qdsimilarity 取值通常需满足如下条件: 非负性: 0),( ≥qdsimilarity ; 对称性: ),(),( dqsimilarityqdsimilarity ≡ ; 若 0),( =qdsimilarity ,则表示文档d 与用户查询q 完全不相关; ),( qdsimilarity 值越大,表示文档d 与用户查询 q 相关性越大; ),( qdsimilarity 的取值范围通常经正规化处理为区间 ]1,0[ 上的一个值; 1),( =qdsimilarity ,当且仅当文档 d 与用户查询 q 完全相同 信息检索技术 32 相似度计算 两个 N 维向量的内积: ∑ = ⋅= N i jiqi wwdqsimilarity 1 ,,),( 余弦相似度(Cosine Similarity): ∑∑ ∑ == = ⋅ ⋅ = N i qi N i ji N i qiji j ww ww qdsimilarity 1 2 , 1 2 , 1 ,, )()( ),( 余弦相似度的取值范围在[0,1]区间,满足相似度函数取值需满足的条件, 是最为常用的相似度计算方法。主要缺点:对于一个用户查询,包含索引词个 数较多的长文档往往计算结果偏低 信息检索技术 33 概率模型 概率模型通常采用索引词在文档中的统计分布等参 量计算任意文档d 与给定用户查询q 相关的概率 )|( dqP 。 本小节重点介绍一类典型的信息检索概率模型:贝叶 斯推理网络模型,该推理网络模型提供了将不同来源的证 据结合起来以确定给定文档满足用户查询或者信息需求 的概率的一种自然的方法 信息检索技术 34 贝叶斯网络 贝叶斯网络是一个描述随机变量之间因果关系的有向 无环图:节点表示随机变量,一条从父节点Y 到子节点 X 的 边表示两个随机变量的依赖关系,任一节点 X 都附加了一 系列条件概率 ),...,|( 1 nYYXP 表示该节点与其父节点 nYY ,...,1 的依赖关系的强度,在贝叶斯网络中,一个节点仅 条件依赖于它的父节点。 信息检索技术 35 信息检索中的贝叶斯网络模型 dj … k1 k2 kN q 信息检索技术 36 概率计算 ∑∑ =⋅= NN kk Nj kk NNjj kkdqPkkPkkdqPdqP ... 1 ... 11 11 ),...,,,(),...,(),...|),((),( ∑ ⋅= Nkk NjNj kkdPkkdqP ... 11 1 ),...,,()),...,(|( ∑ ⋅⋅= Nkk jjNN dPdkkPkkqP ... 11 1 )()|,...,(),...,|( 由索引词的独立假设: ∏∏ == −⋅= 0|1| 1 ))|(1()|()|,...,( ii ki ji ki jijN dkPdkPdkkP 于是: ∑∏∏ == −⋅⋅⋅= Niikkki ji ki jiNj j dkPdkPkkqPdP dqP ... 0|1| 1 1 ))|(1()|(),...,|()( ),( 信息检索技术 37 问题转化为以下概率值的计算 )( jdP :文档的概率 )|( ji dkP :索引词 ik 与文档 jd 相关的概率 ),...,|( 1 NkkqP :索引词 Nkk ,...1 与用户查询相关的概率 信息检索技术 38 文档的概率 1、均匀分布法 ndP j 1)( = 其中, n 为数据全集中文档的总数。 2、正规化法 j j d dP 1)( = 其中, jd 为文档向量 jd 的长度。 信息检索技术 39 索引词与文档相关概率 1、二值法 ⎩ ⎨ ⎧= 0 1)|( ji dkP 2、权重法 }{max)|( , , jkk ji ji freq freqdkP = 如果索引词 ik 在文档 jd 中出现 否则 信息检索技术 40 索引词与用户查询相关的概率 1、二值法 ⎩ ⎨ ⎧= 0 1),...,|( 1 NkkqP 2、权重法 ⎩ ⎨ ⎧= 0),...,|( 1 的函数某个基于idfkkqP N 如果索引词 Nkk ,...,1 在且仅在查询q 中出现 否则信息检索技术 41 信息检索中的自然语言处理方法 „ 信息检索中的自然语言处理方法,是指通过对 文档中的自然语言文本进行语法语义分析,以 提高信息检索的精确度或者召回率的方法的统 称 „ 通常只能停留在“浅层”(Shallow)处理的层次 上,例如,对文档中的名词短语进行自动识别 和分类等 „ 与统计方法并没有明显的界限,可以将自然语 言处理方法视为基于统计的信息检索技术的有 益补充信息检索技术 42 信息检索涉及的自然语言处理层次 „ 词形分析:词干抽取 „ 词法分析:停用词表中词汇的选择等 „ 专有名词的自动识别与分类 „ 文档文本的自动词性标注 „ 语义分析--语义相似度计算信息检索技术 43 语义相似度(Semantic Similarity) „ 同一语义可以有多种不同的表达方式,而不同用户使 用相同的词汇进行查询的可能性很小->“语义相关” „ 计算词汇间的语义相似度,据此对用户的查询词汇进 行语义相似词汇的扩展或改进用户查询与文档相似度 的计算方法 „ 汉语缺乏语法形态,语义知识更加重要。确定汉语词 汇的语义,不仅在于标明一个词的语义属性,更需要 确定该词汇与其他词汇的关系,“关系是词汇语义的灵 魂”-董振东 „ 语义相似度:将词汇间的种种不同的直接或间接语义 关系映射为一个表示词汇间语义相关的紧密程度的数 值信息检索技术 44 知网中的概念(词汇)语义网络 „ 上下位关系、部分-整体关系、同义关系、反义 关系、对义关系等 信息检索技术 45 基于语义辞典的 语义相似度计算方法 „ 基于按照概念间结构层次关系组织的语 义辞典的方法 „ 两个词汇具有一定的语义相关性当且仅 当它们在概念间的结构层次网络图中存 在一条通路(假设) „ 主要是根据在这类语言学资源中概念之 间的上下位关系和同义关系来计算信息检索技术 46 语义词典 „ 基于语义辞典的方法通常依赖于比较完备的按 照概念间结构层次关系组织的大型语义词典 „ 汉语语义词典研究 „ 董振东、董强等开发的《关系语义知识库(KBRS)》 „ 清华大学黄昌宁等1988年进行的语义词典研究 „ “905”项目《信息处理用汉语语义词典》 „ 汉语语义分类体系的研究 „ 梅家驹《同义词词林》 „ 林杏光《简明汉语义类词典》 „ 陈群秀、张普《信息处理用现代汉语语义分类体系》 „ 缺乏统计信息信息检索技术 47 Wordnet中语义相似度计算 Resnik 根据在 Wordnet 中上下位关系网络中两个词的公共祖先节点的最大信息量来 衡量两个词的语义相关度。 )]([max),( )},(),(|{21 21 pwxsubsumewxsubsumexcpp cpwwsimilarity ppp −= ∧∈ ),( wxsubsume 为词汇 w 的所有通过上下位关系相连结的祖先概念节点。 一个概念c 是一个由同义词构成的集合, p p p N cfreqcp )()( = , pN 是在该语料库中具 有词性 p 的词汇的总数, )( pcfreq 是具有词性 p 的概念c 在大规模语料库中出现的个数: ∑ ∈ = )( )()( pcwordsn p ncountcfreq , )( pcword 是在 Wordnet 中所有具有词性 p 的概念c 包 含的词汇,包括概念c 本身以及概念c 的通过上下位关系相连接的所有后代概念节点 信息检索技术 48 基于统计的方法 „ 将词汇的上下文信息的概率分布作为词 汇间语义相关度计算的参照 „ 建立在两个词汇具有某种程度的语义相 关当且仅当它们出现在相同的上下文中 这一假设的基础上信息检索技术 49 文本自动分类技术 „ 文本自动分类技术(Text Automatic Classification):基本任务是对一篇文 档,根据其内容,从预先定义好的标记 集中找出一个或者多个最适合于该文档 的标记信息检索技术 50 分类问题的描述 问题描述:给一个决策矩阵中的每个元素赋值,并且在 }1,0{ 的实数范围 内取值,如下表所示: d1 ⋯ ⋯ dj ⋯ ⋯ dn c1 a11 ⋯ ⋯ a1j ⋯ ⋯ a1n ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ci ai1 ⋯ ⋯ aij ⋯ ⋯ ain ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ cm am1 ⋯ ⋯ amj ⋯ ⋯ amn 其中, },,{ 1 mccC L= 是预先定义好的类别集合或者标记集合, },,{ 1 nddD L= 是待分类文档集合, jia , 是一个文档和类别标记的隶属度, ]1,0[, ∈jia 。 信息检索技术 51 说明 类别标记是一组符号。例如,大多数搜索引擎使用的类别体系, 包括科学技术、社会文化、政治军事、医疗健康、体育健身等; 文档对类别的隶属度应该是基于文档的内容,而不是基于描述 文档的元数据(Metadata)(例如文档出版日期、文档类型等); jia , 为一条件概率 )|(, jiji dcpa = ,如果 1, =jia ,表示第 j 个文 档完全属于第 i 个类别(或者说完全相关); 0, =jia ,表示文档 j 和 类别 i 完全无关。 信息检索技术 52 文本分类系统 文档预处理训练文档 系统词库 stopwords 文档索引 特征选择 分类模型 原始文档 分类算法 输入 中间处理 分类 输出 结果 训练过程 分类过程信息检索技术 53 分类预处理--文本的预处理 „ 对中文文本而言,最常用的文本源是 Internet上的HTML页面,其预处理步骤 包括: „ 去除HTML的标记以及乱码; „ 汉语分词; „ 过滤文本中的停止词。信息检索技术 54 分类预处理--建立文本索引 目前文本自动分类技术都是基于向量空间模型的。 对于文档集合,可以表示为坐标词和文档组成的矩阵 A (在具体的实现中,可以对不同的类别,采用不同的坐 标词)。 )( , jiwA = ,其中 jiw , 表示词 i 在文档 j 中的权 重。通常矩阵 A 是一个稀疏矩阵(如果用系统词典的全 部词作为横坐标,稀疏的问题会更为严重)。 信息检索技术 55 向量空间约简 „ 如果使用所有的在训练文档集合中出现 的词语作为二维空间的横坐标,那么表 示一个文档的向量的维数可能会很大。 通常的分类方法不能处理这种特征集, 时空复杂性过大,而且没有规模足够大 的训练集,用以保证分类结果的有效性。 因此,通常都要对向量空间进行约简。信息检索技术 56 主要约简方法 1. 基于文档频率特征选择:以在所有训练文 档集合中出现的词作为候选特征,从中去除那些包 含特征词的文档数小于某个既定阈值的特征。 2. 基于信息增益度(Information Gain)的 特 征 选择 3. 基于 2χ 分布的特征选择 4. 基于矩阵分解的特征选择 信息检索技术 57 分类方法 „ 主要分类算法大都基于统计和机器学习技术 „ 两类分类问题(Binary Classification)是 指待分类对象的目标类别只有两类,即“是”和 “不是” „ 多类问题(Multi-Classification),即类别 主题多于2的分类问题,也是实践中使用较多 的分类,它的结果往往是一个按相关度大小排 序的类别集合 „ 下面介绍的这些方法大多适用于多分类问题信息检索技术 58 几种数据表示 分类测试集 },,{ 1 Mdd L ,所有可能的类别集合 },,{ 1 Kcc L ; 分类训练集 },,{ 1 Ndd L ,已经被确定的类别集合 },,{ 1 Nyy L ; Nj 是训练集中属于类别 Cj 的文档数目。 信息检索技术 59 Rocchio算法 „ 文档分类的经典方法。 „ 基本思想:为每一个类别ci建立原型向 量,然后根据文档向量和类别原型向量 的距离,确定文档的类别。类别i的原型 向量是通过计算属于该类别的所有文档 向量的平均值而得到的。 „ 特点:速度快,但是精度较低。信息检索技术 60 Naïve Bayes算法 通过对训练数据的学习,得到在一个文档出现的条件下类别i出现的条件概率,我们用 Bayes方法来估计这一概率: )( )|()()|( dp cdPcPdcP ii i = ,简化为: )|()()|( iii cdPcPdcP = )(ˆ icP 为 )( icP 的估计: N NcP i i =)(ˆ 此方法最根本的特点是:假设文档中词语的出现是相互独立的,可以下式: ∏ = = M j ijii cdPcPcdP 1 )|()()|( )|(ˆ ij cdP 为 )|( ij cdP 的估计: ∑ =+ += M k kj ji ij NM NcdP 1 , ,1)|(ˆ 其中, ijN , 是训练集中词语(特征)j在类别 ic 中出现的次数。 这种方法其实是一种基于最小错误率的贝叶斯决策理论的分类方法。 信息检索技术 61 其它方法 „ 决策树算法 „ 最大熵分类信息检索技术 62 自动聚类(Automatic Clustering) „ 当系统没有预先定义的类别集,训练数 据也没有标注类别信息的情况下,直接 由训练数据之间的相似性进行分组 „ 典型的无导师机器学习问题 „ 大致可以分为层次聚类法和平面聚类法谢谢!

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档

相关文档