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的联系。