本节课主要简介K最近岭(KNN)算法和线性分类器两种算法。

什么是图像分类？

图像分类问题就如它的名字一样，它解决的问题是输入一张图像如何计算出该章图像的类别。图像分类是计算机视觉领域的核心问题，后期的目标检测，语义分割，实例分割等任务都是基于图像分类问题去解决的。

图像分类遇到的挑战

图像在计算机中是以数字矩阵的形式进行存储的，比如一只猫的图片他在计算机看来就是一个数字矩阵：

image-20210812151621221

但是如果摄像机从不同的角度拍摄猫，或者不同背景的猫又或是不同品种的猫。这些图片的像素矩阵已经是完全不一样的了。那么我们要如何通过计算机去学习到“猫”这种特征呢？

image-20210812211440662

如果你想用硬编码的方式去实现一个图像分类，可能你写的就是这样的代码了。

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

我们可以很清晰的认识到，图像分类并不像数组排序这样有一个“显式”的特征可以进行提取。no obvious way to hard-code the algorithm for recognizing a cat, or other classes

正是因为人们不能提取出一个硬编码来描述什么是一只猫，所以我们就采用数据驱动的方法去解决这个问题。

机器学习：数据启动的方法

在上面已经说到了我们不能够使用硬编码的方式去写出来一个分类器。所以人们就选择用大数据的方式去让代码“学习”图像的特征。使用大数据去训练分类器的一般步骤如下：

  1. 制作数据集：图片和标签
  2. 使用机器学习算法去训练分类器
  3. 在新的图片上评估分类器

在CS231N的本节课程中介绍了两种算法，第一种算法是最近岭算法，第二种算法是线性分类算法。

最近岭算法

最近岭算法非常的简单，举一个很形象的例子就是我要判断你是不是一个好人我就判断离你最近的那个人是不是好人。在训练过程也非常的简单，其实最近岭算法都不能算是有训练过程。它的训练过程可以说是记忆所有的数据和标签。在进行预测时去在它“记忆”的数据中找“最近”的图片，把“最近”的这个图片的标签当做预测的结果。

image-20210812211532771

那么如何衡量两个图片之间的距离呢？ 我们可以使用L1距离来衡量图片之间的距离，L1距离的公式如下：
d1(I1,I2)=∑p∣I1p−I2p∣d_{1}\left(I_{1}, I_{2}\right)=\sum_{p}\left|I_{1}^{p}-I_{2}^{p}\right|
这个公式也是很好理解，他就是将两个图片的像素值进行相减然后将所有像素值相加作为两张图片之间的距离。

image-20210812211624696

最近岭的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import numpy as np

class NearestNeighbor:
  def __init__(self):
    	pass
  def train(self,X,y)
  		"""
  		X的维度是N x D维，每一行都是一个图片（打平后），y是一个1xN为的label矩阵
  		"""
	    self.Xtr = X
  	  self.ytr = y
    
   def predict(self,X):
      num_test = X.shape[0] 
      Ypred = np.zeros(num_test,dtype=self.ytr.dtype)
      # 循环每一个测试集
      for i in xrange(num_test):
        	# 计算L1距离
        	distances = np.sum(np.abs(self.Xtr-X[i,:]),axis=1)
          # 找到L1距离最小的样本的索引
          min_index = np.argmin(distances)
          # 将其作为预测的类别
          Ypred[i] = self.ytr[min_index]
      return Ypred

K最近岭（KNN）

对最近岭进行了小小优化的一种算法叫做K最近岭，最近岭是选择最近的一个。K最近岭是选择最近的K个。K最近岭算法的优点就是可以让决策便捷更加的平滑，减小各种 “边界凸起”。下图是K=1，2，3时的类别决策边界：

image-20210812155159540

可以看到K=1的时候，边界处有很多的蜜汁凸起。这对于一个分类器来说是非常不好的。我们应该希望每个类别的边界尽可能的平滑。这样就不会因为输入的细微改变而导致输出类别发生彻底的变化。当然了现在有很多的研究都证明了当代的神经网络非常容易收到恶意样本的干扰（跑题了，这不不在本节范围内）。

不同的距离衡量函数

L1距离前面已经介绍过了，L1的公式如下：

d1(I1,I2)=∑p∣I1p−I2p∣d_{1}\left(I_{1}, I_{2}\right)=\sum_{p}\left|I_{1}^{p}-I_{2}^{p}\right|

除了L1距离还有L2距离，L2距离就是我们高中熟知的点与点距离的计算公式。

d2(I1,I2)=∑p(I1p−I2p)2d_{2}\left(I_{1}, I_{2}\right)=\sqrt{\sum_{p}\left(I_{1}^{p}-I_{2}^{p}\right)^{2}}

L1距离和L2距离也有各自的特点，L1距离比较适用于坐标轴是明确的。如果特征没有明确的语义含义比如计算两地之间的距离，使用L2距离更合适。

K最近岭算法的缺点

  • 非常的慢
  • 无论是L1距离还是L2距离都有没有办法准确的衡量图片之间的距离。
  • 维度的诅咒（随着维度的增加计算量是爆炸性的增加）

线性分类算法

在一维空间中线性分类器就是用一个点进行分类，二维空间中就是用一个直线来进行分类，三维空间中就是用一个平面来进行线性分类。对于多类别分类问题就可以用多个线性分类器来实现。

一个线性分类器可以抽象为以下的一个函数：

f=Wx+bf = Wx+b

多个线性分类器就可以完成多分类的这样一个任务: 我们现在需要做一个三分类的分类器。那么我们就有三个WW]。每个分类器都会输出一个置信度，置信度最高的类别就是分类的结果。

image-20210812211946529

比较有趣的一点是：我们如果使用在cifar10或者其他数据集上训练出来的线性分类器的权重WiW_i的可视化结果。

image-20210812212750229

这样说明了一点：线性分类器学习到的是浅层的图像特征，这点可以与目前的卷积网络提取的特征形成比较鲜明的对比。

线性分类器最大的问题是：线性分类器无法对于非线性的数据进行分类

在下一节的课程中将会写到如何去写损失函数、如何进行优化以及如何过度到卷积神经网络。