本文不做数学推导,仅从最简单的概念上讲解核方法。
问题
有训练样本 x i x_i xi,其标定 y i y_i yi, i=1,2…N。
欲求解一个回归函数 f ( z ) f(z) f(z),希望 f ( x i ) = y i f(x_i)=y_i f(xi)=yi。
线性回归
使用线性函数来预测,即 f ( z ) = w T z f(z)=w^Tz f(z)=wTz。
求解方法有许多种,以脊回归(Ridge Regression)为例,最小化下列函数即可:
λ ∣ ∣ w ∣ ∣ 2 + ∑ i ( w T x i − y i ) 2 \lambda||w||^2+\sum_i(w^Tx_i-y_i)^2 λ∣∣w∣∣2+i∑(wTxi−yi)2
这个最小化问题有闭式解:
w = ( X T X + λ I ) − 1 X T y w=(X^T X+\lambda I)^{-1}X^Ty w=(XTX+λI)−1XTy
其中, X X X的第i行为 x i x_i xi,列向量 y y y的第i元素为 y i y_i yi。
非线性回归
使用非线性函数来预测,即 f ( z ) f(z) f(z)是关于 z z z的非线性函数。
非线性函数能够处理线性函数搞不定的分类问题。
非线性函数的估计较难,为了提高效率,引入了核方法。
核方法
对 z z z进行一个非线性变换 ψ \psi ψ, f ( z ) f(z) f(z)是变换结果的线性函数:
f ( z ) = w T ψ ( z ) f(z)=w^T\psi(z) f(z)=wTψ(z)
w w w由训练样本的非线性变换 ψ ( x i ) \psi(x_i) ψ(xi)的线性组合构成:
w = ∑ i α i ψ ( x i ) w=\sum_i\alpha_i\psi(x_i) w=i∑αiψ(xi)
两者结合,得到完整形式:
f ( z ) = [ ∑ i α i ψ ( x i ) ] ψ ( z ) = ∑ i [ α i ψ ( x i ) ψ ( z ) ] f(z)=\left[ \sum_i\alpha_i\psi(x_i) \right] \psi(z)= \sum_i\left[ \alpha_i\psi(x_i)\psi(z)\right] f(z)=[i∑αiψ(xi)]ψ(z)=i∑[αiψ(xi)ψ(z)]
记 κ ( x i , x j ) = ψ ( x i ) ψ ( x j ) \kappa(x_i,x_j)=\psi(x_i)\psi(x_j) κ(xi,xj)=ψ(xi)ψ(xj),称为核函数。则:
f ( z ) = ∑ i α i κ ( z , x i ) = α T κ ( z ) f(z)=\sum_i\alpha_i\kappa(z,x_i)=\alpha^T\kappa(z) f(z)=i∑αiκ(z,xi)=αTκ(z)
α \alpha α为 N × 1 N\times1 N×1矢量, κ ( z ) \kappa(z) κ(z)为 N × 1 N\times1 N×1,第i个元素为训练样本 x i x_i xi和测试样本 z z z的核函数值。
f ( z ) f(z) f(z)是关于 z z z的非线性函数,但却是关于 κ ( z ) \kappa(z) κ(z)的线性函数,可以使用线性函数的优化方法求解 α \alpha α。
同样以脊回归为例:
α = ( K + λ I ) − 1 y \alpha = (K+\lambda I)^{-1}y α=(K+λI)−1y
注:这个解对于原问题相当于 w = X − 1 y w=X^{-1}y w=X−1y,不过原问题中 X X X不是方阵,所以要写成矩阵伪逆的形式。
我们称,原始参数 w w w处于原空间prime space中,新参数 α \alpha α则处于对偶空间dual space中。
和真正的线性方法比起来,核方法在估计每一个 z z z的标签时,需要计算 z z z和训练集中每一个样本 x i x_i xi的核函数 κ ( z , x i ) \kappa(z,x_i) κ(z,xi)。其复杂度和训练集大小相关。