张华平 博士 副教授 研究生导师 计算机语言信息处理研究所 副所长 Beijing

Presentation on theme: "张华平 博士 副教授 研究生导师 计算机语言信息处理研究所 副所长 Beijing"— Presentation transcript:

1 张华平 博士 副教授 研究生导师 计算机语言信息处理研究所 副所长 2010-3-12@Nokia Beijing
面向互联网应用的中文浅层语言分析技术 张华平 博士 副教授 研究生导师 计算机语言信息处理研究所 副所长 Beijing

2 纲要 常用汉语分词方法综述 浅层语言分析的需求背景 ICTCLAS2010: 中文浅层语言分析集大成者 互联网搜索对语言分析的新需求与挑战 总结与展望

3 问题背景 汉语的书面语是按句分开的,词与词之间没有明确的分隔标记。 词是最小的能够独立活动的有意义的语言成分 。 中文信息处理只要涉及句法、语义(如检索、翻译、文摘、校对等应用),就需要以词为基本单位。句法分析、语句理解、自动文摘、自动分类和机器翻译等，更是少不了词的详细信息 。

4 分词的必要性： 词语信息熵大，计算速度更快
evidence understand school physics physics barber theory subject price 物 学 物理学 理 products science study credit image … … reason student … body physicist × × = :

5 主要困难 重叠词、离合词、词缀 高高兴兴，高兴高兴，糊里糊涂，白花花，研究研究，个个，回回，工作工作（错误）
洗了一个澡，担什么心，发理了没有 学术性、花儿，盆儿

6 主要困难2：汉语的切分歧义 交集型歧义（交叉型歧义）：如果字串abc既可切分为ab/c，又可切分为a/bc。其中a，ab，c和bc是词；占86%. 有意见： 我 对 他 有 意见。 总统 有意 见 他。 组合型歧义（覆盖型歧义）：若ab为词，而a和b在句子中又可分别单独成词，占14%. 马上： 我 马上 就 来。 他 从 马 上 下来。 将来： 我 将来 要 上 大学。 我 将 来 上海。 混合型歧义：由交集型歧义和组合型歧义自身嵌套或两者交叉组合而产生的歧义 人才能：这样 的 人才 能 经受 住 考验。 人才能：这样 的 人 才能 经受 住 考验。 人才能：这样 的 人 才 能 经受 住 考验。

7 主要困难2续：歧义问题 歧义全局歧义与局部歧义: 乒乓球拍/卖/完了； 乒乓球/拍卖/完了； [护士对喝酒的病人说:]“小心/肝”
[爱人对你说:]“小/心肝”

8 主要困难3：未登录词问题 命名实体、新词术语往往不能全部收录到分词词典中，一般分词系统的词典是静态的，对未登录词的处理 干扰作用 克林顿对内塔尼亚胡说 龚学平等领导 根据我们的实验，未登录词和歧义问题大约占所有词语中的1.73%,但是导致了3.76%的切分错误。

9 汉语切分的数据结构－词图 根据这个数据结构，我们可以把词法分析中的几种操作转化为：
中国 国人 人民 国 人 民 万 岁 中 S E 万岁 中国人 根据这个数据结构，我们可以把词法分析中的几种操作转化为： 给词图上添加边（查词典，处理重叠词、离合词、前后缀和未定义词）； 寻找一条起点S到终点E的最优路径（切分排歧）； 给路径上的边加上标记（词性标注）；

10 汉语切分算法综述 规则方法 统计方法 规则统计结合方法 全切分 最大匹配方法 最短路径方法 N元语言模型； 互信息、
最大熵方法、条件随机场； 规则统计结合方法 N元语法

11 全切分方法 给出所有的切分结果 算法（略） 算法的时间复杂度随着句子长度的增加呈指数增长

12 最大匹配方法 1 正向最大匹配（MM） 逆向最大匹配（RMM) 双向最大匹配 自左往右 每次取最长词 自右往左 依次采用正向和逆向最大匹配
如果结果一致则输出 如果结果不一致再用其他方法排歧

13 最大匹配方法 II 优点 缺点 简单、快速 在某些应用场合已经足够 单向最大匹配会忽略交集型歧义和组合型歧义
幼儿园 地 节目 ／ 独立自主 和平 等 互利 的 原则 双向最大匹配会忽略链长为偶数的交集型歧义和组合型歧义 原子 结合 成分 子时 ／ 他 从 马上 下来

14 最短路径方法

