1. 為什么KNN值得單獨(dú)拿出來(lái)寫一篇筆記很多人第一次接觸cs231n作業(yè)1的時(shí)候注意力都被后面的兩層神經(jīng)網(wǎng)絡(luò)或者圖像特征部分吸引走了覺(jué)得KNN這個(gè)算法太簡(jiǎn)單sklearn調(diào)個(gè)包就完事了。但我實(shí)際做下來(lái)發(fā)現(xiàn)KNN這部分恰恰是整個(gè)作業(yè)1里最能幫你建立向量化思維和距離度量直覺(jué)的模塊。它看起來(lái)簡(jiǎn)單但當(dāng)你真的要從零實(shí)現(xiàn)一個(gè)不依賴任何循環(huán)的向量化版本時(shí)坑一個(gè)接一個(gè)。這篇筆記面向的是正在做或者準(zhǔn)備做cs231n作業(yè)1的讀者也適合任何想真正搞懂KNN底層實(shí)現(xiàn)細(xì)節(jié)的人。我會(huì)把KNN在CIFAR-10上的完整流程拆開(kāi)講——從數(shù)據(jù)加載、距離矩陣計(jì)算、交叉驗(yàn)證調(diào)參到最終的可視化驗(yàn)證。重點(diǎn)不是告訴你調(diào)這個(gè)函數(shù)就行而是把每一步為什么這么做、參數(shù)怎么選、踩過(guò)什么坑都講清楚。KNN的核心思想其實(shí)一句話就能說(shuō)清給定一張測(cè)試圖片找到訓(xùn)練集中跟它最像的K張圖片然后讓這K張圖片投票決定測(cè)試圖片的類別。但最像怎么定義、K張?jiān)趺催x、投票怎么投每一個(gè)環(huán)節(jié)都有講究。下面我按實(shí)際做作業(yè)的順序一步步展開(kāi)。2. 數(shù)據(jù)準(zhǔn)備與預(yù)處理的關(guān)鍵細(xì)節(jié)2.1 CIFAR-10數(shù)據(jù)集的加載與結(jié)構(gòu)理解cs231n作業(yè)1用的是CIFAR-10數(shù)據(jù)集包含60000張32x32的彩色圖片分10個(gè)類別每個(gè)類別6000張。官方給的數(shù)據(jù)格式是pickle文件加載之后你會(huì)得到一個(gè)字典里面有幾個(gè)關(guān)鍵的keydata、labels、batch_label。data的形狀是N×3072這里的3072就是32×32×3展開(kāi)成一維的結(jié)果。這里第一個(gè)容易困惑的點(diǎn)是為什么是3072而不是32×32×3分開(kāi)存因?yàn)楹罄m(xù)計(jì)算距離的時(shí)候我們需要把每張圖片當(dāng)成一個(gè)3072維的向量來(lái)處理。展開(kāi)成一維之后兩張圖片之間的歐氏距離就是這3072個(gè)維度上差值的平方和開(kāi)根號(hào)。這個(gè)展開(kāi)順序是RGB通道分別展平的也就是說(shuō)前1024個(gè)數(shù)是R通道中間1024個(gè)是G通道最后1024個(gè)是B通道。你在做可視化的時(shí)候必須按這個(gè)順序reshape回去否則顏色會(huì)亂掉。加載數(shù)據(jù)的代碼大概長(zhǎng)這樣import pickle import numpy as np def load_cifar10_batch(filepath): with open(filepath, rb) as f: datadict pickle.load(f, encodingbytes) X datadict[bdata] Y datadict[blabels] X X.reshape(10000, 3, 32, 32).transpose(0, 2, 3, 1).astype(float) Y np.array(Y) return X, Y注意這里有個(gè)transpose(0, 2, 3, 1)的操作把原來(lái)的(N, C, H, W)轉(zhuǎn)成(N, H, W, C)。為什么要轉(zhuǎn)因?yàn)楹竺婵梢暬臅r(shí)候用matplotlib顯示圖片它期望的格式是(H, W, C)。如果你不轉(zhuǎn)顯示出來(lái)的圖片顏色通道就錯(cuò)位了。2.2 數(shù)據(jù)劃分與采樣策略作業(yè)要求把50000張訓(xùn)練集再拆出一部分做驗(yàn)證集。標(biāo)準(zhǔn)做法是取最后5000張作為驗(yàn)證集前45000張作為訓(xùn)練集。但實(shí)際調(diào)試的時(shí)候我強(qiáng)烈建議你先從訓(xùn)練集里采樣一個(gè)很小的子集來(lái)跑通流程比如只取500張訓(xùn)練、100張測(cè)試。原因很簡(jiǎn)單KNN的計(jì)算量隨訓(xùn)練集大小線性增長(zhǎng)你如果一上來(lái)就用45000張跑光是距離矩陣計(jì)算就能讓你等好幾分鐘調(diào)參的時(shí)候根本受不了。采樣的時(shí)候要注意類別平衡。CIFAR-10每個(gè)類別的樣本數(shù)是一樣的如果你隨機(jī)采樣導(dǎo)致某些類別樣本過(guò)少驗(yàn)證準(zhǔn)確率會(huì)波動(dòng)很大。我一般用每個(gè)類別取相同數(shù)量的方式來(lái)做子采樣這樣得到的準(zhǔn)確率更有參考價(jià)值。還有一個(gè)細(xì)節(jié)數(shù)據(jù)要不要?dú)w一化對(duì)于KNN來(lái)說(shuō)如果你用的是歐氏距離特征的尺度會(huì)直接影響距離計(jì)算。CIFAR-10的像素值范圍是0到255不同通道之間的尺度差異不大所以歸一化不是必須的。但如果你后面要跟其他特征拼接比如HOG特征那就必須做標(biāo)準(zhǔn)化否則量綱大的特征會(huì)主導(dǎo)距離計(jì)算。我在做作業(yè)1的時(shí)候試過(guò)歸一化和不歸一化在純像素上差別不大準(zhǔn)確率波動(dòng)在1%以內(nèi)。3. 距離計(jì)算的兩種實(shí)現(xiàn)與性能對(duì)比3.1 雙循環(huán)版本的實(shí)現(xiàn)與理解KNN最核心的計(jì)算就是測(cè)試樣本和訓(xùn)練樣本之間的距離矩陣。假設(shè)訓(xùn)練集有N張圖測(cè)試集有M張圖那距離矩陣的維度就是M×N。最直觀的實(shí)現(xiàn)是兩層循環(huán)def compute_distances_two_loops(X_train, X_test): num_test X_test.shape[0] num_train X_train.shape[0] dists np.zeros((num_test, num_train)) for i in range(num_test): for j in range(num_train): diff X_test[i] - X_train[j] dists[i, j] np.sqrt(np.sum(diff ** 2)) return dists這個(gè)版本最好理解就是老老實(shí)實(shí)算每對(duì)圖片之間的歐氏距離。但它的性能極差在45000×5000的規(guī)模下Python的雙層循環(huán)大概要跑好幾分鐘。不過(guò)它的價(jià)值在于你可以用它來(lái)驗(yàn)證后面向量化版本的正確性。我每次寫完向量化版本都會(huì)先用小規(guī)模數(shù)據(jù)跟雙循環(huán)版本對(duì)比一下確保結(jié)果一致。這里有個(gè)小坑np.sqrt(np.sum(diff ** 2))和np.linalg.norm(diff)是等價(jià)的但后者在某些numpy版本上會(huì)慢一點(diǎn)點(diǎn)。另外如果你不需要開(kāi)根號(hào)比如只比較距離大小可以省掉sqrt因?yàn)槠椒骄嚯x的排序和距離的排序是一樣的。但在KNN里我們需要真實(shí)的距離值來(lái)做閾值判斷所以還是得開(kāi)。3.2 單循環(huán)版本的優(yōu)化思路單循環(huán)版本的核心思路是每次處理一張測(cè)試圖片但把跟所有訓(xùn)練圖片的距離計(jì)算向量化。def compute_distances_one_loop(X_train, X_test): num_test X_test.shape[0] num_train X_train.shape[0] dists np.zeros((num_test, num_train)) for i in range(num_test): diff X_train - X_test[i] dists[i, :] np.sqrt(np.sum(diff ** 2, axis1)) return dists這里的關(guān)鍵是X_train - X_test[i]利用了numpy的廣播機(jī)制得到一個(gè)(N, 3072)的矩陣然后沿axis1求和得到N個(gè)距離值。這個(gè)版本比雙循環(huán)快了幾十倍因?yàn)閮?nèi)層循環(huán)被numpy的底層C實(shí)現(xiàn)替代了。但要注意內(nèi)存問(wèn)題當(dāng)N45000的時(shí)候X_train - X_test[i]會(huì)臨時(shí)創(chuàng)建一個(gè)45000×3072的矩陣大概占500MB內(nèi)存。如果你的機(jī)器內(nèi)存不夠這個(gè)操作可能會(huì)觸發(fā)swap反而變慢。我一般會(huì)確保至少有8GB可用內(nèi)存再跑這個(gè)版本。3.3 完全向量化版本的數(shù)學(xué)推導(dǎo)完全向量化版本是作業(yè)1里最精華的部分也是面試?？嫉狞c(diǎn)。核心公式是$$||a - b||^2 ||a||^2 ||b||^2 - 2a \cdot b$$把測(cè)試集矩陣記為$X_{test}$M×D訓(xùn)練集矩陣記為$X_{train}$N×D那么距離矩陣的平方可以寫成$$D^2 \text{sum}(X_{test}^2, \text{axis}1)[:, \text{None}] \text{sum}(X_{train}^2, \text{axis}1)[\text{None}, :] - 2 X_{test} X_{train}^T$$對(duì)應(yīng)的代碼def compute_distances_no_loops(X_train, X_test): train_sq np.sum(X_train ** 2, axis1) test_sq np.sum(X_test ** 2, axis1) cross X_test.dot(X_train.T) dists np.sqrt(test_sq[:, None] train_sq[None, :] - 2 * cross) return dists這個(gè)版本跑45000×5000的距離矩陣只需要幾秒鐘。但有一個(gè)隱藏的坑由于浮點(diǎn)數(shù)精度問(wèn)題test_sq[:, None] train_sq[None, :] - 2 * cross可能會(huì)算出很小的負(fù)數(shù)比如-1e-12然后sqrt就會(huì)產(chǎn)生nan。解決辦法是在sqrt之前加一個(gè)clipdists np.sqrt(np.maximum(dists, 0))這個(gè)坑我在第一次做的時(shí)候踩得很慘距離矩陣?yán)锍霈F(xiàn)了一堆nan導(dǎo)致后續(xù)預(yù)測(cè)全部出錯(cuò)排查了半天才發(fā)現(xiàn)是數(shù)值精度問(wèn)題。3.4 三種實(shí)現(xiàn)的性能對(duì)比我在同一臺(tái)機(jī)器上8核CPU16GB內(nèi)存用5000張訓(xùn)練、500張測(cè)試的數(shù)據(jù)跑了三種實(shí)現(xiàn)結(jié)果如下實(shí)現(xiàn)方式耗時(shí)相對(duì)加速比內(nèi)存占用雙循環(huán)約45秒1x低單循環(huán)約1.2秒約37x中完全向量化約0.08秒約560x高這個(gè)對(duì)比很直觀地說(shuō)明了向量化的重要性。但要注意完全向量化版本在訓(xùn)練集特別大的時(shí)候比如全量45000張內(nèi)存占用會(huì)很高因?yàn)橐瑫r(shí)存儲(chǔ)M×N的距離矩陣。如果內(nèi)存吃緊可以考慮分塊計(jì)算每次只算一部分測(cè)試樣本的距離。4. 交叉驗(yàn)證調(diào)參與預(yù)測(cè)邏輯4.1 K值選擇的交叉驗(yàn)證流程KNN里最重要的超參數(shù)就是K。K太小模型對(duì)噪聲敏感容易過(guò)擬合K太大決策邊界過(guò)于平滑容易欠擬合。作業(yè)要求用交叉驗(yàn)證來(lái)選K具體做法是把訓(xùn)練集分成5折每次用4折訓(xùn)練、1折驗(yàn)證取平均準(zhǔn)確率最高的K。def cross_validate(X_train, y_train, k_choices, num_folds5): fold_size X_train.shape[0] // num_folds k_to_accuracies {k: [] for k in k_choices} for fold in range(num_folds): val_start fold * fold_size val_end (fold 1) * fold_size X_val X_train[val_start:val_end] y_val y_train[val_start:val_end] X_tr np.concatenate([X_train[:val_start], X_train[val_end:]]) y_tr np.concatenate([y_train[:val_start], y_train[val_end:]]) dists compute_distances_no_loops(X_tr, X_val) for k in k_choices: y_pred predict_labels(dists, y_tr, kk) acc np.mean(y_pred y_val) k_to_accuracies[k].append(acc) return k_to_accuracies這里有個(gè)實(shí)操細(xì)節(jié)交叉驗(yàn)證的時(shí)候每次都要重新計(jì)算距離矩陣因?yàn)橛?xùn)練集變了。如果你用全量數(shù)據(jù)算一次距離矩陣然后復(fù)用那是不對(duì)的因?yàn)轵?yàn)證集的樣本在訓(xùn)練時(shí)不應(yīng)該被看到。我一開(kāi)始為了省時(shí)間想復(fù)用距離矩陣后來(lái)發(fā)現(xiàn)準(zhǔn)確率偏高才意識(shí)到這個(gè)問(wèn)題。K的候選值一般取[1, 3, 5, 8, 10, 12, 15, 20, 50, 100]。在CIFAR-10上我實(shí)測(cè)下來(lái)K10左右通常表現(xiàn)最好準(zhǔn)確率大概在28%到30%之間。這個(gè)數(shù)字看起來(lái)很低但要知道CIFAR-10有10個(gè)類別隨機(jī)猜的準(zhǔn)確率是10%KNN能到28%已經(jīng)說(shuō)明像素層面的相似性確實(shí)包含了一些判別信息。4.2 預(yù)測(cè)函數(shù)的實(shí)現(xiàn)與投票機(jī)制預(yù)測(cè)函數(shù)的邏輯是對(duì)每個(gè)測(cè)試樣本找到距離最近的K個(gè)訓(xùn)練樣本然后看這K個(gè)樣本里哪個(gè)類別最多就預(yù)測(cè)為哪個(gè)類別。def predict_labels(dists, y_train, k1): num_test dists.shape[0] y_pred np.zeros(num_test) for i in range(num_test): closest_y y_train[np.argsort(dists[i])[:k]] y_pred[i] np.argmax(np.bincount(closest_y)) return y_pred這里有幾個(gè)細(xì)節(jié)值得說(shuō)。np.argsort返回的是排序后的索引取前K個(gè)就得到了最近的K個(gè)訓(xùn)練樣本的索引。np.bincount統(tǒng)計(jì)每個(gè)類別出現(xiàn)的次數(shù)np.argmax取最多的那個(gè)。但np.bincount要求輸入是非負(fù)整數(shù)如果你的標(biāo)簽是浮點(diǎn)數(shù)得先轉(zhuǎn)成int。還有一個(gè)投票平局的問(wèn)題如果K個(gè)鄰居里兩個(gè)類別的票數(shù)一樣多np.argmax會(huì)返回索引較小的那個(gè)。這在實(shí)踐中影響不大但如果你追求嚴(yán)謹(jǐn)可以隨機(jī)選一個(gè)或者按距離加權(quán)投票。距離加權(quán)投票的思路是距離越近的鄰居話語(yǔ)權(quán)越大權(quán)重可以取距離的倒數(shù)。我試過(guò)加權(quán)投票在CIFAR-10上準(zhǔn)確率提升了不到0.5%但計(jì)算量增加了一些所以作業(yè)里用簡(jiǎn)單投票就夠了。4.3 準(zhǔn)確率評(píng)估與結(jié)果解讀最終在測(cè)試集上的準(zhǔn)確率用K10大概能到28%左右。這個(gè)結(jié)果說(shuō)明兩個(gè)問(wèn)題第一原始像素層面的KNN確實(shí)能捕捉到一些類別間的差異比如汽車和船的像素分布差異比較大第二KNN的天花板很低因?yàn)橄袼鼐嚯x并不能很好地反映語(yǔ)義相似性一張稍微平移過(guò)的貓的圖片在像素空間里可能跟另一張貓的圖片距離很遠(yuǎn)。作業(yè)里還要求可視化一些錯(cuò)誤分類的案例。我看了之后發(fā)現(xiàn)很多錯(cuò)誤是因?yàn)楸尘案蓴_。比如一張馬的圖片背景是大片綠色草地KNN可能會(huì)把它分到鹿或者青蛙類別因?yàn)榫G色像素占比很高。這也解釋了為什么后面要引入顏色直方圖或者HOG特征來(lái)提升KNN的表現(xiàn)。5. 實(shí)操中踩過(guò)的坑與排查技巧5.1 距離矩陣出現(xiàn)nan的排查前面提到過(guò)完全向量化版本因?yàn)楦↑c(diǎn)精度問(wèn)題可能產(chǎn)生nan。排查方法很簡(jiǎn)單在sqrt之前檢查是否有負(fù)數(shù)。dists_sq test_sq[:, None] train_sq[None, :] - 2 * cross print(np.min(dists_sq)) # 如果輸出是負(fù)數(shù)說(shuō)明有精度問(wèn)題解決辦法就是加np.maximum(dists_sq, 0)。這個(gè)坑的隱蔽性在于它只在某些數(shù)據(jù)上出現(xiàn)而且nan會(huì)傳播到后續(xù)所有計(jì)算導(dǎo)致準(zhǔn)確率變成0或者報(bào)錯(cuò)。我建議在寫完向量化版本后先用小數(shù)據(jù)跑一遍檢查距離矩陣?yán)镉袥](méi)有nan。5.2 內(nèi)存不足與分塊計(jì)算當(dāng)訓(xùn)練集是全量45000張、測(cè)試集是5000張的時(shí)候距離矩陣是5000×45000每個(gè)元素是float64大概占1.8GB內(nèi)存。加上中間變量峰值內(nèi)存可能超過(guò)4GB。如果你的機(jī)器內(nèi)存不夠可以分塊計(jì)算def compute_distances_chunked(X_train, X_test, chunk_size500): num_test X_test.shape[0] num_train X_train.shape[0] dists np.zeros((num_test, num_train)) train_sq np.sum(X_train ** 2, axis1) for start in range(0, num_test, chunk_size): end min(start chunk_size, num_test) X_chunk X_test[start:end] test_sq np.sum(X_chunk ** 2, axis1) cross X_chunk.dot(X_train.T) dists[start:end] np.sqrt(np.maximum( test_sq[:, None] train_sq[None, :] - 2 * cross, 0)) return dists這樣每次只處理500張測(cè)試圖片內(nèi)存占用降到原來(lái)的十分之一。代價(jià)是稍微慢一點(diǎn)因?yàn)檠h(huán)次數(shù)增加了但總體還是比單循環(huán)快很多。5.3 交叉驗(yàn)證中的常見(jiàn)錯(cuò)誤交叉驗(yàn)證最容易犯的錯(cuò)誤是數(shù)據(jù)泄露。比如你在劃分折之前就對(duì)整個(gè)訓(xùn)練集做了歸一化那驗(yàn)證集的信息就泄露到了訓(xùn)練過(guò)程中。正確的做法是先劃分折然后在每折內(nèi)部單獨(dú)做歸一化用訓(xùn)練折的均值和方差去標(biāo)準(zhǔn)化驗(yàn)證折。另一個(gè)錯(cuò)誤是K值選擇時(shí)的過(guò)擬合。如果你用測(cè)試集來(lái)選K那選出來(lái)的K在測(cè)試集上表現(xiàn)很好但這不是真實(shí)的泛化性能。作業(yè)里明確要求用驗(yàn)證集選K最后再用測(cè)試集評(píng)估一次。我見(jiàn)過(guò)有人直接用測(cè)試集調(diào)參然后報(bào)告測(cè)試準(zhǔn)確率這是不嚴(yán)謹(jǐn)?shù)摹?.4 常見(jiàn)問(wèn)題速查表問(wèn)題現(xiàn)象可能原因解決方法距離矩陣出現(xiàn)nan浮點(diǎn)精度導(dǎo)致負(fù)數(shù)開(kāi)根號(hào)sqrt前加np.maximum(dists, 0)準(zhǔn)確率異常低接近10%距離計(jì)算錯(cuò)誤或標(biāo)簽錯(cuò)位用雙循環(huán)版本對(duì)比驗(yàn)證內(nèi)存溢出距離矩陣太大分塊計(jì)算或減小數(shù)據(jù)集交叉驗(yàn)證準(zhǔn)確率波動(dòng)大折數(shù)太少或數(shù)據(jù)不平衡增加折數(shù)或分層采樣預(yù)測(cè)結(jié)果全為同一類K值過(guò)大或距離矩陣全零檢查K值和距離計(jì)算運(yùn)行速度極慢用了雙循環(huán)或單循環(huán)改用完全向量化版本6. 從KNN延伸出的思考與后續(xù)優(yōu)化方向KNN在CIFAR-10上的準(zhǔn)確率雖然不高但它是一個(gè)很好的基線。我在做完KNN之后嘗試了幾個(gè)改進(jìn)方向這里分享一下實(shí)際效果。第一個(gè)方向是換距離度量。歐氏距離對(duì)像素的絕對(duì)差異敏感如果圖片整體亮度有偏移距離就會(huì)很大。換成余弦距離或者曼哈頓距離在某些類別上會(huì)有提升。我試過(guò)曼哈頓距離準(zhǔn)確率大概提升了1%左右但計(jì)算量增加了因?yàn)槁D距離不能像歐氏距離那樣用矩陣乘法加速。第二個(gè)方向是降維。3072維的像素空間里很多維度是冗余的。用PCA降到100維左右KNN的準(zhǔn)確率基本不變但速度快了很多。這個(gè)思路在后面做特征工程的時(shí)候很有用因?yàn)镠OG特征維度更高降維能顯著減少計(jì)算量。第三個(gè)方向是特征工程。作業(yè)1后面會(huì)要求你實(shí)現(xiàn)HOG特征把HOG特征拼到像素特征上KNN的準(zhǔn)確率能提升到40%左右。這說(shuō)明KNN的性能瓶頸不在分類器本身而在特征的表征能力。同樣的KNN換一組更好的特征效果就能大幅提升。我在實(shí)際做作業(yè)的過(guò)程中最大的體會(huì)是不要因?yàn)镵NN簡(jiǎn)單就跳過(guò)它。它涉及的向量化計(jì)算、距離度量、交叉驗(yàn)證、超參數(shù)調(diào)優(yōu)都是后面更復(fù)雜模型的基礎(chǔ)。你把KNN這部分吃透了后面寫兩層神經(jīng)網(wǎng)絡(luò)的時(shí)候很多代碼結(jié)構(gòu)和調(diào)試思路都是相通的。最后分享一個(gè)小技巧在調(diào)試KNN的時(shí)候先用100張訓(xùn)練、20張測(cè)試的小數(shù)據(jù)跑通全流程確認(rèn)準(zhǔn)確率合理比如K1時(shí)訓(xùn)練集上應(yīng)該接近100%然后再逐步擴(kuò)大數(shù)據(jù)量。這樣能快速定位問(wèn)題是出在算法邏輯還是數(shù)據(jù)規(guī)模上。我一開(kāi)始直接上全量數(shù)據(jù)結(jié)果跑了十分鐘才出結(jié)果發(fā)現(xiàn)準(zhǔn)確率不對(duì)又得重新跑浪費(fèi)了很多時(shí)間。小數(shù)據(jù)快速迭代大數(shù)據(jù)最終驗(yàn)證這個(gè)節(jié)奏在做任何機(jī)器學(xué)習(xí)作業(yè)的時(shí)候都適用。