CS231 Computer vision

Image Classification pipline

课程第一章啥也没讲，第二章开始。以图片分类为主题，逐步引出KNN，线性分类等算法。图片数据使用CIFAR-10的数据，计算机扫描图片只能看到一个个像素点，如果是彩色图片，那就是一个三维图片矩阵，如果是黑白图片那就是二维。

CIFAR-10要求给出某张图片的分类，要求很简单，但是并不意外着做起来简单。首先是图片多角度的问题，一只猫也有不同角度的照片，这些照片能否全部识别成猫对于计算机来说是一个挑战。还有照片尺寸大小，或者是图片角色不同姿势等等。CIFAR-10数据集有十个种类，每一个种类提供50000训练数据和10000的测试数据。

KNN

这个算法老早前就实现过：Chapter 6:Similarity-Based Methods 这里只不过是简单提及一下而已，对于相似度算法，我觉得没有哪个老师讲的比林轩田老师的数据《learning from data》要好了，特别是KNN的理论推导方面还有模型演化写的很好。KNN算法属于半参数模型，这类模型没有训练过程，预测过程时间比一般的参数模型的时间要更多，相对于把训练模型的时间转移到了预测阶段。 事实上这种算法在图片识别上很少使用，预测效果并不好。KNN算法的关键就在于如何比较双方图片的差距了，比较差距的方法很多，在推荐系统中也学了不少，就是不知道能不能用上。KNN最主要的比较手段就是L1和L2距离：

d1(l1,l2) = \sum_{i=0}^n |l1-l2|

d2(l1,l2) =\sqrt {\sum_{i=0}^n (l1-l2)^2}

这两种距离有点像正则化的w1和w2，所以我一开始觉得区别应该就是能不能求导的问题，d1边界不平滑，难求导；而d2边界就是一个圆，可以求导。

课程还提到另一种区别，之前没有想到的。d1距离类似一个菱形，这里展示的是l1和l2的二维图，当坐标轴发生变化，转一个角度，那么d1距离就会发生变化，也就是说d1距离和坐标轴以及当前度量单位有关。而d2完全没有这种问题，怎么转都一样。有这样的区别自然适用情况也有差别，如果数据带有意义，比如预测升高，一个人的腿长，身长都是有具体意义的，那么最好使用d1，如果数据没有特别的意义，比如因子分解机分解出来的属性（推荐系统），这些属性数据可以人为给定意义，比如电影的剧情，喜剧程度等等，也可以不给，因为本身就没有意义，为了方便解释给定意义而已，那么久可以用d2。当然了，大多数情况最好还是两个都试一下。

代码测试,首先下载CIFAR-10的数据，然后处理一下：

def unpickle(file):
    import pickle
    with open(file, 'rb') as fo:
        dict = pickle.load(fo, encoding='bytes')
    return dict

返回的是一个字典，由于读出的二进制文件，在读取字典需要加d。

以k=1，d1距离为例实现算法，其他的只要改改就好了。

由这个最简单的NearestNeighbor可以演变成KNN，让其附近的K个数据点投票即可。对于k的选择其实是越多越好，但问题就在于k越多，计算量会指数增长，比如k=3到k=5，效益指数增加了百分之0.03（具体推导在learning from data中），计算量确打了不止一个级别，性价比太低。所以正常情况下还是选择k=3即可。

KNN算法根本不适合用于图像识别，首先是计算量的问题，KNN算法的好处在于其最坏分类的结果不会超过最后分类结果的2倍，具体推导在Chapter 6:Similarity-Based Methods

但是这是建立在数据点密集的情况下，数据是二维还好，数据要是三四五维，那得多少数据才能填满这些空间。其次就是图片相似度的问题，图片相似度未必能用d1，d2距离测量的准确，比如一张图片是汽车和大片天空，另一张图片也是马和大片天空，这两张图片角色不同，但是天空占大多数，所这两张图片会归为一类，自然是不对的。

Validation sets for Hyperparameter tuning

