视觉识别的核心任务就是进行 图像分类

Challenges

当计算机进行视觉识别时，有许多的因素会对识别产生影响，例如，视角、明暗、变形、遮挡，而如何排除影响就是我们的问题。

在算法中，我们期望着将图片喂给算法，而算法能够很快的回馈给我们图片对应的标签。

def classify_image(image):
	# Some magic here?
	return class_label

但是，计算机看图片的方式与我们的有很大的不同，在计算机的眼里，输入进去的图片就是一堆堆数字，这就造成了语义鸿沟（Semantic Gap）。
这就产生了一个新的问题，对于同一个物体，不同的视角也会使数据产生很大的不同。
图片中的明暗，物体的变形、遮挡，背景与物体分界线不清晰，同一类物体的不同个体，计算机都需要进行处理。
对于这些问题，算法都需要具有鲁棒性，这是一个很大的挑战。

数据驱动方法

1. 收集数据集（图片 and 标签）
2. 训练一个分类器
3. 使用新图片去测试分类器

使用一个函数接收数据，进行训练
另外一个函数使用新的数据评估模型

def train(image, label):
	# Machine Learning
	return model

def predict(model, test_images):
	# Use model to predict labels
	return test_labels

第一个分类器——最近邻

最近邻算法就是一个数据驱动的算法。它将算法分为了两个函数，一个接收数据的输入，另一个进行预测。
L1 Distance（曼哈顿距离）：使用曼哈顿距离来比较两幅图片，获得两张图片的差值

最近邻分类器的代码：

import numpy as np 

class NearestNeighbor:
    def __init__(self):
        pass

    def train(self, X, y):
        '''X is N x D where each row is an example. Y is 1-dimension of size N'''
        # the nearest neighbor classifier simply remeber all the training data
        self.Xtr = X
        self.ytr = y

	def predict(self, X):
	    ''''X is N x D where each row is an example we wish to predict label for'''
	    num_test = X.shape[0]
	    # lets make sure that the output type matches the input type
	    Ypred = np.zeros(num_test, dtype=self.ytr.dtype)
	
	    # loop over all test rows
	    for i in xrange(num_test):
	        # find the nearest training image to the i'th test image
	        # using the L1 distance (sum of absolute value differences)
	        distances = np.sum(np.abs(self.Xtr - X[i, :]), axis = 1)
	        min_index = np.argmin(distances)
	        Ypred[i] = self.ytr[min_index]

    	return Ypred

时间复杂度： Train O(1); predict O(N)
训练的速度快于预测的速度，而我们通常希望能够预测的快一些

太过于死板，不能够有效地排除某些噪点或错误数据的影响。

K-最近邻算法（KNN）

1. 在临近点中选择k个临近点
2. 对这些临近点进行投票
3. 根据票数多的临近点预测结果

L2 Distance（欧式距离）：差平方之和求根
L2距离是确定的，旋转坐标轴也不会产生什么影响。

设置超参

超参数：在算法学习的过程中无法学到的数据，比如k和距离的选择。我们需要提前选择合适的超参数。
Method 1：
将数据集分为三个部分：

• train （image & label）
• validation （只知道image，将image与训练集对比，选择相应的 label）
• test

总是最后接触到测试集，以便于保证我们数据的准确性

Method 2：交叉验证
将数据集分为两大部分：

• test
• train

将train集再分为多份，每一份都可以当做验证集。一般对于小的数据集效果明显，在深度学习中不常用。
5折交叉验证：对于每个k值，使用算法进行5次不同的测试，可以得出每个k值的在局数据集上的准确率。

但是，KNN是不常使用的算法。
首先，它在整个算法上的计算比重在 test 阶段，而我们希望重点在如何 train 算法。
当 L2 距离相等时，对于图片的相似性不能很好的区分。
维度灾难，对于高维度的数据，使用L2 Distance 去计算是不合理的。

线性分类

Input：32×32×3（rgb三通道）图像
分类方法：一个函数 $f(x,W)$
在这个函数中，$x$是我们输入的图像，$W$是一个超参数。最终我们输出10个数字，这代表了图片在10个类中分别的分数。
Eg：$f(x,W)=Wx$
输出：一个10×1的数组（或者说矩阵）。
根据矩阵相乘的规则，图片原有的32×32×3大小的数组变换格式为3072×1大小（$x$）。$W$的大小也是可知的10×3072。
我们还会加一个偏置（bias），函数变成了这样：$f(x,W)=Wx+b$。这个偏置将会使点积结果更加偏向某个class。
线性分类器试图在高维决策空间中划分一个线性决策边界。
局限：一个函数只能针对一个class训练一个模型。

损失函数 & 优化

在线性分类中，只描述了$W$对结果的影响，但是，什么样的$W$能够产生正确结果呢？如果无法产生正确的结果，就会像下面这样：

我们需要一个函数，能够度量任意一个$W$的好坏。
损失函数：Input $W$，得到对这个$W$的评分，进行定量估计。
优化：从$W$的可行域里找到较优或最优的$W$。
给你一个数据集：
{ ( x i , y i ) } i N = 1 \{(x_i, y_i)\}_i^N = 1 {(xi​,yi​)}iN​=1

$x_i$是图片
$y_i$是标签（Integer），是训练集的第i个样本的正确分类

那么，对于这个数据集，损失函数就是：
$$L=\frac{1}{N}\sum _i{L}_i(f(x_i,W),y_i)$$
这是一个通用的公式。

多分类SVM损失函数

这个函数要干嘛？

损失函数能够对我们选择的超参数进行评估。函数输出的10×1大小的分数，我们将正确分类的分数与其他错误分类的分数之和做差，得到一个结果。当这个结果高于一个安全值时，我们就确定这是一个正确的模型。

数学公式

$$\begin{array}{rl}{L}_i& =\sum _{j\ne y_i}\{\begin{array}{ll}0& if{s}_{y_i}\ge s_j+1\\ s_j-s_{y_i}+1& otherwise\end{array}\\ & =\sum _{j\ne y_i}\max (0,s_j-s_{y_i}+1)\end{array}$$
$s_{y_i}$ 是真实分类的分数
$s_j$ 是所有错误的分数之和
当 $s_{y_i}$ 比 $s_j$ 高出一个安全距离时（这里是1），损失为0。

简图（CS231n ppt截屏）

x轴是正确分类对应的分数，y轴是损失。

伪代码

输入正确的分类y以及数据样本x。下面的代码把训练函数也放了进去以便于计算分数。

def L_i_vectorized(x, y, W):
	scores = W.dot(x)
	margins = np.maximum(0, scores - scores[y] + 1)
	margin[y] = 0
	loss_i = np.sum(margins)
	return loss_i

New Question

当得到的损失函数为0时，存在多个不同的权重$W$（$W$ and $2W$），那么我们如何在这些$W$中进行选择呢？