EdX-Columbia機器學習課第10講筆記：核方法與高斯過程

05-06

特徵擴展

當線性模型在原始特徵空間內 $xin mathbb{R}^d$ 效果不好時，可以把特徵映射到高維空間 $phi(x) in mathbb{R}^D (D > d)$ ，然後在高維空間再進行線性建模。但是應該怎麼映射這都是case by case的，通常可以使用「kitchen sink」法，然後用 $ell_1$ 正則化來進行特徵篩選

$w_{ell_1} = { m arg}min_w sum_{i=1}^n f(y_i, phi(x_i), w) + lambda |!|w|!|_1$

不過更簡單地，我們可以只考慮特徵展開的內積 $phi(x_i)^Tphi(x_j)$ ，稱之為核，記作 $K(x_i, x_j)$

核

以感知機為例，由前面的講解，可知感知機從數據中構建超平面的方法是將所有錯分樣本的標籤和數據的內積累加起來，即

$w = sum_{i in mathcal{M}} y_ix_i$

其中 $mathcal{M}$ 是所有錯分樣本的一個順序集合

有了 $w$ 以後就可以對新的樣本 $x_0$ 預測其對應的 $y_0$

$y_0 = { m sign}(x_0^Tw) = { m sign}left(sum_{i in mathcal{M}}y_ix_0^Tx_i ight)$

如果對所有數據都進行特徵擴展，那麼上面的預測方法就會被改寫。注意 $x_0$ 會被映射到 $phi(x_0)$ ， $x_i$ 也會被映射到 $phi(x_i)$

$y_0 = { m sign}left(phi(x_0)^Tw ight) = { m sign}left(sum_{i in mathcal{M}}y_iphi(x_0)^Tphi(x_i) ight)$

這裡就出現了一個核

可以對核做出一個定義：核 $K(cdot, cdot): mathbb{R}^d imes mathbb{R}^d ightarrow mathbb{R}$ 是一個對稱函數 ( $K(a,b) = K(b,a)$ )，並且滿足對任意 $n$ 個 $mathbb{R}^d$ 中的數據點 $x_1, ldots, x_n in mathbb{R}^d$ ，其構成的 $n$ 階方陣 $K$ （ $K_{ij} = K(x_i, x_j)$ ）是半正定的。從直覺來看，這說明 $K$ 滿足了作為一個協方差矩陣的所有屬性

Mercer定理：如果函數 $K(cdot, cdot)$ 滿足了上述條件，則肯定存在一個映射 $phi: mathbb{R}^d ightarrow mathbb{R}^D$ 使得
$K(x_i, x_j) = phi(x_i)^Tphi(x_j)$

如果我們先定義 $phi$ ，則肯定能得到 $K$ 。不過有時我們先定義 $K$ ，避免定義 $phi$

最被廣泛使用的一種核稱為高斯核，也叫作徑向基函數 (radial basis function, RBF)

$K(x, x) = aexpleft{-frac{1}{b}|!|x-x|!|^2 ight}$

RBF衡量了兩個點之間的距離。當兩個點重合時，函數取得最大值 $a$ ；當兩點無限遠時，函數取得最小值0。高斯核的映射 $phi(x)$ 能把原始數據映射到無限維空間

另一種核： $K(x, x) = (1+x^Tx)^b, b > 0$

通過以下三種方法，可以從舊核 $K_1, K_2$ 構建新核

$egin{aligned}K(x,x) &= K_1(x,x)K_2(x,x) \K(x,x) &= K_1(x,x)+K_2(x,x) \K(x,x) &= exp{K_1(x,x)}end{aligned}$

##### 核感知機

如果選擇徑向基函數( $a=1$ )作為核，那麼核感知機的決策過程為

$egin{aligned}y_0 &= { m sign}left(sum_{i in mathcal{M}}y_iphi(x_0)^Tphi(x_i) ight) \&= { m sign}left(sum_{i in mathcal{M}}y_iK(x_0, x_1) ight) \&= { m sign}left(sum_{i in mathcal{M}}y_iexpleft{-frac{1}{b}|!|x_0 - x_i|!|^2 ight} ight)end{aligned}$

考慮之前介紹的RBF的性質，上面的決策過程實際就是遍歷錯分點，判斷錯分點與新數據之間的距離。如果距離遠，函數值趨近於0，說明其標籤在最後總和里的權重小；否則則大。即RBF使得決策過程類似一個「軟投票」 (soft voting)過程。

訓練時也是找一個新的 $x$ 滿足 $y ot= { m sign}(sum_{iin mathcal{M}_t}y_i K(x,x_i))$ ，但是這時只需要把 $x$ 的索引加入到 $mathcal{M}$ ，而不需要計算 $w^{(t+1)}$

核感知機的思想可以進一步推廣到核k-NN上。在這裡我們不止針對錯分的數據集 $mathcal{M}$ ，而是對所有數據進行求和，即

$y_0 = { m sign}left(sum_{i=1}^n y_iexp left{-frac{1}{b}|!|x_0 - x_i|!|^2 ight} ight)$

