Kernel Methods

之前 # LMS 更新方程如下： $

\begin{aligned} \theta &:=\theta+\alpha \sum_{i=1}^{n}\left(y^{(i)}-h_{\theta}\left(x^{(i)}\right)\right) x^{(i)} \\ &:=\theta+\alpha \sum_{i=1}^{n}\left(y^{(i)}-\theta^{T} x^{(i)}\right) x^{(i)} \end{aligned}

$

令 $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{p}$ 为从 attributes $x$ （ $\mathbb{R}^d$ ） 到 $\phi(x)$ （ $\mathbb{R}^p$ ）的 feature map 。 直接将 $x$ 使用 $\phi(x)$ 代替得：

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

直接使用 LMS 算法更新 $\theta$ 需要很大的计算量。 举个例子，假设 $x\in\mathbb{R}^d$ ， feature map $\phi(x)$ 为最高次小于等于 3 的多项式：

$$ \phi(x)=\left[\begin{array}{c} 1 \\ x_{1} \\ x_{2} \\ \vdots \\ x_{1}^{2} \\ x_{1} x_{2} \\ x_{1} x_{3} \\ \vdots \\ x_{2} x_{1} \\ \vdots \\ x_{1}^{3} \\ x_{1}^{2} x_{2} \\ \vdots \end{array}\right] $$

$\phi(x)$ 的维度为 $d^3$ ，如果 $d=1000$ ，那么每次更新都需要保存和计算 $10^{9}$ 个数据， 花费相当大。

为了简化这个计算，我们引入了 Kernel Trick 方法解决计算问题。

为了简单，我们将 $\theta$ 初始化为 0。 注意到，在每个阶段，都可以把 $\theta$ 看作 $\phi(x^{(1)}),\cdots,\phi(x^{(n)})$ 的线性组合。 数学归纳法证明如下：

最开始， $\theta=0=\sum_{i=0}^{n}0\cdot\phi(x^{(i)})$ 。 之后每步更新中，假设

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

其中， $\beta_1,\cdots,\beta_n\in\mathbb{R}$ 。

那么下一步的 $\theta$ 可以表示为：

\begin{equation} \begin{aligned} \theta &:=\theta+\alpha \sum_{i=1}^{n}\left(y^{(i)}-\theta^{T} \phi\left(x^{(i)}\right)\right) \phi\left(x^{(i)}\right) \\ &=\sum_{i=1}^{n} \beta_{i} \phi\left(x^{(i)}\right)+\alpha \sum_{i=1}^{n}\left(y^{(i)}-\theta^{T} \phi\left(x^{(i)}\right)\right) \phi\left(x^{(i)}\right) \\ &=\sum_{i=1}^{n} \underbrace{\left(\beta_{i}+\alpha\left(y^{(i)}-\theta^{T} \phi\left(x^{(i)}\right)\right)\right)}_{\text {new } \beta_{i}} \phi\left(x^{(i)}\right) \end{aligned} \end{equation}

证毕。

由上证明可得：

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

将上一时刻的 $\theta$ 用 $\beta$ 替换得：

$$ \forall i\in{1,\cdots,n},\beta_i:=\beta_i+\alpha(y^{(i)}-\sum_{j=1}^{n}\beta_{j}\phi(x^{(j)})^{T}\phi(x^{(i)})) $$

我们通常将 $\phi(x^{(j)})^T\phi(x^{(j)})$ 记作 $\left\langle\phi(x^{(j)}),\phi(x^{(i)})\right\rangle$ ， 表示两个向量之间的内积。到此，我们成功将问题转换成了 $\beta$ 的更新。 但我们仍然需要计算 $\left\langle\phi(x^{(j)}),\phi(x^{(i)})\right\rangle$ ，对于每个 $i,j$ ，其计算复杂度为 $O(p)$ 。 这计算量相当的大了，但是，有下面两个方法可以解决这个问题：

1. 提前将 $\left\langle\phi(x^{(j)}),\phi(x^{(i)})\right\rangle$ 计算好，在循环里面就可以直接使用了；
2. 绝大多数的核函数可以高效的计算内积。

拿我们之前定义的 feature map $\phi(x)$ 来说，其内积为：

\begin{aligned} \langle\phi(x), \phi(z)\rangle &=1+\sum_{i=1}^{d} x_{i} z_{i}+\sum_{i, j \in\{1, \ldots, d\}} x_{i} x_{j} z_{i} z_{j}+\sum_{i, j, k \in\{1, \ldots, d\}} x_{i} x_{j} x_{k} z_{i} z_{j} z_{k} \\ &=1+\sum_{i=1}^{d} x_{i} z_{i}+\left(\sum_{i=1}^{d} x_{i} z_{i}\right)^{2}+\left(\sum_{i=1}^{d} x_{i} z_{i}\right)^{3} \\ &=1+\langle x, z\rangle+\langle x, z\rangle^{2}+\langle x, z\rangle^{3} \end{aligned}

因此，我们可以先计算 $\left\langle x,z \right\rangle$ ，时间复杂度为 $O(d)$ ， 然后再用常数倍的时间复杂度就可以求出 $\left\langle\phi(x^{(j)}),\phi(x^{(i)})\right\rangle$ 。

从上面的分析可以看出，核函数非常重要，知道如何求解核函数，就可以求出问题的最优解。 我们定义 Kernel 为：

$$ K(x,z)=\left\langle\phi(x),\phi(z)\right\rangle $$

我们讲前面的算法重新整理一下：

