【一起看論文】隨機特徵

04-25

今天來讀 2007 年 Ali 等人發表在 NIPS 上面的 Random Features for Large-Scale Kernel Machines，提出了一個叫隨機特徵的方法，來加速訓練大型的核分類器（即用了核技巧的分類器）。

摘要中提到，為了加速訓練核機器，他們把輸入數據映射到一個「隨機」的低維特徵空間，然後在這空間上面用現有的快速線性方法進行訓練。這裡的「隨機」的含義還有待下文詳細解說。論文中提出的「隨機化」特徵滿足一個性質：數據的在降維空間中的內積近似等於在原來特徵空間中時的內積。當然實驗表明，這個隨機特徵的方法效果的確不錯。

支持向量機（SVM），是非常受歡迎的核機（Kernel Machine），因為它們實際上可以以任意精確度擬合任何無重複點的數據集。但是，隨著數據量的增大，核 SVM 的運行效率大打折扣，因為演算法核心中用到了數據集的核矩陣（Kernel Matrix），矩陣元素的個數隨著數據規模增大成平方增長。但與此同時，線性 SVM 則不受此困擾，因為演算法核心用的是數據集的協方差矩陣，矩陣大小和數據集大小無關，而僅和數據維數有關。對低維的數據，線性 SVM 的運行效率就尤為出色。因此本文的 Idea 就是結合線性和 kernel trick 兩方面的優勢，既能夠擬合好數據集，又有高的運行效率。在這個 Idea 的指導下，本文又受另外 2 篇論文的啟發（Sampling techniques for kernel methods; Random projection, margins, kernels, and feature-selection），提出了將數據映射到低維的隨機特徵空間，然後在這空間上面用快速的線性方法，這樣一條加速訓練核機的思路。

這裡首先回憶一下什麼是 kernel trick。kernel trick 是用一個核函數把數據點之間的內積包裝起來，藉此把數據映射到高維空間的一種技巧。比如 $phi$ 是一個映射，它對應的核函數是 $k$ ，使得 $left<phi(x),phi(y) ight>=k(x,y)$ 。

論文提出，構造一個「隨機」映射 $z:R^d o R^D$ 直接將數據映射到低維的空間，使得在這空間上的內積可以近似等於核函數：

$k(x,y)=left<phi(x),phi(y) ight>approxleft< z(x),z(y) ight>$

可以看到原來的映射 $phi$ 是將數據映到高維空間的，而 $z$ 則是將數據映到低維空間的。在低維空間上，我們就可以用快速的線性訓練演算法了，而且因為上面的近似關係，我們還能很大程度保留住 kernel trick 帶來的優勢。

到這裡，論文的整體思路就出來了：在盡量保持內積的前提下，給數據做降維，然後在低維空間上用快速的線性訓練演算法。接下來，問題就集中在如何選取保持核函數的映射 $z$ 上。論文部分回答了這個問題，作者給出了平移不變的核函數 $k(x-y)$ 對應的映射 $z$ 的構造法，但是沒有給出其他類型核函數的。對平移不變的核函數，作者還證明了，若給定精度要求 $epsilon$ ，可以構造誤差一致小於 $epsilon$ 的映射 $z$ ，而且 $z$ 將數據維數降低到 $D=Oleft(dfrac{1}{epsilon^2}logfrac{1}{epsilon^2} ight)$ 。最後，論文用實驗（而不是理論）說明了數據維數降到更低的 $D$ 也可以得到很好的分類和回歸模型。

運用論文提出的這種思路，除了訓練得到加速以外，預測效率也得到了大大提高。只要回憶演算法最終是用線性模型，就不難理解其中的原因。

接下來，作者就要介紹他們想到的 2 種構造映射 $z$ 的方法了。當然其他的構造方法是可能找到的，但是首先要看看它們在哪些方面能夠比論文提到的 2 種更好。第一種構造法，叫做隨機傅立葉特徵（Random Fourier Features），它的思路是，從核函數的傅立葉變換中，隨機的抽取正弦基，來構造所需映射。第二種構造法，叫做隨機裝箱特徵（Random Binning Features），它的思路是，用隨機平移和解析度的網格（箱子）分割輸入空間，從而構造所需映射。注意到 2 種構造方法當中都涉及到隨機選取的操作，故而構造出來的映射也被作者簡稱隨機映射，將它作用到數據上得到的特徵叫做隨機特徵，於是有了論文的題目。作者指出，第一個映射是光滑的，因此適用於插值問題，而第二個映射雖然不光滑，但是利用了數據之間的親疏關係，非常適合逼近基於數據點之間 $L_1$ 距離的核函數。當然，文章最後在實驗中證實了這種思路的確可行，而且效果可喜。

下面先來介紹一下第一種構造方法。

Random Fourier Features

