專欄｜李飛飛主講斯坦福大學 CS231n 課程筆記:K 近鄰算法&線性分類
AI 科技評論按：本門課程是李飛飛主講的斯坦福 CS231n 計算機視覺課程，吉林大學珠海學院的趙一帆進行了筆記方面的整理。筆記如有出錯，請及時告知。本文對應章節：數據驅動的圖像分類方式：K 最近鄰與線性分類器。上一章節：計算機視覺歷史回顧與介紹
回到圖片上來討論KNN：
可以看到，它實際上表現的不是很好。這裏標記了紅色和綠色，圖像分類正確與否取決於它的最近鄰值，可以看到 KNN 的表現效果不是很好，但如果使用一個更大的 K 值，那麼投票操作的結果就可能會達到前三名或者前五名，甚至包括所有的數據範圍。
用這種方法來檢索相鄰數據時，可以想象到這樣會對噪聲產生更大的魯棒性。還有另外一個選擇，就是當使用 K-近鄰算法時，確定應該如何比較相對鄰近數據距離值傳遞不同。
對於迄今爲止的例子，已經展示了已經討論過的 L1 距離，它是像素之間絕對值的總和，另一種常見的選擇是 L2 距離，也是歐式距離，即取平方和的平方根，並把這個作爲距離。
選擇不同的距離度量實際上是一個非常有趣的話題，因爲在不同維度裏，會在預測的空間裏對底層的幾何或拓撲結構做出不同的假設。
相對於下面所示的 L1 距離和 L2 距離實際上是一個根據距離的這個圍繞着原點的方形和圓，這個方形上的每一個點在 L1 上是與原點等距的，而距離上類似的會是一個圓，它看起來像你所期望的。
這兩種方法之間特別指出一件有趣的問題：
L1 距離取決於你選擇的座標系統，如果你選擇座標軸，將會改變點之間的 L1 距離，而改變座標軸對 L2 距離毫無影響，無論在怎麼樣的座標下，L2 距離是一個確定的值。
如果輸入一些特徵向量，向量中的一些值有一些重要意義的任務，那麼 L1 也許會更加適合。
但如果它只是某個空間中的一個通用向量，而不知道其中的不同元素的意義，那麼 L2 會更適合些。
還有一點：
通過使用不同的距離度量，可以將 K-最近鄰分類器泛化到許多不同的數據類型上，而不僅僅是向量，不僅僅是圖像。例如，假設想對文本進行分類，那麼只需要用 KNN 指定一個距離函數，這個函數可以測量兩段話或者兩段話之間的距離。因此，簡單的通過指定不同的距離度量，便可以很好地將這個算法應用在基本上任何類型的數據上。
選擇不同的距離度量在幾何學中是一個有趣的問題。
在左邊可以看到一組 L1 距離，右側是使用 L2 距離。
可以看出，分類器的決策邊界其實是相差很大的：
L1 的決策邊界趨向於隨座標軸，這是因爲 L1 取決於對座標的選擇；
L2 對距離的排序並不會受到座標的影響，只是把邊界放置在存在最自然的地方。
如何根據問題和數據來確定這些超參數？
選擇能對訓練集給出高準確率、表現最佳的超參數。這其實是一種非常糟糕的想法，千萬不要這麼做。
例如，在之前的 K-最近鄰分類算法中，假設 K=1，總能完美分類訓練數據，所以如果採用這一策略總是選擇 K=1，但是正如之前案例所見的，在實踐中讓 K 取更大的值，儘管會在訓練集中分錯個別數據，但對於在訓練集中未出現過的數據分類性能更佳，歸根到機器學習中，關心的並不是要儘可能擬合訓練集，而是要讓分類器在訓練集以外的未知數據上表現更好。
另一個想法是把數據分成兩部分，一部分是訓練集，另一部分是測試集，然後在訓練集上用不同的超參數來訓練算法，然後將訓練好的分類器用在測試集上，再選擇一組在測試集上表現最好的超參數。
這似乎是個合理的策略，但事實上也非常糟糕。因爲機器學習的目的是瞭解算法表現如何，所以測試集只是一種預估的方法，即在沒遇到的數據上算法表現會如何，如果採用這種不同的超參數訓練不同算法的策略，然後選擇在測試集上表現最好的超參數，那麼很有可能選擇了一組超參數，只是讓算法在這組測試集上表現良好，但是這組測試集的表現無法代表在權限的未見過的數據上的表現。
更常見的做法是將數據分爲三組：大部分作爲訓練集，然後一個驗證集，一個測試集。在訓練集上用不同的超參數訓練，在驗證集上進行評估，然後選擇一組評估最好的參數，然後再把這組數據放到測試集中跑一跑，這纔是要寫到論文中的數據，這纔是算法在未見過的新數據上的表現。
還有一個設計超參數的方法是交叉驗證。
這個在小數據集上比較常用，在深度學習中並不怎麼常用。它的理念是，取出測試集數據，將整個數據集保留部分作爲最後使用的測試集，對於剩餘的數據分成很多份，在這種情況下，輪流將每一份都當做驗證集。
經過交叉驗證，會得到這樣一張圖：
x 軸表示 K-近鄰分類器中參數 K 值，y 軸表示分類器對於不同 K 在數據上的準確率。在這個例子中，用了 5 次交叉驗證，也就是說對於每個 K 值，都對算法做了 5 次測試來了解表現如何。
使用 K 次交叉驗證也許是一個量化它的好方法，可以觀察到算法在不同驗證集上表現的方差，同時，不光是知道哪樣更好，還能看到算法效果的分佈。
其實，KNN 在圖像分類中很少用到，原因包括剛纔談到的所有問題。一是它在測試時運算時間很長，這和剛剛提到的要求不符；另一個問題在於，像歐幾里得距離或者 L1 距離這樣的衡量標準用在比較圖片上實在不太合適。這種向量化的距離函數不太適合表示圖像之間視覺的相似度。
圖中左邊圖的女生和右邊三張經過不同處理的圖片，如果計算他們和原圖的歐式距離，會得到相同的答案，這並不是想要的。可以感覺出來 L2 不適合表示圖像之間視覺感知的差異。
還有一個問題稱之爲維度災難，如果還記得對 K 近鄰的描述，它有點像訓練點把樣本空間分成幾塊，這意味着，如果希望分類器有根號的結果，需要訓練數據能夠密集地分佈在空間中。否則最鄰近點的實際距離可能會很遠。
問題在於，要想要密集分佈在空間中的數據，意味着需要指數倍地訓練數據。
小結：
我們介紹了 KNN 做圖像分類的基本思路，藉助訓練集的圖片和相應的標記，我們可以預測測試集中數據的分類。
下面將介紹神經網絡，通常會把神經網絡比喻爲玩樂高。
可以將不同種類的神經網絡組件組合在一起，來構建不同的大型卷積網絡，它是在不同類型的深度學習應用中看到的最基本的構建塊之一。這類有關神經網絡的模塊化性質的例子來自於圖像字幕實驗室的一些研究。
輸入一副圖片，然後輸出用於描述圖像的描述性的句子。這類工作是由一個關注圖像的卷積神經網絡和一個只關注語言的循環神經網絡組成的，把這兩個網絡放在一起訓練最後得到一個超級厲害的系統來做一些偉大的事情。
線性分類器是這種參數模型最簡單的例子：
參數模型實際上有兩個不同的部分，以這張圖片爲例子，一組是左邊的貓，還有一組是權重參數，通常叫做 W，有時也叫做 θ。現在要寫一些包含了輸入數據 x 和參數 θ 的函數，就會輸出 10 個數字對應 CIFAR-10 中對應的 10 個類別所對應的分數。根據上述描述，比如說貓的分數更大，表面輸入 x 是貓的可能性更大。
在最近鄰算法的設置中沒有參數，取而代之的是通常會保留所有種類的訓練集並在測試中使用。但是現在，在一個參數化的方法中，將對訓練數據進行總結，並把所有的知識用到這些參數 W 中，在測試的時候，不再需要實際的訓練數據，只需要用到參數 W，這使得模型更有效率，甚至可以運行在手機這樣的小設備上。
在深度學習中，整個描述都是關於函數 F 的正確結構，可以發揮想象來編寫不同的函數形式，用不同的、複雜的方式組合權重和數據，這樣可以對應不同的神經網絡體系結構。
所以 F(X)=Wx 是一個最簡單的線性分類器，如果能把上述方程的維度解出來，前提是圖像是 32*32*3 的輸入值，要取這些值然後把它們展開成一個 3072 項長列向量，想要得出 10 個類的得分。對於該圖像，想要最終得到 10 個數字，從而給出每個類別對應得分情況，也就是說，現在 W 是 10*3072 的矩陣，X 是 3072*10 的矩陣，因此，一旦這兩項相乘，就會得到一個列向量，給 10 個類的分數。
通常會添加一個偏置項，它是一個 10 元素的常向量，它不與訓練數據交互，而只會給一些數據獨立的偏置值。
這裏有一個簡單的例子。左邊是一個簡單的圖像，所以線性分類器的工作是把 2*2 的圖像拉伸成一個有四個元素的列向量。
假設這裏例子中只有三類，現在權重矩陣是 3*4，可以把線性分類理解爲幾乎是一種模板匹配的方法，這個矩陣中的每一行對應於圖像的某個模板。根據輸入矩陣行列之間的乘積或者點積，從而得到圖像的像素點。計算這個點積，可以得到在這個類模板和圖像的像素之間，有一個相似之處，然後偏置給這個數據對立縮放比例以及每個類的偏置移量。
如果根據這個模板匹配的觀點，考慮分類器，實際上，可以取這個權重矩陣的行向量，並且將他們還原爲圖像。這個例子中，在圖像上訓練好一個線性分類器，下方是數據集中訓練到的權重矩陣中的行向量對應於 10 個類別相關的可視化結果。
舉例來說，飛機類別的模板似乎由中間類似藍色斑點狀圖形和藍色背景組成，這就產生一種飛機的線性分類器可能在尋找藍色圖形和斑點狀圖形的感覺，然後這些行爲使得這個分類器更像飛機。車子類別的模板能夠看到在中間有一個紅色斑點狀物體以及在頂部是一個擋風玻璃的藍色斑點狀物體。
但這些看起來很奇怪，它不像一個真正的東西，所以就存在這樣一個問題，線性分類器每個類別只能學習一個模板，如果這個類別出現了某種類型的變體，那麼它將嘗試求取所有那些不同變體的平均值，並且只使用一個單獨的模板來識別其中的每一類別。
另一個關於分類器的觀點：
迴歸到圖像，作爲點和高緯空間的概念，可以想象成每一張圖像都是高維空間中一個點，現在這個分類器在這些線性決策邊界上嘗試畫一個線性分類面來劃分一個類別和剩餘其他類別。在左上角，看到用來訓練的飛機樣例，通過訓練，這個分類器會嘗試繪製這條藍色直線用以劃分飛機與其他類別。
如果觀察訓練過程，這些線條會隨機地開始，然後快速變換，試圖將數據正確區分開。
但是當從這個高維空間角度來考慮線性分類器，就能再次看到線性分類器中可能出現的問題：
要構造一個線性分類器完全失效數據樣例並不難。在左邊，假設有一個兩類別的數據集，這些數據可能全部，也可能部分是人爲的。數據集有紅色和藍色兩類，藍色類是圖像中像素的數量，這個數字大於 0 並且是奇數，任何像素個數大於 0 的圖像都歸爲紅色類別。
如果真的去畫這些不同的決策區域，能看到奇數像素點的藍色類別在平面上有兩個象限，甚至是兩個相反的象限。所以，沒有辦法畫出一條獨立的直線來劃分藍色和紅色，這是線性分類器的困境。
線性分類器難以解決的其他情況是多分類問題。在右側，可能藍色類別存在於三個不同的象限，然後其他所有都是另外一個類別。所以對於在之前的例子中看到的像馬匹這樣的東西，當然在現實中某種情況下也會出現，在馬匹的像素空間中，可能一個頭向左看，另一個頭向右看。目前還沒有較好的方法可以在這兩個類別之間繪製一條單獨的線性邊界。
當有多模態數據時，這也是線性分類器可能有困境的地方。
線性分類器存在很多問題，但它是一個超級簡單的算法，易於使用和理解。
