P1-背景介绍

Kernel Method

• 把低维空间的非线性问题，转化到高维空间的线性问题求解

Kernel trick

• 使用核函数减少计算量，避免计算高维特征空间的内积（计算角度）

Kernel Function

• 把输入空间𝓧 映射（任意形式$ϕ(x)$）到高维特征空间𝓩

  $$ K(x,x')=\phi(x)^T \phi(x') $$

• 为什么是：

  1. 非线性带来高维转换:

     线性分类最完美的情况:二分类问题严格线性可分，即存在一个或多个线性超平面可以把两类正确分开，不同的初值最终收敛的结果不同。对于非线性输入无法收敛。

     对于不同的输入数据，采用不同的算法：

     线性可分	线性不可分
     	存在一点点非线性	严格非线性
     PLA	Pocket Algorithm	多层感知机(隐藏层数≥1,逼近任一连续函数); 非线性转换(Cover Therom: 高维比低维更易线性可分)
     Hard-margin SVM	Soft-margin SVM	Kernel SVM(先做非线性转换，再做SVM)

  2. 对偶表示带来内积:

     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'}) 是一个核函数 $$

     将(输入空间的)样本代入核函数即可算出(高维空间的)内积，减少了计算量