15 最短路径方法 II 基本思想： 算法： 优点：好于单向的最大匹配方法 缺点：忽略了所有覆盖歧义，也无法解决大部分交叉歧义
在词图上选择一条词数最少的路径 算法： 动态规划算法 优点：好于单向的最大匹配方法 最大匹配：独立自主 和平 等 互利 的 原则(6) 最短路径：独立自主 和 平等互利 的 原则(5) 缺点：忽略了所有覆盖歧义，也无法解决大部分交叉歧义 结合 成分 子时

16 N元语法分词方法 句子的出现概率用P(W) 将分词问题转化为求概率最大的词语序列问题。 引入三元模型，不考虑未登录词问题，精度可以达到98%以上； 常用的模型为二元(一阶马尔科夫模型)和三元模型(二阶马尔科夫模型)

17 互信息与双字耦合度方法 互信息(MI，Mutual Information)用来表示两个字之间结合的强度 双字耦合度
“过目”这一双字对在出现16次，其中出现在“过目不忘”，“一一过目”这样的词中12次，而在“超过/目前”这样的语境中出现了4次，所以Coup（<过,目>）=12/(12+4)=0.75。 研究结果表明：随机字对总数超过3600万，但只有10万左右的字会相邻构词，规律性极强，可以通过这一规律进行分词。

18 其他方法 决策树方法： 最大熵方法： 最大压缩方法： 将分词问题转化为决策判断问题
将字分为单字词、词首、词中、词尾，训练信息熵，最后将分词问题转化为求解信息熵最大的标注方法（类似与词性标注）。 他/SS 说/SS 的/WF 确/WE 在/WF理/WE。/DELIM 最大压缩方法： 将词语作为一个信息单元，最后对文本进行压缩，压缩比最好的信息单元就是最佳的分词结果。

19 相关切分算法的对比测试实验 [召回率/结果数]

20 Web搜索的串划分的简化方法 基于字的n元切分方法（C1C2…CN）： ->|Cn*k+1…Cn(k+1)| k=0,…[N/k]-1 n元交叉切分算法（C1C2…CN） ： ->|Ck…Ck+n| k=1,…N-1 串分割速度快，前者存在漏检问题，后者覆盖率全面，但是后者的存储和索引项是前者的n倍； 在小型或者语言非敏感的检索应用场景中，串划分简单快捷有效。

21 纲要 常用汉语分词方法综述 浅层语言分析的需求背景 ICTCLAS2010: 中文浅层语言分析集大成者 互联网搜索对语言分析的新需求与挑战 总结与展望

22 需求背景-Web内容现状 (CNNIC第19次报告)
网页数 全国网页总数 4,472,577,939个 其中：静态网页数 2,025,348,984个 动态网页数 2,447,228,955个 静、动态网页数比例 0.83 :1 平均每个网站的网页数 5,057.2个 网页字节数 全国网页总字节数 122,305,737,000 KB 平均每个网页字节数 27.3 KB 平均每个网站的网页字节数 137,297.9 KB

23 需求背景-内容形式

24 Web成为当前自然语言处理的主要对象； 需求背景 超大规模： 截止到2006年，CNNIC报告数据为122TB，实际规模更大；
语言形式自由灵活：Webpages/ BBS/ Blog / SMS/ Browse and Search Log 时序性：用语、表达方式均在动态变化； 多维度关联：正文、图片、链接、评论等 社会动态交互性：发布者、接收者

25 新环境下，语言呈现出新的特征：新、变、短、杂；
需求背景 新环境下，语言呈现出新的特征：新、变、短、杂； 新：新的术语/说法/现象/话题； 变：词形、词性、词义的变化； 短：短小、简约经济原则； 杂：个性化，形式和内容不规范，多种多样，不一而足。

26 需求背景 新形势下，传统自然语言处理存在明显不足 重精度而忽视速度效率：复杂精准的分词算法速度大约在每秒5000字，最高不超过100KB/s
重个案而忽视统计性能：比如语言学家各种人造的未登录词和歧义问题，实际上，这些问题在实际语言中可以忽略不计。 重通用研究而忽视工程定制：全面深度分析实际上并非必要，面向特定领域可以简单定制的系统往往可以事半功倍。

27 浅层语言分析 浅层语言分析：针对信息网络（大规模Web和短消息）环境下的语言文字信息，从实际应用出发，研究自然语言的表示、关联、变化与计算的一门计算语言学的分支学科。 浅层语言分析 vs. 传统自然语言处理： Full and inefficient vs. Shadow and efficient Customized vs. Generalized Sensitive vs. Robust

