CS231 作业1

课程视频地址: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的广播机制上式可以简写如下:

1
2
3
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​$求梯度可得

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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}$,其中

对应代码如下:

1
2
3
4
5
6
7
8
#样本数量
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​$的布尔矩阵,对应代码如下(这部分写的不够简洁):

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

在考虑下式之前

先考虑其每个分量,即

所以

注意到

所以

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

对应代码如下

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

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

1
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$,因此循环形式的梯度更新代码如下:

1
2
3
4
5
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}}​$,所以

对应代码如下:

1
2
3
4
5
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$可以很方便计算上式,对应代码如下

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

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

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

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

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

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

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

对应代码如下

1
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} $作如下更新

对应代码如下

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

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

对应代码如下

1
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​$的计算方法不变,对应代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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}}$,注意到我们有

所以

因此

所以

对应代码为

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

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

1
2
#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)}$,那么

注意到

因此

对应代码为

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

本文标题:CS231 作业1

文章作者:Doraemonzzz

发布时间:2019年03月02日 - 22:39:00

最后更新:2019年03月29日 - 19:50:35

原始链接:http://doraemonzzz.com/2019/03/02/CS231 作业1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。