落园 » 统计学习精要(The Elements of Statistical Learning)课堂笔记(二十二):核函数和核方法|专注经济视角下的互联网

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

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

核函数(正定)

定义 K(x,y), x,y\in\mathbb{R}满足:

1) 对称: K(x,y)=K(y,x)

2) 正定: n个观测x_{1},x_{2},...,x_{n}\in\mathbb{R}^{p}K_{n}=\left[\begin{array}{ccc}K(x_{1},x_{1}) & \cdots & K(x_{1},x_{n})\\\vdots & \ddots & \vdots\\K(x_{n},x_{1}) & \cdots & K(x_{n},x_{n})\end{array}\right] 正定(或者非负定)。

K(x,y)举例:

  • 常数——K(x,y)=C\Rightarrow\sum_{j}\sum_{j}cu_{i}u_{j}=c\left\Vert u_{i}\right\Vert
  • 内积—— K(x,y)=\sum x_{i}y_{i},或广义下K(x,y)=(\Phi(x),\Phi(y)),其中\Phi(x):x\rightarrow X,从\mathbb{R}^{p}\rightarrow\mathbb{R}^{q}

性质:

1. 封闭性

1) K(x,y)正定,\alpha>0,则\alpha K(x,y)正定。

2) K_{1}(x,y)正定,K_{2}(x,y)正定,则K_{1}(x,y)+K_{2}(x,y)正定,K_{1}(x,y)\cdot K_{2}(x,y)正定。

3) \{K(x,y)\}正定,K_{n}(x,y)\rightarrow K(x,y),则K(x,y)正定。

4) (1+(x,y))^{k}正定

5) \exp(-\frac{\left\Vert x-y\right\Vert }{2\sigma^{2}})正定。

2. 归一性

\bar{K}(x,y)=\frac{K(x,y)}{\sqrt{k(x,x)}\sqrt{k(y,y)}}正定,\Rightarrow\bar{K}(x,x)=1

再生核Hilbert空间(RKHS)

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

1. Hilbert空间:完备内积空间,可以视作欧氏空间的推广。H=\{x,y,z,...\}

在这个空间中,我们定义:

  • 加法:x+y
  • 数乘:\alpha x, \alpha\in\mathbb{R}
  • 内积(x,y):对称性(x,y)=(y,x);线性 (x_{1}+x_{2},y)=(x_{1},y)+(x_{2},y)\alpha(x,y)=(\alpha x,y).
  • 零元素:若(x,x)=0,则x=\phi定义为零元素。
  • 完备性:如果x_{n}\rightarrow xx_{n}\in H,则x\in H。(收敛到该空间内)。

2. 再生核Hilbert空间

给定K(x,y)正定,可以构造Hilbert空间H使得K(\cdot,y)\in H(K(\cdot,y),K(\cdot,z))=K(y,z);且构造一个\Phi(x):\mathbb{R}^{p}\rightarrow H,使得K(x,y)=(\Phi(x),\Phi(y)),即核函数可以写成内积形式。

这样对于\forall f\in H(f,K(\cdot,x))=f(x)

核方法

1. 基本思想

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

x\underrightarrow{\Phi(x)}\tilde{X}=\Phi(x),从\mathbb{R}^{p}\mathbb{R}^{q}(H)的一个映射。举例:\Phi(x)=(x,x^{2}),这样就可以拓展为广义线性模型。

2. SVM

\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}

s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i

可以转化为:

\min-g(\lambda,\mu)=\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})-\sum_{i}\lambda_{i}

s.t.\sum_{i}\lambda_{i}y_{i}=0

0\leq\lambda_{i}\leq C

\mu_{i}\geq0

w=\sum\lambda_{i}x_{i}y_{i}b=y_{i}-w'x_{i},则f(x)=sign(\sum\lambda_{i}y_{i}(x'x_{i})+b)

非线性变换之后,

\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}

s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i

注意此时w的维数有变化(p\rightarrow q)。

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *