前言

本文旨在学习和记录，如需转载，请附出处https://www.jianshu.com/p/e1edb629eab2

Linear classification

在cs231n的第一节实验中采取的是KNN分类算法，但是KNN算法有两个缺点

1. 分类器必须记住并所有的训练样本，存储空间会很大如果数据量大的话；
2. 测试时需要跟所有的训练样本进行对比（当然例如KD树的策略可以提高搜索效率）
   线性分类器是DNN和CNN的前身，将原始图像点线性变换到label space中，给定得分函数和损失函数进行学习，训练好一个映射函数:initial image space到label space。

其映射函数可以写为：

其中每个样本的维度为, W的维度为,b的维度为。其中D为原始数据的特征数目，K为类别数目。

特点

1. 是有效的，可以并行的产生K类分类器，其中W矩阵的每一行就是每个分类器；
2. 样本是固定的，学习过程是有监督的，需要学习确保正确类别的得分比其他类别的得分要高；

3. 线性分类器的优点在于采用训练数据训练的模型，我们只需要存储W和b的参数。这样在测试时用训练好的参数进行简单的线性变换即可预测，在测试时间上比KNN要快很多，而且模型占用的空间相对也很小；

   
   image.png

损失函数

在线性分类器中最重要的是损失函数，它用来量化预测标签和真实标签的一致性，一般损失函数是可导的，因为在学习过程中都是基于反向传播，梯度更新。

SVM

这里的SVM损失是Multiclass Support Vector Machine，期望在正确类别的得分比其他类别的得分都要高一个，不然这样预测就不够准。
其损失函数为：

如果一个样本的正确类别点的得分比所有其他类的得分都要高，则该样本的损失就为0

cs231n课件截图.png
code

def svm_loss_vectorized(W, X, y, reg):
    """
    Structured SVM loss function, vectorized implementation.

    Inputs and outputs are the same as svm_loss_naive.
     - W: A numpy array of shape (D, C) containing weights.
    - X: A numpy array of shape (N, D) containing a minibatch of data.
    - y: A numpy array of shape (N,) containing training labels; y[i] = c means
      that X[i] has label c, where 0 <= c < C.
    - reg: (float) regularization strength
    """
    loss = 0.0
    dW = np.zeros(W.shape) # initialize the gradient as zero

    num_classes = W.shape[1]
    num_train = X.shape[0]
    scores = np.dot(X,W)#linear multiply
    scores_correct = scores[np.arange(num_train), y] # find correct score
    scores_correct = scores_correct.reshape(num_train,-1)
    margins = scores-scores_correct+1# 1 is delta
    
    margins = np.maximum(0,margins)
    margins[np.arange(num_train), y] = 0
    
    loss += np.sum(margins) / num_train# loss项
    loss += 0.5 * reg * np.sum(W * W)
    # grad
    margins[margins>0] = 1
    row_sum = np.sum(margins,axis=1);#按行计算有多少loss为正的地方
    margins[np.arange(num_train),y] = -row_sum# 这部分需要减去
    
    dW += np.dot(X.T,margins)/num_train+reg*W
    
    return loss, dW

交叉熵损失

交叉熵损失一般都利用了softmax分类器，softmax的公式为

即将线性输出的得分函数转换成概率的形式。然后利用softmax的输出概率跟真实的概率输出进行交叉熵计算。


其中q代表softmax的输出概率，p代表真实标签的hot向量，如果属于真实类别的概率越大的话（最大为1），其损失就会越小，在交叉熵计算时，只计算了真实类别输出的概率值。

cs231n课件截图.png
code

def softmax_loss_vectorized(W, X, y, reg):
    """
    Softmax loss function, vectorized version.

    Inputs and outputs are the same as softmax_loss_naive.
    """
    # Initialize the loss and gradient to zero.
    loss = 0.0
    dW = np.zeros_like(W)
    num_train = X.shape[0]
    num_classes = W.shape[1]
    
    scores = X.dot(W)
    scores = scores- np.max(scores, axis=1,keepdims=True)#防止数值溢出
    p = np.exp(scores)/np.sum(np.exp(scores),axis =1,keepdims=True)
    loss += np.sum(-np.log(p[np.arange(num_train),y]))/num_train+0.5*np.sum(W*W)*reg
    
    p[np.arange(num_train),y] -= 1
    dW = np.dot(X.T,p)
    dW = dW/num_train + 0.5*reg*W

    return loss, dW

