课程视频地址：https://study.163.com/courses-search?keyword=CS231

课程主页：http://cs231n.stanford.edu/2017/

参考资料：https://github.com/zhyh2010/cs231n/tree/master/assignment1

我的代码地址：https://github.com/Doraemonzzz/CS231n

这一部分回顾作业1的重点。

1.k-最近邻分类器

这题的难点是向量化k-nn的计算过程，将问题描述如下，假设

其中$x^{(i)} ,y^{(i)} \in \mathbb R^d​$，现在的问题是如何高效计算矩阵$D \in \mathbb R^{m\times n}​$，其中

首先对$D_{i,j}$进行处理

那么

利用numpy的广播机制上式可以简写如下：

test = np.sum(X ** 2, axis=1).reshape(-1, 1)
train = np.sum(self.X_train ** 2, axis=1).reshape(1, -1)
dists = np.sqrt(test + train.T - 2 * X.dot(self.X_train.T))

2.训练一个SVM

这一部分介绍如何求SVM的梯度，首先有如下假设

其中$x^{(i)} \in \mathbb R^d,y^{(i)}\in \mathbb R​$，我们的计算公式如下：

对于样本$x^{(i)}​$，损失函数如下

计算$s^{(i)}​$的第$j​$项$s_j ^{(i)}​$可得

所以

所以$\nabla _{W} s^{(i)}_j​$为除了第$j​$列为$x^{(i)}​$，其余元素全为$0​$的矩阵。现在关于$L_i​$求梯度可得

因此循环形式的梯度更新代码如下：

dW = np.zeros(W.shape) # initialize the gradient as zero

# compute the loss and the gradient
num_classes = W.shape[1]
num_train = X.shape[0]
#print(X.shape, dW.shape)
loss = 0.0
for i in xrange(num_train):
    scores = X[i].dot(W)
    correct_class_score = scores[y[i]]
    for j in xrange(num_classes):
      if j == y[i]:
        continue
      margin = scores[j] - correct_class_score + 1 # note delta = 1
      if margin > 0:
        loss += margin
        dW[:, j] += X[i]
        dW[:, y[i]] -= X[i]

接下来考虑如何将上述过程向量化。注意到$j=y^{(i)}$时，

所以梯度的式子可以改写为

总梯度为

上述形式提醒了我们该如何向量化，首先计算得分矩阵$S’\in \mathbb R^{m\times c}$，其中

对应代码如下：

#样本数量
n = X.shape[0]
#记录得分
score = X.dot(W)
#正确的分数
score_correct = score[np.arange(n), y].reshape(-1, 1)
#计算分数
temp = score - score_correct + 1

然后计算$S’>0​$的布尔矩阵，对应代码如下（这部分写的不够简洁）：

temp[temp < 0] = 0
temp[temp > 0] = 1

在考虑下式之前

先考虑其每个分量，即

所以

注意到

所以

因为$\nabla_W s_{y^{(i)}}^{(i)}$表示除了第$y^{(i)}$列为$x^{(i)}$，其余元素全为$0$的矩阵，实际操作时要减去上述梯度，所以$S’$应该作出如下更新

对应代码如下

num = np.sum(temp, axis=1)
temp[np.arange(n), y] -= num

这步结束后重新利用$X^T S’​$计算梯度即可，代码为

dW = X.T.dot(temp)

3.实现Softmax分类器

这部分推导Softmax分类器下的梯度，首先依旧有

其中$x^{(i)} \in \mathbb R^d,y^{(i)}\in \mathbb R​$，我们的计算公式如下：

在Softmax分类器，我们有

对于样本$x^{(i)}$，损失函数如下

计算$s^{(i)}​$的第$j​$项$s_j ^{(i)}​$可得

所以

所以$\nabla_W L_i$可以拆成两个矩阵，记为$A_i,B_i$，即

其中矩阵$A_i​$第$s,t​$个元素为

即矩阵$A_i $第$y^{(i)}$列为$-x^{(i)}$，其余元素全为$0$，因此循环形式的梯度更新代码如下：

N, D = X.shape
for i in range(N):
    x = X[i]
    #计算梯度第一项
    dW[:, y[i]] -= x

