Higher-level representations, image features Optimization, stochastic gradient descent
导语：
在上一个部分我们介绍了在图像识别领域的两个重要部分：score function 和 loss function, SVM的公式如下：
$L = \frac{1}{N} \sum_i \sum_{j\neq y_i} \left[ \max(0, f(x_i; W)j - f(x_i; W){y_i} + 1) \right] + \alpha R(W)$
记下来我们来介绍最后一个部分，优化。优化是发现最优的W来最小化损失函数。
Hinge Loss简介：Hinge Loss是一种目标函数（或者说损失函数）的名称，有的时候又叫做max-margin objective。其最著名的应用是作为SVM的目标函数。
其二分类情况下，公式如下： $\begin{equation}
l(y)=max(0, 1-t\cdot y)
\end{equation}$
其中，y是预测值（-1到1之间），t为目标值（±1）。
其含义为，y的值在-1到1之间就可以了，并不鼓励|y|>1，即并不鼓励分类器过度自信，让某个可以正确分类的样本距离分割线的距离超过1并不会有任何奖励。从而使得分类器可以更专注整体的分类误差。
变种: 实际应用中，一方面很多时候我们的y的值域并不是[-1,1]，比如我们可能更希望y更接近于一个概率，即其值域最好是[0,1]。另一方面，很多时候我们希望训练的是两个样本之间的相似关系，而非样本的整体分类，所以很多时候我们会用下面的公式：
$\begin{equation}
l(y,y')=max(0, m-y+y')
\end{equation}$
其中，y是正样本的得分，y’是负样本的得分，m是margin（自己选一个数）
即我们希望正样本分数越高越好，负样本分数越低越好，但二者得分之差最多到m就足够了，差距增大并不会有任何奖励。
可视化：
通常损失函数都是高维空间的，使得他们很难可视化。然而，我们仍然可以得到一些直观感受通过将高维空间用切片的方式观察，比如我们可以产生一个随机的权重矩阵，然后沿着一条射线来记录损失函数的变化。
除此之外，您可能从其碗形外观中猜出，SVM成本函数是凸函数的一个例子有大量的文献专门用于有效地最小化这些类型的函数，您还可以选择斯坦福大学关于主题（凸优化）。一旦我们将我们的分数函数ff扩展到神经网络，我们的目标函数将变得非凸，并且上述可视化不会具有碗而是复杂而颠簸的地形。
不可微分的损失函数。作为技术说明，您还可以看到损失函数中的扭结（由于最大运算）在技术上使损失函数不可微分，因为在这些扭结中，渐变没有定义。然而，子梯度仍然存在并且通常被使用。在这个类中，可以使用术语“梯度”和“渐变”。
最优化
重申一下，损失函数可以让我们量化任何特定的权重集W的质量。优化的目的是找到最小化损失函数的W。我们现在将激励和缓慢地开发一种优化损失功能的方法。对于你以前的经验来看这个课程的人，这部分可能看起来很奇怪，因为我们将使用的工作示例（SVM损失）是一个凸起的问题，但请记住，我们的目标是最终优化神经网络，在那里我们不容易使用凸版优化文献中开发的任何工具。
策略一 最差的解决方案是随机搜索
由于很容易检验W的好坏，所以第一个解决方案就是随机的搜索。代码如下：
# assume X_train is the data where each column is an example (e.g. 3073 x 50,000)
# assume Y_train are the labels (e.g. 1D array of 50,000)
# assume the function L evaluates the loss function
bestloss = float("inf") # Python assigns the highest possible float value
for num in xrange(1000):
W = np.random.randn(10, 3073) * 0.0001 # generate random parameters
loss = L(X_train, Y_train, W) # get the loss over the entire training set
if loss < bestloss: # keep track of the best solution
bestloss = loss
bestW = W
print 'in attempt %d the loss was %f, best %f' % (num, loss, bestloss)
核心思想：迭代细化。当然，事实证明，我们可以做得更好。核心思想是找到最好的权重集W是一个非常困难或甚至不可能的问题（特别是一旦W包含整个复杂神经网络的权重），但是将一组特定的权重W精细化为稍好一些的问题是显着的不那么困难换句话说，我们的方法是从随机的W开始，然后迭代地改进它，使它每次稍微好一些。
策略二 随机局部搜索
你可能会想到的第一个策略是尝试在随机方向上延伸一只脚，然后只有在下坡的时候才采取一个步骤。具体来说，我们将从随机W开始，对其产生随机扰动δW，如果扰动的W +δW的损耗较低，则将进行更新。此过程的代码如下：
W = np.random.randn(10, 3073) * 0.001 # generate random starting W
bestloss = float("inf")
for i in xrange(1000):
step_size = 0.0001
Wtry = W + np.random.randn(10, 3073) * step_size
loss = L(Xtr_cols, Ytr, Wtry)
if loss < bestloss:
W = Wtry
bestloss = loss
print 'iter %d loss is %f' % (i, bestloss)
策略三 根据梯度
在上一节中，我们尝试在权重空间中找到一个方向，这将改善我们的权重向量（并给我们较低的损失）。事实证明，没有必要随机搜索一个好的方向：我们可以计算出我们应该改变我们的权重向量的最佳方向，该权重向量在数学上保证是最陡峭下降的方向（至少在极限中为步长为零）。这个方向与损失函数的梯度有关。在我们的徒步比喻中，这种做法大致对应于感觉到我们脚下的山坡，并且沿着最陡峭的方向。
在一维函数中，斜率是您可能感兴趣的任何点的函数的瞬时变化率。梯度是不采用单个数字而是数字向量的函数的斜率的推广。此外，梯度只是输入空间中每个维度的斜率向量（通常称为导数）。 1-D函数的导数与其输入的数学表达式是：
$\frac{df(x)}{dx} = \lim_{h\ \to 0} \frac{f(x + h) - f(x)}{h}$
当函数有多维向量而不是一个数字的时候我们做偏微分，梯度就是在不同方向上的偏微分。
梯度计算
有两种计算梯度的方法，一种是比较慢的虽然是近似但是简单的和一种快的 但是可能有错误。
第一种：
def eval_numerical_gradient(f, x):
"""
a naive implementation of numerical gradient of f at x
- f should be a function that takes a single argument
- x is the point (numpy array) to evaluate the gradient at
"""
fx = f(x) # evaluate function value at original point
grad = np.zeros(x.shape)
h = 0.00001
# iterate over all indexes in x
it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])
while not it.finished:
# evaluate function at x+h
ix = it.multi_index
old_value = x[ix]
x[ix] = old_value + h # increment by h
fxh = f(x) # evalute f(x + h)
x[ix] = old_value # restore to previous value (very important!)
# compute the partial derivative
grad[ix] = (fxh - fx) / h # the slope
it.iternext() # step to next dimension
return grad
但是这种梯度的定义中h的极限趋近于0，但是实际上他使用一个足够小的值就足够了，理想情况，你会想用最小的步长以不会引起计算问题。除此之外，实际上计算数字梯度使用中心极限定理是更好的。$ [f(x+h) - f(x-h)] / 2 h $
loss_original = CIFAR10_loss_fun(W) # the original loss
print 'original loss: %f' % (loss_original, )
# lets see the effect of multiple step sizes
for step_size_log in [-10, -9, -8, -7, -6, -5,-4,-3,-2,-1]:
step_size = 10 ** step_size_log
W_new = W - step_size * df # new position in the weight space
loss_new = CIFAR10_loss_fun(W_new)
print 'for step size %f new loss: %f' % (step_size, loss_new)
我们应该逆向更新梯度方向，并且梯度告诉了我们增加最陡峭的方向但是没有告诉我们应该向哪个方向前进。选择合适的步长也就是学习速率将会成为参数设定中的重要因素。
另外就是效率问题，你可能已经注意到数字梯度有一个复杂的线性参数关系。参数越多，这种策略可能会越差。
计算gradient analytically
鉴于上面的分析，又有另一种非常普遍的计算题都的方法叫做gradient check，如果使用SVM的例子，我们可以拿到相应于w的梯度：
$\nabla_{w_{y_i}} L_i = - \left( \sum_{j\neq y_i} \mathbb{1}(w_j^Tx_i - w_{y_i}^Tx_i + \Delta > 0) \right) x_i $
这里1是一个示性函数，就是里面的是真的那么就取1，假的取0，所以梯度下降算法，小批量梯度下降。在大规模应用（如ILSVRC挑战）中，培训数据可以有数百万个例子。因此，为了仅执行单个参数更新，计算整个训练集中的全损失函数似乎是浪费的。解决这一挑战的一个非常常见的方法是计算训练数据批次之间的梯度。例如，在目前最先进的ConvNets中，典型的批次包含来自整个120万个培训集的256个示例。此批次然后用于执行参数更新：
# Vanilla Gradient Descent
while True:
weights_grad = evaluate_gradient(loss_fun, data, weights)
weights += - step_size * weights_grad # perform parameter update
原因很好的是训练数据中的例子是相关的。为了看到这一点，考虑到极端情况，ILSVRC中的所有120万图像实际上由仅有1000个独特图像的精确重复（每个类别一个，或者每个图像的1200个相同的副本）组成。然后很明显，我们将为所有1200个相同的副本计算的梯度将全部相同，当我们平均所有120万图像中的数据丢失时，我们将获得完全相同的损失，就像我们只评估一小部分当然，实际上，数据集不会包含重复的图像，小批量的渐变是完整目标的梯度的很好的近似值。因此，通过评估小型批量梯度来执行更频繁的参数更新，实践中可以实现更快的收敛。
极端情况是迷你批次仅包含一个示例的设置。该过程称为随机梯度下降（SGD）（或有时在线梯度下降）。这是相对较少见的，因为在实践中由于矢量化的代码优化，对于100个示例，对于100个示例的梯度来说，计算上可以更有效地评估梯度，而不是一个示例100次的梯度。即使SGD技术上是指一次使用一个例子来评估渐变，即使在提到微型批量梯度下降（即提及“Minibatch Gradient Descent”的MGD或BGD for “批量梯度下降”很少见），通常假设使用小批量。小批量的大小是超参数，但是交叉验证它不是很常见。它通常基于内存约束（如果有的话），或者设置为一些值，例如。 32,64或128.在实践中，我们使用2的幂，因为当它们的输入的大小为2的幂时，许多向量化的操作实现工作更快。