note

1. softmax函数在计算时需要考虑其数值上溢和下溢的线性
   下溢：接近0的数被四舍五入为0时发生下溢，比如，除以一个很小的数，四舍五入为0了，输出会出现NAN的可能；
   上溢：大量级的数被近似为或者，进一步的计算会导致这些无限值变为非数字。
   
   当所有的都为同一个常数时，理论上softmax输出都应该为1/n；但是，从数值计算上来说，如果该常数数量级太大的话，就会出现上溢的现象；反过来说，如果该常数是比较小的负数，经过指数函数之后就比较小，这个时候就出现下溢，意味着softmax的分母为0，所以最后的结果很可能是未定义的。
   解决方法：，然后计算softmax(z)。z的最大值为0，则不会出现上溢；另外，分母中也会有一个至少为1的项，不会出现分母下溢的现象。
2. 导数计算
   
   该损失函数其实只有针对correct label位置的损失，其他位置的损失都为0；则有
   
   根据dy的公式可以发现对正确label处的求导其实是p-1，其他位置求导的都是p，p为正向传播中的softmax输出。
3. 初始训练时交叉熵损失的近似值，由于刚开始训练时，其权重是随机给的，在没有正则化项时，最后计算出来的分类结果在类别上是平均分布的，所以其初始loss会接近于，该方法可以检测代码的准确性。

正则项

正则化的存在项是为了防止过拟合的产生，如果模型过于复杂，就像截图中的第三幅图一样，直观上高阶量的参数存在且比较大。正则项的存在是约束其参数的复杂程度。


L2正则化约束期望所有权重平方和尽可能的小；L1正则化约束期望有些权重趋近于0，有稀疏的作用。

Andrew Ng课件截图.png

总的损失函数

其中N为训练样本数，如果采用mini-batch训练则为batch的大小，为平衡训练loss和正则化损失的参数。

结果

#交叉验证
from cs231n.classifiers import Softmax
results = {}
best_val = -1
best_softmax = None
learning_rates = [1e-7, 5e-7]
regularization_strengths = [2.5e4, 5e4]
for rate in learning_rates:
    for reg_ in regularization_strengths:
        soft = Softmax()
        loss_hist = soft.train(X_train, y_train, learning_rate=rate, reg=reg_,
                      num_iters=1500, verbose=False)
        y_train_pred = soft.predict(X_train)
        
        acc_train = np.mean(y_train == y_train_pred)
        y_val_pred = soft.predict(X_val)
        acc_val = np.mean(y_val == y_val_pred)
        
        results[(rate, reg_)]=(acc_train, acc_val)
        if acc_val>best_val:
            best_val = acc_val
            best_softmax = soft       
# Print out results.
for lr, reg in sorted(results):
    train_accuracy, val_accuracy = results[(lr, reg)]
    print('lr %e reg %e train accuracy: %f val accuracy: %f' % (
                lr, reg, train_accuracy, val_accuracy))
    
print('best validation accuracy achieved during cross-validation: %f' % best_val)
lr 1.000000e-07 reg 2.500000e+04 train accuracy: 0.343531 val accuracy: 0.361000
lr 1.000000e-07 reg 5.000000e+04 train accuracy: 0.348714 val accuracy: 0.356000
lr 5.000000e-07 reg 2.500000e+04 train accuracy: 0.367592 val accuracy: 0.381000
lr 5.000000e-07 reg 5.000000e+04 train accuracy: 0.341878 val accuracy: 0.354000
best validation accuracy achieved during cross-validation: 0.381000
# evaluate on test set
# Evaluate the best softmax on test set
y_test_pred = best_softmax.predict(X_test)
test_accuracy = np.mean(y_test == y_test_pred)
print('softmax on raw pixels final test set accuracy: %f' % (test_accuracy, ))
softmax on raw pixels final test set accuracy: 0.370000

参考

1. cs231n linear classification