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)课堂笔记(二十三):原型方法和最近邻KNN

笔记(二十二)需要等我找到上一本笔记本再说,暂时不知道扔到哪里去了...汗。届时补上。

这一章主要是讲的原型方法(prototype)和最近邻(KNN)。相对而言直觉更强,公式没那么复杂。

--------------------------笔记开始-------------------

1. 原型方法

1) 1-NN 最近邻居方法

最极端的情况:只找到最近的一位邻居。

数据集,输入,在中找到与最近的邻居,输出对应的类标记

2) 类中心的方法

类中心: ,相当于对于一群有着同样类标记的点,对x取平均。

输入:,而后在所有类中心中与其最近的类中心

输出:对应的类标记。

3) 对每个类可计算若干个“中心”(称之为原型或者样板,比如在每类中做聚类)。

输入:,而后在所有类中心中与其最近的类中心

输出:对应的类标记。

4) K-NN方法

输入:,在中找到与最近的K个邻居。

输出:(最多的那一类,从众原则的感觉)。

由于这一类方法都比较懒,所以称之为lazy learning methods.

2. K-NN方法的错误率(渐近性质)

1) 结果

为Bayes分类器的错误概率(最优分类器);为1-NN分类器的错误概率。

则有:当样本数时,。接下来会证明这个优良的性质。

2) 分类问题

给定,则

这里我们称 为先验分布,为类分布。从而

,称之为后验概率。

3) Bayes分类器

x对应的,即使得后验概率最大的k。

所以,,从

4) 1-NN分类器

1-NN输出的是离x最近的对应的,则

由于只限训练集,而那部分只跟测试集有关,所以由独立性我们可以拆分为:

,则当时,,,上面一项可以收敛为,为后验概率(条件误差)。

5)由于,设为所有中最大的,则

6)。得证。

下一章会讲到聚类,然后就是降维了。

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的计算。