Machine-Learning
k最近鄰的VC-Dimension
如果 k 等於使用的訓練點數，k-最近鄰算法的 VC-Dimension 是多少？
**背景：**這個問題是在我參加的課程中提出的，給出的答案是 0。但是，我不明白為什麼會這樣。我的直覺是 VC-Dimension 應該是 1，因為應該可以選擇兩個模型（即訓練點集），以便根據第一個模型將每個點標記為屬於一個類並屬於另一個類根據第二個模型，因此應該可以粉碎一個點。我的推理錯誤在哪裡？
你說的算法是：k-最近鄰算法，k=使用的訓練點數。我將其定義為jms-k-nearest-neighbor。
由於 VC 維度是訓練誤差為 0的算法所能粉碎的最大訓練點數，因此jms-k-nearest-neighbor的 VC 維度只能為 k 或 0。
1 個訓練實例 => k=1：在訓練期間 jms-1-nearest-neighbor 正好存儲這個實例。在完全相同的訓練集上應用時，一個實例最接近存儲的訓練實例（因為它們是相同的），因此訓練誤差為0。
所以我同意，VC 維度至少為 1。
2 個訓練實例 => k=2：只有標籤不同時才會出現問題。在這種情況下，問題是如何做出類標籤的決定。多數票不會導致結果（VC = 0？），如果我們使用按距離反比加權的多數票，則 VC 維度為 2（假設不允許使用不同標籤兩次具有相同的訓練實例，因為如果所有算法的 VC 維度都是 0（我猜））。
沒有標準的 k 近鄰算法，它更像是一個基本思想相同但在實現細節上風格不同的家族。
使用的資源：Andrew Moore 的 VC 維度幻燈片