EM-Algorithm

Share

今天，让我们讲一讲一个著名的算法：EM算法（期望最大化算法）。

在讲EM算法之前，先让我们认识一个不等式：Jensen不等式

对于凸函数 $ f $, 如果 $ X $ 是一个随机变量，那么总有 \(E[f(x)]\geq f(EX)\)

在这里我们不提供严格证明，提供以下图片方便理解

好了，学会了这个不等式，我们就可以出发了~

EM算法的主体思想是：找到一个下界函数，去逼近原函数，然后通过求下界函数的最大值来迭代求解原函数，类似下图：

接下来我们来看具体的流程

对于任意的训练集 \(\{x^{(1)},x^{(2)},...,x^{(m)}\}\) ,如果我们用模型 \(p(x,z)\) 去拟合，可以得到下面的似然函数：

\[\begin{align} \iota (\theta ) &= \sum _{i=1}^{m}\log p(x;\theta ) \\ &=\sum _{i=1}^{m}\log\sum _{z}p(x,z;\theta ) \end{align}\]

我们令 \(Q_i\) 为 \(z\) 的某些分布（ \(\sum_z Q_i(z)=1\) && \(Q_i(z)\geq 0\)）,则有

\[\begin{align} \sum _i \log p(x^{(i)};\theta ) &= \sum _i \log \sum _{z^{(i)}}p(x^{(i)},z^{(i)};\theta ) \\ & = \sum _i \log \sum _{z^{(i)}}Q_i(z^{(i)}) \frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \\ & \geqslant \sum _i \sum _{z^{(i)}} Q_i(z^{(i)}) \log \frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \end{align}\]

这里用到了Jensen不等式。因为对数函数是凹函数，所以这里不等号需要反过来。

我们已经找到了原函数的下界函数，现在要做的是去逼近原函数。注意Jensen不等式的取等条件，当 \(F(x)=c\) 时等号成立。

所以有， \(\frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}=c\) ,也即 \(Q_i(z^{(i)})\propto p(x^{(i)},z^{(i)};\theta)\)

因为 \(Q_i\) 是 \(z^{(i)}\) 的分布，所以有：

\[\begin{align} Q_i(z^{(i)}) & = \frac {p(x^{(i)},z^{(i)};\theta)}{\sum _z p(x^{(i)},z;\theta)} \\ & = \frac {p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)} \\ & = p(z^{(i)}|x^{(i)};\theta ) \end{align}\]

将值带入，我们就得到了一个在 \(\theta_0\) 处“紧贴”原函数的下界函数。然后，我们去求令该下界函数取值最大的 \(\theta_1\)

总结一下EM算法：

repeat until convergence {

(E-step)For each i, set \[ Q_i(z^{(i)}) = p(z^{(i)}|x^{(i)};\theta ) \] (M-step)Set \[ \theta = argmax_\theta \sum _i \sum _{z^{(i)}} Q_i(z^{(i)}) \log \frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \] }

EM算法的收敛性就不在本文证明，有兴趣的同学可以看CS229的讲义

下面给出两个EM算法的实践：KMeans和GMM

CS231N实验：dropout

Share

PS: 本文默认已学习CS231N相关课程并掌握相关知识。

dropout的相关原理本文不再描述，详情请见Dropout (neural networks)

那么我们怎么实现dropout呢？假设我们有 \(n\) 个神经元，每个神经元输出 \(m\) 维向量。那么，我们就随机生成一个 \(n\) 维向量，并按一定比例将值设为0(随机失活)。

1
2
3
4
5
6
# forward
mask = (np.random.random(x.shape[0]) > p) / (1-p) # rescale
out = x * (mask.reshape(-1, 1))
# backword
dx = mask.reshape(-1, 1) * dout

CS231N实验：Softmax

Share

PS: 本文默认已学习CS231N相关课程并掌握相关知识。

Softmax的实验部分跟SVM非常相似，所以本文就简单求下 \(loss\) 和 \(grad\)

Softmax的 \(loss function\) 定义为

\[ L = - \frac{1}{m}\sum_{i=1}^{m}\ln{\frac{e^{(X[i]*W)[y[i]]}}{\sum_{i=1}^{C}{e^{(X[i]*W)[j]}}}} \]

接下来我们求 \(grad\)

\[ dW[:, l] = {\begin{cases} -X[i] + {\frac{e^{(X[i]*W)[l]}}{\sum_{i=1}^{C}{e^{(X[i]*W)[j]}}}} * X[i], & l = y[i] \\ {\frac{e^{(X[i]*W)[l]}}{\sum_{i=1}^{C}{e^{(X[i]*W)[j]}}}} * X[i], & l \neq y[i] \\ \end{cases} } \]

CS231N实验：SVM

Share

PS: 本文默认已学习CS231N相关课程并掌握相关知识。

