2019-04-09

1. 线性回归 (L2-norm)

目标函数：
$L(w) = (Xw - y)^{T}(Xw - y) + \lambda w^{T}w$
最优解： $w = (X^{T}X + \lambda I)^{-1}X^{T}y$

2. 非线性 && 拉伸函数

拟合目标为非线性，例如真实分布如下：
$y = (x, x^{2})(w_1, w_2)^{T} + b$
则在用线性模型拟合时，应考虑将一维 $x \in \mathcal X^{1}$ “拉伸”为二维向量，即对于每个样本特征从一个标量 $x \in \mathcal X^{1}$ 变换为二维向量 $\phi(x) = (x, x^{2}) \in \mathcal X^{2}$ 。 $\phi(.)$ 称为拉伸函数。
假设N个训练样本，记 $\Phi = \Phi(X) = (\phi(X_1), \phi(X_2), ..., \phi(X_N))^{T}$ ，即对每个样本特征进行拉伸后的结果。那么最优解为 (式2-2)：
$w = (\Phi^{T}\Phi + \lambda I)^{-1}\Phi^{T}y$
实际上对于不同任务找到合适的拉伸函数 $\phi(.)$ 几乎是不可能的。所以为了避开这样的寻找过程，引入“核方法”的技巧。

3. 基本的核方法

（如果没有“核方法”的话，我们要找到合适的拉伸函数 $\phi(.)$ ，然后还要计算高维向量的内积，如式2-2）
我们首先把这样的向量内积计算表示为：
$\phi(X_i)^{T}\phi(X_j) = k(X_i, X_j)$
$k(., .)$ 便是所谓的核函数。线性模型的表达式为： $y = \phi(x)^{T}w = w^{T}\phi(x)$

依据式2-2， $w$ 可以表示为 $w = \Phi^{T} \alpha$ (因为都是线性组合?)，结合矩阵乘法 $w$ 可表示为：
$w = \Phi^{T} \alpha = \sum_{i=1}^{N} \alpha_{n} \phi(X_{i})$
其中 $\alpha = (\alpha_{1}, \alpha_{2}, ... , \alpha_{n})^{T}$ .

所以，
$y = w^{T}\phi(x) = \sum_{i=1}^{N} \alpha_{n} \phi(X_{i})^{T} \phi(x) = \sum_{i=1}^{N} \alpha_{n} k(X_i, x)$

下面求未知向量 $\alpha$ ，记 $K = \Phi\Phi^{T}$ ，有
$L(w) = L(\Phi^{T} \alpha) = (\Phi \Phi^{T} \alpha - y)^{T}(\Phi \Phi^{T} \alpha - y) + \lambda (\Phi^{T} \alpha)^{T}(\Phi^{T} \alpha)$
$= (K\alpha - y)^{T}(K\alpha - y) + \lambda \alpha^{T} K \alpha$
$=\alpha^{T} (K^2 + \lambda K) \alpha - 2y^{T}K\alpha + y^{T}y$
有上式对于 $\alpha$ 的偏导等于 $0$ 可得：
$2(K^2 + \lambda K)\alpha -2yK = 0$
计算得： $\alpha = (K + \lambda I)^{-1} y$

4. 小结

应对场景，选用不同得 $k(.,.)$ ，可以在训练集上计算好 $K, \alpha$ ，就可以构建如下核化的线性模型：
$\hat{y} = w^{T}\phi(x) = \sum_{i=1}^{N} \alpha_{n} \phi(X_{i})^{T} \phi(x) = \sum_{i=1}^{N} \alpha_{n} k(X_i, x)$
其中 $X_{i}$ 为第 $i$ 个训练样本， $(x, \hat{y})$ 为测试的输入输出对。

线性回归中引入核方法