表征学习、以及PCA的细节公式推导

Representation Learning 表征学习

这章将稍微讲讲表征学习，以及经典方法PCA。公式显示出现了一些问题，建议需要的阅读的可以先到 https://blog.csdn.net/chitoseyono/article/details/116021374 顺畅查阅。

机器学习算法的与否可行不仅仅取决于算法的正确选用，也取决于数据的质量和有效的数据表示（representation）。针对不同类型的数据（text，image，video），错误的表示方式可能会导致有效信息的缺失或是暴露，这决定了算法能否有效地解决问题。表征学习的目的是对复杂的原始数据化繁为简，把原始数据的无效的或者冗余的信息剔除，把有效信息进行提炼，形成特征（feature）。特征提取可以人为地手工处理，也可以借助特定的算法自动提取。Roughly Speaking， 前者（手动处理）称为特征工程，后者（借助算法）为表征学习（Representation Learning）。如果数据量较小，我们可以根据自身的经验和先验知识，人为地设计出合适的特征，用作下游的任务，比如分类；但数据量很大且复杂时，则需要依赖自动化的表征学习。

注意，这之后的章节内容都可能比较混乱/缺失，我尽量会把算法的关键思想说清，但是公式推导会有点跳步，请尽量搭配对每一章应参考资料查阅。

1. 表征学习：https://zhuanlan.zhihu.com/p/136554341
2. 流形学习：https://scikit-learn.org/stable/modules/manifold.htm
3. 稀疏表示，特征提取，特征选择：西瓜书
4. van der Maaten, Laurens & Postma, Eric & Herik, H.. (2007). Dimensionality Reduction: A Comparative Review. Journal of Machine Learning Research - JMLR. 10.
5. Anowar, Farzana & Sadaoui, Samira & Selim, Bassant. (2021). Conceptual and empirical comparison of dimensionality reduction algorithms (PCA, KPCA, LDA, MDS, SVD, LLE, ISOMAP, LE, ICA, t-SNE). Computer Science Review. 40. 10.1016/j.cosrev.2021.100378.

Representation Learning要做的一般有：

• Dimension Reduction 降维
• Manifold Learning 流式学习
• Sparse Representation 稀疏表示

目的：

• 减少算法训练/学习的开销，避免维数灾难
• 让数据更好可视化，更好理解与Debug
• 降低数据存储

The curse of dimensionality 维数灾难

在kNN上，我们发现任意测试样本 $x$ 附近任意小的 $δ$ 距离范围内，总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”(dense sample)。然而，这个假设在现实任务中通常很难满足，例如 $δ=0.001$，仅考虑单个属性，则仅需1000个样本点平均分布在归一化后的属性取值范围内，即可使得任意测试样本在其附近0.001距离范围内总能找到一个训练样本。此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。然而，这仅是属性维数为1的情形。若有更多的属性，则情况会发生显著变化。例如假定属性维数为20，若要求样本满足密采样条件，则至少需要$1000^{20}=10^{60}$个样本。现实应用中属性维数经常成千上万，要满足密采样条件约为所需的样本数目是无法达到的天文数字。此外，许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，当维数很高时甚至连计算内积都不再容易。

事实上，在高位情形下出现的数据样本稀疏、距离计算困难问题，是所有机器学习方法的共通障碍——维数灾难。

Feature Extraction vs Feature Selection 特征提取 vs 特征选择

Feature Extraction are ways to transform/project the original features in the data into new features which have some advantage such as

• Lower Dimensionality
• Better description of the variance in the data
• Better ability to distinguish data points or clusters of data points

Whereas Feature Selection is attempt to find a subset of the original features which satisfy some criteria. Ideally the selected subset includes the significant features and eliminates irrelevant and redundant features.

Methods of Feature Selection

• Feature Ranking
• Filter Approach, 如 Relevant Features (Relief)
• Wrapper approach, 如 Las Vegas Wrapper (LVW)
• Embedding approach

This Chapter is focus on Feature Extraction, though feature selection is needed to learned as when comes to some data analysis tasks.

Methods of Feature Extraction

• Linear Methods:
  • Unsupervised
    • PCA
    • ICA
  • Supervised
    • LDA
• Non-linear Methods:
  • Global (preserve global properties)
    • MDS
    • Isomap
    • Kernel PCA
  • Local (preserve properties within local neighborhood)
    • LLE
  • Global + Local
    • SNE

