核化线性降维

【概述】

线性降维方法假设从高维空间到低维空间的函数映射是线性的，但在实际应用中，可能需要非线性映射才能找到合适的低维嵌入

如下图所示，样本点从二维空间中的矩形区域采样后，以 S 形曲面嵌入到三维空间，若直接使用线性降维方法对三维空间观察到的样本点进行降维，则将丢失原本的低维结构

核化线性降维（Kernelized Linear Dimensionality Reduction），是指利用核函数对线性降维方法进行核化（Kernelized），常见的核化线性降维方法有：

• 核主成分分析（Kernelized Principal Component Analysis，Kernelized PCA）
• 核线性判别分析（Kernelized Linear Discriminant Analysis，Kernelized LDA）

关于核函数，详见：特征构建与核方法

【核主成分分析】

投影矩阵

核主成分分析（Kernelized Principal Component Analysis，KPCA）是利用核函数对主成分分析进行核化（Kernelized）

对于给定的样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\}$，第 $i$ 个样本 $\mathbf{x}_i$ 具有 $m$​ 个特征值

假设可以通过某种映射 $\phi:\mathcal{X}\mapsto\mathbb{F}$ 将样本 $\mathbf{x}_i$ 映射到一个特征空间 $\mathbb{F}$ 中，即：

$$\mathbf{z}_i = \phi(\mathbf{x}_i)$$

此时称 $\mathbf{z}_i$ 为 $\mathbf{x}_i$ 在特征空间 $\mathbb{F}$ 中的像

假设在特征空间中，要将原始数据通过投影矩阵 $W$​ 来投影在由 $W$ 确定的超平面上，即：

$$\Big(\sum_{i=1}^n \mathbf{z}_i\mathbf{z}_i^T \Big) W = \lambda W$$

那么有：

$$\begin{align*} W &= \frac{1}{\lambda} \Big(\sum_{i=1}^{n} \mathbf{z}_i \mathbf{z}_i^T\Big) W \\ &= \sum_{i=1}^n \mathbf{z}_i \frac{\mathbf{z}_i^TW}{\lambda} \\ &= \sum_{i=1}^n \mathbf{z}_i \boldsymbol{\alpha}_i \\ &= \sum_{i=1}^n \phi(\mathbf{x}_i) \boldsymbol{\alpha}_i \\ \end{align*}$$

其中，$\boldsymbol{\alpha}_i$ 为变换向量，即：

$$\boldsymbol{\alpha}_i = \frac{1}{\lambda}\mathbf{z}_i^TW = \frac{1}{\lambda}\phi(\mathbf{x}_i^T)W$$

核函数的引入

若 $\phi$ 能被显式表达出来，那么通过它将样本映射到高维特征空间，再在特征空间中实施 PCA 即可

但一般情况下，并不清楚 $\phi$ 的具体形式，于是引入核函数

$$K(\mathbf{x}_i,\mathbf{x}_j) = \phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j)$$

令 $\mathbf{K}\in\mathbb{R}^{m\times m}$ 为核函数 $K(\mathbf{x}_i,\mathbf{x}_j)$ 对应的核矩阵，$A=[\boldsymbol{\alpha}_1,\boldsymbol{\alpha}_2,\cdots,\boldsymbol{\alpha}_n]^T$ 为变换矩阵，那么将核函数带入 $W=\sum\limits_{i=1}^n \phi(\mathbf{x}_i) \boldsymbol{\alpha}_i$ 中，化简后有：

$$\mathbf{K}A = \lambda A$$

显然，这是一个特征值分解问题，取 $\mathbf{K}$ 最大的 $k$ 个特征值对应的特征向量即可

此时，对于样本 $\mathbf{x}$，其投影后的第 $j=1,2,\cdots,k$ 维坐标为：

$$\begin{align*} z_j &= \mathbf{w}_j^T \phi(\mathbf{x}) \\ &= \sum_{i=1}^n \alpha_{ij} \phi(\mathbf{x}_i)^T\phi(\mathbf{x}) \\ &= \sum_{i=1}^n \alpha_{ij} K(\mathbf{x}_i,\mathbf{x}) \end{align*}$$

可以看出，为了获得投影后的坐标，KPCA 需要对所有样本求和，因此其计算开销较大

【核线性判别分析】

均值向量

核线性判别分析（Kernelized Linear Discriminant Analysis，KLDA）是利用核函数对线性判别分析 LDA 进行核化（Kernelized）

