自然语言中的重要技术

分 类IRLAB 大 纲 自 然 语 言 中 的 重 要 技 术 决 策 树 最 大 熵 模 型 K近 邻 自 然 语 言 中 的 分 类 问 题 分 类 的 一 般 过 程 训 练 集 数 学 模 型 训 练 过 程 测 试 集 评 价 精 确 率 ， 宏 平 均 ， 微 平 均 本 课 介 绍 的 几 种 方 法 决 策 树 最 大 熵 模 型 K近 邻 决 策 树 简 介 决 策 树 表 示 法 决 策 树 学 习 的 适 用 问 题 基 本 的 决 策 树 学 习 算 法 决 策 树 学 习 中 的 假 想 空 间 搜 索 决 策 树 学 习 的 常 见 问 题 简 介 决 策 树 方 法 的 起 源 是 概 念 学 习 系 统 CLS，然 后 发 展 到 ID3方 法 而 为 高 潮 ， 最 后 又演 化 为 能 处 理 连 续 属 性 的 C4.5。 有 名 的决 策 树 方 法 还 有 CART和 Assistant。 是 应 用 最 广 的 归 纳 推 理 算 法 之 一 一 种 逼 近 离 散 值 目 标 函 数 的 方 法 对 噪 声 数 据 有 很 好 的 健 壮 性 且 能 学 习 析取 表 达 式 决 策 树 的 表 示 法 决 策 树 通 过 把 实 例 从 根 节 点 排 列 到 某 个叶 子 节 点 来 分 类 实 例 ， 叶 子 节 点 即 为 实例 所 属 的 分 类 。 树 上 的 每 一 个 节 点 说 明了 对 实 例 的 某 个 属 性 的 测 试 ， 并 且 该 节点 的 每 一 个 后 继 分 支 对 应 于 该 属 性 的 一个 可 能 值 图 表 达 式 决 策 树 学 习 的 适 用 问 题 实 例 是 由 属 性 -值 对 表 示 的 目 标 函 数 具 有 离 散 的 输 出 值 可 能 需 要 析 取 的 描 述 训 练 数 据 可 以 包 含 错 误 训 练 数 据 可 以 包 含 缺 少 属 性 值 的 实 例 属 性 选 择 构 造 好 的 决 策 树 的 关 键 在 于 如 何 选 择 好的 逻 辑 判 断 或 属 性 。 对 于 同 样 一 组 例 子 ，可 以 有 很 多 决 策 树 能 符 合 这 组 例 子 。 人们 研 究 出 ， 一 般 情 况 下 或 具 有 较 大 概 率地 说 ， 树 越 小 则 树 的 预 测 能 力 越 强 。 要构 造 尽 可 能 小 的 决 策 树 ， 关 键 在 于 选 择恰 当 的 逻 辑 判 断 或 属 性 。 由 于 构 造 最 小的 树 是 NP-难 问 题 ， 因 此 只 能 采 取 用 启发 式 策 略 选 择 好 的 逻 辑 判 断 或 属 性 。 用 熵 度 量 样 例 的 均 一 性 （ 纯 度 ） 熵 的 定 义 举 例 用 信 息 增 益 度 量 期 望 熵 最 低 举 例 ID3算 法创 建 树 的 Root结 点如 果 Examples都 为 正 ， 那 么 返 回 label=+中 的 单 结 点 Root如 果 Examples都 为 反 ， 那 么 返 回 lable=-单 结 点 树 Root如 果 Attributes为 空 ， 那 么 返 回 单 节 点 树 Root， lable=Examples中 最 普 遍 的 目 标 属 性 值否 则 开 始AAttributes中 分 类 能 力 最 好 的 属 性Root的 决 策 属 性 A对 于 每 个 可 能 值 在 Root下 加 一 个 新 的 分 支 对 应 测 试 A=vi 令 Example-vi为 Examples中 满 足 A属 性 值 为 vi的 子 集如 果 Examples-vi为 空在 这 个 新 分 支 下 加 一 个 叶 子 结 点 ， 节 点 的 lable=Examples中 最 普 遍 的 目 标 属 性 值否 则 在 这 个 新 分 支 下 加 一 个 子 树 ID3(example-vi,target-attribute,attributes-|A|结 束返 回 Root C4.5 C4.5是 对 ID3的 改 进 算 法 对 连 续 值 的 处 理 对 未 知 特 征 值 的 处 理 对 决 策 树 进 行 剪 枝 规 则 的 派 生 决 策 树 学 习 中 的 假 设 空 间 搜 索 假 设 空 间 ID3算 法 中 的 假 设 空 间 包 含 所 有 的 决 策树 当 遍 历 决 策 树 空 间 时 ， ID3仅 维 护 单 一的 当 前 假 设 。 基 本 的 ID3算 法 在 搜 索 中 不 进 行 回 溯 ID3算 法 在 搜 索 的 每 一 步 都 使 用 当 前 的所 有 训 练 样 例 决 策 树 学 习 的 常 见 问 题 (1) 避 免 过 度 拟 合 数 据 基 本 的 决 策 树 构 造 算 法 没 有 考 虑 噪 声 ， 生成 的 决 策 树 完 全 与 训 练 例 子 拟 合 。 有 噪 声情 况 下 ， 完 全 拟 合 将 导 致 过 分 拟 合（ overfitting） ， 即 对 训 练 数 据 的 完 全 拟 合反 而 不 具 有 很 好 的 预 测 性 能 。 解 决 方 法 剪 枝 是 一 种 克 服 噪 声 的 技 术 ， 同 时 它 也 能 使树 得 到 简 化 而 变 得 更 容 易 理 解 。 向 前 剪 枝 （ forward pruning） 向 后 剪 枝 （ backward pruning） 理 论 上 讲 ， 向 后 剪 枝 好 于 向 前 剪 枝 ， 但 计 算复 杂 度 大 。 剪 枝 过 程 中 一 般 要 涉 及 一 些 统 计参 数 或 阈 值 ， 如 停 机 阈 值 ； 有 人 提 出 了 一 种和 统 计 参 数 无 关 的 基 于 最 小 描 述 长 （ MDL） 的有 效 剪 枝 法 决 策 树 学 习 的 常 见 问 题 （ 2） 合 并 连 续 值 属 性 属 性 选 择 的 其 他 度 量 标 准 信 息 增 益 比 （ gain ratio） 、 Gini-index、 距 离 度 量 （ distance measure） 等 。 不 同 的 度 量 有 不 同 的 效 果 ， 特 别 是 对 于 多 值 属 性 。 决 策 树 学 习 的 常 见 问 题 （ 3） 处 理 缺 少 属 性 值 的 训 练 样 例 处 理 不 同 代 价 的 属 性 决 策 树 的 优 点 可 以 生 成 可 以 理 解 的 规 则 ； 计 算 量 相 对 来 说 不 是 很 大 ； 可 以 处 理 连 续 和 离 散 字 段 ； 决 策 树 可 以 清 晰 的 显 示 哪 些 字 段 比 较 重要 不 足 之 处 对 连 续 性 的 字 段 比 较 难 预 测 当 类 别 太 多 时 ， 错 误 可 能 会 增 加 的 比 较快 一 般 的 算 法 分 类 的 时 候 ， 只 是 根 据 一 个属 性 来 分 类 。 不 是 全 局 最 优 。 举 例 ： 利 用 决 策 树 进 行 文 本 分 类 最 大 熵 模 型 熵 定 量 的 描 述 事 物 的 不 确 定 性 设 随 机 变 量 ， 它 有 A1， A2， ， An共 n个可 能 的 结 局 ， 每 个 结 局 出 现 的 机 率 分 别 为p1,p2 ， .， pn， 则 的 不 确 定 程 度 ， 即 信 息熵 为 : 熵 越 大 ， 越 不 确 定 熵 等 于 0， 变 量 是 确 定 的 n ii ppH 1 log)( 最 大 熵 思 想 最 大 熵 思 想 由 来 已 久 ， Occam在 他 著 名 的Occam剃 刀 理 论 中 即 体 现 了 这 种 思 想 ， 对 最 大熵 理 论 的 系 统 论 述 出 现 在 上 世 纪 50年 代 中 期 ，由 E.T. Jaynes提 出 ， 其 原 理 的 基 本 思 想 是 ： 我们 从 全 部 相 容 的 分 布 预 测 中 挑 选 这 样 的 预 测 ，它 是 在 某 些 约 束 条 件 下 （ 通 常 是 给 定 的 某 些随 机 变 量 的 分 布 ） 使 信 息 熵 达 到 极 大 值 。 这是 因 为 信 息 熵 取 得 极 大 值 时 对 应 的 一 组 概 率分 布 出 现 的 概 率 占 绝 对 优 势 。 在 自 然 语 言 中 的 应 用 S.Pietra、 V.Pietra等 人 提 出 了 一 种 基 于 最 大 熵 原 理 的单 词 聚 类 方 法 ， 首 次 将 最 大 熵 理 论 应 用 于 自 然 语 言 处理 。 A.L.Berger、 S.Pietra、 V.Pietra等 人 比 较 详 细 地 介 绍 了最 大 熵 的 理 论 框 架 ， 并 介 绍 了 其 在 基 于 统 计 的 机 器 翻译 领 域 的 一 些 应 用 。 S.Abney在 统 计 属 性 -值 文 法 (Attribute-value Grammars)中 使 用 最 大 熵 进 行 参 数 估 计 。 李 涓 子 、 黄 昌 宁 改 进 了 最 大 熵 的 特 征 选 择 策 略 ， 并 将其 应 用 于 汉 语 的 词 义 消 歧 ， 取 得 了 较 好 的 效 果 A.Borthwick研 究 了 基 于 最 大 熵 的 名 实 体 (Named Entity)的 识 别 最 大 熵 模 型 已 知 训 练 样 本 集 (x1,y1),(x2,y2),(xN,yN),其 中 x为 输 入 ， y为 输 出 指 x出 现 的 情 况 下 ， y的 经 验 概 率 ， 也 就 是 y在 样 本 集 中 的 概 率 。 指 x出 现 的 情 况 下 ， y的 实 际 概 率 。 随 机 事 件 的 不 确 定 性 可 以 用 条 件 熵 来 衡 量 ： 特 征 指 x与 y之 间 存 在 的 某 种 特 定 关 系 ， 可 以 用 一 个 输 出 为 0或 1的 特 征 函 数 表 示 。 otherwise 0 book NP,n n if 1),( 的 核 心xxyyxf yx xypxypxppH , )|(log)|()()( 最 大 熵 模 型 特 征 的 经 验 概 率 为 所 有 满 足 特 征 要 求 的 (x,y)的 验 概 率之 和 ,即 ： 特 征 的 期 望 概 率 ,也 就 是 特 征 在 我 们 所 学 习 的 随 机 事 件中 的 真 实 分 布 为 ： yx yxfxypxpfp , ),()|()()( yx yxfxypxpfp , ),()|()()( 最 大 熵 模 型 选 定 的 特 征 的 重 要 性 可 通 过 下 式 体 现 ： 上 式 表 示 ， 特 征 f的 经 验 概 率 与 期 望 概 率 一 致 ，当 样 本 足 够 多 时 ， 可 信 度 高 的 特 征 的 经 验 概率 与 期 望 概 率 是 一 致 的 )()( fpfp yxyx yxfyxpyxfxypxp , ),(),(),()|()( 约 束 集 根 据 随 机 事 件 的 情 况 ， 约 束 等 式 可 以 有多 组 ， 约 束 等 式 的 集 合 叫 约 束 集 ， 可 表示 为 ),.2,1 , )()( nifpfpC ii 最 大 熵 模 型 最 大 熵 模 型 ， 是 满 足 约 束 集 条 件 的 所 有 模 型 中 熵 最 大 的 模 型 ，即 ： 其 中 p为 满 足 约 束 集 C条 件 的 某 一 统 计 模 型 。 因 为 约 束 集 中 的 每 一 个 特 征 的 分 布 是 最 大 似 然 估 计 ， 所 以 约 束集 中 元 素 越 多 ， 统 计 模 型 从 训 练 样 本 中 学 得 的 越 多 ， 其 做 出 的预 测 也 越 依 赖 于 样 本 集 。 选 择 特 征 较 多 时 ， 满 足 约 束 集 要 求 的统 计 模 型 个 数 较 少 ， 当 把 样 本 中 的 所 有 (x,y)都 作 为 特 征 时 ， 模型 唯 一 ， 为 用 极 大 似 然 估 计 求 p(y|x)所 建 立 的 模 型 。 )( maxarg* pHp 最 大 熵 模 型 求 解 最 大 熵 模 型 求 解 问 题 ， 实 质 是 一 个 约 束 条 件 下 求 极 值 的 问 题 。此 类 问 题 通 常 用 拉 格 朗 日 乘 子 法 确 定 。 其 中 ： i iii fpfppHp )()()(),( yx xypxypxppH , )|(log)|()()( yx yxfyxpfp , ),(),()( yx yxfxypxpfp , ),()|()()( 求 导 后 变 换 得 其 中 最 大 值 可 通 过 求 ),(exp()|( )(1 i iixZ yxfxyp y ii yxfxZ ),(exp()( )(maxarg * 没 有 解 析 解 ， Danroch 和 Rateliff于 1972年 提出 了 一 个 称 为 GIS(Generalized Iterative Scaling Algorithm)算 法 133。 D.Pietra等 改 进 了 原 有 的最 大 熵 模 型 求 解 算 法 ， 降 低 了 求 解 算 法 的 约束 条 件 ， 提 出 了 IIS(Improved Iterative Scaling Algorithm)算 法 ， 增 加 了 算 法 的 适 用 性 ， IIS算法 是 目 前 最 大 熵 参 数 求 解 中 的 常 用 算 法 。 * IIS算 法 IIS算 法 如 下 ： 输 入 ： 约 束 集 ， x， y的 经 验 概 率 分 布 输 出 ： 1、 初 始 令 ， 2、 for i=1 to n 循 环 a) 令 为 下 面 方 程 的 解其 中 ， 由 (3-3)对 f的 定 义 可 知 在 本 文 中 为 某 一 实 例 (x,y)包 含 的 特 征 数 量 。 b) c) 重 复 a)至 收 敛 3、 算 法 结 束 ),.2,1 , )()( nifpfpC ii ),( yxp* 0i ,.,2,1 nii yx iii fpyxfyxfxypxp, # )(),(exp(),()|()( ni i yxfyxf 1# ),(),( iii i n ,.,1* 这 里 求 解 使 用 牛 顿 迭 代 法 yx inin fpyxfayxfxypxpag , # )(),(exp(),()|()()( yx nn yxfafxypxpag , # ),(exp()|()()( 迭 代 算 法1 初 始 令 i=0, ai=023 当 , i+, 循 环 至 2，4 算 法 结 束 , 为 方 程 解 ， = 。)( )(1 iiag agii aa 某 一 较 小 常 数 |)()(| 1 ii agag ia iia 最 大 熵 统 计 模 型 的 优 点 最 大 熵 统 计 模 型 获 得 的 是 所 有 满 足 约 束条 件 的 模 型 中 信 息 熵 极 大 的 模 型 。 其 次 最 大 熵 统 计 模 型 可 以 灵 活 地 设 置 约束 条 件 。 通 过 约 束 条 件 的 多 少 可 以 调 节模 型 对 未 知 数 据 的 适 应 度 和 对 已 知 数 据的 拟 合 程 度 。 另 外 最 大 熵 模 型 还 自 然 地 解 决 了 统 计 模型 中 参 数 平 滑 的 问 题 。 K近 邻 （ KNN） 最 近 邻 分 类 规 则 对 于 测 试 样 本 点 x， 在 集 合 中 距 离 它 最 近 的的 x1。 最 近 邻 分 类 就 是 把 x分 为 x1 所 属 的 类别 最 近 邻 规 则 的 一 个 推 广 - KNN 没 有 好 的 相 似 度 矩 阵 不 能 用 KNN 方 法 目 标 ： 基 于 训 练 集 N的 对 y分 类 确 定 在 N中 与 y最 相 似 的 元 素 x 得 到 k个 最 相 似 的 集 合 设 n1,n2分 别 为 集 合 中 属 于 c1,c2的 个 数 如 果 p(c1|y)p(c2|y),判 为 c1,否 则 判 为 c2( ) ( , )MAX x Nsim y MAX sim x y max | ( , ) ( )A x N sim x y sim y 1 1( | ) 1 2np c y n n 2 2( | ) 1 2np c y n n 特 点 其 性 能 依 赖 于 相 似 度 矩 阵 效 率 问 题 Thanks!