自然语言理解-词法分析.ppt

词法分析 语言根据词的形态结构分类 分析型语言没有专门表示语法意义的附加成分汉语 藏语黏着型语言词内有专门表示语法意义的附加成分芬兰语 日语曲折性语言用词的形态变化表示语法关系英语 德语 法语 什么是词 词是语言中最小的能独立运用的单位 是信息处理的基本单位 界定词的困难所在单字词与语素之间的划界词与短语之间的划界汉语自动分词把没有明显分界标志的字串自动切分为词串 背景汉语的特点 汉语是大字符集的语言英语有26个字母 而常用的汉字就有六七千个 总数超过五万 书面汉语的词与词之间没有明确的分隔标记 背景 汉语中兼类现象严重例如 和 根据 现代汉语词典 可以有五种读音 六种词性 以及十六种不同的词义 印欧语系多有形态变化 而汉语缺少形态变化例如 复数 单数 过去 现在 阴性 阳性等等 汉语词法分析所面临的问题 分词词表重叠词 词缀分词和理解 孰先孰后 歧义切分字段专有名词的识别 分词词表 汉语词的抽象定义 既 词是什么 与具体判定 既 什么是词 问题 语言学界并未完全解决 词表对自动分词而言 是最基础的 构件 分词词表 信息处理用现代汉语分词规范 迄今也没有一个公认的 具有权威性的词表 这是分词问题所面临的第一个困难 汉语双字形容词的重叠形式 汉语单字形容词的重叠形式 汉语双字动词的重叠形式 汉语单字动词的重叠形式 汉语其他词类的重叠形式 名词哥哥 人人山山水水 是是非非 方方面面 头头脑脑数词一一做了回答 两两结伴而来量词个个都是好样的 回回考满分副词常常 仅仅 的的确确 汉语重叠词的特点 汉语词能否重叠具有很强的个性特点研究研究 工作工作 有些词重叠后词性发生了变化形容词重叠后一般成为状态词个别量词重叠后可以成为其他词性回回 副词个个 名词 汉语词缀 前缀老鹰 老虎 老三 老王超豪华 超标准 超高速非党员后缀骨头 砖头 甜头 苦头 盼头 想头桌子 椅子 孩子 票子 房子文学家 指挥家 艺术家科学性 可能性 学术性碗儿 花儿 玩儿 份儿 片儿 分词和理解 孰先孰后 计算机分词仍然面临知识短缺的大问题 计算机大概永远做不到像人那样先理解后分词 不可企求百分之百的正确切分 这是自动分词所面临的第二个困难 汉语切分歧义 例子公路局处理解放大道路面积水问题 南京市长江大桥说 歧义切分字段定义1 1交集型歧义 字串ABC 其中汉字字串A B C的长度均大于零 该字串可以切分为AB C或A BC 则称该字串为交集型歧义字串 例如 出现在 出现 在 切分1 出现在 出 现在 切分2 歧义切分字段 定义1 2组合型歧义 字串AB 其中汉字字串A B的长度均大于零 该字串可以切分成AB或A B 则称该字串为组合型歧义字串 例如 马上 马 上 切分1 马上 马上 切分2 歧义切分字段 混合型歧义 由交集型歧义和组合型歧义自身嵌套或两者交叉组合而产生的歧义人才能 这样的人才能经受住考验 人才能 这样的人才能经受住考验 人才能 这样的人才能经受住考验 真歧义和伪歧义 真歧义确实能在真实语料中发现多种切分形式比如 应用于 地面积 伪歧义虽然有多种切分可能性 但在真实语料中往往取其中一种切分形式比如 挨批评 市政府 交集型歧义字段的链长 链长 交集型歧义字段中含有交集字段的个数 称为链长 链长为1 和尚未链长为2 结合成分链长为3 为人民工作链长为4 中国产品质量结合成分子时链长为6 努力学习语法规则链长为7 治理解放大道路面积水 真实语料中歧义字段的分布 汉语真实文本中的分词歧义情况 材料一 孙茂松等1999一个1亿字真实汉语语料库中抽取出的前4 619个高频交集型歧义切分覆盖了该语料库中全部交集型歧义切分的59 20 其中4279个属伪歧义 占92 63 如 和软件 充分发挥 情不自禁地 覆盖率高达53 35 材料二 刘开瑛2000 第4章78248个交集型歧义字段中 伪歧义 94 真歧义 6 汉语真实文本中的分词歧义情况 续 分词歧义的四个层级 何克抗等1991 50883字语料 词法歧义 84 1 用方块图形式加以描述 句法歧义 10 8 他一阵风似的跑了 语义歧义 3 4 学生会写文章 语用歧义 1 7 美国会采取措施制裁伊拉克 分词模型 歧义切分字段 分词模型阶段一 生成解空间 根据分词词表及其某种切分原则 找出输入句子的侯选切分集合 以供下一阶段处理 最大匹配法是极端之一 给出唯一侯选 侯选即解 分词模型 全切分法是另一个极端 给出输入句子的所有可能切分形式 可实现无盲点分析 代价是解空间膨胀太大 又会造成许多不必要的干扰 关键 能否在保证无切分盲点的前提下 给出尽可能小的解空间 分词模型阶段二 在解空间中求解解决切分歧义的策略 大致有三 基于规则 基于词频 基于隐Markov模型 阶段二 在解空间中求解 基于规则 这类研究吸取了人工智能及专家系统的思想 基于规则 主要困扰是 囿于目前汉语parser的能力 任何期望倚重parser作为解决歧义切分之手段的设想尚缺乏现实的基础 由于无法实现parsing 分词系统所能利用的句法 语义规则必然是局部的 基本上仅涉及若干毗邻词之间的线性关系 可靠性不强 难以建立完整 有效 无矛盾的体系 阶段二 在解空间中求解 基于词频 基于词频的排歧问题可抽象为求有向图两点间最优路径问题 较最大匹配法 可望将切分精确率提高约1 基于词频 本质上这是一个关于词的零阶Markov模型 也称作unigram 存在明显缺陷 其表现不依赖于上下文而变化 例如 字段 只是 或一律作为一个词被切出来 或一律被切成 只 是 完全取决于 只 是 和 只是 的词频 阶段二 在解空间中求解 基于隐Markov模型 语法知识以统计形式量化在标记的概率转移矩阵中 表示简洁 均匀 处理灵活 一致 避免了采用规则系统的某些弊端 基于隐Markov模型 统计数据从不受任何限制的实际语料中获得 可有效提高分析系统的能力及覆盖面 并且分词结果能随时反馈到统计数据中 使系统有一定的自学习功能 模型的求解仍可归结为有向图两点最优路径问题 基于隐Markov模型 关键 以隐Markov模型为主要手段解决切分歧义 是一种最有希望的方案 但 单打一 恐怕不能完全奏效 必须集成多种手段 方法 专有名词的识别 许多分词算法都是在完备词表的假设下设计的 这一假设并不成立 新词不断涌现 而且专有名词虽然不新 但不可能尽收 专有名词的识别 一般说来 专有名词包括 中国人名 中国地名 译名 组织机构名 事件名 时间数量名 商标名 专有名词的识别 陈 nhf平 nhs为 vl北京大学 ni中国经济研究中心 ni经济学 n教授 n w中心 n副 f主任 n w主管 v科研 j w w1968 m年 nt获 v中国科技大学 ni物理系 n学士 n学位 n w1987 m年 nt获 v美国 ns德克萨斯大学 ni物理学 n博士 n学位 n w 陈平 人名 美国 地名 北京大学 中国科技大学 中国经济研究中心 及 德克萨斯大学 属于组织机构名 专有名词的识别 不同的语料 专名所占的比例也不同 对455万字的人民日报语料统计的结果显示 专名占5 74 其中 中国人名占2 55 地名占2 55 外国译名占0 73 如果不予处理 会对切分精确率造成比歧义字段更大的影响 研究进展中文词语的分析过程 预处理过程的词语粗切分 切分排歧与未登录词识别 词性标注在实际的系统中 这三个过程可能相互交叉 反复融合 也可能不存在明显的先后次序 研究进展主要的汉语自动分词系统有 北航的CDWS系统 国内公开的第一个实用性汉字分词系统 采用的自动分词方法为最大匹配法 辅助以词尾字构词检错技术 使用知识库进行纠错 北航的CASS系统 它使用的自动分词方法是正向增字最大匹配法 使用知识库处理歧义字段 研究进展 山西大学的ABWS分词系统 使用 两次扫描联想回溯 法 利用联想 回溯来有效地解决歧义组合结构的切分 同时兼有自动检错和纠错的功能 其分词子系统较好地利用了语言学中的词法知识 句法知识 并具有调用分词规则切分歧义字段和回收生词等功能 北师大的自动分词专家系统 首次将专家系统方法引入到分词系统中 研究进展 清华大学SEG分词系统 此系统提供了带回溯的正向 反向 双向最大匹配法和全切分 评价切分算法 由用户来选择合适的切分算法 其特点则是带修剪的全切分 评价算法 清华大学SEGTAG系统 该系统对词典中的每一个重要的词都加上了切分标志 即标志 ck 或 qk 通过这两种标志并使用几条规则来实现有限的全切分 为了获得切分结果 系统采用在有向图DAG上搜索最佳路径的方法 所运用的搜索算法有两种 即 动态规划 和 全切分搜索 叶子评价 使用了词频 词类频度 词类共现频度等统计信息 研究进展 中科院计算所的词语分析系统ICTCLAS 采用N 最短路径方法进行词语粗分 概率统计 然后用HMM的方法进行分词和标注的一体化处理 国家语委文字所应用句法分析技术的汉语自动分词 此分词模型考虑了句法分析在自动分词系统中的作用 以更好地解决切分歧义 切词过程考虑到了所有的切分可能 并运用汉语句法等信息从各种切分可能中选择出合理的切分结果 研究进展 复旦分词系统 首先 使用正向最小匹配和逆向最大匹配对文本进行双向扫描 如果两种扫描结果相同 则认为切分正确 否则就判别其为歧义字段 使用构词规则和词频统计信息来进行排歧 哈工大的统计分词系统 是一种典型的运用统计方法的纯切词系统 它试图将串频统计和词匹配结合起来 研究进展 杭州大学改进的MM分词系统 其实质为MM 规则 微软研究院多国语言处理平台NLPWin中的中文词语分析词系统 采用了切词 句法分析一体化的方法 使用语法规则并以概率模型作导向来进行排歧 北京大学计算语言学研究所的汉语切分与标注系统 把分词和词类标注结合起来 采用基于规则的标注排歧与基于语料库统计模型的排歧相结合的处理方法 研究进展 北大计算语言汉语文本分析系统 该系统中采用了一种综合性歧义切分处理方法 其要点有 把汉语基本词典中所有的歧义词标记出来 把所有的歧义字段分为两类 简单歧义字段和复杂歧义字段 在切分时 如果匹配出来的词不是歧义词 则可以安全地切分出来 研究进展 当匹配出歧义词时 根据词条的歧义信息 歧义偏移值 判断当前歧义字段的类别 如果是简单歧义 则使用一条非常简单的规则即可全部得解 即优先切出非歧义词 如果是复杂歧义字段 则调用一个 侦歧 过程 进一步判断歧义字段的类型是 歧义词 歧义词 还是 连续型歧义字段 考察词条的 歧义触发信息 和 歧义消隐信息 即可解决所有局部 直接上下文 的歧义 通过浅层句法分析及其同步的语义检查 义类代码及配价项的检查 消解句子级歧义 一个具体系统 前处理 在前处理中解决的问题 文本的一致性文本中的控制词 文本的一致性 中文编码GB 中文词 GB标点 GB字符 ASCII ASCII标点 ASCII字符 同一文本中会出现GB和ASCII 例 鲁迅说 世上本没有路 鲁迅说 世上本没有路 鲁迅说 世上本没有路 例 鲁迅说 世上本没有路 C2B3D1B8A3BAA1B0B0CBB5CAC0C9B1BEC3BBD3D0C2B7A3A1A1B1鲁迅说 世上本没有路 C2B3D1B8A3BA3A22B5CAC0C9B1BEC3BBD3D0C2B72122鲁迅说 世上本没有路 C2B3D1B8A3BA3AB0CBB5CAC0C9B1BEC3BBD3D0C2B721A1B1 GB ASCII混用问题 数据结构GBtwobytesASCIIonebyte系统必须正确识别 不然就会出现乱码 解决方法 将ASCII扩展到两个字节 鲁迅说 世上本没有路 C2B3D1B8A3BAA1B0B0CBB5CAC0C9B1BEC3BBD3D0C2B7A3A1A1B1鲁迅说 世上本没有路 C2B3D1B8A3BA003A0022B5CAC0C9B1BEC3BBD3D0C2B700210022鲁迅说 世上本没有路 C2B3D1B8A3BA003AB0CBB5CAC0C9B1BEC3BBD3D0C2B70021A1B1 控制词问题 控制此并不影响人的理解 但影响系统的识别 这就是人们常说的鹬蚌相争的故事 这就是人们常说的鹬蚌相 争的故事 怎样做 鹬蚌相争 是词组 成语 鹬蚌相 争 还是成语吗 系统必须删除 才能处理文本 解决方法 删除所有控制词 空格 回车 制表符 为便于人的阅读 在段落之间保留控制词 分词 全切分 切分将一个字符串分为几部分普通全切分长度为N的字符串有2n 1个全切分结果 例 太平洋保险保太平 太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平 太平洋保险保太平太平洋保险保太平 普通全切分是无用的 2n 1个结果中绝大多数是没有用的需要重新定义全切分 重定义切分 切分将一个字符串分为几个人类能理解的部分太平洋保险保太平假设这些部分是词典中的词 在2n 1个结果中选择 每一部分要么是词典中的词 要么长度为一 选择结果 太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平太平洋保险保太平 全切分问题 怎样生成结果怎样压缩时间和空间的复杂度 弧 系统使用户来表示一个切分部分Arc是相应的数据结构 typedefstructtagArcWW unsignedintuBegin unsignedintuEnd WordItem uCode UINTuCatThis ArcWW MemberofArc uBegin 弧的起点uEnd 弧的终点uCode 该切分单位在词典中的位置uCatThis 词性 在标注部分填入 使用弧 太平洋保险保太平弧表示为 太平洋保险保太平012345678 在数据结构中 全切分的弧表示 问题转换 对于一个字符串作全切分得到包含所有切分单位的弧集 词表结构 最大匹配项 为了提高效率 我们引入了最大匹配项的概念 太平洋保险保太平太平洋太平太 红色的是最大匹配项 词典词的最大匹配项 词典词的最大匹配项是词典中的词 最大匹配项是词的最大真前缀 不然的话最大匹配项为空 字符串S的最大匹配词 字符串S的最大匹配词是词典中的词最大匹配词是S的最大前缀 不然的话 最大匹配词是S的第一个词 分词 全切分生成所有可能的切分结果切分的结果是其中之一 生成正确的切分结果 在全切分结果中选择正确的一个 切分 全切分的工作 列举所有的歧义 切分 消歧 在全切分结果中选择正确的那一个 选择不同的切分算法 使用不同的切分策略 切分 全切分生成一个弧集不同的弧的组合表示不同的切分结果 太平洋保险保太平 最大正向 选择策略 自左到右都选择最长的候选项太平洋保险保太平 最大正向 最大正向算法中弧的定义 第一条最大正向弧的uBegin是0 第n 1条弧的uBegin是第n条弧的uEnd 最大正向弧是在所有uBegin相同的弧中uEnd最大的那条 最小正向 最小正向算法中弧的定义 第一条最小正向弧的uBegin是0 第n 1条弧的uBegin是第n条弧的uEnd 最大正向弧是在所有uBegin相同的弧中uEnd最小的那条 切分静止点 SSP SSP在每一个切分路径中都存在于两条弧之间 太平洋保险保太平012345678 切分静止点 SSP 全切分的结果是从字串头到尾 一些算法需要自尾到头的信息 最大逆向 选择策略 自右向左每次选择最长的候选项 太平洋保险保太平 最大逆向 最大逆向算法的弧定义 在两个SSP中的弧集称为切分静态弧集SegmentStaticArcSet SSAS 在一个SSAS中 第一条最大逆向弧的uEnd是尾SSP 第n 1条弧的uEnd是第n条弧的uBegin 在一个SSAS中 最后一条最大逆向弧的uBegin是头SSP 最大逆向弧是所有有相同的uEnd的弧中uBegin最小的那条 最小逆向 Choicepolicy 自右向左选择最小的候选项太平洋保险保太平 最小逆向 最小逆向算法弧的定义 在两个SSP中的弧集称为切分静态弧集SegmentStaticArcSet SSAS 在一个SSAS中 第一条最小逆向弧的uEnd是尾SSP 第n 1条弧的uEnd是第n条弧的uBegin 在一个SSAS中 最后一条最小逆向弧的uBegin是头SSP 最小逆向弧是所有有相同的uEnd的弧中uBegin最大的那条 最大概率 令S C1C2 Cn 1Cn C1 Cx1 Cx1 1 Cx2 Cxm 1 Cxm W1W2 Wm根据贝叶斯公式 P W C P W P C W P C P C 是确定值 P C W 是给定词串情况下字串出现的概率 可以认为是1 所以 P W C P W 最大概率 最大概率算法弧的定义 在两个SSP中的弧集称为切分静态弧集SegmentStaticArcSet SSAS 在一个SSAS中 第一条最大概率弧的uEnd是尾SSP 第n 1条弧的uEnd是第n条弧的uBegin 在一个SSAS中 最后一条最大概率弧的uBegin是头SSP 最大概率弧集是每条弧概率之积最大的那个弧集 最短路径 选择策略 选择含弧最少的结果太平洋保险保太平4arcs thesmallestnumofanarcchain 最短路径 最短路径算法的弧定义 在两个SSP中的弧集称为切分静态弧集SegmentStaticArcSet SSAS 在一个SSAS中 第一条最短路径弧的uEnd是尾SSP 第n 1条弧的uEnd是第n条弧的uBegin 在一个SSAS中 最后一条最短路径弧的uBegin是头SSP 最短路径弧集是拥有弧数最少的弧集 屈折语的词法分析 词 词根词缀词尾词法分析的工作 识别屈折变化 如take took takes派生变化 如morphology morphological复合变化 屈折语的词法分析技术 描述性的词法分析过程性的词法分析基于规则的词法分析 描述性的词法分析 为每个单词及其变型设置一个词典入口例如do PRES PR1 PR2 does PRES PR3 did PAST done VEN 相当于字典检索不适用于大词汇量的系统 过程性的词法分析 根据词的变形规律进行分析例 IFpreword的词尾为ied THEN把preword复制到word去掉word的词尾ied 并在word词尾加y如果能在词典中检索出word 则把PAST VEN的属性付给word 否则 IFpreword的词尾为ed THEN把preword复制到word去掉word的词尾ed如果能在词典中检索出word 则把PAST VEN的属性付给word 优点 减少了词典入口数量 提高辞典的检索速度缺点对于形态丰富的语言来说效率低 基于规则的词法分析 词的表层形式和深层形式Walk是深层形式Walks是表层形式词法分析就是寻找两者之间的映射 基于规则的词法分析 规则示例 名词复数 s PLUR es PLUR ies y PLUR 动词第三人称单数 s SINGULAR THIRDPERSON PRESENT es SINGULAR THIRDPERSON PRESENT ies y SINGULAR THIRDPERSON PRESENT 基于规则的词法分析 规则示例 动词现在分词 ing VING ing e VING ying ie VING ing VING 动词过去分词 过去式 ed PAST VEN ed e PAST VEN ied y PAST VEN ed PAST VEN 基于规则的词法分析 输入 一个单词输出 一个或多个单词 其中每个单词还原为原形加前后缀 可以有多个 算法 略 词法分析的分析程度 词干层 如 impossibilities impossibility ies词根层 如 impossibilities im poss ibil it ies分析程度取决于自然语言处理系统的深度 不解决未定义词 分析到词干层 解决未定义词 要分析到词根层