Question

1. PCA方法假设从高维空间到低维空间的映射是线性的，但是在不少现实任务中可能需要非线性映射才能找到合适的低维空间来降维。

   非线性降维的一种常用方法是基于核技巧对线性降维方法进行核化kernelized， 如核主成分分析Kernelized PCA:KPCA ，它是对PCA的一种推广。

2. 假定原始特征空间中的样本点 $ MathJax-Element-917 $ 通过映射 $ MathJax-Element-241 $ 映射到高维特征空间的坐标为 $ MathJax-Element-231 $ ，即 $ MathJax-Element-232 $ 。且假

   设高维特征空间为 $ MathJax-Element-897 $ 维的，即： $ MathJax-Element-234 $ 。假定要将高维特征空间中的数据投影到低维空间中，投影矩阵为 $ MathJax-Element-775 $ 为 $ MathJax-Element-236 $ 维矩阵。

   根据 PCA 推导的结果，求解方程： $ MathJax-Element-252 $ 。其中 $ MathJax-Element-238 $ 为 $ MathJax-Element-239 $ 维矩阵。

   于是有： $ MathJax-Element-240 $ 。

3. 通常并不清楚 $ MathJax-Element-241 $ 的解析表达式，因此并不会直接得到 $ MathJax-Element-242 $ ，所以无法直接求解方程： $ MathJax-Element-252 $ 。

   于是引入核函数： $ MathJax-Element-244 $ 。

   • 定义核矩阵 ：
     

     $ \mathbf K=\begin{bmatrix} \kappa(\mathbf{\vec x}_1,\mathbf{\vec x}_1)&\kappa(\mathbf{\vec x}_1,\mathbf{\vec x}_2)&\cdots&\kappa(\mathbf{\vec x}_1,\mathbf{\vec x}_N)\\ \kappa(\mathbf{\vec x}_2,\mathbf{\vec x}_1)&\kappa(\mathbf{\vec x}_2,\mathbf{\vec x}_2)&\cdots&\kappa(\mathbf{\vec x}_2,\mathbf{\vec x}_N)\\ \vdots&\vdots&\ddots&\vdots\\ \kappa(\mathbf{\vec x}_N,\mathbf{\vec x}_1)&\kappa(\mathbf{\vec x}_N,\mathbf{\vec x}_2)&\cdots&\kappa(\mathbf{\vec x}_N,\mathbf{\vec x}_N)\\ \end{bmatrix} $

     则有： $ MathJax-Element-255 $ 。

   • 定义 $ MathJax-Element-246 $ ，则 $ MathJax-Element-265 $ 为 $ MathJax-Element-248 $ 维行向量 。定义： $ MathJax-Element-249 $ 为 $ MathJax-Element-250 $ 维矩阵

     则有：

   $ \mathbf W=\frac 1\lambda \left(\sum_{i=1}^{N}\mathbf{\vec x}_{i,\phi}\mathbf{\vec x}_{i,\phi}^{T}\right)\mathbf W=\sum_{i=1}^{N}\mathbf{\vec x}_{i,\phi}\frac{\mathbf{\vec x}_{i,\phi}^{T}\mathbf W}{\lambda}=\sum_{i=1}^{N}\mathbf{\vec x}_{i,\phi}\vec \alpha_i =\mathbf X_{\phi}^T\mathbf A $

4. 将 $ MathJax-Element-251 $ 代入 $ MathJax-Element-252 $ ，有： $ MathJax-Element-253 $ 。

   • 两边同时左乘以 $ MathJax-Element-254 $ ，再代入 $ MathJax-Element-255 $ 有： $ MathJax-Element-256 $ 。

   • 通常会要求核矩阵可逆，上式两边同时左乘以 $ MathJax-Element-257 $ ，则有： $ MathJax-Element-258 $ 。

     同样该问题也是一个特征值分解问题，取 $ MathJax-Element-259 $ 最大的 $ MathJax-Element-586 $ 个特征值对应的特征向量组成 $ MathJax-Element-698 $ 即可。

5. 对于新样本 $ MathJax-Element-262 $ ， 其投影后第 $ MathJax-Element-875 $ 维的坐标为：

   $ z_j=\mathbf{\vec w}_j^{T}\phi(\mathbf{\vec x})=\sum_{i=1}^{N}\alpha_{i,j}\phi(\mathbf{\vec x}_i)^{T}\phi(\mathbf{\vec x})=\sum_{i=1}^{N} \alpha_{i,j} \kappa(\mathbf{\vec x}_i,\mathbf{\vec x}) $

   其中 $ MathJax-Element-264 $ 为行向量 $ MathJax-Element-265 $ 的第 $ MathJax-Element-875 $ 个分量。

   可以看到：为了获取投影后的坐标， KPCA需要对所有样本求和，因此它的计算开销较大。