cs231n Assignment1--机器学习基本方法与深度学习尝试_综合

实验日期

2021.10.02 — 2021.10.06

实验环境

python 3.8.8 64-bit

KNN

KNN实验的核心就在于distance矩阵的计算。其中，计算方法分为两层循环，一层循环和无循环计算

两层循环
```
for i in range(num_test):for j in range(num_train):dists[i][j] = np.sqrt(np.sum(np.square(X[i , :] - self.X_train[j , :])))
```
- distance矩阵得出的结果是每一个测试数据距离所有训练数据的距离。因为我们可以在遍历测试集的每一个数据时，将测试数据各个feature的数据与训练数据对应feature相减，然后得到L2-norm形式的距离。最终dists[ i ] [ j ]代表第 i 的测试数据和第 j 个训练数据的L2-norm距离
一层循环
```
 for i in range(num_test):dists[i] = np.sqrt(np.sum(np.square(X[i , :] - self.X_train) , axis=1))
```
- 在这里，只使用一层循环，是遍历测试数据的。np.array的一个特性是，当一个向量与一个矩阵做加减运算时，该向量会自动复制，扩充到和矩阵一样大的维度，然后对应相减。所以这里的测试数据是一个行向量，在减去X_train时，会和X_train的每一行相减，这样我们就得到了所有的差值，然后平方，求和，开方，就得到了L2-norm距离
无循环
```
 a = np.sum(np.square(X) , axis=1 , keepdims=True) #列向量b = np.sum(np.square(self.X_train) , axis=1) # 行向量c = np.multiply(np.dot(X , self.X_train.T) , -2)dists = np.add(a , b)dists = np.add(dists , c)dists = np.sqrt(dists)
```
- 这里需要数学上的小技巧，即利用 $x-y)^2 = x^2 + y^2 - 2xy$ 的公式，我们想要得到式子左边的，可以通过求式子右边的 $x^2$ , $y^2$ , $? 2 x y$ 来得到，即a ， b ， c ，注意：a ， b 分别为列向量和行向量，相加得到一个矩阵
三种循环的运行速度
- Two loop version took 29.890179 seconds
- One loop version took 57.145778 seconds
- No loop version took 0.229963 seconds

补充predict

closest_y = self.y_train[np.argsort(dists[i,:])[:k]] #取前k小个dist对应的索引
y_pred[i] = np.argmax(np.bincount(closest_y))#找出现最多次的label

利用np.argsort得到前k小dists的索引，然后再利用np.bincount计算这些索引出现的次数，最后利用大多数投票的方式得到最终的label

交叉验证

X_train_folds = np.array_split(X_train , num_folds , axis = 0)
y_train_folds = np.array_split(y_train , num_folds , axis = 0)

首先将训练集分为num_folds份

for k in k_choices:accuracies = []for i in range(num_folds):#选取一份当验证集，其余的作为训练集X_train_cv = np.vstack(X_train_folds[0:i] + X_train_folds[i+1:])y_train_cv = np.hstack(y_train_folds[0:i] + y_train_folds[i+1:])X_valid_cv = X_train_folds[i]y_valid_cv = y_train_folds[i]classifier.train(X_train_cv , y_train_cv)dists = classifier.compute_distances_no_loops(X_valid_cv)y_test_pred = classifier.predict_labels(dists , k)num_correct = np.sum(y_test_pred == y_valid_cv)accuracy = float(num_correct) / y_valid_cv.shape[0]accuracies.append(accuracy)k_to_accuracies[k] = accuracies

交叉验证中，将刚才分好的数据，选取一份做验证集，其余的作为训练集，进行训练和预测，并得到预测的准确度
尝试不同的k
最终选取训练效果最好的k = 10
- Got 141 / 500 correct => accuracy: 0.282000

SVM

首先，推导SVM loss function对w的梯度

对于每一个样本，正确分类的得分应该比错误分类的得分至少高 $\Delta$ , $\Delta$ 取值在实际中一般为1

