深度学习系列笔记(三)

深度学习系列笔记(三)

主成分分析(principal components analysis, PCA)

主成分分析是一个简单的机器学习算法，可以通过基础的线性代数知识推导。

假设在R^n空间中有m个点

，我们希望对这些点进行有损压缩。我们希望损失的精度尽可能少。

编码这些点的一种方式是用低维表示。对于每个点x^{(i)} \in R^n，会有一个对应的编码向量c^{(i)}\in R^l.如果l比n小，那么我们便使用了更小的内存来存储原来的数据。我们希望找到一个编码函数，根据输入返回编码，f(x)=c，我们也希望找到一个解码函数，给定编码重构输入x \approx g(f(x))。

PCA由我们选择的解码函数来决定。具体来讲，为了简化编码器，我们使用矩阵乘法将编码映射回R^n，即g(c)=Dc，其中D \in R^{n \times l}是定义解码的矩阵。

为了使问题有唯一解，我们限制D中所有的列向量都有单位范数。为了使编码问题简单一些，PCA限制D的列向量彼此正交。

衡量最优编码的一种方式：解码之后的向量和输入的向量之间的距离最小，可以使用范数来衡量他们之间的距离。在PCA算法中，我们使用L^2范数。

c^* = \arg \min\limits_c \begin{Vmatrix} x-g(c) \end{Vmatrix}_2​。我们可以使用平方L^2​范数替代L^2​方范数，因为两者在相同的值c上取得最小值，由于L^2范数非负，而平方L^2范数在非负值上单调递增。

c^* = \arg \min\limits_c \begin{Vmatrix} x-g(c) \end{Vmatrix}_2^2 最小化函数简化之后得

(x-g(c))^T(x-g(c)) 使用分配律

x^Tx-x^Tg(c)-g(c)^Tx+g(c)^Tg(c) 由于标量g(c)^Tx​的转置等于自己，所以得

x^Tx-2x^Tg(c)+g(c)^Tg(c)​​ ，第一项不依赖于c，忽略，得到优化目标：

c^* = \arg \min\limits_c -2x^Tg(c)+g(c)^Tg(c)​ ，代入g(c)的定义

c^* = \arg \min\limits_c -2x^TDc+c^TD^TDc ，由D的正交性和单位范数约束得：

c^* = \arg \min\limits_c -2x^TDc+c^TI_lc = \arg \min\limits_c -2x^TDc+c^Tc ，通过向量微积分求解这个最优化问题 :::hljs-center \bigtriangledown _c(-2x^TDc+c^Tc)​

-2D^Tx+2c=0

c=D^Tx :::

这使得算法很高效：最优编码x只需要一个矩阵向量乘法操作，为了编码向量我们使用编码函数 f(x)=D^Tx，进一步使用矩阵乘法我们也可以定义PCA重构操作：r(x)=g(f(x))=DD^Tx

那么如何挑选编码矩阵D？前面我们说，要想得到最优编码，那么输入x和重构编码输出g(c^*)的L^2距离要最小。因为用相同的矩阵D对所有点进行解码，我们不能再孤立地看待每个点。反之，我们必须最小化所有维数和所有点上的误差矩阵的Frobenius范数:

D^* = \arg \min\limits_D \sqrt{\sum\limits_{i,j}( x_j^{(i)} - r(x^{(i)})_j)^2}​ subject​ to​ D^TD=I_l，为了推导用于寻求D^*的算法，我们首先考虑l=1的情况。在这这种情况下，D是一个单一向量d，将r(x)代入上式，简化D为d得:d^* = \arg \min\limits_d \sum\limits_i \begin{Vmatrix} x^{(i)} - dd^Tx^{(i)} \end{Vmatrix}_2^2 subject to \begin{Vmatrix} d \end{Vmatrix}_2=1，上述公式不美观，我们通常将标量写在向量左边得：

d^* = \arg \min\limits_d \sum\limits_i \begin{Vmatrix} x^{(i)} - d^Tx^{(i)}d \end{Vmatrix}_2^2​ subject​ to​ \begin{Vmatrix} d \end{Vmatrix}_2=1 ，或者，考虑到标量的转置和自身相等也可以写作：

d^* = \arg \min\limits_d \sum\limits_i \begin{Vmatrix} x^{(i)} - {x^{(i)}}^Tdd \end{Vmatrix}_2^2 subject to \begin{Vmatrix} d \end{Vmatrix}2=1 。将表示个点的向量堆叠成一个矩阵，记为X \in R^{m \times n}，其中X{i,:}={x^{(i)}}^T。得：

d^* = \arg \min\limits_d \begin{Vmatrix} X - X^Tdd^T \end{Vmatrix}_F^2​​​ subject​​​ to​​​ d^Td =1​​ 。 ​​​先不考虑约束，将Frobenius范数简化为下面的形式：

\arg \min\limits_d \begin{Vmatrix} X - X^Tdd^T \end{Vmatrix}_F^2

= \arg \min\limits_d Tr\big((X-Xdd^T)^T(X-Xdd^T\big)​

= \arg \min\limits_d Tr(X^TX-X^TXdd^T-dd^TX^TX+dd^TX^TXdd^T)

=\arg \min\limits_d Tr(X^TX)-Tr(X^TXdd^T)-Tr(dd^TX^TX)+Tr(dd^TX^TXdd^T)

=\arg \min\limits_d -Tr(X^TXdd^T)-Tr(dd^TX^TX)+Tr(dd^TX^TXdd^T) 因为与d无关的项不影响 \arg \min

=\arg \min\limits_d -2Tr(X^TXdd^T)+Tr(dd^TX^TXdd^T)​​ 因为循环改变迹运算中相乘矩阵的顺序不影响结果

=\arg \min\limits_d -2Tr(X^TXdd^T)+Tr(X^TXdd^Tdd^T)​​ 再次使用上述性质

再考虑约束条件：

\arg \min\limits_d -2Tr(X^TXdd^T)+Tr(X^TXdd^Tdd^T)​ subject​ to​ d^Td =1​

=\arg \min\limits_d -2Tr(X^TXdd^T)+Tr(X^TXdd^T)​ subject​ to​ d^Td =1​

=\arg \min\limits_d -Tr(X^TXdd^T)​ subject​ to​ d^Td =1​

=\arg \max\limits_d Tr(X^TXdd^T)​ subject​ to​ d^Td =1​

=\arg \max\limits_d Tr(d^TX^TXd) subject to d^Td =1

这个最优化问题可以通过特征分解来求解。具体来讲，最优的d是X^TX最大特征值对应的特征向量。

以上推导特定于l=1的情况，仅得到了第一个主成分。更一般地，当我们希望得到主成分的基时，矩阵D由前l个最大的特征值对应的特征向量组成。

参考文献： 《深度学习》