对于给定的样本集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_n,y_n)\}$，第 $i$ 个样本的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i = (x_i^{(1)},x_i^{(2)},\cdots,x_i^{(m)})\in \mathbb{R}^{m}$，输出 $y_i\in\{C_1,C_2,\cdots,C_K\}$

由于一共有 $K$ 类，假设每一类的样本个数分别为 $N_1,N_2,\cdots,N_K$，用 $X_k=\{\mathbf{x}_1^{k},\mathbf{x}_2^{k},\cdots,\mathbf{x}_{N_k}^{k}\}$ 来表示第 $k$​ 类中的样本

假设可以通过某种映射 $\phi:\mathcal{X}\mapsto\mathbb{F}$ 将样本 $\mathbf{x}$ 映射到一个特征空间 $\mathbb{F}$ 中，然后在 $\mathbb{F}$ 中执行 LDA，以求得：

$$h(\mathbf{x}) = \mathbf{w}^T\phi(\mathbf{x})$$

若第 $k$ 类样本的数据集为 $D_k$，则第 $k$ 类样本在特征空间 $\mathbb{F}$ 中的均值均值向量为：

$$\mathbf{m}^{\phi} = \frac{\sum\limits_{\mathbf{x}\in D_k} \mathbf{x}}{N_k}$$

散度矩阵

与 LDA 类似，样本在特征空间 $\mathbb{F}$ 中的类间散度矩阵 $S_b^{\phi}$ 和类内散度矩阵 $S_{w}^{\phi}$ 为：

$$\begin{gather*} S_b^{\phi} = \sum_{i,j,i\neq j} (\mathbf{m}_i^{\phi}-\mathbf{m}_j^{\phi}) (\mathbf{m}_i^{\phi}-\mathbf{m}_j^{\phi})^T\\ S_w^{\phi} = \sum_{k=1}^K \Big( \frac{\sum\limits_{\mathbf{x}\in D_k} \mathbf{x}\mathbf{x}^T}{N_k} - \mathbf{m}\mathbf{m}^T\Big) \end{gather*}$$

核函数的引入

与 LDA 类似，KLDA 的优化目标是：

$$\max_{\mathbf{w}} J(\mathbf{w}) = \frac{\mathbf{w}^TS_b^{\phi}\mathbf{w}}{\mathbf{w}^TS_{w}^{\phi}\mathbf{w}}$$

通常来说，映射 $\phi$ 的具体形式难以得知，因此使用核函数来隐式表达映射 $\phi$ 和特征空间 $\mathbb{F}$，即：

$$K(\mathbf{x},\mathbf{x}_i) = \phi(\mathbf{x}_i)^T\phi(\mathbf{x})$$

根据核函数的表示定理，优化问题的解可写为：

$$h(\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x},\mathbf{x}_i)$$

故而可得：

$$\mathbf{w} = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i)$$

令 $\mathbf{K}\in\mathbb{R}^{m\times m}$ 为核函数 $K(\mathbf{x},\mathbf{x}_i)$ 对应的核矩阵，令 $\mathbf{1}_k\in \{C_1,C_2,\cdots,C_K\}^{n\times 1}$ 为第 $k$ 类样本的指示向量，即 $\mathbf{1}_k$ 的第 $j$ 个分量为 $1$ 当且仅当 $\mathbf{x}_j\in X_k$，否则 $\mathbf{1}_k$ 的第 $j$ 个分量为 $0$

再令

$$\begin{gather*} \mathbf{m}_k = \frac{\mathbf{K} \mathbf{1}_k}{N_k} \\ M = \sum_{i,j,i\neq j} (\mathbf{m}_i^{\phi}-\mathbf{m}_j^{\phi}) (\mathbf{m}_i^{\phi}-\mathbf{m}_j^{\phi})^T \\ N = \mathbf{K}\mathbf{K}^T - \sum_{k=1}^K N_k \mathbf{m}_k\mathbf{m}_k^T \end{gather*}$$

于是，优化目标等价于：

$$\max_\boldsymbol{\alpha} J(\boldsymbol{\alpha}) = \frac{\boldsymbol{\alpha}^T M \boldsymbol{\alpha}}{\boldsymbol{\alpha}^T N \boldsymbol{\alpha}}$$

显然，此时再通过使用 LDA 的求解方法，即可得到 $\boldsymbol{\alpha}$，进而可利用 $h(\mathbf{x}) = \sum\limits_{i=1}^n \alpha_i K(\mathbf{x},\mathbf{x}_i)$ 来得到投影函数