若正确分类的得分比错误分类的得分大1 ，则认为判断正确
loss function： $L_i = \sum_{j \ne y_i} [max(0 , w_j^Tx_i - w_{y_i}^Tx_i + \Delta)]$
- $w_{y_i}^Tx_i$ 求的是 $x_i$ 在第 $y_i$ 个类别，也就是对正确分类的得分
- $w_j^Tx_i$ 求的是 $x_i$ 在第 j 个类别的得分，也就是对错误分类的得分
- $\Delta$ 是正确分类的得分要比错误分类的得分高 $\Delta$ 才算分类正确，分类正确 loss 算 0
- $\Delta$ 通常取1 ，因为 $\Delta$ 的变换可以转换成 $w$ 的变化
梯度
- 对loss function 直接求梯度，实际是分成两部分求的，一部分是对 0 求，一部分是对 $\sum_{j \ne y_i}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta)$ 求，所以梯度中会出现判别式
- 对正确分类的梯度：
  - $\bigtriangledown_{w_{y_i}}L_i = -\left(\sum_{j \ne y_i } 1(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) \right) x_i$
  - 注意：需要求和( $y_i$ 是同一个)
  - 若正确分类，则判别式中 > 0 不满足，因此该项梯度为 0
  - 若分类错误，则判别式中 > 0 满足，因此该项梯度为 $x_i$
- 对错误分类的梯度：
  - $\bigtriangledown_{w_j}L_i = 1(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) x_i$
  - 注意：不用求和(每一个 $j$ 都不是同一个)
  - 若正确分类，则判别式中 > 0 不满足，因此该项梯度为 0
  - 若分类错误，则判别式中 > 0 满足，因此该项梯度为 $x_i$

对应求梯度和loss的代码部分，在计算梯度和loss的时候只需要考虑分类错误所带来的影响，因为分类正确时，对loss和梯度的贡献都是0。

    dW = np.zeros(W.shape) # 初始化梯度矩阵为0# compute the loss and the gradientnum_classes = W.shape[1] #类别个数num_train = X.shape[0] #训练数据个数loss = 0.0for i in range(num_train):scores = X[i].dot(W) #一个输入的所有类得分 , W:D-by-C , 每一列评判一个类的得分correct_class_score = scores[y[i]] #y[i]对应这条数据的真实label , 得到真实label的得分for j in range(num_classes):if j == y[i]: #continuemargin = scores[j] - correct_class_score + 1 #分类不正确 #正确分类得分比不正确的至少大1，代表分类正确if margin > 0: # max(0,--)操作 ，若正确类别的得分没有比错误类别得分大 1loss += margindW[:,y[i]] += -X[i] #对应正确分类的梯度 , 结合上面梯度推导很容易明白dW[:,j] += X[i] #对应不正确分类的梯度 , 结合上面梯度推导很容易明白

代码补充svm_loss_naive

只是计算平均梯度并加上正则项

    # 计算平均梯度并加上正则项dW /= num_traindW += reg * W

代码补充svm_loss_vectorized部分

首先计算loss

    scores = np.dot(X,W) #计算出所有的得分 (N , C)大小的矩阵num_train = X.shape[0]correct_class_score = scores[np.arange(num_train),y] #找到所有正确类别的得分 , 1-by-Ncorrect_class_score = np.reshape(correct_class_score,(num_train,-1)) # N-by-1,为下面相减做准备margins = np.maximum(0, scores - correct_class_score + 1)margins[np.arange(num_train),y] = 0 #正确分类自己的 loss 为 0loss += np.sum(margins) / num_trainloss += reg * np.sum(W * W)

需要注意的是
- 找到所有正确分类的得分，是个行向量，我们要将其转化为列向量，这样在与矩阵相减时才能保证对应列相减，因为scores中的每一行是一个数据的所有类别的得分
- 在margins的计算过程中，要注意，正确分类对loss的贡献为0

计算梯度

    margins[margins > 0] = 1 #将所有大于0的项置1row_sum = np.sum(margins,axis=1) margins[np.arange(num_train),y] = -row_sumdW = np.dot(X.T,margins) #X:N-by-D , margins:N-by-C , dW:D-by-C , C代表的是类别个数 , D代表每个类的参数个数#margins中第i行的数代表第i个训练数据对梯度的贡献量dW /= num_traindW += reg * W

