1. 背景
CS231n的全称是:
Convolutional Neural Networks for Visual Recognition，
面向视觉识别的卷积神经网络
这篇文章只是记录了自己学习 cs231n 课程的一些笔记或者自己的一些想法。如果想看完整的笔记,知乎有人做了很详细的翻译版本，请移步这里
机器学习翻来覆去，其实就是那么些算法，这门课，主要是讲在视觉识别领域，如何使用这些算法进行识别和调优。从最简单的KNN到神经网络以及卷积神经等。说白了，如果这些算法已经掌握的很牛逼了，那么我感觉，高手们学习这门课大概也就几个小时的时间，就可以吃透了。
2. 视频链接
内容其实是一样的，只是英文不是很好的同学，可以看这个网易云课堂的版本
3. 正文：深度学习与计算机视觉
3.1 引入
3.1.1 图像分类算法总览
拿到一个图像，我们怎么知道他是个动物还是风景，是张三还是隔壁老王。因为我们的数据库不可能有一模一样的图像，所以只能看它和哪个或者哪些图像最接近，我们就把他归类到这种图像中。
这种行为称之为“分类”。那我们怎么分类呢？分类有哪些算法呢？
机器学习中的分类算法非常多：
这个图基本列举了常见的machine learning的算法，大体分为4类,分别是:
classification (分类)，
clustering (聚类),
regression (回归),
dimensionality reduction (降维)
其中，
分类和回归的区别是：分类是离散的，回归是连续的。
分类和聚类的区别是：分类是监督学习（有可供参考的类别标签的），聚类是无监督学习（没有可供参考的类别标签）；
补充1：回归也属于监督学习，聚类和分类都是离散的。
补充2：降维，这块还没学懂，有监督的算法也有无监督的算法。暂且不展开讨论。
这里不会给大家展开所有的算法，只是先整体有个大概，课程真正的展开是从KNN开始的，
这个是个很简单的算法，从这里入门，便于后续的深入研究。
3.1.2 学习前的准备
首先想这么一个问题：
我们如何比较2幅图的区别？
比较直观的思路是：图的本质就是RGB的组合，每个像素点就是一个RGB值，然后以像素点为单位，一个图就可以扩展为一个m*n的矩阵（假设横向m个像素，纵向n个像素），为了方便比较，我们统一把所有的图都可以整理为m*n的矩阵。那么图像分析问题就转换为矩阵比较问题:
如何确认2个矩阵是相近或者属于同类的?
我的第一反应就是，直接求差。你想啊，如果2个矩阵完全相等，那么求差的结果就是个零矩阵啊。就像手写数字识别一样，你的test数据转换为矩阵A，如果train数据为矩阵B， A-B=[0,…0],那么A样本必然和B属于同类啊。
Notes: 这个思路扩展下去，其实就是2个矩阵求曼哈顿距离（后面会谈到的L1公式）
屏幕快照 2017-04-25 上午12.01.21.png
但这个是理想情况，那么如果test数据和train数据比较发现，和好几个样本的差值都比较接近，（而且关键的一点是，差值可正可负），那怎么定义A的分类呢？
如此说来，求差值必然是不完整的，那么怎么办？差值求出来求绝对值？嗯，好像有点接近，但本质上和直接求差没有太大区别。
那么换个思路，我们放到几何中去考虑，其实本质就是求2点距离的问题，对吧。 这个从小就学过，点A和点B的距离，横纵坐标差的平方和再开方。
Notes: 这个思路扩展下去，其实就是2个矩阵求欧式距离（下面会谈到的L2公式）
那么总结下来，好像我们也不需要懂什么机器学习的理论，客观分析，其实也能大概想到一些解决类似问题的方法。
这个思路扩展下去，就是CS231n后面要讲的KNN算法。当然实际算法，在距离的算法上有一些新的扩展，但原理都是一样的。
3.2 机器学习的常见算法实现
3.2.1 KNN临近算法（K-Nearest Neighbor）
3.2.1.1 理论
对应知乎笔记：CS231n课程笔记翻译：图像分类笔记（上）
这个算法的本质就是“近朱者赤”，从临近范围内（这个范围可以通过L1公式或者L2公式进行计算）的对象看看哪个占比高，就用那个作为其类别。
其中的关键是K,就是选择几个样本的问题，本质就是临近范围选择多少的问题。
L1,L2公式说明：
L1：曼哈顿距离(wiki解释)
简单说就是矩阵直接求差，该公式俗称出租车距离，地图上A.B两点的距离，出租车不可能直线穿过去，只能横向纵向走，所以就有这个公式。
L2：欧式距离（wiki解释）
这个应该大家都学过（空间2点的直线距离），这里不赘述了。
课程的后半段：
其中提到了几个建议的方法，比如交叉验证什么的，这些都是一些优化训练的方法，这会知道了最好，不知道也没关系，实际把数据玩起来，这些方法无形中自然会知道。
所以本章节的关键是，知道KNN算法，并且能实现它。然后知道他在实际中并不怎么用。（毕竟这算法也太简单了，做出来的结果准确率太低啊）。 导师还专门强调了不要在图像识别上使用KNN算法。
3.2.1.2 KNN算法 python实现
知道原理， 算法实现起来很简单。 这里简单交代下背景：
inX: 是输入的测试向量
dataSet: 是训练数据集合（array）
labels: 是训练样本的对应标签（array）
k: 是选择样本的个数
其他：python的tile函数用于生成指定维度的重复数组，sum(axis=1)是按行求和
然后，实现算法：
1.求距离 2. 按距离排序 3.按照k值取前k个使用
#!/usr/bin/python
# -*- encoding: utf-8 -*-
from numpy import *
import operator
from os import listdir
def classify(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
# 1、calculate distance
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# 2、sort from min-> max
sortedDistIndicies = distances.argsort()
# 3、confrim the frequency
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 4、get result
sortedClassCount = sorted(classCount.iteritems(),
key=operator.itemgetter(1), reverse=True)
关键步骤：
最为关键的是计算目标矩阵和临近矩阵的距离，上面的代码只是一个普通的实现方式，如果深思的话，会有多种实现方式.
这门课程的作业1，要求通过3种循环方式实现距离的计算：
def predict(self, X, k=1, num_loops=0):
# 根据传入的num_loops，决定使用哪种计算方式
if num_loops == 0:
dists = self.compute_distances_no_loops(X)
elif num_loops == 1:
dists = self.compute_distances_one_loop(X)
elif num_loops == 2:
dists = self.compute_distances_two_loops(X)
else:
raise ValueError('Invalid value %d for num_loops' % num_loops)
return self.predict_labels(dists, k=k)
这个东西，上来就让人一脸懵逼（对numpy熟悉的同学除外），本身绞尽脑汁才想出来一种最为普通的方式。
现在却还要用到不同的循环方式，完全是get不到点在哪里。
后来查了很多的资料，各种stackoverflow，各种blog才是搞清楚。主要原因是本人对numpy完全不熟悉，所以对于矩阵的计算不甚了解，之前一直仅仅是把矩阵当做数组来说思考处理的，但实际numpy提供了很多便捷的方法。
言归正传： 本质是求两个矩阵的欧氏距离，那我们的矩阵是长什么样的呢？
我们的数据来源是kaggle的CIFAR-10数据集,通过下面这个shell脚本，（或直接去kaggle搜索CIFAR-10），获取数据：
# Get CIFAR10
wget http://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz
tar -xzvf cifar-10-python.tar.gz
rm cifar-10-python.tar.gz
下载后可以看到我们有将近5、6k个图片，每个图片是32*32像素的，然后，上文提到过，我们每个图片本质就是RGB，所以还需要每个像素3个RGB值，这样表示我们的图片集，可以用一个5000*32*32*3的四维矩阵来表示，直观的看就是这样：
对应的矩阵，直观感受下就好：
Training data shape: (50000, 32, 32, 3)
[[[[ 59. 62. 63.]
[ 43. 46. 45.]
[ 50. 48. 43.]
...,
[ 158. 132. 108.]
[ 152. 125. 102.]
[ 148. 124. 103.]]
...,
[[ 198. 190. 170.]
[ 189. 181. 159.]
[ 180. 172. 147.]
...,
[ 178. 171. 160.]
[ 175. 169. 156.]
[ 175. 169. 154.]]
...,
[[ 150. 143. 135.]
[ 140. 135. 127.]
[ 132. 127. 120.]
...,
[ 224. 222. 218.]
[ 230. 228. 225.]
[ 241. 241. 238.]]
[[ 122. 119. 114.]
[ 118. 116. 110.]
[ 120. 116. 111.]
...,
[ 179. 177. 173.]
[ 164. 164. 162.]
[ 163. 163. 161.]]]]
算法1：compute_distances_two_loops：
看到这个矩阵和图片之后，估计大家可以较为简单的想到一个计算方法：就是每个图片彼此求距离啊，那么假设有10个测试数据，20个训练数据，那么2个for循环，取出来图片一一求距离，就可以了：
# 代码比较简单，就不细说了
def compute_distances_two_loops(self, X):
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in xrange(num_test):
for j in xrange(num_train):
dists[i, j] = np.sqrt(
np.sum(np.square(self.X_train[j, :] - X[i, :])))
return dists
算法2：compute_distances_one_loop：
其实，第一个算法想出来之后，第二个原理上是和第一个一样的， 也是取出来测试的图片，逐个和训练集求距离，只是基于numpy的方法，可以更简单的实现：
diffValue = X[i, :] - self.X_train
所以用一个循环实现的距离计算代码是：
def compute_distances_one_loop(self, X):
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in xrange(num_test):
diffValue = X[i, :] - self.X_train
dists[i, :] = np.sqrt(np.sum(diffValue**2))
return dists
算法3：compute_distances_no_loops：
最后一个不用循环，直接求距离的方法，其实是对考察对数学的了解程程度了，两个矩阵的欧式距离：
||v-w||^2 = ||v||^2 + ||w||^2 - 2*dot(v,w)
看着很像平方差公式，对不对，知道这个，翻译成python代码就很简单了：
def compute_distances_no_loops(self, X):
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
# ||v-w||^2 = ||v||^2 + ||w||^2 - 2*dot(v,w)
"""
Soluton1:
"""
dists = np.sum(X * X, axis=1)
test_square = np.reshape(
np.sum(X * X, axis=1), (-1, 1)) # （num_test,1）
train_square = np.reshape(
np.sum(self.X_train * self.X_train, axis=1), (1, -1)) # (1,num_train)
dists = test_square + train_square - 2 * \
np.dot(X, np.transpose(self.X_train)) # (num_test,num_train)
dists = np.sqrt(dists)
"""
Soluton2:
"""
M = np.dot(X, self.X_train.T)
te = np.square(X).sum(axis=1)
tr = np.square(self.X_train).sum(axis=1)
dists = np.sqrt(-2 * M + tr + np.matrix(te).T)
dists = np.array(dists)
return dists
源码地址： https://github.com/polegithub/standford_cs231n_assignment
以上是KNN的算法，并通过3种循环方式分别进行了实现，当然这3种算法，效率上也是有很大差别的，我实际跑下来的时间：
可以看到，向量的实现算法比其他算法在效率上有显著的优势。
至于为什么？ 后面抽个专题讲讲运行效率吧。
3.2.1.3 总结
总体来说，KNN应该是入门里面最为容易理解的算法之一了，不太需要太多的数学功底，基本就是你如何进行矩阵求差的问题。实际工作中虽然也用的不多，但是如果你数据量不大，而且只是想先大概估算某个数据的大致概率或者分布，可以临时用这个快速实现一些简单需求。
3.2.1 线性函数：SVM算法（支持向量机）
3.2.1.1 理论
i> Support vector machine, 支持向量机
所属类别： supervised learning 监督学习
所属范畴： classification
iii> 具体要解释的话，套用窦娥的一句话：
天,你不分黑白何为天; 地,你不辨忠奸枉为地
简单说，就是个分类算法，画地为牢，寻找一条分割线，分出类别。那怎么找出来这条线呢？
桌子上有一堆苹果和香蕉，给你一把尺子，最大限度的将其分开，那怎么分？ 这个很简单，直接从最中间的点入手，左右调整调整就找出最可靠的分法了对吧，基本是这样一张图：
那如果从数学或者几何的角度怎么理解这个东西呢？
首先，苹果和香蕉离得最近或者有重合的部分，沿着这些点，基本能大致确定分割线的方向和路径，然后做一些微调就好。那这样的一件事或者一个行为，称之为machine，其中，离这个分割线比较近的苹果或者香蕉称之为supooer vector(支持向量)，因为这些support vector的友情支持和协助，才能方便我们快速确定分割线。（说白了，简单粗暴点，直接把support vector连点成线，其实就已经是个分割线了，只是有点糙而已）
所以SVM就是“支持向量”的“机器(分类器)”，千万不要理解成“支持”了“向量机”。
iv> 数学计算
知道了定义，那么数学角度，怎么求出这么一条分割下来？
首先来分析，就这条线，处于最中间的位置，意思就是距离是距离两边是相等的，或近似相等的。转化为求distanceApple和distanceBanana相等的曲线函数：
转来一段知乎大拿的解释：
其实关键的部分是SMO相关的数学推导，推荐大家可以看一下这个博客：
支持向量机通俗导论（理解SVM的三层境界）
最终的损失函数公式是：
v> python 实现
一言不合上代码：
把上面的公式一步步翻译成代码：
- 交代背景：
# 我们有N个图片样本，C种类别，D个维度
# classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
# D = 32 * 32 *3 (每个图32*32像素，每个像素有RGB3种颜色构成)
- W: A numpy array of shape (D, C) containing weights.
- X: A numpy array of shape (N, D) containing a minibatch of data.
- y: A numpy array of shape (N,) containing training labels; y[i] = c means
that X[i] has label c, where 0 <= c < C.
- reg: (float) regularization strength
-
要实现的公式：
屏幕快照 2017-05-05 上午12.13.32.png - 核心公式f(xi;W) 实现：
scores = X[i].dot(W)
- 那么max(0,f(xi;W)j - f(xi;w)yi + △)的实现就是：
margin = scores[j] - correct_class_score + 1 # note delta = 1
return margin > 0 ? margin : 0
- 所以SVM的简易版本的实现就是：
def svm_loss_naive(W, X, y, reg):
dW = np.zeros(W.shape) # initialize the gradient as zero
# compute the loss and the gradient
num_classes = W.shape[1]
num_train = X.shape[0]
loss = 0.0
for i in xrange(num_train):
scores = X[i].dot(W)
correct_class_score = scores[y[i]]
for j in xrange(num_classes):
if j == y[i]:
continue
margin = scores[j] - correct_class_score + 1 # note delta = 1
if margin > 0:
loss += margin
loss /= num_train
# Add regularization to the loss.
loss += reg * np.sum(W * W)
return loss, dW
- 上面的简易版本，使用了一次循环，如果从效率的角度，可以通过向量实现，来避免循环：
def svm_loss_vectorized(W, X, y, reg):
loss = 0.0
dW = np.zeros(W.shape) # initialize the gradient as zero
scores = X.dot(W) # N by C 样本数*类别数
num_train = X.shape[0]
num_classes = W.shape[1]
scores_correct = scores[np.arange(num_train), y]
scores_correct = np.reshape(scores_correct, (num_train, 1)) # N*1 每个样本的正确类别
margins = scores - scores_correct + 1.0 # N by C 计算scores矩阵中每一处的损失
margins[np.arange(num_train), y] = 0.0 # 每个样本的正确类别损失置0
margins[margins <= 0] = 0.0 # max(0, x)
loss += np.sum(margins) / num_train # 累加所有损失，取平均
loss += 0.5 * reg * np.sum(W * W) # 正则
# compute the gradient
margins[margins > 0] = 1.0 # max(0, x) 大于0的梯度计为1
row_sum = np.sum(margins, axis=1) # N*1 每个样本累加
margins[np.arange(num_train), y] = -row_sum # 类正确的位置 = -梯度累加
dW += np.dot(X.T, margins)/num_train + reg * W # D by C
return loss, dW
源码地址： https://github.com/polegithub/standford_cs231n_assignment
vi> SVM 总览
SVM展开来说可以参照下图：
待续...
