PowerPoint Presentation

Transcription

1 计 算 语 言 学 第 4 讲 词 法 分 析 ( 一 ) 刘 群 中 国 科 学 院 计 算 技 术 研 究 所 liuqun@ict.ac.cn 中 国 科 学 院 研 究 生 院 2009 年 春 季 课 程 讲 义

2 内 容 提 要 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 2

3 内 容 提 要 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 3

4 内 容 提 要 语 言 的 分 类 曲 折 型 语 言 的 词 法 分 析 Tokenization Lemmatization 汉 语 重 叠 词 离 合 词 和 前 后 缀 的 处 理 汉 语 词 语 切 分 排 歧 汉 语 未 定 义 词 识 别 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 4

5 语 言 的 分 类 传 统 语 言 学 根 据 词 的 形 态 结 构 把 语 言 分 为 三 大 类 : 分 析 型 语 言 : 词 基 本 上 没 有 专 门 表 示 语 法 意 义 的 附 加 成 分, 形 态 变 化 很 少, 语 法 关 系 靠 词 序 和 虚 词 来 表 示 如 汉 语 黏 着 型 语 言 : 词 内 有 专 门 表 示 语 法 意 义 的 附 加 成 分, 一 个 附 加 成 分 表 达 一 种 语 法 意 义, 一 种 语 法 意 义 也 基 本 上 由 一 个 附 加 成 分 来 表 达, 词 根 或 词 干 跟 附 加 成 分 的 结 合 不 紧 密 如 芬 兰 语 日 语 蒙 古 语 等 屈 折 型 语 言 : 用 词 的 形 态 变 化 表 示 语 法 关 系, 一 个 形 态 成 分 可 以 表 示 若 干 种 不 同 的 语 法 意 义, 词 根 或 词 干 跟 词 的 附 加 成 分 结 合 得 很 紧 密, 往 往 不 易 截 然 分 开 如 : 英 语 德 语 和 法 语 等 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 5

6 屈 折 型 语 言 的 词 法 分 析 Tokenization: 把 字 符 串 变 成 词 串 I m a student. I m a student. Lemmatization(Stemming): 对 词 的 内 部 结 构 进 行 分 析 tokenization token + ~ize + ~tion takes take + ~s took take + ~ed POS-Tagging: 词 性 标 注 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 6

7 Tokenization 数 字 :123, % 3/8 11/20/2000 缩 略 ( 包 含 不 同 的 情 况 ): 字 母 - 点 号 - 字 母 - 点 号 组 成 的 序 列, 比 如 :U.S. i.e. 等 等 ; 字 母 开 头, 最 后 以 点 号 结 束, 比 如 :A. b. Mr. eds.prof. ; 包 含 非 字 母 字 符, 比 如 :AT&T Micro$oft 带 杠 的 词 串, 比 如 :three-year-old,one-third,socalled 带 瞥 号 的 词 串, 比 如 :I'm can't dog's let's 带 空 格 的 词 串, 比 如 :"and so on","ad hoc 其 他 : 如 网 址 ( 公 式 等 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 7

