Kernel Method

机器学习

---

写在之前

时间充裕的话，可以从文末给出的参考链接中观看李正轩博士视频，本文是其讲课资料整理。

基本概念

设$\phi$实现$R^2 \rightarrow R^3$的映射，即

$$(x_1, x_2) \rightarrow (z_1, z_2,z_3) = (x_1^2,\sqrt{x_1x_2},x_2^2)$$

对于数据分布按照$\frac{x_1^2}{a^2}+\frac{x_2^2}{b^2}= 1$，映射之后有：$\frac{1}{a^2}z_1+0·z_2+\frac{1}{b^2}z_3= 1$

数据的分割从椭圆变成了3维的平面。

由此，$\phi$可以实现低维到高维的映射，并可以线性划分。来看高维度的几何性质：

$$<\phi(x_1,x_2), \phi(x_1',x_2')>= <(x_1^2,\sqrt{x_1x_2},x_2^2)(x_1'^2,\sqrt{x_1'x_2'},x_2'^2)> \\=(x_1x_1'+x_2x_2')^2 = <x, x'>^2 = \kappa(x, x')$$

$$cos(\theta) = \frac{<\phi(x), \phi(x')>}{||\phi(x)|| ·||\phi(x')||} = \frac{\kappa(x, x')}{\sqrt{\kappa (x, x)}\sqrt{\kappa (x', x')}}$$

$\kappa(x, x')$是核函数，实现了高纬度内积降维到低维，然后掉用Kernel function就可以。仅仅是$\kappa$就可以描述高维空间中的性质，而不需要知道$\phi$具体是如何映射的。

---

简单的分类器

训练集$\{(x_1, y_1), ...(x_n, y_n)\} \in R^d \times \{-1, 1\} \rightarrow \{(\phi(x_1), y_1), ...(\phi(x_n), y_n)\} \in H \times \{-1, 1\}$

正样本中心点：$c_+ =\frac{1}{m_+} \sum_{\{i|y_i = +1\}} {\phi(x_i)}$
负样本中心点：$c_- =\frac{1}{m_-} \sum_{\{i|y_i = -1\}} {\phi(x_i)}$

中心点差向量：$w = c_+-c_-$
中心点：$c= \frac{1}{2}(c_++c_-)$

判断正类样本： $cos(\theta) > 0 \rightarrow <\phi(x)-c, w> >0$
判断负类样本：$cos(\theta) < 0 \rightarrow <\phi(x)-c, w> <0$
即$\begin{align}y = sgn(<\phi(x)-c, w>)\end{align}$

因为$\phi$还不清楚，所以以上判断还需进一步化简，

$$<\phi(x)-c, w> = w^T(\phi(x)-c) = w^T \phi(x)- w^Tc \\ = {(c_+-c_-)}^T \phi(x) - \frac{1}{2}{(c_+-c_-)}^T(c_++c_-) \\ \begin{align}= (\frac{1}{m_+} \sum_{\{i|y_i = +1\}} {\kappa(x, x_i)}- \frac{1}{m_-} \sum_{\{i|y_i = -1\}} {\kappa(x, x_i)}) - b \\ \end{align}$$

---

$\phi$并不是一定要求出来，只要知道Kernel Function 就行。Kernel Function 需要满足有限半正定(finitely positive semi-definite)。对于给定的$\phi$，可以求出$\kappa$计算特征空间的点积；对于给定的$\kappa$，可以找到一个$\phi$构建特征空间H。

---

Dual Representation

设特征空间的线性函数为$f(x) = w^T \phi(x)+b$，为了去掉$\phi$，由(3)需要进一步化简

$$f(x) =( \sum_{i=1}^N \alpha_i \kappa(x_i, x)) +b$$

其中 $w = c_+-c_- =...=\sum_{i=1}^N \alpha_i \phi(x_i)$

从这里看，使用$\kappa$将原本$\phi(x)$的高维向量的内积变成了低维内积，然后做一次kernel function。大大减少了计算量。

参考文献

[1]https://www.youtube.com/watch?v=p4t6O9uRX-U&index=1&list=PLt0SBi1p7xrRKE2us8doqryRou6eDYEOy