Edx Columbia ML 19. 主成分分析 (PCA)

PCA

通常被用来做维度缩减,即将数据从高维空间投影到低维空间,同时尽可能完整地保留原有的信息,可以由一个例子来看。假设在二维空间中存在一个单位向量\(q\),即\(|\!|q|\!| = 1\),对于同一空间中的其它向量\(x_i\),该向量在\(q\)上的投影对应的向量为\(d\cdot \frac{q}{|\!|q|\!|} = dq\)(假设长度为\(d\))。设\(x_i\)\(q\)的夹角为\(\theta\),则\(d = |\!|x_i|\!|\cos \theta\)。又\(\cos \theta = \frac{q^\mathsf{T}x_i}{|\!|q|\!||\!|x_i|\!|}\),因此 \[ d = |\!|x_i|\!|\cos\theta = |\!|x_i|\!|\cdot \frac{q^\mathsf{T}x_i}{|\!|q|\!||\!|x_i|\!|} = q^\mathsf{T}x_i \]\(x_i\)\(q\)上投影对应的向量为\((q^\mathsf{T}x_i)q\)。这样,二维向量\(x_i\)的信息被降为了一维的\(q^\mathsf{T}x_i\)来保存,维度减小,但是信息没有丢失。最好的\(q\)满足平方近似误差最小,即 \[ \begin{align*} q &= {\rm arg}\min_q \sum_{i=1}^n |\!|x_i - qq^\mathsf{T}x_i|\!|^2\ \ \ {\rm subject\ to}\ q^\mathsf{T}q = 1 \\ &= {\rm arg}\min_q \sum_{i=1}^n x_i^\mathsf{T}x_i - q^\mathsf{T}\underbrace{\left(\sum_{i=1}^n x_ix_i^\mathsf{T}\right)}_{=XX^\mathsf{T}}q \end{align*} \] 由于第一项与\(q\)无关,第二项带负号,因此上述问题等价于 \[ q = {\rm arg}\max_q q^\mathsf{T}(XX^\mathsf{T})q\ \ \ {\rm subject\ to}\ q^\mathsf{T}q = 1 \] 这里变化为特征值分解的问题。\(q\)\(XX^\mathsf{T}\)的第一个特征向量,\(\lambda = q^\mathsf{T}(XX^\mathsf{T})q\)是第一个特征值 具体解释如下:对上述优化问题引入Lagrange乘子,则优化问题转化为 \[ \begin{align*} \mathcal{L} &= q^\mathsf{T}(XX^\mathsf{T})q + \lambda (1-q^\mathsf{T}q) \\ \nabla \mathcal{L}_q &= 2XX^\mathsf{T}q - 2q\lambda \end{align*} \]\(\nabla \mathcal{L}=0\)可以得到\(XX^\mathsf{T}q =\lambda q\),这里也是特征值与特征向量的定义。而由于 \[ \begin{align*} q^\mathsf{T}(XX^\mathsf{T})q &= q^\mathsf{T}\lambda q\ \ (\because (XX^\mathsf{T})q = \lambda q)\\ &= \lambda q^\mathsf{T}q \\ &= \lambda\ \ (\because q^\mathsf{T}q = 1) \end{align*} \] 因此求最大的\(q^\mathsf{T}(XX^\mathsf{T})q\)等于求最大\(\lambda\),即最大的特征值