由於將各求和項統一除以一個正數不會改變總和的符號（即不會改變最終決策的結果），因此可以統一除以

$Z = sum_{j=1}^n exp left{-frac{1}{b}|!|x_0 - x_i|!|^2 ight}$

記

$p_i(x_0) = frac{1}{Z}exp left{-frac{1}{b}|!|x_0 - x_i|!|^2 ight}$

則最後的決策 $y_0$ 為

$y_0 = { m sign}left(sum_{i=1}^n y_ip_i(x_0) ight)$

可以看做是讓所有數據投票，但是我們為每個數據根據其與新數據的距離分配投票的權重。離新數據近的權重大，遠的權重小。這裡 $p(x_0)$ 扮演了置信度的概念，我們可以調整 $b$ 使得對大部分 $x_i$ 有 $p_i(x_0) approx 0$ ，使得我們只需要注意 $x_0$ 附近的點

##### 核回歸

也稱Nadaraya-Watson模型。其思想與核KNN方法類似。對新的樣本 $(x_0, y_0)$ ，預測 $y_0$ 為

$y_0 = sum_{i=1}^n y_i frac{K(x_0, x_i)}{sum_{j=1}^n K(x_0, x_j)}$

其意義是找到離 $x_0$ 比較近的 $x_i$ ，計算它們對應 $y_i$ 的加權平均值

高斯過程

假設有 $n$ 個樣本，響應值 $y in mathbb{R}^n$ ，特徵矩陣為 $X$ ，似然和先驗分別為

$y sim N(Xw, sigma^2 I), w sim N(0, lambda^{-1}I)$

可知（= =）其邊緣分布為

$p(y|X) = int p(y|X, w)p(w)dw = N(0, sigma^2I + lambda^{-1}XX^T)$

注意有 $(XX^T)_{ij} = x^T_ix_j$ ，將 $x$ 用 $phi(x)$ 替換，則有 $(phi(X)phi(X)^T)_{ij} = K(x_i, x_j)$ ，記為 $K$ ，所以有

$p(y|X) = int p(y|X, w)p(w)dw = N(0, sigma^2I + lambda^{-1}K)$

稱為高斯過程

定義：假設 $f(x) in mathbb{R}$ ，且 $x in mathbb{R}^d$ ，定義 $K(x,x)$ 為兩個點 $x$ 和 $x$ 之間的核，則 $f(x)$ 是高斯過程， $y(x)$ 是對結果附加的雜訊過程，如果

$y|f sim N(f, sigma^2 I), f sim N(0, K) Leftrightarrow y sim N(0, sigma^2I + K)$

其中 $y = (y_1, ldots, y_n)^T$ ， $K$ 是 $n$ 階方陣，且 $K_{ij} = K(x_i, x_j)$

注意高斯過程本身是不帶雜訊的，但是觀測到的值會受到雜訊影響（即 $f(x)$ ）。這裡雜訊都是服從i.i.d.的，而且是無限維的

講義中高斯過程的生成：選取 $xin [0,1]$ ，然後將其分成1000份，每個區間抽一個點出來，然後構建 $K$ ， $K$ 是一個 $1000 imes 1000$ 的矩陣，使用高斯核

貝葉斯線性回歸：假設我們有 $n$ 個樣本對 $mathcal{D} = {(x_i,y_i)}_{i=1}^N$ ，我們想根據 $x_0$ 預測 $y_0$ ，積掉 $w$ ，聯合分布為

$left[egin{array}{c} y_0 \ y end{array} ight] sim { m Normal}left(0, sigma^2I+ left[egin{array}{cc} x_0^Tx_0 & (Xx_0)^T \ Xx_0 & XX^T end{array} ight] ight)$

那麼有

$egin{aligned}y_0 | mathcal{D}, x_0 &sim { m Normal}(mu_0, sigma_0^2) \mu_0 &= (Xx_0)^T(XX^T)^{-1}y \sigma_0^2 &= sigma^2 + x_0^Tx_0 - (Xx_0)^T(XX^T)^{-1}(Xx_0)end{aligned}$

類似地，高斯過程可以估計 $y(x)$ 這一預測的分布：給定樣本數據集 $mathcal{D}_n = {(x_1, y_1), ldots , (x_n, y_n)}$ ，對任何新的 $x$ ，都可以計算 $y(x)$ 的分布來做預測

令 $K(x,mathcal{D}_n) = [K(x,x_1), ldots, K(x,x_n)]$ ， $K_n$ 是 $n imes n$ 核矩陣，有

$egin{aligned}y(x)|mathcal{D}_n & sim N(mu(x), Sigma(x)), \mu(x) &= K(x, mathcal{D}_n)K_n^{-1}y, \Sigma(x) &= sigma^2 + K(x,x) - K(x,mathcal{D}_n)K_n^{-1}K(x,mathcal{D}_n)^Tend{aligned}$

對 $f(x)$ 的後驗，只需要移去 $sigma^2$

高斯過程可以擬合任何形狀的函數，求回歸