5 Matching Annotations
  1. Mar 2019
  2. Sep 2018
    1. PCA - Another point of view

      Basic Component can ba analogy to sample after projection

      可以从比较形象的角度来理解 PCA,之前的角度是从x -> z , PCA 其本质就是一个线性函数,把 x 空间中一点,转换到 z 空间中一点。

      $$ img_{28*28} \rightarrow x = \begin{vmatrix} 204 \\ 102 \\ 0 \\ 1 \\ . \\ . \\ . \end{vmatrix}^{784*1} \rightarrow z = \begin{vmatrix} 1 \\ 0.5 \\ 0 \\ 1 \\ 0.3 \end{vmatrix} $$

      如果把 z 的每一位都看成是某种笔画的系数,那么我们就可以用另外一种方式来表示一张图片:

      $$ x - \bar{x} \approx c_1u_1 + c_2u_2 + ... + c_ku_k = \hat{x} $$

      • \(c_i\) is the component of x which is an image
      • \(u_i\) is factor of each component
      • \(x\) is img;
      • \(\bar{x}\) is average color degree of pixels;
      • \(\hat{x}\) is the combination of components of a digit.
      • \(x-\bar{x}\) is a normalization to make average degree of color of an image to be 0
      • \(||(x-\bar{x})-\hat{x}||_2\) is reconstruction error

      这就提供了另一种看待问题的视角:

      • 原始PCA 是通过找到一个方向 w,它能最大化投影之后的Variance
      • Components-PCA 是通过找到各个Components的系数,它能最小化 reconstruction error

      于是优化目标的函数也就改变了:

      • 原始 PCA:

      $$ argmax_{w_i} Var(x) = \sum_x(x-\bar{x})^2, with\ ||w_i||_2 = 1, and\ w_i \cdot \{w_j\}_{j=1}^{i-1} = 0 $$

      • Components-PCA:

      \(argmin_{u_1, ..., u_K}\sum||(x-\bar{x}) - (\sum_{k=1}^Kc_ku_k)||_2\)

      \(\sum_{k=1}^Kc_ku_k = \hat{x}\)

      可以证明的是:这个 \(\{u_k\}_{k=1}^K\) 就是我们要找的 \(\{w_k\}_{k=1}^K\)

      $$ \begin{vmatrix} z_1 \\ z_2 \\ . \\. \\. \\z_K \end{vmatrix} = \begin{vmatrix} w_1 \\ w_2 \\ . \\. \\. \\w_K \end{vmatrix} x = \begin{vmatrix} u_1 \\ u_2 \\ . \\. \\. \\u_K \end{vmatrix} x $$

      证明 u = w

      $$ x^1 - \bar{x} \approx c_1^1u^1 + c_2^1u^2 + ... $$

      $$ x^2 - \bar{x} \approx c_1^2u^1 + c_2^2u^2 + ... $$

      $$ x^3 - \bar{x} \approx c_1^3u^1 + c_2^3u^2 + ... $$

      • \(x^i\) : 第 i 个样本
      • \(c_k^i\) : 第 i 个样本的第 k 个 component 的系数(权重)
      • \(u^k\): 第 k 个 component

      【注意】component 对任意样本都是一样的,样本之间不同的是component的系数(权重)

      我们可以把上面 3 个式子组合成矩阵的形式:

      对于单个样本

      可以写成 向量 = 矩阵 * 向量

      $$ c_1^2u^1 + c_2^2u^2 + ... = \sum_{k=1}^Kc_k^1u^k = [u^1, u^2, ...] \cdot \begin{vmatrix}c_1^1\\c_2^1\\.\\.\\.]\end{vmatrix} $$

      把所有样本都组合起来

      可以写成 矩阵 = 矩阵 * 矩阵

      $$ \underbrace{[x^1 - \bar{x}, x^2-\bar{x}, x^3-\bar{x}, ...]}_{\text{dataset:X}} \approx \underbrace{[u^1, u^2, ...]}_{\text{components matrix}} \cdot \underbrace{ \begin{vmatrix} c_1^1 & c_1^2 & c_1^3\\ c_1^1 & c_1^2 & c_1^3\\ c_1^1 & c_1^2 & c_1^3\\ .&.&.\\ .&.&.\\ .&.&. \end{vmatrix}}_{\text{factor matrix}} \text{how to find the best u to make two side of approx as near as possible?} $$

      我们可以使用 SVD 矩阵分解,对 X 进行分解:

      X 可以分解成3个矩阵的乘积:

      \(X_{m*n} \approx U_{m*k} \Sigma_{k*k}V_{k*n}\)

      • m : the dimension of one sample
      • n : the size of dataset
      • k : number of components

      这里直接给出答案,具体过程见线性代数课程。

      K columns of U: a set of orthonormal eigen vectors corresponding to the k largest eigenvalues of \(XX^T\)

      这个 \(XX^T\) 就是 \(Cov(x)\) , 因为这里的 X 是由 \(x - \bar{x}\) 得到的。所以,u = w。

      再回忆下我们对于 u w 和 z 的定义:

      • u : components of x (eg, 数字的笔画)
      • w : 线性函数矩阵 W 用于做 \(z = W^Tx\) 投影
      • z : 投影之后的“新”的样本

      启示:PCA 找出的那些 w(转换矩阵 W 的 columns) 就是 components

    2. Dimension Reduction 为什么可能是有用的?

      一,例子1 为什么 Dimension Reduction 可能是有用的,如下图示:

      Manifold

      如果我们用 3 dimension 的样本维度去描述他其实是非常浪费的,因为很明显他是卷曲在一起的,如果我们有办法把他展平,不同类型(不同颜色代表不同类型)就很容易区隔开,而展平之后我们只需要 2 dimension 的样本维度。所以根本不需要把这个问题放在 3d 中去考虑,2d 就可以了。

      Manifold and dimension reduction by various methods

      二,例子2

      在手写数字辨识的任务中,你或许根本用不到 28*28 的维度,比如数字 3 他可能有很多形态,但其实大部分都是旋转一下角度而已,所以对于辨识 3 这件事可能需要的维度仅仅是一个旋转角度而已(1维度)

      如何做 dimension reduction 呢?

      对数据降维就是找一个function

      \(f(x) \rightarrow x', dim(x) >> dim(x')\)

      一,方法1: feature selection (略)

      二,方法2:PCA

      基本原理

      PCA 的本质就是通过一个一次线性函数 \(W^Tx\)把高维度的数据样本转换为低维度的数据样本。就像 \(w^Tx\) 如果\(W^T\)矩阵只有一行,这个函数就是两个向量的内积 --- 结果是一个(一维)数值,如果 \(W^T\) 是一个矩阵,那么 \(W^T\) 有多少行最终内积结果就有多少维

      $$ R_W^{1*N} \cdot R_x^{N*1} = R_{x'}^{1*1} R_W^{2*N} \cdot R_x^{N*1} = R_{x'}^{2*1} ... $$

      \(f(x) \rightarrow x', dim(x) >> dim(x')\)

      \(z = Wx, to\ find\ 'W'\)

      找到优化问题 --- projection has max variance

      该如何找到 W 呢,从最简单的开始,我们假设 :

      • reduce x to 1 D vector z, means that 'z' is a digit
      • 'W' matrix only have ONE row
      • this row's L2 norm is equal to 1: \(||w^1||_2=1\).

      如此一来,'z' 就可以看做是 'x' 在 'w' 方向上的投影(内积的几何意义)

      所有的 x: \(x^1, x^2, x^3,...\) 都在 w 方向上做投影就得到了 z: \(z^1, z^2, z^3,...\) , 而我们要做的就是从:

      如何找到 W 变成 找到一个 x 的更好的投影方向

      we want the variance of \(z_1\) as large as possible.

      variance 在图像上的表现就是,投影之后的 z 的取值范围(值域)取值范围越大variance越大

      对于投影到一维空间,找到最佳的 w('w' is a row vector) 使得 x('x' is N dimension) 投影到该方向得到的 z ('z' is a digit)的 variance 是最大的, 用公式表示就是:

      \(find\ a\ w\ to\ maximize:\)

      \(Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2)\)

      \(with\ constaint\ :\ ||w_1||_2=1\)

      对于投影到二维(甚至多维)空间,我们要给每个后面的w一个限制就是: 后面的 w(n+1 th row) 要跟前面的所有 w({1~n} rows) 相互垂直, \(w_{n+1} \cdot \{w_{i}\}_{i=1}^n = 0\).

      整体来看就是:

      the 1st row of W should be:

      \(w_1 = argmax(Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2)\)

      \(constraint:\ ||w_1||_2=1\)

      the 2nd row of W should be:

      \(w_2 = argmax(Var(z_2) = \sum_{z_2}(z_2 - \bar{z_2})^2)\)

      \(constraint:\ ||w_2||_2=1, w_2 \cdot w_1 = 0\)

      the 3rd row of W should be:

      \(w_3 = argmax(Var(z_3) = \sum_{z_3}(z_3 - \bar{z_3})^2)\)

      \(constraint:\ ||w_3||_2=1, w_3 \cdot w_1 = 0, w_3 \cdot w_2 = 0\)

      .......

      then the W should be:

      $$ W = \begin{vmatrix} (w_1)T \\ (w_2)T \\ . \\ . \\ . \end{vmatrix}\quad $$

      这里 W 会是一个 Orthogonal matrix, 因为每一行的 norm 都等于1,并且行行之间相互垂直。

      求解这个带限制条件优化问题 ---- 拉格朗日乘数法

      Lagrange multiplier 可以把带限制条件的优化问题转换>为无限制优化问题: target - a(zero_form of >constraint1) - b(zero_form of constraint2)

      无限制的优化问题,就可以通过偏微分=0来找到最优解

      如果 W 矩阵只有一行

      $$ one\ x\ one\ z_1 \bar{z_1} = \sum{z_1} = \sum{w_1 \cdot x} = w_1 \cdot \sum x = w_1 \cdot \bar{x} Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 $$

      对于 \(w \cdot (x - \bar{x})\), 他是两个向量的内积,对于这种内积的平方,要注意如下的惯用转换公式(值得记住)。

      $$ (a \cdot b)^2 = (a^Tb)^2 $$

      因为 \(a \cdot b\) 是内积,是一个数值,数值的平方无关乎顺序,所以可以写成:

      $$ (a^Tb)^2 = a^Tba^Tb $$

      因为 \(a \cdot b\) 是内积,是一个数值,数值的转置还是自身,所以可以写成:

      $$ (a^Tba^Tb = a^Tb(a^Tb)^T $$

      化简之后:

      $$ a^Tb(a^Tb)^T = a^Tbb^Ta $$

      所以之前 var 的式子可以化简为:

      $$ Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 = \sum_x(w_1)^T(x-\bar{x})(x-\bar{x})^Tw_1 $$

      因为是对 x 来求和,所以 w 可以提出去:

      $$ Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 = \sum_x(w_1)^T(x-\bar{x})(x-\bar{x})^Tw_1 = (w_1)^T(\sum_x(x-\bar{x})(x-\bar{x})^T)w_1 $$

      其中 \(\sum_x(x-\bar{x})(x-\bar{x})^T\) 是什么,这个是 x 向量(样本都是向量)的 covariance matrix. covariance 是对称且半正定对的, 也就是说所有的 eigenvalues 都是非负的

      $$ Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 = \sum_x(w_1)^T(x-\bar{x})(x-\bar{x})^Tw_1 = (w_1)^T(\sum_x(x-\bar{x})(x-\bar{x})^T)w_1 = (w_1)^TCov(x)w_1 $$

      我们设 \(S = Cov(x)\) ,于是我们得到了一个新的优化问题:

      find w1 maximizing:

      \(w_1^T S w_1, with\ constraint\ ||w_1||_2 = 1, means\ w_1^Tw_1 = 1\)

      Lagrange multiplier is target - zero_form of constraints

      之前说明过 \(w_1\) 是 W 矩阵的第一个row,再次提醒下。

      \(g(w_1) =w_1^TSw_1 - \alpha(w_1^Tw_1 - 1)\)

      \(\frac{\partial g(w_1)}{\partial w_{11}} = 0\)

      \(\frac{\partial g(w_1)}{\partial w_{12}} = 0\)

      ....

      通过对 Lagrange 式子 \(g(w_1)\) 的微分为0来求最大最优的w,可以得到如下化简后的式子:

      \(Sw_1 - \alpha w_1 = 0\)

      \(Sw_1 = \alpha w_1\)

      这种形式我们就熟悉了,\(w_1\) 是 S 的 eigen vector

      但是这样的 w1 有很多,因为 S 的 eigen vector 有很多,所以 w1 的潜在选择也很多,哪一个是最好的选择呢?通过我们的优化目标来判断。

      \(w_1^TSw_1 = \alpha w_1^Tw_1 = \alpha\)

      而这里的 \(\alpha\) 是 eigen value,

      所以,因为我们要最大化的目标最后等于 alpha, 而 alpha 是 eigen value, 所以我们选择最大的 eigen value, 一个 eigen value 对应一个 eigen vector, 所以最优的 w1 就是最大的 eigen value 对应的那个 eigen vector.

      之前分析过, Find w2 的情况与 Find w1 略有不同,不同在优化问题的限制条件多出一个与之前所有的w都垂直,那么就是:

      \(Find\ w_2\ maximizing: w_2^TSw_2, w_2Tw_2=1, w_2^Tw_1=0\)

      按照 目标函数 - 系数*zero_form of 限制条件 的拉格朗日使用方法,可以得到如下无限制条件的优化问题:

      如果 W 矩阵有多行

      对于 W 矩阵有多行的情况,优化目标函数需要改变, 要增加限制条件,如果不加改变的话你得到的 wn 永远与 w1 一样,增加的这个限制条件是:后面的每个w都要与前面的所有w相互垂直 --- 内积为0

      \(Find\ w_2\ maximizing:\)

      $$ g(w_2) = w_2^TSw_2 - \alpha(w_2^Tw_2-1)-\beta(w_2^Tw_1-0) $$

      同样的通过微分等于0来求无限制条件的优化问题:

      \(\frac{\partial g(w_1)}{\partial w_{11}} = 0\)

      \(\frac{\partial g(w_1)}{\partial w_{12}} = 0\)

      化简上述结果可以得到:

      \(Sw_2 - \alpha w_2 - \beta w_1 = 0\)

      上述等式两边同时乘以 w1:

      \(w_1^TSw_2 - \alpha w_1^Tw_2 - \beta w_1^Tw_1 = 0\)

      \(w_1^TSw_2 - \alpha * 0 - \beta * 1 = 0\)

      因为 \(w_1^TSw_2\) 本身是一个 向量矩阵向量 的形式,他是一个数值,数值的转置还是自身:

      \(w_1^TSw_2 = (w_1STw_2)^T = w_2^TS^Tw_1\)

      因为 S 是 Covariance Matrix of x, 是对称的,所以 \(S^T=S\)

      \(w_2^TS^Tw_1= w_2^TSw_1\)

      使用 w1 的结论,\(Sw_1 = \lambda_1w_1\), 所以有

      \(w_2^TSw_1=\lambda_1w_2^Tw_1=0\)

      所以,综合起来看:

      \(w_1^TSw_2 - \alpha w_1^Tw_2 - \beta w_1^Tw_1 = 0\)

      \(w_1^TSw_2 - \alpha * 0 - \beta * 1 = 0\)

      \(0 - \alpha * 0 - \beta * 1 = 0\)

      所以:

      \(\beta=0\)

      所以:

      \(Sw_2 - \alpha w_2= 0\)

      \(Sw_2 = \alpha w_2\)

      由于 w2 也是 eigen vector, 同样有很多选择,与 w1 选择的依据一样,我们只能选择剩下最大的那个 eigenvalue of S 对应的 eigenvector

      so,结论是:

      $$ z = Wx $$

      $$ W = \begin{vmatrix} (w_1)T \\ (w_2)T \\ . \\ . \\ . \end{vmatrix}\quad $$

      $$ W = \begin{vmatrix} 1st\ largest\ eigenvalues'\ eigenvector\ of\ Cov(x) \\ 2nd\ largest\ eigenvalues'\ eigenvector\ of\ Cov(x) \\ 3rd\ largest\ eigenvalues'\ eigenvector\ of\ Cov(x) \\ ...\end{vmatrix} $$

      PCA 的副产品 --- 降维后数据点的各个维度互相垂直

      数据点的各个维度互相垂直

      用数学语言来表述就是

      数据点的协方差矩阵是一个 Diagonal matrix

      也就是

      数据点的各个维度之间没有 correlation

      这样有什么作用呢?

      一个很好的作用是,原来的 data 经过 PCA 之后输出的新的 data 可以接其他较为简单的(或是对数据点维度要求无 correlation 的)model ---> eg. Naive Bayes.

      如何证明呢?

      $$ Cov(z) = \sum(z - \bar{z})(z-\bar{z})^T $$

      这一项,可以可以展开合并后成为下面这种形式:

      $$ Cov(z) = \sum(z - \bar{z})(z-\bar{z})^T = WSW^T,\ \ S = Cov(x) $$

      $$ W^T=\begin{vmatrix} w_1 \\ .\\.\\.\\ w_k \end{vmatrix}^T= [w_1, ..., w_k] $$

      注意转置之前 w1 是 W矩阵的行向量,转置后,w1 是 W^T 的 列向量:

      $$ \begin{vmatrix} 1 & 2 & 3 & \rightarrow w_1\\ 4 & 5 & 6 & \rightarrow w_2 \\ 7 & 8 & 9 & \rightarrow w_3 \end{vmatrix}^T \rightarrow \begin{vmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \downarrow & \downarrow & \downarrow \\ w_1 & w_2 & w_3 \end{vmatrix} $$

      $$ WSW^T = WS[w_1, ..., w_k] = W[Sw_1, ..., Sw_k] $$

      利用之前的结论:

      \(Sw_1 = \lambda_1 w_1\)

      $$ W[Sw_1, ..., Sw_k] = W[\lambda_1 w_1, ..., \lambda_k w_k] = [\lambda_1Ww_1, ..., \lmabda_kWw_k] = [\lambda_1e_1, ..., \lambda_ke_k] $$

      其中 \(e_i\) 是指第 \(i\) 位为 1, 其余位都为 0 的列向量。

      所以 \(Cov(z)\) 就是一个 Diagonal matrix.

      总结

      PCA 关键词:

      • linear function, projection
      • maximize Variance of z
      • Covariance Matrix of x
      • eigenvector of Covariance Matrix

      一个重要的结论需要记住: Covariance Matrix is a symmetric, positive-semidefinite matrix, so it has non-negative eigenvalues

      一个重要的技术:

      带限制条件优化

      --- Lagrange multiplier ---> 无限制条件优化

      --- partial dirivitive = 0 --->

      求解。

      一个重要的机器学习常识:

      数据点的各个维度互相垂直

      用数学语言来表述就是

      数据点的协方差矩阵是一个 Diagonal matrix

      也就是

      数据点的各个维度之间没有 correlation

  3. Sep 2017
    1. The projection score - an evaluation criterion for variable subset selection in PCA visualization

      "variable" typically means gene or locus in the context of biological data.