课程提到的最后一个问题是选择超参数的问题，KNN算法的k参数需要在训练前指定，问题来了，然后测定K值？课程上老师专门提了一句：we cannot use the test set for the purpose of tweaking hyperparameters，不能动用测试数据来测定超参数。在选择算法训练数据的时候，务必要把测试数据当成是一种很珍贵的资源，不到最后不能使用。 有一种看似合理的做法，把数据集分成两份，一份训练数据，一份测试数据，用每一个k和训练数据来训练模型，然后放到测试数据里面选择最好的。这样看起来好像是合理的，但是test集合未必就能代表所有的样本了，所有有可能只选择了适合在当前样本的数据而已，这样也是不可取的。

另一钟更常见的做法是KFold交叉验证，这种做法在深度学习不常用，毕竟计算量太大了，但是对于机器学习来说不失为一种很好的做法。

代码GitHub：https://github.com/GreenArrow2017/MachineLearning/tree/master/CS231n

Loss Functions and Optimization

课程前面还有一点提到了线性分类器，就是函数

y = w^Tx+b

，课程特意介绍了一下对于b的作用，b可以用来调整类别数量上的不足。对于

w

的每一行上的每一个元素都会告诉我们对应图片的像素对分类有多少影响。 线性模型可以解释成是每一个种类学习的模板，图片的每一个像素都对应一个权重，告诉我们这个像素的影响有多大。还有一种高纬度的解释，线性分类器代表了高纬度空间的一个分类边界。 接下来的关键就是这么找到w。可以用一个函数作为w的输入，定量估计一下w的好坏，这个函数称为loss function。二元SVM的损失函数已经学习过，现在有十个类别，拓展到十个类别多元SVM。SVM使用hinge loss function，这种损失函数存在一个安全边界。这里multiSVM也是一样

S = \sum_{j != y_i}{max\{0,s_j-s_{y_i}+1\}}

给出的一就类似SVM二元里面的ξ，这里的ξ和SVM二元不一样，当

0<a_i<C

时，当前点就睡支持向量，这个时候ξ是0，如果

a_i=C

，那么ξ=0，当前点分类正确，并且这个点远离分类边界。当

a_i = C

，这个就不能确定了。但是在这里这些没有特别的意义，只是类比了SVM的hinge loss function而已。

如上例子，第二幅图片稍微修改一下4.9，score还是没有什么变化。课程还提了另外一个问题，loss function的值域是多少，这个就非常明显了，直接把hinge loss的图像画出来，。另外一个问题是，当模型初始化训练的时候，经常会出现Score分数之间都差不多的情况。这个时候再使用multiSVM的时候得到的loss是多少？当趋向于所有的score都是趋向0的时候，那么si-sj+1=1，所以，加起来就会得到类别的数量-1。这个结论可以在debug的时候测试一下代码是否正确。中间还有几个问题合页函数的平方有时候也会作为一个技巧，比如0.1的损失是可以不处理的，平方之后惩罚力度就更小了，如果是10平方之后惩罚力度更大了。个人感觉可能更好。

这个问题比较有意思，如果算出来的score是唯一的，w是不是唯一的？这个肯定不一定是唯一的，因为w放大缩小相同倍数也是可以得到的。

overfitting

接下来就是过拟合了，这些都是基础知识。如果模型只是一味的进行拟合，模型可能会很曲折。事实上我们关心的不是训练数据的表现，而是测试数据的表现。这个时候会用regularization来解决这个问题。

也就是奥卡姆剃刀原则。推导也很简单，模型简单其实就是w简单，w简单就是简单，也就是让即可，接下来就回到了拉格朗日乘子法了，target function在加上一个，C是常数去掉即可。这里的可以是其他的函数。至于为什么要限制w，因为在vc 维的推导中w的维度+1就是vc维的限制边界了，限制了w也即是限制了vc维也就限制了复杂度。

regularization

regularization有很多类型

L2 \quad regularzation:\sum{w^2} \\ L1 \quad regularzation:\sum{|w|} \\Elastic \quad net(w1 + w2):\sum{w^2+|w|}\\Max \quad norm \quad regularization :choose \quad the \quad MAX \quad one \\ Dropout

L2范式比较常用，L1范式可以使得w矩阵趋向于稀疏矩阵，和拉普拉斯有点关系，l1和l2意义有些相反。

