Image Classfication(kNN and Linear Classfication)

2017-09-24

主要是对图像分类的流程的总体介绍,主要介绍了kNN和Linear Classfication算法。和cs231n的 lecture_2 和 lecture_3对应。

图像分类的几大挑战

1、Viewpoint Variation:相机移动会造成像素点发生改变。
2、Illumination:同一物体在不同光照条件下差别也比较大。
3、Deformation:同一物体的不同形变也会给分类造成较大影响。
4、Occlusion:遮挡问题，有时只能看见物体局部，难以分辨。
5、Background Clutter:背景干扰，比如动物保护色等让人难以分辨。
6、Intraclass Variation:同一物种个体之间差异也大。

图像分类的任务

图像分类的任务就是输入一幅图像，返回其分类结果。此类任务是难以通过显示编程
制定一些规则来进行的。

1
2
3

def classify_image(image):
    #do something
    return label

具体分类方法

较为传统的方法

通过边缘检测，角点检测等方法找出一些特征，然后对特征进行一些统计得出分类结果。

数据驱动的方法(Data-Driven Approach)

大致的流程就是：
1、准备图像和标签一一对应的数据集。
2、通过机器学习的方法去训练一个分类的模型。
3、在另外的数据上去检验这个模型的准确性。

#train a model
def train(images,labels):
    #Machine Learning
    return model
#predict the label
def predict(model,test_images):
    #Use trained model to predict labels
    return test_labels

Nearest Neighbor（最近邻法）

1、在训练阶段只是将图片和标签载入内存，不做任何额外操作。
2、预测阶段，将待预测图片和之前载入的图片逐一比较，选取和待预测图片最相似的训练图片的标签作为预测结果。

如何判断相似性？
L1 Distance or L2 Distance or others?
这里简单使用 L1 distance

优点：思想简单，编程实现容易。
缺点：准确率较低，而且训练时只是读入数据，测试时需要逐一比较，耗时与数据集大小成线性关系，与我们的初衷不符。

K-Nearest Neighbors(K最近邻法)

其基本思想与 Nearest Neighbor一致，只是我们需要保留前k个最相似的图片的结果，然后在这k个结果里面做一个决策。
这里就会出现两个问题：
1、如何选取合适的k值使得预测结果更准确？
2、如何选取distance的算法使得预测结果更准确？
其实这些都叫做 hyperparameters(超参数)，需要我们预先设置。

如何设置超参数？

方法1：选取超参数使得其在训练集上的效果最好。
这个方法存在的一个显著问题就是：k=1总是能够使得其在训练集上的效果最好。这种方法显然不可取。
方法2：将数据集分为训练集和测试集两选取超参数使得在测试集上的效果最好这种方法避免了前一个问题，但是又带来了一个新问题，就是它不能预判断算法在新的数据集上的表现情况。
方法3：分为训练集、验证集和测试集，以验证集选取超参数，在测试集上验证。这种方法比前两种方法都好一点。有效避免了之前的问题。
方法4：交叉验证。将数据集分为n份，分别以其中一份作为验证集，其他作为训练集，最后得到n个结果，再对结果做一个平均。这种方法是目前来说最好的。这种方法主要还是用于训练样本较小的情况下，对于较大的训练样本，其实方法3就能达到较好效果，用该方法会浪费不少时间。

方法的缺陷

实际上k-Nearest Neighbor这种方法从来没有被实际采用过，主要有以下几个原因：
1、正如上面提及过的，时间效率太低。
2、通过像素差值判断相似性本身就有很大的问题。

总结

1、在图像分类问题上，我们在训练集上训练，之后在测试集上验证结果。对于其他的机器学习问题也是如此。
2、距离度量方式和K的都是超参数，需要我们事先确定。
3、用验证集确定超参数，最后在测试集上测试结果。

Linear Classification(线性分类器)

这种方法将比之前的方法都更有效，并且可以以此来引入之后的Neural Networks(神经网络)和Convolutional Neural Networks(卷积神经网络)。主要由两部分组成：
1、score function 实现从原始图像数据到各个标签的得分的一个映射。
2、loss function 用来定量比较分析预测的得分和实际的label的差距。
我们的最终目的就是通过优化，使得loss function最小，最后确定的score function 的参数作为最终的模型的参数，用来预测label。

Score function

f(xi,W,b)=W*xi+b

注意事项

1、W*xi 的结果是一个向量，每个元素代表对应标签的一个预测得分。
2、我们的目标就是通过训练确定W和b，使得预测结果和真实结果最为接近。也就是使得对于一个输入图像xi，我们要使得其正确分类的得分大于错误分类的得分。
3、这种方法的好处在于训练集只是用于训练确定参数W和b，我们最后只需要保留W，b的值。之后对于每一幅输入图像，只需要带入确定的W和b值即可预测出其分类结果。所以这种方法的时间效率远大于之前的NN和kNN算法。
4、实际上，之后的神经网络和卷积神经网络的方法和线性分类器的思想是一致的，只是score function 和 loss function 是另外的函数形式。