矩阵$B_i​$第$s,t ​$个元素为$x^{(i)}_s \frac{e^{s^{(i)}_t} }{\sum_j e^{s^{(i)}_j}}​$，所以

对应代码如下：

score = x.dot(W)
#计算概率
p = np.exp(score) / np.sum(np.exp(score))
#计算梯度第二项
dW += x.reshape(-1, 1).dot(p.reshape(1, -1))

接下来考虑如何将上述过程向量化，首先对损失函数向量化，总损失为

考虑$\frac{e^{s^{(i)}_{y^{(i)}}}}{\sum_j e^{s^{(i)}_j}}​$，首先考虑分子构成的矩阵

利用$\vec y$可以很方便计算上式，对应代码如下

N, D = X.shape
S = X.dot(W)
p1 = np.exp(S[np.arange(N), y])

接着考虑分母构成的矩阵$\sum_j e^{s^{(i)}_j}$，对应代码如下

p2 = np.sum(np.exp(S), axis=1)

所以损失函数可以用如下代码求出

p = p1 / p2
loss = np.sum(-np.log(p))

接着讨论如何向量化求梯度，首先由公式$(1)$可得

先考虑$\sum_{i=1}^ m B_i​$，首先构造矩阵$P \in \mathbb R^{m\times c}​$，使得

对应代码如下

p3 = np.exp(S) / p2.reshape(-1, 1)

因为

所以

接下来考虑$\sum_{i=1}^ m A_i$，注意矩阵$A_i $第$y^{(i)}$列为$-x^{(i)}$，其余元素全为$0$，而$\nabla_W L$为两项之和，所以可以对$P_{i,j} $作如下更新

对应代码如下

p3[np.arange(N), y] -= 1

最后重新计算$X^TP​$得到

对应代码如下

dW = X.T.dot(p3)

4.实现2层神经网络

首先对第3题的softmax稍作修改，然后计算$b$的梯度

其中$x^{(i)} \in \mathbb R^d,y^{(i)}\in \mathbb R$，我们的计算公式如下：

注意上述第一个加号要理解为numpy中加号（利用广播机制自动匹配维度），$s^{(i)}​$对应的损失为

注意到

所以

由$Z_j^{(i)}​$的定义可知

因此

接着构造矩阵$P \in \mathbb R^{m\times c}​$，使得

接下来对矩阵$P$作如下处理

那么$\nabla_b L​$为矩阵$P​$按行求和得到的向量，$\nabla _W L​$的计算方法不变，对应代码如下：

S1 = X.dot(W1) + b1
#RELU
X1 = np.copy(S1)
X1[X1 < 0] = 0
scores = X1.dot(W2) + b2

N, D = scores.shape
#计算概率
p1 = np.exp(scores[np.arange(N), y])
p2 = np.sum(np.exp(scores), axis=1)
p = p1 / p2
#计算损失
loss = np.sum(-np.log(p)) / N + reg * (np.sum(W1 * W1) + np.sum(W2 * W2))

#计算第二层梯度
p3 = np.exp(scores) / p2.reshape(-1, 1)
p3[np.arange(N), y] -= 1
dW2 = X1.T.dot(p3) / N + 2 * reg * W2
db2 = np.sum(p3, axis=0) / N
grads["W2"] = dW2
grads["b2"] = db2

由于要进行反向传播，我们还需要计算$\nabla_X L$，先计算$\frac{\partial s^{(i)}_j}{\partial X_{st}}$，注意到我们有

所以

因此

所以

对应代码为

#计算
dX = p3.dot(W2.T)

接着求RELU函数的导数，对应代码为

#RELU
dX[X1 <= 0] = 0

注意，以下部分请忽略之前的记号。

为了后续讨论方便，这里假设最后的输出为$f$，后一层传给前一层的导数矩阵为$F\in \mathbb R^{m\times c}$，前一层为$X\in \mathbb R^{m\times d}$，对应权重和偏置项为$W\in \mathbb R^{d\times c},b\in \mathbb R^{c}$，记$S$的第$i$行为$s^{(i)}$，$X$的第$i$行为$x^{(i)}$，那么

注意到

因此

对应代码为

#计算第一层的梯度
N1, D1 = S1.shape
dW1 = X.T.dot(dX)
db1 = np.sum(dX, axis=0)