Ｉ Ｓ Ｓ Ｎ １ ０ ０ ４ — ９ ０３ ７ ， ＣＯＤＥＮ Ｓ ＣＹＣＥ４
Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｄａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０， Ｎｏ ．１ ， Ｊ ａ ｎ ． ２ ０ １ ５， Ｐ Ｐ ． ３ ５— ４ ６ Ｄ ｏＩ ： １ ０ ． １ ６ ３ ３ ７ ／ ｊ ． １ ０ ０ ４ — ９ ０ ３ ７ ． ２ ０ １ ５ ． ０ １ ． ０ ０ ３
ｈ ｔ ｔ ｐ ： ／ ／ ｓ ｊ ｃ ｊ ． ｎ ｕ ａ ａ ． ｅ ｄ ｕ ． ｃ ｎ Ｅ — ｍａ ｉ ｌ ： ｓ ｊ ｃ ｊ ＠ｎ ｕ ａ ａ ． ｅ ｄ ｕ ． ｃ ａ Ｔｅ ｌ ／ Ｆａ ｘ： ＋８ ６ － ０ ２ ５ — ８ ４ ８ ９ ２ ７ ４２
◎ ２ ０ １ ５ ｂ ｙ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｄ ａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ
Ｌａ ｓ ｓ ｏ问题 的最 新 算 法研 究
刘 柳 陶大程
（ 悉 尼 科 技 大 学 工 程 与信 息 技 术 学 院量 子 计 算 与 智 能 系 统 研 究 中心 ， 悉尼 ， 澳 大利 亚 ， ２ ０ ０ ７ ）
摘 要 ：随 着 大规 模 数 据 的增 加 ， 解决 Ｌ ａ ｓ ｓ ｏ问题 成 为 一 个新 的 热 点 ， 以往 的 方 法很 难 满 足 大 数 据 背 景 下 的 时 间 和 效 率 问题 。为 了解 决 大规 模 数 据 及 高维 数 据 而 带 来 的 计 算 和 储 存 的 困难 ， 本 文 从 三 个 方 面 分析 最 新 的 算 法 ， 即一阶方法 、 随 机 方 法及 并 行 和 分 布 计 算 。本 文 介 绍 和 分 析 了解 决 最 小收 缩 和 选 择 算
子（ Ｌ ｅ ａ ｓ ｔ ａ ｂ ｓ ｏ ｌ ｕ ｔ ｅ ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ａ ｎ ｄ ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ， Ｌ ａ ｓ ｓ ｏ ） 问题 的 最 新 算 法 ： 梯度下降方法 、 交 替 方 向 乘
子 法（ Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ，ＡＤ ＭＭ ） 和 坐标 下 降 方 法 。其 中梯 度 下 降 结合 一 阶 方 法 和 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的 加 速 和 光 滑技 术 ； 交替 方 向 乘 子 方 法 将 随 机 方 法 融 入 在 最 新 的 算 法 中； 坐 标 下 降 方 法
利 用其 坐标 系的 特 点 结 合 一 阶 方 法 、 随机方法和并行和分布计算 ， 本 文 分 别 从 原 始 目标 函数 和 对 偶 目标
函数 的 角度 对 算 法进 行 分 析 和研 究 。
关 键 词 ：Ｌ ａ ｓ ｓ ｏ问题 ； 一阶方 法； 随机 方 法 ； 交替 方 向 乘子 法 ； 坐标 下 降
中 图分 类 号 ：ＴＰ１ ８ １ 文献 标 志 码 ： Ａ
Ｒｅ ｖ ｉ ｅ ｗ ｏ ｎ Ｒｅ ｃ ｅ ｎ ｔ Ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ Ｓ ｏ ｌ ｖ ｉ ｎｇ Ｌａ ｓ ｓ ｏ Ｐｒ ｏ ｂ ｌ ｅ ｍ
Ｌｉ ｕ Ｌｉ ｕ，Ｄａ ｃ ｈ ｅ ｎ ｇ Ｔａ ｏ
（ Ｑｕ ａ ｎｔ ｕｍ Ｃｏ ｍｐ ｕｔ ａ ｔ ｉ ｏ ｎ＆ Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎｔ Ｓｙ ｓ ｔ ｅ ｍｓ ，Ｆａ ｃ ｕ ｌ ｔ ｙ ｏ ｆ Ｅｎ ｇ ｉ ｎ ｅ ｅ ｒ ｉ ｎ ｇ ａ ｎ ｄ Ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ Ｔｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ，Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ｏ ｆ Ｔｅ ｃ ｈ ｎｏ ｌ ｏ ｇ ｙ。
Ｓ ｙ ｄ ｎ ｅ ｙ ，Ａｕｓ ｔ ｒ ａ ｌ ｉ ａ ，２ ０ ０ ７ ）
Ａｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ｗ ｉ ｔ ｈ ｔ ｈｅ ｉ ｎｃ ｒ ｅ ａ ｓ ｅ ｏ ｆ ｂ ｉ ｇ ｄ ａ ｔ ａ ，ｓ ｏ ｌ ｖ ｉ ｎ ｇ Ｌａ ｓ ｓ ｏ ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｂ ｅ ｃ ｏ ｍｅ ｓ ｔ ｏ ｐ ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ ｆ ｉ ｅ ｌ ｄ ．Ｐａ ｓ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ｃ ｏ ｕ ｌ ｄ ｎ ｏ ｔ ｓ ａ ｔ ｉ ｓ ｆ ｙ ｔ ｈ ｅ ｔ ｉ ｍｅ ａ ｎ ｄ ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｔ ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｕ ｎｄ ｅ ｒ ｂ ｉ ｇ ｄ ａ ｔ ａ ｓ ｉ ｔ ｕ ａ ｔ ｉ ｏ ｎ ．Ｉ ｎ ｏ ｒ ｄ ｅ ｒ ｔ ｏ ｄ ｅ ａ ｌ ｗｉ ｔ ｈ ｄ ｉ ｆ ｆ ｉ ｃ ｕ ｌ ｔ ｙ ｏ ｆ ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ ａ ｎ ｄ ｓ ｔ ｏ ｒ ａ ｇｅ ｂ ｒ ｉ ｎ ｇ ｉ ｎ ｇ ｆ ｒ ｏ ｍ ｈ ｕ ｇ ｅ — ｓ ｃ ａ ｌ ｅ ａ ｎｄ ｈ ｉ ｇ ｈ — ｄ ｉ ｍｅ ｎ ｓ ｉ ｏ ｎ ｄ ａ ｔ ａ，ｔ ｈ ｉ ｓ ｐ ａ ｐ ｅ ｒ ａ ｎ ａ ｌ ｙ ｚ ｅ ｔ ｈｅ ｒ ｅ ｃ ｅ ｎ ｔ Ｌａ ｓ ｓ ｏ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｆ ｒ ｏ ｍ ｔ ｈ ｒ ｅ ｅ ａ ｓ ｐ ｅ ｃ ｔ ｓ：ｏ ｎ ｅ — ｏ ｒ ｄ ｅ ｒ ｍｅ ｔ ｈ ｏ ｄ，ｒ ａ ｎ ｄ ｏ ｍ ，ａ ｎ ｄ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ａ ｎ ｄ ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ ｃ ｏ ｍｐ ｕ ｔ ａ — ｔ ｉ ｏ ｎ，ｗｈ ｉ ｃ ｈ ｐ ｌ ａ ｙ ａ ｎ ｉ ｍｐ ｏ ｒ ｔ ａ ｎ ｔ ｒ ｏ ｌ ｅ ｓ ｉ ｎ ｄ ｅ ａ ｌ ｉ ｎｇ ｗｉ ｔ ｈ ｈ ｕｇ ｅ — ｓ ｃ ａ ｌ ｅ ｄ ａ ｔ ａ ｐ ｒ ｏ ｂｌ ｅ ｍ ． Ｂａ ｓ ｅ ｄ ｏ ｎ ｔ ｈ ｏ ｓ ｅ ｔ ｈ ｒ ｅ ｅ ａ ｓ — ｐ ｅ ｃ ｔ ｓ ，ｔ ｈ ｉ ｓ ｐ ａ ｐｅ ｒ ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｅ ｓ ａ ｎ ｄ ａ ｎ ａ ｌ ｙ ｚ ｅ ｓ ｔ ｈ ｅ ｎ ｏ ｖ ｅ ｌ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ：ｇｒ ａ ｄ ｉ ｅ ｎ ｔ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ，Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ Ｄｉ — ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ（ Ａ ＤＭ Ｍ ），ａ ｎ ｄ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ． Ｇｒ ａ ｄ ｉ ｅ ｎ ｔ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｃ ｏ ｍ—
ｂ ｉ ｎ ｅ ｏ ｎ ｅ — ｏ ｒ ｄ ｅ ｒ ｍｅ ｔ ｈ ｏ ｄ ａ ｎｄ Ｎｅ ｓ ｔ ｅ ｒ ｏｖ Ｓ ａ ｃ ｃ ｅ ｌ ｅ ｒ ａ ｔ ｅ ａ ｎ ｄ ｓ ｍｏ ｏ ｔ ｈ ｉ ｎｇ ｍｅ ｔ ｈ ｏ ｄ； Ａ ＤＭ Ｍ ｐ ｕ ｔ ｔ ｈ ｅ ｒ ａ ｎ ｄ ｏ ｍ ａ ｌ ｇ ｏ — ｒ ｉ ｔ ｈｍ ｉ ｎ ｔ ｏ ｔ ｈ ｅ ｒ ｅ ｃ ｅ ｎｔ ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ；Ｃｏ ｏ ｒ ｄ ｉ ｎａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍａ ｋ ｅ ｕ ｓ ｅ Ｏ ｆ ｔ ｈｅ ｃ ｈ ａ ｒ ａ ｃ ｔ ｅ ｒ ｏ ｆ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｓ ｙ ｓ ｔ ｅ ｍ ｉ ｎ ｃ ｏ ｒ —
ｐ ｏ ｒ ａ ｔ ｉ ｏ ｎ ｏ ｎ ｅ — ｏｒ ｄ ｅ ｒ ｍｅ ｔ ｈ ｏ ｄ， ｒ ａ ｎｄ ｏ ｍ ，ａ ｎ ｄ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ａ ｎｄ ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ ． Ｍｏ ｒ ｅ ｏ ｖ ｅ ｒ ，ｔ ｈ ｉ ｓ ｐ ａ ｐ ｅ ｒ
ｍａ ｋ ｅ ｓ ａ ｄ ｅ ｅ ｐ ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ａ ｎ ｄ ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ ｆ ｒ ｏ ｍ ｐ ｒ ｉ ｍａ ｌ ａ ｎ ｄ ｄ ｕ ａ ｌ ｏ ｂ ｊ ｅ ｃ ｔ ｉ ｖ ｅ ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ．
Ｋｅ ｙ ｗｏ ｒ ｄ ｓ ：Ｌａ ｓ ｓ ｏ ｐ ｒ ｏ ｂ ｌ ｅ ｍ ；ｏ ｎ ｅ — ｏ ｒ ｄ ｅ ｒ ｍｅ ｔ ｈ ｏ ｄ；ｒ ａ ｎｄ ｏ ｍ ｍｅ ｔ ｈ ｏ ｄ；ＡＤＭ Ｍ ；ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎｔ ｍｅ ｔ ｈ ｏ ｄ
收稿 日期 ： ２ ０ １ ４ — １ ０ — １ ０ ； 修 订 日期 ： ２ ０ １ ４ — １ ２ － ３ ０
３ ６
数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｉ Ｄ ａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５
引
言
随 着 科技 的进 步 ， 收 集 数 据 的技 术 也 有 了 很 大 的 发 展 。 因此 如 何 有 效 地 从 数 据 中挖 掘 出有 用 的 信
息 也 越 来 越 受 到 人们 的关 注 。一 般 采 用 基 于 机 器学 习 和 统 计 的方 法 来 解 决 大 规 模 数 据 ， 这 种 趋 势 称 为 “ 大数据” 。它在 很 多领 域 中起 着 非 常 重 要 的 作 用 ， 如人工智 能 、 网络 应 用 、 计算生 物 、 医学 、 金 融 和 市 场
等 。虽 然 应 用在 不 同 的方 面 ， 但 是 大 数 据 问 题 却 又 几个 共 同 的特 点 ： （ １ ） 数据量非常大 ， 包 含 几 百 万 个 或 上亿个训练样本 ； （ ２ ） 数 据 的维 度 很 高 ， 通 常 会详 细 记 录 每 一 个 样 本 的 的信 息 ； （ ３ ） 大 规模 的 数 据 通 常 以
分 布 式 的 方 式储 存 或 收集 。在 机 器 学 习 的算 法 中 ， 对 最 新 算 法 的要 求 既 能 够 解 决 数 据 的 复 杂 性 又 能 够 采 用 平 行 或 分 布 式 的 方 法处 理 大数 据 。 Ｌ ａ ｓ ｓ ｏ问题 是 １ ９ ９ ６年 Ｔｉ ｂ ｓ ｈ ｉ ｒ ａ ｎ ｉ 使 用 ｕ 惩 罚 因 子解 决 含 有 独 立 高 斯 分 布 的 线 性 回归 问 题 ， Ｌ ａ ｓ ｓ ｏ 问题 包 含 平 方 误 差 的 求 和 以及 Ｌ１正 则 化 项 。虽 然 Ｌ ａ ｓ ｓ ｏ问题 出 现 的 比较 晚 ， 然而正则 化项 早在 １ ９ ４ ３
年 Ｔ ｉ ｋ ｈ ｏ ｎ ｏ ｖ 就 提 出用 来 逼 近 不 可解 的 整数 等 式 问 题 。通 常 情 况 下 ， 在 参 数 中增 加 约 束 化 项 ， 用 来 求 解
评 估 问题 ， 如 最 大 似 然 函 数 。正 则 化 项 用 来 减 小 变 量 从 而 避 免 过 拟 合 ， 得 到 的正则化 项 的解更 稳 定 ， Ｂ ｉ ｃ ｋ ｅ ｌ ｌ ２ 给 出 了 正则 化 项 在 统 计 理 论 中详 细 的 分 析 。
Ｌ ａ ｓ ｓ ｏ问题 在 解 决 稀 疏 规 划 中起 着 非 常 重 要 的作 用 。它 可 以解 释 为 寻 找 最 小 二 乘 或 线 性 回归 问 题 的稀 疏 问题 ， 即采 用 若 干 个 非零 的 变量 。Ｌ ａ ｓ ｓ ｏ问题 在 信 号 处 理 领 域 中 同 样 起 着 重 要 的作 用 ， 包 括 解 决 稀疏 信 号修 复 、 稀疏 回 归 ］ 、 稀 疏 图 回 归 ］ ， 稀 疏 逆 协 方 差 和 稀 疏 字 典 的 学 习口 ］ 。生 物 数 据 的 分
析 ］ ， 比如 选 取 大 数 据 中 的－ －４ ， 部 分 来 预 测 结 果 。Ｌ ａ ｓ ｓ ｏ问题 同 样 可 以应 用 在 视 频 中 ， Ｇｅ ｎ ｇ 采 用 并 行 Ｌ ａ ｓ ｓ ｏ的 方 法 解决 大 规 模 视 频 概 念 检 测 ， Ｚ ｈ ｕ ｌ ５ 使 用 Ｇｒ ｏ ｕ ｐ Ｌ ａ ｓ ｓ ｏ解 决 视 频 标 签 以及 Ｚ ｈ ｏ ｕ 用 稀疏 离 群
值分 割移 动 目标 。在 图像 处 理 中 ， Ａ ｆ ｏ ｎ ｓ ｏ 使用 Ｌ ａ ｓ ｓ ｏ方法 解 决 图像 修 复 、 图像 去 噪 和 去 模 糊 ， 其 中正 则 化项 是 图像 的梯 度 范 数 、 网页 图 像 排 序 及 图像 质 量 评 估 ， 利 用 稀 疏 编码 处 理 图像 标 签 问
题 。在 遥感 领域 中 ， Ｌ ａ ｓ ｓ ｏ问题 用 来 解 决 稀 疏 解 混 删 ， 从 而 可 以得 到 每 个 端 元 都 含 有 哪 些 物 质 ， 在 航 天、 农业领域 ， 对 研 究 物 质 成 分 问题 起 着 非 常 重 要 的 作 用 。 解决 Ｉ ａ ｓ ｓ ｏ问题 的方 法 有 很 多 ， 其中Ｅ ｆ ｒ ｏ ｎ ＿ １ ２ ０ ０ ４年 提 出 最 小 角 回 归 ， 它 能 够 有 效 地 解 决 潜 在 的
Ｌ ａ ｓ ｓ ｏ 优 化 问题 ， 同时 在 统 计 和 机 器 学 习 领域 ， 它 为加速 Ｌ ａ ｓ ｓ ｏ算 法 提 供 了一 个 重 要 的 工 具 。在 解 决 大
规模数据问题 中， 梯 度下 降方 法 是 最 简 单 的方 法 。Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 提 出最 优 的 梯 度 下 降 方 法 和 光 滑 模 型 ，
在 Ｌ ａ ｓ ｓ ｏ问 题 中 被广 泛 的应 用 ， 如 快 速 的 交 替 方 向优 化 方 法 ， 锥 模 型 优 化 方 法 以 及 快 速 迭 代 收 缩
阈值 方 法 。随 着 数 据 量 的 增加 ， ＡＤＭＭ 能 够 解 决 大 数 据 问题 ， 并且 已经成 功地应 用在很 多领域 ， 包
括解决 Ｌ ａ ｓ ｓ ｏ问 题 ， Ｂｅ ｃ ｋ ｌ ２ 结 合 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的加 速 方 法 ， 提 出了快速 的方法 ， 其中Ｔ ｏ ｍ［ ２ 提 出 了 快 速 的
Ａ Ｄ ＭＭ 方 法 。最 近 的研 究 者 Ｔ ａ ｉ ｊ ｉ ＿ ２ 驯 和 Ｈｕ ａ 。 结 合大数据 的特点 采用随机 的方法 ， 在 原 有 算 法 的 基 础上 ， 提 高 了算 法 的收 敛 率 ， 在 大 数 据 背 景 下 随 机 坐 标 下 降 方法 成 为一 个 新 的热 点 ， 而 随 机 优 化 方 法 在 解 决 高 维 数 据 和 大 规 模 样 本 有 至关 重 要 的作 用 。Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ ｌ ２ 和 Ｊ ｉ ［ 。 分 别 给 出 了随 机 坐标 下 降方 法 的理 论 分 析 和 证 明 。越 来 越 多 的 基 于 随机 优 化 方 法 出 现 在 Ｌ ａ ｓ ｓ ｏ问 题 ， 包 括 原 始 随 机 坐 标 下 降 方 法 法口 和 原 始 随 机 对偶 坐标 下 降方 法 ， 对 偶 随 机 坐 标 下 降 方 ， 而 且 基 本 的 随 机 下 降 坐 标 方 法 结 合 了 一 阶 最 优 方 法【 ３ 、 随
机 方 法 和并 行分 布 系统 ， 这 三 个 方 面 在 解 决 大 规模 数 据 中起 着 非 常 重 要 的作 用 ， 弥 补 了一 般 算 法 在 大 数
据背景下的不足 ， 其 中 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ加 速 的一 阶 最 优 方 法 ， 只需要 一阶梯度 信息 ， 从 而运算 复杂度 小 、 速 度
快； 随 机 的 方 法 主要 考 虑大 数 据 的本 质 ， 因为 最 终 决 定 最 优 解 的 信 息 并 不 需 要 全 部 的 数 据 ， 如 果 全 部 的
数据都用 来 计 算 不 仅 需 要 更 多储 存 空 间， 而且会 消耗更多 的时间， 从 而 影 响 算 法 的 性 能 。 最 近
Ａｖ ｒ ｏ ｎ 训 介 绍 了在 随 机 梯 度 和 随 机 坐 标 下 降 方 法 下 的 多 核 运 算 ， 算 法 中提 出异 步 并 行计 算 提 高 收敛 率 。
在 Ｋａ ｃ ｚ ｍａ ｒ ｚ 算 法 和 坐 标 下 降
刘柳 等 ： Ｌ ａ ｓ ｓ ｏ问题 的 最 新 算 法 研 究
３ ７
在解决 Ｌ ａ ｓ ｓ ｏ问 题 的过 程 中 ， 很 多 实 验 室 公 开 了软 件 包 和 代 码 ， 以供 大 家 学 习 和 研 究 ， 其 中包 含 凸
优化模型框架 Ｃ Ｖ Ｘ ， 它 可 以用 来 解 决所 有 的 凸优 化 问题 ； 压缩感知包 １ １ 一 ＭＡＧ Ｉ Ｃ ， 它 将 问 题 转 化 为
两阶凸规划 （ Ｓ ｅ ｃ ｏ ｎ ｄ － ｏ ｒ ｄ ｅ ｒ ｃ ｏ ｎ ｅ ｐ ｒ ｏ ｇ ｒ ａ ｍ ，Ｓ ＯＣ Ｐ ｓ ） ， 一 阶锥 模 型 （ Ｔｅ ｍｐ ｌ ａ ｔ ｅ ｓ ｆ ｏ ｒ ｆ ｉ ｒ ｓ ｔ — ｏ ｒ ｄ ｅ ｒ ｃ ｏ ｎ ｉ ｃ ｓ ｏ ｌ ｖ ｅ ｒ ｓ ， ＴＦ ＯＣＳ ） ， 它 主要 是 将 问题 转 化 为 标 准 的 锥模 型 ， 并利用一阶优化方法 ； 共 轭 梯 度 迭 代 方法 （ Ｃｏ ｎ ｊ ｕ ｇ ａ ｔ ｅ ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ／ ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ ｉ ｎ ｇ ， Ｃ ＧＩ Ｓ Ｔ） ， 它 主要 结 合 向 前 向后 分 裂方 法 和加 速 步 长 方 法 。
１ Ｌ ａ ｓ ｓ ｏ问题
在 机 器 学 习 的优 化 算 法 中 ， 一 般 的 凸优 化 问题 可 以表 示 为
ｍ ｉ ｎ Ｐ （ ） 一
其 对 偶 函 数 为
（ ） ＋ （ ） ）
（ １ ）
｛ ： 砉 一 一， 一 Ａ ｇ （ ÷ 砉 ） ）
式中 ： ａ ， …， ａ ∈ Ｒ 为 ； ７ １ ＂ 个数据样本向量； ， …， 为损 失 函数 ； … ． ， 为 的 共 轭 函 数 ； ｇ （?） 为 正 则 化 函数 ； ｇ （?） 为 ｇ的共 轭 函 数 ； 为原始变量 ； Ｙ为 对 偶 变 量 ； ≥０为 正 则 化 参 数 。
每一个样本数据 ｎ 对应着一个独立的变量 ｂ ， 当 仍（ ａ Ｔ ｘ ） 一寺 （ ａ Ｔ ｘ —ｂ ） ， ｇ （ ） ＝ｌ ｌ ＿ １ ｌ ， 即得到
ｚ 约束 线 性 回归 的 特 殊 形 式 ， 称为 Ｌ ａ ｓ ｓ ｏ问 题 ＿ １ ］ ， 即
ｍｉ ｎ÷ ｝ ｌ Ａ ｘ—ｂ ＋ ｌ ｌ ｌ Ｊ
（ ３ ）
式中 ： 变 量 ｘＥ Ｒ ； 矩 阵 Ａ∈Ｒ ； ｂ Ｅ Ｒ ； ＞ ０是 尺 度 约束 参 数 。Ｌａ ｓ ｓ ｏ问题 可 以解 释 为寻 找最 小 二 乘 或线 性 回归 问 题 的 稀 疏 解 。
１ ． １ 一般 的 Ｌ ａ ｓ ｓ ｏ问题
ｍｉ ｎ ÷ ｌ ｌ Ａ ｘ—ｂ ｌ ｌ ； ＋ ｌ ｌ ｌ ｌ
其 中 Ｆ是 任 意 的线 性 变 换 ， 一 个 特 殊 的例 子是 当 Ｆ为 差 异 矩 阵 时 ， 有
ｆ １ Ｆ 一 一 １ Ｊ— ｉ ＋１ Ｊ— ｉ
（ ４ ）
（ ５ ）
【 ０
其他
这 个 问题 转 变 为 Ｔ Ｖ 降 噪 问题 ， 在 信 号 处 理 中有 广 泛 的应 用 。当 Ａ—Ｉ ， Ｆ是 二 次 差 分 矩 阵 ， 问 题
变 为 Ｌ１趋 势 滤 波 ， 用 来 分 析 在 不 同学 科 中 的 时 间 序 列 数 据 。更 新 的迭 代 过 程 中 ， 矩阵Ａ Ａ＋ Ｆ Ｆ 是 五对 角矩 阵 ， 只需 运 行 ０（ ） 的浮点运算 。 １ ． ２ 组 Ｌａ ｓ ｓ ｏ问题
ｍ ｉ ｎ １ ｌ Ｉ Ａ ｘ —ｂ ＋ ∑
式 中 一 （
ｌ
一 ， ） ， Ｘ ∈Ｒ ， 每一个正则化约束项都是分 开 的， 但并不 是完全 的分开 ， 这种 Ｌ １ 范
数 约束 的 扩展 问题 称 之 为 组 Ｌ ａ ｓ ｓ ｏ问题 “ ， 或者叫做 Ｓ ｕ ｍ ｏ ｆ ｎ ｏ ｒ ｍｓ ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ ， 解 决组 Ｌ ａ ｓ ｓ ｏ问 题 一 般 采 用 分 裂 的方 法 ， 并 对 每 一个 子 问 题 进 行 Ｌ ａ ｓ ｓ ｏ问题 的 处 理 。
随着 大规 模 数 据 的增 加 ， 以 往解 决 Ｌ ａ ｓ ｓ ｏ问 题 的 方 法 很 难 满 足 人 们 对 时 间 和 效 率 的 要 求 。 当 数 据
的维 度 越 来 越 大 ， 函数 值 或 梯 度值 计 算 就 会 变 得 越 来 越 困难 ， 尤 其 是 当数 据 的 空 间维 度 大 于存 储 空 间 时， 一 般 的梯 度 方 法将 不 再适 用 。如 果储 存 空 间 不 影 响 梯 度 的 运 算 ， 那 么 大 数 据 的 运 算 可 能会 消耗 更 多
３ ８
数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｄａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５
的时间， 从 而 在 实 际应 用 中会 受 到影 响 ， 比如 图像 处 理 过 程 。 除 了 数 据 的 大 小 ， 并 不 是 所 有 的数 据 都 要 用 来 描 述 机 器 学 习 的 相 关 问题 ， 其 中一部分数 据就 可以解决 优化 问题 ， 而 不 是 等 到 全 部 的 数 据 都 处 理
完 。所 以解 决 这 些 问题 的方 法 不 仅 要 考 虑 算 法 的复 杂 度 ， 而 且 还 应从 实 际 问题 出发 ， 考 虑 如 何 能 够 更 快 地 解 决 大 规 模 数 据 带 来 的 困难 。
２ Ｌ ａ ｓ ｓ ｏ问题 解 决 方 法
大规 模 数 据 下 的 Ｌ ａ ｓ ｓ ｏ问题 主要 面临 着 计 算 复 杂 度 和 时 间 复 杂 度 问 题 ， 而 解 决 这 些 问 题 主 要 从 三
个 方 面考 虑 ： （ １ ） 一 阶方 法 。一 阶 方法 使 用 目标 函数 的梯 度 信 息 ， 虽 然 获 得 较 低 或 中等 精 确 的数 值 结
果， 但 是相 比一 些 复 杂 的运 算 过 程 ， 一 阶 方法 消耗 更 短 的 时 间 。根 据 邻 近 映 射 原 则 ， 一 阶方 法 能 够 解 决
非 光 滑 函 数 问题 ， 并 且 适 合 分 布 和 并 行 计算 。 （ ２ ） 随 机 性 。随 机 问 题 在 其 他 的 逼 近 问题 中 尤 为 突 出 ， 因 为 它 能 够 控 制期 望值 ， 从 而 增 加 一 阶 方 法 的 可 扩展 性 。关 键 的 问题 是 随 机 更 新 部 分 变 量信 息 ， 而不 是 全
部的变量 ， 进 而并 不 需 要 全 部 的 梯 度 信 息 ； 简单 的统计评估 就能 有很好 的计算 结果 ； （ ３ ） 并 行 和 梯 度 计
算： 一 阶梯 度方 法 能 够 用 在 并 行 计 算 和 分 布 优 化 中 ， 同 时还 可 以从 集 中通 信 的并 行 计 算 扩 展 到分 散 通 信
的异 步 算 法 。这 ３个 方 面 在 大 数 据 中 起 着 重 要 的作 用 ， 比如 随机 一 阶方 法 比确 定 策 略 的 方法 要 快 ， 它 能 够 忽 略 一 小 部 分 信 息 而 获得 高 概 率 的最 优 目标 函 数 结 果 。
２ ． １ 梯 度 下 降 方 法
梯 度 下 降 的 方 法 是 基 于一 阶方 法 ， 利 用 局 部 梯 度 信 息 和 迭代 公 式
Ｘ 一Ｘ 一ａ ｆ（ ｘ ） （ ７ ）
当 目标 函数 为 光 滑 函 数 时 ， 可 以使 用 更 快 的加 速 方 法 ， 如牛顿方法 ， 但 是 它 需 要 目标 函数 更 多 的信
息， 比如 二 阶求 导 信 息 ， 从 而 消耗 更 多 的 时 间 ， 而 这 些 信 息 并 不 容 易 在 约 束 函数 和 非 光 滑 函数 中得 到 。 梯 度 下 降 法 却 弥 补 了这 些 缺 点 。一 般 的梯 度 下 降 方 法 需 要 ０ （ Ｉ ／ ｅ ） 的迭代次数才 能达到 ￡ 的精确结果 。
Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 提 出 了一 个 改 进 ， 增 加 一 个 额 外 的 动量 步长 ． ８ 一是 ／ （ 走 ＋１ ）， 从 而 到 达 到 ０（ １ ／ ｅ ） 的迭代次 数 ， 这种 方 法 称 为 最 优 一 阶 方 法 。表 １给 出 了加 速 方 法 在 凸 函 数 和 强 凸 函数 中 的算 法 复 杂 度 。为 了能 够 得
到强 凸 函数 ， 可 以在 目标 函数 中 增加 约 束 化 项 。 因为 如 果 函数 ｆ （ ｘ ） 一／ ￣ ／ ２ ｘ ； 是 凸 函数 的 ， 那 么 是 厂（ ）
强 凸 函数 ， 所 以非 光 滑 函数 也 可 以有强 凸 函数 的性 质 ， 在 Ｌ ａ ｓ ｓ ｏ函数 中增 加 一 个 约 束 项 ， 即 ｇ（ ） ＝Ｘ ＋ ／ ￣ ／ ２ ｘ ； 。
表 １ 梯 度 下 降 方 法 的 算 法 复 杂 度 比较
Ｔａ ｂｌ ｅ ｌ Ｃｏ ｍｐ ｌ ｅ ｘｉ ｔ ｙ ｏ ｆ ｔ ｈｅ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ ｃ ｏ ｍ ｐａ ｒ ｉ ｓ ｏ ｎ ｏ ｆ ｇ ｒ ａ ｄｉ ｅ ｎｔ ａ ｓ ｃ ｅ ｎｔ ｍｅ ｔ ｈｏ ｄ
２ ． １ ． １ 邻 近 梯 度 方 法
邻 近 算 法 可 以 看 成是 解 决 非 光 滑 、 约束 、 大 规 模 和 分 布 式 问 题 的 工 具 。邻 近 算 法 可 以 看 成 是 求
解一部分凸优化问题 ， 从 邻 近运 算 定 义 可 以看 出
， １ 、
ｐ ｒ ｏ ｘ （ ． ） ， ） 一ａ ｒ ｇ ｍ ｉ ｎ ｛ ｇ （ ） ＋寺 ｌ —Ｙ Ｉ Ｉ ； ｝
、
（ ８ ）
函数 的邻 近 运 算 等 价 于 求 解 函数 的梯 度 步长 ｐ ｒ ｏ ｘ （ ｙ ） 一Ｙ — ｇ （ ）。 Ｌ ａ ｓ ｓ ｏ函 数是 一 般 混 合 目标 函数 的 一 种 特殊 形式 ， 邻 近 梯 度 方 法 可 以 利 用 混 合 函数 的性 质 ， 获 得 在 光滑 梯 度 方 法 下 的相 同的 收 敛速 度 （ 如表 １ ） ， 邻 近梯 度 方 法 可 以看 成 是 最 优 梯 度 方 法 的 扩 展 ， 于 是 原 始 的Ｌ ａ ｓ ｓ ｏ问题 结 合 最 优 梯 度方 法 和邻 近梯 度 方 法 ， 得到基于 Ｘ 展 开 的 目标 函数
刘柳 等 ： Ｌａ ｓ ｓ ｏ问题 的 最 新 算 法研 究
３ ９
一 ａ ｒ ｇ ｉ “ ｛ ＿ 厂 （ ） ＋ Ｖ ｆ （ ｘ ） （ 一 ） ＋ 壶ｌ ｌ ｙ 一 ｌ ｌ ； ＋ ｇ （ ｙ ） ｊ
应 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的加 速 方 法 ， 得 到加 速 的邻 近梯 度 方 法
Ｘ ｋ ＋ 一 ｐ ｒ ｏ ｘ （ ｖ 一ａ ＾ ｆ（ ｖ ））
… 一Ｘ ＋ （ ）
（ ９ ）
（ １ ０ ）
在 Ｌ ａ ｓ ｓ ｏ问题 中 ｇ（ ｚ ） 为 Ｌ１范 数 ， 邻 近 运 算 可 以通 过 软 阈值 的方 法 求 解 ， 这 种 加 速 的 方 法 称 为 快 速 收 缩 阈值 算 法 （ Ｆ ａ ｓ ｔ ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ／ ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ ｉ ｎ ｇ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ， Ｆ Ｉ Ｓ ＴＡ） 。除 了 在 迭 代 步 骤 能 够 减 少
迭代次数 、 增 加 收敛 率 ， Ｂ ｌ ａ ｃ ｋ ｆ ｏ ｒ ｄ
２ ． １ ． ２ 对 偶 锥 方 法
采 用 了并 行 矩 阵 一 向量 相 乘 的方 法 来 加 速 运算 。
对 偶 锥 方 法 结 合 对 偶 、 光 滑和一阶优 化方法 ， 用 来 解 决 一 般 的 凸 锥 优 化 问题 。该 方 法 的 优 点 是 能够得到稳定 、 有 效 的迭 代 方 法 。不 用 于邻 近梯 度 方 法 ， 对 偶 锥 方 法 在 对 偶 函数 中加 入 一 阶 优 化 方 法 。
在 原 始 函数 中 ， 这 两 种 方 法 都 增 加 了 一个 约 束项 ， 使 得 目标 函 数 为 强 凸 函数 ， 从 而 达 到表 １中 的收 敛 速 度 。对 偶 锥 方 法 可 以看 成 是 不 断 的缩 减原 始 和对 偶 函数 差 值 ， 当 原 始 函 数值 和 目标 函数 值 相 同 时 ， 即 达
到 最 优 解 。对 偶 锥 方 法 包 含 ４个 步 骤 。 （ １ ） 确 定 等 价 的锥 形 式
Ｌａ ｓ ｓ ｏ问题 的 锥 形 式 可 以表 示 为
ｍｉ ｎ ｌ ｌ ｌ ｌ １ Ｓ ． ｔ ．１ ｌ （ ２ ） 确 定 对 偶 形 式 原 始 函数 不 采 用 一 阶优 化 方 法 有 几 种 可 能 ： （ １ ） 原函数非光 滑 ； （ ２ ） 投影在 ｌ ｌ Ａ ｂ Ｉ Ｉ ≤￡ 需 要 消 耗 大量 的时间 ， 所 以将 问题 转 化 为 对偶 问 题 用 于 减 少 运 算 时 间 ， 对 偶 问 题 表 示 为 ｍａ ｘ ｉ ｎ ｆ ｛１
（ ３ ） 应 用 光 滑技 术
一ｂ ｌ ｌ≤ ｅ
（ １ １ ）
１ 一＜ ｚ ， Ａ ｘ一 ６ ） ｝
（ １ ２ ）
Ｌａ ｓ ｓ ｏ问 题 中 含 有 Ｌ１范 数 ， 从 而 应 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的光 滑 技 术 ， 在 原 目标 函数 中增 加 约束 项 ， 得 到 光 滑
的对 偶 问题
Ｄ （ ） 一ｍ ａ ｘ ｉ ｎ ｆ ｛ ｌ Ｉ ＋÷ ｌ — ｌ 。 ｌ ； ＜ ｚ ， Ａ ｘ 一６ ＞ ｝
（ ４ ） 使 用 一 阶优 化 方法
（ １ ３ ）
在 对 偶 函数 中使 用 一 阶优 化 方 法 ， 类似于邻近梯度方法 ， 同样 采 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的 加 速 方 法 ， 只 不 过 变
量 增 加 了对 偶 变 量 。对 偶 锥 方 法 可 以 看 成 是 鞍 点 方 法 ， 通过交替迭代优化原始函数和对偶函数 ， 达 到 共 同 的最 优 解 。具 体 的算 法 过程 如 下
一
（ １ 一 Ｏ ｋ ） ＋ ｚ ～ Ａ Ｙ ， ）
一
Ｓ ｏ ｆ ｔ Ｔｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ （ ｚ ０
ｚ … 一 Ｓｈ ｒ ｉ ｎｋ（ ｚ 一 ｔ （ ． ） ， 一 Ａｓ ｃ ）， ￡ 女 ￡）
ｖ … 一（ １一 ） Ｖ ＋ ｚ ¨ １
（ １ ４ ）
式中： Ｓ ｈ ｒ ｉ ｎ ｋ （?） 是１ 。收 缩 运 算 ， Ｓ ｏ ｆ ｔ Ｔｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ （?） 是 软 阈 值 运 算 。 图 ｌ表 示 的 是 模 拟 数 据 下 ， 基
于对 偶 锥 方法 和 加 速对 偶 锥 方 法 的 迭 代 结 果 ， 其 中横 坐 标 是 外 部 迭 代 次 数 ， 纵 坐 标 表示 迭代 点 与 最 优 点 的 迭代 误 差 ｌ 一Ｘ ｌ ｌ ｌ ／ｌ ｌ Ｘ ｌ ， ｌ 从 图 １中可 以 看 出 ， 基 于 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 加速的方法收敛更快 。 ２ ． ２ 交 替 方 向 乘 子 方 法 交 替 方 向乘 子 （ Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ， Ａ Ｄ Ｍ Ｍ） 方 法 结 合 分 布 式 凸 优 化 问
题， 适 合 解 决 大 规模 数 据 的 问 题 。ＡＤＭＭ 可 以看 成 是 融 合 对 偶 分 解 和 增 广 Ｌ ａ ｇ ｒ ａ ｎ ｇ ｉ ａ ｎ的 优 点 ， 它 跟 很
４ ０
数据采集与处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｙ Ｄａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５
外部迭代 次数
图 Ｉ 对 偶锥 方 法 和加 速 的对 偶 锥方 法
Ｆｉ ｇ ．１ Ｄｕａ ｌ ｃ ｏｎ ｉ ｃ ａ ｎｄ ａ ｃ ｃ ｅ ｌ ｅ ｒ ａｔ ｅ ｄ ｄｕ ａ ｌ ｃ ｏｎ ｉ ｃ ｍｅ ｔ ｈ ｏｄ
多算 法 有 相 互 联 系 ， 如 Ｂ ｒ ｅ ｇ ｍａ ｎ迭 代 方 法 ， Ｄ ｏ ｕ ｇ ｌ ａ ｓ Ｒａ ｃ ｈ ｆ ｏ ｒ ｄ分 裂 方 法 及 Ｄｙ ｋ ｓ ｔ ｒ ａ交 替 投 影 方 法 等 。 ＡＤＭＭ 方 法 可 以追 溯 到 １ ９ ７ ０年 ， 它 在解 决 大规 模 分 布 计 算 系统 和 大 量 的 优 化 问题 中 起 着 非 常 重 要 的
作用 。 在 ＡＤＭＭ 形 式 中 ， Ｉ ａ ｓ ｓ ｏ问题 可 以看 成
ｍｉ ｎ ｆ（ ｘ ） ＋ ｇ（ ｚ ） Ｓ ． ｔ ．
１
— ｚ一 ０
（ １ ５ ）
Ｎ
式中＿ ／ 、 （ ） 一 专【 【 Ａ ｘ — ｂ ， ｇ （ ） 一 ∑ 得 到 基 于Ａ Ｄ Ｍ Ｍ的 算法
１
”一（ Ａ Ａ＋ ｐ Ｊ ） （ Ａ ｂ＋ ｐ （ ｚ 一 “ ））
ｚ 一Ｓ （ “－ ＋ － ）
ｌ ｆ 一Ｈ ＋ … 一 ｚ
（ １ ６ ）
式 中 的更 新 是岭 回归 过程 ， 解决 Ｌ ａ ｓ ｓ ｏ问题 的 ＡＤＭＭ 方 法 可 以解 释 为 交 替 实 施 岭 回归 过 程 。 图 ２
表示 的是模 拟 数 据 下 ， ＡＤＭＭ 与 梯度 迭 代 方法 的 比较 。其 中红 色 曲线 表 示加 速 的 ＡＤＭＭ（ Ｆ ａ ｓ ｔ － ＡＤ ＭＭ） ，
趔
鞴
圆
峰
Ｉ １ Ｉ Ｉ
图 ２ ＡＤＭＭ 方 法 和 梯 度 方 法
Ｆｉ ｇ ．２ Ａ ＤＭ Ｍ ａ ｎｄ ｇｒ ａ ｄｉ ｅ ｎｔ ｍｅ ｔ ｈｏ ｄ
刘柳 等 ： Ｌ ａ ｓ ｓ ｏ问题 的 最 新 算 法研 究
４ ｌ
黑 色 曲线 表示 ＡＤＭＭ ， 绿 色表 示 加 速 的 邻 近 梯 度 放 方 法 ， 蓝色表 示邻 近梯度 方法 ， 虚 线 表 示 真 实 值 曲 线 。加 速 的 ＡＤＭＭ 比没 有 加 速 的 ＡＤＭＭ 方 法 能 够 更 快 的接 近 最 优 的 目标 函数 值 ， 加 速 的邻 近 梯 度 方 法 相 对 于邻 近梯 度 方法 能 够更 快 的 达 到 最 优 的 函数 值 ， 但是从 整体来 说 ， ＡＤＭＭ 方 法 能 更 快 地 收 敛 最 优 目标 函 数 值 。
一
般 的 ＡＤＭＭ 算 法 的收 敛 速 度 为 ０（ １ ／ ｋ ） ， Ｇｏ ｌ ｄ ｓ ｔ ｅ ｉ ｎ ［ ２ 结 合 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 的 一 阶 最 小 方 法 能 达 到 ０
（ １ ／ ｋ ） 的全 局 收敛 速 度 。然 而 随着 数 据 的 快 速 增 加 ， 如 自然 语 言 处 理 、 图像 识 别 和 生 物 信 息 等 ， 随 机 优 化 算 法 已 成 为 在 机 器 学 习 中重 要 的 方 法 。Ｓ ｕ ｚ ｕ ｋ ｉ ＿ ２ 提 出 了 基 于 随 机 优 化 算 法 的 ＡＤＭＭ 方 法 ， 同样 结
合 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 一阶优化方法 ， 应用在一般 的凸函数 ， 其收敛速 度为 ０（ １ ／ √ 忌 ） ， 而对于强 凸函数能够 达到 ０
（ １ ｏ ｇ （ 忌 ） ／ 忌 ） 的 收敛 速 度 ， Ｓ ｕ ｚ ｕ ｌ ｉ 结合随机对偶 坐标下降方 法（ Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ａ ｓ ｃ ｅ ｎ ｔ ， Ｓ ＤＣＡ） 和 ＡＤＭＭ ， 由 于在 每次 迭代 中 需 要 一 个 或 多 个 样 本 ， 所以 Ｓ ＤＣ Ａ— ＡＤＭＭ 并 不 需 要 非 常 大 的储 存 空 间 ， 这 种 特 点 尤其 是 在 面 对 大 数 据 量 时 ， 能 够 更 好 地 体 现 出算 法 的优 越 性 。 ２ ． ３ 坐 标 下 降 方 法
在 机 器学 习 中 ， 坐 标 下 降 方 法 在 解 决 大 规 模 优 化 问 题 中 起 着 重 要 的作 用 ， 尤 其 是 当 样 本 数 ｍ 非
常大 时 ， 求 全 梯 度 或 次 梯 度需 要 消 耗 大 量 的 时 间 和 储 存 空 间 ， 这 样 求 解 目标 函 数 的 子 函 数 问题 就 成 为 研 究 大规 模 问题 的 热 点 。 子 函 数 问 题 可 以看 成 选 取 坐 标 系 中 的 某 一 个 坐 标 或 某 一 组 坐 标 ， 保 持 其 他 的 坐 标 系 的变 量 不 变 ， 在每一次迭代过程 ， 只 优 化 在 选 取 坐 标 系 下 的 目标 函 数 。 有 效 的坐 标 下 降方 法取 决 于 每 一 次 迭 代 过 程 消 耗 的 时 间 和 目标 函 数 的 下 降 量 。一 个极 端 的 方 法 是
贪婪方法 ， 即选 取 最 大 的 下 降 方 向 。但 是 贪 婪 方 法 面 临 的 问题 ： （ １ ） 要求 所有 的数据可行 ； （ ２ ） 可 能 会 超
出计 算 机 的计 算 能 力 ， 比如需 要计 算 全 梯 度 的 迭 代 步 长 ， 而 不 是 某 个 坐标 系 下 的 迭 代 步 长 。另 外 两 个 选 择 坐标 系 的方 法 是 周期 和 随 机 ， 一般的选择坐标方法是基于周期循环 ， 循 环 坐 标 下 降 方 法 的全 局 和 局 部 收敛 性 质 在 文献 ［ － ５ ７ ￣ 中给出了详细的分析 ， 它 主 要 分 析 了在 等 渗 性 假 设 下 的 光 滑 凸 函 数 。虽 然 周 期 循
环 是 求 解 连续 坐 标 系 的 迭 代 过 程 ， 但 是 并 不 是 在 所 有 坐 标 系 下 的求 解 对 目标 函数 都 产 生 影 响 。 随 机 选
取 坐标 或 坐标 块 的 方 法 已经 成 为 在 大 规 模 数 据 分 析 中的 研 究 热 点 。随 机 选 择 坐 标 系 的 方 法 更适 合 大 规 模数据 ， 最 近 的 研究 表 明 随 机 方 法 确 实 能 够 增 加 收 敛 率 。 。在 均 匀 概 率 下 ， 随 机 选 择 坐 标 系 看 似 等
效 于周 期 循 环 ， 但 是 随 机 坐标 系 的选 择 能 够 避 免 周 期 循 环 下 最 糟 糕 的 情 况 ， 比如 某 些 坐 标 系下 的 数 据 对
目标 函数 并 没 有 作 用 。 除 了均 匀 概率 ， 不 同 的 概率 密 度 函 数 同样 可 以 增 加 收敛 速 度 。 同 时 ， 并 行 分 布 式 运 算 也 可 以用 在 坐标 下 降 方 法 中 ， 从 而达到更好的运算效率 。
Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ加 速 方 法 已经 成 功 地 应 用 在 全 梯 度 下 降 方 法 ， 将 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的 加 速 方 法 应 用 在 随 机 坐 标 下
降 方 法 中 已经 在 文 献 ［ ２ １ ， ３ ４ ］ 中进 行 了 分 析 。Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 口 提 出 了 一 种 加 速 的 随机 坐 标 梯 度 方 法 用 于 解 决 最 小 化 无 约束 的光 滑 函 数 ， Ｌ ｕ和 Ｘｉ ａ ｏ ｌ ３ 给 出 了基 于 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ方 法 的 证 明分 析 。
２ ． ３ ． １ 随 机 坐 标 下 降 方 法
随机 坐 标 下 降方 法 是 在某 个 概 率 分 布 下 选 择 坐 标 系 进 行 迭 代 的 过 程 ， 首先将 Ｎ 维空间分成 ７ ＂ ／ 个
子空 间， ｕ ∈ Ｒ 为矩阵的列置换 ， 任何一个 Ｎ 维空间 的 向量 可 以唯一 的表示 为 一 ＞ Ｕ
ｚ“ ’ 一ｕ 、 Ｘ∈Ｒ ， 当 Ｎ 一１时 ， 即为 单 位 ｅ向量 。Ｌａ ｓ ｓ ｏ问 题 可 以 简 单 的 表示 为
１ Ｔ Ｉ ｉ ｎ ｛ Ｐ（ ）一 厂（ ） ＋Ａ ｇ（ ）｝
∈
，
（ １ ７ ）
每 一 次 迭 代 过 程 只需 要 在 随机 选择 的 坐 标 系 下 进行 ， 即
Ｐ（ ＋ Ｕ ｔ ）一 ＿ 厂 （ Ｘ４ － Ｕ ｔ ） ＋２ ｇ（ ＋ Ｕ ｔ ） （ １ ８ ）
ｒ
其 中 ｆ（ ｘ＋ Ｕ ｔ ）的 上 界 可 以通 过 ／ （ ） 函数 的光 滑 性 表 示 ：ｆ （ ｘ ＋Ｕ ｔ ） ≤ 厂（ ） ＋（ 厂（ ） ， ｆ ） ＋ Ｊ ｆ ｔ
４ ２
数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｄａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０， Ｎｏ ． １ ，２ ０ １ ５
１ ； Ｌ 为 每个 坐 标 系 下 的 Ｌ ｉ ｐ ｓ ｃ ｈ ｉ ｔ ｚ 常 数 。每 一 次 的 迭 代 过 程 需 要 上 一 次 的 迭 代 结 果 ， 得 到 基 本 的 随 机 坐 标算 法
ｊ Ｔ “ （ ｘ ｋ ） 一 ａ ｒ ｇ ｍ ｉ “ ｉ （ ＿ 厂 （ Ｘ ｋ ） ， ） ＋ 等ｌ ｌ ｝ Ｉ ２ ＋ ｇ （ ＋ ） ， ∈ Ｒ ｝
【 Ｘ … 一 ＋ Ｕ Ｔ“ （ ）
（ １ ９ ）
在Ｌ ａ ｓ ｓ ｏ问题 的 目标 函 数 上增 加 正则 化 项 Ｉ Ｉ —Ｘ 。
， 使 得 目标 函数 变 为 严 格 凸 函数 ， 这 种 方 法
应 用 在 基 于 光 滑 函 数 的 坐标 下 降方 法 中得 到 更 好 的 迭 代 结 果 。表 ２ 对 比 了不 同算 法 的 复 杂 度 的结 果 。
表 ２ 不同算法的复杂度比较（ １ ）
Ｔ ａ ｂ ｌ ｅ ２ Ｃｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ ｃ ｏ ｍｐ ａ ｒ ｉ ｓ ｏ ｎ ｏ ｆ ｔ ｈ ｅ ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ ａ ｉ ｇ ｒ ｉ ｔ ｈ ｍ （ Ｉ ）
算 法 Ｙｕ ｎ ａ ｎ ｄ Ｔｓ ｅ ｎ ｇ Ｓ ｈ ａ ｌ ｅ ｖ — Ｓ ｈ ｗａ ｒ ｔ ｚ 。 Ｐ ｅ ｔ ｅ ｒ Ｒ ｉ ｃ ｈ ｔ ａ ｒ ｉ ｋ
复 杂 度 Ｏ（ ｎ Ｌ（ ＿ 厂 ）ｌ Ｘ 一 ０ ／ ￡ ） Ｘ ｏ ／ ｅ ） ｏ ｌ ； ／ ｅ ） Ｏ（ ｎ ｐ Ｉ Ｉ Ｘ 一 。Ｉ Ｉ ； ／ ｅ ） Ｏ （ ｎ ｌ Ｘ
Ｓ ａ ｈ ａ ｒ ａ ａ ｎ ｄ Ｔｅ ｗａ ｒ ｉ ” Ｏ（ ｎ Ｌ（ 厂 ）ｌ
２ ． ３ ． ２ 邻 近 随机 对 偶 坐标 下 降
邻 近 的 随机 对 偶 坐 标 下 降 方 法 （ Ｐ ｒ ｏ ｘ ｉ ｍａ ｌ ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ａ ｓ ｃ ｅ ｎ ｔ ， Ｐ ｒ ｏ ｘ － Ｓ Ｄ Ｃ Ａ） 是 Ｓ ｈ ａ —
ｌ ｅ ｖ和 Ｚ ｈ ａ ｎ ｇ 对 随 机对 偶 问题 的扩 展 ， 允 许 正 则 化 函数 ｇ为 一 般 的 强 凸 函 数 ， 这 样 可 以 用 来 解 决 非 凸 的 Ｌ１正 则 化 函数 。 在 目标 函 数 中增 加 正则 化 项 Ｐ（ ）＋ ／ ２ ｌ ｌ Ｘ— ｚ ， 其 中 ｚ是 上 一 步 的 迭 代 结 果 ，
：
Ｏ（ １ ／ ￣ ｎ ）， 当时 １ ／ （ ） 》 ｎ， 强 正则 化 项 能 够 使 得 邻 近 随 机 对 偶 坐 标 下 降 的 运算 时 间达 到 Ｏ（ ｄ ｎ ） 。在
每次迭代过程中 ， 选择合适 的 能够达到 ｄ 一
的运算 时间。表 ３ 是不同算 法的运算 时间对 比表 。
表 ３ 不 同 算 法 的 运 算 时 间 比 较
Ｔａ ｂｌ ｅ ３ Ｃｏ ｍ ｐｕ ｔ ｉ ｎｇ ｔ ｉ ｍｅ ｃ ｏ ｍ ｐａ ｒ ｉ ｓ ｏ ｎ ｏ ｆ ｔ ｈｅ ｄｉ ｆ ｆ ｅ ｒ ｅ ｎｔ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ
对偶 坐标 下 降 方 法 的 目标 是 增 加 对 偶 目标 函 数 值 ， 随 机 选 取 对 偶 变 量 的 Ｙ的 一 个 坐 标 系 ｅ ， 即Ｙ
对 应 着 原 始 问题 的第 ｉ 个 样 本 。最 大 化 对偶 函数 ， 得 到对 偶 变 量 的迭 代 步 长
Ａ ｙ ＝ ａ ｒ ｇ ｉ ｎ ｛ 一 （ 一（ ＋Ａ ｙ ） ） Ａ ｇ （ ∑＆ ＋ ｉ ｔ １ ｎ Ａ ｙ ） ）
的下 界 问 题
（ ２ ０ ）
为 了简 化 优化 问题 ， 对 共 轭 函数 ｇ做 光滑 处 理 ， 即一阶泰勒展开 ， 从 而 问 题 转 化 为 最 大 化 对 偶 函 数
Ａ ｙ — — ａ ｒ ｇ ｉ ｎ ｛ 一 （ 一（ ＋Ａ ｙ ） ） 一 ｇ （ ∑＆ ） 一（ ２ ｔ ｉ ）＆ Ａ ｙ ）
正则 化 项 ｇ （ ） 一 Ｉ ｌ １ ． ＋ ｌ ｌ Ｘ １ Ｉ 。 ≈ ｌ ｌ Ｘ ｌ （ ｌ 足 够 小 ） 。则 ｇ （ ） 的共 轭 函数梯 度 为
（ ２ １ ）
在 Ｌ ａ ｓ ｓ ｏ问 题 的 正则 化项 中 ， Ｌ１正 则 化 项 不 是 强 凸正 则 化 项 ， 增加 Ｌ ２正 则 化 项 ， 从而定 义 Ｌ ｌ — Ｉ ２
ｇ （ ） 一ｓ ｉ ｇ ｎ （ ｙ ） ［ １ １ 一ｉ ｔ ／ ￣ ３ ＋
Ｐｒ ｏ ｘ — Ｓ ＤＣ Ａ 加 速 方 法 采 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｓ评 估 序 列 技 术
（ ２ ２ ）
用 于 逼 近 随 机 的 邻 近 映 射 。在 每 一 次
Ｐ ｒ ｏ ｘ － Ｓ Ｄ Ｃ Ａ的迭代过程中 ， 改 进 目标 函数 Ｐ（ ） ＋ ／ ２ ｆ Ｘ ｚ ”
， 其 中 正 则 化 项 围 绕 着 向量 ｚ ”＝
刘柳 等 ： Ｌ ａ ｓ ｓ ｏ问题 的 最新 算 法研 究
４ ３
Ｘ ”４ － 口 （ ”一
方法 。
）， 从 而 得 到更 快 的收 敛 速 度 。对 于 选 取 坐 标 系 ， 一 般 在 均 匀 分 布 的概 率 下 选 取 ，
Ｚ ｈ ａ ｎ ｇ 阳 提 出 了在 对 偶 坐 标 系 下 根 据 任 意 的 分 布 选 取 对 偶 变 量 ， 并 获 得 了有 效 的 并 行 和 分 布 式 变 量
２ ． ３ ． ３ 随 机 原 始 对 偶 坐 标 下 降 方 法
随 机 原 始 对 偶 坐 标 下 降方 法 （ Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｐ ｒ ｉ ｍａ ｌ — ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ， Ｓ Ｐ ＤＣ） 是 通 过交 替 优 化 对 偶 函 数
和 原 始 函数 ， 其 中 随机 选 择 对 偶 变量 中 的 一 维 空 间 ， 由 于对 偶 变 量 对 应 着 原 始 目标 函数 中 的样 本 数 。在
给 出随 机 原 始 对 偶 问题 的算 法 前 ， 先 定 义原 始 问题 的 凸一 凹 鞍 点 问 题
ｍｉ ｎ ｍａ ｘ ｛ ｆ （ ｘ ， Ｊ ， ） 一２ （ （ ｎ ， ） 一 （ ） ） ＋Ａ ｇ（ ）｝
ｚ∈ ｙ ＥＲ 、
关 于 变 量 Ｙ通 过 最 大 化 目标 函数 ｆ（ ｘ， ） 得到 ， 需 要 消 耗 ０（ ｎ ｄ ） 的计 算 量 ， 如 果 很 大 ， 需 要 消 耗 更 多 的时间， 所 以通 过 随机 选 取 对 偶 变量 ｙ的坐 标 来 减 少 计 算 量 。这 样 在 选 取 的 坐 标 系 下 最 大 化 目标 函
数， 然 后 交 替 优 化 原 始 目标 函数 。不 同 于一 般 的原 始 对 偶 问题 ， 根 据 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｓ 的加速技 巧 ， 在 原 始 和 对 偶 函数 中增 加 了两 个 正则 化 项 ， 从 而 得 到更 快 的 收 敛 速度 ， Ｃ ｈ ｅ ｎ 介 绍 了随 机 原 始 对 偶 方 法 ， 在 原 始 和 对 偶 目标 函数 中增 加 一 阶变 量 并 且 融人 多 阶段 的 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 的加速方 法 ， 同时 不 需 要 采 用 光 滑 技 术 也 能 达 到 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 光 滑 后 的 收敛 速 度 。同 时 ， Ｚ ｈ ａ ｎ ｇ 提 出 Ｍｉ ｎ ｉ — ｂ ａ ｔ ｃ ｈ的方 法 ， 自动 选 取 多 个 对 偶 坐标 变
量， 在 并 行 运 算 中更 新 “ ¨ ， 仅需 ｏ（ ） 的迭 代 时 间 ， 当然处理多个 对偶坐标 ， 它 的 收 敛 率 比一 般 的 Ｓ Ｐ — ＤＣ方 法 要 快 很 多 ， 表 ４给 出 了 不 同算 法 的时 间 复 杂 度 。
表 ４ 不 同算 法 的 复 杂 度 比 较 （ ２ ）
Ｔａ ｂ ｌ ｅ ４ Ｃｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ ｃ ｏ ｍｐ ａ ｒ ｉ ｓ ｏ ｎ ｏ ｆ ｔ ｈ ｅ ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ （ Ⅱ ）
算 法
Ｎｅ ｓ ｔ ｅ ｒ ｏｖ ［ ］ Ｔｓ ｅ ｎ ｇ［ ］
复 杂 度
Ｏ（（ １＋ ）ｌ ｏ ｇ（ １ ／ ｅ ））
０（ （ ＋ ）ｌ ｏ ｇ （ １ ／ ｅ ））
Ｏ（ （ ＋Ⅳ）ｌ ｏ ｇ（ １ ／ ｅ ））
Ｓｈａ ｌ ｅ ｖ － Ｓｈｗａ ｒ ｔ ｚ ［ ３ ２ ］ Ｚｈ ａ ｎｇ ａ ｎ ｄ Ｌｉ ｎｃ 。 ］
Ｏ（ （ １ ＋
）ｌ ｏ ｇ （ １ ／ Ｅ ））
３ 结 束 语
近年来 ， 随 着 数 据 量 的增 加 ， 对解决 Ｌ ａ ｓ ｓ ｏ问 题 提 出 了更 大 的挑 战 。在 解 决 大 规 模 数 据 中 ， 必 须 要 考虑计算时间和储存能力 ， 当硬 件 条 件 还 不 能 完 全 满 足 大 数 据 背 景 下 带 来 的需 求 ， 尤 其 是 面 对 高 维 数
据， 以往 的 方 法 很 难 再 满 足 人 们 对 数 据 的分 析 ， 研 究 最 新 的算 法 就 成 为 最 新 的 热 点 。一 阶 方 法 、 随机 方
法 和 并 行 和 分 布 计 算 在 解 决 大 规 模 数 据 中起 中重 要 的 作 用 ， 首先 一 阶方法计算起 来简单 ， 消耗时 间短 ， 符合人们对时间效率的要求 ； 再次 ， 随 机 方 法 主要 从 数 据 的 特 点 来 考 虑 ， 大 规 模 数 据 并 不 代 表 所 有 的 数 据都会对算法产生影响 ， 如 果 对 所 有 的数 据 进 行 处 理 ， 那 么 必 将 消 耗 更 多 的 时 间 和储 存 空 间 ， 随 机 算 法 正 好 弥 补 了这 些 缺 点 ； 并 行 和 分 布 计 算 同样 是 为 了减 少 时 间 消耗 ， 加 速运 算 ， 增加效率 。 本文从 ３ 个典型的算法分析 了 Ｌ ａ ｓ ｓ ｏ 问 题 的最 新 算 法 ： 梯度下降方法 、 交 替 方 向乘 子 法 和 坐 标 下 降 方 法 。解 决 大 规 模 数 据 往 往 采 用 简 单 的方 法 更 能 提 高 效 率 。梯 度 下 降 是 做 简 单 的 方 法 ， 它 结 合 一 阶 方 法和 Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ的加 速 和光 滑技 术 ， 使 最 终 的 收敛 速度 达 到 ０ （ １ ／ ｋ ） 。ＡＤ ＭＭ 和 坐 标 下 降 方 法 也 是 在 梯 度下降方法的基础上进行改进 ， 使 得 它 们 能 够 更 适 合 大 规 模 的 数 据 。同 时 Ａ Ｄ ＭＭ 和 坐 标 下 降 方 法 采 用随机方法进行迭代 ， 因为 在 大 规 模 数 据 中能 够 减 少 时 间 消 耗 ， 实验结果 也证实 了在大规模 数据 中， 基 于 随 机 算 法 能 够 得 到 更 好 的结 果 。坐 标 下 降 方 法 利 用 其 坐 标 系 的 特 点 结 合 一 阶方 法 、 随 机 方 法 和 并 行 和 分 布计 算 。坐 标 下 降 方 法 之 所 以是 最 近 研 究 的热 点 ， 主 要 是 利 用 了其 坐 标 系 的特 点 ， 另 一 个 原 因是 数 据 样 本 的增 加 和 数 据 维 度 越 来 越 高 ， 为 了提 高 效 率 ， 坐标 下 降 方 法 是 可 行 的 方 法 ， 在 原 始 目标 函 数 中采
４ ４
数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｄａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０， Ｎｏ ． １ ，２ ０ １ ５
用 坐 标 下 降 方 法 是 为 了 避 免 高维 度 ， 而 在 对 偶 函数 下 的 坐标 下 降 为 了 解 决 大 数 据 样 本 问题 。 基 于 随 机 的坐 标 下 降 方 法 在 未 来 的研 究 中仍 然 起 着 非 常 重 要 的 作 用 ， 同 时 在 某 些 概 率分 布下 ， 对 坐 标 系 的 随机 选
择 将 会 是 下 一 个 阶 段研 究 的热 点 问题 。 参考文献 ：
［ １ ］ Ｔｉ ｂ ｓ ｈ ｉ ｒ ａ ｎ ｉ Ｒ．Ｒｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ａ ｎ ｄ ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ ｖ ｉ ａ ｔ ｈ ｅ ｌ ａ ｓ ｓ ｏ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ ｔ ｈ ｅ Ｒ ｏ ｙ ａ ｌ Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ Ｓ ｏ ｃ ｉ ｅ ｔ ｙ ．Ｓ ｅ ｒ ｉ ｅ ｓ Ｂ（ Ｍｅ ｔ ｈ ｏ ｄ —
ｏ ｌ ｏ ｇ ｉ ｃ ａ １ ）， １ ９ ９ ６， １ ５ （ １ ） ： ２ ６ ７ — ２ ８ ８ ．
Ｅ ２ ］ Ｂ ｉ ｃ ｋ ｅ ｌ Ｐ Ｊ ，Ｌ ｉ Ｂ ，Ｔｓ ｙ ｂ ａ ｋ ｏ ｖ Ａ Ｂ，ｅ ｔ ａ １ ．Ｒｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ ｉ ｎ ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ｓ ［ Ｊ ］ ．Ｓ ｏ ｃ ｉ ｅ ｄ ａ ｄ ｄ ｅ Ｅ ｓ ｔ ａ ｄ ｉ ｓ ｔ ｉ ｃ ａ ｅ Ｉ ｎ ｖ ｅ ｓ ｔ ｉ ｇ ａ ｃ ｉ ｏ ｎ Ｏｐ ｅ ｒ ａ ｔ ｉ ｖ ａ ，
２ ０ ０６ ，１ ５ （ ２ ）： ２ ７ １ － ３ ４ ４ ．
［ ３ ］ Ｆ ａ ｄ ｉ ｌ ｉ Ｍ Ｊ ， Ｓ ｔ ａ ｒ ｃ ｋ Ｊ Ｉ Ｍｏ ｎ ｏ ｔ ｏ ｎ ｅ ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ｓ ｐ ｌ ｉ ｔ ｔ ｉ ｎ ｇ ｆ ｏ ｒ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ｉ ｎ ｓ ｐ ａ ｒ ｓ ｅ ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ ［ Ｃ］ Ｉ ｍａ ｇ ｅ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ （ Ｉ ＣＩ Ｐ ） ，２ ０ ０ ９ １ ６ ｔ ｈ Ｉ Ｅ ＥＥ Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ｏ ｎ ．Ｃａ ｉ ｒ ｏ ，Ｅ ｇ ｙ ｐ ｔ ；ｓ ． ｎ ． ］ ，２ ０ ０ ９ ：１ ４ ６ １ － １ ４ ６ ４ ． ［ ４ ］ Ｉ ｉ ｕ Ｊ ， Ｙｕ ａ ｎ Ｉ ，Ｙｅ Ｊ ．Ｄ ｉ ｃ ｔ ｉ ｏ ｎ ａ ｒ ｙ Ｌ ａ ｓ ｓ ｏ ：Ｇ ｕ ａ ｒ ａ ｎ ｔ ｅ ｅ ｄ ｓ ｐ ａ ｒ ｓ ｅ ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ ｕ ｎ ｄ ｅ ｒ ｌ ｉ ｎ ｅ ａ ｒ ｔ ｒ ａ ｎ ｓ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ ［ Ｃ ］ ∥ Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ ｏ ｆ Ｍａ —
ｃ ｈ ｉ ｎ ｅ Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ，２ ０ １ ２ ３ ０ ｔ ｈ Ｉ Ｅ Ｅ Ｅ ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ １ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ．Ａｔ ｌ ａ ｎ ｔ ａ ，ＵＳ Ａ： Ｅ ｓ ． ｎ ． ］ ， ２ ０ １ ２ ：１ － ２ ８ ．
Ｅ ｓ ３ Ｚ ｈ ｏ ｕ Ｔ，Ｔ ａ ｏ Ｄ．Ｍｕ ｌ ｔ ｉ — ｔ ａ ｓ ｋ ｃ ｏ ｐ ｕ ｌ ａ ｂ ｙ ｓ ｐ ａ ｒ ｓ ｅ ｇ ｒ ａ ｐ ｈ ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ［ Ｃ ］ Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅ ２ ０ ｔ ｈ ＡＣ Ｍ Ｓ Ｉ ＧＫＤ Ｄ Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ｏ ｎ Ｋｎ ｏ ｗｌ ｅ ｄ ｇ ｅ Ｄ ｉ ｓ ｃ ｏ ｖ ｅ ｒ ｙ ａ ｎ ｄ Ｄ ａ ｔ ａ Ｍｉ ｎ ｉ ｎ ｇ ．Ｎｅ ｗ Ｙｏ ｒ ｋ，ＵＳ Ａ： Ｅ ｓ ． ｎ ． ］ ，２ ０ １ ４ ： ７ ７ １ － ７ ８ ０ ． ［ ６ ３ Ｙｕ ａ ｎ ｘ ．Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ｓ ｐ ａ ｒ ｓ ｅ ｃ ｏ ｖ ａ ｒ ｉ ａ ｎ ｅ ｅ ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｓ ｃ ｉ ｅ ｎ ｔ ｉ ｆ ｉ ｃ Ｃ ｏ ｍｐ ｕ ｔ ｉ ｎ ｇ ， ２ ０ １ ２ ，５ １ （ ２ ） ：
２６１ — ２７３
［ ７ ］ Ｓ ｕ ｎ Ｙ， Ｌ ｉ ｕ Ｑ，Ｔ ａ ｎ ｇ Ｊ ，ｅ ｔ ａ １ ．Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ｄ ｉ ｓ ｃ ｒ ｉ ｍｉ ｎ ａ ｔ ｉ ｖ ｅ ｄ ｉ ｃ ｔ ｉ ｏ ｎ ａ ｒ ｙ ｆ ｏ ｒ ｇ ｒ ｏ ｕ ｐ ｓ ｐ ａ ｒ ｓ ｅ ｒ ｅ ｐ ｒ ｅ ｓ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｉ Ｅ ＥＥ Ｔ ｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｏ ｎ
Ｉ ｍａ ｇｅ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ，２ ０ １ ４，２ ３ （ ９ ）： ３ ８１ ６ － ３ ８ ２ ６
［ ８ ］ Ｈａ ｓ ｔ ｉ ｅ Ｔ， Ｔｉ ｂ ｓ ｈ ｉ ｒ ａ ｎ ｉ Ｒ， Ｆ ｒ ｉ ｅ ｄ ｍａ ｎ Ｊ ， ｅ ｔ ａ １ ．Ｔｈ ｅ ｅ ｌ ｅ ｍｅ ｎ ｔ ｓ ｏ ｆ ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ： Ｄａ ｔ ａ ｍｉ ｎ ｉ ｎ ｇ ，ｉ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ａ ｎ ｄ ｐ ｒ ｅ ｄ ｉ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．
Ｔｈ ｅ Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎｃ ｅ ｒ ，２ ０ ０ ５，２ ７（ ２） ： ８ ３ — ８ ５ ．
［ ９ ］ Ｇｅ ｎ ｇ Ｂ ，Ｌ ｉ Ｙ，Ｔａ ｏ Ｄ，ｅ ｔ ａ １ ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｌ ａ ｓ ｓ ｏ ｆ ｏ ｒ ｌ ａ ｒ ｇ ｅ — ｓ ｃ ａ ｌ ｅ ｖ ｉ ｄ ｅ ｏ ｃ ｏ ｎ ｃ ｅ ｐ ｔ ｄ ｅ ｔ ｅ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｍｕ ｌ ｔ ｉ ｍｅ ｄ ｉ ａ ， Ｉ Ｅ Ｅ Ｅ Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ ｏ ｎ ，
２ Ｏ １ ２， １ ４ （ １ ）： ５ ５ － ６ ５ ．
［ １ Ｏ ］ Ｚ ｈ ｏ ｕ Ｔ， Ｔａ ｏ Ｄ．Ｓ ｈ ｉ ｆ ｔ ｅ ｄ ｓ ｕ ｂ ｓ ｐ ａ ｅ ｅ ｓ ｔ ｒ ａ ｃ ｋ ｉ ｎ ｇ ｏ ｎ ｓ ｐ ａ ｒ ｓ ｅ ｏ ｕ ｔ ｌ ｉ ｅ ｒ ｆ ｏ ｒ ｍｏ ｔ ｉ ｏ ｎ ｓ ｅ ｇ ｍｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ ［ Ｃ ］ Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅ Ｔ ｗｅ ｎ ｔ ｙ — Ｔｈ ｉ ｒ ｄ
Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ Ｊ ｏ ｉ ｎ ｔ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ｏ ｎ Ａｒ ｔ ｉ ｆ ｉ ｃ ｉ ａ ｌ Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎ ｃ ｅ ．Ｂ ｅ ｉ ｊ ｉ ｎ ｇ ，Ｃ ｈ ｉ ｎ ａ ： ［ ｓ ． ｎ ． ］ ，２ ０ １ ３ ：１ ９ ４ ６ — １ ９ ５ ２ ． ｏ ｎ ｓ ｏ Ｍ Ｖ ，Ｂｉ ｏ ｕ ｃ ａ ｓ － Ｄｉ ａ ｓ Ｊ Ｍ ，Ｆｉ ｇ ｕ ｅ ｉ ｒ ｅ ｄ ｏ Ｍ Ａ． Ｆａ ｓ ｔ ｉ ｍａ ｇｅ ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ ｕ ｓ ｉ ｎ ｇ ｖ ａ ｒ ｉ ａ ｂ ｌ ｅ ｓ ｐ ｌ ｉ ｔ ｔ ｉ ｎ ｇ ａ ｎ ｄ ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｅ ｄ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ １ ｉ ３ Ａｆ
Ｅ Ｊ ］ ．Ｉ ｍａ ｇ ｅ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ，Ｉ Ｅ Ｅ Ｅ Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ ｏ ｎ ， ２ ０ １ ０ ，１ ９ （ ９ ） ： ２ ３ ４ ５ — ２ ３ ５ ６ ． ［ １ ２ ］ Ｅ ｌ ａ ｄ Ｍ ，Ｍａ ｔ ａ ｌ ｏ ｎ Ｂ ，Ｚ ｉ ｂ ｕ ｌ ｅ ｖ ｓ ｋ ｙ Ｍ．Ｉ ｍａ ｇ ｅ ｄ ｅ ｎ ｏ ｉ ｓ ｉ ｎ ｇ ｗｉ ｔ ｈ ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ａ ｎ ｄ ｒ ｅ ｄ ｕ ｎ ｄ ａ ｎ ｔ ｒ ｅ ｐ ｒ ｅ ｓ ｅ ｎ ｔ ａ ｔ ｉ ０ ｎ ｓ ［ ｃ ］ ∥ Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ Ｖ ｉ ｓ ｉ ｏ ｎ ａ ｎ ｄ Ｐ ａ ｔ ｔ ｅ ｒ ｎ Ｒｅ ｃ ｏ ｇ ｎ ｉ ｔ ｉ ｏ ｎ ，２ ０ ０ ６ Ｉ Ｅ Ｅ Ｅ Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ Ｓ ｏ ｃ ｉ ｅ ｔ ｙ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ，Ｎｅ ｗ Ｙｏ ｒ ｋ ，ＵＳ Ａ：ｓ ． ｎ ． ］ ，２ ０ ０ ６ ， ２ ：１ ９ ２ ４ — １ ９ ３ １ ． ［ １ ３ ］ Ｆ ｉ ｇ ｕ ｅ ｉ ｒ ｅ ｄ ｏ Ｍ Ａ，Ｎ ｏ ｗａ ｋ Ｒ Ｄ ．Ａ ｎ ｅ ｍ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｆ ｏ ｒ ｗａ ｖ ｅ ｌ ｅ ｔ — ｂ ａ ｓ ｅ ｄ ｉ ｍａ ｇ ｅ ｒ ｅ ｓ ｔ ｏ ｒ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｉ ｍａ ｇ ｅ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ， Ｉ Ｅ Ｅ Ｅ Ｔｒ ａ ｎ ｓ ａ ｃ —
ｔ ｉ ｏ ｎ ｓ ｏｎ．２ ０ ０ ３，】 ２ （ ８） ． ９ ０ ６ － ９ １ ６ ．
ｇ １ ４ ３ Ｙｕ Ｊ ，Ｒｕ ｉ Ｙ，Ｔ ａ ｏ Ｄ Ｃｌ ｉ ｃ ｋ ｐ ｒ ｅ ｄ ｉ ｃ ｔ ｉ ｏ ｎ ｆ ｏ ｒ ｗ ｅ ｂ ｉ ｍａ ｇ ｅ ｒ ｅ ｒ ａ ｎ ｋ ｉ ｎ ｇ ｕ ｓ ｉ ｎ ｇ ｍｕ ｌ ｔ ｉ ｍｏ ｄ ａ ｌ ｓ ｐ ａ ｒ ｓ ｅ ｃ ｏ ｄ ｉ ｎ ｇ ［ Ｊ ３ ．Ｉ Ｅ Ｅ Ｅ Ｔｒ ａ ｎ ｓ ａ ｅ ｔ ｉ ｏ ｎ ｓ ０ ｎ
Ｉ ｍａ ｇ ｅ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎｇ，２ ０ １ ４，２ ３（ ５ ）：２ ０ １ ９ － ２ ０ ３ ２．
［ １ ５ ］ Ｈｅ Ｉ ，Ｔａ ｏ Ｄ， Ｉ Ａ ｘ，ｅ ｔ ａ １ ．Ｓ ｐ ａ ｒ ｓ ｅ ｒ ｅ ｐ ｒ ｅ ｓ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ ｆ ｏ ｒ ｂ ｌ ｉ ｎ ｄ ｉ ｍａ ｇ ｅ ｑ ｕ ａ ｌ ｉ ｔ ｙ ａ ｓ ｓ ｅ ｓ ｓ ｍｅ ｎ ｔ ［ Ｃ ］ ∥Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ Ｖｉ ｓ ｉ ｏ ｎ ａ ｎ ｄ Ｐ ａ ｔ ｔ ｅ ｒ ｎ Ｒｅ ｃ —
ｏ ｇ ｎ ｉ ｔ ｉ ｏ ｎ（ Ｃ ＶＰ Ｒ ） ，２ ０ １ ２ Ｉ Ｅ Ｅ Ｅ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ．Ｒｈ ｏ ｄ ｅ ，Ｉ ｓ ｌ ａ ｎ ｄ ：ｓ ． ｎ ． ］ ，２ ０ １ ２ ，１ １ ４ ６ — １ １ ５ ３ ．
ｏｕ ｃ ａ ｓ — Ｄｉ ａ ｓ Ｊ Ｍ ，Ｆｉ ｇ ｕ ｅ ｉ ｒ ｅ ｄ ｏ Ｍ Ａ．Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ａ ｌ ｇｏ ｒ ｉ ｔ ｈ ｍｓ ｆ ｏ ｒ ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｅ ｄ ｓ ｐ ａ ｒ ｓ ｅ ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ：Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｔ ｏ ｈ ｙ ｐ ｅ ｒ — ［ １ ６ ］ Ｂｉ
ｓ ｐ ｅ ｃ ｔ ｒ ａ ｌ ｕ ｎ ｍｉ ｘ ｉ ｎ ｇ ［ Ｃ ］ ∥ Ｈｙ ｐ ｅ ｒ ｓ ｐ ｅ ｃ ｔ ｒ ａ ｌ Ｉ ｍａ ｇ ｅ ａ ｎ ｄ Ｓ ｉ ｇ ｎ ａ ｌ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ：Ｅ ｖ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ｉ ｎ Ｒ ｅ ｍｏ ｔ ｅ Ｓ ｅ ｎ ｓ ｉ ｎ ｇ（ Ｗ ＨＩ Ｓ Ｐ ＥＲ Ｓ ） ，２ ０ １ ０ ２ ｎ ｄ
Ｗｏ ｒ ｋ ｓ ｈ ｏ ｐ ．Ｒｅ ｙ ｋ ｊ ａ ｖ ｉ ｋ ，Ｉ ｃ ｅ ｌ ａ ｎ ｄ ： ［ ｓ ． ｎ ． ］ ，２ ０ ｉ ０ ：ｌ 一 ４ ． ［ １ ７ ］ Ｌ ｉ ｎ ｅ ａ ｒ Ａ．Ｆ ｏ ｒ ｅ ｗｏ ｒ ｄ ｔ ｏ ｔ ｈ ｅ ｓ ｐ ｅ ｃ ｉ ａ ｌ ｉ ｓ ｓ ｕ ｅ ｏ ｎ ｓ ｐ ｅ ｃ ｔ ｒ ａ ｌ ｕ ｎ ｍｉ ｘ ｉ ｎ ｇ ｏ ｆ ｒ ｅ ｍｏ ｔ ｅ ｌ ｙ ｓ ｅ ｎ ｓ ｅ ｄ ｄ ａ ｔ ａ ［ Ｊ ］ ．Ｉ Ｅ Ｅ Ｅ Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ ｏ ｎ Ｇ ｅ ｏ ｓ ｃ ｉ ｅ ｎ ｃ ｅ
ａ ｎ ｄ Ｒｅ ｍｏ ｔ ｅ Ｓ ｅ ｎ ｓ ｉ ｎ ｇ， ２ ０ １ １，４ ９（ １ １ ）： ４ １ ０ ３ ．
［ １ ８ ］ Ｒ ｉ ｃ ｈ ａ ｒ ｄ ｓ Ｊ Ａ．Ｒｅ ｍｏ ｔ ｅ ｓ ｅ ｎ ｓ ｉ ｎ ｇ ｄ ｉ ｇ ｉ ｔ ａ ｌ ｉ ｍａ ｇ ｅ ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ［ Ｍ］ ．Ｎｅ ｗ Ｙ ｏ ｒ ｋ： Ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ，１ ９ ９ ９ ． ［ １ ９ ］ Ｅ ｆ ｒ ｏ ｎ Ｂ，Ｈａ ｓ ｔ ｉ ｅ Ｔ，Ｊ ｏ ｈ ｎ ｓ ｔ ｏ ｎ ｅ Ｉ 。ｅ ｔ ａ １ ．Ｌ ｅ ａ ｓ ｔ ａ ｎ ｇ ｌ ｅ ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ［ Ｊ ］ ．Ｔ ｈ ｅ Ａｎ ｎ ａ ｌ ｓ ｏ ｆ Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ｓ ， ２ ０ ０ ４ ，３ ２ （ ２ ） ： ４ ０ ７ — ４ ９ ９ ．
［ ２ ０ ］ Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｙ，Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｉ Ｅ ．Ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｔ ｏ ｒ ｙ ｌ ｅ ｃ ｔ ｕ ｒ ｅ ｓ ｏ ｎ ｃ ｏ ｎ ｖ ｅ ｘ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ： Ａ ｂ ａ ｓ ｉ ｃ ｃ ｏ ｕ ｒ ｓ ｅ ￣ Ｍ］ ．ＵＳ Ａ： Ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ，２ ０ ０ ４ ．
［ ２ １ ］ Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｙ．Ｓ ｍｏ ｏ ｔ ｈ ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｏ ｆ ｎ ｏ ｎ — ｓ ｍｏ ｏ ｔ ｈ ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓ ［ Ｊ ￣ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ Ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ，２ ０ ０ ５ ，１ ０ ３ （ １ ） ： １ ２ ７ — １ ５ ２ ．
ｏ ｙ ｄ Ｓ，Ｐ ａ ｒ ｉ ｋｈ Ｎ ，Ｃｈ ｕ Ｅ，ｅ ｔ ａ １ ．Ｄｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ａ ｎｄ ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ¨ｅ ａ ｒ ｎ ｉ ｎ ｇ ｖ ｉ ａ ｔ ｈ ｅ ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ ｍｕｌ — ［ ２ ２ ］ Ｂ
ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ［ Ｊ ］ ．Ｆ ｏ ｕ ｎ ｄ ａ ｔ ｉ ｏ ｎ ｓ ａ ｎ ｄ Ｔｒ ｅ ｎ ｄ ｓ Ｒ ｉ ｎ Ｍａ ｃ ｈ ｉ ｎ ｅ Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ，２ ０ １ １ ，３ （ １ ） ： １ － １ ２ ２ ． Ｅ ２ ３ ］ Ｂ ｅ ｃ ｋ ｅ ｒ Ｓ ．Ｒ， Ｃ ａ ｎ ｄ ６ ｓ Ｅ Ｊ ，Ｇｒ ａ ｎ ｔ Ｍ Ｃ．Ｔｅ ｍｐ ｌ ａ ｔ ｅ ｓ ｆ ｏ ｒ ｃ ｏ ｎ ｖ ｅ ｘ ｃ ｏ ｎ ｅ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ｗｉ ｔ ｈ ａ ｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ ｔ ｏ ｓ ｐ ａ ｒ ｓ ｅ ｓ ｉ ｇ ｎ ａ ｌ ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ ［ Ｊ ］ ．
Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ Ｐｒ ｏ ｇ ｒ ａ ｍｍ ｉ ｎｇ Ｃｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ，２ ０ １ １，３ （ ３ ）： １ ６ ５ — ２１ ８ ．
［ ２ ４ ］ Ｂ ｅ ｃ ｋ Ａ，Ｔ ｅ ｂ ｏ ｕ ｌ ｌ ｅ Ｍ．Ａ ｆ ａ ｓ ｔ ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ — ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ ｉ ｎ ｇ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｆ ｏ ｒ ｌ ｉ ｎ ｅ ａ ｒ ｉ ｎ ｖ ｅ ｒ ｓ ｅ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｎ Ｉ ｍ—
ａ ｇ ｉ ｎ ｇ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ，２ ０ ０ ９，２ （ １ ）： １ ８ ３ — ２ ０ ２ ．
［ ２ ５ ］ Ｇ ｏ ｌ ｄ ｓ ｔ ｅ ｉ ｎ Ｔ，ＯＤ ｏ ｎ ｏ ｇ ｈ ｕ ｅ Ｂ ，Ｓ ｅ ｔ ｚ ｅ ｒ Ｓ ．Ｆ ａ ｓ ｔ ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ Ｊ ｏ ｕ ｒ ｎ ａ ｌ Ｉ ｍａ ｇ ｉ ｎ ｇ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ，
刘柳 等 ： Ｌａ ｓ ｓ ｏ问题 的 最 新 算 法研 究
Ｚ Ｏｌ ４，７（ ３） ： ｌ ５ ８ ８ 一 ｌ ６ Ｚ ３ ．
４ ５
［ ２ ６ ］ Ｓ ｕ ｚ ｕ ｋ ｉ Ｔ．Ｄ ｕ ａ ｌ ａ ｖ ｅ ｒ ａ ｇ ｉ ｎ ｇ ａ ｎ ｄ ｐ ｒ ｏ ｘ ｉ ｍａ ｌ ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｆ ｏ ｒ ｏ ｎ ｌ ｉ ｎ ｅ ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｍｅ ｔ ｈ ｏ ｄ ｉ Ｃ ］ｆ ，Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ
ｏ ｆ ｔ ｈ ｅ ３ ｏ ｔ ｈ Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ｏ ｎ Ｍａ ｃ ｈ ｉ ｎ ｅ Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ（ Ｉ ＣＭＬ － １ ３ ） ．Ａｔ ｌ ａ ｎ ｔ ａ ，ＵＳ Ａ： ［ ｓ ． ｎ ． ］ ， ２ ０ １ ３ ：３ ９ ２ — ４ ０ ０ ． ［ ２ ７ ］ Ｓ ｕ ｚ ｕ ｋ ｉ Ｔ ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ａ ｓ ｃ ｅ ｎ ｔ ｗ ｉ ｔ ｈ ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｍｅ ｔ ｈ ０ ｄ ［ Ｅ Ｂ ／ ０Ｌ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ， ２ ０ １ ４ ．
［ ２ ８ ３ Ｏｕ ｙ ａ ｎ ｇ Ｈ ，Ｈｅ Ｎ， Ｔｒ ａ ｎ Ｌ， ｅ ｔ ａ １ ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ［ Ｃ ￣ ∥Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ ｏ ｆ ｔ ｈ ｅ ３ ０ ｔ ｈ Ｉ ｎ ｔ ｅ ｒ —
ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ Ｃｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ｏ ｎ Ｍａ ｃ ｈｉ ｎｅ Ｌｅ ａ ｒ ｎ ｉ ｎ ｇ，Ａｔ ｌ ａ ｎ ｔ ａ ，ＵＳＡ ： ｓ ． ｎ ． ２ Ｏ１ ３：８ Ｏ 一 ８ ８ ．
［ ２ ９ ］ Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｙ．Ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｃ ｙ ｏ ｆ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ｏ ｎ ｈ ｕ ｇ ｅ — ｓ ｃ ａ ｌ ｅ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｎ Ｏｐ ｔ ｉ ｍｉ ｚ ａ —
ｔ ｉ ｏ ｎ，２ ０ １ ２，２ ２ （ ２ ）： ３ ４１ － ３ ６ ２ ．
［ ３ ０ ］ １ ｉ ｕ Ｊ ， Ｗｒ ｉ ｇ ｈ ｔ Ｓ Ｊ ．Ａｓ ｙ ｎ ｃ ｈ ｒ ｏ ｎ ｏ ｕ ｓ ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ： Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｉ ｓ ｍ ａ ｎ ｄ ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ｐ ｒ ｏ ｐ ｅ ｒ ｔ ｉ ｅ ｓ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥
ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ，２ ０ １ ４ ．
Ｒｉ ｃ ｈ ｔ ｄ ｒ ｉ ｋ Ｐ，Ｔａ ｋ ｄ ｃ Ｍ．Ｉ ｔ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｃ ｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ ｏ ｆ ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ｂ ｌ ｏ ｃ ｋ — ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈｏ ｄ ｓ ｆ ｏ ｒ ｍｉ ｎ ｉ ｍｉ ｚ ｉ ｎ ｇ ａ ｃ ｏ ｍｐ ｏ ｓ ｉ ｔ ｅ ［ ３ １ ］
ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ Ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ， ２ ０ １ ４ 。１ ４ ４ （ １ － ２ ） ： １ － ３ ８ ． ［ ３ ２ ］ Ｓ ｈ ａ Ｉ ｅ ｖ Ｓ ｈ ｗａ ｒ ｔ ｚ Ｓ ，Ｚ ｈ ａ ｎ ｇ Ｔ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ａ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ ｌ ｏ ｓ ｓ ［ Ｊ ］ ．Ｔｈ ｅ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｍａ ｃ ｈ ｉ ｎ ｅ
Ｌｅ ａ ｒ ｎ ｉ ｎ ｇ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ，２ ０１ ３ ，１ ４ （ １ ）： ５ ６ ７ — ５ ９ ９ ．
［ ３ ３ ］ Ｓ ｈ ａ ｌ ｅ ｖ — Ｓ ｈ ｗ ａ ｒ ｔ ｚ Ｓ， Ｚ ｈ ａ ｎ ｇ Ｔ ．Ａｃ ｃ ｅ ｌ ｅ ｒ ａ ｔ ｅ ｄ ｐ ｒ ｏ ｘ ｉ ｍａ ｌ ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ａ ｓ ｃ ｅ ｎ ｔ ｆ ｏ ｒ ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ ｌ ｏ ｓ ｓ ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｅ Ｂ ／
ＯＬ ］ ．ｈ ｔ ｔ ｐ ｔ ？ ？ ｌ ｉ ｎ ｋ ． ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ． ｃ ｏ ｍ／ ｊ ｏ ｕ ｒ ｎ ａ ｌ ／ １ ０ １ ０ ７ ，２ ０ １ ５ ．
［ ３ ４ ］ Ｚ ｈ ａ ｎ ｇ Ｙ，Ｘｉ ａ ｏ Ｌ ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｐ ｒ ｉ ｍａ ｌ — ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｍｅ ｔ ｈ ｏ ｄ ｆ ｏ ｒ ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ ｅ ｍｐ ｉ ｒ ｉ ｃ ａ ｌ ｒ ｉ ｓ ｋ ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥
ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／，２ ０ １ ４ ．
［ ３ ５ ］ Ｃｈ ｅ ｎ Ｙ，Ｌ ａ ｎ Ｇ，Ｏｕ ｙ ａ ｎ ｇ Ｙ．Ｏｐ ｔ ｉ ｍａ ｌ ｐ ｒ ｉ ｍａ ｌ ｄ ｕ ａ ｌ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ａ ｃ ｌ ａ ｓ ｓ ｏ ｆ ｓ ａ ｄ ｄ ｌ ｅ ｐ ｏ ｉ ｎ ｔ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｎ Ｏｐ ｔ ｉ ｍｉ —
ｚ ａ ｔ ｉ ｏ ｎ，２ ０ １ ４，２ ４（ ４ ）： １ ７ ７ ９ － １ ８ １ ４ ．
［ ３ ６ ３ Ｄｅ ｖ ｏ ｌ ｄ ｅ ｒ Ｏ， Ｇｌ ｉ ｎ ｅ ｕ ｒ Ｆ， Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｙ ．Ｆ ｉ ｒ ｓ ｔ — ｏ ｒ ｄ ｅ ｒ ｍｅ ｔ ｈ ｏ ｄ ｓ ｏ ｆ ｓ ｍｏ ｏ ｔ ｈ ｃ ｏ ｎ ｖ ｅ ｘ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｗｉ ｔ ｈ ｉ ｎ ｅ ｘ ａ ｃ ｔ ｏ ｒ ａ ｃ ｌ ｅ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ —
ｃ ａ ｌ Ｐｒ ｏ ｇ ｒ ａ ｍｍ ｉ ｎ ｇ，２ ０１ ４，１ ４ ６（ １ — ２ ）： ３ ７ — ７ ５ ．
Ａｖ ｒ ｏ ｎ Ｈ ［ ３ ７ ］ ，Ｄｒ ｕ ｉ ｎ ｓ ｋ ｙ Ａ ，Ｇｕ ｐ ｔ ａ Ａ． Ｒｅ ｖ ｉ ｓ ｉ ｔ ｉ ｎ ｇ ａ ｓ ｙ ｎ ｃ ｈｒ ｏ ｎｏ ｕ ｓ ｌ ｉ ｎ ｅ ａ ｒ ｓ ｏ ｌ ｖ ｅ ｒ ｓ ：Ｐｒ ｏ ｖ ａ ｂｌ ｅ ｃ ｏ ｎｖ ｅ ｒ ｇ ｅ ｎｃ ｅ ｒ ａ ｔ ｅ ｔ ｈ ｒ ｏ ｕ ｇ ｈ ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ
［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ？ ｝ ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ２ ０ １ ４ ． Ｅ ３ ８ ］ Ｒｅ ｅ ｈ ｔ Ｂ， Ｒｅ Ｃ， Ｗｒ ｉ ｇ ｈ ｔ Ｓ， ｅ ｔ ａ １ ．Ｈｏ ｇ ｗｉ ｌ ｄ ： Ａ ｌ ｏ ｃ ｋ — ｆ ｒ ｅ ｅ ａ ｐ ｐ ｒ ｏ ａ ｃ ｈ ｔ ｏ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｉ ｚ ｉ ｎ ｇ ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ［ Ｃ ］ ∥ Ａｄ ｖ ａ ｎ ｃ ｅ ｓ ｉ ｎ Ｎｅ ｕ ｒ ａ ｌ Ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｓ ｙ ｓ ｔ ｅ ｍｓ ．Ｇｒ ａ ｎ ａ ｄ ａ ，Ｓ ｐ ａ ｉ ｎ ： Ｉ ｓ ． １ ３ ＿ ． ］ ，２ ０ １ １ ：６ ９ ３ — ７ ０ １ ．
［ ３ ９ ］ Ｒｉ ｃ ｈ ｔ ｄ ｒ ｉ ｋ Ｐ， Ｔａ ｋ ｄ ｃ Ｍ ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ｂ ｉ ｇ ｄ ａ ｔ ａ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ，２ ０ １ ４ ．
［ ４ ｏ ］ Ｌ ｉ ｕ Ｊ ，Ｗｒ ｉ ｇ ｈ ｔ Ｓ Ｊ ， Ｒ６ Ｃ， ｅ ｔ ａ １ ．Ａｎ ａ ｓ ｙ ｎ ｃ ｈ ｒ ｏ ｎ ｏ ｕ ｓ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ．
ｏ ｒ ｇ ／ ，２ ０ １ ４ ．
［ ４ １ ３ Ｌ ｉ ｕ Ｊ ，Ｗ ｒ ｉ ｇ ｈ ｔ Ｓ Ｊ ，Ｓ ｒ ｉ ｄ ｈ ａ ｒ Ｓ ．Ａ ｎ ａ ｓ ｙ ｎ ｃ ｈ ｒ ｏ ｎ ｏ ｕ ｓ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ｋ ａ ｅ ｚ ｍａ ｒ ｚ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ，
２ Ｏ １ ４ ．
［ ４ ２ ３ Ｓ ｔ ｒ ｏ ｈ ｍｅ ｒ Ｔ， Ｖｅ ｒ ｓ ｈ ｙ ｎ ｉ ｎ Ｒ．Ａ ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ｋ ａ ｃ ｚ ｍａ ｒ ｚ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｗ ｉ ｔ ｈ ｅ ｘ ｐ ｏ ｎ ｅ ｎ ｔ ｉ ａ ｌ ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｆ ｏ ｕ ｒ ｉ ｅ ｒ Ａｎ ａ ｌ ｙ ｓ ｉ ｓ
ａ ｎ ｄ Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ ，２ ０ ０ ９，１ ５（ ２ ）： ２ ６ ２ — ２ ７ ８ ．
［ ４ ３］ Ｇｒ ａ ｎ Ｍ ，Ｂ ｏ ｙ ｄ Ｓ ，Ｙｅ Ｙ．Ｃ ｖ ｘ ：Ｍａ ｔ ｌ ａ ｂ ｓ ｏ ｆ ｔ ｗ ａ ｒ ｅ ｆ ｏ ｒ ｄ ｉ ｓ ｃ ｉ ｐ ｌ ｉ ｎ ｅ ｄ ｃ ｏ ｎ ｖ ｅ ｘ ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ｃ ｖ ｘ ｒ ． ｃ ｏ ｍ／ ｃ ｖ ｘ ／ ，
２ ０ ０ ８ ．
［ ４ ４ ］Ｃ ａ ｎ ｄ ｅ ｓ Ｅ， Ｒｏ ｍｂ ｅ ｒ ｇ Ｊ ．１ １ 一 ｍａ ｇ ｉ ｃ ：Ｒｅ ｃ ｏ ｖ ｅ ｒ ｙ ｏ ｆ ｓ ｐ ａ ｒ ｓ ｅ ｓ ｉ ｇ ｎ ａ ｌ ｓ ｖ ｉ ａ ｃ ｏ ｎ ｖ ｅ ｘ ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ．［ Ｅ Ｂ ／ Ｏ Ｌ］ ．ｈ ｔ ｔ ｐ ： ∥ ｅ —ｄ ｕ ／ ｌ ｌ ｍａ ｇ ｉ ｃ ／
ｄ ｏ ｗｎ ｌ ｏ ａ ｄ ｓ ／ ｌ ｌ ｍａ ｇ ｉ ｃ ， ２ ０ ０ ５ ．
［ ４ ５ ３ Ｇｏ ｌ ｄ ｓ ｔ ｅ ｉ ｎ Ｔ，Ｏｓ ｈ ｅ ｒ Ｓ ．Ｔｈ ｅ ｓ ｐ ｌ ｉ ｔ ｂ ｒ ｅ ｇ ｍａ ｎ ｍｅ ｔ ｈ ｏ ｄ ｆ ｏ ｒ １ １ 一 ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｏ Ｉ ｍａ ｇ ｉ ｎ ｇ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ，２ ０ ０ ９ ，
２ （ ２ ）： ３ ２ ３ － ３ ４ ３ ．
［ ４ ６ ］ Ｒｕ ｄ ｉ ｎ Ｉ Ｉ Ｏｓ ｈ ｅ ｒ Ｓ， Ｆ ａ ｔ ｅ ｍｉ Ｅ ．Ｎｏ ｎ ｌ ｉ ｎ ｅ ａ ｒ ｔ ｏ ｔ ａ ｌ ｖ ａ ｒ ｉ ａ ｔ ｉ ｏ ｎ ｂ ａ ｓ ｅ ｄ ｎ ｏ ｉ ｓ ｅ ｒ ｅ ｍｏ ｖ ａ ｌ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ［ Ｊ ］ ．Ｐ ｈ ｙ ｓ ｉ ｃ ａ Ｄ： Ｎｏ ｎ ｌ ｉ ｎ ｅ ａ ｒ Ｐ ｈ ｅ ｎ ｏ ｍｅ —
ｎ ａ，１ ９ ９ ２，６ Ｏ（ １ ）： ２ ５ ９ － ２ ６ ８．
［ ４ ７ ］ Ｋｉ ｍ Ｓ Ｊ ，Ｋｏ ｈ Ｋ， Ｂ ｏ ｙ ｄ Ｓ ．Ｓ ｋ ｙ ｓ ｔ ｒ ｅ ｎ ｄ ｆ ｉ ｌ ｔ ｅ ｒ ｉ ｎ ｇ ［ Ｊ ］ ．Ｓ ｉ ａ ｍ Ｒｅ ｖ ｉ ｅ ｗ， ２ ０ ０ ９ ，５ １ （ ２ ） ： ３ ３ ９ — ３ ６ ０ ．
［ ４ ８ ３ Ｚ ｈ ｕ ｘ，Ｈｕ ａ ｎ ｇ Ｚ ，Ｃ ｕ ｉ Ｊ ，ｅ ｔ ａ １ ．Ｖｉ ｄ ｅ ｏ — ｔ ｏ — ｓ ｈ ｏ ｔ ｔ ａ ｇ ｐ ｒ ｏ ｐ ａ ｇ ａ ｔ ｉ ｏ ｎ ｂ ｙ ｇ ｒ ａ ｐ ｈ ｓ ｐ ａ ｒ ｓ ｅ ｇ ｒ ｏ ｕ ｐ ｌ ａ ｓ ｓ ｏ ［ Ｊ ￣ ．Ｍｕ ｌ ｔ ｉ ｍｅ ｄ ｉ ａ ，Ｉ Ｅ Ｅ Ｅ Ｔ ｒ ａ ｎ ｓ ａ ｃ —
ｔ ｉ ｏ ｎ ｓ ｏ ｎ，２ Ｏ １ ３，１ ５（ ３ ）： ６ ３ ３ － ６ ４ ６ ．
［ ４ ９ ］ Ｙｕ ａ ｎ Ｍ， Ｌｉ ｎ Ｙ．Ｍｏ ｄ ｅ ｌ ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ ａ ｎ ｄ ｅ ｓ ｔ ｉ ｍａ ｔ ｉ ｏ ｎ ｉ ｎ ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ｗｉ ｔ ｈ ｇ ｒ ｏ ｕ ｐ ｅ ｄ ｖ ａ ｒ ｉ ａ ｂ ｌ ｅ ｓ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ ｔ ｈ ｅ Ｒ ｏ ｙ ａ ｌ Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ Ｓ ｏ —
ｃ ｉ ｅ ｔ ｙ：Ｓｅ ｒ ｉ ｅ ｓ Ｂ（ Ｓｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ Ｍｅ ｔ ｈ ｏ ｄ ｏ ｌ ｏ ｇ ｙ） ，２ ０ ０ ６，６ ８（ １ ）： ４ ９ — ６ ７ ．
［ ５ Ｏ ］Ｏｈ ｌ ｓ ｓ ｏ ｎ Ｈ， Ｉ ￣ ｕ ｎ ｇ ，Ｌ ，Ｂ ｏ ｙ ｄ Ｓ ．Ｓ ｅ ｇ ｍｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ ｏ ｆ ａ ｒ ｘ － ｍｏ ｄ ｅ ｌ ｓ ｕ ｓ ｉ ｎ ｇ ｓ ｕ ｍ— ｏ ｆ — ｎ ｏ ｒ ｍｓ ｒ ｅ ｇ ｕ １ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ａｕ ｔ ｏ ｍａ ｔ ｉ ｃ ａ ，２ ０ １ ０ ，４ ６
（ ６ ）： １ １ ０ ７ — １ １ １ １ ．
［ ５ １ ］Ｃ ｅ ｖ ｈ ｅ ｒ Ｖ， Ｂ ｅ ｃ ｋ ｅ ｒ Ｓ ， Ｓ ｃ ｈ ｍｉ ｄ ｔ Ｍ．Ｃ ｏ ｎ ｖ ｅ ｘ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｆ ｏ ｒ ｂ ｉ ｇ ｄ ａ ｔ ａ ： Ｓ ｃ ａ ｌ ａ ｂ ｌ ｅ ，ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ， ａ ｎ ｄ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ｆ ｏ ｒ ｂ ｉ ｇ ｄ ａ — ｔ ａ ａ ｎ ａ ｌ ｙ ｔ ｉ ｃ ｓ ［ Ｊ ］ ．Ｓ ｉ ｇ ｎ ａ ｌ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｍａ ｇ ａ ｚ ｉ ｎ ｅ ，Ｉ Ｅ Ｅ Ｅ，２ ０ １ ４ ， ３ １ （ ５ ） ： ３ ２ — ４ ３ ． Ｅ ５ ２ ］Ｐ ａ ｒ ｉ ｋ ｈ Ｎ， Ｂ ｏ ｙ ｄ Ｓ ．Ｐ ｒ ｏ ｘ ｉ ｍａ ｌ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ［ Ｊ ］ ．Ｆ ｏ ｕ ｎ ｄ ａ ｔ ｉ ｏ ｎ ｓ ａ ｎ ｄ Ｔｒ ｅ ｎ ｄ ｓ ｉ ｎ Ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ，２ ０ １ ３ ，１ （ ３ ） ： １ ２ ３ — ２ ３ １ ．
４ ６
数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｄａ ｔ ａ Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ ａ ｎ ｄ Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５
Ｅ ６ ３ ３ Ｂ ｌ ａ ｃ ｋ ｆ ｏ ｒ ｄ Ｌ Ｓ ， Ｃｈ ｏ ｉ Ｊ ， Ｃ ｌ ｅ ａ ｒ ｙ Ａ，ｅ ｔ ａ １ ．Ｓ ｃ ａ Ｌ ＡＰ ＡＣ Ｋ ｕ ｓ ｅ ｒ ｓ ｇ ｕ ｉ ｄ ｅ ［ Ｅ Ｂ ／ ｏＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ ＷＷＷ ． ｎ ｅ ｔ ｌ ｉ ｂ ． ０ ｒ ｇ ／ ｓ ｃ ａ ｌ ａ ｐ ａ ｃ ｋ ／ ｓ ｃ ａ ｌ ａ ｐ ａ ｃ ｋ
ｕ ｇ ． ｐ ｓ ．２ ０ ０ ６ ．
Ｅ ５ ４ ３ Ｄ ｅ ｍｍｅ ｌ Ｍ Ｊ Ｗ ，Ｈｅ ａ ｔ ｈ Ｍ Ｔ， Ｖａ ｎ Ｄｅ ｒ Ｖｏ ｒ ｓ ｔ Ｈ Ａ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｎ ｕ ｍｅ ｒ ｉ ｃ ａ ｌ ｌ ｉ ｎ ｅ ａ ｒ ａ ｌ ｇ ｅ ｂ ｒ ａ ［ Ｊ ］ ．Ａｃ ｔ ａ Ｎｕ ｍｅ ｒ ｉ ｃ ａ ，１ ９ ９ ３ ，２ ： １ １ １ — １ ９ ７ ．
［ ５ ５ ３ Ｇａ ｌ ｌ ｉ ｖ ａ ｎ Ｋ Ａ， Ｐ ｌ ｅ ｍｍｏ ｎ ｓ Ｒ Ｊ ， Ｓ ａ ｍｅ ｈ Ａ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ｆ ｏ ｒ ｄ ｅ ｎ ｓ ｅ ｌ ｉ ｎ ｅ ａ ｒ ａ ｌ ｇ ｅ ｂ ｒ ａ ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ ｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ ｒ ｅ ｖ ｉ ｅ ｗ，１ ９ ９ ０ ，
３ ２ （ １ ）： ５ ４ － １ ３ ５ ．
Ｅ ５ ７ ］Ｓ ａ ｈ ａ Ａ ，Ｔ ｅ ｗ ａ ｒ ｉ Ａ．Ｏｎ ｔ ｈ ｅ ｆ ｉ ｎ ｉ ｔ ｅ ｔ ｉ ｍｅ ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ｏ ｆ ｃ ｙ ｃ ｌ ｉ ｃ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ［ Ｊ ］ ．Ｓ ｉ ａ ｍ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ，
２ ０ ｌ ３，２ ３（ １） ： ５ ７ ６ — ６ ０１ ．
［ ５ ６ ］ Ｆ ｒ ｉ ｅ ｄ ｍａ ｎ Ｊ ，Ｈａ ｓ ｔ ｉ ｅ Ｔ，Ｈｏ ｆ ｌ ｉ ｎ ｇ Ｈ， ｅ ｔ ａ １ ．Ｐ ａ ｔ ｈ ｗｉ ｓ ｅ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｔｈ ｅ Ａ ｎ ｎ ａ ｌ ｓ ｏ ｆ Ａ ｐ ｐ ｌ ｉ ｅ ｄ Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ｓ ，２ ０ ０ ７ ，１
（ ２ ）： ３ ０ ２ － ３ ３ ２ ．
［ ５ ８ ３ Ｌ ｅ ｖ ｅ ｎ ｔ ｈ ａ ｌ Ｄ，Ｌ ｅ ｗｉ ｓ Ａ Ｓ ．Ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ｌ ｉ ｎ ｅ ａ ｒ ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｔ ｓ ：Ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ｒ ａ ｔ ｅ ｓ ａ ｎ ｄ ｃ ０ ｎ ｄ ｉ ｔ ｉ ｏ ｎ ｉ ｎ ｇ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ｓ
ｏ ｆ Ｏｐ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ，２ ０１ ０，３ ５ （ ３ ）： ６ ４ １ — ６ ５ ４ ．
［ ５ ９ ］Ｓ ｈ ａ ｌ ｅ ｖ ～ Ｓ ｈ ｗａ ｒ ｔ ｚ Ｓ ，Ｔ ｅ ｗａ ｒ ｉ Ａ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ １ 卜ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ ｌ ｏ ｓ ｓ ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｔｈ ｅ Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｍａ ｃ ｈ ｉ ｎ ｅ Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ
Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ，２ ０ １ ｌ，１ ２： １ ８ ６ ５ — １ ８ ９ ２ ．
［ ６ ０ ］ Ｑｕ Ｚ， Ｒｉ ｃ ｈ ｔ ｄ ｒ ｉ ｋ Ｐ， Ｚ ｈ ａ ｎ ｇ Ｔ．Ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ｄ ｕ ａ ｌ ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ａ ｓ ｃ ｅ ｎ ｔ ｗｉ ｔ ｈ ａ ｒ ｂ ｉ ｔ ｒ ａ ｒ ｙ ｓ ａ ｍｐ ｌ ｉ ｎ ｇ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ，
２ Ｏ１ ４ ．
Ｅ ６ １ ］ Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ Ｙ．Ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ｍｉ ｎ ｉ ｍｉ ｚ ｉ ｎ ｇ ｃ ｏ ｍｐ ｏ ｓ ｉ ｔ ｅ ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ Ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ， ２ ０ １ ３ ，１ ４ ０ （ １ ） ： １ ２ ５ — １ ６ １ ． Ｅ ６ ２ ］ Ｔｓ ｅ ｎ ｇ Ｐ．Ｏｎ ａ ｃ ｃ ｅ ｌ ｅ ｒ ａ ｔ ｅ ｄ ｐ ｒ ｏ ｘ ｉ ｍａ ｌ ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｓ ｆ ｏ ｒ ｃ ｏ ｎ ｖ ｅ ｘ － ｃ ｏ ｎ ｃ ａ ｖ ｅ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ Ｅ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ｔ｝ ｝ ＷＷＷ． ｍｉ ｔ ． ｅ ｄ ｕ ／～
ｄ ｉ ｍｉ ｔ ｒ ｉ ｂ ／ Ｐ Ｔ ｓ ｅ ｎ ｇ ／ ｐ ａ ｐ ｅ ｒ ｓ ． ｂ ｔ ｍｌ ，２ ０ ０ ８ ．
［ ６ ３ ］ Ｔｓ ｅ ｎ ｇ Ｐ，Ｙｕ ｎ Ｓ ．Ｂ ｌ ｏ ｃ ｋ — ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ ｄ ｅ ｓ ｃ ｅ ｎ ｔ ｍｅ ｔ ｈ ｏ ｄ ｆ ｏ ｒ ｌ ｉ ｎ ｅ ａ ｒ ｌ ｙ ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｅ ｄ ｎ ｏ ｎ ｓ ｍｏ ｏ ｔ ｈ ｓ ｅ ｐ ａ ｒ ａ ｂ ｌ ｅ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．
Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ Ｔｈ ｅ ｏ ｒ ｙ ａ ｎｄ Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ，２ ０ ０ ９，１ ４ ０（ ３） ： ５１ ３ — ５ ３ ５ ．
作 者 简介 ； 刘柳 （ １ ９ ８ ７ 一 ） ， 女， 博士研究生 ， 研究方向 ： 机 器 学 习 ，Ｅ — ｍａ ｉ ｌ ： Ｌ ｉ ｕ ． Ｌ ｉ ｕ 一 ２ ＠ｓ ｔ ｕ ｄ ｅ ｎ ｔ ． ｕ ｔ ｓ ． ｅ ｄ ｕ ． ａ ｕ ； 陶大程（ １ ９ ７ ８ 一 ） ， 男， 教 授 研究方 向： 模式识别， 机器 学 习 ， 计算机视觉 ， Ｅ — ｍａ ｉ ｌ ： ｄ ａ ｃ ｈ ｅ ｎ ｇ ． ｔ ａ ｏ ＠ｇ ｍａ ｉ ｌ ． ｃ ｏ ｎ。 ｒ