28 浅层语言分析四大科学问题 表示：语言的局部表示问题 关联：语言内在的关联问题
采用什么样的模型来表征某个单位（句子、篇章）的语言：n-gram, HMM, EM, CRF, VSM 如何标注语言的各个元素：分词、词类标注、命名实体与未登录词识别。 语言篇章的抽取与分析：元信息抽取：时间、地点、人物、主题、关键词(TAG)；分析：态度分析、聚类 关联：语言内在的关联问题 语言元素之间潜在关联分析：同义、近义、某种潜在关联(拼音与词语；输入错误、共同的某个媒介等)、查询扩展； 语言内容与其他元信息之间的关联：用户兴趣、发送时间、作者、链接、网页关联、搜索点击关联等；

29 浅层语言分析四大科学问题 变化：语言的宏观变化问题 计算：大规模计算问题 如何最快地反应语言的变化：有意义串（新词、新话题与新现象）；
语言在时间、空间、事件等多维度的动态变化规律 如何表征语言话题的发展趋势分析与预测： 计算：大规模计算问题 如何解决不规范噪音问题：大规模萃取 Tradeoff between deep understanding and high performance 语言计算往往精而不准、准而不精，如何满足大规模Web计算的要求？频率高的词未必是热门话题，回复最多的、转发最多的信息才是热门，辅助语言计算往往事半功倍。

30 潜在的应用方向 面向Web的浅层语言计算； IR：索引词分析、相关搜索； 文本挖掘：特征分析、关键词抽取;
态度分析：词语的感情色彩和上下文环境分析； 舆论热点与流行分析：热点词语抽取、有意义串和新词 趋势分析：发展趋势分析 面向搜索和浏览日志的用户行为分析； 用户兴趣建模：词语语义聚类与关联分析； 定向精准营销：营销需求与用户兴趣关联。

31 纲要 常用汉语分词方法综述 浅层语言分析的需求背景 ICTCLAS2010: 中文浅层语言分析集大成者 互联网搜索对语言分析的新需求与挑战 总结与展望

32 ICTCLAS：HHMM Architecture
Character String Class-based WS model Word graph Atom Segment NSP rough segment Unknown word recognition Training Role model Corpus Lexical result Optimized selection

33 ICTCLAS: Word Segmentation
Word class definition Class-based segmentation model wi iff wi is listed in the segmentation lexicon; PER, LOC, ORG, TIME or NUM iff wi is an unknown named entity; STR iff wi is an unknown symbol string; BEG iff beginning of a sentence END iff ending of a sentence OTHER otherwise. ci =

34 ICTCLAS: Unknown word recognition
In unknown word recognition, we mainly deal with Named Entities, such as person names, location names, organization names, and transliterations of foreign names We use two-level HMM for unknown word recognition In 1st level HMM, we recognize person names，simple location names, transliterations of foreign names and other proper names In 2nd level HMM, we recognize complex location names and organization names, usually with some simple unknown words as its components.

35 ICTCLAS : Unknown word recognition(Cont.)
We divided the role tag set into an internal tag set and an external tag set The role tags in the internal tag set represent the component of the unknown words The role tags in the external tag set represent the context of the unknown words There is a sub-HMM for each role-tagging HMM, which only use the tags in the internal tag set. We call it the internal-HMM of the role-tagging HMM.

36 ICTCLAS: Unknown word recognition
Unknown words recognition: role-based HMM 毛/Surname 泽/Mid_name 东/last_name 1893年/context 诞生/remote_context Probability P(Wi|Ci) of recognized unknown words could be estimated in role-based HMM ZHANG Hua-Ping, LIU Qun, YU Hong-Kui, CHENG Xue-Qi, BAI Shuo. Chinese Named Entity Recognition Using Role Model. Published in International Journal of Computational Linguistics and Chinese Language Processing, 2003,Vol. 8 (2)

37 ICTCLAS Solution Sample
-log p(泽|毛) -log p(NUM|东) -log p(年|NUM) 毛/毛 泽/泽 东/东 1893/NUM 年/年 诞/诞 生/生 -log p(毛|S) -log p(诞|TIME) S/S -log p(TIME|东) -log p(PER|S) -log p(NUM|PER) E/E 毛泽东/PER 1893年/TIME 诞生/诞生 log p(TIME|PER)

38 ICTCLAS Evaluation: Result

