Recall from last lecture

上一节课介绍了几个重要的问题：

图片识别的困难与挑战
数据驱动的方法：kNN
线性分类器：评分函数(score function)和权重矩阵W。

但是从上节课例子中还有两个问题需要解决：

不同的权重在不同图片上的作用效果差别很大，可能理想可能糟糕，需要找到一个清晰的概念来定义这个好坏。
需要尽量中道找到一些权重W对所有识别的类别相一致

这节课两个重要任务：

定义Loss Function来衡量我们对结果的不满意程度
最小化Loss Fuction找到合适的参数

Loss Function

损失函数（Loss Function）（有时也叫代价函数Cost Function或目标函数Objective）当评分函数输出结果与真实结果之间差异越大，损失函数输出越大，反之越小。

Multiclass Support Vector Machine Loss

简单来说，SVM的损失函数计算了每个图片的所有不正确的类别。其中x_i是图片，y_i是图片的标签。将所有不正确的类别的评分与正确类别的评分之差加上1，讲得到的值与0做比较，取两者中的最大值，然后将所有的取值进行求和。

这样计算loss的公式也叫Hinge loss，如下图所示：

对此的理解就是，不仅要使正确类别的评分高于错误类别的评分，还要加上一个安全系数，这里系数值为 1。对于1这个数字某种程度上可以认为是一个随意的选择，因为score是可以随意成比例放大缩小的，大小与量度的选择相关。

在完成对数据集中每一个图片的计算之后，再对它们求均值，就得到了整个数据集上的Loss function。下图是一个简单例子，可以更好的理解计算过程。

对于第一个图片来说，正确cat的分数是3.2，则其他两个分数最大值不能超过2.2，所以对于car来说5.1-2.9=2.2，而frog的-1.7远低于2.2，则为0，求和后结果为2.9；而对于第二个4.9-1=3.9远高于另外两个，所以loss为0；对第三个图片，可以看出正确的frog类分数很低，其他类都比他要高，这个结果就是很糟糕的。

loss function的numpy向量化实现

def L_i_vectorized(x, y, W):
    # x是一维行向量，y是整数表示标签，W权重矩阵
    scores = W.dot(x)
    margins = np.maximum(0, scores - scores[y] + 1)
    margins[y] = 0 # 清除j=y_i的情况
    loss_i = np.sum(margins)
    return loss_i

下面是几个小的问题及回答

Q1: What if the sum was over all classes?(including j = y_i)

如果对于所有类别计算而不只是不正确的类别，对于 j = y_i时，loss恒等于1，求和后再求均值，相当于在最终结果上多加了一个1，不影响最终判断的。

Q2: What if we used mean instead of sum?

如果用的是均值，最终结果的绝对值会变小，相当于缩小了种类数的倍数，也不影响最终判断。

Q3: What if we used square loss?

上述两个问题相当于对L进行了平移和缩放的线性运算，而这个问题就是非线性的变化，对结果还是会有影响的。平方的loss被称为square hinge loss，有一些时候会用到，而且表现比hinge loss要好，但是hinge loss还是最常用的。

Q4: what is the min/max possible loss?

min: 0, max: ∞

Q5: At initialization W is small so all s ≈ 0. What is the loss?

种类数-1，因为 s ≈ 0 所有的分数都是零，所以loss都为1，求和后求均值就等于种类数-1。这个特性在具体实现时可以用来验证loss function的正确性。

Q6: Suppose that we found a W such that L = 0. Is this W unique?

对于L=0的情况来说，W并非唯一，以一个系数来缩放W，比如2W，也可以满足L=0。这也是一个bug。

Regularization

对于损失函数来说，我们希望它尽量满足训练集，这时候就会出现过拟合的情况。如下图所示，蓝色的线是满足原本数据集时的最佳拟合，但是对新的数据（绿色）并不适用，所以绿的线泛化能力更好。

所以我们加入了λR(W)这一项，让模型更简单，R(W)衡量了W的好坏，我们不仅想要数据拟合的好，也希望优化W，所以λ加入让他们fight，来获得更好的结果。

λR(W)就是我们的正则化(Regularization)，用于权衡训练损失和用于测试集后的泛化损失。

对于R(W)的选择有以下几种：

其中L2最常见，在L2 regularization下，W全是0时结果最好，但是当然是不可能的，因为W全为0就不能分类了，所以就需要与前面进行均衡。

假设下图中w1,w2的loss function一致，w2要比w1好，因为w2考虑到了x中的大部分元素，分散了计算而w1完全忽略的后三个元素输入。这时L2 regularization的优点就体现出来了。

另外L1后面可能会用到，它对于稀疏的W矩阵效果很好。

Softmax Classifier

Softmax classifier即为多元逻辑回归(Multinomial Logistic Regression)，是逻辑回归的多维推广。

在Softmax classifier中，我们不把分数理解为某种边界，而是对应不同类未经标准化的对数概率。正确分类概率的对数更高，错误的、负的结果就会很低。下图是一个计算过程

Q1: What is the min/max possible loss L_i?

min:0 如果完全正确，概率为1，取对数为0；

max:-∞ 如果不正确，概率为0，取对数为∞

Q2: Usually at initialization W is small so all s ≈ 0. What is the loss?

0 —>exp(0) = 1 —> 1/n —>对数取负值。

