数学之美系列二十一 － 布隆过滤器（Bloom Filter）

Transcription

1 数 学 之 美 & 浪 潮 之 巅 吴 军 Google 研 究 院 2008 年 12 月 30 日 整 理 I

2 目 录 1. 数 学 之 美 数 学 之 美 系 列 一 统 计 语 言 模 型 数 学 之 美 系 列 二 谈 谈 中 文 分 词 数 学 之 美 系 列 三 隐 含 马 尔 可 夫 模 型 在 语 言 处 理 中 的 应 用 数 学 之 美 系 列 四 怎 样 度 量 信 息? 数 学 之 美 系 列 五 简 单 之 美 : 布 尔 代 数 和 搜 索 引 擎 的 索 引 数 学 之 美 系 列 六 图 论 和 网 络 爬 虫 (Web Crawlers) 数 学 之 美 系 列 七 信 息 论 在 信 息 处 理 中 的 应 用 数 学 之 美 系 列 八 贾 里 尼 克 的 故 事 和 现 代 语 言 处 理 数 学 之 美 系 列 九 如 何 确 定 网 页 和 查 询 的 相 关 性 数 学 之 美 系 列 十 有 限 状 态 机 和 地 址 识 别 数 学 之 美 系 列 十 一 Google 阿 卡 47 的 制 造 者 阿 米 特. 辛 格 博 士 数 学 之 美 系 列 十 二 余 弦 定 理 和 新 闻 的 分 类 数 学 之 美 系 列 十 三 信 息 指 纹 及 其 应 用 数 学 之 美 系 列 十 四 谈 谈 数 学 模 型 的 重 要 性 数 学 之 美 系 列 十 五 繁 与 简 自 然 语 言 处 理 的 几 位 精 英 数 学 之 美 系 列 十 六 ( 上 ) 不 要 把 所 有 的 鸡 蛋 放 在 一 个 篮 子 里 - 谈 谈 最 大 熵 模 型 数 学 之 美 系 列 十 六 ( 下 ) 不 要 把 所 有 的 鸡 蛋 放 在 一 个 篮 子 里 - 最 大 熵 模 型 数 学 之 美 系 列 十 七 闪 光 的 不 一 定 是 金 子 -- 谈 谈 搜 索 引 擎 作 弊 问 题 (Search Engine Anti-SPAM) 数 学 之 美 系 列 十 八 矩 阵 运 算 和 文 本 处 理 中 的 分 类 问 题 数 学 之 美 系 列 十 九 马 尔 可 夫 链 的 扩 展 贝 叶 斯 网 络 (Bayesian Networks) 数 学 之 美 系 列 二 十 自 然 语 言 处 理 的 教 父 -- 马 库 斯 数 学 之 美 系 列 二 十 一 布 隆 过 滤 器 (Bloom Filter) 数 学 之 美 系 列 二 十 二 由 电 视 剧 暗 算 所 想 到 的 - 谈 谈 密 码 学 的 数 学 原 理 数 学 之 美 系 列 二 十 三 输 入 一 个 汉 字 需 要 敲 多 少 个 键 - 谈 谈 香 农 第 一 定 律 数 学 之 美 系 列 二 十 四 从 全 球 导 航 到 输 入 法 - 谈 谈 动 态 规 划 浪 潮 之 巅 浪 潮 之 巅 第 一 章 帝 国 的 余 辉 (AT&T)( 一 ) 浪 潮 之 巅 第 一 章 帝 国 的 余 辉 (AT&T)( 二 ) I

3 目 录 2.3. 浪 潮 之 巅 第 一 章 帝 国 的 余 辉 (AT&T)( 三 ) 浪 潮 之 巅 第 一 章 帝 国 的 余 辉 (AT&T)( 四 ) 浪 潮 之 巅 第 二 章 蓝 色 巨 人 (IBM)( 一 ) 浪 潮 之 巅 第 二 章 蓝 色 巨 人 (IBM)( 二 ) 浪 潮 之 巅 第 二 章 蓝 色 巨 人 (IBM)( 三 ) 浪 潮 之 巅 第 二 章 蓝 色 巨 人 (IBM)( 四 ) 浪 潮 之 巅 第 二 章 蓝 色 巨 人 (IBM)( 五 ) 浪 潮 之 巅 第 二 章 蓝 色 巨 人 (IBM)( 六 ) 浪 潮 之 巅 第 三 章 水 果 公 司 的 复 兴 ( 乔 布 斯 和 苹 果 公 司 )( 一 ) 浪 潮 之 巅 第 三 章 水 果 公 司 的 复 兴 ( 乔 布 斯 和 苹 果 公 司 )( 二 ) 浪 潮 之 巅 第 三 章 水 果 公 司 的 复 兴 ( 乔 布 斯 和 苹 果 公 司 )( 三 ) 浪 潮 之 巅 第 三 章 " 水 果 " 公 司 的 复 兴 ( 乔 布 斯 和 苹 果 公 司 )( 四 ) 浪 潮 之 巅 第 四 章 计 算 机 工 业 的 生 态 链 ( 一 ) 浪 潮 之 巅 第 四 章 计 算 机 工 业 的 生 态 链 ( 二 ) 浪 潮 之 巅 第 四 章 计 算 机 工 业 的 生 态 链 ( 三 ) 浪 潮 之 巅 第 五 章 奔 腾 的 芯 ( 英 特 尔 Intel)( 一 ) 浪 潮 之 巅 第 五 章 奔 腾 的 芯 ( 英 特 尔 Intel)( 二 ) 浪 潮 之 巅 第 五 章 奔 腾 的 芯 ( 英 特 尔 Intel)( 三 ) 浪 潮 之 巅 第 五 章 奔 腾 的 芯 ( 英 特 尔 Intel)( 四 ) 浪 潮 之 巅 第 五 章 奔 腾 的 芯 ( 英 特 尔 Intel)( 五 ) 浪 潮 之 巅 第 六 章 互 联 网 的 金 门 大 桥 ( 思 科 )( 一 ) 浪 潮 之 巅 第 六 章 互 联 网 的 金 门 大 桥 ( 思 科 )( 二 ) 浪 潮 之 巅 第 六 章 互 联 网 的 金 门 大 桥 ( 思 科 )( 三 ) 浪 潮 之 巅 第 六 章 互 联 网 的 金 门 大 桥 ( 思 科 )( 四 ) 浪 潮 之 巅 第 七 章 硅 谷 的 见 证 人 ( 惠 普 公 司 )( 一 ) 浪 潮 之 巅 第 七 章 硅 谷 的 见 证 人 惠 普 公 司 ( 二 ) 浪 潮 之 巅 第 七 章 硅 谷 的 见 证 人 惠 普 公 司 ( 三 ) 浪 潮 之 巅 第 七 章 硅 谷 的 见 证 人 惠 普 公 司 ( 四 ) 浪 潮 之 巅 第 七 章 硅 谷 的 见 证 人 惠 普 公 司 ( 五 ) 浪 潮 之 巅 第 八 章 没 落 的 贵 族 摩 托 罗 拉 ( 一 ) 浪 潮 之 巅 第 八 章 没 落 的 贵 族 摩 托 罗 拉 ( 二 ) 浪 潮 之 巅 第 八 章 没 落 的 贵 族 摩 托 罗 拉 ( 三 ) 浪 潮 之 巅 第 八 章 没 落 的 贵 族 摩 托 罗 拉 ( 四 ) 浪 潮 之 巅 第 八 章 没 落 的 贵 族 摩 托 罗 拉 ( 五 ) 浪 潮 之 巅 第 八 章 没 落 的 贵 族 摩 托 罗 拉 ( 六 ) 浪 潮 之 巅 第 九 章 硅 谷 的 另 一 面 ( 一 ) 浪 潮 之 巅 第 九 章 硅 谷 的 另 一 面 ( 二 ) 浪 潮 之 巅 第 九 章 硅 谷 的 另 一 面 ( 三 ) 浪 潮 之 巅 第 九 章 硅 谷 的 另 一 面 ( 四 ) 浪 潮 之 巅 第 九 章 硅 谷 的 另 一 面 ( 五 ) 浪 潮 之 巅 第 十 章 短 暂 的 春 秋 与 机 会 失 之 交 臂 的 公 司 ( 一 ) 浪 潮 之 巅 第 十 章 短 暂 的 春 秋 与 机 会 失 之 交 臂 的 公 司 ( 二 ) 浪 潮 之 巅 第 十 章 短 暂 的 春 秋 与 机 会 失 之 交 臂 的 公 司 ( 三 ) 浪 潮 之 巅 第 十 章 短 暂 的 春 秋 与 机 会 失 之 交 臂 的 公 司 ( 四 ) II

4 目 录 浪 潮 之 巅 第 十 章 短 暂 的 春 秋 与 机 会 失 之 交 臂 的 公 司 ( 五 ) 浪 潮 之 巅 第 十 章 短 暂 的 春 秋 与 机 会 失 之 交 臂 的 公 司 ( 六 ) 浪 潮 之 巅 第 十 一 章 幕 后 的 英 雄 风 险 投 资 (Venture Capital) 浪 潮 之 巅 第 十 一 章 幕 后 的 英 雄 风 险 投 资 (Venture Capital) 浪 潮 之 巅 第 十 一 章 幕 后 的 英 雄 风 险 投 资 (Venture Capital) 浪 潮 之 巅 第 十 一 章 幕 后 的 英 雄 风 险 投 资 (Venture Capital) 浪 潮 之 巅 第 十 一 章 幕 后 的 英 雄 风 险 投 资 (Venture Capital) 浪 潮 之 巅 第 十 一 章 幕 后 的 英 雄 风 险 投 资 (Venture Capital) 浪 潮 之 巅 第 十 二 章 信 息 产 业 的 规 律 性 ( 一 ) 浪 潮 之 巅 第 十 二 章 信 息 产 业 的 规 律 性 ( 二 ) 浪 潮 之 巅 第 十 二 章 信 息 产 业 的 规 律 性 ( 三 ) III

5 数 学 之 美 1. 数 学 之 美 吴 军, Google 研 究 员 1.1. 数 学 之 美 系 列 一 统 计 语 言 模 型 2006 年 4 月 3 日 上 午 08:15:00 从 本 周 开 始, 我 们 将 定 期 刊 登 Google 科 学 家 吴 军 写 的 数 学 之 美 系 列 文 章, 介 绍 数 学 在 信 息 检 索 和 自 然 语 言 处 理 中 的 主 导 作 用 和 奇 妙 应 用 发 表 者 : 吴 军, Google 研 究 员 前 言 也 许 大 家 不 相 信, 数 学 是 解 决 信 息 检 索 和 自 然 语 言 处 理 的 最 好 工 具 它 能 非 常 清 晰 地 描 述 这 些 领 域 的 实 际 问 题 并 且 给 出 漂 亮 的 解 决 办 法 每 当 人 们 应 用 数 学 工 具 解 决 一 个 语 言 问 题 时, 总 会 感 叹 数 学 之 美 我 们 希 望 利 用 Google 中 文 黑 板 报 这 块 园 地, 介 绍 一 些 数 学 工 具, 以 及 我 们 是 如 何 利 用 这 些 工 具 来 开 发 Google 产 品 的 系 列 一 : 统 计 语 言 模 型 (Statistical Language Models) Google 的 使 命 是 整 合 全 球 的 信 息, 所 以 我 们 一 直 致 力 于 研 究 如 何 让 机 器 对 信 息 语 言 做 最 好 的 理 解 和 处 理 长 期 以 来, 人 类 一 直 梦 想 着 能 让 机 器 代 替 人 来 翻 译 语 言 识 别 语 音 认 识 文 字 ( 不 1

6 数 学 之 美 论 是 印 刷 体 或 手 写 体 ) 和 进 行 海 量 文 献 的 自 动 检 索, 这 就 需 要 让 机 器 理 解 语 言 但 是 人 类 的 语 言 可 以 说 是 信 息 里 最 复 杂 最 动 态 的 一 部 分 为 了 解 决 这 个 问 题, 人 们 容 易 想 到 的 办 法 就 是 让 机 器 模 拟 人 类 进 行 学 习 - 学 习 人 类 的 语 法 分 析 语 句 等 等 尤 其 是 在 乔 姆 斯 基 (Noam Chomsky 有 史 以 来 最 伟 大 的 语 言 学 家 ) 提 出 形 式 语 言 以 后, 人 们 更 坚 定 了 利 用 语 法 规 则 的 办 法 进 行 文 字 处 理 的 信 念 遗 憾 的 是, 几 十 年 过 去 了, 在 计 算 机 处 理 语 言 领 域, 基 于 这 个 语 法 规 则 的 方 法 几 乎 毫 无 突 破 其 实 早 在 几 十 年 前, 数 学 家 兼 信 息 论 的 祖 师 爷 香 农 (Claude Shannon) 就 提 出 了 用 数 学 的 办 法 处 理 自 然 语 言 的 想 法 遗 憾 的 是 当 时 的 计 算 机 条 件 根 本 无 法 满 足 大 量 信 息 处 理 的 需 要, 所 以 他 这 个 想 法 当 时 并 没 有 被 人 们 重 视 七 十 年 代 初, 有 了 大 规 模 集 成 电 路 的 快 速 计 算 机 后, 香 农 的 梦 想 才 得 以 实 现 首 先 成 功 利 用 数 学 方 法 解 决 自 然 语 言 处 理 问 题 的 是 语 音 和 语 言 处 理 大 师 贾 里 尼 克 (Fred Jelinek) 当 时 贾 里 尼 克 在 IBM 公 司 做 学 术 休 假 (Sabbatical Leave), 领 导 了 一 批 杰 出 的 科 学 家 利 用 大 型 计 算 机 来 处 理 人 类 语 言 问 题 统 计 语 言 模 型 就 是 在 那 个 时 候 提 出 的 给 大 家 举 个 例 子 : 在 很 多 涉 及 到 自 然 语 言 处 理 的 领 域, 如 机 器 翻 译 语 音 识 别 印 刷 体 或 手 写 体 识 别 拼 写 纠 错 汉 字 输 入 和 文 献 查 询 中, 我 们 都 需 要 知 道 一 个 文 字 序 列 是 否 能 构 成 一 个 大 2