首先将margins中大于0的项置1，因为所有未正确分类的数据都会对dW[:,y[i]]有多次影响

参照

 if margin > 0: # max(0,--)操作 ，若正确类别的得分没有比错误类别得分大 1loss += margindW[:,y[i]] += -X[i] #对应正确分类的梯度 , 结合上面梯度推导很容易明白dW[:,j] += X[i] #对应不正确分类的梯度 , 结合上面梯度推导很容易明

从每个margin > 0 ，正确分类的梯度都要减去X[i] , 因此有
```
margins[np.arange(num_train),y] = -row_sum
```
对未正确分类的梯度来说，只需要加上X[i] 即可

关键的部分在于

dW = np.dot(X.T,margins) #X:N-by-D , margins:N-by-C , dW:D-by-C , C代表的是类别个数 , D代表每个类的参数个数#margins中第i行的数代表第i个训练数据对梯度的贡献量

当X.T与margins相乘时，可以将margins中的数看成贡献量
若margins[i] [j] = k , 则dW[:,j] += k * X[i] , 这个式子是向量化计算的核心

调参（交叉验证）

就是简单的遍历 + 训练 + 预测，得到最好的参数
结果：best validation accuracy achieved during cross-validation: 0.398000
linear SVM on raw pixels final test set accuracy: 0.377000

for learning_rate in learning_rates:for regularization_strength in regularization_strengths:svm = LinearSVM()loss_hist = svm.train(X_train, y_train, learning_rate=learning_rate, reg=regularization_strength,num_iters=1500, verbose=True)#训练模型y_train_pred = svm.predict(X_train)#预测训练集y_val_pred = svm.predict(X_val)#预测验证集y_train_acc = np.mean(y_train_pred==y_train)y_val_acc = np.mean(y_val_pred==y_val)results[(learning_rate,regularization_strength)] = [y_train_acc, y_val_acc] #得到一组参数对应的结果if y_val_acc > best_val:#更新best_val = y_val_accbest_svm = svm

softmax

首先，推导softmax loss function对w的梯度

Softmax 公式： $S_i = \frac{e^ {f_{y_i}}}{\sum_je^ {f_j} }$
Softmax Loss 公式： $L_i = -\log \frac{e^ {f_{y_i}}}{\sum_je^ {f_{j}} }$ , $f_j = X(i)W(j)$ ，若 $f_{y_i}$ 的得分越高，则其所占总得分比例越大， $L_i$ 越小
梯度
- 对每一个 X[i] 来说，可能对分类器判断所有类别的参数都有贡献，需要对所有的 $W (j) 求导$
- $\frac{\partial L_i}{\partial W_j} = \frac{\partial L_i}{\partial f_j}\frac{\partial f_j}{\partial W_j}$ , 可见，当求导链式法则第一项时，分子下标为 i ，分母下标为 j ，因此分为 $i = j$ 和 $\ne j$ 来求导第一项
  - i = j
    - $\frac{\partial L_i}{\partial f_j} = -\frac{\sum_{j}^{} }{e^{f_{y_i}}} \frac{e^{f_{y_i}}\sum_{j}-e^{f_{y_i}}e^{f_j}}{ {\sum_{j}}^2} =\frac{e^{f_j} - \sum_j }{\sum_{j} }$
  - $\ne j$
    - $\frac{\partial L_i}{\partial f_j} = -\frac{\sum_{j}^{} }{e^{f_{y_i}}} \frac{-e^{f_{y_i}}e^{f_j}}{ {\sum_{j}}^2} =\frac{e^{f_j}}{\sum_{j} }$
- 易知： $\frac{\partial f_j}{\partial W_j} = \frac{\partial X_iW_j}{\partial W_j} = X_i$
- 综上：
  - i = j
    - $\frac{\partial L_i}{\partial W_j} = \frac{e^{f_j} - \sum_j }{\sum_{j} }X_i = (S_j - 1)X_i$
  - $\ne j$
    - $\frac{\partial L_i}{\partial W_j} = \frac{e^{f_j}}{\sum_{j} }X_i = S_jX_i$

