Tag: SVM

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十二）：核函数和核方法

补上笔记。这节课讲的就是大名鼎鼎的Kernel Method...

核函数（正定）

定义 , 满足：

1) 对称：

2) 正定： n个观测， 正定（或者非负定）。

举例：

  • 常数——
  • 内积—— ，或广义下，其中，从。

性质：

1. 封闭性

1) 正定，，则正定。

2) 正定，正定，则正定，正定。

3) 正定，，则正定。

4) 正定

5) 正定。

2. 归一性

正定，。

再生核Hilbert空间（RKHS)

（走神一下：关于这个命名的吐槽猛击 -> 翻译版、 英文原版Normal Deviate）

1. Hilbert空间：完备内积空间，可以视作欧氏空间的推广。。

在这个空间中，我们定义：

  • 加法：x+y
  • 数乘：, 。
  • 内积：对称性;线性 ，.
  • 零元素：若，则定义为零元素。
  • 完备性：如果且，则。（收敛到该空间内）。

2. 再生核Hilbert空间

给定正定，可以构造Hilbert空间H使得，；且构造一个，使得，即核函数可以写成内积形式。

这样对于，。

核方法

1. 基本思想

将线性模型推广到非线性模型的方法（其中较为简单的一种）

，从到的一个映射。举例：，这样就可以拓展为广义线性模型。

2. SVM

可以转化为：

令，，则

非线性变换之后，

注意此时的维数有变化（）。

---------------------

如果各位更关心SVM后面的直觉，还是去看看Andrew Ng的相关课程吧...这里推导太多，直觉反而丢了一些。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十一）：SMO算法

1. SVM优化问题

1) 原问题

2) 拉格朗日形式的表述

其中，。

3) 对偶问题

4) SVM分类器

(i)

(ii) 选，，然后。

(iii)SVM分类器

2. SMO算法

1) 基本思想：迭代下降、坐标下降

一次要选择两个变量（否则会破坏的约束），之后就可以解这个双变量优化问题。

2) 两个变量的优化

任取,作为变量，其他作为常量。

展开的矩阵大致如下：

目标函数=

这样,,,。

约束(对应对偶问题)

，这里d代表其余不改变的那些。

化到单变量的话，

所以，

  • 目标函数= ，最优条件
  • 约束 ，其中和分别为lower/upper bound。故必有最优点在L、H之间或者L、H之一。
  • ，，可以解得

这里虽然需要迭代很多次，但是迭代的每一步都比较快。

至于如何选择，第一个变量可以选择，同时最大。第二个变量选择最大的。

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十）：SVM

这节课主要是讲线性优化的对偶问题。感觉这东西貌似在运筹学的时候被折腾过一遍，现在又来了-_-||

附赠个老的掉牙的段子...

有人问经济学家一个数学问题，经济学家表示不会解...

然后那个人把这个数学问题转成了一个等价的最优化问题，经济学家立马就解出来了...

好吧，我还是乖乖的赘述一遍对偶问题吧，表示被各种经济学最优化问题折磨过的孩子这点儿真是不在话下。

--------------------------------------------------------------------

1. 对偶问题的一般情况

1) 优化问题

一个典型的最优化问题形如：

(不等式约束)

（等式约束）

2) 优化问题的Lagrange （拉格朗日）函数

3) 对偶函数

称为该优化问题的对偶函数。此时，

，显然这个时候一阶偏导数为0。

4) 对偶问题

我们称为原优化问题的对偶问题，可化为最优化问题的标准形式。

如果原优化问题为凸优化，则必为凹函数，从而最终的标准形式依旧是一个凸优化问题。

5) 弱对偶性

令为原问题的解，则，且，.

令为对偶问题的解，则; .

定理（弱对偶性）：，即对偶问题的优化值必然小于等于原问题优化值。

6) 强对偶性

当时，两者具有强对偶性；满足该条件的称之为constraint qualifications，如Sliter定理。

强对偶性满足的时候，原优化问题就可以化为一个二步优化问题了。

7) KTT条件（库恩-塔克条件）

局部最优化成立的必要条件：

（一阶条件）

注：SVM满足强对偶性，所以可以直接解对偶问题。

2. 对偶问题应用于SVM

1) SVM的最优化问题

上节课可知，SVM的最优化问题为：

写成标准形式就是

这样这里总计有2N个约束条件。

对应的Lagrange函数为：

这样一阶条件就是


这样最后我们有.

3) 对偶函数

这里的对偶函数就是

4) 对偶问题

5) KKT条件

6) SVM分类器

  • 解对偶问题，得到,
  • 计算
  • 计算：找到一个（非边界上），从而满足。由，我们可得
  • 平面分类器: , ，故只与内积有关。

这样下节课就会讲到解对偶问题的方法，以及SVM和kernel methods的联系。

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十九）：SVM

支持向量机——最大边距方法

前言：这节课我人在北京，只能回来之后抄一下笔记，然后对着书和wiki理解一下....有什么错误还请大家及时指出。

------------------------------

1. 背景

  • 问题：两类分类问题
  • 数据：有标识、有监督
  • 模型：，线性模型
  • 准则：最大边距

先说一下个人理解的SVM的直觉。下图来自wiki。二次元中的SVM就是想找到一条直线（或者对应高维空间下的超平面）来尽可能的分割开两组数据。比如图中H3和H2这两条直线虽然都可以分开这两组数据，但是显然H3离两组数据都远一些——这就是SVM遵循的最大边距准则。

svm1

而在实践中，我们把二类分类分别作为正负1，所以两条距离该分割线平行距离1的直线就应景而生。在这两条直线上的点我们称之为支持向量（SV）。

2. 线性可分时的SVM

1) 线性可分：存在使得为分割超平面。

2) 一个点到超平面的距离：

3) 分割超平面的正则表示

数据集到某个超平面的距离。将标准化，则。

4) 最大边距准则

5) 线性可分时的SVM

等同于

这样就有了一个sign分类器。

6) support vector：分离超平面落在隔离带的边缘，满足的被称为SV。

7) 优点：

  • 对测试误差错识小
  • 稀疏性
  • 自然直观
  • 有效
  • 有理论深度（这话的意思是，又可以造出来一堆论文了么？）

3.一般的（线性）SVM

不满足约束的时候，可以做一些放松——引入作为松弛变量。

这样原来的最优化问题就变成

最优的分类器则为

svm_graph

这里大概示意了的应用场景。左边是上述完全可分的情况，右边是没法分开，所以我们容忍一些误差，只要误差之和在一个可以接受的范围之内。

4.非线性的SVM

这里的直觉大概是，在低维空间较为稠密的点，可以在高维空间下变得稀疏。从而可能可以找到一个高维空间的线性平面，把他们分开。

原来的数据集是：

然后定义一个从低维到高维的映射：，使得。其中原本属于，此时被映射到一个高维的，可为无限维Hilbert空间（这里我只是照抄笔记...）。

映射之后的，之后就是传统的寻找一个线性平面。

的例子：

，这样就打散到一个高维的空间（圆）。

下节课是线性SVM的计算。