7 数 学 之 美 家 能 理 解 的 句 子, 显 示 给 使 用 者 对 这 个 问 题, 我 们 可 以 用 一 个 简 单 的 统 计 模 型 来 解 决 这 个 问 题 如 果 S 表 示 一 连 串 特 定 顺 序 排 列 的 词 w1, w2,, wn, 换 句 话 说,S 可 以 表 示 某 一 个 由 一 连 串 特 定 顺 序 排 练 的 词 而 组 成 的 一 个 有 意 义 的 句 子 现 在, 机 器 对 语 言 的 识 别 从 某 种 角 度 来 说, 就 是 想 知 道 S 在 文 本 中 出 现 的 可 能 性, 也 就 是 数 学 上 所 说 的 S 的 概 率 用 P(S) 来 表 示 利 用 条 件 概 率 的 公 式,S 这 个 序 列 出 现 的 概 率 等 于 每 一 个 词 出 现 的 概 率 相 乘, 于 是 P(S) 可 展 开 为 : P(S) = P(w1)P(w2 w1)p(w3 w1 w2) P(wn w1 w2 wn-1) 其 中 P (w1) 表 示 第 一 个 词 w1 出 现 的 概 率 ;P (w2 w1) 是 在 已 知 第 一 个 词 的 前 提 下, 第 二 个 词 出 现 的 概 率 ; 以 次 类 推 不 难 看 出, 到 了 词 wn, 它 的 出 现 概 率 取 决 于 它 前 面 所 有 词 从 计 算 上 来 看, 各 种 可 能 性 太 多, 无 法 实 现 因 此 我 们 假 定 任 意 一 个 词 wi 的 出 现 概 率 只 同 它 前 面 的 词 wi-1 有 关 ( 即 马 尔 可 夫 假 设 ), 于 是 问 题 就 变 得 很 简 单 了 现 在,S 出 现 的 概 率 就 变 为 : P(S) = P(w1)P(w2 w1)p(w3 w2) P(wi wi-1) ( 当 然, 也 可 以 假 设 一 个 词 又 前 面 N-1 个 词 决 定, 模 型 稍 微 复 杂 些 ) 接 下 来 的 问 题 就 是 如 何 估 计 P (wi wi-1) 现 在 有 了 大 量 机 读 文 本 后, 这 个 问 题 变 得 很 简 单, 只 要 数 一 数 这 对 词 (wi-1,wi) 在 统 计 的 文 本 中 出 现 了 多 少 次, 以 及 wi-1 本 身 在 同 样 的 文 本 中 3

8 数 学 之 美 前 后 相 邻 出 现 了 多 少 次, 然 后 用 两 个 数 一 除 就 可 以 了,P(wi wi-1) = P(wi-1,wi)/ P (wi-1) 也 许 很 多 人 不 相 信 用 这 么 简 单 的 数 学 模 型 能 解 决 复 杂 的 语 音 识 别 机 器 翻 译 等 问 题 其 实 不 光 是 常 人, 就 连 很 多 语 言 学 家 都 曾 质 疑 过 这 种 方 法 的 有 效 性, 但 事 实 证 明, 统 计 语 言 模 型 比 任 何 已 知 的 借 助 某 种 规 则 的 解 决 方 法 都 有 效 比 如 在 Google 的 中 英 文 自 动 翻 译 中, 用 的 最 重 要 的 就 是 这 个 统 计 语 言 模 型 去 年 美 国 标 准 局 (NIST) 对 所 有 的 机 器 翻 译 系 统 进 行 了 评 测,Google 的 系 统 是 不 仅 是 全 世 界 最 好 的, 而 且 高 出 所 有 基 于 规 则 的 系 统 很 多 现 在, 读 者 也 许 已 经 能 感 受 到 数 学 的 美 妙 之 处 了, 它 把 一 些 复 杂 的 问 题 变 得 如 此 的 简 单 当 然, 真 正 实 现 一 个 好 的 统 计 语 言 模 型 还 有 许 多 细 节 问 题 需 要 解 决 贾 里 尼 克 和 他 的 同 事 的 贡 献 在 于 提 出 了 统 计 语 言 模 型, 而 且 很 漂 亮 地 解 决 了 所 有 的 细 节 问 题 十 几 年 后, 李 开 复 用 统 计 语 言 模 型 把 997 词 语 音 识 别 的 问 题 简 化 成 了 一 个 20 词 的 识 别 问 题, 实 现 了 有 史 以 来 第 一 次 大 词 汇 量 非 特 定 人 连 续 语 音 的 识 别 我 是 一 名 科 学 研 究 人 员, 我 在 工 作 中 经 常 惊 叹 于 数 学 语 言 应 用 于 解 决 实 际 问 题 上 时 的 神 奇 我 也 希 望 把 这 种 神 奇 讲 解 给 大 家 听 当 然, 归 根 结 底, 不 管 什 莫 样 的 科 学 方 法 无 论 多 莫 奇 妙 的 解 决 手 段 都 是 为 人 服 务 的 我 希 望 Google 多 努 力 一 分, 用 户 就 多 一 分 搜 索 的 喜 悦 4

9 数 学 之 美 1.2. 数 学 之 美 系 列 二 谈 谈 中 文 分 词 2006 年 4 月 10 日 上 午 08:10:00 发 表 者 : 吴 军, Google 研 究 员 谈 谈 中 文 分 词 统 计 语 言 模 型 在 中 文 处 理 中 的 一 个 应 用 上 回 我 们 谈 到 利 用 统 计 语 言 模 型 进 行 语 言 处 理, 由 于 模 型 是 建 立 在 词 的 基 础 上 的, 对 于 中 日 韩 等 语 言, 首 先 需 要 进 行 分 词 例 如 把 句 子 中 国 航 天 官 员 应 邀 到 美 国 与 太 空 总 署 官 员 开 会 分 成 一 串 词 : 中 国 / 航 天 / 官 员 / 应 邀 / 到 / 美 国 / 与 / 太 空 / 总 署 / 官 员 / 开 会 最 容 易 想 到 的, 也 是 最 简 单 的 分 词 办 法 就 是 查 字 典 这 种 方 法 最 早 是 由 北 京 航 天 航 空 大 学 的 梁 南 元 教 授 提 出 的 用 查 字 典 法, 其 实 就 是 我 们 把 一 个 句 子 从 左 向 右 扫 描 一 遍, 遇 到 字 典 里 有 的 词 就 标 识 出 来, 遇 到 复 合 词 ( 比 如 上 海 大 学 ) 就 找 最 长 的 词 匹 配, 遇 到 不 认 识 的 字 串 就 分 割 成 单 字 词, 于 是 简 单 的 分 词 就 完 成 了 这 种 简 单 的 分 词 方 法 完 全 能 处 理 上 面 例 子 中 的 句 子 八 十 年 代, 哈 工 大 的 王 晓 龙 博 士 把 它 理 论 化, 发 展 成 最 少 词 数 的 分 词 理 论, 即 一 句 话 应 该 分 成 数 量 最 少 的 词 串 这 种 方 法 一 个 明 显 的 不 足 是 当 遇 到 有 二 义 性 ( 有 双 重 理 解 意 思 ) 的 分 割 时 就 无 能 为 力 了 比 如, 对 短 语 发 展 中 国 家 正 确 的 分 割 是 发 展 - 中 - 国 家, 而 从 左 向 右 查 字 典 的 办 法 会 将 它 5

10 数 学 之 美 分 割 成 发 展 - 中 国 - 家, 显 然 是 错 了 另 外, 并 非 所 有 的 最 长 匹 配 都 一 定 是 正 确 的 比 如 上 海 大 学 城 书 店 的 正 确 分 词 应 该 是 上 海 - 大 学 城 - 书 店, 而 不 是 上 海 大 学 - 城 - 书 店 九 十 年 代 以 前, 海 内 外 不 少 学 者 试 图 用 一 些 文 法 规 则 来 解 决 分 词 的 二 义 性 问 题, 都 不 是 很 成 功 90 年 前 后, 清 华 大 学 的 郭 进 博 士 用 统 计 语 言 模 型 成 功 解 决 分 词 二 义 性 问 题, 将 汉 语 分 词 的 错 误 率 降 低 了 一 个 数 量 级 利 用 统 计 语 言 模 型 分 词 的 方 法, 可 以 用 几 个 数 学 公 式 简 单 概 括 如 下 : 我 们 假 定 一 个 句 子 S 可 以 有 几 种 分 词 方 法, 为 了 简 单 起 见 我 们 假 定 有 以 下 三 种 : A1, A2, A3,..., Ak, B1, B2, B3,..., Bm C1, C2, C3,..., Cn 其 中,A1, A2, B1, B2, C1, C2 等 等 都 是 汉 语 的 词 那 么 最 好 的 一 种 分 词 方 法 应 该 保 证 分 完 词 后 这 个 句 子 出 现 的 概 率 最 大 也 就 是 说 如 果 A1,A2,..., Ak 是 最 好 的 分 法, 那 么 (P 表 示 概 率 ): P (A1, A2, A3,..., Ak) P (B1, B2, B3,..., Bm), 并 且 6

11 数 学 之 美 P (A1, A2, A3,..., Ak) P(C1, C2, C3,..., Cn) 因 此, 只 要 我 们 利 用 上 回 提 到 的 统 计 语 言 模 型 计 算 出 每 种 分 词 后 句 子 出 现 的 概 率, 并 找 出 其 中 概 率 最 大 的, 我 们 就 能 够 找 到 最 好 的 分 词 方 法 当 然, 这 里 面 有 一 个 实 现 的 技 巧 如 果 我 们 穷 举 所 有 可 能 的 分 词 方 法 并 计 算 出 每 种 可 能 性 下 句 子 的 概 率, 那 么 计 算 量 是 相 当 大 的 因 此, 我 们 可 以 把 它 看 成 是 一 个 动 态 规 划 (Dynamic Programming) 的 问 题, 并 利 用 维 特 比 (Viterbi) 算 法 快 速 地 找 到 最 佳 分 词 在 清 华 大 学 的 郭 进 博 士 以 后, 海 内 外 不 少 学 者 利 用 统 计 的 方 法, 进 一 步 完 善 中 文 分 词 其 中 值 得 一 提 的 是 清 华 大 学 孙 茂 松 教 授 和 香 港 科 技 大 学 吴 德 凯 教 授 的 工 作 需 要 指 出 的 是, 语 言 学 家 对 词 语 的 定 义 不 完 全 相 同 比 如 说 北 京 大 学, 有 人 认 为 是 一 个 词, 而 有 人 认 为 该 分 成 两 个 词 一 个 折 中 的 解 决 办 法 是 在 分 词 的 同 时, 找 到 复 合 词 的 嵌 套 结 构 在 上 面 的 例 子 中, 如 果 一 句 话 包 含 北 京 大 学 四 个 字, 那 么 先 把 它 当 成 一 个 四 字 词, 然 后 再 进 一 步 找 出 细 分 词 北 京 和 大 学 这 种 方 法 是 最 早 是 郭 进 在 Computational Linguistics ( 计 算 机 语 言 学 ) 杂 志 上 发 表 的, 以 后 不 少 系 统 采 用 这 种 方 法 一 般 来 讲, 根 据 不 同 应 用, 汉 语 分 词 的 颗 粒 度 大 小 应 该 不 同 比 如, 在 机 器 翻 译 中, 颗 粒 度 应 该 大 一 些, 北 京 大 学 就 不 能 7

12 数 学 之 美 被 分 成 两 个 词 而 在 语 音 识 别 中, 北 京 大 学 一 般 是 被 分 成 两 个 词 因 此, 不 同 的 应 用, 应 该 有 不 同 的 分 词 系 统 Google 的 葛 显 平 博 士 和 朱 安 博 士, 专 门 为 搜 索 设 计 和 实 现 了 自 己 的 分 词 系 统 也 许 你 想 不 到, 中 文 分 词 的 方 法 也 被 应 用 到 英 语 处 理, 主 要 是 手 写 体 识 别 中 因 为 在 识 别 手 写 体 时, 单 词 之 间 的 空 格 就 不 很 清 楚 了 中 文 分 词 方 法 可 以 帮 助 判 别 英 语 单 词 的 边 界 其 实, 语 言 处 理 的 许 多 数 学 方 法 通 用 的 和 具 体 的 语 言 无 关 在 Google 内, 我 们 在 设 计 语 言 处 理 的 算 法 时, 都 会 考 虑 它 是 否 能 很 容 易 地 适 用 于 各 种 自 然 语 言 这 样, 我 们 才 能 有 效 地 支 持 上 百 种 语 言 的 搜 索 对 中 文 分 词 有 兴 趣 的 读 者, 可 以 阅 读 以 下 文 献 : 1. 梁 南 元 书 面 汉 语 自 动 分 词 系 统 7.pdf 2. 郭 进 统 计 语 言 模 型 和 汉 语 音 字 转 换 的 一 些 新 结 果 3. 郭 进 Critical Tokenization and its Properties 8

13 数 学 之 美 4. 孙 茂 松 Chinese word segmentation without using lexicon and hand-crafted training data DE&id= 数 学 之 美 系 列 三 隐 含 马 尔 可 夫 模 型 在 语 言 处 理 中 的 应 用 2006 年 4 月 17 日 上 午 08:01:00 发 表 者 : 吴 军,Google 研 究 员 前 言 : 隐 含 马 尔 可 夫 模 型 是 一 个 数 学 模 型, 到 目 前 为 之, 它 一 直 被 认 为 是 实 现 快 速 精 确 的 语 音 识 别 系 统 的 最 成 功 的 方 法 复 杂 的 语 音 识 别 问 题 通 过 隐 含 马 尔 可 夫 模 型 能 非 常 简 单 地 被 表 述 解 决, 让 我 不 由 由 衷 地 感 叹 数 学 模 型 之 妙 自 然 语 言 是 人 类 交 流 信 息 的 工 具 很 多 自 然 语 言 处 理 问 题 都 可 以 等 同 于 通 信 系 统 中 的 解 码 问 题 -- 一 个 人 根 据 接 收 到 的 信 息, 去 猜 测 发 话 人 要 表 达 的 意 思 这 其 实 就 象 通 信 中, 我 们 根 据 接 收 端 收 到 的 信 号 去 分 析 理 解 还 原 发 送 端 传 送 过 来 的 信 息 以 下 该 图 就 表 示 了 一 个 典 型 的 通 信 系 统 : 9

14 数 学 之 美 其 中 s1,s2,s3... 表 示 信 息 源 发 出 的 信 号 o1, o2, o3... 是 接 受 器 接 收 到 的 信 号 通 信 中 的 解 码 就 是 根 据 接 收 到 的 信 号 o1, o2, o3... 还 原 出 发 送 的 信 号 s1,s2,s3... 其 实 我 们 平 时 在 说 话 时, 脑 子 就 是 一 个 信 息 源 我 们 的 喉 咙 ( 声 带 ), 空 气, 就 是 如 电 线 和 光 缆 般 的 信 道 听 众 耳 朵 的 就 是 接 收 端, 而 听 到 的 声 音 就 是 传 送 过 来 的 信 号 根 据 声 学 信 号 来 推 测 说 话 者 的 意 思, 就 是 语 音 识 别 这 样 说 来, 如 果 接 收 端 是 一 台 计 算 机 而 不 是 人 的 话, 那 么 计 算 机 要 做 的 就 是 语 音 的 自 动 识 别 同 样, 在 计 算 机 中, 如 果 我 们 要 根 据 接 收 到 的 英 语 信 息, 推 测 说 话 者 的 汉 语 意 思, 就 是 机 器 翻 译 ; 如 果 我 们 要 根 据 带 有 拼 写 错 误 的 语 句 推 测 说 话 者 想 表 达 的 正 确 意 思, 那 就 是 自 动 纠 错 那 么 怎 么 根 据 接 收 到 的 信 息 来 推 测 说 话 者 想 表 达 的 意 思 呢? 我 们 可 以 利 用 叫 做 隐 含 马 尔 可 夫 模 型 (Hidden Markov Model) 来 解 决 这 些 问 题 以 语 音 识 别 为 例, 当 我 们 观 测 到 语 音 信 号 o1,o2,o3 时, 我 们 要 根 据 这 组 信 号 推 测 出 发 送 的 句 子 s1,s2,s3 显 然, 我 们 应 该 在 所 有 可 能 的 句 子 中 找 最 有 可 能 性 的 10

