一般来说，支持向量机是一个线性的学习系统，可以用于两类的分类问题。 令训练集合 D 为{(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)}，其中 xi=(xi1,xi2,…,xin)是一个 r 维输入向量，如遇实数空间 X∈������������������������ ,yi 是 它的类别标记（输出值），并且 yi∈{1， -1}1 表示正类，-1 表示负类。为了构造一个分类器，支持向量机寻找一个线性函 数， f (x) =< w • x > +b 。如果 f(xi)>0 那么 xi 被赋予正类，否则赋予负类。即
线性支持向量机：可分的情况............................................................................................... 4 第三部分：实验 .............................................................................................................................. 6
刘禹 中科院自动化所 2009M8014629010 2010-8-14
[键入公司名称]
SVM 在文本分类中 的应用
[键入文档副标题]
目录
第一部分：统计学习基本框架....................................................................................................... 3 第二部分：SVM 原理与对数回归原理...........................................................................................3
第二部分：SVM 原理与对数回归原理
支持向量机（SVM）属于判别式学习系统，其众多优点使得它成为了最流行 的算法之一。它不仅有扎实的理论基础，而且在许多应用领域比大多数其他算法 更准确，尤其在处理高维数据时。一些研究人员认为支持向量机可能是解决温饱 分类问题的最准确的算法。它也被广泛用于分类和生物信息领域。
考 察 最 接 近 超 平 面 < w • x > +b =0 的 一 个 正 例 点 （ x+，1 ） 和 一 个 负 例 点
（x−, −1）。定义两个平行的超平面H+和H−，分别经过 x+和 x− 点，并且与 < w • x > +b =0 平行。将 w,b 放缩可以得到：
H+ :< w • x+ > +b =1 H− :< w • x− > +b = −1 使得 < w • x > +b ≥ 1 当yi =1 < w • x > +b ≤ 1 当yi = −1
f (x) 是一个实值函数 w={w1,w2,…,wr}被称为权向量。b 被称为偏置。< w • x > 表
示点积。本质上支持向量机是寻找一个超平面 < w • x > +b =0 这个超平面能够区 分正类和负类，被称为决策边界。
线性支持向量机：可分的情况
通过线性代数中的知识，我们知道在 < w • x > +b =0 中，w 定义了垂直与超平 面的方向。w 被称为超平面的法向量。不改变法向量 w，我们可以通过变化 b 来 平 移 超 平 面 。 注 意 到 < w • x > +b =0 含 有 内 在 的 自 由 度 。 通 过 加 入 参 数 ，
∑ Lp=
1 2
(<
ww
>) −
n i=1
αi
yi
(<
wxi
>
+b) −1
其中就αi 是> 0拉格朗日乘子
优化理论中，上式的最优解需要满足 Kuhn-Tucker 条件。下面简要介绍一下凸优 化理论中对类似于上述问题的建模。
最小化：f (x)
满足 : gi (x) ≤ bi ,i = 1, 2,..., n 其中是f 目标函数，是g约i 束函数，拉格朗日算符为是
(<
wxi
>
+b) −1
其中就αi 是> 0拉格朗日乘子
得到对偶的目标函数：
∑ ∑ n
LD=
=i 1
= ai − 12 i, nj
yi y jaia j
1
<
xi
• xj
>
这样原来的问题转化成对偶问题
∑ ∑ n
最大化：LD=
=i 1
= ai − 12 i, nj
1
yi y jaia j
<
xi
• xj
这些条件称为 Kuhn-Tucker 条件。其中（2）是原始约束，（4）被称为称为互补 条件，它说明在解中，
如果a那i >么0 gi (x) = b,
如果那g么i (x) > bi
ai = 0
这些条件意味着，对有效的约束 ai > 0 ，反之对无效的约束 ai = 0 。
回到本问题，本问题符合 Kuhn-Tucker 条件，因此可以用哪个拉格朗日算法法。 又：对凸优化问题的拉格朗日处理导致了一个对偶问题，相对容易求解。对主问 题：
实验设计框架................................................................................................................... 7 文本预处理一体化模块框架图....................................................................................... 8 该模块运行情况截图....................................................................................................... 8 三种特征词选择算法介绍............................................................................................... 9 实验进展......................................................................................................................... 10 实验结果......................................................................................................................... 11 小结： ....................................................................................................................................17
实验目的 .................................................................................................................................. 6 实验设计 .................................................................................................................................. 7
这样，H+和H−之间不存在样本。 现在让我们来计算两个边缘超平面之间的距离，即
������������+ + ������������−。在线性代数的向量空间中，两个平行超平面之间的距离为
d1− d 2 w
w 代表 W 的欧式范数
由此
边距
d1− d 2
margin=
=
2
ww
2
w 最大边距问题可归结于最优化问题，等价于求解 最小化。由此学习问题转
概率分布 F（y|x）产生一个输出向量 y. （3） Learning Machine,图中用 LM 表示。它能够实现一系列函数 f(x,a) a∈Λ的
集合，Λ为一系列参数。
所谓学习问题就是从函数集——f(x,a) a∈Λ的集合，Λ为一系列参数，中寻找最 优的函数 f(x,������������`),使其能够更好地近似 Supervisor 的输出。 统计机器学习中的一个重要的度量手段是 VC 维（由 Vapnik-Chervonenkis 提 出），它表征一个统计模型能够正确分类的能力和精度。 学习问题存在两类风险：经验风险和结构风险。统计机器学习的目标是为了达到 经验风险最小（ERM），结构风险（SRM）最小。
统计机器学习
刘禹 自动化所 2009M8014629010
第一部分：统计学习基本框架
统计机器学习的模型框架可以作如下表示：
图1
统计机器学习模型框架主要有三个组件构成 （1） Generator,图中用 G 表示。它从一个概率未知，但是固定的分布函数 F（x）
中独立取样,产生随机向量 x. （2） Supervisor,图中用 S 表示。它对每个输入向量 x 根据固定但是未知的条件