39 ICTCLAS Evaluation: National Evaluation
Domain #Words WP(%) PP (%) RPP (%) Sports 33,348 97.01 86.77 89.31 International 59,683 97.51 88.55 90.78 Culture 20,524 96.40 87.47 90.59 Law 14,668 98.44 85.26 86.59 Theory 55,225 98.12 87.29 88.91 Economics 24,765 97.80 86.25 88.16 Total 208,213 97.58 87.32 89.42 Note:1)WP: word segmentation precision; PP: POS tagging Precision; RPP: relevant POS tagging Precision 2) The evaluated POS set is different from ours.

40 ICTCLAS Evaluation: International Bakeoff
The First International Word Segmentation bakeoff was held by SIGHAN (the Special Interest Group on Chinese Language Processing) affiliated with Association of Computational Linguistics on Apr , 2003. 12 Participants from China, China Taiwan, China Hong Kong, Japan, Singapore and USA. Including Peking Univ. , Microsoft, U.Penn, Systran. ICTCLAS ranks top within all participants. It indicates that ICTCLAS is one of the best Chinese lexical analyzers in the world till now.

41 ICTCLAS Evaluation: International Bakeoff(Cont.)
Six tracks: (Site ID: S01) All GB-coded tracks: CTBo,c and PKo,c Both BIG5-coded close tracks: ASc and HKc Ranks in the evaluation (Richard Sproat, 2003) PKc: #1/8; PKo: #2/6; CTBc #1/5; CTBo: #4/5 Asc #5/5; HKc rank #4/4

42 ICTCLAS2010: 完美双数组TRIE树词典管理算法
Motivation: Convert TRIE-structured dictionary into double linear array with the minimal size (space usage is over 90%). S A B C D E F S A B C D E F … base check S A B

43 ICTCLAS2010: 完美双数组TRIE树词典管理算法
The entry query time is O(word_length). The performance will not decrease as the dictionary size grow. On PIV/256M PC, it can query over 800,000 entries per second. Making maximum word segmentation with such lexicons, the speed is 23.5MB/s.

44 ICTCLAS2010最新进展 技术革新： 采用完美双数组TRIE树专利算法，词典查询速度与词典规模无关，内存占用仅为词典文本的2-3倍，查询速度仅和词长相关。 整个系统没有任何一个耗时的字符串操作； 模型参数的优选剪支，参数规模下降90%,采用较好的平滑算法估计零概率事件； 分词、命名实体识别、词性标注编译级别定制组合； API控制在200KB以内，内存消耗在10M左右，切分速度接近1MB/s；符合大规模浅层语言分析的需要；

45 ICTCLAS2010最新进展 应用革新： 支持外置的大规模用户专业词典，用户词典规模在20万左右，系统切分速度仅降低10%；
支持Windows/Linux/FreeBSD操作系统，支持C/C++/C#/Java/VB等主流编程语言；完全兼容Lucene； 经过150G实际网页开放式测试，鲁棒性经过实际环境测试。 FreeCode版本已经在全球授权3万余份，自发建立了多个ICTCLAS的研究社团，ICTCLAS2010在中科院计算所的搜索应用系统中大规模应用，在中科计算技术转移中心专业孵化，建立了完备的技术支持与服务体系，目前已经授权给NEC、Citylife.com、台湾交通大学等数十家企事业单位。

46 ICTCLAS2010综合测试结果 -真正适合Web的浅层语言分析利器

47 汉语分词系统 ICTCLAS2010:内核为ICTCLAS2010，融入了量身定做的特色功能：Java/C++/C/C#等接口；兼容Linux/FreeBSD/Windows ICTCLAS主要功能包括中文分词、动态用户词典、分词粒度可调、新词识别、词性标注、多级词性标注、关键词提取、指纹提取 。 国内和国际权威的公开评测第一、十万客户的认可; 综合性能最优,ICTCLAS2010分词速度单机996KB/s，分词精度98.45%。 全方位支持各种环境下的应用开发,支持Windows/Linux/ FreeBSD操作系统，支持C/C++/C#/Java/VB等主流编程语言； 应需而变，量身定做 Content Layouts 47

48 ICTCLAS汉语分词系统 Content Layouts 48

49 新特征词识别结果示例

50 ICTCLAS2010版本结果示例

51 纲要 常用汉语分词方法综述 浅层语言分析的需求背景 ICTCLAS2010: 中文浅层语言分析集大成者 互联网搜索对语言分析的新需求与挑战 总结与展望