1. 计算所有核函数 Kernel $K(x^{(i)},x^{(j)})=\left\langle\phi(x^{(i)}),\phi(x^{(j)})\right\rangle$ ， $\beta:=0$
2. Loop. $$ \forall{i\in\{1,\dots,n\}},\beta_i:=\beta_i+\alpha(y^{(i)}-\sum_{j=1}^{n}\beta_{i}K(x^{(i)},x^{(j)})) $$ 令 $K$ 为 $n\times n$ 的矩阵， $K_{ij}=K(x^{(i)},x^{(j)})$ ，有 $$ \beta:=\beta+\alpha(\vec{y}-K\beta) $$

至此，我们将 $\beta$ 更新的时间复杂度降到了 $O(n)$ 。 求解预测值时也非常简单：

$$ \theta^{T}\phi(x)=\sum_{i=1}^{T}\beta_{i}\phi(x^{(i)})^{T}\phi(x)=\sum_{i=1}^{n}\beta_{i}K(x^{(i)},K(x^{(j)})) $$

可以看出，我们其实并不需要知道真正的 feature map 是什么就可以计算预测值了， 只要有一个合适的 Kernel 就可以了。 换句话说，我们需要找一个函数 $K$ ，验证其满足一些性质，使得这个函数对应的 feature map $\phi$ 存在， 就可以使用上诉算法求解了。

先来看几个 Kernel 方程的例子。

1. $K(x,z)=(x^{T}z)^2$

   \begin{aligned} K(x,z)&=(\sum_{i=1}^{d}x_{i}z_{i})(\sum_{j=1}^{d}x_{j}z_{j}) \\ &=\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}x_{j}z_{i}z_{j} \\ &=\sum_{i,j=1}^{d}(x_{i}x_{j})(z_{i}z_{j}) \end{aligned}

   由 $K(x,z)=\left\langle(\phi(x),\phi(z))\right\rangle$ 知， $$ \phi(x)=\left[\begin{array}{c} x_{1} x_{1} \\ x_{1} x_{2} \\ x_{1} x_{3} \\ x_{2} x_{1} \\ x_{2} x_{2} \\ x_{2} x_{3} \\ x_{3} x_{1} \\ x_{3} x_{2} \\ x_{3} x_{3} \end{array}\right] $$

2. $K(x,z)=(x^{T}z+c)^2$

   \begin{aligned} K(x,z)=\sum_{i,j=1}^{d}(x_{i},x_{j})(z_{i},z_{j})+\sum_{i=1}^{d}(\sqrt{2cx_{i}})(\sqrt{2cz_{i}})+c^2 \end{aligned}

   其对应的 feature map 为： $$ \phi(x)=\left[\begin{array}{c} x_{1} x_{1} \\ x_{1} x_{2} \\ x_{1} x_{3} \\ x_{2} x_{1} \\ x_{2} x_{2} \\ x_{2} x_{3} \\ x_{3} x_{1} \\ x_{3} x_{2} \\ x_{3} x_{3} \\ \sqrt{2 c} x_{1} \\ \sqrt{2 c} x_{2} \\ \sqrt{2 c} x_{3} \\ c \end{array}\right] $$

更一般的， $K(x,z)=(x^{T}z+c)^k$ 也是一个 Kernel 。

对于 $K(x,z)=\phi(x)^T\phi(z)$ ，如果 $\phi(x)$ 和 $\phi(z)$ 离得越远， $K$ 越小。 因此，可以把 $K$ 看作是衡量 $\phi(x),\phi(z)$ （或者 $x,z$ ）相似性的标准。

基于这个想法，我们可以快速的验证一些函数是否可以作为 Kernel 。 例如，当：

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

这个函数满足上面提到的性质：当 $x,z$ 靠近， $K$ 变大，当 $x,z$ 离远， $K$ 变小。 这个 Kernel 叫做 Gaussian Kernel ，之后我们会讨论它。

定义 Kernel Maxtrix $K$ ， $K_{ij}=K(x^{(i)},x^{j})$ 。

如果 $K$ 可以作为 Kernel 函数，那么 $K_{ij}=K(x^{(i)},x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)})=\phi(x^{(j)})^T\phi(x^{(i)})=K(x^{(j)},x^{(i)})$ ， 因此 $K$ 是一个对称矩阵。

另外，对于任意向量 $z$ ，有：

\begin{aligned} z^T K z&=\sum_{i}\sum_{j}z_{i}K_{ij}z_{j} \\ &= \sum_{i}\sum_{j}z_{i}\phi(x^{(i)})^{T}\phi(x^{(j)})z_{j} \\ &= \sum_{i}\sum_{j}z_{i}\sum_{k}\phi_{k}(x^{(i)})\phi_{k}(x^{(j)})z_j \\ &= \sum_{k}\sum_{i}\sum_{j}z_{i}\phi_{k}(x^{(i)})\phi_{k}(x^{(j)})z_{j} \\ &= \sum_{k}(\sum_{i}z_{i}\phi_{k}(x^{(i)}))^2 \\ &\geq 0 \end{aligned}

其中， $\phi_{k}$ 是 $\phi(x)$ 的第 $k$ 个元素。 $\sum_{ij}a_{i}a_{j}=(\sum_{i}a_{i})^2$ 。 这表明 $K$ 是一个# 半正定矩阵。

综上，K 矩阵是一个半正定对称矩阵。

事实上，上面的必要条件也是 Kernel 的充分条件。

TODO: 证明太长不想看了。