解释线性分类器

线性分类器实际上就是计算一个图像各个像素各个通道的加权和。加权的结果取决于我们设置的W，b的值。

将图像作为高维点分析

一幅32x32x3的图像可以被拉伸为1x3072的高维点来表示。所以数据集中的图像可以看做一系列高维点。因为我们定义每个分类的score是所有像素点的加权和，实际上每个分类的分数就是这个高维点的线性函数。虽然无法可视化3072维的数据，但是当我们把3072维压缩成2维，就可以尝试着可视化线性分类器的操作。

将线性分类器解释为模板匹配

这种解释将W的每一行看做是对应的分类的一个模板，也就是对应的分类的一个原型。实际上每个分类的score就是将输入图像与模板进行比较(这里是通过点积的形式)，最后看输入图像和哪个模板最匹配。
这其实和最近邻算法类似，主要区别在：
1、最近邻算法是将输入图像和每幅图像作比较，而线性分类器是将输入图像和模板图像相比较。
2、最近邻算法通过L1或者L2距离判断相似性，线性分类器通过点积判断相似性。

下面是根据CIFAR-10训练得到的模板图像

处理b参数的小技巧

实际上我们可以通过对W 矩阵增加1列，对xi增加1行的方法，将
f(xi,W,b)=Wxi+b ——> f(xi,W)=Wxi
这样就只用训练一个参数W。
如下图所示：

图像预处理

在应用中常常需要对图像数据进行预处理，比如
[0,255]->[-127,127]->[-1,1],关键在于让零值居中，使得数据集中。

Loss Function(损失函数)

损失函数的作用是来评价在训练集上分类结果的好坏，当分类结果接近真实结果时，损失函数自然就小，反之则大。损失函数有多种计算方法，下面分别从阐述。

Multiclass Support Vector Machine loss

设置 SVM loss的目的是为了让正确分类的得分与错误分类的得分至少相差某一个确定的δ,
简单来说，其计算公式如下：

更多细节可以参考
cs231n spring2017 linear_classify notes

其实概括来说就是SVM loss 希望让正确分类的得分大于错误分类的得分至少δ，如果没有达到要求，那么我们就计算一个loss,如果达到要求，那么loss为0。针对线性分类器，我们有如下的计算SVM loss的公式：

其实形如 max(0,-)这样的损失函数叫做 hinge loss,并且指数项不一定是1次，有时为了让错误结果更明显，可能用指数项为2次得到的效果会更好。具体使用哪种可以通过前面提及的交叉验证来确定。确定了损失函数之后，接下来的工作就是找到一种优化的方法，使得loss尽可能小，然后确定W。

上面提及的SVM loss还存在一个问题：假设我们有一个数据集和W使得对于每一个图像i都满足Li=0,那么显然W 不是唯一的。因为这样的话 λW(λ>1) 也能使得Li=0。那这样我们该选择哪个W作为最终结果呢？这样对于正确的分类没有影响，但是对于错误的分类，就会将loss放大λ倍。

为了解决以上的问题，引入了一个 regularization penalty(正则惩罚项) R(W)。通常的做法是利用L2 norm 来限制W中每个元素的大小。
如下所示：

注意这里的R(W)只和W有关，而和数据集无关。这样SVM loss就有 data loss和 regularization loss 两部分组成：

在线性分类器中，其形式如下：

λ作为超参数通常也是要通过交叉验证来确定。

引入正则惩罚项的一个最大的好处是增强模型的泛化能力，让最终的结果尽可能受到更多参数的影响，能够减小过拟合的情况。另外值得注意的是，当引入正则惩罚之后，Loss就不可能为0了，因为如果Loss为0，那么意味着W=0，那将毫无意义。接下来我们将要考虑的就是通过什么方法来使得loss尽可能小。

如何确定超参数δ，实际上我们可以简单设置δ为1。其实δ和λ对于loss的影响是一致的，所以我们其实只需要确定λ就好。

Softmax loss

这是另一种计算损失函数的方法，和SVM 计算每个分类得分的方法不同，Softmax分类器是对属于每个分类的可能性做评估。
在这里，将每个分类的得分转化为属于这个分类的概率，并且用 cross-entropy loss(交叉熵损失)代替hinge loss。
计算形式如下：

其中softmax function 形如以下：

其中的一些理论不再阐述。
实践的技巧：由于要计算指数项，除以大数可能造成数值不稳定，所以需要归一化的技巧，可以如下操作：

比较常用的方法是设置

