先描述，再判斷：k-NN、SVM 與特徵袋

從單一範例到大量範例：監督式分類

在上一篇你是用比對來辨識：你拿出一個樣板（一個儲存的範例），把它在影像上滑動，找出對得最齊的位置。當目標長相永遠一樣時這行得通，但世界很少這麼配合。一隻「貓」可能是橘色或灰色、蜷成一團或正在跳躍、從左邊或右邊打光。沒有任何單一樣板能代表上述所有情況。本篇要從「與單一範例比較」跨到從大量範例學習，這正是古典辨識流程背後的引擎。

這就是監督式分類的框架。我們從一個訓練集出發：一堆影像，每張都貼上一個標籤（這張是貓、那張是狗）。先前的學習軌已教過如何把原始影像轉成數字——邊緣、梯度、HOG 類描述子——所以我們在此直接假設描述子已給定。於是每張影像都變成一個特徵向量：一串有順序的數字，例如 (0.21, 0.04, 0.88, …)，用來概括這張影像的長相。整張影像被壓縮成高維空間中的一個點，而它的標籤就是我們替這個點塗上的顏色。

分類器學的是一條決策規則——一種「看到全新特徵向量就輸出標籤」的方法。真正的目標不是把手上已有的影像答對，而是泛化：在從未見過的影像上也答對。把它想成準備考試。如果你只背去年考卷的答案，在那份考卷上會顯得很厲害，遇到新考卷卻會卡住。所以我們把一部分有標籤的資料藏起來當測試集，只用其餘的（訓練集）來訓練，並且只用這份保留的測試集來評斷模型——它公平地代表「未來的影像」。在訓練上表現好、在測試上表現差的模型，是死記而非理解。像k-最近鄰影像分類器這樣的學習法，更讓你無法忽視這個切分。

k-最近鄰：物以類聚

最溫和的分類器是k-最近鄰影像分類器（k-NN）。要替一張新影像貼標籤，它會找出特徵向量離新影像最近的 k 張訓練影像，讓它們投票。出乎意料的是，它根本沒有真正的「訓練」：k-NN 只是把整個訓練集留在記憶體裡，到查詢時才開始思考。我們稱它為懶惰學習器——它把每個決定都拖到你真的問它問題時才做。整個「模型」就是資料集本身。

查詢向量與第 i 個訓練向量之間的歐氏（直線）距離。

「最近」需要一個距離度量，預設是歐氏距離。由左到右讀公式：\mathbf{x} 是查詢特徵向量（新影像），\mathbf{x}_i 是第 i 個儲存的訓練向量，索引 j 跑遍 D 個特徵維度，而 x_j 對上 x_{i,j} 是一次比較一個維度。我們在每個維度內相減，平方讓正負都算數、且大落差被狠狠懲罰，再把全部 D 個維度加總，最後開平方根抵消平方、回到真實單位——就是你在紙上用尺量到的距離。二維小例子：查詢 (2,2)、鄰居 (3,3)：\sqrt{(2-3)^2+(2-3)^2}=\sqrt{2}\approx1.41。由於每個維度都以相同權重加總，特徵縮放極為重要：若某個特徵範圍是 0–1000、另一個是 0–1，大的那個會淹沒小的那個。把每個特徵標準化（例如化為零均值、單位變異數）能讓每個維度用同樣的音量發言。

預測在 k 個最近鄰中得票最多的標籤 c。

接著是投票規則。\hat{y} 是預測標籤；N_k(\mathbf{x}) 是與 \mathbf{x} 距離最小的 k 個訓練點所成的集合；c 跑遍各個可能類別；而 \mathbb{1}[y_i=c] 是一個指示函數，當鄰居 i 的標籤等於 c 時為 1、否則為 0。所以這個加總只是在數 k 個鄰居中各類別各有幾張票，再由 \arg\max 選出票數最多的類別——就是單純的多數決。平手（例如 k=4 變成 2 比 2）可以靠縮小 k、擲銅板，或更優雅地用 1/d 加權每一票來打破，讓非常近的鄰居比遠的鄰居更有分量。k 的選擇是關鍵旋鈕：小 k（k=1）給出貼合每個雜訊點的鋸齒邊界——高變異、過度配適；大 k 對一大群人取平均、把邊界抹平——高偏差、配適不足。這正是偏差—變異權衡最純粹的樣貌。

