Kernel Methods

Description

之前线性回归讲了如何用线性函数去拟合数据，那么当数据比较复杂， 不是线性关系时，线性函数拟合的效果就不会很好， 我们就需要尝试使用非线性函数去拟合数据。

假设我们使用三次方程 $y={\theta }_3{x}^3+{\theta }_2{x}^2+{\theta }_{1}x+{\theta }_0$ 来拟合数据， 可以发现三次方程可以看作是不同特征向量的线性组合。 令 $\varphi :\mathbb{R}\to {\mathbb{R}}^4$ ，则：

$$\varphi (x)=\left[\begin{array}{c}1\\ \\ x\\ \\ x^2\\ \\ x^3\end{array}\right]\in {\mathbb{R}}^4$$

令 $\theta \in {\mathbb{R}}^4$ 包含向量 ${\theta }_0,{\theta }_1,{\theta }_2,{\theta }_3$ 。 重写上诉三次方程为：

$${\theta }_3{x}^3+{\theta }_2{x}^2+{\theta }_{1}x+{\theta }_0={\theta }^T\varphi (x)$$

因此，一个多项式方程可以被看作是关于 $\varphi (x)$ 的线性方程。 我们称原始输入为 attributes ， $\varphi (x)$ 为 features map ， 映射之后的新输入为 features 。

LMS(least mean squares) with features

之前 LMS 更新方程如下：

\begin{equation*} \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} \end{equation*}

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

$$\theta :=\theta +\alpha \sum _{i=1}^n(y^{(i)}-{\theta }^T\varphi (x^{(i)}))\varphi (x^{(i)})$$

LMS with kernel skills

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

$$\varphi (x)=\left[\begin{array}{c}1\\ \\ x_1\\ \\ x_2\\ \\ ⋮\\ \\ x_1^2\\ \\ x_1{x}_2\\ \\ x_1{x}_3\\ \\ ⋮\\ \\ x_2{x}_1\\ \\ ⋮\\ \\ x_1^3\\ \\ x_1^2{x}_2\\ \\ ⋮\end{array}\right]$$

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

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

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

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

$$\theta =\sum _{i=1}^n{\beta }_i\varphi (x^{(i)})$$

其中， ${\beta }_1,\cdots ,{\beta }_n\in \mathbb{R}$ 。

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

$$\begin{array}{rl}\theta & :=\theta +\alpha \sum _{i=1}^n\left(y^{(i)}-{\theta }^T\varphi \left(x^{(i)}\right)\right)\varphi \left(x^{(i)}\right)\\ & \\ & =\sum _{i=1}^n{\beta }_i\varphi \left(x^{(i)}\right)+\alpha \sum _{i=1}^n\left(y^{(i)}-{\theta }^T\varphi \left(x^{(i)}\right)\right)\varphi \left(x^{(i)}\right)\\ & \\ & =\sum _{i=1}^n\underset{\text{new }{\beta }_i}{\underbrace{\left({\beta }_i+\alpha \left(y^{(i)}-{\theta }^T\varphi \left(x^{(i)}\right)\right)\right)}}\varphi \left(x^{(i)}\right)\end{array}$$

证毕。

由上证明可得：

$${\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\varphi (x^{(j)}{)}^T\varphi (x^{(i)}))$$

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

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

拿我们之前定义的 feature map $\varphi (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}

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

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

$$K(x,z)=⟨\varphi (x),\varphi (z)⟩$$

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

1. 计算所有核函数 Kernel $K(x^{(i)},x^{(j)})=⟨\varphi (x^{(i)}),\varphi (x^{(j)})⟩$ ， $\beta :=0$
2. Loop. $$\begin{gathered} \forall i\in \\ 1,\dots ,n \\ ,{\beta }_i:={\beta }_i+\alpha (y^{(i)}-\sum _{j=1}^n{\beta }_{i}K(x^{(i)},x^{(j)})) \end{gathered}$$ 令 $K$ 为 $n\times n$ 的矩阵， $K_{ij}=K(x^{(i)},x^{(j)})$ ，有 $$\beta :=\beta +\alpha (\vec{y}-K\beta )$$

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

$${\theta }^T\varphi (x)=\sum _{i=1}^T{\beta }_i\varphi (x^{(i)}{)}^T\varphi (x)=\sum _{i=1}^n{\beta }_{i}K(x^{(i)},K(x^{(j)}))$$

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

先来看几个 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)=⟨(\varphi (x),\varphi (z))⟩$ 知，

   $$\varphi (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 为：

   $$\varphi (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{2c}{x}_1\\ \\ \sqrt{2c}{x}_2\\ \\ \sqrt{2c}{x}_3\\ \\ c\end{array}\right]$$

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

Kernel 作为衡量相似性的指标

对于 $K(x,z)=\varphi (x{)}^T\varphi (z)$ ，如果 $\varphi (x)$ 和 $\varphi (z)$ 离得越远， $K$ 越小。 因此，可以把 $K$ 看作是衡量 $\varphi (x),\varphi (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 的必要条件

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

如果 $K$ 可以作为 Kernel 函数，那么 $K_{ij}=K(x^{(i)},x^{(j)})=\varphi (x^{(i)}{)}^T\varphi (x^{(j)})=\varphi (x^{(j)}{)}^T\varphi (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}

其中， ${\varphi }_k$ 是 $\varphi (x)$ 的第 $k$ 个元素。 ${\sum }_{ij}{a}_i{a}_j=({\sum }_i{a}_i{)}^2$ 。 这表明 $K$ 是一个半正定矩阵。

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

Kernel 的充分条件

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

TODO: 证明太长不想看了。