同样的它也可以起到一个验证的作用，经过优化后的损失值应该在整个初始值到0之前，如果不在就有可能出错了。

Comparison

相同点：除了计算稍有不同外，函数的定义几乎一样，目的也是一样的。两种形式的计算花费时间也是几乎相同的，softmax可能计算会稍多，但如果用同样的网络，这些计算对于卷积来说不值一提。

不同点： SVM的稳定性更高，因为margin的存在，所以损失值更为稳定。但是对于softmax，任何一个测试例都能提升分类的性能，因为softmax对于每一个样本都有关注，只要有一点变动，就会改变损失值

Optimization

我们已经定义了loss function现在要做的就是寻找最佳的W。

第一种策略就是随机测试。随机取一些W的采样，计算他们的损失值，然后重复这些步骤直到找到一个W的值使得损失值最小。这显然不是一个很好的方法。

第二种策略是把损失值看作是在一个高维度的W空间中。形象的讲，找到最小的损失值相当于下山，你看不到山谷，但是知道每一点的高度，可以试图找到找到一个更低的损失值，然后一步一步到达山谷。这种方法我们叫做梯度下降(Gradient Descent)。

Gradient Descent

梯度(Gradient)就是计算当前点的每个方向上的斜率(slope)。如果斜率为负，就沿着这个方向往下走。

对于一维的斜率计算可以用下面的公式来求导数，而对于多维就是对每一个维度的偏导数组成的向量。这种计算叫做数值梯度(Numerical gradient)，这种方法容易用代码实现，但是比较慢和粗略。这样对每一个单独的维度计算的方法是比较蠢的，如果有成百上千个参数时，每迈出一步就要花费很多时间。

实际上L是关于W的一个函数，我可以用微积分计算它的梯度，这叫做统计梯度(Analytic gradient)，这种方法更精确也更迅速，但是容错性不好。实践时，我们会用微积分来计算梯度值，同时写一段代码来计算数值梯度来进行验证，这叫做梯度验证(gradient check)。

在实际操作中，虽然我们拥有完整的数据集，但是只是从训练集中取样一批，如下面的代码，这种方法叫做批量梯度下降法(Mini-batch Gradient Descent)，样本的个数通常为32/64/128个样本。这里有一个链接详细了介绍了这种方法与BGD/SGD的区别。

while True:
  data_batch = sample_training_data(data, 256)# sample 256 examples
  weights_grad = evaluate_gradient(loss_func, data, weights)
  weights += step_size * weights_grad # perform parameter update

这样做的优点是提高了运算速度，可以迭代更多次；缺点是因为只取了一小部分样本计算梯度所以比较多噪声存在。下图是实现中的loss曲线，可以看出噪声很多，但是总体上是一个明显的下降趋势。如果是用整个数据集的话，就不会有这些噪声而是一个平滑的下降曲线。

这里步长(step_size)也叫学习速率(learning rate)，是梯度下降中十分重要的超参数，如果过小下降速率太慢，过大时则会来回震荡。

下图是不同学习速率在损失函数上的影响

学习速率是指每一个循环中移动的大小。总的来说，如果学习速率太高或者每一步走的太远，那么一开始损失函数值会在空间内来回乱窜，之后损失函数不会收敛甚至会越来越大。如果用一个很低的速率的话，那么更新的速率会很慢，最终收敛会需要很长时间。而如果用一个比较高的学习速率，最终也很收敛，但是会卡在一个较高的位置，也就是没有达到最低，有可能进入局部最小值。所以实践中一般会选一个高的然后一点点降低这个学习速率。

此外，对于W的初始值选择也是比较重要的。如果非常注意选取初始值的话，那么损失函数的下降速度就会很小，因为初始损失值会比较小。但是如果使用了一个明显不正确的初始值的话，那么优化的过程中，损失函数就会在开始的时候有一个很明显的下降趋势。

Image Features

很明显我们不能把线性分类器直接应用到一张没有经过任何处理的图片上去，因为线性分类器没办法解决像素问题。所以常见的做法是计算图片的不同特征，然后计算不同特征的描述，最终通过统计来理解图片是什么。对于机器来说，我们相当于把图片转换成一个巨大的向量，然后把向量放入线性分类器。

简单的例子把图片的颜色特征看成一个颜色分布的直方图，把整个图片的pixels颜色数据放到这个直方图中，然后通过直方图中某个颜色的数值就能得到这张图中相应颜色的数量，图片颜色的统计一个feature。

HOG/SIFT 不同物体之间的边缘方向来做分类，把不同方向的边缘用直方图做一个总结，统计一下这张图片上不同方向的边缘有多少，最后通过这个边缘数量的统计来得出图中有什么东西。

pipline：首先我们的程序要看到图片上不同的点，描述出在一个个小块上我们看到了什么，比如某个元素的频率，颜色等特征，然后我们用这些数据形成一种“字典”，最终我们得到的结果是一个在图上各种东西出现次数的k均值。接下来就是计算这个特征向量，把计算结果放到线性分类器中去。

因此实际上我们拿到图片需要进行一步特征提取，在这一步我们决定了对于不同内容的图片什么东西比较重要，也决定了什么是分类器比较感兴趣的特征。而cnn就是把每种特征做成一个函数，然后无需人工提取特征，机器直接从像素开始训练，这样更高。