简单比较他们的性质：

Principal Component Analysis 主成分分析

参考资料：

1. 西瓜书 10.3
2. 拉格朗日函数：https://math.stackexchange.com/questions/1104376/how-to-set-up-lagrangian-optimization-with-matrix-constrains
3. Unsupervised and Supervised Principal Component Analysis: Tutorial
4. 花书 2.7, 2.8
5. M. Turk and A. Pentland, “Eigenfaces for recognition,” Journal of cognitive neuroscience, vol. 3, no. 1, pp. 71–86, 1991.
6. M. A. Turk and A. P. Pentland, “Face recognition using eigenfaces,” in Computer Vision and Pattern Recognition, 1991. Proceedings CVPR’91., IEEE Computer Society Conference on, pp. 586–591, IEEE, 1991.
7. 视觉化：https://setosa.io/ev/principal-component-analysis/

PCA降维的核心思想是：找到最有影响力，使全部样本最大可分的向量（即方差最大的），作为主成分，然后映射到该向量去。对其求垂直便能找到第二个主成分，然后找到k个主成分后，那么原来n维可以降到k维。

主要做法有Eigen-decomposition（特征值分解）与Singular Value Decomposition（奇异值分解），后者被称为Dual PCA。

定义

Preprocessing 预处理

Train Set：$\mathbf{X}\in \mathbb{R}^{d\times n} = [X_1,\cdots,X_n] = {X_i\in \mathbb{R}^d}_{i=1}^n$

Mean：$\mu=\frac{1}{n}\sum^n_{i=1} X_i \in \mathbb{R}^d$

Normalization：$\breve{\mathbf{X}}=\mathbf{X}-\mu =\mathbf{X}·H$（这里是用线性变换的方法近似归一化效果，减少运算量，其中$H=I-(1/n)11^T$，$1$是全1向量。$H$被称为 centering matrix）

（其中对于NLP的任务不需要归一化，因为NLP中负数是无意义的，这时就称为LSI/LSA）

投影 Projection 与 还原 Reconstruction

我们的目的是找到映射矩阵 $\mathbf{U}\in\R^{dp}$，将数据从$\R^{dn}$映射到$\R^{p*n}$。

Projection：$\mathbf{\tilde{X}} = \mathbf{U}^T\mathbf{\breve{X}},\mathbf{\tilde{X}}\in \mathbb{R}^{p\times n}$

Reconstruction：$\mathbf{\hat{X}}=\mathbf{U}\mathbf{U}^T\mathbf{\breve{X}}+\mu=\mathbf{U}\mathbf{\tilde{X}}+\mu$

Test Set：$\mathbf{\tilde{X_t}} = \mathbf{U}^T\mathbf{\breve{X}},\mathbf{\hat{X_t}}=\mathbf{U}\mathbf{\tilde{X_t}}+\mu_x$（相当于用训练出的投影矩阵处理测试集）

优化目标

为寻找优化目标，我们从两个角度去看主成分分析算法。分别是最小化重构Error（最近重构性）和最大方差（最大可分性），他们能够得出一样的结果。

1 最大化方差

根据最大可分性，我们希望重构后数据的方差会尽量的大。我们将作为constant项的$\mu$去掉，取其Square Frobenius Norm，有：
$$
\begin{array}{l}\left|\hat{\mathbf{X}}\right|{F}^{2} = \left|\boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right|{F}^{2} \=\operatorname{tr}\left(\left(\boldsymbol{U} \boldsymbol{U}^{\top}\breve{\boldsymbol{X}}\right)^{\top}\left(\boldsymbol{U}\boldsymbol{U}^{\top}\breve{\boldsymbol{X}}\right)\right) \=\operatorname{tr}(\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \underbrace{\boldsymbol{U}^{\top}\boldsymbol{U}}_{\boldsymbol{I}}\boldsymbol{U}^{\top}\breve{\boldsymbol{X}})\=\operatorname{tr}\left(\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right)\=\operatorname{tr}\left(\boldsymbol{U}^{\top}\breve{\boldsymbol{X}}\breve{\boldsymbol{X}}^{\top}\boldsymbol{U} \right) \end{array}
$$
Minimization（常规做法会用到拉格朗日函数，最好查看参考链接[3]理解这一步）：
$$\begin{aligned} &\underset{\boldsymbol{U}}{\operatorname{minimize}}\operatorname{tr}\left(\boldsymbol{U}^{\top}\breve{\boldsymbol{X}}\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \right) \ &\text { subject to } \boldsymbol{U}^{\top} \boldsymbol{U}=\boldsymbol{I} \ \end{aligned}$$