f = np.array([123, 456, 789]) # example with 3 classes and each having large scores
p = np.exp(f) / np.sum(np.exp(f)) # Bad: Numeric problem, potential blowup
# instead: first shift the values of f so that the highest number is 0:
f -= np.max(f) # f becomes [-666, -333, 0]
p = np.exp(f) / np.sum(np.exp(f)) # safe to do, gives the correct answer

SVM loss 和 Softmax loss 的比较

具体分析见
cs231n spring2017 linear_classify notes

Optimization(优化)

确定了score function和 loss function之后，我们要做的就是通过优化使得 loss function 尽可能小，然后确定 score function的参数。不仅是针对线性分类器，其他分类方法的整个流程也是一样的，只是score function 和 loss function可能有所不同。
主要有如下一些策略：

Random Search(随机搜索)

顾名思义就是随机设置W的数值，每次记录loss,迭代若干次，找出使得loss最小的结果。显然，迭代次数越多，能够尝试的参数就会越多，就越有可能找出更为准确的参数，但是永远不可能找出所有的结果。并且我们是盲目地找结果，效率较低，这显然过于笨拙。
但是这种方法也能给我们一些启示：我们能不能找到一种方法，从一个随机的参数W开始，进行优化，每次迭代使得loss降低一些？这给下一个策略提供了思路。

# 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)
# prints:
# in attempt 0 the loss was 9.401632, best 9.401632
# in attempt 1 the loss was 8.959668, best 8.959668
# in attempt 2 the loss was 9.044034, best 8.959668
# in attempt 3 the loss was 9.278948, best 8.959668
# in attempt 4 the loss was 8.857370, best 8.857370
# in attempt 5 the loss was 8.943151, best 8.857370
# in attempt 6 the loss was 8.605604, best 8.605604
# ... (trunctated: continues for 1000 lines)

Random Local Search

这种方法的思想就是随机给W设置一个初始值，然后在此基础上给一个增量变为W+δW,比较两处的loss,如果增加后更小，则更新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)

Following the Gradient

第二种方法虽然效率比第一种稍高，但是在选择δW的时候还是随机的，效率也较低，而实际上是可以有一定的策略选择δW的。比如可以通过计算梯度，沿着梯度小于0的方向就能使得loss变小。

如何计算梯度

从以上分析看出，前两种优化策略都显得盲目，效率较低，而根据梯度来进行优化显然更为合理。那么梯度怎么去计算呢？主要有两种方法：1、numerical gradient,通过定义去计算梯度，其优点是思想简单，缺点是速度慢并且只是近似值，精度取决于δ的大小。2、analytic gradient，根据分析得出偏导数的表达式计算，其优点是快速准确，缺点就是容易出错。接下来分别介绍这两种算法。

Numerical Gradient

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

实际使用中常用的公式是 [f(x+h)-f(x-h)]/2h
在更新W的时候，是沿着负梯度的方向更新的，这样能够确保每次使得loss在降低。
选择合适的step size 很重要，也就是 learning rate(学习率)，这也是机器学习中的一个超参数。learning rate过低，使得更新缓慢，时间效率低，而learning rate如果过高，可能使得overstep(即越过最低点到达一个很糟糕的地方)。
更新梯度与参数数量成线性关系，对于30730个参数，我们需要对30731个参数验证梯度，最后只在1个参数上更新，对于参数少的情况着无关紧要，但是当参数特别多时，这就比较麻烦了，所以需要更好的办法。

Computing the gradient analytically with Calculus

这种方法因为有确定的公式，所以计算速度很快，但是容易出错。常常会将这两种方法进行比较以验证梯度计算方法的正确性，这叫做 gradient check(梯度检查)。不同的loss function自然有不同的梯度表达式。

Gradient Descent

计算出梯度之后，我们就将沿着梯度下降的方向更新参数。这就叫做Gradient Descent(梯度下降)。

# Vanilla Gradient Descent
while True:
  weights_grad = evaluate_gradient(loss_fun, data, weights)
  weights += - step_size * weights_grad # perform parameter update

之后可能会有其他方法来优化这一过程，但是其核心思想都是梯度下降。

Mini-batch gradient descent

在训练集比较大的情况下，如果每执行一次单个参数的更新就对每个数据的loss进行计算，显得效率太低。常用的解决方法是计算批量数据之间的梯度，如下面所示：

# Vanilla Minibatch Gradient Descent
while True:
  data_batch = sample_training_data(data, 256) # sample 256 examples
  weights_grad = evaluate_gradient(loss_fun, data_batch, weights)
  weights += - step_size * weights_grad # perform parameter update

实际上，批量数据的梯度是完整数据的梯度的良好近似，用批量数据的梯度代替完整数据的梯度进行快速计算，实现参数的快速更新，在实践中往往能够达到更好的结果。这算是时间效率和精度的一个折中方案。