代码补充softmax_loss_naive

    num_classes = W.shape[1]num_train = X.shape[0]for i in xrange(num_train):scores = X[i].dot(W) #(1,C)shift_scores = scores - max(scores) #保持数据稳定性 ， 防止exp过大loss += (-shift_scores[y[i]] + np.log(sum(np.exp(shift_scores))) )for j in xrange(num_classes):softmax_output = np.exp(shift_scores[j])/sum(np.exp(shift_scores))if j == y[i]:dW[:,j] += (-1 + softmax_output) *X[i] else: dW[:,j] += softmax_output *X[i] loss /= num_train loss +=  0.5* reg * np.sum(W * W)dW = dW/num_train + reg* W

首先通过X[i]对W的一个点积，得到所有训练数据的所有类别的得分
所有数据的得分减去这个数据所有类别得分中的最大值，以保证得分较小，防止在exp时溢出
得到loss
在梯度中可以清晰地看到
- i = j
  - $\frac{\partial L_i}{\partial W_j} = \frac{e^{f_j} - \sum_j }{\sum_{j} }X_i = (S_j - 1)X_i$
- $\ne j$
  - $\frac{\partial L_i}{\partial W_j} = \frac{e^{f_j}}{\sum_{j} }X_i = S_jX_i$
- 这里的 S 就是softmax_output , 也就是经过softmax之后的得分

代码补充softmax_loss_vectorized

    num_classes = W.shape[1]num_train = X.shape[0]scores = X.dot(W) #N-by-Cshift_scores = scores - np.max(scores, axis = 1, keepdims = True)# 每一项都用softmax公式转成概率softmax_output = np.exp(shift_scores)/np.sum(np.exp(shift_scores), axis = 1, keepdims = True) loss = -np.sum(np.log(softmax_output[range(num_train), list(y)]))loss = loss / num_train + 0.5* reg * np.sum(W * W)dscores = softmax_output.copy()#这个矩阵乘法和SVM的一样，只是参数不一样#X.T : D-by-N dscores : N-by-C#N个输入中的每一个都会对dW的整个矩阵有贡献 ，对X[i]来说，若当前 j = y[i] ， 则贡献量为softmax_output[i][y[i]] - 1#否则为 softmax_output[i][y[i]] ，即不用修改softmax_output矩阵dscores[range(num_train), y] += -1 #dscores的第i行代表 X[i] 对整个分类器的贡献量dW = (X.T).dot(dscores)dW = dW/num_train + reg* W

可以说，上述过程和 SVM 的向量化计算非常类似，只是loss和梯度的计算方式发生了改变，其原理都是一样的
loss很容易算出
要注意的是，这里的dscores中的元素也可以当做贡献量来看
- dscores[i] [j] = k ，则 dW[:,j] += X[i]
- 而k ，也就是X[i] 前面的系数，只有 -1 和不 -1 之分，这点可以通过梯度的计算公式得到

调参（交叉验证）

这里的交叉验证也和SVM类似，不再多说
结果：best validation accuracy achieved during cross-validation: 0.358000
softmax on raw pixels final test set accuracy: 0.361000

for reg in regularization_strengths:for lr in learning_rates:svm = Softmax()loss_hist = svm.train(X_train, y_train, lr, reg, num_iters=1500)y_train_pred = svm.predict(X_train)train_accuracy = np.mean(y_train == y_train_pred)y_val_pred = svm.predict(X_val)val_accuracy = np.mean(y_val == y_val_pred)if val_accuracy > best_val:best_val = val_accuracybest_softmax = svm           results[(lr,reg)] = train_accuracy, val_accuracy

three_layer_net

代码补充 loss

h1 = np.dot(X , W1) + b1
first_layer = np.maximum(0 , h1) #第一层全连接层 + ReLu: N-by-D * D-by-H + H-by-1 -> N-by-H h2 = np.dot(first_layer , W2) + b2
second_layer = np.maximum(0 , h2) # N-by-Hscores = np.dot(second_layer , W3) + b3 #最后一个全连接层的输出 N-by-C

这里需要注意的就是，层与层之间的维度关系不要乱