$$\mathcal{L}=\operatorname{tr}\left(\boldsymbol{U}^{\top}\breve{\boldsymbol{X}}\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \right) -\operatorname{tr}\left(\Lambda^{\top}\left(\boldsymbol{U}^{\top} \boldsymbol{U}-\boldsymbol{I}\right)\right) \ \mathbb{R}^{d \times p} \ni \frac{\partial \mathcal{L}}{\partial \boldsymbol{U}}=2 \breve{\boldsymbol{X}}\breve{\boldsymbol{X}}^{\top} \boldsymbol{U}-2 \boldsymbol{U} \Lambda \stackrel{\text { set }}{=} 0 \\Longrightarrow \breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top} \boldsymbol{U}=\boldsymbol{U} \Lambda$$

2 最小化重构Error

根据最近重构性，我们希望重构后的原数据会尽量相似，那就指出了我们的优化目标：最小化重构/还原Error(即距离)：

Reconstruction Distance：
$$
\left|\mathbf{X}-\mathbf{\hat{X}}\right|{F}^{2} = \left|\breve{\boldsymbol{X}}-\boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right|{F}^{2} \
=\operatorname{tr}\left(\left(\breve{\boldsymbol{X}}-\boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right)^{\top}\left(\breve{\boldsymbol{X}}-\boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right)\right) \
=\operatorname{tr}\left(\left(\breve{\boldsymbol{X}}^{\top}-\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top}\right)\left(\breve{\boldsymbol{X}}-\boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right)\right) \
=\operatorname{tr}(\breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}-2 \breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}+\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \underbrace{\boldsymbol{U}^{\top} \boldsymbol{U}}{\boldsymbol{I}} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}) \
=\operatorname{tr}\left(\breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}-\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right) \
=\operatorname{tr}\left(\breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}\right)-\operatorname{tr}\left(\breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right) \
=\operatorname{tr}\left(\breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}\right)-\operatorname{tr}\left(\breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top}\right)
$$
Minimization：
$$
\begin{aligned}
&\underset{\boldsymbol{U}}{\operatorname{minimize}}\left|\breve{\boldsymbol{X}}-\boldsymbol{U} \boldsymbol{U}^{\top} \breve{\boldsymbol{X}}\right|{F}^{2} \
&\text { subject to } \boldsymbol{U}^{\top} \boldsymbol{U}=\boldsymbol{I} \
\end{aligned}
$$

$$\mathcal{L}=\operatorname{tr}\left(\breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}\right)-\operatorname{tr}\left(\breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top} \boldsymbol{U} \boldsymbol{U}^{\top}\right)-\operatorname{tr}\left(\Lambda^{\top}\left(\boldsymbol{U}^{\top} \boldsymbol{U}-\boldsymbol{I}\right)\right) \ \mathbb{R}^{d \times p} \ni \frac{\partial \mathcal{L}}{\partial \boldsymbol{U}}=2 \breve{\boldsymbol{X}}\breve{\boldsymbol{X}}^{\top} \boldsymbol{U}-2 \boldsymbol{U} \Lambda \stackrel{\text { set }}{=} 0 \ \Longrightarrow \breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top} \boldsymbol{U}=\boldsymbol{U} \Lambda$$

注释

对于带矩阵约束的优化问题，通过拉格朗日乘子可以求解。

e.g. 对于$\text{max或min} f(X) \ s.t. Φ(X)=0$，其拉格朗日函数为$\mathcal L(X,\Lambda) = f(X)+tr(\Lambda^{\top}Φ(X))$，具体请查阅 [3]。

降维

上述两个方法最后得出的式子都是一个：$\breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top} \boldsymbol{U}=\boldsymbol{U} \Lambda$。