52 互联网新的语言分析需求 单纯的分词、命名实体识别和词性标注远远不能满足要求；
分词算法与粒度问题：分词算法与检索存在复杂的关系，作为分析处理粒度的语言单元和搜索精度与速度存在着制约关系；如：中科院计算所； 语言变化更新问题：Web搜索需要适应新的语言变化，及时更新并追踪最新的语言形式，对检索的速度和精度都至关重要，决定搜索是否能够“与时俱进”，是否能够做时尚的前锋。

53 (Average precision/ R-Precision)
分词算法与粒度问题 不同分词应用与搜索的对比实验 查询切分 文档切分 人工切分 (Average precision/ R-Precision) 和文档切分方法一致 单字切分 0.3021/0.3511 0.3192/0.3565 交叉二元切分 0.3312/0.3756 0.3427/0.3823 ICTCLAS 0.3496/0.3812 0.3583/3872

54 分词算法与粒度问题II 分词性能与检索精度的关系

55 分词算法与粒度问题III 面向Web搜索的分词系统要求： 分词算法的时间性能要比较高；
分词正确率的提高并不一定带来检索性能的提高 ；中国|历史学|会 分词粒度应该根据索引大小、检索速度、精度与召回率专门定制规范，原则：采用大规模Web信息最大压缩的思路，检索与索引量大的长习语优先入库； “八荣八耻”、“方永刚精神”； 词库可以新增和删除，粒度可调整 ； 未登录词识别的准确率要比召回率更加重要。

56 分词算法与粒度问题IV 我们专门定制了面向大规模搜索引擎应用的ICTCLAS2010-IRSEG系统：
自动抽取切分规范词库，并进行检索精度、召回率与速度上的检验； 算法综合权衡速度与性能

57 有意义串挖掘问题 有意义串的定义: 结构完整、语义单一完整、语用灵活、有一定流通度；
新出现、有一定使用频次的有意串往往是热点的特征线索，就是一个很有价值的社会现象。如“非典”、“禽流感”、“超女”这些串反映了当时社会上广泛关注的热点事件。 有意义串往往是一些固定搭配，其语义粒度较词更具有区别性。 2006年度的部分有意义串示例： 自主创新 “十一五”规划 和谐社会 社会主义新农村 社会主义荣辱观 丛飞 消费税 青藏铁路 德国世界杯 双核

58 有意义串挖掘问题-算法

59 有意义串对搜索应用的价值 有意义串可以应用于构建专业术语词典。
有意义串可以及时发现最新的网络语言与即将流行的话题，是反映网络发展变化的晴雨表。 有意义串反映了最近用户潜在检索新潮流，提高服务的前瞻性，增加对应的索引项或者直接Cache，提供查询的精度，加快检索的速度；

60 有意义串分析结果 艾滋病病毒 安检人员 半裸 宝马车 保监 保险补贴 保险营销员 保障体系 报警电话 暴风修士 避税 便利化 标准化畜禽 博客 查赌 车辆图像记录系统 城中村 创新体系 创新型国家 磁悬浮项目 存款准备金率 典当合同 电动自行车 电瓶垃圾车 电影兑换券 电子化考试 电子警察 独岛 短信订票 短信消费 恩格尔系数 法定退休年龄 返程投资 光雕 国六条 韩日世界杯 航空货运市场 华北商埠 环保型电瓶垃圾车 换妻 黄宏生案件 黄金周 婚姻合同 活禽 火锅油 火炉山

61 纲要 常用汉语分词方法综述 浅层语言分析的需求背景 ICTCLAS2010: 中文浅层语言分析集大成者 互联网搜索对语言分析的新需求与挑战 总结与展望

62 总结与展望 面向互联网搜索应用需求，传统自然语言处理存在不足，浅层语言分析成为Web语言分析的关键利器； ICTCLAS2010综合速度与准确率，是适合Web搜索应用的浅层语言分析系统； 新的需求在于：分词算法与粒度定制、有意义串挖掘；

63 展望：Next Generation Web
Architecture: From server-centered to Peer-distributed P2P, BLOG

64 展望：Next Generation Web II
From information to Message Interactive, dynamic Community Instant Messenger, Online chat: MSN Messenger, ICQ, QQ

65 展望：Next Generation Web III
From one single dimension to multi-dimension Text content, multimedia data Timestamp Information structure Relationship network: such as sender & receiver time data Receiver Sender

66 Toward Next Generation Web Computing …
P2P-centered Web platform Personalization Modeling and Personalized Web Services Message Full-Scale Mining: temporal reasoning, text mining, data mining, knowledge management, community generation … Customized Shallow Chinese Language Computing would be popular.

67 Thanks!