8 Tokenization 问 题 例 外 较 多, 跟 文 本 来 源 有 关 歧 义 现 象 ( 如 点 号 的 句 子 边 界 歧 义 ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 8

9 数 字 的 识 别 数 词 的 识 别 一 般 可 以 用 有 限 状 态 自 动 机 来 实 现 识 别 分 数 的 正 则 表 达 式 : [0-9]+ / [0-9]+ e.g. 12/21 识 别 百 分 数 的 正 则 表 达 式 : ([+ -])? [0-9]+ (. [0-9]* )? % e.g. -5.9% 91% 识 别 十 进 制 数 字 的 正 则 表 达 式 : ( [0-9]+(, )? )+ (. [0-9]+ )? e.g. 12,345 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 9

10 Tokenization 算 法 输 入 : 一 段 文 本 输 出 : 单 词 串 算 法 :( 略 ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 10

11 Lemmatization 屈 折 型 语 言 的 词 语 变 化 形 式 : 屈 折 变 化 : 即 由 于 单 词 在 句 子 中 所 起 的 语 法 作 用 的 不 同 而 发 生 的 词 的 形 态 变 化, 而 单 词 的 词 性 基 本 不 变 的 现 象, 如 ( take, took, takes) 识 别 这 种 变 化 是 词 法 分 析 的 最 基 本 的 任 务 派 生 变 化 : 即 一 个 单 词 从 另 外 一 个 不 同 类 单 词 或 词 干 衍 生 过 来, 如 morphological morphology, 英 语 中 派 生 变 化 主 要 通 过 加 前 缀 或 后 缀 的 形 式 构 成 ; 在 其 他 语 言 中, 如 德 语 和 俄 语 中, 同 时 还 伴 有 音 的 变 化 复 合 变 化 : 两 个 或 更 多 个 单 词 以 一 定 的 方 式 组 合 成 一 个 新 的 单 词 这 种 变 化 形 式 比 较 灵 活, 如 well-formed, 6- year-old 等 等 Lemmatization 的 目 的 : 将 上 述 变 化 还 原 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 11

12 Lemmatization 常 见 的 问 题 半 规 则 变 化 flied fly + ~ed rebelled rebel + ~ed 不 规 则 变 化 good, better, best child, children 歧 义 现 象 better good + ~er or well + ~er? works work + ~s or works? 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 12

13 Lemmatization 规 则 示 例 (1) 名 词 复 数 *s *, (PLUR) *es *, (PLUR) *ies *y, (PLUR) 动 词 第 三 人 称 单 数 *s * (SINGULAR) (THIRDPERSON) (PRESENT) *es * (SINGULAR) (THIRDPERSON) (PRESENT) *ies *y (SINGULAR) (THIRDPERSON) (PRESENT) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 13

14 Lemmatization 规 则 示 例 (2) 动 词 现 在 分 词 *ing * (VING) *ing *e (VING) *ying *ie (VING) *??ing *? (VING) 动 词 过 去 分 词 过 去 式 *ed * (PAST,VEN) *ed *e (PAST,VEN) *ied *y (PAST,VEN) *??ed *? (PAST,VEN) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 14

15 Lemmatization 算 法 输 入 : 一 个 单 词 输 出 : 一 个 或 多 个 单 词, 其 中 每 个 单 词 还 原 为 原 形 加 前 后 缀 ( 可 以 有 多 个 ) 算 法 :( 略 ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 15

16 Lemmatization 要 做 到 何 种 程 度 词 干 层 如 : impossibilities impossibility+ies 词 根 层 如 : impossibilities im+poss+ibil+it+ies 分 析 程 度 取 决 于 自 然 语 言 处 理 系 统 的 深 度 : 不 解 决 未 定 义 词, 分 析 到 词 干 层 解 决 未 定 义 词, 要 分 析 到 词 根 层 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 16

17 汉 语 词 法 分 析 所 面 临 的 问 题 重 叠 词 离 合 词 词 缀 汉 语 词 语 的 切 分 歧 义 汉 语 未 定 义 词 词 性 标 注 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 17

18 汉 语 双 字 形 容 词 的 重 叠 形 式 形 容 词 (AB) ABAB 式 AABB 式 A 里 AB 式 高 兴 高 兴 高 兴 高 高 兴 兴 明 白 明 白 明 白 明 明 白 白 热 闹 热 闹 热 闹 热 热 闹 闹 潇 洒 潇 洒 潇 洒 潇 潇 洒 洒 糊 涂 糊 糊 涂 涂 糊 里 糊 涂 流 气 流 里 流 气 粘 乎 粘 乎 粘 乎 粘 粘 乎 乎 凉 快 凉 快 凉 快 凉 凉 快 快 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 18

19 汉 语 单 字 形 容 词 的 重 叠 形 式 形 容 词 (A) AA 式 ABB 式 ABCD 式 黑 黑 黑 黑 压 压 黑 不 溜 秋 白 白 白 白 花 花 白 不 呲 咧 红 红 红 红 彤 彤 亮 亮 亮 亮 晶 晶 恶 恶 狠 狠 香 香 香 香 喷 喷 滑 滑 滑 滑 溜 溜 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 19

20 汉 语 双 字 动 词 的 重 叠 形 式 动 词 (AB) ABAB 式 AABB 式 研 究 研 究 研 究 讨 论 讨 论 讨 论 哆 嗦 哆 哆 嗦 嗦 唠 叨 唠 叨 唠 叨 唠 唠 叨 叨 嘀 咕 嘀 嘀 咕 咕 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 20

21 汉 语 单 字 动 词 的 重 叠 形 式 动 词 (V) VV 式 V 一 V 式 V 了 V 式 V 了 一 V 式 听 听 听 听 一 听 听 了 听 听 了 一 听 想 想 想 想 一 想 想 了 想 想 了 一 想 玩 玩 玩 玩 一 玩 玩 了 玩 玩 了 一 玩 醒 醒 醒 醒 一 醒 试 试 试 试 一 试 试 了 试 试 了 一 试 笑 笑 笑 笑 一 笑 笑 了 笑 笑 了 一 笑 讲 讲 讲 讲 一 讲 讲 了 讲 讲 了 一 讲 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 21

22 汉 语 其 他 词 类 的 重 叠 形 式 名 词 哥 哥, 人 人 山 山 水 水, 是 是 非 非, 方 方 面 面, 头 头 脑 脑 数 词 一 一 做 了 回 答, 两 两 结 伴 而 来 量 词 个 个 都 是 好 样 的, 回 回 考 满 分 副 词 常 常, 仅 仅, 的 的 确 确 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 22

23 汉 语 重 叠 词 的 特 点 汉 语 词 能 否 重 叠 具 有 很 强 的 个 性 特 点 研 究 研 究 工 作 工 作 有 些 词 重 叠 后 词 性 发 生 了 变 化 形 容 词 重 叠 后 一 般 成 为 状 态 词 个 别 量 词 重 叠 后 可 以 成 为 其 他 词 性 回 回 : 副 词 个 个 : 名 词 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 23

24 汉 语 词 缀 前 缀 老 鹰 老 虎 老 三 老 王 超 豪 华 超 标 准 超 高 速 非 党 员 后 缀 骨 头 砖 头 甜 头 苦 头 盼 头 想 头 桌 子 椅 子 孩 子 票 子 房 子 文 学 家 指 挥 家 艺 术 家 科 学 性 可 能 性 学 术 性 碗 儿 花 儿 玩 儿 份 儿 片 儿 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 24

25 汉 语 离 合 词 汉 语 动 词 存 在 离 合 词 现 象 游 泳 : 游 了 一 会 儿 泳 理 发 : 发 理 了 没 有 担 心 : 担 什 么 心 洗 澡 : 洗 了 个 热 水 澡 白 硕 的 解 释 : 语 义 重 心 偏 移 动 词 虚 化 ( 类 似 英 语 DO) 语 义 重 心 落 在 后 面 的 名 词 性 语 素 上 游 泳 : 游 了 一 会 儿 泳 :DO 了 一 会 儿 游 泳 理 发 : 发 理 了 没 有 : 理 发 DO 了 没 有 担 心 : 担 什 么 心 :DO 什 么 担 心 洗 澡 : 洗 了 个 热 水 澡 :DO 了 一 个 热 水 洗 澡 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 25

26 处 理 识 别 词 形 变 化 的 规 则 (1) VV -- v [ 重 叠 形 式 :VV] << V -- UVUV -- v [ 重 叠 形 式 :UVUV] << UV -- V 了 V -- v [ 重 叠 形 式 :V 了 V] << V -- V 一 V -- v [ 重 叠 形 式 :V 一 V] << V -- V 了 N -- v [ 重 叠 形 式 :V 了 N] << VN -- v [ 趋 向 动 词 : 否 VVN -- v [ 重 叠 形 式 :VVN] << VN -- V 过 N -- v [ 重 叠 形 式 :V 过 N] << VN -- v [ 趋 向 动 词 : 否 V 了 一 N -- v [ 重 叠 形 式 :V 了 一 N] << VN -- V 过 一 N -- v [ 重 叠 形 式 :V 过 一 N] << VN -- V 不 了 N -- v [ 重 叠 形 式 :V 不 了 N] << VN -- v 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 26

27 处 理 识 别 词 形 变 化 的 规 则 (2) AA -- a [ 重 叠 形 式 :AA] << A -- AABB -- a [ 重 叠 形 式 :AABB] << AB -- ABAB -- a [ 重 叠 形 式 :ABAB] << AB -- DD -- d [ 重 叠 形 式 :DD] << D -- R 俩 -- r << R 们 -- N 儿 -- n [ 重 叠 形 式 :N 儿 ] << N -- MN 儿 -- n [ 重 叠 形 式 :MN 儿 ] << MN -- n 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 27

28 汉 语 的 切 分 歧 义 交 集 型 歧 义 ( 交 叉 型 歧 义 ): 如 果 字 串 abc 既 可 切 分 为 ab/c, 又 可 切 分 为 a/bc 其 中 a,ab,c 和 bc 是 词 有 意 见 : 我 对 他 有 意 见 总 统 有 意 见 他 组 合 型 歧 义 ( 覆 盖 型 歧 义 ): 若 ab 为 词, 而 a 和 b 在 句 子 中 又 可 分 别 单 独 成 词 马 上 : 我 马 上 就 来 他 从 马 上 下 来 将 来 : 我 将 来 要 上 大 学 我 将 来 上 海 混 合 型 歧 义 : 由 交 集 型 歧 义 和 组 合 型 歧 义 自 身 嵌 套 或 两 者 交 叉 组 合 而 产 生 的 歧 义 人 才 能 : 这 样 的 人 才 能 经 受 住 考 验 人 才 能 : 这 样 的 人 才 能 经 受 住 考 验 人 才 能 : 这 样 的 人 才 能 经 受 住 考 验 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 28

29 交 集 型 歧 义 字 段 的 链 长 链 长 : 交 集 型 歧 义 字 段 中 含 有 交 集 字 段 的 个 数, 称 为 链 长 链 长 为 1: 和 尚 未 链 长 为 2: 结 合 成 分 链 长 为 3: 为 人 民 工 作 链 长 为 4: 中 国 产 品 质 量 结 合 成 分 子 时 链 长 为 6: 努 力 学 习 语 法 规 则 链 长 为 8: 治 理 解 放 大 道 路 面 积 水 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 29

30 真 歧 义 和 伪 歧 义 真 歧 义 确 实 能 在 真 实 语 料 中 发 现 多 种 切 分 形 式 比 如 应 用 于 地 面 积 伪 歧 义 虽 然 有 多 种 切 分 可 能 性, 但 在 真 实 语 料 中 往 往 取 其 中 一 种 切 分 形 式 比 如 挨 批 评 市 政 府 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 30

31 真 实 语 料 中 歧 义 字 段 的 分 布 刘 开 瑛,2000, 中 文 文 本 自 动 分 词 和 标 注, 商 务 印 书 馆, 第 65 页 (500 万 新 闻 语 料 的 统 计 结 果 ) 链 长 总 计 词 次 数 比 例 字 段 数 比 例 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 31

32 词 语 切 分 标 准 (1) 建 立 汉 语 词 语 切 分 标 准 的 必 要 性 汉 语 词 语 定 义 不 明 确 牛 肉 是 词, 鸡 肉 是 不 是? 打 倒 是 词, 打 死 打 伤 饿 死 涂 黑 是 不 是? 为 操 作 的 方 便, 必 须 确 定 统 一 的 标 准 或 规 范 采 用 分 词 单 位 的 说 法 问 题 取 舍 理 由 不 够 充 分, 人 为 色 彩 过 重 过 于 复 杂, 难 于 把 握 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 32

33 词 语 切 分 标 准 (2) 相 关 的 标 准 信 息 处 理 用 汉 语 分 词 规 范 GB/T , 中 国 标 准 出 版 社,1993 资 讯 处 理 用 中 文 分 词 规 范 台 湾 中 研 院 人 民 日 报 语 料 库 词 语 切 分 规 范 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 33

34 词 语 切 分 标 准 ( 例 ) (3) 人 民 日 报 标 注 语 料 库 词 语 切 分 规 范 ( 述 补 结 构 的 切 分 ) 未 收 入 词 典 的 双 音 节 述 补 结 构, 若 拆 开 各 是 一 个 词, 通 常 作 为 两 个 切 分 单 位 走 /v 到 /v, 撞 /v 上 /v, 调 /v 好 /a, 坐 /v 稳 /a 若 拆 开 了, 其 中 至 少 有 一 个 是 语 素, 通 常 就 不 切 分, 作 为 一 个 切 分 单 位 形 成 /v, 鼓 动 /v, 说 明 /v, 震 动 /v 双 音 节 的 述 补 结 构 中 间 插 入 得 或 不 一 般 应 予 切 分, 走 /v 得 /u 到 /v, 走 /v 不 /d 到 /v, 安 /v 得 /u 上 /v, 安 /v 不 /d 上 /v 但 是 如 果 去 掉 得 或 不 后, 前 后 两 个 字 不 构 成 一 个 词 的, 则 作 为 一 个 分 词 单 位 来 得 及 /v, 来 不 及 /v, 对 得 起 /v, 对 不 起 /v, 说 得 过 去 /l, 说 不 过 去 /l 有 的 去 掉 得 或 不 后 虽 然 是 一 个 合 成 词, 但 其 中 至 少 有 一 个 是 语 素, 拆 开 了 却 是 难 以 理 解 的, 仍 作 为 一 个 切 分 单 位 形 得 成 /v, 形 不 成 /v 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 34

35 未 定 义 词 的 类 型 汉 语 人 名 : 李 素 丽 老 张 李 四 王 二 麻 子 汉 语 地 名 : 定 福 庄 白 沟 三 义 庙 韩 村 河 马 甸 翻 译 人 名 : 乔 治 布 什 叶 利 钦 包 法 利 夫 人 翻 译 地 名 : 阿 尔 卑 斯 山 新 奥 尔 良 约 克 郡 机 构 名 : 方 正 公 司 联 想 集 团 国 际 卫 生 组 织 外 贸 部 商 标 字 号 : 非 常 可 乐 乐 凯 波 导 杉 杉 同 仁 堂 专 业 术 语 : 万 维 网 主 机 板 模 态 逻 辑 贝 叶 斯 算 法 缩 略 语 : 三 个 代 表 五 讲 四 美 打 假 扫 黄 打 非 计 生 办 新 词 语 : 卡 拉 OK 波 波 族 美 刀 港 刀 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 35

36 未 定 义 词 识 别 的 困 难 未 定 义 词 没 有 明 确 边 界 未 定 义 词 的 构 成 单 元 ( 汉 字 ) 本 身 都 可 以 独 立 成 词 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 36

37 未 定 义 词 识 别 的 依 据 内 部 构 成 规 律 ( 用 字 规 律 ) 外 部 环 境 ( 上 下 文 ) 重 复 出 现 规 律 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 37

38 未 定 义 词 识 别 的 研 究 进 展 较 成 熟 中 国 人 名 译 名 中 国 地 名 较 困 难 商 标 字 号 机 构 名 很 困 难 专 业 术 语 缩 略 语 新 词 语 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 38

39 中 国 人 名 的 内 部 构 成 规 律 (1) 在 汉 语 的 未 定 义 词 中, 中 国 人 名 是 规 律 性 最 强, 也 是 最 容 易 识 别 的 一 类 ; 中 国 人 名 一 般 由 以 下 部 分 组 合 而 成 : 姓 : 张 王 李 刘 诸 葛 西 门 范 徐 丽 泰 名 : 李 素 丽, 张 华 平, 王 杰 诸 葛 亮 前 缀 : 老 王, 小 李 后 缀 : 王 老, 赵 总 中 国 人 名 各 组 成 部 分 用 字 比 较 有 规 律 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 39

40 中 国 人 名 的 内 部 构 成 规 律 (2) 根 据 统 计, 汉 语 姓 氏 大 约 有 1000 多 个, 姓 氏 中 使 用 频 度 最 高 的 是 王 姓, 王, 陈, 李, 张, 刘 等 5 个 大 姓 覆 盖 率 达 32%, 姓 氏 频 度 表 中 的 前 14 个 高 频 度 的 姓 氏 覆 盖 率 为 50%, 前 400 个 姓 氏 覆 盖 率 达 99% 人 名 的 用 字 也 比 较 集 中 频 度 最 高 的 前 6 个 字 覆 盖 率 达 10.35%, 前 10 个 字 的 覆 盖 率 达 %, 前 15 个 字 的 覆 盖 率 达 %, 前 400 个 字 的 覆 盖 率 达 90% 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 40

41 中 国 人 名 的 内 部 构 成 规 律 (3) 中 国 人 名 各 组 成 部 分 的 组 合 规 律 姓 + 名 姓 名 前 缀 + 姓 姓 + 后 缀 姓 + 姓 + 名 ( 海 外 已 婚 妇 女 ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 41

42 中 国 人 名 的 上 下 文 构 成 规 律 身 份 词 : 前 : 工 人 教 师 影 星 犯 人 后 : 先 生 同 志 前 后 : 女 士 教 授 经 理 小 姐 总 理 地 名 或 机 构 名 : 前 : 静 海 县 大 丘 庄 禹 作 敏 的 字 结 构 前 : 年 过 七 旬 的 王 贵 芝 动 作 词 前 : 批 评, 逮 捕, 选 举 后 : 说, 表 示, 吃, 结 婚 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 42

43 中 国 人 名 识 别 的 难 点 一 些 高 频 姓 名 用 字 在 非 姓 名 中 也 是 高 频 字 姓 氏 : 于, 马, 黄, 张, 向, 常, 高 名 字 : 周 鹏 和 同 学, 周 鹏 和 同 学 人 名 内 部 相 互 成 词, 指 姓 与 名 名 与 名 之 间 本 身 就 是 一 个 已 经 被 收 录 的 词 [ 王 国 ] 维 [ 高 峰 ] [ 汪 洋 ] 张 [ 朝 阳 ] 人 名 与 其 上 下 文 组 合 成 词 这 里 [ 有 关 ] 天 培 的 壮 烈 ; 费 孝 通 向 人 大 常 委 会 提 交 书 面 报 告 人 名 地 名 冲 突 河 北 省 刘 庄 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 43

44 中 国 地 名 的 识 别 中 国 地 名 委 员 会 编 写 了 中 华 人 民 共 和 国 地 名 录, 收 集 了 全 国 乡 镇 以 上 ( 含 乡 镇 ) 各 级 行 政 区 域 的 名 称, 以 乡 镇 人 民 政 府 所 在 地 为 主 的 居 民 聚 落 名 称, 山 河 湖 海 岛 高 原 盆 地 沙 溪 等 自 然 地 理 实 体 名 称, 名 胜 古 迹 纪 念 地 古 遗 址 水 库 桥 梁 电 站 等 名 称 共 收 录 地 名 10 万 多 条 这 个 地 名 录 中 使 用 的 汉 字 共 2662 个, 频 度 最 高 的 前 65 个 汉 字 占 总 频 度 的 50.22%, 前 622 个 汉 字 占 总 频 度 的 90.01%, 前 1872 个 汉 字 占 总 频 度 的 99% 与 人 名 的 用 字 情 况 相 比 较, 地 名 用 字 分 散 得 多 地 名 内 部 也 有 一 定 的 结 构, 右 边 界 比 左 边 界 更 容 易 识 别 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 44

45 音 译 名 的 识 别 (1) 音 译 名 用 字 非 常 集 中 英 语 姓 名 译 名 手 册 中 共 收 英 语 姓 氏, 教 名 约 4 万 个, 经 计 算 机 统 计 得 出 英 语 姓 名 译 名 用 字 表 共 476 个 : 啊 阿 埃 艾 爱 昂 奥 巴 白 柏 拜 班 邦 包 保 堡 鲍 北 贝 倍 本 比 彼 边 别 滨 宾 玻 波 博 勃 伯 卜 布 采 蔡 藏 策 查 察 昌 彻 陈 楚 垂 茨 慈 次 聪 存 措 达 大 戴 代 丹 当 道 德 得 登 邓 迪 底 地 蒂 第 帝 丁 东 杜 敦 顿 多 厄 恩 耳 尔 法 凡 范 方 菲 费 芬 丰 冯 佛 夫 福 弗 辅 富 盖 甘 冈 高 哥 戈 葛 格 各 根 贡 古 顾 瓜 圭 郭 果 哈 海 罕 翰 汉 杭 豪 赫 黑 亨 洪 侯 胡 华 怀 惠 霍 基 吉 季 计 嘉 佳 加 贾 简 姜 焦 杰 捷 金 津 京 久 居 喀 卡 开 凯 坎 康 考 柯 科 可 克 肯 孔 扣 寇 库 夸 匡 奎 魁 坤 昆 阔 拉 腊 莱 来 赖 兰 朗 劳 勒 乐 雷 黎 理 李 里 礼 荔 丽 历 利 立 莲 连 廉 良 列 琳 林 霖 龄 留 刘 流 柳 龙 隆 卢 鲁 露 路 吕 略 伦 萝 罗 洛 玛 马 麦 迈 满 曼 芒 茅 梅 门 蒙 孟 米 密 敏 明 名 摩 莫 墨 默 姆 木 穆 拿 娜 纳 乃 奈 南 内 嫩 能 妮 尼 年 涅 宁 牛 纽 农 努 女 诺 欧 帕 派 潘 庞 培 佩 彭 蓬 皮 匹 平 泼 朴 普 漆 奇 齐 契 恰 钱 强 乔 切 钦 琴 青 琼 丘 邱 屈 让 热 仁 日 荣 茹 儒 瑞 若 撒 萨 塞 赛 三 缮 桑 瑟 森 莎 沙 珊 山 尚 绍 舍 申 生 盛 圣 施 诗 石 什 史 士 寿 舒 朔 斯 思 丝 松 孙 索 所 塔 泰 坦 汤 唐 陶 特 藤 提 惕 田 铁 汀 廷 亭 通 透 图 托 脱 娃 瓦 万 旺 威 韦 为 维 伟 魏 卫 温 文 翁 沃 乌 武 伍 西 锡 希 悉 席 霞 夏 显 香 向 晓 肖 歇 谢 欣 辛 兴 幸 姓 雄 休 修 雪 逊 雅 亚 延 扬 阳 尧 耀 耶 叶 依 易 意 因 英 永 尤 雨 约 宰 赞 早 泽 曾 扎 詹 湛 章 张 哲 者 珍 真 芝 知 智 治 朱 卓 兹 子 宗 祖 佐 丕 谟 葆 薇 岑 弼 娅 缪 珀 瑙 赉 滕 斐 熙 鸠 窦 艮 麟 黛 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 45

46 音 译 名 的 识 别 (2) 音 译 名 内 部 很 难 划 分 出 结 构, 但 有 一 些 常 见 音 节, 如 斯 基 斯 坦 等 不 同 语 言 的 音 译 规 律 不 尽 相 同, 如 法 语 俄 语 蒙 古 语 译 名 用 字 与 英 语 就 有 较 大 区 别 ( 蒙 语 人 名 举 例 : 那 顺 乌 日 图 青 格 勒 图 ), 如 果 按 不 同 的 语 言 训 练 不 同 的 模 型 可 能 会 比 使 用 统 一 的 模 型 效 果 更 好 音 译 名 可 以 是 人 名 地 名 或 其 他 专 名, 上 下 文 规 律 差 别 较 大 由 于 音 译 名 用 字 比 较 集 中, 识 别 正 确 率 较 高 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 46

47 机 构 名 的 内 部 构 成 规 律 (1) 机 构 名 一 般 都 是 定 中 结 构 机 构 名 的 后 缀 一 般 比 较 集 中, 识 别 相 对 容 易 机 构 名 左 边 界 识 别 非 常 困 难 机 构 名 中 含 有 大 量 的 人 名 地 名 企 业 字 号 等 专 有 名 称 在 这 些 专 有 名 称 中, 地 名 所 占 的 比 例 最 大, 其 中 未 登 录 地 名 又 占 了 相 当 一 部 分 的 比 例 所 以 机 构 名 识 别 应 在 人 名 地 名 等 其 他 专 名 识 别 之 后 进 行, 其 他 专 名 识 别 的 正 确 率 对 机 构 名 识 别 正 确 率 有 较 大 影 响 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 47

48 机 构 名 的 内 部 构 成 规 律 (2) 中 文 机 构 名 用 词 非 常 广 泛 通 过 对 人 民 日 报 1998 年 1 月 中 的 个 机 构 名 所 含 的 个 词 进 行 统 计, 共 计 27 种 词, 其 中 名 词 最 多 (9941 个 ), 地 名 其 次 (5023 个 ), 以 下 依 次 为 简 称 (1169 个 ) 专 有 名 词 (1125 个 ) 动 词 (848 个 ) 以 及 机 构 名 (714 个 ) 等 机 构 名 长 度 极 其 不 固 定 机 构 名 很 不 稳 定 随 着 社 会 发 展, 新 机 构 不 断 涌 现, 旧 机 构 不 断 被 淘 汰 改 组 或 更 名 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 48

49 内 容 提 要 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 49

50 内 容 提 要 汉 语 词 性 标 注 汉 语 词 性 的 特 点 词 的 兼 类 现 象 与 词 性 标 注 基 于 规 则 的 词 性 标 注 方 法 基 于 转 换 的 错 误 驱 动 的 词 性 标 注 方 法 基 于 隐 马 尔 科 夫 模 型 的 词 性 标 注 方 法 汉 语 词 法 分 析 系 统 的 集 成 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 50

51 关 于 汉 语 词 性 (1) 英 语 的 词 性 英 语 的 词 性 主 要 是 由 词 的 变 化 形 式 决 定 的 英 语 的 词 性 与 词 的 句 法 功 能 存 在 着 比 较 明 确 的 一 一 对 应 关 系 汉 语 的 词 性 汉 语 词 几 乎 没 有 形 态 变 化 汉 语 词 性 与 所 充 当 的 语 法 功 能 不 存 在 明 确 的 一 一 对 应 关 系 问 题 : 如 何 确 定 汉 语 的 词 性? 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 51

52 关 于 汉 语 词 性 (2) 问 题 1: 词 性 判 定 的 依 据 是 什 么? 句 法 功 能 语 义 金 银 铜 铁 锡 红 黑 紫 灰 粉 红 色 咖 啡 色 战 争 打 仗 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 52

53 关 于 汉 语 词 性 (3) 问 题 2: 同 一 个 词 在 充 当 不 同 句 子 成 分 时 词 性 是 否 发 生 变 化? 我 们 调 查 了 这 件 事 调 查 很 重 要 这 件 事 很 困 难 我 们 不 怕 困 难 去 是 有 道 理 的 暂 时 不 去 是 有 道 理 的 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 53

54 关 于 汉 语 词 性 (4) 问 题 1 的 答 案 : 词 性 判 定 的 依 据 只 能 是 句 法 功 能 ; 问 题 2 的 答 案 : 同 一 个 词 在 充 当 不 同 句 子 成 分 时 词 性 不 发 生 变 化 参 考 文 献 : 朱 德 熙, 语 法 答 问, 商 务 印 书 馆,1985 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 54

55 汉 语 词 性 标 记 集 几 个 典 型 的 词 性 标 记 集 北 京 大 学 人 民 日 报 语 料 库 标 记 集 清 华 大 学 汉 语 树 库 词 性 标 记 集 语 用 所 信 息 处 理 用 现 代 汉 语 词 类 及 词 性 标 记 集 规 范 宾 州 树 库 规 范 计 算 所 词 性 标 记 集 (V3.0) 参 考 : 词 性 标 记 集 对 照 表 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 55

56 词 的 兼 类 现 象 (1) 兼 类 数 兼 类 词 数 百 分 比 例 词 及 词 性 标 记 % 和 c-n-p-q-v % 光 a-d-n-v % 画 n-q-v % 锁 n-v 合 计 % 总 词 数 :55191 数 据 来 源 : 北 大 计 算 语 言 所 现 代 汉 语 语 法 信 息 词 典 1997 年 版 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 56

57 词 的 兼 类 现 象 (2) 兼 类 词 数 百 分 比 例 词 n-v % 爱 好, 把 握, 报 道 a-n 74 5% 本 分, 标 准, 典 型 a-v % 安 慰, 保 守, 抽 象 b-d 103 7% 长 期, 成 批, 初 步 n-q 64 4% 笔, 刀, 口 a-d 30 2% 大, 老, 真 合 计 % 兼 两 类 词 数 :1475 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 57

58 词 的 兼 类 现 象 (3) (English data, from Brown corpus) 引 自 : percent of the lexicon is ambiguous as to part-of-speech (types) 40 percent of the words in the Brown corpus are ambiguous (tokens) Degree of ambiguity Total frequency (39,440) tag 35, tags 4, , 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 58

59 词 性 标 注 (POS-Tagging) 语 法 体 系 词 性 标 记 集 的 确 定 一 词 多 类 现 象 Time flies like an arrow. Time/n-v-a flies/v-n like/p-v an/det arrow/n 把 这 篇 报 道 编 辑 一 下 把 /q-p-v-n 这 /r 篇 /q 报 道 /v-n 编 辑 /v-n 一 /m-c 下 /f-q-v 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 59

60 词 性 标 注 方 法 回 顾 序 号 作 者 / 标 注 项 目 标 记 集 方 法, 特 点 处 理 语 料 规 模 精 确 率 1 Klein&Simmons (1963) 2 TAGGIT (Greene&Rubin, 1971) 3 CLAWS (Marshall,1983; Booth, 1985) 4 VOLSUNGA (DeRose,1988) 5 Eric Brill's tagger ( ) 30 手 工 规 则 百 科 全 书 小 样 本 90% 86 人 工 规 则 (3300 条 ) Brown 语 料 库 77% 130 概 率 方 法 效 率 低 97 概 率 方 法 效 率 高 48 机 器 规 则 (447 条 ) 效 率 高 LOB 语 料 库 96% Brown 语 料 库 96% UPenn WSJ 语 料 库 97% 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 60

61 规 则 方 法 进 行 词 性 标 注 示 例 信 (n-v) CONDITION FIND(L,NEXT,X){%X.yx= 的 封 写 看 读 } SELECT n OTHERWISE SELECT 一 边 (c-s) CONDITION FIND(LR,FAR,X) {%X.yx = 一 边 } SELECT c OTHERWISE SELECT s 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 61

62 基 于 转 换 的 错 误 驱 动 的 词 性 标 注 方 法 Eric Brill (1992,1995) Transformation-based error-driven part of speech Tagging 基 于 转 换 规 则, 先 给 出 初 始 标 记, 然 后 不 断 修 正 有 监 督 的 学 习, 通 过 语 料 库 学 习 转 换 规 则 基 本 思 想 : (1) 正 确 结 果 是 通 过 不 断 修 正 错 误 得 到 的 (2) 修 正 错 误 的 过 程 是 有 迹 可 循 的 (3) 让 计 算 机 学 习 修 正 错 误 的 过 程, 这 个 过 程 可 以 用 转 换 规 则 (transformation) 形 式 记 录 下 来, 然 后 用 学 习 得 到 转 换 规 则 进 行 词 性 标 注 下 载 Brill s tagger: 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 62

63 转 换 规 则 的 学 习 流 程 C 0_raw 表 示 C 0 拿 掉 正 确 标 注 后 的 生 语 料 库 C 0 表 示 带 有 正 确 标 注 的 语 料 库 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 63

64 转 换 规 则 学 习 器 算 法 描 述 1) 首 先 用 初 始 标 注 器 对 C 0_raw 进 行 标 注, 得 到 带 有 词 性 标 记 的 语 料 C i (i =1); 2) 将 C i 跟 正 确 的 语 料 标 注 结 果 C 0 比 较, 可 以 得 到 C i 中 总 的 词 性 标 注 错 误 数, 并 根 据 规 则 模 板, 产 生 一 个 可 应 用 的 候 选 规 则 集 合 ; 3) 依 次 从 候 选 规 则 中 取 出 一 条 规 则 T m (m=1,2, ), 每 用 一 条 规 则 对 C i 中 的 词 性 标 注 结 果 进 行 一 次 修 改, 就 会 得 到 一 个 新 版 本 的 语 料 库, 不 妨 记 做 C im (m=1,2,3, ), 将 每 个 C i m 跟 C 0 比 较, 可 计 算 出 每 个 C i m 中 的 词 性 标 注 错 误 数 假 定 其 中 错 误 数 最 少 的 那 个 是 C ij ( 且 C i j 中 的 错 误 数 少 于 C i 中 的 错 误 数 ), 产 生 它 的 规 则 T j 就 是 这 次 学 习 得 到 的 转 换 规 则 ; 此 时 C i j 成 为 新 的 待 修 改 语 料 库, 即 C i+1 = C ij 4) 重 复 第 3 步 的 操 作, 得 到 一 系 列 的 标 注 语 料 库 C 2k, C 3l, C 4m, 后 一 个 语 料 库 中 的 标 注 错 误 数 都 少 于 前 一 个 中 的 错 误 数, 每 一 次 都 学 习 到 一 条 令 错 误 数 降 低 最 多 的 转 换 规 则 直 至 运 用 所 有 规 则 后, 都 不 能 降 低 错 误 数, 学 习 过 程 结 束 这 时 得 到 一 个 有 序 的 转 换 规 则 集 合 {T a, T b, T c, } 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 64

65 转 换 规 则 的 形 式 转 换 规 则 由 两 部 分 组 成 改 写 规 则 (rewriting rule) 激 活 环 境 (triggering environment) 一 个 例 子 : 转 换 规 则 T 1 改 写 规 则 : 将 一 个 词 的 词 性 从 动 词 (v) 改 为 名 词 (n); 激 活 环 境 : 该 词 左 边 第 一 个 紧 邻 词 的 词 性 是 量 词 (q), 第 二 个 词 的 词 性 是 数 词 (m) S0: 他 /r 做 /v 了 /u 一 /m 个 /q 报 告 /v 运 用 T 1 S1: 他 /r 做 /v 了 /u 一 /m 个 /q 报 告 /n 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 65

66 转 换 规 则 的 模 板 (template) 改 写 规 则 : 将 词 性 标 记 x 改 写 为 y 激 活 环 境 : (1) 当 前 词 的 前 ( 后 ) 面 一 个 词 的 词 性 标 记 是 z;(2) 当 前 词 的 前 ( 后 ) 面 第 二 个 词 的 词 性 标 记 是 z; (3) 当 前 词 的 前 ( 后 ) 面 两 个 词 中 有 一 个 词 的 词 性 标 记 是 z; 其 中 x,y,z 是 任 意 的 词 性 标 记 代 码 规 则 模 板 决 定 了 所 有 可 能 的 规 则 构 成 的 一 个 规 则 空 间, 规 则 模 板 定 义 的 好 坏, 直 接 影 响 最 终 系 统 的 性 能 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 66

67 根 据 模 板 可 能 学 到 的 转 换 规 则 T 1 : 当 前 词 的 前 一 个 词 的 词 性 标 记 是 量 词 (q) 时, 将 当 前 词 的 词 性 标 记 由 动 词 (v) 改 为 名 词 (n); T 2 : 当 前 词 的 后 一 个 词 的 词 性 标 记 是 动 词 (v) 时, 将 当 前 词 的 词 性 标 记 由 动 词 (v) 改 为 名 词 (n); T 3 : 当 前 词 的 后 一 个 词 的 词 性 标 记 是 形 容 词 (a) 时, 将 当 前 词 的 词 性 标 记 由 动 词 (v) 改 为 名 词 (n); T 4 : 当 前 词 的 前 面 两 个 词 中 有 一 个 词 的 词 性 标 记 是 名 词 (n) 时, 将 当 前 词 的 词 性 标 记 由 形 容 词 (v) 改 为 数 词 (m); 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 67

68 词 性 标 注 的 统 计 方 法 寻 找 最 优 路 径 =96 种 可 能 性, 哪 种 可 能 性 最 大? 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 68

69 隐 马 尔 科 夫 模 型 - 假 设 对 于 一 个 随 机 事 件, 有 一 个 观 察 值 序 列 :O 1,...,O T 该 事 件 隐 含 着 一 个 状 态 序 列 :X 1,...,X T 假 设 1: 马 尔 可 夫 假 设 ( 状 态 构 成 一 阶 马 尔 可 夫 链 ) p(x i X i-1 X 1 ) = p(x i X i-1 ) 假 设 2: 不 动 性 假 设 ( 状 态 与 具 体 时 间 无 关 ) p(x i+1 X i ) = p(x j+1 X j ), 对 任 意 i,j 成 立 假 设 3: 输 出 独 立 性 假 设 ( 输 出 仅 与 当 前 状 态 有 关 ) p(o 1,...,O T X 1,...,X T ) = Π p(o t X t ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 69

70 隐 马 尔 科 夫 模 型 - 图 示 X 1 X 2 X T O 1 O 2 O T 状 态 转 移 观 察 值 输 出 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 70

71 隐 马 尔 科 夫 模 型 - 定 义 一 个 隐 马 尔 可 夫 模 型 (HMM) 是 一 个 五 元 组 : 其 中 : (ΩX, ΩO, A, B, π ) ΩX = {q1,...qn}: 状 态 的 有 限 集 合 ΩO = {v1,...,vm}: 观 察 值 的 有 限 集 合 A = {aij},aij = p(xt+1 = qj Xt = qi): 转 移 概 率 B = {bik},bik = p(ot = vk Xt = qi): 输 出 概 率 π = {πi}, πi = p(x1 = qi): 初 始 状 态 分 布 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 71

72 隐 马 尔 科 夫 模 型 - 问 题 令 λ= {A,B,π} 为 给 定 HMM 的 参 数, 令 σ = O 1,...,O T 为 观 察 值 序 列, 隐 马 尔 可 夫 模 型 (HMM) 的 三 个 基 本 问 题 : 1. 评 估 问 题 : 对 于 给 定 模 型, 求 某 个 观 察 值 序 列 的 概 率 p(σ λ) ;( 语 言 模 型 ) 2. 解 码 问 题 : 对 于 给 定 模 型 和 观 察 值 序 列, 求 可 能 性 最 大 的 状 态 序 列 ; 3. 学 习 问 题 : 对 于 给 定 的 一 个 观 察 值 序 列, 调 整 参 数 λ, 使 得 观 察 值 出 现 的 概 率 p(σ λ) 最 大 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 72

73 隐 马 尔 科 夫 模 型 - 算 法 评 估 问 题 : 向 前 算 法 定 义 向 前 变 量 采 用 动 态 规 划 算 法, 复 杂 度 O(N 2 T) 解 码 问 题 : 韦 特 比 (Viterbi) 算 法 采 用 动 态 规 划 算 法, 复 杂 度 O(N 2 T) 学 习 问 题 : 向 前 向 后 算 法 EM 算 法 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 73

74 隐 马 尔 科 夫 模 型 - 例 子 假 设 : 某 一 时 刻 只 有 一 种 疾 病, 且 只 依 赖 于 上 一 时 刻 疾 病 一 种 疾 病 只 有 一 种 症 状, 且 只 依 赖 于 当 时 的 疾 病 症 状 ( 观 察 值 ): 发 烧, 咳 嗽, 咽 喉 肿 痛, 流 涕 疾 病 ( 状 态 值 ): 感 冒, 肺 炎, 扁 桃 体 炎 转 移 概 率 : 从 一 种 疾 病 转 变 到 另 一 种 疾 病 的 概 率 输 出 概 率 : 某 一 疾 病 呈 现 出 某 一 症 状 的 概 率 初 始 分 布 : 初 始 疾 病 的 概 率 解 码 问 题 : 某 人 症 状 为 : 咳 嗽 咽 喉 痛 流 涕 发 烧 请 问 : 其 疾 病 转 化 的 最 大 可 能 性 如 何? 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 74

75 隐 马 尔 科 夫 模 型 - 例 子 ( 续 ) 转 移 概 率 感 冒 肺 炎 扁 桃 体 炎 感 冒 肺 炎 扁 桃 体 炎 输 出 概 率 发 烧 咳 嗽 咽 喉 痛 流 涕 感 冒 肺 炎 扁 桃 体 炎 初 始 分 布 感 冒 肺 炎 扁 桃 体 炎 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 75

76 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 76 HMM 评 估 问 题 = = = = = = = X O X T i X X O X X X T i O X T i X X X X X i i i i i i i i b a b b a X O P X P X O P O P ) ( ) )( ( ), ( ) ( ), ( ) ( π π λ λ λ λ 可 能 的 状 态 序 列 有 N T 种 可 能 性, 计 算 复 杂 度 极 高 评 估 问 题 : 对 于 给 定 模 型, 求 某 个 观 察 值 序 列 的 概 率 p(σ λ) ;( 语 言 模 型 )

77 HMM 评 估 问 题 - 向 前 算 法 (1) 定 义 前 向 变 量 为 HMM 在 时 间 t 输 出 序 列 O 1 O t, 并 且 位 于 状 态 X t 的 概 率 : α ( i ) = P( O1 O, X = q λ) t t t i 初 始 化 : 迭 代 公 式 为 : α ( i ) = π b i α 1 io t 1 N = i= ( j) α t ( i) aij b jot+ 1 最 终 结 果 为 : N P O λ) = i= 1 ( α ( i ) T 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 77

78 HMM 评 估 问 题 - 向 前 算 法 (2) α t (1) q 1 a 1j α t (2) q 2 a 2j q j α t+1 (j) a nj α t (n) q n 时 间 t 时 间 t+1 向 前 算 法 的 时 间 复 杂 度 :O(N 2 T) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 78

79 HMM 评 估 问 题 - 向 后 算 法 (1) 定 义 后 向 变 量 为 HMM 在 时 间 t 并 且 位 于 状 态 X t 的 情 况 下, 输 出 序 列 O t+1 O T,: β ( i ) = P( O + 1 O, X = q λ) t t T t i 初 始 化 : β T ( i) = 1 迭 代 公 式 为 : N β () i = a b ( j) β t t ij jo t j= 1 最 终 结 果 为 : P( O λ) = N i= 1 π b i io 1 β1 ( i) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 79

80 HMM 评 估 问 题 - 向 后 算 法 (2) a i1 q 1 β t+1 (1) β t (i) q i a i2 q 2 β t+1 (2) a in q n 时 间 t 时 间 t+1 β t+1 (n) 向 后 算 法 的 时 间 复 杂 度 :O(N 2 T) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 80

81 HMM 解 码 问 题 解 码 问 题 : 对 于 给 定 模 型 λ 和 观 察 值 序 列 O, 求 可 能 性 最 大 的 状 态 序 列 X; X * = arg max X P( X O, λ ) 如 果 要 枚 举 所 有 的 状 态 序 列, 时 间 复 杂 度 是 O(N T ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 81

82 HMM 解 码 问 题 -Viterbi 算 法 (1) 定 义 Viterbi 变 量 为 HMM 在 时 间 t 沿 着 某 一 条 路 径 到 达 状 态 q i, 且 输 出 观 察 值 O 1 O 2 O i 的 最 大 概 率 δ t ( i) = max P( X 1X 2... X t = qi, O1O 2 X X 2... X i O t λ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 82

83 HMM 解 码 问 题 -Viterbi 算 法 (2) 初 始 化 δ 1( i) = π i bio 1 迭 代 计 算 2 t T 1 j N 取 最 优 路 径 回 溯 2 t T δ ( j) = t Ψ p q t * * T ( j) = 1 i N max[ δ 1 i N 1 i N t 1 ( i) a arg max[ δ = max[ δ ( i)] 1 i N T T t 1 = arg max[ δ ( i)] * q 1( * t = Ψ t + qt+ 1) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 83 ij ] b j O ( i) a ij t ] b j O t

84 HMM 解 码 问 题 -Viterbi 算 法 (3) Viterbi 算 法 的 时 间 复 杂 度 :O(N 2 T) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 84

85 HMM 学 习 问 题 已 知 观 察 序 列 O=O 1 O 2 O T 估 计 λ 的 参 数 :π i, a ij, b ik 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 85

86 HMM 学 习 问 题 - 最 大 似 然 估 计 已 知 观 察 序 列 O 对 应 的 状 态 序 列 为 ( 有 指 导 学 习 ): X=X 1 X 2 X T 采 用 最 大 似 然 估 计 : π i = δ ( X 1, qi ) a b ij jk X中 从 状 态 q 转 移 到 状 态 q 的 次 数 i j t= 1 t i t+ 1 = = T 1 X中 从 状 态 qi转 移 另 一 状 态 ( 含 q j) 的 次 数 δ ( X, ) t= 1 t qi X中 从 状 态 q 其 中 δ ( x, y) 输 出 到 状 态 v 的 次 数 1, 如 果 x = y = 0, 如 果 x y j k t= 1 t j = = T X中 到 达 状 态 q j次 数 δ ( t= 1 T δ ( X, q T 1 δ ( X, q ) δ (O, v X t, q j ) t ) δ ( X k ), q j ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 86

87 HMM 学 习 问 题 -Baum-Welch 算 法 (1) 不 知 道 O 对 应 的 状 态 序 列 : 无 指 导 学 习 采 用 Baum-Welch( 又 称 向 前 向 后 算 法 ) 是 EM(Expectation-Maximization) 算 法 的 一 种 实 现 初 试 化 :λ 0 EM 步 骤 : 循 环 执 行 以 下 步 骤, 直 到 λ i 收 敛 E- 步 骤 : 根 据 λ i 计 算 所 有 可 能 的 状 态 序 列 M- 步 骤 : 根 据 状 态 序 列 和 输 出 序 列 估 计 参 数 λ i+1 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 87

88 HMM 学 习 问 题 -Baum-Welch 算 法 (2) 初 试 化 : 随 机 给 π i, a ij, b jk 赋 初 始 值 需 要 满 足 以 下 归 一 化 约 束 : N i = 1 π i = 1 N j = 1 a ij = 1, 对 于 1 i N N k = 1 b jk = 1, 对 于 1 j N 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 88

89 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 89 HMM 学 习 问 题 -Baum-Welch 算 法 (3) E- 步 骤 : 已 知 观 察 序 列 O 1 O 2 O T 和 模 型 参 数 π i, a ij, b jk, 估 计 : 在 时 间 t 和 t+1 分 别 位 于 状 态 q i,q j 的 概 率 : = = = = = = = N i N j t O j ij t t O j ij t t O j ij t j t i t t j b a i j b a i O P j b a i O P O q X q X P j i t t t ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ),, ( ), ( β α β α λ β α λ λ ξ 在 时 间 t 位 于 状 态 q i 的 概 率 : = = N i t i j i 1 ), ( ξ γ

90 HMM 学 习 问 题 -Baum-Welch 算 法 (4) ξ t (i, j) 的 计 算 使 用 了 前 向 变 量 和 后 向 变 量 : α t (1) q 1 α t (i) β t+1 (j) q 1 β t+1 (1) α t (2) q 2 q j q i q 2 β t+1 (2) a ij b jot+1 α t (n) q n q n β t+1 (n) 时 间 t 时 间 t+1 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 90

91 HMM 学 习 问 题 -Baum-Welch 算 法 (5) M- 步 骤 : 已 知 ξ t (i, j) 和 γ t (i), 估 计 模 型 λ: π i = X 为 qi的 概 率 = γ 1( 1 i ) a b ij jk X中 从 状 态 q 转 移 到 状 态 q 的 次 数 T t= i j 1 t = = T 1 X中 从 状 态 qi转 移 另 一 状 态 ( 含 q j) 的 次 数 t= 1 X中 从 状 态 q 输 出 到 观 察 值 v 的 次 数 j k t= 1 = = T X中 到 达 状 态 q j次 数 t= 1 T 1 ξ ( i, γ ( i) γ ( j) t j) γ ( j) δ (O, v k ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 91

92 HMM 学 习 问 题 -Baum-Welch 算 法 (5) 迭 代 终 止 条 件 : log P( O λ i+ 1) log P( O λi ) < ε ε 是 事 先 给 定 的 阈 值 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 92

93 HMM 学 习 问 题 -Baum-Welch 算 法 (6) Baum-Welch 算 法 只 能 达 到 局 部 最 优 Baum-Welch 算 法 的 结 果 依 赖 于 初 始 值 的 设 定 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 93

94 隐 马 尔 科 夫 模 型 - 应 用 语 音 识 别 音 字 转 换 词 性 标 注 (POS Tagging) 组 块 分 析 基 因 分 析 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 94

95 隐 马 尔 科 夫 模 型 - 资 源 Rabiner, L. R., A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, vol. 77, no. 2, Feb. 1989, pgs There is a lot of notation but verbose explanations accompany. HTK:HMM Toolkit Hidden Markov Model (HMM) White Paper (GeneMatcher) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 95

96 隐 马 尔 科 夫 模 型 - 总 结 HMM 模 型 可 以 看 作 一 种 特 定 的 Bayes Net HMM 模 型 等 价 于 概 率 正 规 语 法 或 概 率 有 限 状 态 自 动 机 HMM 模 型 可 以 用 一 种 特 定 的 神 经 网 络 模 型 来 模 拟 优 点 : 研 究 透 彻, 算 法 成 熟, 效 率 高, 效 果 好, 易 于 训 练 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 96

97 基 于 HMM 进 行 词 性 标 注 (1) 把 词 汇 序 列 ( 记 做 W=w 1 w 2 w n ) 理 解 为 观 察 值 把 词 性 标 注 序 列 ( 记 做 T=t 1 t 2 t n ) 理 解 为 隐 含 的 状 态 值 词 性 标 注 问 题 变 成 HMM 中 的 解 码 问 题 已 知 词 串 W( 观 察 序 列 ) 和 模 型 λ 情 况 下, 求 使 得 条 件 概 率 P(T W, λ) 值 最 大 的 那 个 T, 一 般 记 做 : T ' = arg max P( T T W, λ) 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 97

98 基 于 HMM 进 行 词 性 标 注 (2) 利 用 Bayes 公 式, 可 以 进 一 步 分 解 为 : argmax P( T T W ) = arg max P( T) P( W T) 其 中 : P( T ) = P( t1 t0 ) P( t2 t1, t0 )... P( t i ti 1, ti 2,...) 根 据 HMM 假 设, 可 得 P( T ) P( t1 t0 ) P( t2 t1)... P( t i ti 1) T 词 性 之 间 的 转 移 概 率 可 以 从 语 料 库 中 估 算 得 到 : P( t i t 1) i = 训 练 语 料 中 ti出 现 在 ti 1之 后 的 次 数 训 练 语 料 中 t 出 现 的 总 次 数 i 1 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 98

99 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 99 基 于 HMM 进 行 词 性 标 注 (3) ),...,,,,..., ( )...,, ( ) ( ) ( w w w t t t w P w t t w P t w P T W P i i i i i = P(W T) 是 已 知 词 性 标 记 串, 产 生 词 串 的 条 件 概 率 : 根 据 HMM 假 设, 上 面 公 式 可 简 化 为 : 已 知 词 性 标 记 下 输 出 词 语 的 概 率 可 以 从 语 料 库 中 统 计 得 到 : 训 练 语 料 中 出 现 的 总 次 数 的 词 性 被 标 记 为 的 次 数 训 练 语 料 中 i i i i i t t w t w P ) ( ) ( )... ( ) ( ) ( i w i t P t w P t w P T W P

100 基 于 HMM 进 行 词 性 标 注 示 例 把 /? 这 /? 篇 /? 报 道 /? 编 辑 /? 一 /? 下 /? 把 /q-p-v-n 这 /r 篇 /q 报 道 /v-n 编 辑 /v-n 一 /m-c 下 /f-q-v P(T1 W) = P(q $)P( 把 q)p(r q)p( 这 r) P(f m)p( 下 f) P(T2 W) = P(q $)P( 把 q)p(r q)p( 这 r) P(q m)p( 下 q) P(T3 W) = P(q $)P( 把 q)p(r q)p( 这 r) P(v m)p( 下 v) P(T96 W) = P(n $)P( 把 n)p(r q)p( 这 r) P(v c)p( 下 v) 从 中 选 一 个 最 大 值 词 性 转 移 概 率 词 语 输 出 概 率 计 算 语 言 学 讲 义 (04) 词 法 分 析 ( 一 ) 100