1. 背景
CS231n的全稱是:
Convolutional Neural Networks for Visual Recognition，
面向視覺識別的卷積神經(jīng)網(wǎng)絡(luò)
這篇文章只是記錄了自己學(xué)習(xí) cs231n 課程的一些筆記或者自己的一些想法。如果想看完整的筆記,知乎有人做了很詳細(xì)的翻譯版本，請移步這里
機(jī)器學(xué)習(xí)翻來覆去，其實(shí)就是那么些算法，這門課，主要是講在視覺識別領(lǐng)域，如何使用這些算法進(jìn)行識別和調(diào)優(yōu)。從最簡單的KNN到神經(jīng)網(wǎng)絡(luò)以及卷積神經(jīng)等。說白了，如果這些算法已經(jīng)掌握的很牛逼了，那么我感覺，高手們學(xué)習(xí)這門課大概也就幾個小時的時間，就可以吃透了。
2. 視頻鏈接
內(nèi)容其實(shí)是一樣的，只是英文不是很好的同學(xué)，可以看這個網(wǎng)易云課堂的版本
3. 正文：深度學(xué)習(xí)與計(jì)算機(jī)視覺
3.1 引入
3.1.1 圖像分類算法總覽
拿到一個圖像，我們怎么知道他是個動物還是風(fēng)景，是張三還是隔壁老王。因?yàn)槲覀兊臄?shù)據(jù)庫不可能有一模一樣的圖像，所以只能看它和哪個或者哪些圖像最接近，我們就把他歸類到這種圖像中。
這種行為稱之為“分類”。那我們怎么分類呢？分類有哪些算法呢？
機(jī)器學(xué)習(xí)中的分類算法非常多：
這個圖基本列舉了常見的machine learning的算法，大體分為4類,分別是:
classification (分類)，
clustering (聚類),
regression (回歸),
dimensionality reduction (降維)
其中，
分類和回歸的區(qū)別是：分類是離散的，回歸是連續(xù)的。
分類和聚類的區(qū)別是：分類是監(jiān)督學(xué)習(xí)（有可供參考的類別標(biāo)簽的），聚類是無監(jiān)督學(xué)習(xí)（沒有可供參考的類別標(biāo)簽）；
補(bǔ)充1：回歸也屬于監(jiān)督學(xué)習(xí)，聚類和分類都是離散的。
補(bǔ)充2：降維，這塊還沒學(xué)懂，有監(jiān)督的算法也有無監(jiān)督的算法。暫且不展開討論。
這里不會給大家展開所有的算法，只是先整體有個大概，課程真正的展開是從KNN開始的，
這個是個很簡單的算法，從這里入門，便于后續(xù)的深入研究。
3.1.2 學(xué)習(xí)前的準(zhǔn)備
首先想這么一個問題：
我們?nèi)绾伪容^2幅圖的區(qū)別？
比較直觀的思路是：圖的本質(zhì)就是RGB的組合，每個像素點(diǎn)就是一個RGB值，然后以像素點(diǎn)為單位，一個圖就可以擴(kuò)展為一個m*n的矩陣（假設(shè)橫向m個像素，縱向n個像素），為了方便比較，我們統(tǒng)一把所有的圖都可以整理為m*n的矩陣。那么圖像分析問題就轉(zhuǎn)換為矩陣比較問題:
如何確認(rèn)2個矩陣是相近或者屬于同類的?
我的第一反應(yīng)就是，直接求差。你想啊，如果2個矩陣完全相等，那么求差的結(jié)果就是個零矩陣啊。就像手寫數(shù)字識別一樣，你的test數(shù)據(jù)轉(zhuǎn)換為矩陣A，如果train數(shù)據(jù)為矩陣B， A-B=[0,…0],那么A樣本必然和B屬于同類啊。
Notes: 這個思路擴(kuò)展下去，其實(shí)就是2個矩陣求曼哈頓距離（后面會談到的L1公式）
屏幕快照 2017-04-25 上午12.01.21.png
但這個是理想情況，那么如果test數(shù)據(jù)和train數(shù)據(jù)比較發(fā)現(xiàn)，和好幾個樣本的差值都比較接近，（而且關(guān)鍵的一點(diǎn)是，差值可正可負(fù)），那怎么定義A的分類呢？
如此說來，求差值必然是不完整的，那么怎么辦？差值求出來求絕對值？嗯，好像有點(diǎn)接近，但本質(zhì)上和直接求差沒有太大區(qū)別。
那么換個思路，我們放到幾何中去考慮，其實(shí)本質(zhì)就是求2點(diǎn)距離的問題，對吧。 這個從小就學(xué)過，點(diǎn)A和點(diǎn)B的距離，橫縱坐標(biāo)差的平方和再開方。
Notes: 這個思路擴(kuò)展下去，其實(shí)就是2個矩陣求歐式距離（下面會談到的L2公式）
那么總結(jié)下來，好像我們也不需要懂什么機(jī)器學(xué)習(xí)的理論，客觀分析，其實(shí)也能大概想到一些解決類似問題的方法。
這個思路擴(kuò)展下去，就是CS231n后面要講的KNN算法。當(dāng)然實(shí)際算法，在距離的算法上有一些新的擴(kuò)展，但原理都是一樣的。
3.2 機(jī)器學(xué)習(xí)的常見算法實(shí)現(xiàn)
3.2.1 KNN臨近算法（K-Nearest Neighbor）
3.2.1.1 理論
對應(yīng)知乎筆記：CS231n課程筆記翻譯：圖像分類筆記（上）
這個算法的本質(zhì)就是“近朱者赤”，從臨近范圍內(nèi)（這個范圍可以通過L1公式或者L2公式進(jìn)行計(jì)算）的對象看看哪個占比高，就用那個作為其類別。
其中的關(guān)鍵是K,就是選擇幾個樣本的問題，本質(zhì)就是臨近范圍選擇多少的問題。
L1,L2公式說明：
L1：曼哈頓距離(wiki解釋)
簡單說就是矩陣直接求差，該公式俗稱出租車距離，地圖上A.B兩點(diǎn)的距離，出租車不可能直線穿過去，只能橫向縱向走，所以就有這個公式。
L2：歐式距離（wiki解釋）
這個應(yīng)該大家都學(xué)過（空間2點(diǎn)的直線距離），這里不贅述了。
課程的后半段：
其中提到了幾個建議的方法，比如交叉驗(yàn)證什么的，這些都是一些優(yōu)化訓(xùn)練的方法，這會知道了最好，不知道也沒關(guān)系，實(shí)際把數(shù)據(jù)玩起來，這些方法無形中自然會知道。
所以本章節(jié)的關(guān)鍵是，知道KNN算法，并且能實(shí)現(xiàn)它。然后知道他在實(shí)際中并不怎么用。（畢竟這算法也太簡單了，做出來的結(jié)果準(zhǔn)確率太低?。?導(dǎo)師還專門強(qiáng)調(diào)了不要在圖像識別上使用KNN算法。
3.2.1.2 KNN算法 python實(shí)現(xiàn)
知道原理， 算法實(shí)現(xiàn)起來很簡單。 這里簡單交代下背景：
inX: 是輸入的測試向量
dataSet: 是訓(xùn)練數(shù)據(jù)集合（array）
labels: 是訓(xùn)練樣本的對應(yīng)標(biāo)簽（array）
k: 是選擇樣本的個數(shù)
其他：python的tile函數(shù)用于生成指定維度的重復(fù)數(shù)組，sum(axis=1)是按行求和
然后，實(shí)現(xiàn)算法：
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)
關(guān)鍵步驟：
最為關(guān)鍵的是計(jì)算目標(biāo)矩陣和臨近矩陣的距離，上面的代碼只是一個普通的實(shí)現(xiàn)方式，如果深思的話，會有多種實(shí)現(xiàn)方式.
這門課程的作業(yè)1，要求通過3種循環(huán)方式實(shí)現(xiàn)距離的計(jì)算：
def predict(self, X, k=1, num_loops=0):
# 根據(jù)傳入的num_loops，決定使用哪種計(jì)算方式
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熟悉的同學(xué)除外），本身絞盡腦汁才想出來一種最為普通的方式。
現(xiàn)在卻還要用到不同的循環(huán)方式，完全是get不到點(diǎn)在哪里。
后來查了很多的資料，各種stackoverflow，各種blog才是搞清楚。主要原因是本人對numpy完全不熟悉，所以對于矩陣的計(jì)算不甚了解，之前一直僅僅是把矩陣當(dāng)做數(shù)組來說思考處理的，但實(shí)際numpy提供了很多便捷的方法。
言歸正傳： 本質(zhì)是求兩個矩陣的歐氏距離，那我們的矩陣是長什么樣的呢？
我們的數(shù)據(jù)來源是kaggle的CIFAR-10數(shù)據(jù)集,通過下面這個shell腳本，（或直接去kaggle搜索CIFAR-10），獲取數(shù)據(jù)：
# 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像素的，然后，上文提到過，我們每個圖片本質(zhì)就是RGB，所以還需要每個像素3個RGB值，這樣表示我們的圖片集，可以用一個5000*32*32*3的四維矩陣來表示，直觀的看就是這樣：
對應(yīng)的矩陣，直觀感受下就好：
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：
看到這個矩陣和圖片之后，估計(jì)大家可以較為簡單的想到一個計(jì)算方法：就是每個圖片彼此求距離啊，那么假設(shè)有10個測試數(shù)據(jù)，20個訓(xùn)練數(shù)據(jù)，那么2個for循環(huán)，取出來圖片一一求距離，就可以了：
# 代碼比較簡單，就不細(xì)說了
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：
其實(shí)，第一個算法想出來之后，第二個原理上是和第一個一樣的， 也是取出來測試的圖片，逐個和訓(xùn)練集求距離，只是基于numpy的方法，可以更簡單的實(shí)現(xiàn)：
diffValue = X[i, :] - self.X_train
所以用一個循環(huán)實(shí)現(xiàn)的距離計(jì)算代碼是：
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：
最后一個不用循環(huán)，直接求距離的方法，其實(shí)是對考察對數(shù)學(xué)的了解程程度了，兩個矩陣的歐式距離：
||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種循環(huán)方式分別進(jìn)行了實(shí)現(xiàn)，當(dāng)然這3種算法，效率上也是有很大差別的，我實(shí)際跑下來的時間：
可以看到，向量的實(shí)現(xiàn)算法比其他算法在效率上有顯著的優(yōu)勢。
至于為什么？ 后面抽個專題講講運(yùn)行效率吧。
3.2.1.3 總結(jié)
總體來說，KNN應(yīng)該是入門里面最為容易理解的算法之一了，不太需要太多的數(shù)學(xué)功底，基本就是你如何進(jìn)行矩陣求差的問題。實(shí)際工作中雖然也用的不多，但是如果你數(shù)據(jù)量不大，而且只是想先大概估算某個數(shù)據(jù)的大致概率或者分布，可以臨時用這個快速實(shí)現(xiàn)一些簡單需求。
3.2.1 線性函數(shù)：SVM算法（支持向量機(jī)）
3.2.1.1 理論
i> Support vector machine, 支持向量機(jī)
所屬類別： supervised learning 監(jiān)督學(xué)習(xí)
所屬范疇： classification
iii> 具體要解釋的話，套用竇娥的一句話：
天,你不分黑白何為天; 地,你不辨忠奸枉為地
簡單說，就是個分類算法，畫地為牢，尋找一條分割線，分出類別。那怎么找出來這條線呢？
桌子上有一堆蘋果和香蕉，給你一把尺子，最大限度的將其分開，那怎么分？ 這個很簡單，直接從最中間的點(diǎn)入手，左右調(diào)整調(diào)整就找出最可靠的分法了對吧，基本是這樣一張圖：
那如果從數(shù)學(xué)或者幾何的角度怎么理解這個東西呢？
首先，蘋果和香蕉離得最近或者有重合的部分，沿著這些點(diǎn)，基本能大致確定分割線的方向和路徑，然后做一些微調(diào)就好。那這樣的一件事或者一個行為，稱之為machine，其中，離這個分割線比較近的蘋果或者香蕉稱之為supooer vector(支持向量)，因?yàn)檫@些support vector的友情支持和協(xié)助，才能方便我們快速確定分割線。（說白了，簡單粗暴點(diǎn)，直接把support vector連點(diǎn)成線，其實(shí)就已經(jīng)是個分割線了，只是有點(diǎn)糙而已）
所以SVM就是“支持向量”的“機(jī)器(分類器)”，千萬不要理解成“支持”了“向量機(jī)”。
iv> 數(shù)學(xué)計(jì)算
知道了定義，那么數(shù)學(xué)角度，怎么求出這么一條分割下來？
首先來分析，就這條線，處于最中間的位置，意思就是距離是距離兩邊是相等的，或近似相等的。轉(zhuǎn)化為求distanceApple和distanceBanana相等的曲線函數(shù)：
轉(zhuǎn)來一段知乎大拿的解釋：
其實(shí)關(guān)鍵的部分是SMO相關(guān)的數(shù)學(xué)推導(dǎo)，推薦大家可以看一下這個博客：
支持向量機(jī)通俗導(dǎo)論（理解SVM的三層境界）
最終的損失函數(shù)公式是：
v> python 實(shí)現(xiàn)
一言不合上代碼：
把上面的公式一步步翻譯成代碼：
- 交代背景：
# 我們有N個圖片樣本，C種類別，D個維度
# classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
# D = 32 * 32 *3 (每個圖32*32像素，每個像素有RGB3種顏色構(gòu)成)
- 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
-
要實(shí)現(xiàn)的公式：
屏幕快照 2017-05-05 上午12.13.32.png - 核心公式f(xi;W) 實(shí)現(xiàn)：
scores = X[i].dot(W)
- 那么max(0,f(xi;W)j - f(xi;w)yi + △)的實(shí)現(xiàn)就是：
margin = scores[j] - correct_class_score + 1 # note delta = 1
return margin > 0 ? margin : 0
- 所以SVM的簡易版本的實(shí)現(xiàn)就是：
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
- 上面的簡易版本，使用了一次循環(huán)，如果從效率的角度，可以通過向量實(shí)現(xiàn)，來避免循環(huán)：
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 樣本數(shù)*類別數(shù)
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 計(jì)算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的梯度計(jì)為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展開來說可以參照下圖：
待續(xù)...
