Kernel Method
- 把低维空间的非线性问题，转化到高维空间的线性问题求解
Kernel trick
- 使用核函数减少计算量，避免计算高维特征空间的内积（计算角度）
Kernel Function
-
把输入空间𝓧 映射（任意形式$ϕ(x)$）到高维特征空间𝓩
$$ K(x,x’)=\phi(x)^T \phi(x’) $$
-
为什么是：
-
非线性带来高维转换:
线性分类最完美的情况:二分类问题严格线性可分，即存在一个或多个线性超平面可以把两类正确分开，不同的初值最终收敛的结果不同。对于非线性输入无法收敛。
对于不同的输入数据，采用不同的算法：
线性可分 线性不可分 存在一点点非线性 严格非线性 PLA Pocket Algorithm 多层感知机(隐藏层数≥1,逼近任一连续函数);
非线性转换(Cover Therom: 高维比低维更易线性可分)Hard-margin SVM Soft-margin SVM Kernel SVM(先做非线性转换，再做SVM) -
对偶表示带来内积:
SVM的思想是最大间隔分类，是一个（凸）优化问题。然后根据拉格朗日对偶性，转化为求解原问题的对偶问题:
$$ \begin{array}{c} \begin{array}{cc} 原问题\ \begin{cases} \underset{\mathbf w,b}{\operatorname{min}}\ \frac{1}{2} \mathbf w^T \mathbf w \ s.t. \quad y_i(\mathbf w^T x_i + b) \geq 1 \end{cases} \end{array}
\Longrightarrow\begin{array}{cc} 对偶问题\ \begin{cases} \underset{\lambda}{\operatorname{min}}\ \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \lambda_i \lambda_j y_i y_j \mathbf x_i^T \mathbf x_j - \sum_{i=1}^N \lambda_i \ s.t. \quad \lambda_i \geq 0, \quad \forall i=1,…,N \ \ \qquad \sum_{i=1}^N \lambda_i y_i =0 \end{cases} \end{array}
\end{array}
$$
Dual Problem 包含内积: $\mathbf x_i^T \mathbf x_j$，即需要求解任意两个数据之间的内积
而对于非线性可分问题，做了非线性转换之后，内积变为：$\phi(x_i)^T \phi(x_j)$，但是对于高维空间的 $\phi(x)$，由于维度太高很难求。 所以希望找到一个函数直接求内积: $K(\mathbf{x,x’})$，而避免求单个特征的 $\phi(x)$
数学表示：
$$ \forall \mathbf{x,x’} \in \mathcal X,\quad \exist \phi: \mathcal X \rightarrow \mathcal Z s.t. \quad K(\mathbf{x,x’}) = \phi(\mathbf x)^T \phi(\mathbf x’) = <\phi(\mathbf x) \phi(\mathbf x’)> 则称：K(\mathbf{x,x’}) 是一个核函数 $$
将(输入空间的)样本代入核函数即可算出(高维空间的)内积，减少了计算量
-