CS229: 5

核方法, Kernel

核(Kernel)

有时候，直接得到的自变量$x$用线性的方法直接预测不太好，比如$y=x^2$，要提取出一些别的特征，我们还是希望使用线性的方法，可以把$x$映射到$\phi(x)$，在$\phi(x)$上用前面的线性的方法。$\phi(x)$称为特征。

但是注意，乱加特征很容易过拟合。

线性回归，就相应改成了

$$h_{\theta}=\theta^T\phi(x)\\ \theta:= \theta+\alpha(y^{(i)}-\theta^T\phi(x^{(i)}))\phi(x^{(i)})$$

但是如果特征太多，进行梯度下降就很慢了。

核技巧

用来加速梯度下降。

先证明$\theta$可以被$\phi(x^{(i)})$线性表示。

考虑归纳，设一开始$\theta=0=\sum_{i=1}^n0\phi(x^{(i)})$，成立。

若迭代$k$次成立，设

$$\theta=\sum_{i=1}^{n}\beta_i\phi(x^{(i)})$$

进行第$k+1$次迭代时

$$\theta'=\theta+\alpha \sum_{i=1}^{n}(y^{(i)}-\theta^T\phi(x^{(i)}))\phi(x^{(i)})\\ =\sum_{i=1}^{n}(\beta_i+\alpha y^{(i)}-\alpha\theta^T\phi(x^{(i)}))\phi(x^{(i)})\\ \beta_i'=\beta_i+\alpha(y^{(i)}-\theta^T\phi(x^{(i)}))\\ =\beta_i+\alpha (y^{(i)}-\sum_{j=1}^{n}\beta_j\phi(x^{(j)})\phi(x^{(i)})^T)\\ =\beta_i+\alpha (y^{(i)}-\sum_{j=1}^{n}\beta_j \left< \phi(x^{(j)}), \phi(x^{(i)})\right>)$$

如果能预处理出来全部$\phi(x^{(i)})$的内积，也就是一个gram矩阵，对整个训练集梯度下降一次是$O(n^2)$，$d$是特征的维数。

但是朴素做法一次复杂度是$O(nd)$，如果涉及到很高维的特征就会变快。还有一个用核技巧的重要原因是朴素做法不能处理映射到无穷维的情况。

我们称这个内积的函数为核函数

$$K(x,y)=\left< \phi(x), \phi(y) \right>\\ K_{i,j}=\left< \phi(x^{(i)}), \phi(x^{(j)}) \right>$$

核函数的性质

• 核函数的矩阵实对称
• 核函数的矩阵是半正定的

$$v^TKv=\sum_{i=1}^{n}\sum_{j=1}^{n}v_iv_j \left< \phi(x^{(i)}), \phi(x^{(j)})\right>\\ =\sum_{i=1}^{n}\sum_{j=1}^{n} \left< v_i\phi(x^{(i)}), v_j\phi(x^{(j)})\right>\\$$

考虑到内积的运算是双线性的（这里都是实数），有

$$=\left< \sum_{i=1}^{n} v_i\phi(x^{(i)}), \sum_{i=1}^{n} v_i\phi(x^{(i)})\right>\geq 0$$

• Mercer Theroem: 一个矩阵能充当核函数矩阵的充要条件是半正定

  不会证，好像要泛函分析

$$K(x,z)=K_1(x,z)+K_2(x,z)$$

考虑$v^TKv=v^T(K_1+K_2)v=v^TK_1v+v^TK_2v\geq 0$即可。

值得注意的是，相减不一定能得到核函数（内积要求范数非负）

$$K(x,z)=K_1(x,z)K_2(x,z)$$

首先要拓展一下之前讨论半正定的数域

$$v^TKv\geq 0,v\in \R ^n$$

则希望证明

$$v^HKv \geq 0,v \in C^n$$

设

$$v=x+iy,x,y\in R^n$$

直接代入得

$$v^HKv=(x^T-iy^T)K(x+iy)=x^TKx+ix^TKy-iy^TKx+y^TKy=x^TKx+y^TKy\geq 0$$

还是从矩阵的视角来看核函数

$$K_{i,j}=[K_1]_{i,j}[K_2]_{i,j}$$

知道$K_1$实对称，一定可以正交相似对角化

$$K_1=C^TDC$$

$D$是特征值组成的对角矩阵。

在复数域中对对角阵$D$开方，得

$$K_1=U^HU$$

直接考虑半正定的定义式

$$v^TKv=v^HKv=\sum_{i=1}^{n}\sum_{j=1}^{n}\overline{v_i}v_j[K_1]_{i,j}[K_2]_{i,j}\\ =\sum_{i=1}^{n}\sum_{j=1}^{n}\overline{v_i}v_j[K_2]_{i,j}\sum_{k=1}^{n}\overline{u_{k,i}}u_{k,j}\\ =\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}[K_2]_{i,j}\overline{u_{k,i}v_i}u_{k,j}v_j\\ =\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}[K_2]_{i,j}w^{(k)}_iw^{(k)}_j\\ =\sum_{k=1}^{n}(w^{(k)})^TK_2w^{(k)}\\ \geq 0$$

在数学上这种对矩阵的操作被称为哈达玛积，记为

$$K=K_1 \odot K_2$$

• 正定核

  $$K(x,z)=\exp(-\frac{||x-z||^2}{2\tau^2})$$

  实际上将向量映射到了无穷维，而维数越高越利于用超平面分类（线性可分），这在后面的SVM中得到了广泛应用。