Logistic & GDA

区别

1. Logistic是判别模型（对条件概率进行建模$P(y|x)$），GDA是生成模型（对联合概率进行建模$P(x|y)$）
2. GDA实际上有着更强的假设，同时，其后验概率分布就是sigmoid函数
   • 在模型符合该假设的前提下，效果比logistic更好
3. logistic模型的robust更好
   • 可以发现，如果$p(x|y)$的条件概率不满足正态分布，而是posisson分布，也能得到sigmoid函数（用Logistic效果也不错）
4. 生成模型的好处就是：需要的数据更少（因为对数据的假设更强）

SVM

SVM的主要思想是，对一个超平面而言，希望对分类边界的geometry margin最大。写出函数的约束和求解目标，通过Lagrange函数转为对偶问题，同时用KKT条件使得对偶问题的最优解和原始问题的最优解相同。同时，为了处理非线性的情况，引入了kenrel的概念，通过coordinate ascent（SMO）算法求解对偶问题的最优解。

• 原始问题建模

  • $\min \frac{1}{2} ||w||^2$
  • $s.t. \quad y_i(w\cdot x_i + b ) -1 \ge 0, i = 1,2,...,N$
  • 当$y_i(w\cdot x_i + b) =1$时是support vector

• 对偶问题

  • $\min \frac{1}{2}\sum_i\sum_j \alpha_i \alpha_j y_i y_j(x_i\cdot x_j) - \sum_i \alpha_i$
  • $s.t. \quad \sum \alpha_iy_i = 0\quad \alpha_i \ge 0$
  • 由KKT条件，$w = \sum \alpha_iy_ix_i$，同时可求得对应的b
  • 决策函数只依赖于输入样本的内积
  • 求得了$\alpha$，当$\alpha_j>0$时对应的$j$是support vector（真正对$w$有用的）

• Kernel

  • 将attributes -> feature 的过程定义为feature mapping，例如
    • $\phi(x) = \begin{bmatrix}x\\x^2 \\ x^3\end{bmatrix}$
    • 因此，我们想从feature中进行学习，而不是原始的attributes。而注意到，我们对样本的预测只与内积有关，因此可以定义Kernel：$K(x,z) = \phi(x)^T\phi(z)$
  • 这样，在原始算法中的所有内积都用Kernel代替，这样就实现了从feature中学习
  • 这种kernel的思想并不仅仅适用于SVM，只要有内积的形式，都可以使用，可以大大减少feature空间的维度
  • Gaussian kernel：$K(x,z) = \exp(-\frac{||x-z||^2}{w\sigma^2})$

• SMO

  • 使用coordinate ascent进行优化，也就是每次对一个序列中的某些参数更新。由于对偶问题是二次型的形式，因此很容易进行求解。

  • 需要注意的是，由于我们的每个$\alpha$存在约束，因此不能每次只对一个参数进行优化（至少需要两个），约束条件可以从等式中得到。

EM algorithm

EM是一种用于处理隐变量的迭代算法，它基于局部最优解进行求解，而不能保证全局最优。（可以认为是coordinate ascent方法）

Kmeans

kmeans是一种相当简单和直观的聚类算法，主要分类两步：

1. 对于每个点，选择离他最近的聚类中心作为他的类别：$c^{(i)} :=\arg \min _{j}||x^{(i)}-\mu_j||^2$
2. 对于每个类别，求解聚类这个类的聚类中心：$\mu_{j} :=\frac{\sum_{i=1}^{m} 1\{c^{(i)}=j\} x^{(i)}}{\sum_{i=1}^{m} 1\{c^{(i)}=j\}}$

Kmeans算法的两步可以与EM对应起来，唯一的不同是，在E步时，Kmeans用了硬分类，而不是得到属于某个类的概率。

GMM

一种密度估计的算法，我们使用EM思想来处理，主要有两个步骤：

1. E步：通过期望去guss $z$的最可能的值 $w_{j}^{(i)} :=p\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)$
   • 实际上我们是通过后验概率来进行估计
     • $p\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)=\frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{\sum_{l=1}^{k} p\left(x^{(i)} | z^{(i)}=l ; \mu, \Sigma\right) p\left(z^{(i)}=l ; \phi\right)}$
   • 在这里，我们分子上的概率都可以直接得到，因此可以得到$x^{(i)} = j$的概率，也就是soft assignments $w^{(i)}_j$
2. M步：通过已知的$z$来对模型参数进行估计（与MLE相同）
   • $\phi_{j} :=\frac{1}{m} \sum_{i=1}^{m} w_{j}^{(i)}$
   • $\mu_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{j}^{(i)}}$
   • $\Sigma_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} w_{j}^{(i)}}$
3. 注意与GDA的区别，在GDA中，是已知隐变量的（也就是监督学习），但它们在都是通过贝叶斯公式MLE进行参数估计，但实际上GDA与logistic更像。

EM

我们可以通过Jensen’s inequality来证明EM算法总是能使得似然函数单调非减，同时说明了我们为什么在E步时需要求后验概率（$Q$函数，一般来说对于M步是带入它的期望，所以称为E步）：这是因为该$z$的分布函数能够使得不等式的等式成立，从而得到一个tight bound。

在M 步时，我们实际上是对最后一个式子求MLE估计，这样我们可以得到GMM的地推公式。

Factor analysis

当数据的维度远远大于数据的数量时，这时候如果我们还是用多维高斯来拟合，会发现其协方差矩阵是奇异矩阵，因此无法计算矩阵的逆。一种方法是，从低维空间中生成一系列的随机变量$z$，然后通过一个仿射变换到高维空间，同时加上误差项，就可以得到高维空间中的样本，例如： $\begin{aligned} z & \sim \mathcal{N}(0, I) \ \epsilon & \sim \mathcal{N}(0, \Psi) \ x &=\mu+\Lambda z+\epsilon \end{aligned}$ 这种方法被称为Factor analysis，其中$z$为factor。

可以认为$z$是隐变量，因此使用EM算法进行迭代求解（求解相对比较复杂，见CS229-note9）。需要注意的是，这里的E步并不仅仅是求期望，还需要协方差）