15 数 学 之 美 一 个 用 数 学 语 言 来 描 述, 就 是 在 已 知 o1,o2,o3,... 的 情 况 下, 求 使 得 条 件 概 率 P (s1,s2,s3,... o1,o2,o3...) 达 到 最 大 值 的 那 个 句 子 s1,s2,s3,... 当 然, 上 面 的 概 率 不 容 易 直 接 求 出, 于 是 我 们 可 以 间 接 地 计 算 它 利 用 贝 叶 斯 公 式 并 且 省 掉 一 个 常 数 项, 可 以 把 上 述 公 式 等 价 变 换 成 P(o1,o2,o3,... s1,s2,s3...) * P(s1,s2,s3,...) 其 中 P(o1,o2,o3,... s1,s2,s3...) 表 示 某 句 话 s1,s2,s3... 被 读 成 o1,o2,o3,... 的 可 能 性, 而 P(s1,s2,s3,...) 表 示 字 串 s1,s2,s3,... 本 身 能 够 成 为 一 个 合 乎 情 理 的 句 子 的 可 能 性, 所 以 这 个 公 式 的 意 义 是 用 发 送 信 号 为 s1,s2,s3... 这 个 数 列 的 可 能 性 乘 以 s1,s2,s3... 本 身 可 以 一 个 句 子 的 可 能 性, 得 出 概 率 ( 读 者 读 到 这 里 也 许 会 问, 你 现 在 是 不 是 把 问 题 变 得 更 复 杂 了, 因 为 公 式 越 写 越 长 了 别 着 急, 我 们 现 在 就 来 简 化 这 个 问 题 ) 我 们 在 这 里 做 两 个 假 设 : 第 一,s1,s2,s3,... 是 一 个 马 尔 可 夫 链, 也 就 是 说,si 只 由 si-1 决 定 ( 详 见 系 列 一 ); 11