import math

# Tiny 2D example. Each sample = (feature vector, label).
train = [
    ((2, 1), "cat"),
    ((1, 2), "cat"),
    ((3, 3), "dog"),
    ((0, 0), "cat"),
    ((4, 2), "dog"),
]
query = (2, 2)
k = 3

def dist(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

# rank training points by distance, keep the k closest
ranked = sorted(train, key=lambda s: dist(query, s[0]))
neighbours = ranked[:k]   # (2,1)cat d=1.00, (1,2)cat d=1.00, (3,3)dog d=1.41

votes = {}
for vec, label in neighbours:
    votes[label] = votes.get(label, 0) + 1

prediction = max(votes, key=votes.get)  # cat: 2 votes beats dog: 1 vote
print(prediction, votes)                # -> cat {'cat': 2, 'dog': 1}

支援向量機：找出最寬的那條街

支援向量機（SVM）曾是古典分類器的主力。想像兩個類別散落在紙上；有無限多條直線能把它們分開。哪一條最好？Vladimir Vapnik 的答案是最寬的那條街：在所有能分開的線裡，選出間隔最大的那條——也就是兩側都沒有任何點落入、最寬的那條空白緩衝帶。緩衝帶愈胖，代表你可以把一個新點挪動很遠才會越界到錯的一邊，而這正是讓規則能泛化的原因。剛好碰到街道邊緣、把它釘住的那少數幾個點，就是支援向量；驚人的是，整條邊界只取決於它們，其餘的點都被忽略。

線性決策函數及其以正負號判斷的分類規則。

這條邊界在二維是一條線、在更高維是一個超平面，由這個決策函數描述。\mathbf{x} 是你要分類的特徵向量；\mathbf{w} 是權重向量，它垂直（法向）於邊界、決定邊界的朝向；b 是偏置，讓邊界朝原點靠近或遠離地平移；而 \mathbf{w}\cdot\mathbf{x}=\sum_j w_j x_j 是內積。邊界本身就是所有使 f(\mathbf{x})=0 的點所成的集合。要分類，取 \operatorname{sign}(f(\mathbf{x}))：正號是一類、負號是另一類。具體地，取 \mathbf{w}=(2,0)、b=-3，點 \mathbf{x}=(2,5) 得到 f=2\cdot2+0\cdot5-3=1>0（類別 +1），而 \mathbf{x}=(1,9) 得到 f=2-3=-1<0（類別 −1）。注意第二個特徵在這裡無關緊要，因為它的權重是 0——權重編碼了哪些特徵重要。

街道的寬度，完全由權重向量的長度決定。

巧妙之處在這裡。SVM 會縮放 \mathbf{w} 與 b，使支援向量恰好落在 f(\mathbf{x})=+1 與 f(\mathbf{x})=-1 上。這兩條邊界之間的垂直間距於是算得 2/\lVert\mathbf{w}\rVert，其中 \lVert\mathbf{w}\rVert=\sqrt{\sum_j w_j^2} 是權重向量的長度。仔細讀：間隔與 \lVert\mathbf{w}\rVert 成反比，所以更寬的街道意味著更短的 \mathbf{w}。這就是為什麼「最大化間隔」與「最小化 \lVert\mathbf{w}\rVert」是同一件事——一個我們真的解得出來的乾淨最佳化問題。用數字看：把 \lVert\mathbf{w}\rVert 從 2 減半到 1，街道就從 1 加倍到 2。

軟間隔 SVM：在加寬街道的同時，為侵入街道的點付出代價。

真實資料不會完美可分，所以 SVM 採用軟間隔，容許少數點落在街道內、甚至落到錯的一邊，但要付出代價。逐項看：\tfrac{1}{2}\lVert\mathbf{w}\rVert^2 是「把街道保持寬」的部分；y_i=\pm1 是範例 i 的真實標籤；y_i f(\mathbf{x}_i) 在預測正確且自信地落在間隔之外時為正。Hinge 損失 \max(0,\,1-y_i f(\mathbf{x}_i)) 在點安全地超出自己的間隔時（y_i f \ge 1）為 0，並在點擠進街道或越過街道時線性增長。常數 C 設定了這兩個目標之間的匯率。大 C 嚴懲每個錯誤 → 狹窄、彎曲去貼合資料的間隔（過度配適）；小 C 容忍違規 → 寬而平滑的間隔（正則化較強，可能配適不足）。C 對 SVM 扮演的角色，就如同 k 對 k-NN 一樣。

如果兩個類別沒有任何直線能分開呢？核技巧讓 SVM 表現得彷彿先把資料抬升到一個高得多的空間，在那裡一個平直的邊界確實能把它們分開——而且完全不必把那些座標明確算出來。把線性 SVM 配上強力的手工特徵，你就得到著名的 HOG + SVM 偵測器；在深度網路之前，它在物件與行人偵測上稱霸了將近十年：HOG 把局部梯度型態變成穩健的描述子，而 SVM 在「物件」與「非物件」之間劃出可能最寬的那條街。

每張影像一個向量：視覺詞袋

有個我們一直默默忽略的不對等。局部特徵方法（類 SIFT 的關鍵點、影像塊）對每張影像會產生數量不定的描述子——一張雜亂的照片可能吐出 2,000 個，一張單純的只有 50 個。但 k-NN 與 SVM 都要求一個固定長度的向量，每次都同樣大小，這樣每個點才能活在同一個一致的空間裡。我們要如何把一組變化劇烈的描述子，壓成單一固定向量，又不把資訊丟掉？

這個訣竅是向文字借來的。要比較兩份文件，你不需要它們的字詞順序——你可以用出現了哪些字、各出現幾次來描述每一份：一個「詞袋」。（「the cat sat」和「sat the cat」給出相同的袋子。）電腦視覺原封不動地照抄這個想法。我們建一套反覆出現的視覺單字詞彙——像角點、像眼睛的斑塊、一段條紋這類有特色的小塊——再用每張影像含有各個視覺單字幾個，來描述這張影像。順序與位置被丟棄；只留下計數。

1. 在所有訓練影像上抽取大量局部描述子（每張數千個，總計數百萬個）。
2. 用 k-means 把這片描述子海洋分成 K 群；每個群心成為一個視覺單字。這正是字典學習——這 K 個群心就是學到的碼本（詞彙表）。
3. 對影像中的每個描述子，把它指派給最近的視覺單字（向量量化）。
4. 建一個直方圖：數有多少描述子落入這 K 個單字裡的每一個，然後標準化。
5. 把這個固定長度的直方圖當作該影像的特徵向量，餵給 SVM 或 k-NN。

向量量化：把每個描述子吸附到最近的碼本群心。

第 3 步就是向量量化，而它的全部內容就只是這條小公式。\mathbf{d} 是一個局部描述子（一個向量）；\mathbf{c}_k 是 k-means 第 k 群的群心——碼本裡的第 k 個視覺單字；\lVert\mathbf{d}-\mathbf{c}_k\rVert 是我們已認識的歐氏距離。\arg\min 回傳最近群心的索引 k，所以 q(\mathbf{d}) 就是這個描述子被蓋上的單字編號。實際上我們把一個豐富、連續的描述子換成一個整數——「這個影像塊是第 37 號單字」——就像你把 3.8 四捨五入到最近的整數一樣。我們用精度換來一個整潔、可計數的表示。

標準化的詞袋直方圖：被指派給第 i 個單字的描述子所佔的比例。

第 4 步把單字編號變成影像的最終向量 h。它有 K 個欄位，每個視覺單字一個。N 是這張影像找到的描述子數量；\mathbb{1}[q(\mathbf{d}_n)=i] 在第 n 個描述子被量化到單字 i 時為 1、否則為 0，所以這個加總就是在數有多少描述子落到單字 i。1/N 這個因子用總數做標準化：沒有它的話，一張有 2,000 個描述子的忙碌影像會有巨大的長條，一張只有 50 個的稀疏影像則是小小的長條，即使它們呈現同一個物件，看起來也無法比較。除以 N 把原始計數變成加起來為 1 的比例，於是「以條紋為主」無論影像雜亂或乾淨都長得一樣。例子：100 個描述子，其中 30 個落入第 5 號單字 → h_5=0.30。如今每張影像，不管原本有多少描述子，都成了一個固定 K 長度、可直接交給分類器的向量。

from sklearn.cluster import KMeans
import numpy as np

# 1) collect local descriptors from ALL training images (e.g. SIFT/HOG patches)
all_descriptors = np.vstack([describe(img) for img in training_images])  # (M, D)

# 2) learn the visual vocabulary: K cluster centres = the codebook (dictionary)
K = 200
codebook = KMeans(n_clusters=K).fit(all_descriptors)

def bag_of_words(img):
    desc = describe(img)                # (n, D) -- variable count per image
    words = codebook.predict(desc)      # 3) nearest visual word for each descriptor
    hist = np.bincount(words, minlength=K).astype(float)  # 4) count per word
    return hist / hist.sum()            # normalize -> fixed-length, scale-free vector

把位置找回來：空間金字塔比對

詞袋的弱點現在很刺眼：它對佈局視而不見。天空藍的影像塊在上、灰色道路的影像塊在下，和兩者對調，會給出完全相同的全域直方圖——但一個是正常的戶外場景，另一個卻是上下顛倒。空間金字塔比對（SPM）藉由重新引入一些幾何來救我們，又不必一路退回僵硬的樣板。

做法漂亮地簡單。在影像上鋪一系列愈來愈細的網格：第 0 層是整張影像（1×1，就是普通詞袋），第 1 層把它切成 2×2 = 4 格，第 2 層切成 4×4 = 16 格。在每一格內計算一個詞袋直方圖，再把它們全部串接成一個長向量。粗的那層攜帶「影像整體裡有什麼」；細的那幾層加上「而且每樣東西大致在哪裡」。每一格都重用同一套字典學習碼本，所以各層的單字彼此可比。

金字塔比對核：跨各層的直方圖交集分數的加權總和。

要比較兩張影像，SPM 使用金字塔比對核 K，得到單一相似度分數。逐符號看：l 是金字塔層級，從最粗的 l=0 一路到最細的 l=L；I_l 是直方圖交集相似度，做法是逐格把兩張影像單字計數的逐元素最小值加總起來——正是第 1 篇的彩色直方圖交集度量，如今按格套用再相加；而 w_l=1/2^{\,L-l} 是給第 l 層的權重。以 L=2 檢查權重：w_0=1/2^2=0.25、w_1=1/2^1=0.5、w_2=1/2^0=1。愈細的層權重愈大。 原因是：在細層的匹配代表兩張影像在「是什麼」和「在哪裡」兩者上都一致，這比只在「是什麼」上一致的粗層匹配是更強的證據——但粗層仍會貢獻，所以分數會平滑地退化，而不是硬要求完美對齊。

想像一個場景分類器要判斷「海灘」還是「街道」。如果兩者都含藍色與灰色影像塊，普通詞袋可能會搞混。用金字塔後，「海灘」在下方格穩定地有沙/水單字、在上方格有天空單字，而「街道」在兩側有建築物——這些位置型態如今都成了向量的一部分。這種「把粗略與精細串接」的想法，曾是場景與物件資料集上重要的深度學習之前的基準贏家，而同樣的直覺——保留一個粗略摘要，再加幾層更細的空間細節——也悄悄存活在現代網路的池化金字塔裡。

它真的有用嗎？誠實的評估

一個分類器值不值得信，取決於你怎麼量它，所以本節是整個學習軌裡最能重複使用的部分。最高原則是訓練／驗證／測試的紀律。在訓練集上訓練。在另一個獨立的驗證集上調旋鈕——k-NN 的 k、SVM 的 C、碼本大小 K。對測試集只在最後動一次手，用來回報最終數字。一旦你偷看測試集並據此調整任何東西，它就不再衡量未來、開始討好你——你已經悄悄拿它在訓練了，而你回報的分數就成了謊言。

最顯然的分數是準確率 = 預測正確的比例。它在不平衡資料上有個著名陷阱。假設每 100 張影像裡有 1 張含有罕見瑕疵。一個每次都大喊「沒瑕疵！」的懶惰模型有 99% 準確率，卻 100% 沒用——它從來抓不到你在意的那個東西。要看穿這點，我們攤開混淆矩陣：一張「真實類別對上預測類別」的小表，對於是／否任務有四格，分別是真陽性、偽陽性、偽陰性與真陰性。每個更精緻的指標都是由這四個數字搭出來的。

精確率與召回率，皆由混淆矩陣的計數搭成。

精確率問：在我標示為陽性的一切之中，有多少真的是陽性？召回率問：在真正是陽性的一切之中，我抓到了多少？這裡 TP（真陽性）是正確的陽性標示，FP（偽陽性）是假警報，FN（偽陰性）是溜走的真陽性。實作範例：一項癌症篩檢對 100 名病患做檢查；其中 10 人真的有病。模型標示 12 人為陽性——其中 8 人正確（TP=8）、4 人是假警報（FP=4）；它漏掉 2 名病患（FN=2）。那麼精確率 =8/(8+4)=0.67、召回率 =8/(8+2)=0.80。兩者互相取捨：把每個人都標成陽性，召回率衝到 1.0 但精確率崩盤；只標你最有把握的那一個，精確率是 1.0 但召回率慘不忍睹。你該為哪一個而戰，取決於每種錯誤的代價。 垃圾郵件過濾器要高精確率（絕不誤埋一封真郵件）；癌症篩檢要高召回率（絕不漏掉一名病患，假警報還可以忍）。

F1 分數：精確率 (P) 與召回率 (R) 的調和平均。

當你需要單一數字時，F1 分數把精確率 P 與召回率 R 以它們的調和平均結合起來。用調和平均而非普通平均的原因是：調和平均會被拉向兩者中較小的那個，所以它懲罰失衡的分數。取 P=1.0 但 R=0.0（你只標了一樣、標對了，其餘全漏）：普通平均是好看的 0.5，但 F1 =2(1)(0)/(1+0)=0——正確地殘酷。以我們的癌症例子，F_1=2(0.67)(0.80)/(0.67+0.80)=0.73，誠實地落在兩者之間。F1 只有在精確率與召回率兩者都不錯時才會爬高，而這正是我們對一個摘要數字的期待。

最後，這些指標讓你能診斷前面的偏差—變異失敗。過度配適的徵兆是訓練分數近乎完美、驗證分數卻很差——模型把雜訊背了起來（k-NN 的 k 太小、SVM 的 C 太大）。配適不足的徵兆是兩邊分數都平庸——模型太僵硬，抓不住型態（k 太大、C 太小）。你在驗證集上診斷，挑出讓驗證誤差最小的旋鈕，然後才把測試集讀一次，得到誠實的最終裁決。