EdX-Columbia機器學習課第7講筆記：kNN與貝葉斯分類器

05-20

來自專欄機器學習演算法與NLP學習筆記

分類問題：

其輸入是輸入空間 $mathcal{X} = mathbb{R}^d$ 中的 $n$ 個樣本 $x_1, ldots, x_n$ ，輸出是離散空間 $mathcal{Y}$ 中的某個值。當 $mathcal{Y} = {-1,+1}$ 或 ${0,1}$ 時，問題是一個二元分類問題；當 $mathcal{Y} = {1, ldots, K}$ 時，問題是一個多元分類問題

分類問題使用函數 $f$ （即分類器）將輸入 $x$ 映射到類別 $y$ 上，即 $y = f(x)$

近鄰分類

其演算法思想是，給定數據 $(x_1, y_1), ldots, (x_n, y_n)$ ，構造分類器 $hat{f}(x) ightarrow y$ 如下：

1. 對於不在訓練數據里的 $x$ ，令 $x_i$ 是 $(x_1, y_1), ldots, (x_n, y_n)$ 中離 $x$ 「最近」的點

2. 返回其標籤 $y_i$

如何衡量 $x$ 之間的距離？常見的是使用歐幾里得距離，即

$|!|u-v|!|_2 = left(sum_{i=1}^d (u_i - v_i)^2 ight)^{frac{1}{2}}$

當然也可以使用其它衡量方法，例如 $ell_p$ 、編輯距離（適用於字元串）或者相關距離（衡量兩個向量的相關性）

k近鄰分類

與原始的近鄰分類類似，不過是選取「最近」的 $k$ 個點，然後得票最多的類別是判定的類別

分類器有效的基本假定也是測試數據（未知數據）與訓練數據（已知數據）獨立同分布

貝葉斯分類

最優分類器

假設 $(X,Y) mathop{sim}^{iid} mathcal{P}$ ，而且我們不知道 $mathcal{P}$ 的分布，那麼關於分布 $mathcal{P}$ 有兩個性質

一個事件的指示變數的期望是這個事件的概率。即若定義 $1(cdot) = 0{ m or 1}$ 取決於 $cdot$ 是否為真，則有
$mathbb{E}_P[1(Y=1)] = P(Y=1)$
條件概率的期望可能會是隨機變數，但是這個隨機變數的期望是一個常數，即 $C = mathbb{E}[A|B], mathbb{E}[C] = mathbb{E}[mathbb{E}[A|B]] = mathbb{E}[A]$

對於任意分類器 $f: mathcal{X} ightarrow mathcal{Y}$ ，其預測誤差為

$P(f(X) ot= Y) = mathbb{E}[1(f(X) ot= Y)] = mathbb{E}[mathbb{E}[1(f(X) ot= Y)|X]]$

對每個 $xin mathcal{X}$ ，有

$mathbb{E}[1(f(X) ot= Y)|X=x] = sum_{y in mathcal{Y}} P(Y=y|X=x)cdot 1(f(x) ot= y)$

所以上式取得最小值的條件是分類器 $f^star$ 對所有 $x in mathcal{X}$ ，都取

$f^star (x) = { m arg}max_{y in mathcal{Y}} P(Y=y|X=x)$

對所有 $x in mathcal{X}$ 都具有這一屬性的分類器 $f$ 稱為貝葉斯分類器，它在所有分類器中有最小預測誤差

貝葉斯分類器

對於上式，根據貝葉斯定律，等價於有

$f^star (x) = { m arg}max_{y in mathcal{Y}} P(Y = y) imes P(X = x|Y = y)$

其中 $P(Y=y)$ 稱為類別先驗， $P(X=x|Y=y)$ 稱為 $X$ 的類別條件分布（當 $X$ 是連續隨機變數時， $P(X=x|Y=y)$ 寫為 $p(x|Y=y)$ ，稱為類別條件密度）。在實際中，這兩個分布我們都不知道會是什麼，所以只能去近似之

以下四段轉載於生成模型與判別模型 - zouxy09的專欄 - 博客頻道 - CSDN.NET

