PCA和KPCA的SVM形式

机器学习

---

PCA的SVM形式

PCA的目标是找到合适投影方向实现方差最大化：

$$max_{w} \sum _{k=1} ^N (0-w^Tx_k)^2$$

从目标出发还有一种表达：

$$max _{w, e} J_P(w, e)= \gamma \frac{1}{2} \sum _{k=1} ^N e_k^2 -\frac{1}{2} w^Tw$$

$$e_k = w^Tx_k, \ k=1, ...N$$

这种表达没有了之前特种空间基向量要求是单位向量的限制，新的限制体现在只需要尽量小即可。

同样用Lagrangian求解：

$$L(w, e;\alpha) = \gamma \frac{1}{2} \sum _{k=1} ^N e_k^2 -\frac{1}{2} w^Tw- \sum _{k=1} ^N \alpha _k(e_k - w^ T x_k)$$

求偏导得：

$$\frac {\partial L}{\partial w} = 0 \ \rightarrow w = \sum _{k=1} ^N \alpha _k x_k$$

$$\frac {\partial L}{\partial e_k} = 0 \ \rightarrow \alpha _k = \gamma x_k, \ k= 1, ...,N$$

$$\frac {\partial L}{\partial \alpha _k} = 0 \ \rightarrow e _k - w^Tx_k= 0, \ k= 1, ...,N$$

消去$e, w$，得：

$$\frac{1}{\gamma}\alpha _k - \sum _{l=1}^N \alpha_l x_l^T x_k = 0, k=1, ..., N$$

写成矩阵形式：

$$\begin{bmatrix} x_1^Tx_1 \quad ... \quad x_1^Tx_N \\ \vdots \qquad \qquad \vdots \\x_N^Tx_1 \quad ... \quad x_N^Tx_N \end{bmatrix} \begin{bmatrix} \alpha _1 \\\vdots \\ \alpha _N \end{bmatrix}= \lambda \begin{bmatrix} \alpha _1 \\\vdots \\ \alpha _N \end{bmatrix}$$

其中 $\lambda = \frac{1}{\gamma}$

以上表明最优解时$\lambda$是协方差矩阵的特征值。

下面说明最优解是最大特征值对应的特征向量。

$$\sum _{k=1} ^N (w^T x_k)^2 = \sum _{k=1} ^N (e_k)^2 = \sum _{k=1} ^N (\frac{1}{ \gamma ^2})(\alpha _k)^2 = \lambda _{max} ^2$$

投影向量为：

$$z(x) = w^T x = \sum _{l=1}^N \alpha _l x_l^T x$$

题外话：
1. 每一个投影向量都是不相关的，因为$\alpha$向量都是正交的。并且特征空间的基$w$是相互正交的。
2. $\alpha$ 向量的归一化，将会导出 $w^Tw = \lambda$，这个和原本的约束$w^Tw = 1$非常不一样

KPCA的SVM形式

KPCA的目标是在特征空间找到合适投影方向实现方差最大化：

$$max_{w} \sum _{k=1} ^N (0-w^T(\phi(x_k)- \hat \mu _{\phi}))^2$$

其中$\hat \mu _{\phi} = \frac{1}{N} \sum _{k=1} ^N \phi (x_k)$

从目标出发还有一种表达：

$$max _{w, e} J_P(w, e)= \gamma \frac{1}{2} \sum _{k=1} ^N e_k^2 -\frac{1}{2} w^Tw$$

$$e_k = w^T(\phi(x_k)- \hat \mu _{\phi}), \ k=1, ...N$$

这种表达没有了之前对齐要求是单位向量的限制，新的限制体现在只需要尽量小即可。

同样用Lagrangian求解：

$$L(w, e;\alpha) = \gamma \frac{1}{2} \sum _{k=1} ^N e_k^2 -\frac{1}{2} w^Tw- \sum _{k=1} ^N \alpha _k(e_k - w^T(\phi(x_k)- \hat \mu _{\phi}))$$

求偏导得：

$$\frac {\partial L}{\partial w} = 0 \ \rightarrow w = \sum _{k=1} ^N \alpha _k (\phi(x_k)- \hat \mu _{\phi})$$

$$\frac {\partial L}{\partial e_k} = 0 \ \rightarrow \alpha _k = \gamma x_k, \ k= 1, ...,N$$

$$\frac {\partial L}{\partial \alpha _k} = 0 \ \rightarrow e _k - w^T(\phi(x_k)- \hat \mu _{\phi})= 0, \ k= 1, ...,N$$

消去$e, w$，得：

$$\frac{1}{\gamma}\alpha _k - \sum _{l=1}^N \alpha_l (\phi(x_l)- \hat \mu _{\phi})^T (\phi(x_l)- \hat \mu _{\phi}) = 0, k=1, ..., N$$

写成矩阵形式：

$$\Omega _c \alpha = \lambda \alpha$$

其中 $\lambda = \frac{1}{\gamma}$, $\Omega _{c, kl} = (\phi(x_k)- \hat \mu _{\phi})^T(\phi(x_l)- \hat \mu _{\phi}), \quad k,l=1,..,.N$

$\Omega _c$是可以用kernel function表示的：

$$\Omega _c = K(x_k, x_l)- \frac{2}{N} \sum_{r=1}^{N} K(x_k, x_r)+ \frac{1}{N^2} \sum_{r=1}^{N} \sum _{s = 1}^N K(x_r, x_s) = M_c \Omega M_c$$

其中，

$$M_c = I -\frac{1}{N}1_v 1_v^T$$

以上表明最优解时$\lambda$是协方差矩阵的特征值。

说明最优解是最大特征值对应的特征向量(略)。

投影向量为：

$$z(x) = w^T (\phi(x_k)- \hat \mu _{\phi}) = \sum _{l=1}^N \alpha _l ( K(x_l, x)- \frac {1}{N}\sum_{r=1}^{N} K(x_r, x)- \frac {1}{N}\sum_{r=1}^{N} K(x_r, x_l)\\+\frac{1}{N^2} \sum_{r=1}^{N} \sum _{s = 1}^N K(x_r, x_s))$$

参考文献

[1] Suykens J A K, Van Gestel T, Vandewalle J, et al. A support vector machine formulation to PCA analysis and its kernel version[J]. IEEE Transactions on neural networks, 2003, 14(2): 447-450.