從鄰域到決策
密度估計關心某個位置附近有多少概率質量;分類則問,附近的觀測有多少屬於類別一。局部比例可以在不預設有限維公式的情況下估計條件類別概率,因此決策邊界可以彎曲,但距離、特徵單位和鄰居個數都會影響結果。
定義 25.1.1
( 近鄰投票與決策)
設 ,,是 的獨立同分佈副本,其中 、。固定查詢點 ,按歐氏距離(Euclidean distance)排列樣本;距離相同則按下標決定次序。對 ,令 為前 個下標,定義
平票依約判為一,也可事先採用其他固定規則。
記 為條件概率的一個版本;下面的定理要求該版本在查詢點連續。誤判代價相等時,一個貝葉斯(Bayes)決策為 。代價不等時門檻會改變:估計概率與據此作決策是兩件不同的事。
例題 25.1.2
(三個鄰居與五個鄰居)
訓練對為 ,查詢 。距離由小至大為 1、1、2、3、4,按下標處理相同距離後標籤依次為 。 時估計為 , 時為 ;等代價下都判為一。若假陽性的代價是假陰性的四倍,行動一、零的條件風險分別為 和 ,因此只有 才判一。代入上述兩個估計,行動都變為零。這些比例只是局部估計,並不保證真實條件概率等於它們。
鄰居數與半徑為何都重要
若 保持很小,即使鄰居很近,標籤仍有隨機波動;若 保持很大,鄰域未必收縮,遠處標籤會造成持續偏差。以下結果只針對一個固定查詢點,不聲稱一致收斂或收斂速率。
定理 25.1.3
(逐點概率與超額風險一致性)
假設 在 連續,且對每個 都有 。若整數 滿足 、,則 依概率收斂到 。在零一損失下,隨機擬合決策 在 的條件超額風險也依概率收斂到零。
證明
(收縮半徑並平均標籤噪音)
固定 ,記 。球內訓練特徵的數目 服從二項分佈,均值為 ,方差為 。最終 ;由切比雪夫(Chebyshev)不等式,。因此第 個鄰居的距離 依概率趨於零。
以全部訓練特徵為條件,標籤幾乎處處條件獨立且為均值 的伯努利(Bernoulli)變量。令 。投票的條件方差至多為 ,故條件切比雪夫不等式給出 (依概率)。由 在 連續和 ,有 (依概率):對任意容差,可選適當的 ,使 時每個求和項與 的差都小於該容差。合併兩項即得第一結論。
固定訓練樣本時,在 選擇一的條件錯誤率為 ,選擇零則為 。若擬合行動不同於某個貝葉斯行動,則 與 位於 的相反側(平票不影響結論)。條件超額錯誤率至多為 ;行動相同時為零。因此得到第二結論。這裏測試標籤是新的,且其在 的分佈由同一個 定義。
證明透視
兩種不同的誤差
半徑論證控制附近的條件均值與目標的差;方差論證控制標籤相對於這些均值的隨機波動。兩者缺一不可:很近的標籤仍可能有噪音,而精確平均遠處鄰域也可能估錯目標。
反例模式
一個鄰居無法平均掉噪音
設所有特徵都為零,標籤獨立服從伯努利。在 ,按平距規則,一個鄰居的估計就是第一個標籤。無論 多大,估計都是零或一,與 至少相差 ,所以不依概率收斂到 。對獨立測試標籤的期望分類錯誤率是 ,高於貝葉斯錯誤率 。
例題 25.1.4
(訓練準確率完美,留一法準確率為零)
取一維四點 ,標籤為 。取 並把訓練點本身計入時,每個點都是自己的最近鄰,距離為零,所以訓練準確率為 。現在逐一留出每個點,只用其餘三點分類。點 的最近鄰是點 ,標籤為 :錯。點 的鄰居 與 距離都是一,標籤都是 :錯。點 的鄰居 與 標籤都是 :錯。點 的最近鄰是點 ,標籤為 :錯。留一法準確率是 。取 時,點 的留一估計依次為 ,預測依次為 ,每個點仍然判錯。這個標籤排列刻意取得不平滑,但它說明 的訓練準確率對新樣本沒有提供任何資訊。
例題 25.1.5
(改變單位會改變最近鄰)
取兩個訓練點 (標籤 )與 (標籤 ),查詢點為 。歐氏距離到 是 ,到 是 ,所以單一鄰居規則預測 。現在把第二個座標改用大十倍的單位:、、查詢點 。距離變為 與 ,最近鄰變成 ,預測為 。數據相同,規則卻改變了,因為歐氏距離依賴單位。因此特徵縮放是程序的一部分,必須只用訓練數據選定。
常見錯誤
(訓練集上的好投票不保證測試表現)
時,訓練觀測通常以自己為最近鄰,訓練準確率可能看似完美,而新樣本預測仍然很差。應只用訓練折選擇 、擬合特徵縮放及其他預處理,再用未參與這些選擇的數據評價整個選擇流程。
常見錯誤
(較大的 以方差換偏差)
較大的 可能降低投票方差,卻也可能模糊邊界。高維下,要使鄰域真正局部往往需要更多數據,因此定理不是有限樣本表現保證。
練習與解答
快速檢查
(某查詢點的五個有序標籤為 。求 時的估計與等代價決策。)
對前 個標籤取平均。
解答 · 答案
估計依次為 、、,決策依次為零、一、零。同一組有序數據採用不同的 可以改變決策。
快速檢查
(令 ,檢查定理的兩個條件。若 呢?)
計算 。
解答 · 答案
平方根序列趨於無窮,且與 的比趨於零。若 ,該比為一,鄰域就是全部樣本,收縮鄰域的論證不適用。
快速檢查
(設 ,而擬合估計為 。求條件超額零一風險,並與證明中的界比較。)
先找出擬合的行動。
解答 · 答案
擬合行動為零,條件錯誤率為 ;貝葉斯行動為一,錯誤率為 。超額錯誤率為 ,不超過 。這裏針對固定 的新標籤。