k-NN分类器的不足：
概述：我们可以实现一种更加强大的新方法来解决图像分类问题。该方法由两部分组成：
该方法可转化为一个最优化问题，即通过更新score function的参数来最小化loss。
现假设有一个包含很多图像的训练集$x_i\in \mathcal{R}^D$，每个图像都有一个对应的分类标签$y_i$，其中$i=1,2,...,N$且$y_i\in 1...K$，即有N个图像样例，每个图像的维度是D，共有K种不同的分类。
现在定义score function为：$$f:\mathcal{R}^D \to \mathcal{R}^K$$该函数是原始图像像素到分类分值的映射。
将图像看做高维度的点：由于图像被伸展成为了一个高维度的列向量，我们可以把图像看做是这个高维度空间中的一个点，整个数据集就是一个点的集合，每个点都带有一个分类标签。同样的，既然定义每个分类类别的分值是权重和图像的矩阵乘，那么每个分类类别的分数就是这个空间中的一个线性函数的函数值。
$W$的每一行都是一个分类类别的分类器，如果改变其中一行的数字，会看见分类器在空间中对应的直线开始想着不同的方向旋转，而偏差$b$则允许分类器对应的直线平移。
将线性分类器看做模板匹配：关于权重$W$的另一个解释是它的每一行对应着一个分类的模板（有时候也叫作原型/prototype）。一张图像对应不同分类的得分，是通过使用内积（也叫点积）来比较图像和模板，然后找到和哪个模板最相似。
从这个角度来看，线性分类器就是在利用学习到的模板，针对图像做模板匹配。从另一个角度来看，可以认为还是在高效地使用k-NN，不同的是我们没有使用所有的训练集的图像来比较，而是每个类别只用了一张图片（这张图片是我们学习到的，而不是训练集中的某一张），而且我们会使用（负）内积来计算向量间的距离，而不是使用L1或者L2距离。
偏差和权重的合并技巧：一般为了能够将常用的参数W和b合二为一，可以把两个参数放到同一个矩阵中，同时$x_i$向量增加一个维度，且这个维度的数值是常量1，即为默认的偏差维度（bias dimension）
如此，新的公式简化为：$$f(x_i,W)=Wx_i$$
图像数据预处理：在机器学习中，对于输入的特征做归一化（normalization）处理是常见的套路。而在图像分类的例子中，图像上的每个像素可以看做一个特征。在实践中，对每个特征减去平均值来中心化数据是非常重要的。在这些图片的例子中，该步骤意味着根据训练集中所有的图像计算出一个平均图像值，然后每个图像都减去这个平均值，这样图像的像素值就大约分布在[-127, 127]之间了。下一个常见步骤是，让所有数值分布的区间变为[-1, 1]。零均值的中心化是很重要的。
损失函数（Loss Function）有时也叫作代价函数（Cost Function）或目标函数（Objective）。我们使用损失函数来衡量我们对结果的不满意程度，当评分函数输出结果与真实结果之间的差异越大，损失函数的输出越大，反之越小。
SVM的loss function希望SVM在正确分类上的得分始终比不正确分类上的得分高出一个边界值$\Delta$。
第i个数据中包含图像$x_i$的像素和代表正确类别的标签$y_i$。评分函数输入像素数据，然后通过公式$f(x_i,W)$来计算不同分类类别的分值。这里我们将分值简写为$s$。比如，针对第j个类别的得分就是第j个元素：$s_j=f(x_i,W)_j$。针对第i个数据的多类SVM的损失函数定义如下：
$$L_i=\sum_{j\neq y_i} \max(0,s_j-s_{y_i}+\Delta)$$在本模型中，还可将其改写为：
$$L_i=\sum_{j\neq y_i} \max(0,w_j^Tx_i-w_{y_i}^Tx_i+\Delta)$$其中$w_j$是权重W的第j行
Hinge loss（折叶损失）：$\max(0,-)$
Squared Hinge Loss(平方折叶损失)：$\max(0,-)^2$
Regularization（正则化）：假设有一个数据集和一个权重集W能够正确地分类每个数据（即所有的边界都满足，对于所有的i都有$L_i=0$）。问题在于这个W并不唯一：可能有很多相似的W都能正确地分类所有的数据。一个简单的例子：如果W能够正确分类所有数据，即对于每个数据，损失值都是0。那么当$\lambda>1$时，任何数乘$\lambda W$都能使得损失值为0，因为这个变化将所有分值的大小都均等地扩大了，所以它们之间的绝对差值也扩大了。
为了对某些特定的权重W添加一些偏好，对其他权重不添加，以此来消除模糊性，可以向损失函数添加一个正则化惩罚（regularization penalty）$R(W)$。最常用的正则化惩罚是L2范式：
$$R(W)=\sum_{k} \sum_{l} W_{k,l}^2$$添加正则化惩罚后，完整的多类SVM损失函数由两部分组成：数据损失（data loss），即所有样例的平均损失$L_i$，以及正则化损失（regularization loss）。完整公式如下所示：
$$L = \underbrace{ \frac{1}{N} \sum_i L_i }_\text{data loss} + \underbrace{ \lambda R(W) }_\text{regularization loss}$$还可将其展开为：
$$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} + \Delta) \right] + \lambda \sum_k\sum_l W_{k,l}^2$$其中，N是训练集的数据量。现在正则化惩罚添加到了损失函数里面，并用超参数$\lambda$来计算其权重。该超参数无法简单确定，需要通过交叉验证来获取。
L2惩罚倾向于更小更分散的权重向量，这就会鼓励分类器最终将所有维度上的特征都用起来，而不是强烈依赖其中少数几个维度。这一效果将会提升分类器的泛化能力，并避免过拟合。
需要注意的是，和权重不同，偏差没有这样的效果，因为它们并不控制输入维度上的影响强度。因此通常只对权重W正则化，而不正则化偏差b。
def L_i(x, y, W):
"""
unvectorized version. Compute the multiclass svm loss for a single example (x,y)
- x is a column vector representing an image (e.g. 3073 x 1 in CIFAR-10)
with an appended bias dimension in the 3073-rd position (i.e. bias trick)
- y is an integer giving index of correct class (e.g. between 0 and 9 in CIFAR-10)
- W is the weight matrix (e.g. 10 x 3073 in CIFAR-10)
"""
delta = 1.0 # see notes about delta later in this section
scores = W.dot(x) # scores becomes of size 10 x 1, the scores for each class
correct_class_score = scores[y]
D = W.shape[0] # number of classes, e.g. 10
loss_i = 0.0
for j in xrange(D): # iterate over all wrong classes
if j == y:
# skip for the true class to only loop over incorrect classes
continue
# accumulate loss for the i-th example
loss_i += max(0, scores[j] - correct_class_score + delta)
return loss_i
def L_i_vectorized(x, y, W):
"""
A faster half-vectorized implementation. half-vectorized
refers to the fact that for a single example the implementation contains
no for loops, but there is still one loop over the examples (outside this function)
"""
delta = 1.0
scores = W.dot(x)
# compute the margins for all classes in one vector operation
margins = np.maximum(0, scores - scores[y] + delta)
# on y-th position scores[y] - scores[y] canceled and gave delta. We want
# to ignore the y-th position and only consider margin on max wrong class
margins[y] = 0
loss_i = np.sum(margins)
return loss_i
def L(X, y, W):
"""
fully-vectorized implementation :
- X holds all the training examples as columns (e.g. 3073 x 50,000 in CIFAR-10)
- y is array of integers specifying correct class (e.g. 50,000-D array)
- W are weights (e.g. 10 x 3073)
"""
# evaluate loss over all examples in X without using any for loops
# left as exercise to reader in the assignment
设置Delta：该超参数在绝大多数情况下设为$\Delta=1.0$都是安全的。超参数$\Delta$和$\lambda$看起来是两个不同的超参数，但实际上他们一起控制同一个权衡：即损失函数中的数据损失和正则化损失之间的权衡。理解这一点的关键是要知道，权重W的大小对于分类分值有直接影响（当然对他们的差异也有直接影响）：当我们将W中值缩小，分类分值之间的差异也变小，反之亦然。因此，不同分类分值之间的边界的具体值（比如$\Delta=1$或$\Delta=100$）从某些角度来看是没意义的，因为权重自己就可以控制差异变大和缩小。也就是说，真正的权衡是我们允许权重能够变大到何种程度（通过正则化强度$\lambda$来控制）。
在初始形式中进行最优化：在神经网络相关领域中，损失函数的最优化的始终在非限制初始形式下进行。很多这些损失函数从技术上来说是不可微的（比如当x=y时，max(x,y)函数就不可微分），但是在实际操作中并不存在问题，因为通常可以使用次梯度。
SVM将输出$f(x_i,W)$作为每个分类的评分，而Softmax的输出为归一化的分类概率。在Softmax分类器中，函数映射$f(x_i;W)=Wx_i$不变，但将这些评分视为每个分类的未归一化的对数概率，并且将hinge loss替换为cross-entropy loss（交叉熵损失）。公式如下：
$$L_i = -\log\left(\frac{e^{f_{y_i}}}{ \sum_j e^{f_j} }\right) \hspace{0.5in} \text{or equivalently} \hspace{0.5in} L_i = -f_{y_i} + \log\sum_j e^{f_j}$$在上式中，使用$f_j$来表示分类评分向量$f$中的第$j$个元素。和之前一样，整个数据集的损失值是数据集中所有样本数据的损失值$L_i$的均值与正则化损失$R(W)$之和。其中函数$f_j(z)=\frac{e^{z_j}}{\sum_ke^{z_k}}$被称作softmax 函数：其输入值是一个向量，向量中元素为任意实数的评分值（z中的），函数对其进行压缩，输出一个向量，其中每个元素值在0到1之间，且所有元素之和为1。
两个分类器都计算了同样的分值向量$f$（本节中是通过矩阵乘来实现）。不同之处在于对$f$中分值的解释：SVM分类器将它们看做是分类评分，它的损失函数鼓励正确的分类（本例中是蓝色的类别2）的分值比其他分类的分值高出至少一个边界值。Softmax分类器将这些数值看做是每个分类没有归一化的对数概率，鼓励正确分类的归一化的对数概率变高，其余的变低。
Softmax分类器为每个分类提供了“可能性”
在实际使用中，SVM和Softmax经常具有相似的效果