SVM的实验部分分为以下内容：

  • 计算loss和grad
  • 随机梯度下降
  • 模型调参

计算loss和grad

MultiClass SVM的方程为

\[ f(x) = x * W \]

其中， \(x\) 为 \(1*k\), W为 \(k*C\) ( \(C\) 是label种类)

\(loss function\) 定义为

\[ L = \frac{1}{m}\sum_{i=1}^{m}{\sum_{j \neq y[i]}{max{(0, f(X[i])[j] - f(X[i])[y[i]] + 1)}}}\]

实验中已经帮我们实现了 \(loss function\) ,接下来我们要做的就是计算 \(grad\) 。众所周知，\(grad = \frac{\partial L}{\partial W}\) 。 \(loss function\) 只是简单的相加，所以我们考虑每一项不为0的组成部分对导数的贡献。

\[\begin{align} dW[:, l] & = \frac{\partial (f(X[i])[j] - f(X[i])[y[i]] + 1)}{\partial W[:, l]} \\ & = {\begin{cases} X[i], & l = j \\ -X[i], & l = y[i] \\ 0, & other \\ \end{cases} } \end{align}\]

这样，我们就求出了 \(dW\) 。

随机梯度下降

首先我们要从数据中随机获取 \(batch\_size\) 样本（使用numpy.randomchoice）,然后用这些数据进行一轮迭代，获得grad,再进行下降。

模型调参

SVM模型有各种不同的参数。我们用多重循环，得到每种参数的组合的train accuracy和val accuracy，并记录最好的。（比较简单暴力）

CS231N实验：KNN

Share

PS: 本文默认已学习CS231N相关课程并掌握相关知识。

KNN的实验部分主要分为3大块内容：

  • 计算测试集数据与训练集数据之间的距离，存放在dists矩阵中
  • 用距离最近的K个标签，做classifier得到测试集label
  • 交叉验证

接下来我们对这三部分进行探究

距离计算

实验中分别让我们用two-loops, one-loop和no-loop计算距离。

假设我们的训练集规模为 $ n * k $, 测试集规模为 $ m * k $, 那么计算距离的方法如下：

\[ dists[i][j] = \sqrt{\sum_{l=1}^k(test[i][l] - train[j][l])^2} \]

其中，dists为$ m * n $的矩阵

那么，two-loops的计算方法就呼之欲出了，就是对两个$ k $维向量计算距离：

1
2
3
for i in xrange(num_test):
  for j in xrange(num_train):
    dists[i][j] = np.sqrt(np.sum(np.square(X[i] - self.X_train[j])))

现在，我们考虑下one-loop的算法。对于测试集中每一个数据，都要与训练集中每个数据计算距离。其实我们可以利用numpy的broadcast,对每个测试集中的数据计算他到所有训练集数据的距离：

1
2
for i in xrange(num_test):
    dists[i] = np.sqrt(np.sum(np.square(X[i] - self.X_train), axis=1))

接下来，我们考虑no-loop的做法，这就需要用到一些矩阵运算的知识。我们将平方项展开:

\[\begin{align} dists[i][j] & = \sqrt{\sum_{l=1}^k(test[i][l] - train[j][l])^2} \\ & = \sqrt{\sum_{l=1}^k(test[i][l]^2 - 2 * test[i][l] * train[j][l] + train[j][l]^2)} \\ & = \sqrt{- 2 * \sum_{l=1}^k{test[i][l] * train[j][l]} + \sum_{l=1}^k{test[i][l]^2} + \sum_{l=1}^k{train[j][l]^2}} \end{align}\]

在这里我们注意到, \({\sum_{l=1}^{k}{test[i][l] * train[j][l]}}\) 就是 \(test * train^T\) , 而 \(\sum_{l=1}^k{test[i][l]^2}\) 和 \(\sum_{l=1}^k{train[j][l]^2}\) 只是对矩阵中的 \(k\) 维向量求平方和，可以用numpy实现。代码如下：

1
dists = np.sqrt(-2*np.dot(X, self.X_train.T) + np.sum(np.square(self.X_train), axis = 1) + np.transpose([np.sum(np.square(X), axis = 1)]))

计算测试集label

在得到dists矩阵后，我们就可以计算测试集中每个样本的label。KNN算法就是获得距离样本最近的K个点，然后将这K个点中出现最多的label作为样本label：

1
2
3
4
5
6
7
# 获得最近的k个点标签
dist = np.argsort(dists[i])
for i in xrange(k):
    closest_y.append(self.y_train[dist[i]])
# 获得出现最多的label
y_pred[i] = np.argmax(np.bincount(closest_y))

交叉验证

交叉验证最主要的工作在于数据集的划分，实验中提供了np.array_split作为参考。实验中用了5-floder交叉验证。我们使用np.vstack将其他四份数据合在一起作为训练集，剩下一份作为验证集。

代码参考

  • https://github.com/lightaime/cs231n