中文分词词性标注系统.ppt

中文自动分词系统IRSEG 设计与实现,高立琦 王卓然 2004.9.20,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,中文分词的意义和用途,汉语的特点 最小书写单位为字 最小表意单位为词 词与词之间没有书写边界 分词系统的用途 各种中文信息处理系统的基础模块 自然语言处理 信息检索 ,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,IRSEG系统框架设计,资源: 词典资源，未登录词知识库等,构建分词有向图,重叠词识别,未登录词识别,歧义字段处理,输出,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,数学模型与原理分析,信道噪声模型 设S=c1c2cn为输入汉字序列，W=w1w2wm为切分词序列。 分词系统的任务是，找到一种切分结果W*，满足： 根据贝叶斯公式： 假设：一个词wi的出现概率以它前面的词的出现没有关系（Unigram模型） 则： 为了实现上的方便，我们对上述公式取负对数，得到：,数学模型与原理分析(续),构建分词有向图 通过最短路径搜索，即得最优（概率最大）结果： 结合 / 成/ 分子,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,“N最短路径”算法设计,N最短路径的思想 中科院张华平博士提出”N最短路径“粗分模型 IRSEG系统的背景 哈工大信息检索研究室CUP自然语言理解平台 IRSEG中”N最短路径”模块的特点 追求最短路径的准确率和召回率 在CUP平台中利用高层语言信息的反馈纠正分词结果 算法设计 利用分词有向图的特点（有向无环图） 明显减小了时间复杂度和空间复杂度,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),结 合 成 分 子,“N最短路径”算法设计(续),回溯得到N最优结果： 结合 / 成 / 分子 结合 / 成分 / 子 结 / 合成 / 分子 结合 / 成 / 分 / 子 时间复杂度： 搜索过程时间复杂度为O(k)，K为图中边的总数； 保留结果过程插入排序时间复杂度O(N2)； 总时间复度为O(k*N2)。,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,未登录词识别模块,Unigram的困境 很有效的解决歧义字段切分问题 绝大多数歧义现象为交集型歧义 对未登录词识别力不从心 未登录词构成极其复杂 与上下文形成各种歧义 自身构成形成各种歧义 很多情况下需借助上下文信息 Bigram性价比很低 90%以上的问题Unigram可以解决得很好 Bigram需要很大规模的训练语料和更复杂的词典结构 Bigram解码过程复杂度高，产生N最短路径开销是可观的,未登录词识别模块(续),局部Bigram模型 思想 在必要的范围应用Bigram模型 全局以Unigram模型为主 借助平滑的思想用插值将不同维数概率结合起来 用聚类的方法处理数据稀疏问题 优点 时间复杂度小（几乎与Unigram的相同） 不需要大规模的训练语料 可以通过方便的调节上下文信息对未登录词识别的影响 在原有数据结构上稍作修改即可输出N最短路径 达到和整体Bigram模型相当的效果,大纲,中文分词的意义和用途 IRSEG系统框架设计 数学模型与原理分析 “N最短路径”的算法设计 基于局部Bigram模型的未登录词识别模块 系统评测,系统评测,词典资源