16 数 学 之 美 第 二, 第 i 时 刻 的 接 收 信 号 oi 只 由 发 送 信 号 si 决 定 ( 又 称 为 独 立 输 出 假 设, 即 P(o1,o2,o3,... s1,s2,s3...) = P(o1 s1) * P(o2 s2)*p(o3 s3)... 那 么 我 们 就 可 以 很 容 易 利 用 算 法 Viterbi 找 出 上 面 式 子 的 最 大 值, 进 而 找 出 要 识 别 的 句 子 s1,s2,s3,... 满 足 上 述 两 个 假 设 的 模 型 就 叫 隐 含 马 尔 可 夫 模 型 我 们 之 所 以 用 隐 含 这 个 词, 是 因 为 状 态 s1,s2,s3,... 是 无 法 直 接 观 测 到 的 隐 含 马 尔 可 夫 模 型 的 应 用 远 不 只 在 语 音 识 别 中 在 上 面 的 公 式 中, 如 果 我 们 把 s1,s2,s3,... 当 成 中 文, 把 o1,o2,o3,... 当 成 对 应 的 英 文, 那 么 我 们 就 能 利 用 这 个 模 型 解 决 机 器 翻 译 问 题 ; 如 果 我 们 把 o1,o2,o3,... 当 成 扫 描 文 字 得 到 的 图 像 特 征, 就 能 利 用 这 个 模 型 解 决 印 刷 体 和 手 写 体 的 识 别 P (o1,o2,o3,... s1,s2,s3...) 根 据 应 用 的 不 同 而 又 不 同 的 名 称, 在 语 音 识 别 中 它 被 称 为 声 学 模 型 (Acoustic Model), 在 机 器 翻 译 中 是 翻 译 模 型 (Translation Model) 而 在 拼 写 校 正 中 是 纠 错 模 型 (Correction Model) 而 P (s1,s2,s3,...) 就 是 我 们 在 系 列 一 中 提 到 的 语 言 模 型 在 利 用 隐 含 马 尔 可 夫 模 型 解 决 语 言 处 理 问 题 前, 先 要 进 行 模 型 的 训 练 常 用 的 训 练 方 法 由 伯 姆 (Baum) 在 60 年 代 提 出 的, 并 以 他 的 名 字 命 名 隐 含 马 尔 可 夫 模 型 在 处 理 语 言 问 题 早 期 的 成 功 应 用 是 语 音 识 别 七 十 年 代, 当 时 IBM 的 Fred Jelinek ( 贾 12

17 数 学 之 美 里 尼 克 ) 和 卡 内 基 梅 隆 大 学 的 Jim and Janet Baker ( 贝 克 夫 妇, 李 开 复 的 师 兄 师 姐 ) 分 别 独 立 地 提 出 用 隐 含 马 尔 可 夫 模 型 来 识 别 语 音, 语 音 识 别 的 错 误 率 相 比 人 工 智 能 和 模 式 匹 配 等 方 法 降 低 了 三 倍 ( 从 30% 到 10%) 八 十 年 代 李 开 复 博 士 坚 持 采 用 隐 含 马 尔 可 夫 模 型 的 框 架, 成 功 地 开 发 了 世 界 上 第 一 个 大 词 汇 量 连 续 语 音 识 别 系 统 Sphinx 我 最 早 接 触 到 隐 含 马 尔 可 夫 模 型 是 几 乎 二 十 年 前 的 事 那 时 在 随 机 过 程 ( 清 华 著 名 的 一 门 课 ) 里 学 到 这 个 模 型, 但 当 时 实 在 想 不 出 它 有 什 么 实 际 用 途 几 年 后, 我 在 清 华 跟 随 王 作 英 教 授 学 习 研 究 语 音 识 别 时, 他 给 了 我 几 十 篇 文 献 我 印 象 最 深 的 就 是 贾 里 尼 克 和 李 开 复 的 文 章, 它 们 的 核 心 思 想 就 是 隐 含 马 尔 可 夫 模 型 复 杂 的 语 音 识 别 问 题 居 然 能 如 此 简 单 地 被 表 述 解 决, 我 由 衷 地 感 叹 数 学 模 型 之 妙 1.4. 数 学 之 美 系 列 四 怎 样 度 量 信 息? 2006 年 4 月 26 日 上 午 08:11:00 发 表 者 : 吴 军,Google 研 究 员 前 言 : Google 一 直 以 整 合 全 球 信 息, 让 人 人 能 获 取, 使 人 人 能 受 益 为 使 命 那 么 究 竟 每 一 条 信 息 应 该 怎 样 度 量 呢? 13

18 数 学 之 美 信 息 是 个 很 抽 象 的 概 念 我 们 常 常 说 信 息 很 多, 或 者 信 息 较 少, 但 却 很 难 说 清 楚 信 息 到 底 有 多 少 比 如 一 本 五 十 万 字 的 中 文 书 到 底 有 多 少 信 息 量 直 到 1948 年, 香 农 提 出 了 信 息 熵 (sh āng) 的 概 念, 才 解 决 了 对 信 息 的 量 化 度 量 问 题 一 条 信 息 的 信 息 量 大 小 和 它 的 不 确 定 性 有 直 接 的 关 系 比 如 说, 我 们 要 搞 清 楚 一 件 非 常 非 常 不 确 定 的 事, 或 是 我 们 一 无 所 知 的 事 情, 就 需 要 了 解 大 量 的 信 息 相 反, 如 果 我 们 对 某 件 事 已 经 有 了 较 多 的 了 解, 我 们 不 需 要 太 多 的 信 息 就 能 把 它 搞 清 楚 所 以, 从 这 个 角 度, 我 们 可 以 认 为, 信 息 量 的 度 量 就 等 于 不 确 定 性 的 多 少 那 么 我 们 如 何 量 化 的 度 量 信 息 量 呢? 我 们 来 看 一 个 例 子, 马 上 要 举 行 世 界 杯 赛 了 大 家 都 很 关 心 谁 会 是 冠 军 假 如 我 错 过 了 看 世 界 杯, 赛 后 我 问 一 个 知 道 比 赛 结 果 的 观 众 哪 支 球 队 是 冠 军? 他 不 愿 意 直 接 告 诉 我, 而 要 让 我 猜, 并 且 我 每 猜 一 次, 他 要 收 一 元 钱 才 肯 告 诉 我 是 否 猜 对 了, 那 么 我 需 要 付 给 他 多 少 钱 才 能 知 道 谁 是 冠 军 呢? 我 可 以 把 球 队 编 上 号, 从 1 到 32, 然 后 提 问 : 冠 军 的 球 队 在 1-16 号 中 吗? 假 如 他 告 诉 我 猜 对 了, 我 会 接 着 问 : 冠 军 在 1-8 号 中 吗? 假 如 他 告 诉 我 猜 错 了, 我 自 然 知 道 冠 军 队 在 9-16 中 这 样 只 需 要 五 次, 我 就 能 知 道 哪 支 球 队 是 冠 军 所 以, 谁 是 世 界 杯 冠 军 这 条 消 息 的 信 息 量 只 值 五 块 钱 14

19 数 学 之 美 当 然, 香 农 不 是 用 钱, 而 是 用 比 特 (bit) 这 个 概 念 来 度 量 信 息 量 一 个 比 特 是 一 位 二 进 制 数, 计 算 机 中 的 一 个 字 节 是 八 个 比 特 在 上 面 的 例 子 中, 这 条 消 息 的 信 息 量 是 五 比 特 ( 如 果 有 朝 一 日 有 六 十 四 个 队 进 入 决 赛 阶 段 的 比 赛, 那 么 谁 世 界 杯 冠 军 的 信 息 量 就 是 六 比 特, 因 为 我 们 要 多 猜 一 次 ) 读 者 可 能 已 经 发 现, 信 息 量 的 比 特 数 和 所 有 可 能 情 况 的 对 数 函 数 log 有 关 (log32=5, log64=6 ) 有 些 读 者 此 时 可 能 会 发 现 我 们 实 际 上 可 能 不 需 要 猜 五 次 就 能 猜 出 谁 是 冠 军, 因 为 象 巴 西 德 国 意 大 利 这 样 的 球 队 得 冠 军 的 可 能 性 比 日 本 美 国 韩 国 等 队 大 的 多 因 此, 我 们 第 一 次 猜 测 时 不 需 要 把 32 个 球 队 等 分 成 两 个 组, 而 可 以 把 少 数 几 个 最 可 能 的 球 队 分 成 一 组, 把 其 它 队 分 成 另 一 组 然 后 我 们 猜 冠 军 球 队 是 否 在 那 几 只 热 门 队 中 我 们 重 复 这 样 的 过 程, 根 据 夺 冠 概 率 对 剩 下 的 候 选 球 队 分 组, 直 到 找 到 冠 军 队 这 样, 我 们 也 许 三 次 或 四 次 就 猜 出 结 果 因 此, 当 每 个 球 队 夺 冠 的 可 能 性 ( 概 率 ) 不 等 时, 谁 世 界 杯 冠 军 的 信 息 量 的 信 息 量 比 五 比 特 少 香 农 指 出, 它 的 准 确 信 息 量 应 该 是 = -(p1*log p1 + p2 * log p p32 *log p32), 其 中,p1,p2,...,p32 分 别 是 这 32 个 球 队 夺 冠 的 概 率 香 农 把 它 称 为 信 息 熵 (Entropy), 一 般 用 符 号 H 表 示, 单 位 是 比 特 有 兴 趣 的 读 者 可 以 推 算 一 下 当 32 个 球 队 夺 冠 概 率 相 同 时, 对 应 的 信 息 熵 等 于 五 比 特 有 数 学 基 础 的 读 者 还 可 15

20 数 学 之 美 以 证 明 上 面 公 式 的 值 不 可 能 大 于 五 对 于 任 意 一 个 随 机 变 量 X ( 比 如 得 冠 军 的 球 队 ), 它 的 熵 定 义 如 下 : 变 量 的 不 确 定 性 越 大, 熵 也 就 越 大, 把 它 搞 清 楚 所 需 要 的 信 息 量 也 就 越 大 有 了 熵 这 个 概 念, 我 们 就 可 以 回 答 本 文 开 始 提 出 的 问 题, 即 一 本 五 十 万 字 的 中 文 书 平 均 有 多 少 信 息 量 我 们 知 道 常 用 的 汉 字 ( 一 级 二 级 国 标 ) 大 约 有 7000 字 假 如 每 个 字 等 概 率, 那 么 我 们 大 约 需 要 13 个 比 特 ( 即 13 位 二 进 制 数 ) 表 示 一 个 汉 字 但 汉 字 的 使 用 是 不 平 衡 的 实 际 上, 前 10% 的 汉 字 占 文 本 的 95% 以 上 因 此, 即 使 不 考 虑 上 下 文 的 相 关 性, 而 只 考 虑 每 个 汉 字 的 独 立 的 概 率, 那 么, 每 个 汉 字 的 信 息 熵 大 约 也 只 有 8-9 个 比 特 如 果 我 们 再 考 虑 上 下 文 相 关 性, 每 个 汉 字 的 信 息 熵 只 有 5 比 特 左 右 所 以, 一 本 五 十 万 字 的 中 文 书, 信 息 量 大 约 是 250 万 比 特 如 果 用 一 个 好 的 算 法 压 缩 一 下, 整 本 书 可 以 存 成 一 个 320KB 的 文 件 如 果 我 们 直 接 用 两 字 节 的 国 标 编 码 存 储 这 本 书, 大 约 需 要 1MB 大 小, 是 压 缩 文 件 的 三 倍 这 两 个 数 量 的 差 距, 在 信 息 论 中 称 作 冗 余 度 (redundancy) 需 要 指 出 的 是 我 们 这 里 讲 的 250 万 比 特 是 个 平 均 数, 同 样 长 度 的 书, 所 含 的 信 息 量 可 以 差 很 多 如 果 一 本 书 重 复 的 内 容 很 多, 它 的 信 息 量 就 小, 冗 余 度 就 大 16

21 数 学 之 美 不 同 语 言 的 冗 余 度 差 别 很 大, 而 汉 语 在 所 有 语 言 中 冗 余 度 是 相 对 小 的 这 和 人 们 普 遍 的 认 识 汉 语 是 最 简 洁 的 语 言 是 一 致 的 在 下 一 集 中, 我 们 将 介 绍 信 息 熵 在 信 息 处 理 中 的 应 用 以 及 两 个 相 关 的 概 念 互 信 息 和 相 对 熵 对 中 文 信 息 熵 有 兴 趣 的 读 者 可 以 读 我 和 王 作 英 教 授 在 电 子 学 报 上 合 写 的 一 篇 文 章 语 信 息 熵 和 语 言 模 型 的 复 杂 度 1.5. 数 学 之 美 系 列 五 简 单 之 美 : 布 尔 代 数 和 搜 索 引 擎 的 索 引 2006 年 5 月 10 日 上 午 09:10:00 发 表 者 : 吴 军,Google 研 究 员 [ 建 立 一 个 搜 索 引 擎 大 致 需 要 做 这 样 几 件 事 : 自 动 下 载 尽 可 能 多 的 网 页 ; 建 立 快 速 有 效 的 索 引 ; 根 据 相 关 性 对 网 页 进 行 公 平 准 确 的 排 序 我 们 在 介 绍 Google Page Rank ( 网 页 排 名 ) 时 已 经 谈 到 了 一 些 排 序 的 问 题, 这 里 我 们 谈 谈 索 引 问 题, 以 后 我 们 还 会 谈 如 何 度 量 网 页 的 相 关 性, 和 进 行 网 页 自 动 下 载 ] 17

22 数 学 之 美 世 界 上 不 可 能 有 比 二 进 制 更 简 单 的 计 数 方 法 了, 也 不 可 能 有 比 布 尔 运 算 更 简 单 的 运 算 了 尽 管 今 天 每 个 搜 索 引 擎 都 宣 称 自 己 如 何 聪 明 多 么 智 能 化, 其 实 从 根 本 上 讲 都 没 有 逃 出 布 尔 运 算 的 框 框 布 尔 (George Boole) 是 十 九 世 纪 英 国 一 位 小 学 数 学 老 师 他 生 前 没 有 人 认 为 他 是 数 学 家 布 尔 在 工 作 之 余, 喜 欢 阅 读 数 学 论 著 思 考 数 学 问 题 1854 年 思 维 规 律 (An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities) 一 书, 第 一 次 向 人 们 展 示 了 如 何 用 数 学 的 方 法 解 决 逻 辑 问 题 布 尔 代 数 简 单 得 不 能 再 简 单 了 运 算 的 元 素 只 有 两 个 1 (TRUE, 真 ) 和 0 (FALSE, 假 ) 基 本 的 运 算 只 有 与 (AND) 或 (OR) 和 非 (NOT) 三 种 ( 后 来 发 现, 这 三 种 运 算 都 可 以 转 换 成 与 非 AND-NOT 一 种 运 算 ) 全 部 运 算 只 用 下 列 几 张 真 值 表 就 能 完 全 地 描 述 清 楚 AND 这 张 表 说 明 如 果 AND 运 算 的 两 个 元 素 有 一 个 是 0, 则 运 算 结 果 总 是 0 如 果 两 个 元 素 都 是 1, 运 算 结 果 是 1 例 如, 太 阳 18

23 数 学 之 美 从 西 边 升 起 这 个 判 断 是 假 的 (0), 水 可 以 流 动 这 个 判 断 是 真 的 (1), 那 么, 太 阳 从 西 边 升 起 并 且 水 可 以 流 动 就 是 假 的 (0) OR 这 张 表 说 明 如 果 OR 运 算 的 两 个 元 素 有 一 个 是 1, 则 运 算 结 果 总 是 1 如 果 两 个 元 素 都 是 0, 运 算 结 果 是 0 比 如 说, 张 三 是 比 赛 第 一 名 这 个 结 论 是 假 的 (0), 李 四 是 比 赛 第 一 名 是 真 的 (1), 那 么 张 三 或 者 李 四 是 第 一 名 就 是 真 的 (1) NOT 这 张 表 说 明 NOT 运 算 把 1 变 成 0, 把 0 变 成 1 比 如, 如 果 象 牙 是 白 的 是 真 的 (1), 那 么 象 牙 不 是 白 的 必 定 是 假 的 (0) 读 者 也 许 会 问 这 么 简 单 的 理 论 能 解 决 什 么 实 际 问 题 布 尔 同 时 代 的 数 学 家 们 也 有 同 样 的 问 题 事 实 上 在 布 尔 代 数 提 出 后 80 多 年 里, 它 确 实 没 有 什 么 像 样 的 应 用, 直 到 1938 年 香 农 在 他 的 硕 士 论 文 中 指 出 用 布 尔 代 数 来 实 现 开 关 电 路, 才 使 得 布 尔 代 数 成 为 数 字 电 路 的 基 础 所 有 的 数 学 和 逻 辑 运 算, 加 减 乘 除 乘 方 开 方 等 等, 全 部 能 转 换 成 二 值 的 布 尔 运 算 19

24 数 学 之 美 现 在 我 们 看 看 文 献 检 索 和 布 尔 运 算 的 关 系 对 于 一 个 用 户 输 入 的 关 键 词, 搜 索 引 擎 要 判 断 每 篇 文 献 是 否 含 有 这 个 关 键 词, 如 果 一 篇 文 献 含 有 它, 我 们 相 应 地 给 这 篇 文 献 一 个 逻 辑 值 -- 真 (TRUE, 或 1), 否 则, 给 一 个 逻 辑 值 -- 假 (FALSE, 或 0) 比 如 我 们 要 找 有 关 原 子 能 应 用 的 文 献, 但 并 不 想 知 道 如 何 造 原 子 弹 我 们 可 以 这 样 写 一 个 查 询 语 句 原 子 能 AND 应 用 AND (NOT 原 子 弹 ), 表 示 符 合 要 求 的 文 献 必 须 同 时 满 足 三 个 条 件 : - 包 含 原 子 能 - 包 含 应 用 - 不 包 含 原 子 弹 一 篇 文 献 对 于 上 面 每 一 个 条 件, 都 有 一 个 True 或 者 False 的 答 案, 根 据 上 述 真 值 表 就 能 算 出 每 篇 文 献 是 否 是 要 找 的 早 期 的 文 献 检 索 查 询 系 统 大 多 基 于 数 据 库, 严 格 要 求 查 询 语 句 符 合 布 尔 运 算 今 天 的 搜 索 引 擎 相 比 之 下 要 聪 明 的 多, 它 自 动 把 用 户 的 查 询 语 句 转 换 成 布 尔 运 算 的 算 式 当 然 在 查 询 时, 不 能 将 每 篇 文 献 扫 描 一 遍, 来 看 看 它 是 否 满 足 上 面 三 个 条 件, 因 此 需 要 建 立 一 个 索 引 最 简 单 索 引 的 结 构 是 用 一 个 很 长 的 二 进 制 数 表 示 一 个 关 键 字 是 否 出 现 在 每 篇 文 献 中 有 多 少 篇 文 献, 就 有 多 少 位 数, 每 一 位 对 应 一 篇 文 献,1 代 表 相 应 的 文 献 有 这 个 关 键 字,0 代 表 没 有 比 如 关 键 字 原 子 能 对 应 的 二 进 制 数 是 , 表 示 第 二 第 五 第 九 第 十 第 十 六 篇 文 献 包 含 着 个 关 键 字 20

25 数 学 之 美 注 意, 这 个 二 进 制 数 非 常 之 长 同 样, 我 们 假 定 应 用 对 应 的 二 进 制 数 是 那 么 要 找 到 同 时 包 含 原 子 能 和 应 用 的 文 献 时, 只 要 将 这 两 个 二 进 制 数 进 行 布 尔 运 算 AND 根 据 上 面 的 真 值 表, 我 们 知 道 运 算 结 果 是 表 示 第 五 篇, 第 十 六 篇 文 献 满 足 要 求 注 意, 计 算 机 作 布 尔 运 算 是 非 常 非 常 快 的 现 在 最 便 宜 的 微 机 都 可 以 一 次 进 行 三 十 二 位 布 尔 运 算, 一 秒 钟 进 行 十 亿 次 以 上 当 然, 由 于 这 些 二 进 制 数 中 绝 大 部 分 位 数 都 是 零, 我 们 只 需 要 记 录 那 些 等 于 1 的 位 数 即 可 于 是, 搜 索 引 擎 的 索 引 就 变 成 了 一 张 大 表 : 表 的 每 一 行 对 应 一 个 关 键 词, 而 每 一 个 关 键 词 后 面 跟 着 一 组 数 字, 是 包 含 该 关 键 词 的 文 献 序 号 对 于 互 联 网 的 搜 索 引 擎 来 讲, 每 一 个 网 页 就 是 一 个 文 献 互 联 网 的 网 页 数 量 是 巨 大 的, 网 络 中 所 用 的 词 也 非 常 非 常 多 因 此 这 个 索 引 是 巨 大 的, 在 万 亿 字 节 这 个 量 级 早 期 的 搜 索 引 擎 ( 比 如 Alta Vista 以 前 的 所 有 搜 索 引 擎 ), 由 于 受 计 算 机 速 度 和 容 量 的 限 制, 只 能 对 重 要 的 关 键 的 主 题 词 建 立 索 引 至 今 很 多 学 术 杂 志 还 要 求 作 者 提 供 3-5 个 关 键 词 这 样 所 有 不 常 见 的 词 和 太 常 见 的 虚 词 就 找 不 到 了 现 在, 为 了 保 证 对 任 何 搜 索 都 能 提 供 相 关 的 网 页, 所 有 的 搜 索 引 擎 都 是 对 所 有 的 词 进 行 索 引 为 了 网 页 排 名 方 便, 索 引 中 还 需 存 有 大 量 附 加 信 息, 诸 如 每 个 词 出 现 的 位 置 次 数 等 等 因 此, 整 个 索 引 就 变 得 非 常 之 大, 以 至 于 不 可 能 用 一 台 计 算 机 存 下 大 家 普 遍 的 做 法 就 是 根 据 网 页 的 序 号 将 索 引 21

26 数 学 之 美 分 成 很 多 份 (Shards), 分 别 存 储 在 不 同 的 服 务 器 中 每 当 接 受 一 个 查 询 时, 这 个 查 询 就 被 分 送 到 许 许 多 多 服 务 器 中, 这 些 服 务 器 同 时 并 行 处 理 用 户 请 求, 并 把 结 果 送 到 主 服 务 器 进 行 合 并 处 理, 最 后 将 结 果 返 回 给 用 户 不 管 索 引 如 何 复 杂, 查 找 的 基 本 操 作 仍 然 是 布 尔 运 算 布 尔 运 算 把 逻 辑 和 数 学 联 系 起 来 了 它 的 最 大 好 处 是 容 易 实 现, 速 度 快, 这 对 于 海 量 的 信 息 查 找 是 至 关 重 要 的 它 的 不 足 是 只 能 给 出 是 与 否 的 判 断, 而 不 能 给 出 量 化 的 度 量 因 此, 所 有 搜 索 引 擎 在 内 部 检 索 完 毕 后, 都 要 对 符 合 要 求 的 网 页 根 据 相 关 性 排 序, 然 后 才 返 回 给 用 户 1.6. 数 学 之 美 系 列 六 图 论 和 网 络 爬 虫 (Web Crawlers) 2006 年 5 月 15 日 上 午 07:15:00 发 表 者 : 吴 军,Google 研 究 员 [ 离 散 数 学 是 当 代 数 学 的 一 个 重 要 分 支, 也 是 计 算 机 科 学 的 数 学 基 础 它 包 括 数 理 逻 辑 集 合 论 图 论 和 近 世 代 数 四 个 分 支 数 理 逻 辑 基 于 布 尔 运 算, 我 们 已 经 介 绍 过 了 这 里 我 们 介 绍 图 论 和 互 联 网 自 动 下 载 工 具 网 络 爬 虫 (Web Crawlers) 之 间 的 关 系 顺 便 提 一 句, 我 们 用 Google Trends 来 搜 索 一 下 离 散 数 学 这 22

27 数 学 之 美 个 词, 可 以 发 现 不 少 有 趣 的 现 象 比 如, 武 汉 哈 尔 滨 合 肥 和 长 沙 市 对 这 一 数 学 题 目 最 有 兴 趣 的 城 市 ] 我 们 上 回 谈 到 了 如 何 建 立 搜 索 引 擎 的 索 引, 那 么 如 何 自 动 下 载 互 联 网 所 有 的 网 页 呢, 它 要 用 到 图 论 中 的 遍 历 (Traverse) 算 法 图 论 的 起 源 可 追 溯 到 大 数 学 家 欧 拉 (Leonhard Euler) 1736 年 欧 拉 来 到 德 国 的 哥 尼 斯 堡 (Konigsberg, 大 哲 学 家 康 德 的 故 乡, 现 在 是 俄 罗 斯 的 加 里 宁 格 勒 ), 发 现 当 地 市 民 们 有 一 项 消 遣 活 动, 就 是 试 图 将 下 图 中 的 每 座 桥 恰 好 走 过 一 遍 并 回 到 原 出 发 点, 从 来 没 有 人 成 功 过 欧 拉 证 明 了 这 件 事 是 不 可 能 的, 并 写 了 一 篇 论 文, 一 般 认 为 这 是 图 论 的 开 始 图 论 中 所 讨 论 的 的 图 由 一 些 节 点 和 连 接 这 些 节 点 的 弧 组 成 如 果 我 们 把 中 国 的 城 市 当 成 节 点, 连 接 城 市 的 国 道 当 成 弧, 那 么 全 国 的 公 路 干 线 网 就 是 图 论 中 所 说 的 图 关 于 图 的 算 法 有 很 多, 但 最 重 要 的 是 图 的 遍 历 算 法, 也 就 是 如 何 通 过 弧 访 问 图 的 各 个 节 23

28 数 学 之 美 点 以 中 国 公 路 网 为 例, 我 们 从 北 京 出 发, 看 一 看 北 京 和 哪 些 城 市 直 接 相 连, 比 如 说 和 天 津 济 南 石 家 庄 南 京 沈 阳 大 同 直 接 相 连 我 们 可 以 依 次 访 问 这 些 城 市, 然 后 我 们 看 看 都 有 哪 些 城 市 和 这 些 已 经 访 问 过 的 城 市 相 连, 比 如 说 北 戴 河 秦 皇 岛 与 天 津 相 连, 青 岛 烟 台 和 济 南 相 连, 太 原 郑 州 和 石 家 庄 相 连 等 等, 我 们 再 一 次 访 问 北 戴 河 这 些 城 市, 直 到 中 国 所 有 的 城 市 都 访 问 过 一 遍 为 止 这 种 图 的 遍 历 算 法 称 为 广 度 优 先 算 法 (BFS), 因 为 它 先 要 尽 可 能 广 地 访 问 每 个 节 点 所 直 接 连 接 的 其 他 节 点 另 外 还 有 一 种 策 略 是 从 北 京 出 发, 随 便 找 到 下 一 个 要 访 问 的 城 市, 比 如 是 济 南, 然 后 从 济 南 出 发 到 下 一 个 城 市, 比 如 说 南 京, 再 访 问 从 南 京 出 发 的 城 市, 一 直 走 到 头 然 后 再 往 回 找, 看 看 中 间 是 否 有 尚 未 访 问 的 城 市 这 种 方 法 叫 深 度 优 先 算 法 (DFS), 因 为 它 是 一 条 路 走 到 黑 这 两 种 方 法 都 可 以 保 证 访 问 到 全 部 的 城 市 当 然, 不 论 采 用 哪 种 方 法, 我 们 都 应 该 用 一 个 小 本 本, 记 录 已 经 访 问 过 的 城 市, 以 防 同 一 个 城 市 访 问 多 次 或 者 漏 掉 哪 个 城 市 现 在 我 们 看 看 图 论 的 遍 历 算 法 和 搜 索 引 擎 的 关 系 互 联 网 其 实 就 是 一 张 大 图, 我 们 可 以 把 每 一 个 网 页 当 作 一 个 节 点, 把 那 些 超 链 接 (Hyperlinks) 当 作 连 接 网 页 的 弧 很 多 读 者 可 能 已 经 注 意 到, 网 页 中 那 些 蓝 色 的 带 有 下 划 线 的 文 字 背 后 其 实 藏 着 对 应 的 网 址, 当 你 点 下 去 的 的 时 候, 浏 览 器 是 通 过 这 些 隐 含 的 网 址 转 到 相 应 的 网 页 中 的 这 些 隐 含 在 文 字 背 后 的 网 址 称 为 超 链 接 有 了 超 链 接, 我 们 可 以 从 任 何 一 个 网 页 出 发, 用 图 的 遍 历 算 法, 24

29 数 学 之 美 自 动 地 访 问 到 每 一 个 网 页 并 把 它 们 存 起 来 完 成 这 个 功 能 的 程 序 叫 做 网 络 爬 虫, 或 者 在 一 些 文 献 中 称 为 " 机 器 人 "(Robot) 世 界 上 第 一 个 网 络 爬 虫 是 由 麻 省 理 工 学 院 (MIT) 的 学 生 马 休. 格 雷 (Matthew Gray) 在 1993 年 写 成 的 他 给 他 的 程 序 起 了 个 名 字 叫 互 联 网 漫 游 者 ("www wanderer") 以 后 的 网 络 爬 虫 越 写 越 复 杂, 但 原 理 是 一 样 的 我 们 来 看 看 网 络 爬 虫 如 何 下 载 整 个 互 联 网 假 定 我 们 从 一 家 门 户 网 站 的 首 页 出 发, 先 下 载 这 个 网 页, 然 后 通 过 分 析 这 个 网 页, 可 以 找 到 藏 在 它 里 面 的 所 有 超 链 接, 也 就 等 于 知 道 了 这 家 门 户 网 站 首 页 所 直 接 连 接 的 全 部 网 页, 诸 如 雅 虎 邮 件 雅 虎 财 经 雅 虎 新 闻 等 等 我 们 接 下 来 访 问 下 载 并 分 析 这 家 门 户 网 站 的 邮 件 等 网 页, 又 能 找 到 其 他 相 连 的 网 页 我 们 让 计 算 机 不 停 地 做 下 去, 就 能 下 载 整 个 的 互 联 网 当 然, 我 们 也 要 记 载 哪 个 网 页 下 载 过 了, 以 免 重 复 在 网 络 爬 虫 中, 我 们 使 用 一 个 称 为 哈 希 表 (Hash Table) 的 列 表 而 不 是 一 个 记 事 本 纪 录 网 页 是 否 下 载 过 的 信 息 现 在 的 互 联 网 非 常 巨 大, 不 可 能 通 过 一 台 或 几 台 计 算 机 服 务 器 就 能 完 成 下 载 任 务 比 如 雅 虎 公 司 (Google 没 有 公 开 公 布 我 们 的 数 目, 所 以 我 这 里 举 了 雅 虎 的 索 引 大 小 为 例 ) 宣 称 他 们 索 引 了 200 亿 个 网 页, 假 如 下 载 一 个 网 页 需 要 一 秒 钟, 下 载 这 200 亿 个 网 页 则 需 要 634 年 因 此, 一 个 商 业 的 网 络 爬 虫 需 要 有 成 千 上 万 个 服 务 器, 并 且 由 快 速 网 络 连 接 起 来 如 何 建 立 这 样 复 杂 25

30 数 学 之 美 的 网 络 系 统, 如 何 协 调 这 些 服 务 器 的 任 务, 就 是 网 络 设 计 和 程 序 设 计 的 艺 术 了 1.7. 数 学 之 美 系 列 七 信 息 论 在 信 息 处 理 中 的 应 用 2006 年 5 月 25 日 上 午 07:56:00 发 表 者 : 吴 军, Google 研 究 员 我 们 已 经 介 绍 了 信 息 熵, 它 是 信 息 论 的 基 础, 我 们 这 次 谈 谈 信 息 论 在 自 然 语 言 处 理 中 的 应 用 先 看 看 信 息 熵 和 语 言 模 型 的 关 系 我 们 在 系 列 一 中 谈 到 语 言 模 型 时, 没 有 讲 如 何 定 量 地 衡 量 一 个 语 言 模 型 的 好 坏, 当 然, 读 者 会 很 自 然 地 想 到, 既 然 语 言 模 型 能 减 少 语 音 识 别 和 机 器 翻 译 的 错 误, 那 么 就 拿 一 个 语 音 识 别 系 统 或 者 机 器 翻 译 软 件 来 试 试, 好 的 语 言 模 型 必 然 导 致 错 误 率 较 低 这 种 想 法 是 对 的, 而 且 今 天 的 语 音 识 别 和 机 器 翻 译 也 是 这 么 做 的 但 这 种 测 试 方 法 对 于 研 发 语 言 模 型 的 人 来 讲, 既 不 直 接 又 不 方 便, 而 且 很 难 从 错 误 率 反 过 来 定 量 度 量 语 言 模 型 事 实 上, 在 贾 里 尼 克 (Fred Jelinek) 的 人 研 究 语 言 模 型 时, 世 界 上 既 没 有 像 样 的 语 音 识 别 系 统, 更 没 有 机 器 翻 译 我 们 知 道, 语 言 模 型 是 为 了 用 上 下 文 预 测 当 前 的 文 字, 模 型 越 好, 预 测 得 越 准, 那 么 当 前 文 字 的 不 确 定 性 就 越 小 26

31 数 学 之 美 信 息 熵 正 是 对 不 确 定 性 的 衡 量, 因 此 信 息 熵 可 以 直 接 用 于 衡 量 统 计 语 言 模 型 的 好 坏 贾 里 尼 克 从 信 息 熵 出 发, 定 义 了 一 个 称 为 语 言 模 型 复 杂 度 (Perplexity) 的 概 念, 直 接 衡 量 语 言 模 型 的 好 坏 一 个 模 型 的 复 杂 度 越 小, 模 型 越 好 李 开 复 博 士 在 介 绍 他 发 明 的 Sphinx 语 音 识 别 系 统 时 谈 到, 如 果 不 用 任 何 语 言 模 型 ( 即 零 元 语 言 模 型 ) 时, 复 杂 度 为 997, 也 就 是 说 句 子 中 每 个 位 置 有 997 个 可 能 的 单 词 可 以 填 入 如 果 ( 二 元 ) 语 言 模 型 只 考 虑 前 后 词 的 搭 配 不 考 虑 搭 配 的 概 率 时, 复 杂 度 为 60 虽 然 它 比 不 用 语 言 模 型 好 很 多, 但 是 和 考 虑 了 搭 配 概 率 的 二 元 语 言 模 型 相 比 要 差 很 多, 因 为 后 者 的 复 杂 度 只 有 20 信 息 论 中 仅 次 于 熵 的 另 外 两 个 重 要 的 概 念 是 互 信 息 (Mutual Information) 和 相 对 熵 (Kullback-Leibler Divergence) 互 信 息 是 信 息 熵 的 引 申 概 念, 它 是 对 两 个 随 机 事 件 相 关 性 的 度 量 比 如 说 今 天 随 机 事 件 北 京 下 雨 和 随 机 变 量 空 气 湿 度 的 相 关 性 就 很 大, 但 是 和 姚 明 所 在 的 休 斯 敦 火 箭 队 是 否 能 赢 公 牛 队 几 乎 无 关 互 信 息 就 是 用 来 量 化 度 量 这 种 相 关 性 的 在 自 然 语 言 处 理 中, 经 常 要 度 量 一 些 语 言 现 象 的 相 关 性 比 如 在 机 器 翻 译 中, 最 难 的 问 题 是 词 义 的 二 义 性 ( 歧 义 性 ) 问 题 比 如 Bush 一 词 可 以 是 美 国 总 统 的 名 字, 也 可 以 是 灌 木 丛 ( 有 一 个 笑 话, 美 国 上 届 总 统 候 选 人 凯 里 Kerry 的 名 字 被 一 些 机 器 翻 译 系 统 翻 译 成 了 " 爱 尔 兰 的 小 母 牛 ",Kerry 在 英 语 中 另 外 一 个 意 思 ) 那 么 如 何 27

32 数 学 之 美 正 确 地 翻 译 这 个 词 呢? 人 们 很 容 易 想 到 要 用 语 法 要 分 析 语 句 等 等 其 实, 至 今 为 止, 没 有 一 种 语 法 能 很 好 解 决 这 个 问 题, 真 正 实 用 的 方 法 是 使 用 互 信 息 具 体 的 解 决 办 法 大 致 如 下 : 首 先 从 大 量 文 本 中 找 出 和 总 统 布 什 一 起 出 现 的 互 信 息 最 大 的 一 些 词, 比 如 总 统 美 国 国 会 华 盛 顿 等 等, 当 然, 再 用 同 样 的 方 法 找 出 和 灌 木 丛 一 起 出 现 的 互 信 息 最 大 的 词, 比 如 土 壤 植 物 野 生 等 等 有 了 这 两 组 词, 在 翻 译 Bush 时, 看 看 上 下 文 中 哪 类 相 关 的 词 多 就 可 以 了 这 种 方 法 最 初 是 由 吉 尔 (Gale), 丘 奇 (Church) 和 雅 让 斯 基 (Yarowsky) 提 出 的 当 时 雅 让 斯 基 在 宾 西 法 尼 亚 大 学 是 自 然 语 言 处 理 大 师 马 库 斯 (Mitch Marcus) 教 授 的 博 士 生, 他 很 多 时 间 泡 在 贝 尔 实 验 室 丘 奇 等 人 的 研 究 室 里 也 许 是 急 于 毕 业, 他 在 吉 尔 等 人 的 帮 助 下 想 出 了 一 个 最 快 也 是 最 好 地 解 决 翻 译 中 的 二 义 性, 就 是 上 述 的 方 法, 这 个 看 上 去 简 单 的 方 法 效 果 好 得 让 同 行 们 大 吃 一 惊 雅 让 斯 基 因 而 只 花 了 三 年 就 从 马 库 斯 那 里 拿 到 了 博 士, 而 他 的 师 兄 弟 们 平 均 要 花 六 年 时 间 信 息 论 中 另 外 一 个 重 要 的 概 念 是 相 对 熵, 在 有 些 文 献 中 它 被 称 为 成 交 叉 熵 在 英 语 中 是 Kullback-Leibler Divergence, 是 以 它 的 两 个 提 出 者 库 尔 贝 克 和 莱 伯 勒 的 名 字 命 名 的 相 对 熵 用 来 衡 量 两 个 正 函 数 是 否 相 似, 对 于 两 个 完 全 相 同 的 函 数, 它 们 的 相 对 熵 等 于 零 在 自 然 语 言 处 理 中 可 以 用 相 对 熵 来 衡 量 两 个 常 用 词 ( 在 语 法 上 和 语 义 上 ) 是 否 同 义, 或 者 两 篇 文 章 28

33 数 学 之 美 的 内 容 是 否 相 近 等 等 利 用 相 对 熵, 我 们 可 以 到 处 信 息 检 索 中 最 重 要 的 一 个 概 念 : 词 频 率 - 逆 向 文 档 频 率 (TF/IDF) 我 们 下 回 会 介 绍 如 何 根 据 相 关 性 对 搜 索 出 的 网 页 进 行 排 序, 就 要 用 的 餐 TF/IDF 的 概 念 另 外, 在 新 闻 的 分 类 中 也 要 用 到 相 对 熵 和 TF/IDF 对 信 息 论 有 兴 趣 又 有 一 定 数 学 基 础 的 读 者, 可 以 阅 读 斯 坦 福 大 学 托 马 斯. 科 弗 (Thomas Cover) 教 授 的 专 著 " 信 息 论 基 础 "(Elements of Information Theory): m/ ?n= Code=17909 科 弗 教 授 是 当 今 最 权 威 的 信 息 论 专 家 1.8. 数 学 之 美 系 列 八 贾 里 尼 克 的 故 事 和 现 代 语 言 处 理 2006 年 6 月 8 日 上 午 09:15:00 发 表 者 :Google 研 究 员, 吴 军 读 者 也 许 注 意 到 了, 我 们 在 前 面 的 系 列 中 多 次 提 到 了 贾 里 尼 克 这 个 名 字 事 实 上, 现 代 语 音 识 别 和 自 然 语 言 处 理 确 实 是 和 它 的 名 字 是 紧 密 联 系 在 一 起 的 我 想 在 这 回 的 系 列 里, 介 绍 贾 里 尼 29

34 数 学 之 美 克 本 人 在 这 里 我 不 想 列 举 他 的 贡 献, 而 想 讲 一 讲 他 作 为 一 个 普 普 通 通 的 人 的 故 事 这 些 事 要 么 是 我 亲 身 经 历 的, 要 么 是 他 亲 口 对 我 讲 的 弗 莱 德 里 克. 贾 里 尼 克 (Fred Jelinek) 出 生 于 捷 克 一 个 富 有 的 犹 太 家 庭 他 的 父 母 原 本 打 算 送 他 去 英 国 的 公 学 ( 私 立 学 校 ) 读 书 为 了 教 他 德 语, 还 专 门 请 的 一 位 德 国 的 家 庭 女 教 师, 但 是 第 二 次 世 界 大 战 完 全 打 碎 了 他 们 的 梦 想 他 们 先 是 被 从 家 中 赶 了 出 去, 流 浪 到 布 拉 格 他 的 父 亲 死 在 了 集 中 营, 弗 莱 德 自 己 成 天 在 街 上 玩 耍, 完 全 荒 废 了 学 业 二 战 后, 当 他 再 度 回 到 学 校 时, 他 的 成 绩 一 塌 糊 涂, 全 部 是 D, 但 是 很 快 他 就 赶 上 了 班 上 的 同 学 不 过, 他 在 小 学 时 从 来 没 有 得 过 A 1949 年, 他 的 母 亲 带 领 全 家 移 民 美 国 在 美 国, 贾 里 尼 克 一 家 生 活 非 常 贫 困, 全 家 基 本 是 靠 母 亲 做 点 心 卖 钱 为 生, 弗 莱 德 自 己 十 四 五 岁 就 进 工 厂 打 工 补 助 全 家 贾 里 尼 克 最 初 想 成 为 一 个 律 师, 为 他 父 亲 那 样 的 冤 屈 者 辩 护, 但 他 很 快 意 识 到 他 那 浓 厚 的 外 国 口 音 将 使 他 在 法 庭 上 的 辩 护 很 吃 力 贾 里 尼 克 的 第 二 个 理 想 是 成 为 医 生, 他 想 进 哈 佛 大 学 医 学 院, 但 经 济 上 他 无 法 承 担 医 学 院 8 年 高 昂 的 学 费 与 此 同 时 麻 省 理 工 学 院 给 于 了 他 一 份 ( 为 东 欧 移 民 设 的 ) 全 额 奖 学 金 贾 里 尼 克 决 定 到 麻 省 理 工 学 电 机 工 程 在 那 里, 他 遇 到 了 信 息 论 的 鼻 祖 香 农 博 士, 和 语 言 学 大 师 贾 格 布 森 Roman Jakobson ( 他 提 出 了 著 名 的 通 信 六 功 能 )[ 注 释 一 ], 后 来 贾 里 尼 克 又 陪 着 太 太 听 最 30

35 数 学 之 美 伟 大 的 语 言 学 家 乔 姆 斯 基 (Noam Chomsky) 的 课 这 三 位 大 师 对 贾 里 尼 克 今 后 的 研 究 方 向 -- 利 用 信 息 论 解 决 语 言 问 题 产 生 的 重 要 影 响 贾 里 尼 克 从 麻 省 理 工 获 得 博 士 学 位 后, 在 哈 佛 大 学 教 了 一 年 书, 然 后 到 康 乃 尔 大 学 任 教 他 之 所 以 选 择 康 乃 尔 大 学, 是 因 为 找 工 作 时 和 那 里 的 一 位 语 言 学 家 谈 得 颇 为 投 机 当 时 那 位 教 授 表 示 愿 意 和 贾 里 尼 克 在 利 用 信 息 论 解 决 语 言 问 题 上 合 作 但 是, 等 贾 里 尼 克 到 康 乃 尔 以 后, 那 位 教 授 表 示 对 语 言 学 在 没 有 兴 趣 而 转 向 写 歌 剧 了 贾 里 尼 克 对 语 言 学 家 的 坏 印 象 从 此 开 始 加 上 后 来 他 在 IBM 时 发 现 语 言 学 家 们 嘴 上 头 头 是 道, 干 起 活 来 高 不 成 低 不 就, 对 语 言 学 家 从 此 深 恶 痛 绝 他 甚 至 说 :" 我 每 开 除 一 名 语 言 学 家, 我 的 语 音 识 别 系 统 错 误 率 就 降 低 一 个 百 分 点 " 这 句 话 后 来 在 业 界 广 为 流 传, 为 每 一 个 搞 语 音 识 别 和 语 言 处 理 的 人 所 熟 知 贾 里 尼 克 在 康 乃 尔 十 年 磨 一 剑, 潜 心 研 究 信 息 论, 终 于 悟 出 了 自 然 语 言 处 理 的 真 谛 1972 年, 贾 里 尼 克 到 IBM 华 生 实 验 室 (IBM T.G.Watson Labs) 做 学 术 休 假, 无 意 中 领 导 了 语 音 识 别 实 验 室, 两 年 后 他 在 康 乃 尔 和 IBM 之 间 选 择 了 留 在 IBM 在 那 里, 贾 里 尼 克 组 建 了 阵 容 空 前 绝 后 强 大 的 研 究 队 伍, 其 中 包 括 他 的 著 名 搭 档 波 尔 (Bahl), 著 名 的 语 音 识 别 Dragon 公 司 的 创 始 人 贝 克 夫 妇, 解 决 最 大 熵 迭 代 算 法 的 达 拉 皮 垂 (Della Pietra) 孪 生 兄 弟,BCJR 算 法 的 另 外 两 个 共 31

36 数 学 之 美 同 提 出 者 库 克 (Cocke) 和 拉 维 夫 (Raviv), 以 及 第 一 个 提 出 机 器 翻 译 统 计 模 型 的 布 朗 七 十 年 代 的 IBM 有 点 像 九 十 年 代 的 微 软 和 今 天 的 Google, 给 于 杰 出 科 学 家 作 任 何 有 兴 趣 研 究 的 自 由 在 那 种 宽 松 的 环 境 里, 贾 里 尼 克 等 人 提 出 了 统 计 语 音 识 别 的 框 架 结 构 在 贾 里 尼 克 以 前, 科 学 家 们 把 语 音 识 别 问 题 当 作 人 工 智 能 问 题 和 模 式 匹 配 问 题 而 贾 里 尼 克 把 它 当 成 通 信 问 题, 并 用 两 个 隐 含 马 尔 可 夫 模 型 ( 声 学 模 型 和 语 言 模 型 ) 把 语 音 识 别 概 括 得 清 清 楚 楚 这 个 框 架 结 构 对 至 今 的 语 音 和 语 言 处 理 有 着 深 远 的 影 响, 它 从 根 本 上 使 得 语 音 识 别 有 实 用 的 可 能 贾 里 尼 克 本 人 后 来 也 因 此 当 选 美 国 工 程 院 院 士 贾 里 尼 克 和 波 尔, 库 克 以 及 拉 维 夫 对 人 类 的 另 一 大 贡 献 是 BCJR 算 法, 这 是 今 天 数 字 通 信 中 应 用 的 最 广 的 两 个 算 法 之 一 ( 另 一 个 是 维 特 比 算 法 ) 有 趣 的 是, 这 个 算 法 发 明 了 二 十 年 后, 才 得 以 广 泛 应 用 IBM 于 是 把 它 列 为 了 IBM 有 史 以 来 对 人 类 最 大 贡 献 之 一, 并 贴 在 加 州 Amaden 实 现 室 墙 上 遗 憾 的 是 BCJR 四 个 人 已 经 全 部 离 开 IBM, 有 一 次 IBM 的 通 信 部 门 需 要 用 这 个 算 法, 还 得 从 斯 坦 福 大 学 请 一 位 专 家 去 讲 解, 这 位 专 家 看 到 IBM 橱 窗 里 的 成 就 榜, 感 慨 万 分 贾 里 尼 克 和 IBM 一 批 最 杰 出 的 科 学 家 在 九 十 年 代 初 离 开 了 IBM, 他 们 大 多 数 在 华 尔 街 取 得 了 巨 大 的 成 功 贾 里 尼 克 的 书 生 气 很 浓, 于 是 去 约 翰 霍 普 金 斯 大 学 建 立 了 世 界 著 名 的 CLSP 实 验 32

37 数 学 之 美 室 每 年 夏 天, 贾 里 尼 克 邀 请 世 界 上 名 顶 级 的 科 学 家 和 学 生 到 CLSP 一 起 工 作, 使 得 CLSP 成 为 世 界 上 语 音 和 语 言 处 理 的 中 心 之 一 贾 里 尼 克 治 学 极 为 严 谨, 对 学 生 要 求 也 极 严 他 淘 汰 学 生 的 比 例 极 高, 即 使 留 下 来 的, 毕 业 时 间 也 极 长 但 是, 另 一 方 面, 贾 里 尼 克 也 千 方 百 计 利 用 自 己 的 影 响 力 为 学 生 的 学 习 和 事 业 创 造 方 便 贾 里 尼 克 为 组 里 的 每 一 位 学 生 提 供 从 进 组 第 一 天 到 离 开 组 最 后 一 天 全 部 的 学 费 和 生 活 费 他 还 为 每 一 位 学 生 联 系 实 习 机 会, 并 保 证 每 位 学 生 在 博 士 生 阶 段 至 少 在 大 公 司 实 习 一 次 从 他 那 里 拿 到 博 士 学 位 的 学 生, 全 部 任 职 于 著 名 实 验 室, 比 如 IBM, 微 软,AT&T 和 Google 的 实 验 室 为 了 提 高 外 国 人 的 英 语 水 平, 贾 里 尼 克 用 自 己 的 经 费 为 他 们 请 私 人 英 语 教 师 贾 里 尼 克 生 活 俭 朴, 一 辆 老 式 丰 田 车 开 了 二 十 多 年, 比 组 里 学 生 的 车 都 破 他 每 年 都 邀 请 组 里 的 学 生 和 教 授 到 家 里 做 客, 很 多 毕 业 了 的 学 生 也 专 程 赶 来 聚 会 在 那 里, 他 不 再 谈 论 学 术 问 题, 而 会 谈 些 巩 俐 的 电 影 ( 他 太 太 是 哥 伦 比 亚 大 学 电 影 专 业 的 教 授 ), 或 是 某 著 名 教 授 被 拉 斯 韦 加 斯 的 赌 馆 定 为 不 受 欢 迎 的 人 等 等 但 是 他 聚 会 的 食 物 实 在 难 吃, 无 非 是 些 生 胡 萝 卜 和 芹 菜 后 来 贾 里 尼 克 掏 钱 让 系 里 另 一 个 教 授 承 办 聚 会, 那 个 教 授 每 次 请 专 业 大 厨 在 家 作 出 极 丰 盛 的 晚 宴, 并 准 备 许 多 美 酒, 从 此 这 种 聚 会 就 转 移 到 那 个 教 授 家 了 33

38 数 学 之 美 除 了 巩 俐 的 电 影, 贾 里 尼 克 对 中 国 的 了 解 就 是 清 华 大 学 和 青 岛 啤 酒 了 他 有 时 会 把 两 个 名 字 搞 混, 有 两 次 被 香 港 科 技 大 学 的 Pascale 冯 教 授 抓 住 贾 里 尼 克 说 话 心 直 口 快, 不 留 余 地 在 他 面 前 谈 论 学 术 一 定 要 十 分 严 谨, 否 则 很 容 易 被 他 抓 住 辫 子 除 了 刚 才 提 到 的 对 语 言 学 家 略 有 偏 见 的 评 论, 他 对 许 多 世 界 级 的 大 师 都 有 过 很 多 刻 薄 但 又 实 事 求 是 的 评 论, 这 些 评 论 在 业 界 广 为 流 传 贾 里 尼 克 在 四 十 多 年 的 学 术 生 涯 中 居 然 没 有 得 罪 太 多 的 人, 可 以 说 是 一 个 奇 迹 注 释 一 : 贾 格 布 森 的 通 信 模 型 1 上 下 文 2 信 息 3 发 送 着 接 收 者 5 信 道 6 编 码 34

39 数 学 之 美 1.9. 数 学 之 美 系 列 九 如 何 确 定 网 页 和 查 询 的 相 关 性 2006 年 6 月 27 日 上 午 09:53:00 发 表 者 : 吴 军,Google 研 究 员 [ 我 们 已 经 谈 过 了 如 何 自 动 下 载 网 页 如 何 建 立 索 引 如 何 衡 量 网 页 的 质 量 (Page Rank) 我 们 今 天 谈 谈 如 何 确 定 一 个 网 页 和 某 个 查 询 的 相 关 性 了 解 了 这 四 个 方 面, 一 个 有 一 定 编 程 基 础 的 读 者 应 该 可 以 写 一 个 简 单 的 搜 索 引 擎 了, 比 如 为 您 所 在 的 学 校 或 院 系 建 立 一 个 小 的 搜 索 引 擎 ] 我 们 还 是 看 上 回 的 例 子, 查 找 关 于 原 子 能 的 应 用 的 网 页 我 们 第 一 步 是 在 索 引 中 找 到 包 含 这 三 个 词 的 网 页 ( 详 见 关 于 布 尔 运 算 的 系 列 ) 现 在 任 何 一 个 搜 索 引 擎 都 包 含 几 十 万 甚 至 是 上 百 万 个 多 少 有 点 关 系 的 网 页 那 么 哪 个 应 该 排 在 前 面 呢? 显 然 我 们 应 该 根 据 网 页 和 查 询 原 子 能 的 应 用 的 相 关 性 对 这 些 网 页 进 行 排 序 因 此, 这 里 的 关 键 问 题 是 如 何 度 量 网 页 和 查 询 的 相 关 性 我 们 知 道, 短 语 原 子 能 的 应 用 可 以 分 成 三 个 关 键 词 : 原 子 能 的 应 用 根 据 我 们 的 直 觉, 我 们 知 道, 包 含 这 三 个 词 多 的 网 页 应 该 比 包 含 它 们 少 的 网 页 相 关 当 然, 这 个 办 法 有 一 个 明 显 的 漏 洞, 就 是 长 的 网 页 比 短 的 网 页 占 便 宜, 因 为 长 的 网 页 总 的 来 讲 包 含 的 关 键 词 要 多 些 因 此 我 们 需 要 根 据 网 页 的 长 度, 对 关 键 词 的 次 数 进 行 归 一 化, 也 就 是 用 关 键 词 的 次 数 除 以 网 页 的 总 字 35

40 数 学 之 美 数 我 们 把 这 个 商 称 为 关 键 词 的 频 率, 或 者 单 文 本 词 汇 频 率 (Term Frequency), 比 如, 在 某 个 一 共 有 一 千 词 的 网 页 中 原 子 能 的 和 应 用 分 别 出 现 了 2 次 35 次 和 5 次, 那 么 它 们 的 词 频 就 分 别 是 和 我 们 将 这 三 个 数 相 加, 其 和 就 是 相 应 网 页 和 查 询 原 子 能 的 应 用 相 关 性 的 一 个 简 单 的 度 量 概 括 地 讲, 如 果 一 个 查 询 包 含 关 键 词 w1,w2,...,wn, 它 们 在 一 篇 特 定 网 页 中 的 词 频 分 别 是 : TF1, TF2,..., TFN (TF: term frequency) 那 么, 这 个 查 询 和 该 网 页 的 相 关 性 就 是 : TF1 + TF TFN 读 者 可 能 已 经 发 现 了 又 一 个 漏 洞 在 上 面 的 例 子 中, 词 的 站 了 总 词 频 的 80% 以 上, 而 它 对 确 定 网 页 的 主 题 几 乎 没 有 用 我 们 称 这 种 词 叫 应 删 除 词 (Stopwords), 也 就 是 说 在 度 量 相 关 性 是 不 应 考 虑 它 们 的 频 率 在 汉 语 中, 应 删 除 词 还 有 是 和 中 地 得 等 等 几 十 个 忽 略 这 些 应 删 除 词 后, 上 述 网 页 的 相 似 度 就 变 成 了 0.007, 其 中 原 子 能 贡 献 了 0.002, 应 用 贡 献 了 细 心 的 读 者 可 能 还 会 发 现 另 一 个 小 的 漏 洞 在 汉 语 中, 应 用 是 个 很 通 用 的 词, 而 原 子 能 是 个 很 专 业 的 词, 后 者 在 相 关 性 排 名 中 比 前 者 重 要 因 此 我 们 需 要 给 汉 语 中 的 每 一 个 词 给 一 个 权 重, 这 个 权 重 的 设 定 必 须 满 足 下 面 两 个 条 件 : 36

41 数 学 之 美 1. 一 个 词 预 测 主 题 能 力 越 强, 权 重 就 越 大, 反 之, 权 重 就 越 小 我 们 在 网 页 中 看 到 原 子 能 这 个 词, 或 多 或 少 地 能 了 解 网 页 的 主 题 我 们 看 到 应 用 一 次, 对 主 题 基 本 上 还 是 一 无 所 知 因 此, 原 子 能 的 权 重 就 应 该 比 应 用 大 2. 应 删 除 词 的 权 重 应 该 是 零 我 们 很 容 易 发 现, 如 果 一 个 关 键 词 只 在 很 少 的 网 页 中 出 现, 我 们 通 过 它 就 容 易 锁 定 搜 索 目 标, 它 的 权 重 也 就 应 该 大 反 之 如 果 一 个 词 在 大 量 网 页 中 出 现, 我 们 看 到 它 仍 然 不 很 清 楚 要 找 什 么 内 容, 因 此 它 应 该 小 概 括 地 讲, 假 定 一 个 关 键 词 w 在 Dw 个 网 页 中 出 现 过, 那 么 Dw 越 大,w 的 权 重 越 小, 反 之 亦 然 在 信 息 检 索 中, 使 用 最 多 的 权 重 是 逆 文 本 频 率 指 数 (Inverse document frequency 缩 写 为 IDF), 它 的 公 式 为 log(d/ Dw) 其 中 D 是 全 部 网 页 数 比 如, 我 们 假 定 中 文 网 页 数 是 D= 10 亿, 应 删 除 词 的 在 所 有 的 网 页 中 都 出 现, 即 Dw=10 亿, 那 么 它 的 IDF=log(10 亿 /10 亿 )= log (1) = 0 假 如 专 用 词 原 子 能 在 两 百 万 个 网 页 中 出 现, 即 Dw=200 万, 则 它 的 权 重 IDF=log(500) =6.2 又 假 定 通 用 词 应 用, 出 现 在 五 亿 个 网 页 中, 它 的 权 重 IDF = log(2), 则 只 有 0.7 也 就 只 说, 在 网 页 中 找 到 一 个 原 子 能 的 比 配 相 当 于 找 到 九 个 应 用 的 匹 配 利 用 IDF, 上 述 相 关 性 计 算 个 公 式 就 由 词 频 的 简 单 求 和 变 成 了 加 权 求 和, 即 TF1*IDF1 + TF2*IDF TFN*IDFN 在 上 面 的 例 子 中, 该 网 页 和 原 子 能 的 应 用 的 相 关 37

42 数 学 之 美 性 为 , 其 中 原 子 能 贡 献 了 , 而 应 用 只 贡 献 了 这 个 比 例 和 我 们 的 直 觉 比 较 一 致 了 TF/IDF(term frequency/inverse document frequency) 的 概 念 被 公 认 为 信 息 检 索 中 最 重 要 的 发 明 在 搜 索 文 献 分 类 和 其 他 相 关 领 域 有 广 泛 的 应 用 讲 起 TF/IDF 的 历 史 蛮 有 意 思 IDF 的 概 念 最 早 是 剑 桥 大 学 的 斯 巴 克 - 琼 斯 [ 注 : 她 有 两 个 姓 ] (Karen Sparck Jones) 提 出 来 的 斯 巴 克 - 琼 斯 1972 年 在 一 篇 题 为 关 键 词 特 殊 性 的 统 计 解 释 和 她 在 文 献 检 索 中 的 应 用 的 论 文 中 提 出 IDF 遗 憾 的 是, 她 既 没 有 从 理 论 上 解 释 为 什 么 权 重 IDF 应 该 是 对 数 函 数 log(d/dw)( 而 不 是 其 它 的 函 数, 比 如 平 方 根 ), 也 没 有 在 这 个 题 目 上 作 进 一 步 深 入 研 究, 以 至 于 在 以 后 的 很 多 文 献 中 人 们 提 到 TF/IDF 时 没 有 引 用 她 的 论 文, 绝 大 多 数 人 甚 至 不 知 道 斯 巴 克 - 琼 斯 的 贡 献 同 年 罗 宾 逊 写 了 个 两 页 纸 的 解 释, 解 释 得 很 不 好 倒 是 后 来 康 乃 尔 大 学 的 萨 尔 顿 (Salton) 多 次 写 文 章 写 书 讨 论 TF/IDF 在 信 息 检 索 中 的 用 途, 加 上 萨 尔 顿 本 人 的 大 名 ( 信 息 检 索 的 世 界 大 奖 就 是 以 萨 尔 顿 的 名 字 命 名 的 ) 很 多 人 都 引 用 萨 尔 顿 的 书, 甚 至 以 为 这 个 信 息 检 索 中 最 重 要 的 概 念 是 他 提 出 的 当 然, 世 界 并 没 有 忘 记 斯 巴 克 - 琼 斯 的 贡 献,2004 年, 在 纪 念 文 献 学 学 报 创 刊 60 周 年 之 际, 该 学 报 重 印 了 斯 巴 克 - 琼 斯 的 大 作 罗 宾 逊 在 同 期 期 刊 上 写 了 篇 文 章, 用 香 农 的 信 息 论 解 释 IDF, 这 回 的 解 释 是 对 的, 但 文 章 写 的 并 不 好 非 常 冗 长 ( 足 足 十 八 页 ), 把 一 个 简 单 问 题 38

43 数 学 之 美 搞 复 杂 了 其 实, 信 息 论 的 学 者 们 已 经 发 现 并 指 出, 其 实 IDF 的 概 念 就 是 一 个 特 定 条 件 下 关 键 词 的 概 率 分 布 的 交 叉 熵 (Kullback-Leibler Divergence)( 详 见 上 一 系 列 ) 这 样, 信 息 检 索 相 关 性 的 度 量, 又 回 到 了 信 息 论 现 在 的 搜 索 引 擎 对 TF/IDF 进 行 了 不 少 细 微 的 优 化, 使 得 相 关 性 的 度 量 更 加 准 确 了 当 然, 对 有 兴 趣 写 一 个 搜 索 引 擎 的 爱 好 者 来 讲, 使 用 TF/IDF 就 足 够 了 如 果 我 们 结 合 上 网 页 排 名 (Page Rank), 那 么 给 定 一 个 查 询, 有 关 网 页 综 合 排 名 大 致 由 相 关 性 和 网 页 排 名 乘 积 决 定 数 学 之 美 系 列 十 有 限 状 态 机 和 地 址 识 别 2006 年 7 月 5 日 上 午 09:09:00 发 表 者 : 吴 军,Google 研 究 员 地 址 的 识 别 和 分 析 是 本 地 搜 索 必 不 可 少 的 技 术, 尽 管 有 许 多 识 别 和 分 析 地 址 的 方 法, 最 有 效 的 是 有 限 状 态 机 一 个 有 限 状 态 机 是 一 个 特 殊 的 有 向 图 ( 参 见 有 关 图 论 的 系 列 ), 它 包 括 一 些 状 态 ( 节 点 ) 和 连 接 这 些 状 态 的 有 向 弧 下 图 是 一 个 识 别 中 国 地 址 的 有 限 状 态 机 的 简 单 的 例 子 39

44 数 学 之 美 每 一 个 有 限 状 态 机 都 有 一 个 启 始 状 态 和 一 个 终 止 状 态 和 若 干 中 间 状 态 每 一 条 弧 上 带 有 从 一 个 状 态 进 入 下 一 个 状 态 的 条 件 比 如, 在 上 图 中, 当 前 的 状 态 是 省, 如 果 遇 到 一 个 词 组 和 ( 区 ) 县 名 有 关, 我 们 就 进 入 状 态 区 县 ; 如 果 遇 到 的 下 一 个 词 组 和 城 市 有 关, 那 么 我 们 就 进 入 市 的 状 态, 如 此 等 等 如 果 一 条 地 址 能 从 状 态 机 的 起 始 状 态 经 过 状 态 机 的 若 干 中 间 状 态, 走 到 终 止 状 态, 那 么 这 条 地 址 则 有 效, 否 则 无 效 比 如 说, 北 京 市 双 清 路 83 号 对 于 上 面 的 有 限 状 态 来 讲 有 效, 而 上 海 市 辽 宁 省 马 家 庄 则 无 效 ( 因 为 无 法 从 市 走 回 到 省 ) 使 用 有 限 状 态 机 识 别 地 址, 关 键 要 解 决 两 个 问 题, 即 通 过 一 些 有 效 的 地 址 建 立 状 态 机, 以 及 给 定 一 个 有 限 状 态 机 后, 地 址 字 串 的 匹 配 算 法 好 在 这 两 个 问 题 都 有 现 成 的 算 法 有 了 关 于 地 址 的 有 限 状 态 机 后, 我 们 就 可 又 用 它 分 析 网 页, 找 出 网 页 中 的 地 址 部 分, 建 立 本 地 搜 索 的 数 据 库 同 样, 我 们 也 可 以 对 用 户 输 入 的 查 询 进 行 分 析, 挑 出 其 中 描 述 地 址 的 部 分, 当 然, 剩 下 的 关 键 词 就 是 用 户 要 找 的 内 容 比 如, 对 于 用 户 输 入 的 北 京 市 双 清 路 附 40

45 数 学 之 美 近 的 酒 家,Google 本 地 会 自 动 识 别 出 地 址 北 京 市 双 清 路 和 要 找 的 对 象 酒 家 上 述 基 于 有 限 状 态 机 的 地 址 识 别 方 法 在 实 用 中 会 有 一 些 问 题 : 当 用 户 输 入 的 地 址 不 太 标 准 或 者 有 错 别 字 时, 有 限 状 态 机 会 束 手 无 策, 因 为 它 只 能 进 行 严 格 匹 配 ( 其 实, 有 限 状 态 机 在 计 算 机 科 学 中 早 期 的 成 功 应 用 是 在 程 序 语 言 编 译 器 的 设 计 中 一 个 能 运 行 的 程 序 在 语 法 上 必 须 是 没 有 错 的, 所 以 不 需 要 模 糊 匹 配 而 自 然 语 言 则 很 随 意, 无 法 用 简 单 的 语 法 描 述 ) 为 了 解 决 这 个 问 题, 我 们 希 望 有 一 个 能 进 行 模 糊 匹 配 并 给 出 一 个 字 串 为 正 确 地 址 的 可 能 性 为 了 实 现 这 一 目 的, 科 学 家 们 提 出 了 基 于 概 率 的 有 限 状 态 机 这 种 基 于 概 率 的 有 限 状 态 机 和 离 散 的 马 尔 可 夫 链 ( 详 见 前 面 关 于 马 尔 可 夫 模 型 的 系 列 ) 基 本 上 等 效 在 八 十 年 代 以 前, 尽 管 有 不 少 人 使 用 基 于 概 率 的 有 限 状 态 机, 但 都 是 为 自 己 的 应 用 设 计 专 用 的 有 限 状 态 机 的 程 序 九 十 年 代 以 后, 随 着 有 限 状 态 机 在 自 然 语 言 处 理 的 广 泛 应 用, 不 少 科 学 家 致 力 于 编 写 通 用 的 有 限 状 态 机 程 序 库 其 中, 最 成 功 的 是 前 AT&T 实 验 室 的 三 位 科 学 家, 莫 瑞 (Mohri), 皮 瑞 尔 (Pereira) 和 瑞 利 (Riley) 他 们 三 人 花 了 很 多 年 时 间, 编 写 成 一 个 通 用 的 基 于 概 率 的 有 限 状 态 机 C 语 言 工 具 库 由 于 AT&T 有 对 学 术 界 免 费 提 供 各 种 编 程 工 具 的 好 传 统, 他 们 三 人 也 把 自 己 多 年 的 心 血 拿 出 来 和 同 行 们 共 享 可 惜 好 景 不 长,AT&T 实 验 室 风 光 不 再, 这 41

46 数 学 之 美 三 个 人 都 离 开 了 AT&T, 莫 瑞 成 了 纽 约 大 学 的 教 授, 皮 瑞 尔 当 了 宾 西 法 尼 亚 大 学 计 算 机 系 系 主 任, 而 瑞 利 成 了 Google 的 研 究 员,AT&T 实 验 室 的 新 东 家 不 再 免 费 提 供 有 限 状 态 机 C 语 言 工 具 库 虽 然 此 前 莫 瑞 等 人 公 布 了 他 们 的 详 细 算 法, 但 是 省 略 了 实 现 的 细 节 因 此 在 学 术 界, 不 少 科 学 家 能 够 重 写 同 样 功 能 的 工 具 库, 但 是 很 难 达 到 AT&T 工 具 库 的 效 率 ( 即 运 算 速 度 ), 这 的 确 是 一 件 令 人 遗 憾 的 事 数 学 之 美 系 列 十 一 Google 阿 卡 47 的 制 造 者 阿 米 特. 辛 格 博 士 2006 年 7 月 10 日 上 午 09:52:00 发 表 者 :Google 研 究 员, 吴 军 枪 迷 或 者 看 过 尼 古 拉 斯. 凯 奇 (Nicolas Cage) 主 演 的 电 影 战 争 之 王 (Lord of War) 的 人 也 许 还 记 得 影 片 开 头 的 一 段 话 :( 在 所 有 轻 武 器 中,) 最 有 名 的 是 阿 卡 47( AK47) 冲 锋 枪 ( 也 就 是 中 国 的 五 六 式 冲 锋 枪 的 原 型 ), 因 为 它 从 不 卡 壳 从 不 损 坏 可 在 任 何 环 境 下 使 用 可 靠 性 好 杀 伤 力 大 并 且 操 作 简 单 我 认 为, 在 计 算 机 中 一 个 好 的 算 法, 应 该 向 阿 卡 47 冲 锋 枪 那 样 简 单 有 效 可 靠 性 好 而 且 容 易 读 懂 ( 或 者 说 易 操 作 ), 而 不 应 该 是 故 弄 玄 虚 Google 的 杰 出 工 程 师 阿 米 特. 辛 格 博 士 (Amit 42

47 数 学 之 美 Singhal) 就 是 为 Google 设 计 阿 卡 47 冲 锋 枪 的 人, 在 公 司 内 部,Google 的 排 序 算 法 便 是 以 他 的 名 字 命 名 的 从 加 入 Google 的 第 一 天, 我 就 开 始 了 和 辛 格 长 期 而 愉 快 的 合 作, 而 他 一 直 是 我 的 一 个 良 师 益 友 辛 格 Matt Cutts( 中 国 一 些 用 户 误 认 为 他 是 联 邦 调 查 局 特 工, 当 然 他 不 是 ) 马 丁 和 我 四 个 人 当 时 一 同 研 究 和 解 决 网 络 搜 索 中 的 作 弊 问 题 (Spam) 我 们 需 要 建 一 个 分 类 器, 我 以 前 一 直 在 学 术 界 工 作 和 学 习, 比 较 倾 向 找 一 个 很 漂 亮 的 解 决 方 案 我 设 计 了 一 个 很 完 美 的 分 类 器, 大 约 要 花 三 个 月 到 半 年 时 间 来 实 现 和 训 练, 而 辛 格 认 为 找 个 简 单 有 效 的 办 法 就 行 了 我 们 于 是 尽 可 能 简 化 问 题, 一 两 个 月 就 把 作 弊 的 数 量 减 少 了 一 半 当 时 我 们 和 公 司 工 程 副 总 裁 罗 森 打 了 个 赌, 如 果 我 们 能 减 少 40% 的 作 弊, 他 就 送 我 们 四 个 家 庭 去 夏 威 夷 度 假, 后 来 罗 森 真 的 履 约 了 这 个 分 类 器 设 计 得 非 常 小 巧 ( 只 用 很 小 的 内 存 ), 而 且 非 常 快 速 ( 几 台 服 务 器 就 能 处 理 全 球 搜 索 的 分 类 ), 至 今 运 行 得 很 好 后 来 我 和 辛 格 一 起 又 完 成 了 许 多 项 目, 包 括 对 中 日 韩 文 排 名 算 法 的 改 进 每 一 次, 辛 格 总 是 坚 持 找 简 单 有 效 的 解 决 方 案 这 种 做 法 在 Google 这 个 人 才 济 济 的 公 司 常 常 招 人 反 对, 因 为 很 多 资 深 的 工 程 师 怀 疑 这 些 简 单 方 法 的 有 效 性 不 少 人 试 图 用 精 确 而 复 杂 的 办 法 对 辛 格 的 设 计 的 各 种 阿 卡 47 进 行 改 进, 后 来 发 现 几 乎 所 有 时 候, 辛 格 的 简 单 方 法 都 接 近 最 优 化 的 解 决 方 案, 43

48 数 学 之 美 而 且 还 快 得 多 另 一 条 选 择 简 单 方 案 的 原 因 是 这 样 设 计 的 系 统 很 容 易 查 错 (debug) 当 然, 辛 格 之 所 以 总 是 能 找 到 那 些 简 单 有 效 的 方 法, 不 是 靠 直 觉, 更 不 是 撞 大 运, 而 是 靠 他 丰 富 的 研 究 经 验 辛 格 早 年 从 师 于 搜 索 大 师 萨 尔 顿 (Salton) 教 授, 毕 业 后 就 职 于 AT&T 实 验 室 在 那 里, 他 和 两 个 同 事 半 年 就 搭 起 了 一 个 中 等 规 模 的 搜 索 引 擎, 这 个 引 擎 索 引 的 网 页 数 量 虽 然 无 法 和 商 用 的 引 擎 相 比, 但 是 准 确 性 却 非 常 好 在 AT&T, 他 对 搜 索 问 题 的 各 个 细 节 进 行 了 仔 细 的 研 究, 他 的 那 些 简 单 而 有 效 的 解 决 方 案, 常 常 是 深 思 熟 虑 去 伪 存 真 的 结 果 辛 格 非 常 鼓 励 年 轻 人 不 怕 失 败, 大 胆 尝 试 一 次 一 位 刚 毕 业 不 久 的 工 程 师 因 为 把 带 有 错 误 的 程 序 推 出 到 Google 的 服 务 器 上 而 惶 惶 不 可 终 日 辛 格 安 慰 她 讲, 你 知 道, 我 在 Google 犯 的 最 大 一 次 错 误 是 曾 经 将 所 有 网 页 的 相 关 性 得 分 全 部 变 成 了 零, 于 是 所 有 搜 索 的 结 果 全 部 是 随 机 的 了 这 位 工 程 师 后 来 为 Google 开 发 了 很 多 好 的 产 品 辛 格 在 AT&T 时 确 立 了 他 在 学 术 界 的 地 位, 但 是, 他 不 是 一 个 满 足 于 做 实 验 写 论 文 的 人, 于 是 他 离 开 了 实 验 室 来 到 了 当 时 只 有 百 十 人 的 Google 在 这 里, 他 得 以 施 展 才 智, 重 写 了 Google 的 排 名 算 法, 并 且 一 直 在 负 责 改 进 它 辛 格 因 为 舍 不 得 放 下 两 个 孩 子, 很 少 参 加 各 种 会 议, 但 是 他 仍 然 被 学 术 界 公 认 为 是 当 今 最 权 威 的 网 络 搜 索 专 家 2005 年, 辛 格 作 为 杰 出 校 友 被 请 回 母 校 44

49 数 学 之 美 康 乃 尔 大 学 计 算 机 系 在 40 年 系 庆 上 作 报 告, 获 得 这 一 殊 荣 的 还 有 大 名 鼎 鼎 的 美 国 工 程 院 院 士, 计 算 机 独 立 磁 盘 冗 余 阵 列 (RAID) 的 发 明 人 凯 茨 (Randy Katz) 教 授 数 学 之 美 系 列 十 二 余 弦 定 理 和 新 闻 的 分 类 2006 年 7 月 20 日 上 午 10:12:00 发 表 者 : 吴 军,Google 研 究 员 余 弦 定 理 和 新 闻 的 分 类 似 乎 是 两 件 八 杆 子 打 不 着 的 事, 但 是 它 们 确 有 紧 密 的 联 系 具 体 说, 新 闻 的 分 类 很 大 程 度 上 依 靠 余 弦 定 理 Google 的 新 闻 是 自 动 分 类 和 整 理 的 所 谓 新 闻 的 分 类 无 非 是 要 把 相 似 的 新 闻 放 到 一 类 中 计 算 机 其 实 读 不 懂 新 闻, 它 只 能 快 速 计 算 这 就 要 求 我 们 设 计 一 个 算 法 来 算 出 任 意 两 篇 新 闻 的 相 似 性 为 了 做 到 这 一 点, 我 们 需 要 想 办 法 用 一 组 数 字 来 描 述 一 篇 新 闻 我 们 来 看 看 怎 样 找 一 组 数 字, 或 者 说 一 个 向 量 来 描 述 一 篇 新 闻 回 忆 一 下 我 们 在 如 何 度 量 网 页 相 关 性 一 文 中 介 绍 的 TF/IDF 的 概 念 对 于 一 篇 新 闻 中 的 所 有 实 词, 我 们 可 以 计 算 出 它 们 的 单 文 本 词 汇 频 率 / 逆 文 本 频 率 值 (TF/IDF) 不 难 想 象, 和 新 闻 主 题 有 关 的 那 些 实 词 频 率 高,TF/IDF 值 很 大 我 们 按 照 这 些 实 词 在 45

50 数 学 之 美 词 汇 表 的 位 置 对 它 们 的 TF/IDF 值 排 序 比 如, 词 汇 表 有 六 万 四 千 个 词, 分 别 为 单 词 编 号 汉 字 词 1 阿 2 啊 3 阿 斗 4 阿 姨 服 装 做 作 在 一 篇 新 闻 中, 这 64,000 个 词 的 TF/IDF 值 分 别 为 单 词 编 号 TF/IDF 值

51 数 学 之 美 如 果 单 词 表 中 的 某 个 次 在 新 闻 中 没 有 出 现, 对 应 的 值 为 零, 那 么 这 64,000 个 数, 组 成 一 个 64,000 维 的 向 量 我 们 就 用 这 个 向 量 来 代 表 这 篇 新 闻, 并 成 为 新 闻 的 特 征 向 量 如 果 两 篇 新 闻 的 特 征 向 量 相 近, 则 对 应 的 新 闻 内 容 相 似, 它 们 应 当 归 在 一 类, 反 之 亦 然 学 过 向 量 代 数 的 人 都 知 道, 向 量 实 际 上 是 多 维 空 间 中 有 方 向 的 线 段 如 果 两 个 向 量 的 方 向 一 致, 即 夹 角 接 近 零, 那 么 这 两 个 向 量 就 相 近 而 要 确 定 两 个 向 量 方 向 是 否 一 致, 这 就 要 用 到 余 弦 定 理 计 算 向 量 的 夹 角 了 余 弦 定 理 对 我 们 每 个 人 都 不 陌 生, 它 描 述 了 三 角 形 中 任 何 一 个 夹 角 和 三 个 边 的 关 系, 换 句 话 说, 给 定 三 角 形 的 三 条 边, 我 们 可 以 用 余 弦 定 理 求 出 三 角 形 各 个 角 的 角 度 假 定 三 角 形 的 三 条 边 为 a, b 和 c, 对 应 的 三 个 角 为 A, B 和 C, 那 么 角 A 的 余 弦 如 果 我 们 将 三 角 形 的 两 边 b 和 c 看 成 是 两 个 向 量, 那 么 上 述 公 式 等 价 于 47

52 数 学 之 美 其 中 分 母 表 示 两 个 向 量 b 和 c 的 长 度, 分 子 表 示 两 个 向 量 的 内 积 举 一 个 具 体 的 例 子, 假 如 新 闻 X 和 新 闻 Y 对 应 向 量 分 别 是 x1,x2,...,x64000 和 y1,y2,...,y64000, 那 么 它 们 夹 角 的 余 弦 等 于, 当 两 条 新 闻 向 量 夹 角 的 余 弦 等 于 一 时, 这 两 条 新 闻 完 全 重 复 ( 用 这 个 办 法 可 以 删 除 重 复 的 网 页 ); 当 夹 角 的 余 弦 接 近 于 一 时, 两 条 新 闻 相 似, 从 而 可 以 归 成 一 类 ; 夹 角 的 余 弦 越 小, 两 条 新 闻 越 不 相 关 我 们 在 中 学 学 习 余 弦 定 理 时, 恐 怕 很 难 想 象 它 可 以 用 来 对 新 闻 进 行 分 类 在 这 里, 我 们 再 一 次 看 到 数 学 工 具 的 用 途 48

53 数 学 之 美 数 学 之 美 系 列 十 三 信 息 指 纹 及 其 应 用 2006 年 8 月 3 日 上 午 11:17:00 发 表 者 : 吴 军,Google 研 究 员 任 何 一 段 信 息 文 字, 都 可 以 对 应 一 个 不 太 长 的 随 机 数, 作 为 区 别 它 和 其 它 信 息 的 指 纹 (Fingerprint) 只 要 算 法 设 计 的 好, 任 何 两 段 信 息 的 指 纹 都 很 难 重 复, 就 如 同 人 类 的 指 纹 一 样 信 息 指 纹 在 加 密 信 息 压 缩 和 处 理 中 有 着 广 泛 的 应 用 我 们 在 图 论 和 网 络 爬 虫 一 文 中 提 到, 为 了 防 止 重 复 下 载 同 一 个 网 页, 我 们 需 要 在 哈 希 表 中 纪 录 已 经 访 问 过 的 网 址 (URL) 但 是 在 哈 希 表 中 以 字 符 串 的 形 式 直 接 存 储 网 址, 既 费 内 存 空 间, 又 浪 费 查 找 时 间 现 在 的 网 址 一 般 都 较 长, 比 如, 如 果 在 Google 或 者 百 度 在 查 找 数 学 之 美, 对 应 的 网 址 长 度 在 一 百 个 字 符 以 上 下 面 是 百 度 的 链 接 AE%C3%C0&sr=&z=&cl=3&f=8 &wd=%ce%e2%be%fc+%ca%fd%d1%a7%d6%ae%c3%c0&ct=0 假 定 网 址 的 平 均 长 度 为 一 百 个 字 符, 那 么 存 贮 200 亿 个 网 址 本 身 至 少 需 要 2 TB, 即 两 千 GB 的 容 量, 考 虑 到 哈 希 表 的 存 储 效 率 一 般 只 有 50%, 实 际 需 要 的 内 存 在 4 TB 以 上 即 使 把 这 些 49

54 数 学 之 美 网 址 放 到 了 计 算 机 的 内 存 中, 由 于 网 址 长 度 不 固 定, 以 字 符 串 的 形 式 查 找 的 效 率 会 很 低 因 此, 我 们 如 果 能 够 找 到 一 个 函 数, 将 这 200 亿 个 网 址 随 机 地 映 射 到 128 二 进 位 即 16 个 字 节 的 整 数 空 间, 比 如 将 上 面 那 个 很 长 的 字 符 串 对 应 成 一 个 如 下 的 随 机 数 : 这 样 每 个 网 址 只 需 要 占 用 16 个 字 节 而 不 是 原 来 的 一 百 个 这 就 能 把 存 储 网 址 的 内 存 需 求 量 降 低 到 原 来 的 1/6 这 个 16 个 字 节 的 随 机 数, 就 称 做 该 网 址 的 信 息 指 纹 (Fingerprint) 可 以 证 明, 只 要 产 生 随 机 数 的 算 法 足 够 好, 可 以 保 证 几 乎 不 可 能 有 两 个 字 符 串 的 指 纹 相 同, 就 如 同 不 可 能 有 两 个 人 的 指 纹 相 同 一 样 由 于 指 纹 是 固 定 的 128 位 整 数, 因 此 查 找 的 计 算 量 比 字 符 串 比 较 小 得 多 网 络 爬 虫 在 下 载 网 页 时, 它 将 访 问 过 的 网 页 的 网 址 都 变 成 一 个 个 信 息 指 纹, 存 到 哈 希 表 中, 每 当 遇 到 一 个 新 网 址 时, 计 算 机 就 计 算 出 它 的 指 纹, 然 后 比 较 该 指 纹 是 否 已 经 在 哈 希 表 中, 来 决 定 是 否 下 载 这 个 网 页 这 种 整 数 的 查 找 比 原 来 字 符 串 查 找, 可 以 快 几 倍 到 几 十 倍 产 生 信 息 指 纹 的 关 键 算 法 是 伪 随 机 数 产 生 器 算 法 (prng) 最 早 的 prng 算 法 是 由 计 算 机 之 父 冯 诺 伊 曼 提 出 来 的 他 的 办 法 非 常 简 单, 就 是 将 一 个 数 的 平 方 掐 头 去 尾, 取 中 间 的 几 位 数 比 如 一 个 四 位 的 二 进 制 数 1001( 相 当 于 十 进 制 的 9), 其 平 方 为 ( 十 进 制 的 81) 掐 头 去 尾 剩 下 中 间 的 四 位 0100 当 然 50

55 数 学 之 美 这 种 方 法 产 生 的 数 字 并 不 很 随 机, 也 就 是 说 两 个 不 同 信 息 很 有 可 能 有 同 一 指 纹 现 在 常 用 的 MersenneTwister 算 法 要 好 得 多 信 息 指 纹 的 用 途 远 不 止 网 址 的 消 重, 信 息 指 纹 的 的 孪 生 兄 弟 是 密 码 信 息 指 纹 的 一 个 特 征 是 其 不 可 逆 性, 也 就 是 说, 无 法 根 据 信 息 指 纹 推 出 原 有 信 息, 这 种 性 质, 正 是 网 络 加 密 传 输 所 需 要 的 比 如 说, 一 个 网 站 可 以 根 据 用 户 的 Cookie 识 别 不 同 用 户, 这 个 cookie 就 是 信 息 指 纹 但 是 网 站 无 法 根 据 信 息 指 纹 了 解 用 户 的 身 份, 这 样 就 可 以 保 护 用 户 的 隐 私 在 互 联 网 上, 加 密 的 可 靠 性, 取 决 于 是 否 很 难 人 为 地 找 到 拥 有 同 一 指 纹 的 信 息, 比 如 一 个 黑 客 是 否 能 随 意 产 生 用 户 的 cookie 从 加 密 的 角 度 讲 MersenneTwister, 算 法 并 不 好, 因 为 它 产 生 的 随 机 数 有 相 关 性 互 联 网 上 加 密 要 用 基 于 加 密 伪 随 机 数 产 生 器 (csprng) 常 用 的 算 法 有 MD5 或 者 SHA1 等 标 准, 它 们 可 以 将 不 定 长 的 信 息 变 成 定 长 的 128 二 进 位 或 者 160 二 进 位 随 机 数 值 得 一 提 的 事, SHA1 以 前 被 认 为 是 没 有 漏 洞 的, 现 在 已 经 被 中 国 的 王 小 云 教 授 证 明 存 在 漏 洞 但 是 大 家 不 必 恐 慌, 因 为 这 和 黑 客 能 真 正 攻 破 你 的 注 册 信 息 是 还 两 回 事 信 息 指 纹 的 虽 然 历 史 很 悠 久, 但 真 正 的 广 泛 应 用 是 在 有 了 互 联 网 以 后, 这 几 年 才 渐 渐 热 门 起 来 51