至此，我们只需要对$\breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top}$进行特征值分解$\breve{\boldsymbol{X}} \breve{\boldsymbol{X}}^{\top} =\boldsymbol{U} \Lambda\boldsymbol{U}^{\top}$，将求得的特征值$\Lambda$从小到大进行排序:$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_d$，然后取前$p$个特征值对应构成特征向量$\mathbf{U} = [u_1,\cdots,u_p]$，其中$u_k$为单位特征向量，便是我们最后得到的投影矩阵了。

一般如何选择需要降的维数$p$呢？

Scree plot, Ratio

$$ratio = \frac{\lambda_j}{\sum^d_{k=1}\lambda_k}$$

一般没有要求的话，我们会选择ratio的转折点(knee)的那一点作为我们最后选择的p。对重构阈值$t$有要求的话就：
$$\frac{\sum^p_{k=1}\lambda_k}{\sum^d_{k=1}\lambda_k}\ge t$$
这样就OK啦。

Dual PCA

如果我们不用特征值分解呢？而是使用 奇异值分解 SVD 呢？这时候就是Dual PCA。

Why Dual PCA?

1. 在对于n<<d的计算时，对$\boldsymbol{\breve{X}}^{\top}\boldsymbol{\breve{X}}$的特征值分解比对$\boldsymbol{\breve{X}} \boldsymbol{\breve{X}}^{\top}$的特征值分解要快很多（因为$\boldsymbol{\breve{X}}^{\top}\boldsymbol{\breve{X}} \in\mathbb{R}^{n\times n}$而$\boldsymbol{\breve{X}}\boldsymbol{\breve{X}}^{\top} \in\mathbb{R}^{p\times p}$。
2. 对于Kernel PCA的形式上有帮助。（Kernel PCA在之后有时间会尝试补充）

奇异值分解 SVD Review

奇异值分解的形式都一样：$\mathbf{A} = \mathbf{U\Sigma V}^\top,\mathbf{A}\in \mathbb{R}^{a\times b}$

SVD 本身也可以用于降维，当原数据有zero mean时其实就是PCA在用SVD了。

奇异值分解有两种：

Complete SVD

$\mathbf{U}\in\mathbb{R}^{a\times a},\mathbf{V}\in\mathbb{R}^{b\times b},\mathbf{\Sigma}\in\mathbb{R}^{a\times b}$

此时$\mathbf{U}$称为左奇异向量，$\mathbf{V}$称为右奇异向量，$\mathbf{\Sigma}$是一个矩形矩阵，其主对角线上的值都是奇异值。
$$\boldsymbol{\Sigma}=\left[\begin{array}{ccc} \sigma_{1} & 0 & 0 \ \vdots & \ddots & \vdots \ 0 & 0 & \sigma_{\beta} \ 0 & 0 & 0 \ \vdots & \vdots & \vdots \ 0 & 0 & 0 \end{array}\right] \text { and }\left[\begin{array}{cccccc} \sigma_{1} & 0 & 0 & 0 & \cdots & 0 \ \vdots & \ddots & \vdots & 0 & \cdots & 0 \ 0 & 0 & \sigma_{\alpha} & 0 & \cdots & 0 \end{array}\right]$$
其中奇异值数量是$min(a,b)$。

Incomplete SVD

$\mathbf{U}\in\mathbb{R}^{a\times k},\mathbf{V}\in\mathbb{R}^{b\times k},\mathbf{\Sigma}\in\mathbb{R}^{k\times k}$ where $k:=min(a,b)$

此时$\mathbf{U}$称为左奇异向量，$\mathbf{V}$称为右奇异向量，$\mathbf{\Sigma}$是一个方正矩阵，其主对角线上的值都是奇异值。
$$\boldsymbol{\Sigma}=\left[\begin{array}{ccc} \sigma_{1} & 0 & 0 \ \vdots & \ddots & \vdots \ 0 & 0 & \sigma_{k} \ \end{array}\right]$$

SVD的特点

