PCA

• 数学角度：
  -

从数据中提取低维特征

• 一般通过 SVD 来计算

回顾一下 PCA

假设数据是中心化的：$\sum_{i=1}^n x_i = 0$

在方向 v 上的任意投影也是中心化的，$\sum_{i=1}^n v^T x_i = 0$

我们希望数据之间能够越离散越好，相当于让投影后的方差最大：

$$\mathop{max}_v \sum{i=1}^n (v^T x_i)^2 \ \ \ \ s.t.\ v^tv = 1$$

也可以写成：

$$\mathop{max}_v v^TXX^Tv \ \ \ \ s.t.\ v^tv = 1$$

使用 Lagrangian 乘子对于 v 求导得 0 后：

$$(XX^T - \lambda I )v = 0 \rightarrow XX^T v = \lambda v$$

观察上面右边这个式子我们发现，这个很像特征值和特征向量的表示形式

• $XX^T$：协方差矩阵
• $v$：上面协方差举证的特征向量

EM Algotirhm

Gaussian Mixture Model

假设我们的数据分布在拥有 K 个 gaussian 核的空间中，每个数据点的概率等于它属于每个核的概率总和：

$$p(x) = \sum_{k=1}^K \pi_k N (x| \mu_k ,\Sigma_k)$$

其中 $\pi_k$ 是 mixing coefficient：

$$\sum_{k=1}^K \pi_k = 1, \ \ \ \ \pi_k\geq 0$$

于是所有数据点的 likelihood 就是：

$$\mathop{ln} p(X|\pi,\mu,\Sigma) = \sum_{n=1}^N ln \left( \sum_{k=1}^K \pi_k N (x^{(n)}| \mu_k, \Sigma_k) \right)$$

w.r.t $\Theta = \{ \pi_k, \mu_k, \Sigma_k\}$

Latent Variable

我们可以用一个隐变量 z 来表示哪一个 Gaussian 以多大的概率产生了我们的观测 x，从而可以解释上式括号内的项的由来

令 $z\sim Categorical(\pi)$, 有：

$$\begin{align} p(x) &= \sum_{k=1}^K p(x, z=k) \\ &= \underbrace{p(z=k)}_{\pi_k} \underbrace{p(x|z=k)}_{N(x|\mu_k,\Sigma_k)} \end{align}$$

最后给定数据，变量为 $\Theta$ 的 likelihood 就变成了：

$$\begin{align} l(\pi,\mu,\Sigma) = ln \ p(X|\pi,\mu,\Sigma) &= \sum_{n=1}^N ln \ p(x^{(n)}|\pi,\mu,\Sigma) \\ &=\sum_{n=1}^N ln \sum_{z^{(n)}= 1 }^K p(z^{(n)} | \pi)\ p(x^{(n)}|z^{(n)}; \mu, \Sigma) \end{align}$$

现在的问题就是我们如何来优化这个目标函数

Expectation Maximization

EM 算法分为两步：

1. E-step：对于每个 gaussian 计算对于每个点的后验概率 posterior
2. M-step：在给定每个点的概率下，重新计算 gaussian 的参数，使似然最大

EM 算法要解决的问题的一般形式为：

$$ln\ p(x|\Theta) = ln \sum_z p(x,z|\Theta)$$

z 是 latent variable，也就是说，z 一开始我们是不知道的。。所以 EM 算法其实是 unsupervised learning

但是对于 latent variable，我们可以做一个预测 $p(Z|X,\Theta^{old})$

于是，一般形式的 EM 算法为：

1. Initialize: $\Theta^{old}$
2. E-step：compute $p(Z|X,\Theta^{old})$
3. M-step：maximize $Q(\Theta, \Theta^{old}) = \sum_z p(Z|X,\Theta^{old})ln p(X,Z|\Theta)$
4. If not converged set $\Theta^{old} = \Theta$ and go to step 2