SVM loss vectorized 实现

Posted on

什么是 SVM loss vectorized

SVM loss vectorized 即用 vector 的方式来计算 SVM 的 loss function.

SVM loss function 的原理并不难理解，直接用循环实现也很简单。但是因为 Numpy 的底层做了优化，所以使用矩阵运算会比使用循环快得多。而这对于不熟悉 Numpy 的人来说，写起来有不小的压力。所以本文将详尽的对实现代码进行分析，包括整体计算思路，每一个函数的作用和每一步以后变量的变化。

准备工作

本文聚焦于 Multiclass Support Vector Machine Loss，首先简要的介绍下什么是 Multiclass Support Vector Machine Loss。

SVM loss

援引自 CS231n 中的介绍： >给定一个参数\(\Delta\)，SVM loss function 总是希望 SVM 针对除了正确分类以外的每一个错误分类的评分都比正确分类的评分要高 \(\Delta\)。如果对正确分类的评分比错误分类的评分要高，那么这一点的 loss 就记为 0，否则记为 \(s_j-s_{y_i} + \Delta\)（即，错误评分-正确评分+\(\Delta\)）。

\(s_j-s_{y_i} + \Delta\) 是 SVM 希望的结果的负值，仔细阅读每一个字可以看出。

完整的 loss function 的定义如下:

\[ L = \frac{1}{N}\sum_i\sum_{j \ne y_i}[max(0,w_j^Tx_i-w_{y_i}^Tx_i+\Delta)] + \lambda\sum_k\sum_l W_{k,l}^2 \]

Analytic Gradient

所谓 Analytic Gradient, 一言以蔽之，就是先用纸笔算出loss function 的 gradient，然后再用代码实现，针对大小为 n 的 mini-batch而言，不是针对单个而言。

对 \(w_j\) （错误的分类）求导时：

\[ \nabla_{w_j}L=\frac{1}{N}\sum_i1(w_j^Tx_i-w_{y_i}^Tx_i+\Delta > 0)x_i + 2\lambda W_{i,j} \]

对 \(w_{y_i}\) （正确的分类）求导时：

\[ \nabla_{w_{y_i}}L=-\left(\sum_i\sum_{j \ne y_i}1\left(w_j^Tx_i-w_{y_i}^Tx_i+\Delta > 0\right)x_i+2\lambda W_{i，j}\right) \]

实现及解释

其中

  • 权重 W(3073, 10)：3073个属性，分类是10个。
  • 输入属性 X(500, 3073)：500个输入，每个输入有 3073个属性。
  • 正确分类 y(500,)：针对每一个的正确分类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def svm_loss_vectorized(W, X, y, reg):
  loss = 0.0
  dW = np.zeros(W.shape)
  num_train = X.shape[0]

  # 计算 loss。
  scores = X.dot(W)
  correct_scores = scores[np.arange(scores.shape[0]), y]
  margins = np.maximum(0, scores - np.matrix(correct_scores).T + 1)
  margins[np.arange(num_train), y] = 0
  loss = np.sum(margins, axis=1) / num_tranin
  loss += reg * np.sum(W * W)

  # 计算 gradient。
  binary = margins
  binary[margins > 0] = 1
  row_sum = np.sum(binary, axis=1)
  binary[np.arange(num_train), y] = -row_sum.T
  dW = np.dot(X.T, binary)

  dW /= num_train

  # Regularize
  dW += 2 * reg * W

  return loss, dW

计算 Loss

我们计算时采用 mini-batch，每个 mini-batch 的大小是 500，恰好等于输入的 X(500, 3073) 的大小，所以我们只需要计算 loss，然后加在一起。 1. num_train = X.shape[0]得到的是训练数据集的数量，在这里是 500。 2. scores = X.dot(W)，score是(500,10)，计算的是500个数据集中每个数据项在这10个分类的得分。 3. correct_scores = scores[np.arange(scores.shape[0]), y]，从scores出提取出每一个数据项在正确分类的得分。这里np.arange(scores.shape[0]生成了一个(500,1)的 vector，内容为[0, 1, 2, ..., 498, 499]^T，y同样也是一个(500,1)的array，这两个相对应，从score中提取出scores[0, y[0]], scores[1, y[1]], ... scores[499, y[499]] 项，也就是提取出了正确分类的得分，所以 scores 为一个 (500,1) 的 vector。 4. margins = np.maximum(0, scores - np.matrix(correct_scores).T + 1)，margin大小为(500，10)。这一步利用公式 loss function 中的公式计算出所有数据项的 margin。但是有一点值得注意，在公式中，我们是要跳过正确分类 magin 的计算的，也就是把 对于正确分类的 magin 记为 0。这里并没有跳过，所以计算出了它的值，所以在下一步我们要正确分类的 margin 设置为0。 5. margins[np.arange(num_train), y] = 0，将正确分类的 margin 值设置为 0。 6. loss = np.sum(margins, axis=1) / num_tranin，因为我们是对 mini-batch(500)上进行的 loss 进行的计算，所有我们要取其平均值。 7. loss += reg * np.sum(W * W)：加上 Regulariztion 的部分。

计算 Gradient

计算 gradient 的公式在准备工作->Analytic Gradient 这一小节中已经给出，我们计算 Gradient 的主要依据就是这两个公式。

大体思路

我们计算 Gradient 的时候，主要研究的是某一个数据项 的针对每一个分类（此处共 10 个 分类）的 margin 值。对于某个错误分类的 marging 如果大于 0，那么将错误分类对应的 \(dW_i(3073, 1)\) 加上一个所对应的 \(x_i(3073, 1)\)；同时，对于 n 个 margin 大于 0 的分类（不包括正确的分类），就将它对应的 \(dW_{y_i}(3073, 1)\) 设置成 \(-n*x_i(3073, 1)\)。

  1. binary = margins，binary 的大小是(500,10)。这里 binary 这个名字有点误导性，对于每个 margin > 0 的非正确分类，我们确实将它设置为 1，对于每个 margin = 0 的部分，我们保持 0。但是对于每个数据项的正确分类，我们总是将它设置为所有 margin > 0 的非正确分类的数量和。
  2. binary[margins > 0] = 1，对于每个 margin > 0 的非正确分类，我们将它设置为 1。
  3. row_sum = np.sum(binary, axis=1)，row_sum 的 size 是 (500,1)。记录的是对于每一个数据线，分别有多少个 margin > 0 的非正确分类，我们利用这个来计算出正确分类的 \(dW\)。
  4. binary[np.arange(num_train), y] = -row_sum.T，将对于每个数据项中 margin > 0的非正确分类的的数量的负值记录在相应的位置。
  5. dW = np.dot(X.T, binary), dW 的 size 为 (3073, 10)。运用点乘的技巧，将每个x负值在dW上。

总结

原理十分的简单，非 vectorized 的实现其实也很容易，主要的难点还是在如何使用 numpy 。

0%