判別方法：由數據直接學習決策函數Y=f(X)或者條件概率分布P(Y|X)作為預測的模型，即判別模型。基本思想是有限樣本條件下建立判別函數，不考慮樣本的產生模型，直接研究預測模型。典型的判別模型包括k近鄰，感知級，決策樹，支持向量機等。
生成方法：由數據學習聯合概率密度分布P(X,Y)，然後求出條件概率分布P(Y|X)作為預測的模型，即生成模型：P(Y|X)= P(X,Y)/ P(X)。這樣的方法之所以稱為生成方法，是因為模型表示了給定輸入X產生輸出Y的生成關係。用於隨機生成的觀察值建模，特別是在給定某些隱藏參數情況下。典型的生成模型有：樸素貝葉斯和隱馬爾科夫模型等。
生成方法的特點：上面說到，生成方法學習聯合概率密度分布P(X,Y)，所以就可以從統計的角度表示數據的分布情況，能夠反映同類數據本身的相似度。但它不關心到底劃分各類的那個分類邊界在哪。生成方法可以還原出聯合概率分布P(Y|X)，而判別方法不能。生成方法的學習收斂速度更快，即當樣本容量增加的時候，學到的模型可以更快的收斂於真實模型，當存在隱變數時，仍可以用生成方法學習。此時判別方法就不能用。
判別方法的特點：判別方法直接學習的是決策函數Y=f(X)或者條件概率分布P(Y|X)。不能反映訓練數據本身的特性。但它尋找不同類別之間的最優分類面，反映的是異類數據之間的差異。直接面對預測，往往學習的準確率更高。由於直接學習P(Y|X)或P(X)，可以對數據進行各種程度上的抽象、定義特徵並使用特徵，因此可以簡化學習問題。

plug-in分類器

通常情況下，我們並不知道 $P(Y=y|X=x), P(X=x|Y=y)$ 和 $P(Y=y)$ ，我們只有從分布 $mathcal{P}$ 中得到的帶標籤的樣本。但是按照道理來講，在不知道 $mathcal{P}$ 的情況下我們無法構建貝葉斯分類器，所以需要用手頭數據去估計 $P(Y=y)$ 和 $P(X=x|Y=y)$ ，其代價是得到的結果不會是最好的結果——這種分類器稱為plug-in分類器

對於 $mathcal{X} = mathbb{R}^d$ 和 $mathcal{Y} = {1,ldots, K}$ ，可以通過MLE來估計貝葉斯分類器。類別的先驗的MLE估計 $pi_y$ 為

$hat{pi}_y = frac{1}{n} sum_{i=1}^n 1(y_i = y)$

類別的條件概率密度可以假設為 $p(x|Y=y) = N(x|mu_y, Sigma_y)$ ，兩個參數的MLE估計為

$egin{aligned}hat{mu}_y &= frac{1}{n_y} sum_{i=1}^n 1(y_i = y)x_i \hat{Sigma}_y &= frac{1}{n_y} sum_{i=1}^n 1(y_i = y)(x_i - hat{mu}_y)(x_i - hat{mu}_y)^Tend{aligned}$

對應的plug-in分類器為

$hat{f}(x) = { m arg}max_{y in mathcal{Y}} hat{pi}_y |hat{Sigma}_y|^{-frac{1}{2}}expleft{-frac{1}{2} (x - hat{mu}_y)^That{Sigma}_y ^{-1}(x-hat{mu}_y) ight}$

例如，在垃圾郵件分類器中，使用樸素貝葉斯，其假設 $X$ 的各個維度在 $y$ 下條件獨立，忽略了它們之間的相關性使得概率容易算，即

$p(X= x|Y=y) = prod_{j=1}^d p_j(x(j)|Y=y)$

這時類別的先驗為

$P(Y=y) = frac{#{ m observations in class }y}{{ m # observations}}$

條件分布使用Poisson分布，即

$P(X=x|Y=y) = prod_j p_j(x(j)|Y=y) = prod_j { m Poisson}(x(j)|lambda_j^{(y)})$

其中 $lambda_j^{(y)}$ 的MLE為

$lambda_j^{(y)} = frac{#{ m unique uses of word }j{ m in observations from class }y}{#{ m observations in class }y}$