首先，无论是Complete还是Incomplete，其$\mathbf{U,V}$都满足正交，即：
$$s.t. \ \boldsymbol{U}^{\top} \boldsymbol{U}=\boldsymbol{I}\ s.t. \ \boldsymbol{V}^{\top} \boldsymbol{V}=\boldsymbol{I}$$
其中$\mathbf{U}$是的特征分解后的特征向量，而$\mathbf{V}$为的特征值分解后的特征向量，证明如下。
$$
\begin{aligned}
\boldsymbol{A} \boldsymbol{A}^{\top} &=\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)^{\top}=\boldsymbol{U} \boldsymbol{\Sigma} \underbrace{\boldsymbol{V}^{\top} \boldsymbol{V}}_{\boldsymbol{I}} \boldsymbol{\Sigma} \boldsymbol{U}^{\top} \
&=\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{\Sigma} \boldsymbol{U}^{\top}=\boldsymbol{U} \boldsymbol{\Sigma}^{2} \boldsymbol{U}^{\top}
\end{aligned}\

$$\begin{aligned} \boldsymbol{A}^{\top} \boldsymbol{A} &=\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)^{\top}\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)=\boldsymbol{V} \boldsymbol{\Sigma} \underbrace{\boldsymbol{U}^{\top} \boldsymbol{U}}_{\boldsymbol{I}} \boldsymbol{\Sigma} \boldsymbol{V}^{\top} \ &=\boldsymbol{V} \boldsymbol{\Sigma} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}=\boldsymbol{V} \boldsymbol{\Sigma}^{2} \boldsymbol{V}^{\top} \end{aligned}$$
$$

在PCA中使用SVD

在这里，我们使用Incomplete SVD来做完原来PCA所做的所有内容，但我们将$\mathbf{U}$全部转换为$\mathbf{V}$：

$\mathbf{\breve{X}} = \mathbf{U\Sigma V}^\top$, where $\mathbf{U}\in\mathbb{R}^{d\times p},\mathbf{V}\in\mathbb{R}^{n\times p},\mathbf{\Sigma}\in\mathbb{R}^{p\times p}$

1.Projection

$$\mathbf{\tilde{X}}=\mathbf{U}^\top\mathbf{\breve{X}} = \underbrace{\boldsymbol{U}^{\top} \boldsymbol{U}}_{\boldsymbol{I}}\mathbf{\Sigma V}^\top =\mathbf{\Sigma V}^\top$$

2.Recounstruction

$$\mathbf{\breve{X}}\mathbf{V} = \mathbf{U\Sigma}\underbrace{\boldsymbol{V}^{\top} \boldsymbol{V}}_{\boldsymbol{I}} =\mathbf{U\Sigma}\ \Longrightarrow \mathbf{U}=\mathbf{\breve{X}}\mathbf{V\Sigma}^{-1}\ \begin{aligned} \mathbf{\hat{X}}&=\mathbf{U}\mathbf{\tilde{X}}+\mu\&=\mathbf{\breve{X}}\mathbf{V\Sigma}^{-1}\mathbf{\tilde{X}}+\mu\&=\mathbf{\breve{X}}\mathbf{V\Sigma}^{-1}\mathbf{\Sigma V}^\top+\mu\ &=\mathbf{\breve{X}}\mathbf{VV}^\top+\mu \end{aligned}$$

3. Test Set

$$
\begin{array}{l}
\boldsymbol{U}=\check{\boldsymbol{X}} \boldsymbol{V} \Sigma^{-1} \Longrightarrow \boldsymbol{U}^{\top}=\Sigma^{-\top} \boldsymbol{V}^{\top} \breve{\boldsymbol{X}}^{\top}=\Sigma^{-1} \boldsymbol{V}^{\top} \breve{\boldsymbol{X}}^{\top} \
\tilde{\boldsymbol{X}}{t}=\boldsymbol{U}^{\top} \breve{\boldsymbol{X}}{t}=\Sigma^{-1} \boldsymbol{V}^{\top} \breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}_{t}
\end{array}
$$

$$
\begin{aligned}
\boldsymbol{U} \boldsymbol{U}^{\top} &=\breve{\boldsymbol{X}} \boldsymbol{V} \boldsymbol{\Sigma}^{-1} \boldsymbol{\Sigma}^{-1} \boldsymbol{V}^{\top} \breve{\boldsymbol{X}} \ \widehat{\boldsymbol{X}}{t}&=\breve{\boldsymbol{X}} \boldsymbol{V} \boldsymbol{\Sigma}^{-2} \boldsymbol{V}^{\top} \breve{\boldsymbol{X}}^{\top} \breve{\boldsymbol{X}}{t}+\boldsymbol{\mu}_{x}
\end{aligned}
$$