# 写在前面

介绍核方法中的非线性投影技巧(Nonlinear Projection Trick in Kernel Methods)。

# 核方法

核方法是将数据通过核函数转化为核矩阵，再运用模式识别算法进行分析。因此，核方法提供了模块化框架

  • 在高维（甚至无限维）向量空间中映射数据。
  • 在这样的空间中寻找（线性）关系。

如果映射选得足够合适，再复杂的关系也可以简化且容易检测到。

p.s. 这也意味着需要大量尝试核函数并探索先验信息。多核学习(Multiple Kernel Learning)，即基本核函数进行线性组合，通过参数学习来达到更优的结果。当然，这也可能会带来计算复杂和过拟合。

# 核技巧

核矩阵通过内积或ℓ2\ell_2范数的形式描述嵌入空间数据的几何信息，被应用至大量机器学习算法中。但当算法不具备内积或ℓ2\ell_2范数的形式时，例如基于ℓ1\ell_1范数或非凸度量等优化问题，核技巧将不在适用。

因此，能否通过核方法找到输入数据到嵌入特征空间的直接映射吗？

# 核空间的几何结构

  • 训练样本集XX的核映射Φ(X)=[ϕ(x1),…,ϕ(xn)]\Phi(X) = [\phi(x_1),\ldots,\phi(x_n)]组成特征空间的rr维子空间PP的正交基

设核矩阵K=Φ(X)TΦ(X)K = \Phi(X)^T \Phi(X)的秩为rr，其特征分解K=UΛUTK = U \Lambda U^T，则矩阵

Π=Φ(X)UΛ−12\Pi = \Phi(X) U \Lambda^{-\frac{1}{2}}

的列πi=Φ(X)uiλi−12\pi_i = \Phi(X) u_i \lambda_i^{-\frac{1}{2}}构成PP的正交基。

  • 训练样本xx的核映射ϕ(x)\phi(x)在子空间KK上的投影ϕP(x)\phi_P(x)的坐标

设核向量k(x)=Φ(X)Tϕ(x)k(x) = \Phi(X)^T\phi(x)

ϕP(x)=ΠΠTϕ(x)=ΠΛ−12UTk(x)\phi_P(x) = \Pi\Pi^T\phi(x) = \Pi \Lambda^{-\frac{1}{2}}U^T k(x)

ϕP(x)\phi_P(x)可视为样本xx到由Π\Pi张成子空间的非线性映射，映射后的直接产物为x→y=Λ−12UTk(x)x \to y = \Lambda^{-\frac{1}{2}}U^T k(x)。

  • 样本集XX非线性映射后得到的坐标为

Y=Λ−12UTK=Λ12UTY = \Lambda^{-\frac{1}{2}}U^T K = \Lambda^{\frac{1}{2}}U^T

那么问题来了，坐标唯一吗？注意到：

K=UΛUT=YTY(SVD)K=Y′TY′(Cholesky decomp)⇒Y′=VΛ12UT=VY(SVD)\begin{aligned} K &= U\Lambda U^T = Y^T Y \quad\text{(SVD)}\\ K &= Y^{\prime T}Y^{\prime} \quad\text{(Cholesky decomp)}\\ \Rightarrow Y^{\prime} &= V\Lambda^{\frac{1}{2}}U^T = VY \quad\text{(SVD)} \end{aligned}

其中Y′Y^{\prime}是唯一确定的，而VV是酉阵，因此YY的结果虽然不唯一，但是仅于Y′Y^{\prime}存在一个旋转。

  • 训练集合的均值

若训练集合核映射后的特征矩阵是以原点为中心的，即满足∑iϕ(xi)=0\sum_i \phi(x_i) = 0，则映射后的点yiy_i也是以原点为中心的，即∑iyi=0\sum_i y_i = 0。但在实际应用中，这一假设过于理想，因此中心化处理非常有必要。

  • 残差的坐标

设增广数据集X′=[X,x]X^\prime = [X,x]，投影Φ(X′)=[Φ(X),ϕ(x)]\Phi(X^\prime) = [\Phi(X), \phi(x)]，残差为δϕP(x)=ϕ(x)−ϕP(x)(≠0)\delta\phi_P(x) = \phi(x)-\phi_P(x)(\neq 0)，则