對數據點 $x$ ，第一種構造方法是選取一系列的傅立葉基底 $z_omega(x)=cosleft(omega^Tx+b ight)$ 來組成映射 $z(x)=left[z_{omega_1}(x),cdots,z_{omega_D}(x) ight]$ 。其中， $omegain R^d$ 是隨機向量， $bin R$ 是一個隨機變數， $omega_1,cdots,omega_N$ 是 $omega$ 的一些樣本。令 $b$ 服從 $[0,2pi]$ 的均勻分布，於是問題就集中在，怎麼確定 $omega$ 的分布，使得我們隨機抽取 $omega$ 構造出來的映射可以逼近核函數。

這是怎麼想出來的呢？我們又應該怎麼繼續想下去呢？所有的一切，都來源於調和分析中 Bochner 的一個定理（可以到 Rudin 的 Fourier Analysis on Groups 一書中找到）：

（Bochner）一個 $R^d$ 上連續的平移不變核函數 $k(x,y)=k(x-y)$ 是正定的，當且僅當函數 $k(delta)$ 是一個非負測度的傅立葉變換。

如此一來，只要將一個平移不變的核函數 $k(delta)$ 做適當的標準化，根據 Bochner 的定理，它的傅立葉變換 $p(omega)$ 就是一個概率分布函數（pdf）。這裡開始有隨機的影子出現了。記 $zeta_omega(x)=e^{jomega^Tx}$ ，則按 $p(omega)$ 的定義，有：

$k(x-y)=int_{R^d}p(omega)e^{jomega^T(x-y)}domega=int_{R^d}p(omega)e^{jomega^Tx}e^{-jomega^Ty}domega=E_omegaleft[zeta_omega(x)overline{zeta_omega(y)} ight]$

由此可以看到，如果 $omega$ 從分布 $p$ 中取出來，則 $zeta_omega(x)overline{zeta_omega(y)}$ 是 $k(x-y)$ 的無偏估計。這裡又有擬合，逼近的意味在了。因為核函數是實變的，展開上面的積分，虛部捨去，得到：

$k(x-y)=int_{R^d}p(omega)cos(omega^T(x-y))domega$

再補一個在 $[0,2pi]$ 上均勻分布的隨機變數 $b$ ，將容易驗證上式等價於：

$=int_0^{2pi}frac{1}{2pi}dbint_{R^d}p(omega)2cos(omega^Tx+b)cos(omega^Ty+b)domega=E[z_omega(x)z_omega(y)]$

其中 $z_omega(x)=sqrt{2}cos(omega^Tx+b)$ 是實的映射。由此可見， $z_omega(x)z_omega(y)$ 是 $k(x-y)$ 的無偏估計。

得到了 $k(x-y)$ 的無偏估計之後，我們還希望降低估計的方差，這隻要從分布 $p$ 中選取 $D$ 個 $omega$ ，放到一起併除以 $sqrt{D}$ ，就構造出來一個映射 $z$ ，使得內積 $z(x)^Tz(y)=frac{1}{D}sum_{j=1}^Dz_{omega_j}(x)z_{omega_j}(y)$ 是 $D$ 個 $z_omega$ 的樣本均值，這不僅是核函數的無偏估計，而且方差還小。

至此，我們已經得到了構造方法。但是這種構造對目標核函數的逼近程度還有待進一步討論，論文繼續深入探討這件事。論文指出，利用 Hoeffding 不等式：

$Prleft[left|z(x)^Tz(y)-k(x,y) ight|geqepsilon ight]leq2e^{-D(frac{epsilon}{2})^2}$

可以說明，映射 $z$ 對核函數 $k$ 的偏離大於指定精度 $epsilon$ 的概率隨 $D$ 增大而指數遞減。這還不夠，論文作者還希望刻畫映射的一致逼近效果，於是又引出了論文的 Claim 1，以後有時間再深究。

總而言之，隨機離散特徵映射的構造演算法是：

前提條件：正定的，平移不變的核函數 $k(x,y)=k(x-y)$

1. 計算核函數的傅立葉變換 $p(omega)=frac{1}{2pi}int e^{-jomega^Tdelta}k(delta)ddelta$

2. 從分布 $p$ 中選取獨立的 $D$ 個樣本 $omega_1,cdots,omega_D$ ，從 $[0,2pi]$ 上的均勻分布選取獨立的 $D$ 個樣本 $b_1,cdots,b_D$

3. 構造 $z(x)=sqrt{frac{2}{D}}left[cos(omega_1^Tx+b) cdots cos(omega_D^Tx+b) ight]$

後記
論文構造映射 z 的過程中，展示了如何用概率論知識來刻畫隨機帶來的影響，從而藉此指導構造思路。同時，論文展示了數學功底對於開發新演算法的極高重要性。
注意本文對問題是有一些限制條件的，比如隨機傅立葉特徵演算法中，要求核函數是正定，平移不變的，因此可以嘗試討論非正定，或者有方向性的核函數的逼近問題。