上述表示可以推广到将数据降维到\(K\)维的情况,即 \[ \begin{align*} q &= {\rm arg}\min_q \sum_{q=1}^n \left|\!\left|x_i - \underbrace{\sum_{k=1}^K(x_i^\mathsf{T}q_k)q_k}_{ {\rm approximates\ } x}\right|\!\right|^2\ \ \ {\rm s.t.}\ q_k^\mathsf{T}q_k' = \begin{cases}1, & k = k' \\ 0, & k \not= k'\end{cases} \\ &= {\rm arg}\min_q \sum_{i=1}^n x_i^\mathsf{T}x_i - \sum_{k=1}^K q_k^\mathsf{T} \underbrace{\left(\sum_{i=1}^n x_ix_i^\mathsf{T} \right)}_{=XX^\mathsf{T}}q_k \end{align*} \]

因此投影为 \[ x_{\rm proj} = \left[\begin{array}{c} q_1^\mathsf{T}x \\ \vdots \\ q^\mathsf{T}_K x \end{array}\right],\ \ x \approx \sum_{k=1}^K (q_k^\mathsf{T}x)q_k = Qx_{\rm proj} \]

使用SVD分解,可以得到\(X=USV^\mathsf{T}\)。我们有\(XX^\mathsf{T} = US^2U^\mathsf{T}\),可以推出\(Q=U, \lambda_i = (S^2)_{ii} \ge 0\),即\(XX^\mathsf{T}\)是半正定矩阵,因此特征值有\(r = \min\{d, n\}\)个,且 \[ \lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_r > 0 \]

PCA之前一般要做一个预处理,把\(x\)的每个维度减去该列的均值

概率PCA

使用SVD分解,有\(X=USV^\mathsf{T}\)。如果我们用矩阵\(W\)\(Z\)近似,即\(X\approx WZ\),其中

  • \(W\)是一个\(d \times K\)矩阵,类似特征向量组成的集合,但是并不需要正交
  • \(Z\)的第\(i\)\(z_i \in \mathbb{R}^K\)\(x_i\)在低维空间的表示

则概率PCA的生成过程为 \[ x_i \sim N(Wz_i, \sigma^2I),\ \ z_i \sim N(0,I) \]

目标是在边缘分布下(即积分掉\(z_i\)以后)找出\(W\)的最大似然估计,即 \[ W_{\rm ML} = {\rm arg}\max_W \ln p(x_1, \ldots, x_n|W) = {\rm arg}\max_W \sum_{i=1}^n \ln p(x_i|W) \] 由于\(p(x_i|W) = N(x_i |0, \sigma^2I + WW^\mathsf{T})\) \[ N(x_i |0, \sigma^2I + WW^\mathsf{T}) = \frac{1}{(2\pi)^{\frac{d}{2}}\left|\sigma^2 I + WW^\mathsf{T}\right|^{\frac{1}{2}}}e^{-\frac{1}{2}x^\mathsf{T}(\sigma^2I + WW^\mathsf{T})^{-1}x} \] 可以借助\(z_1, \ldots, z_n\)来使用EM算法求解

概率PCA的EM算法 输入:数据\(x_{1:n}, x_i \in \mathbb{R}^d\),模型\(x_i \sim N(W_{z_i}, \sigma^2), z_i \sim N(0,I), z\in \mathbb{R}^K\) 输出:\(W\)的点估计和\(z_i\)的后验分布 E步:令每个\(q(z_i) = p(z_i|x_i, W) = N(z_i|\mu_i, \Sigma_i)\),其中 \[ \Sigma_i = (I + W^\mathsf{T}W/\sigma^2)^{-1},\ \ \mu_i = \Sigma_iW^\mathsf{T}x_i / \sigma^2 \] M步:最大化E步的目标函数\(\mathcal{L}\),更新\(W\) \[ W = \left[\sum_{i=1}^n x_i\mu_i^\mathsf{T}\right]\left[\sigma^2I + \sum_{i=1}^n (\mu_i\mu_i^\mathsf{T}+\Sigma_i)\right]^{-1} \]

核PCA

在原始的PCA中,\(\sum_{i=1}^n x_ix_i^\mathsf{T}\)可以写作\(XX^\mathsf{T}\)。如果我们使用\(\phi(x)\)把特征从\(\mathbb{R}^d\)映射到\(\mathbb{R}^D\),即做特征值分解 \[ \left[\sum_{i=1}^n \phi(x_i)\phi(x_i)^\mathsf{T}\right]q_k = \lambda_kq_k \] 同时又不真正在高维空间中做计算,即,如何不显式使用\(\phi(\cdot)\)\(q\),直接做PCA?

由于由前式有 \[ \sum_{i=1}^n \phi(x_i)\underbrace{(\phi(x_i)^\mathsf{T}q_k)/\lambda_k}_{=a_{ki}} = q_k \] 因此\(q_k\)可以写为 \[ q_k = \sum_{i=1}^n a_{ki}\phi(x_i) \] 其中\(\mathbf{a}_k \in \mathbb{R}^n\)

因此我们可以不学习\(q_k\),直接学习\(\mathbf{a}_k\)。把上面\(q_k\)的式子代回原始公式,有 \[ \sum_{i=1}^n \phi(x_i) \sum_{j=1}^n a_{kj}\underbrace{\phi(x_i)^\mathsf{T}\phi(x_j)}_{K(x_i, x_j)} = \lambda_k \sum_{i=1}^n a_{ki}\phi(x_i) \] 对于赏识,左右两边再乘以\(\phi(x_l)^\mathsf{T}\)\(l \in \{1,\ldots, n\}\),可以得到 \[ K^2\mathbf{a}_k = \lambda_k K \mathbf{a}_k \Leftrightarrow K\mathbf{a}_k = \lambda_k \mathbf{a}_k \] 其中\(K\)是在数据上构建的\(n\times n\)核矩阵

核PCA 输入:数据\(x_1, \ldots, x_n, x\in \mathbb{R}^d\),以及核函数\(K(x_i, x_j)\) 构造数据上的核矩阵,例如 \[ K_{ij} = b\exp\left\{-\frac{|\!|x_i - x_j|\!|^2}{c}\right\} \] 对核矩阵做特征值分解,得到前\(r <\!\!< n\)个特征值/特征向量 \((\lambda_1, \mathbf{a}_1) , \ldots, (\lambda_r, \mathbf{a}_r)\) 输出:\(x_i\)的低维表示,先将\(x_i\)映射到\(\phi(x_i)\),然后投影为\(q_k^\mathsf{T}\phi(x_i)\) \[ x_i \mathop{\rightarrow}^{\rm proj} \left[\begin{matrix} \lambda_1a_{1i} \\ \vdots \\ \lambda_ra_{ri} \end{matrix}\right] \] 其中\(a_{ki}\)是第\(k\)个特征向量\(\mathbf{a}_k\)的第\(i\)

对新数据也可以做类似的kernel trick,只不过有 \[ \begin{align*} x_0 &\mathop{\rightarrow}^{\rm proj} \left[\begin{matrix} \phi(x_0)^\mathsf{T}q_1 \\ \vdots \\ \phi(x_0)^\mathsf{T}q_r \end{matrix}\right] \\ \phi(x_0)^\mathsf{T}q_k &= \sum_{i=1}^n a_{ki}\phi(x_0)^\mathsf{T}\phi(x_i) = \sum_{i=1}^n a_{ki}K(x_0, x_i) \end{align*} \]

坚持原创技术分享,您的支持将鼓励我继续创作!