#softmax
shift_scores = scores - np.max(scores, axis = 1, keepdims = True)
softmax_output = np.exp(shift_scores)/np.sum(np.exp(shift_scores), axis = 1, keepdims = True) 
loss = -np.sum(np.log(softmax_output[range(N), y]))
loss = loss / N + 0.5 * reg * np.sum(W1 * W1) +  0.5 * reg * np.sum(W2 * W2) + 0.5 * reg * np.sum(W3 * W3)

这里的 loss 就是一个softmax的过程，和前面softmax一模一样，只不过多加了几个正则项

dscores = softmax_output
dscores[range(N),y] -= 1
grads['W3'] = np.dot(second_layer.T,dscores) / N + reg * W3
grads['b3'] = np.sum(dscores,axis=0,keepdims=False) / N #b 和 W 一样 ， 只不过不用乘以X[i] , 因为b的前面没有参数mask = np.zeros_like(h2)
mask[h2>0] = 1 # ReLu中大于0的部分
#print(da2_dz2.shape)
delta2 = np.dot(dscores , W3.T) * mask #链式法则，前面求的是score对second_layer的导数，再乘以dscore(tot_loss对score的导数)
grads['W2'] = first_layer.T.dot(delta2) / N + reg * W2
grads['b2'] = np.ones(N).dot(delta2) / Nmask2 = np.zeros_like(h1)
mask2[h1>0] = 1
delta1 = np.dot(delta2 , W2.T) * mask2
grads['W1'] = X.T.dot(delta1) / N + reg * W1
grads['b1'] = np.ones(N).dot(delta1) / N

这里就需要注意了
- 第三层
  - dscores 的本质：是tot_loss 对 score 的梯度
  - 在求解W3的梯度时，其实就是softmax中对W3的梯度，求的是 tot_loss 对 W3 的导数
  - 在求解b3的梯度时，其实和W3一样，只是没有了X[i]作为系数，因为b的前面没有参数
- 第二层
  - 根据链式法则，tot_loss 对第二层 + ReLu 之后的数据second_layer的导数，应该是tot_loss对scores的梯度 * scores对second_layer的梯度
  - second_layer就是 W3*X + b3 中的 X ，也就是第三层的输入，因此scores对second_layer的导数就是 $W_3^T$
  - ReLu将小于0的值，归成了0 ，大于 0 的为 x
    - 因此second_layer 对 ReLu之前的数据 h2 的导数为， 0 或 1
    - h2 对 W2 的梯度为 $first\_layer^T$
  - 所以就有了这部分，这部分就是链式法则的运用
```
mask = np.zeros_like(h2)
mask[h2>0] = 1 # ReLu中大于0的部分
#print(da2_dz2.shape)
delta2 = np.dot(dscores , W3.T) * mask #链式法则，前面求的是score对second_layer的导数，再乘以dscore(tot_loss对score的导数)
```
- 第一层
  - 从第二层到第一层和从第三层到第二层一样，直接重复上述操作即可

代码补充train

# 选择训练集
batch_inx = np.random.choice(num_train, batch_size)
X_batch = X[batch_inx,:]
y_batch = y[batch_inx]

self.params['W1'] -= learning_rate * grads['W1']
self.params['b1'] -= learning_rate * grads['b1']
self.params['W2'] -= learning_rate * grads['W2']
self.params['b2'] -= learning_rate * grads['b2']
self.params['W3'] -= learning_rate * grads['W3']
self.params['b3'] -= learning_rate * grads['b3']

选择训练集和参数迭代

代码补充predict

scores = self.loss(X)
y_pred = np.argmax(scores, axis=1)

选得分最高的

调参（交叉验证）

结果：Test accuracy: 0.495

best_acc = 0
learning_rate = [1e-4, 5e-3, 1e-3,1e-2]
#regulations = [0.2, 0.25, 0.3, 0.35]
regulations = [1e-4, 5e-4, 1e-3, 4e-3,1e-2]
for lr in learning_rate:for reg in regulations:stats = net.train(X_train, y_train, X_val, y_val,num_iters=2500, batch_size=150,learning_rate=lr, learning_rate_decay=0.95,reg=reg, verbose=True)val_acc = (net.predict(X_val) == y_val).mean()if val_acc > best_acc:best_acc = val_accbest_net = netprint('lr = ',lr ,' reg = ',reg, ' acc = ', best_acc)

