核方法与非线性识别能力

机器学习领域，学习问题实际情况往往是非线性的，所谓的线性较少存在。但是由于线性方法的大量存在，那么就不可避免的涉及到一个问题，如何将这些线性的学习方法应用在非线性问题上或者说获得非线性识别能力？

Fig.1 映射函数 $\Phi$ 将数据映射到一个高维空间中，使得非线性的模式线性可分。核方法计算输入向量与训练样本间的内积表示数据点之间的相似程度。

考虑嵌入映射（embedding map）： $\Phi:x\in R^{n}\mapsto \Phi(x)\in H\subseteq R^{N}$ 映射到高维空间，这个空间可以是有限维空间，也可以是无穷维空间。它是一个Hilbert空间。任何核方法包括：1）映射方法(embed the data into a space where the patterns can be discovered as linear relations) 2）学习算法来发掘映射空间中的线性模式（Represent linear patterns efficiently in high-dimensional space to ensure adequate representational power）

实际上，svm核方法升维，使得在高维上的线性切割，投射到实际空间就变为非线性的切割；lr通过增加大量非线性特征，使得获得非线性切割能力；深度学习通过二层以上神经网络获得非线性切割。核心都需要有非线性识别能力。

Least Squares Linear Regression

首先让我们抛开所谓的核方法，而从least squares linear regression（最小二乘线性回归）这个通俗易懂的问题切入。

给定训练集 $S=\{(x_{1},y_{1}),..., (x_{l},y_{l})\}$ ， $x_{i}\in X=R^n,y_{i}\in Y=\{1,-1\} \in R,i=1,...,l$

$n$ 维输入向量 $x=(x_1,x_2,...,x_n)$ ，需要找出一个决策函数，推断输入 $x$ 相对应的输出值 $y$ 。最简单的方法就是通过一个线性函数 $g(x)$ 将 $x$ 映射到 $y$ 。

$g(x)=<w,x>=w^{'}x={\sum_{i=1}^{n} }{w_{i}x_{i}}$ ，要求 $f((x,y))=\lvert{y-g(x)}\rvert=\lvert{y-<w,x>}\rvert \approx 0$

Fig.2. A one-dimensional $n$ =1 linear regression problem.

$X_{l\times n}w_{n\times 1}=y_{l\times 1},X=[x{_1}^{'};...;x{_l}^{'}],y=(y_1,...,y_{l})^{'}$

当存储数据的矩阵 $X$ 的行维数（即数据点的个数）小于数据点的维数时， $w$ 有无穷多个解（describe the data exactly），此时选择的标准是取最小范数的 $w$ 。当 $X$ 的行维数大于列维数时，且数据点存在噪声，此时不存在准确的模式（exact pattern），此时应使误差最小。一般情况下处理有噪声的小数据集，我们应选择 $w$ ，使误差最小及其范数最小。

$\xi=(y-g(x))$ 为误差， $f((x,y))=\lvert{y-g(x)}\rvert=\lvert{\xi} \rvert$ ，寻找一个映射函数使得训练误差最小。通常选择误差的平方和 $\rm{L}(g,S)=\rm{L}(w,S)={\sum_{i=1}^{l} (y_{i}-g((x_{i}))^2}=\sum_{i=1}^{l}\xi_{i}^2$ ，寻找 $w\in W$ 使得训练误差总和（collective loss）最小。