Φ(X′)\Phi(X^\prime)位于包含PP的r+1r+1维子空间，Φ(X)\Phi(X)的坐标为[YT,0]T[Y^T,0]^T，ϕ(x)\phi(x)的坐标为[yT,k(x,x)−yTy]T[y^T,\sqrt{k(x,x)-y^Ty}]^T。

  • ww的坐标

如果空间PP中的向量具有形式w=Φ(X)αw=\Phi(X)\alpha，则也可表示为w=Πβw = \Pi \beta，其中β=Yα\beta = Y \alpha为ww在PP中的坐标。

  • ϕw(x)\phi_w(x)的坐标

核映射ϕ(x)\phi(x)在ww上的投影ϕw(x)=Πγ\phi_w(x) = \Pi \gamma，其中γ=ββTβTβy\gamma = \frac{\beta\beta^T}{\beta^T\beta}y为ϕw(x)\phi_w(x)的坐标。

  • 中心化

记Ψ(X)=[ψ(x1),…,ψ(xn)]\Psi(X) = [\psi(x_1),\ldots,\psi(x_n)]为未中心化数据的特征，其均值ψˉ=1n∑i=1nψ(xi)\bar \psi = \frac{1}{n} \sum_{i=1}^n \psi(x_i)。κ(a,b)=ψ(a)Tψ(b)\kappa(a,b) = \psi(a)^T\psi(b)为未中心化的核函数，K=Ψ(X)TΨ(X)\mathcal K = \Psi(X)^T\Psi(X)为未中心化的核矩阵，κ(x)=[κ(x1,x),…,κ(xn,x)]T\kappa(x) = [\kappa(x_1,x),\ldots,\kappa(x_n,x)]^T为未中心化的核向量。

中心化特征、中心化核矩阵、中心化核向量

Φ(X)=Ψ(X)−ψˉ1nT=Ψ(X)(In−En)K=Φ(X)TΦ(X)=(In−En)K(In−En)k(x)=Φ(X)Tϕ(x)=(In−En)[κ(x)−1nK1n]\begin{aligned} \Phi(X) &= \Psi(X) - \bar \psi 1_n^T = \Psi(X)(I_n - E_n)\\ K &= \Phi(X)^T \Phi(X) = (I_n - E_n)\mathcal K(I_n - E_n)\\ k(x) &= \Phi(X)^T \phi(x) = (I_n - E_n)[\kappa(x) - \frac{1}{n}\mathcal K 1_n] \end{aligned}

其中，En=1n1n1nTE_n = \frac{1}{n} 1_n 1_n^T。

# 核方法

# 算法应用

# KPCA

arg⁡min⁡w∥wTΦ(X)∥22s.t.∥w∥2=2\arg\min_w \|w^T\Phi(X)\|_2^2 \quad \text{s.t.} \quad \|w\|_2 = 2

  • 核技巧

    • 计算散度矩阵Sf=Φ(X)Φ(X)TS_f = \Phi(X)\Phi(X)^T的特征分解

      Sfwi=λiwiS_f w_i = \lambda_i w_i

    • 利用w=Φ(X)αw = \Phi(X) \alpha，得到

      Kαi=λiαiK\alpha_i = \lambda_i \alpha_i

    • 解

      αi=uiλi−12\alpha_i = u_i \lambda_i^{-\frac{1}{2}}

    • 非线性特征为

      z=WTϕ(x)=Λm−12UmTk(x)z = W^T\phi(x)=\Lambda_m^{-\frac{1}{2}} U_m^T k(x)

  • 非线性投影技巧

    • 非线性投影

      Y=Λ12UTY = \Lambda^{\frac{1}{2}}U^T

    • 计算散度矩阵

    SY=YYT=Λ S_Y = YY^T = \Lambda

    • 非线性特征

      z=Λm−12UmTk(x)z = \Lambda_m^{-\frac{1}{2}} U_m^T k(x)

# SVM