features

不在图像的原始像素上运用分类器，而是先从原始数据上计算好一些特征，再对这些特征运用分类器
主要有两个特征提取器
- hog_feature 注重texture
- color_histogram_hsv注重颜色

SVM

结果：best validation accuracy achieved during cross-validation: 0.420000

for lr in learning_rates:for reg_str in regularization_strengths:svm = LinearSVM()loss_hist = svm.train(X_train_feats, y_train, learning_rate=lr, reg=reg_str,num_iters=1500, verbose=False)y_train_pred = svm.predict(X_train_feats)accuracy_train = np.mean(y_train == y_train_pred)y_val_pred = svm.predict(X_val_feats)accuracy_val = np.mean(y_val == y_val_pred)results[(lr, reg_str)] = (accuracy_train, accuracy_val) if accuracy_val > best_val:print ("lr:",lr)print ("reg:", reg_str)best_val = accuracy_valbest_svm = svm

ThreeLayerNet

结果：lr = 1 reg = 1e-05 acc = 0.558
test_acc：0.551

调参得到较优的参数为 learning_rat = 1 , reg_choice = 1e-5 , num_iters = 10000

best_acc = -1
input_size = 32 * 32 * 3#learning_rate_choice = [1e-4, 5e-3, 1e-3,1e-2,1e-1,1e-5,1e-6]
#reg_choice = [1e-4, 5e-4, 1e-3, 4e-3,1e-2,1e-1,1,10,1e-5]
learning_rate_choice  =  [1e-2 , 1e-1 , 1]
reg_choice =  [1e-5 , 1e-4 , 1e-3 , 1e-2 , 1e-1]for learning_rate_curr in learning_rate_choice:for reg_cur in reg_choice:    net = ThreeLayerNet(input_dim, hidden_dim, num_classes)stats = net.train(X_train_feats, y_train, X_val_feats, y_val,num_iters=10000, batch_size=150,learning_rate=learning_rate_curr, learning_rate_decay=0.95,reg=reg_cur, verbose=True)val_acc = (net.predict(X_val_feats) == y_val).mean()if val_acc>best_acc:best_acc = val_accbest_net = netbest_stats = statsprint('lr = ',learning_rate_curr ,' reg = ',reg_cur, ' acc = ', best_acc)

结论分析与体会

通过本次实验，自己推导了SVM loss function 对 W 和 b 的梯度公式，对SVM loss function 有了深入的了解
通过本次实验，自己推导了SoftMax loss function 对 W 和 b 的梯度公式，对SoftMax loss function 有了深入的了解
通过本次实验，手动构建了三层神经网络，直观体会了每一层的 Input 和 W ，b ， Output 的关系，特别是维度之间的联系
手动推导了多层神经网络的链式法则
手动进行了bp过程
手动进行了调参（有点玄学）
这种通过在有基本框架的基础上补全代码的实验形式，能让我们学到很多东西，就是比较费时间

实验过程中遇到的问题和解决方法

实验过程中遇到的主要问题就是不会求梯度，一开始无从下手
- 因为先做的 $S V M$ ，在 $S V M$ 中遇到求梯度的问题，去搜博客，然后手推并总结
- 在做完 $S V M$ 去做 $S o f t M a x$ 时，仿照 $S V M$ 的思想，直接手推就好了
在做三层神经网络的时候，遇到了这个问题 , 不理解这个内积是干什么用的，在求对第二层的导数的时候，为什么用的都是第三层的量
```
delta2 = np.dot(dscores , W3.T) * mask
```
- 后面通过与同学讨论，了解到这一步就是链式法则
- 然后再了解了这一步是链式法则的基础上，想明白了第二层 + ReLu的输出就是第三层的输入 $X_3$ 那 $d s c o r e s$ 是 $tot_loss$ 对scores的梯度， $scores = X_3W_3 + b_3$ , 这里出现 $W_3$ 刚好是scores对 $X_3$ 的导数，这就搞明白了每一层的梯度和链式法则