softmax

除了multiSVM还有另外一种常见的多分类，softmax loss。

所以

接着思考几个问题，的上限和下限是什么，这个问题很好回答，既然是概率，最大最小就是0和1，自然就是infinity和0了。如果在正确类别上对softmax的正确分类上进行些许改变，softmax会有变化，而SVM不会有变化，因为SVM只要正确类别比错误类别高出一个delta即可，而softmax不会，无论高出多少，只要不是1就会一直叠加score朝一的方向进行。

picture feature

还有一个很重要的就是图片特征。前面还有一小节是讲optimization的，就是求导之类的，很基础。之前的特征都是直接把所有的像素都拉长了，直接传进分类器，但是这样做可能不太好。所以在拿到图片时，可以先计算图片的各个特征。在神经网络兴起前，常用的特征向量是方向梯度直方图，因为人们发现，有向边缘很重要

这样的图片可以看出包含了几种颜色，有哪些不同的类型边缘。

还有一种是词袋模型。如果得到了一句话，那么表示这句话的一个方法就是用单词出现在这句话的次数来表示。但是仅仅把文字类比于图片不太合理，所以需要我们自定义我们自己的单词表。首先把图片转换成各个像素，然后用Kmeans等等的聚类方法集合成簇，得到不同的簇中心

聚类完成之后会得到不同的颜色。

最后还有一些优化问题，对于multi-SVM，求导起来就非常简单了

按照这个公式进行梯度下降就好了。

def loss(x, y, reg, w):
    num_train = x.shape[0]
    score = x.dot(w)
    correct_score_class = score[range(num_train), list(y)].reshape(-1,1)
    margins = np.maximum(0, score - correct_score_class + delta)
    margins[range(num_train), list(y)] = 0
    loss = np.sum(margins) / num_train + 0.5 * reg * np.sum(w * w)

    num_classes = w.shape[1]
    gradient = np.zeros((num_train, num_classes))
    gradient[margins > 0] = 1
    gradient[range(num_train), list(y)] = 0
    gradient[range(num_train), list(y)] = -np.sum(gradient, axis=1)
    

    dw = (x.T).dot(gradient)
    dw = dw / num_train + reg * w
    return loss, dw

softmax也一样

S_i = -f_{y_i} + log\sum_i e^{f_i}

求导也要分两种情况，这算是很简单的情况了，SVM后面的smo算法求导真的写到爆肺。

#softmax multi-classification

def getLossAndDW(x, y, weight):
    LOSS = 0.0
    n = x.shape[0]
    score = x.dot(weight)
    correct_class = score[np.arange(n), y].reshape(n, 1)
    exp_sum = np.sum(np.exp(score), axis=1).reshape(n, 1)
    LOSS += np.sum(np.log(exp_sum) - correct_class)
    LOSS /= n
    LOSS += 0.5 * reg * np.sum(w ** 2)

    dweight = np.exp(score) / exp_sum
    dweight[range(n), list(y)] -= 1
    dweight = (x.T).dot(dweight) / n + reg * weight
    return LOSS, dweight

代码就很直接了。超参数什么的懒的选取了，反正训练步骤也就那样，垃圾电脑跑半天跑不出来，CIFAR数据前四份训练最后一份测试。

def train_softmax(weight, losses, acc,time=10):
    num_train = 200
    for k in range(time):
        for i in range(4):
            start = 0
            print("%d training data : " % (i + 1))
            for j in range(50):
                x = trainData[i][start:num_train + start]
                y = trainLabel[i][start:num_train + start]
                start += num_train
                loss, dw = getLossAndDW(x, y, weight)
                weight -= learning_rate * dw
                accr = predict(weight)
                if j % 5 == 0:
                   print("loss = ", loss, " ", accr)
                losses.append(loss)
                acc.append(accr)

训练了一万多次吧，每隔100次打一次数据，如果训练时间更长还会一直降，之前在谷歌云训练可以降到0.7多，这里最低才2.0，准确率最高可以跑到42%，现在就不花这么多时间，最高准确率33%。

assignment1还有神经网络的实现，之前都实现过，不过CS231居然给了模板，写完SVM和softmax才发现。