arg⁡min⁡w,b12∥w∥22s.t.ci(wTϕ(xi)+b)≥1∀i\arg\min_{w,b} \frac{1}{2} \|w\|_2^2 \quad \text{s.t.} \quad c_i (w^T\phi(x_i)+b)\geq 1 \quad \forall i

  • 核技巧

    • Lagrange乘子对偶形式

      arg⁡max⁡α∑i=1nαi−12∑i,j=1nαiαjcicjk(xi,xj)s.t.∑i=1nαici=0,αi≥0∀i\begin{aligned} &\arg\max_\alpha \sum_{i=1}^n \alpha_i -\frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j c_i c_j k(x_i,x_j) \\ &\text{s.t.} \quad \sum_{i=1}^n \alpha_ic_i = 0, \alpha_i \geq 0 \quad \forall i \end{aligned}

    • ww的结果为

      w=∑i=1nαiciϕ(xi)⇒wTϕ(x)=∑i=1nαicik(xi,x)w=\sum_{i=1}^n \alpha_i c_i \phi(x_i) \Rightarrow w^T\phi(x)=\sum_{i=1}^n \alpha_i c_i k(x_i, x)

    • bb的结果可由约束条件的KKT条件得到

    • 测试样本xx分类

      sgn(wTϕ(x)+b)\text{sgn}(w^T\phi(x)+b)

  • 非线性投影技巧

    • 非线性投影

      Y=Λ12UTY = \Lambda^{\frac{1}{2}}U^T

    • 原始问题

      arg⁡min⁡v,d12∥v∥22s.t.ci(vTϕ(yi)+d)≥1∀i\arg\min_{v,d} \frac{1}{2} \|v\|_2^2 \quad \text{s.t.} \quad c_i (v^T\phi(y_i)+d)\geq 1 \quad \forall i

    • 对偶问题

      arg⁡max⁡β∑i=1nβi−12∑i,j=1nβiβjcicjyiTyjs.t.∑i=1nβici=0,βi≥0∀i\begin{aligned} &\arg\max_\beta \sum_{i=1}^n \beta_i -\frac{1}{2}\sum_{i,j=1}^n \beta_i \beta_j c_i c_j y_i^T y_j \\ &\text{s.t.} \quad \sum_{i=1}^n \beta_ic_i = 0, \beta_i \geq 0 \quad \forall i \end{aligned}

      注意：k(xi,xj)=yiTyjk(x_i,x_j) = y_i^Ty_j

    • vv的结果为

      v=∑i=1nβiciyiv=\sum_{i=1}^n \beta_i c_i y_i

    • 测试样本xx首先映射为y=Λ−12UTk(x)y=\Lambda^{-\frac{1}{2}} U^T k(x)，再分类

      sgn(vTϕ(y)+d)\text{sgn}(v^T\phi(y)+d)

# PCA-L1

  • 原始形式

    arg⁡max⁡w∥wTX∥1s.t.∥w∥2=1\arg\max_w\|w^T X\|_1 \quad \text{s.t.} \quad \|w\|_2 =1

  • 核技巧

    arg⁡max⁡w∥wTΦ(X)∥1s.t.∥w∥2=1\arg\max_w\|w^T \Phi(X)\|_1 \quad \text{s.t.} \quad \|w\|_2 =1

    该问题不是基于ℓ2\ell_2范数的优化问题，因此不容易求解。

  • 非线性投影技巧

    通过非线性投影Y=Λ12UTY = \Lambda^{\frac{1}{2}}U^T后，

    w=Πβ,∥w∥2=∥β∥2=1,wTΦ(X)=βTYw=\Pi \beta,\|w\|_2 = \|\beta\|_2 =1, w^T\Phi(X) = \beta^T Y

    原问题转化为

    arg⁡max⁡β∥βTY∥1s.t.∥β∥2=1\arg\max_\beta\|\beta^T Y\|_1 \quad \text{s.t.} \quad \|\beta\|_2 =1

    显然，这两问题形式上一致，因此可使用PCA-L1算法（见基于L1范数的主成分分析 (opens new window)）来解决KPCA-L1问题。

# References

L1/L2最小化的加速算法