要真正了解SVM (Support Vector Machines, 支持向量機), 必須了解什麼是核模型和核技巧, 假如只粗淺地知道它是一個最大化間隔(margin)的方法就太可惜了。以下從線性模型(Linear Model)開始, 逐步講到核模型(Kernel Model), 一窺其優雅之處。
線性模型(Linear Model)
假如我們要學習一個函數\(f\), 而假定這個函數的輸入(input)是一維的, 輸出是一個純量(scalar), 最直觀的函數模擬方式就是線性模型, 考慮一個線性加法模型, 也就是把每個\(x\)前面冠上一個參數\(\theta\), 再線性加總起來:
\[f_{\theta}=\sum_{j=1}^{d} \theta_{j}x_{j}=\Theta\mathbf{x}\]
\[\mathbf{x} = (x_1, x_2, ..., x_d)^T\]
\[\Theta = (\theta_1, \theta_2,..., \theta_d)\]
廣義線性模型(Generailized Linear Model)
然而, 當遇到複雜函數時, 線性模型顯然不足以表達, 因此定義廣義線性模型:
\[f_{\theta}=\sum_{j=1}^{b} \theta_{j}\phi_{j}(\mathbf{x})=\Theta\Phi\]
\[\Theta = (\theta_1, \theta_2,..., \theta_b)\]
\[\Phi = (\phi_1(\mathbf{x}),\phi_2(\mathbf{x}), ..., \phi_b(\mathbf{x}))^T \]
其中, \(b\)是基函數(basis function)的個數, 此時就可以來表達非線性模型了, 可以透過設計一組好的基函數, 來增加模型的表達能力。
為了把特徵空間複雜化, 通常基函數的個數\(b\)會遠大於輸入的維度\(d\) (\(b>>d\)), 這個\(\phi\)可以視為是將特徵從\(d\)維映射到\(b\)維的函數。
特徵複雜化之後可以做什麼呢?
(1)對於迴歸(regression)型任務, 特徵複雜化有助於函數擬合(curve fitting)。
(2)對於分類(classification)型任務, 特徵複雜化有助於找到好的分割超平面(hyperplane)。
這裡的基函數, 可以定義成:
\[\phi(x)=(1, x, x^2, ..., x^{(b-1)})^T\]
這種形式, \(f_{\theta}\)就成為多項式(polynomial)
或是定義成:
\[\phi(x)=(1, sin(x), cos(x), sin(2x), cos(2x)..., sin(mx), cos(mx))^T\]
\[b=2m+1\] 函數\(f_{\theta}\)就成為離散傅立葉級數(Discrete Fourier series)。
經過適當設計,可以讓\(\Phi(\mathbf{x})\)成為對\(\mathbf{x}\)進行離散傅立葉變換（Discrete Fourier Transform，DFT）。
如果考慮連續傅立葉變換, 基函數可以無窮多個, 也就是說, 甚至可以將特徵從維度\(d\)投影到無窮維。
核模型(Kernel Model)
前面講到, 廣義線性模型將特徵\(\mathbf{x}\)透過\(\phi\)映射到更多維甚至無窮維的空間, 這時候就產生一個問題: 如何設計最好的\(\phi\)?
這是一個頗難的問題, 想想看, 先不要管基函數的形式怎麼設計(多項式?三角函數?指數?), 光是基函數的個數\(b\)就難以決定: 到底要投影到幾維才足夠複雜到可以解決任務, 且維度詛咒(curse of dimensionality)又不至於太過嚴重呢?
面對這種看起來毫無頭緒的問題, 這時候需要引入一些先驗假設, 而最好的先驗知識來源, 就是我們的輸入樣本(也就是數據)。
試想, 假如數據中隱含某種模式或原則, 符合模式的那些樣本彼此之間應該距離較近; 或者換個方式說, 過去有出現過的樣本在特徵空間中的分布如果集中在某個位置, 我們可以假定下一個出現的樣本應該有比較大的機率出現在相同位置。
因此, 想要從樣本中找規律, 我們有時會希望讓不同樣本之間可以產生一些互動, 此時通常會涉及到計算:\(\phi(x_i)\phi(x_j)\), 也就是兩個特徵向量的內積, 而這個內積其實並不好計算, 尤其當特徵空間維度(基函數個數\(b\))很大的時候。
此時核函數(kernel function)\(K\)就能派上用場, 核函數是一個二元函數\(K(\cdot,\cdot)\) 是一個定義內積的函數, 可被設計, 而核模型(Kernel Model)可以表示為核函數的線性組合。
\[f_{\theta}=\sum_{j=1}^{n} \theta_{j}K(\mathbf{x},\mathbf{x}_ j)=\Theta\mathbf{K}\]
其中\(n\)是樣本數, 注意: 線性模型的基函數與樣本無關, 然而核模型設計時會用到輸入樣本 
, 核函數構成的矩陣\(\mathbf{K}\)可以寫成:
值得注意的是, 核模型的參數個數只與樣本數\(n\)有關, 與輸入的維度\(d\)無關, 這代表在樣本數不大(\(d>>n\))的情形下, 核模型可以避免維度災難。
即使\(n\)很大, 只要取輸入樣本 的部分集合均值 
來進行計算 $ (b<<n) $ , 維度也能得到很好的控制。
\[f_{\theta}=\sum_{j=1}^{b} \theta_{j} K(\mathbf{x},\mathbf{c}_ j)=\Theta\mathbf{K}_{b \times n}\]
核模型並非線性模型, 但是線性模型可以視為核模型的特例。
透過這種定義核函數的方法, 對基函數的內積進行特殊設計, 使得不須直接設計基函數, 透過定義核函數而隱式地(implicitly)定義了基函數, 這種方法稱為核技巧(kernel trick)或核方法(kernel method)。
核函數的設計要滿足一些條件, 核函數必須是對稱函數, 且所構成的核矩陣$ $必須要是半正定(證明可參考Scholkopf and Smola, 2002)
幾種常用的核函數如下:
- 線性核
\[K(\mathbf{x}_i, \mathbf{x}_j)=\mathbf{x}_i^{T}\mathbf{x}_j\]
- 多項式核
\[K(\mathbf{x}_i, \mathbf{x}_j)=(\mathbf{x}_i^{T}\mathbf{x}_j)^d, d\geq1\]
- 高斯核(一種徑向基函數核, Radial basis function kernel, RBF核)
\[K(\mathbf{x}_i, \mathbf{x}_j)=exp(-\frac{||\mathbf{x}_i-\mathbf{x}_j||^2}{2\sigma^2})\]
高斯核(RBF核)是最常用的一種kernel, 它的意義是將每個樣本的出現都視為由一個高斯分布的隨機變數\(X_j \sim N(\mathbf{x}_{j}, \sigma)\)生成, 而待學習的參數\(\theta_j\)則是這個分布的高度。
高斯核模型是用高斯核函數的加權加總在逼近一個未知函數, 這個函數逼近的過程可以看做是一個簡單神經網路。
高斯核模型又有點像是\(n\)個Component的高斯混合模型（Gaussian mixture model，GMM）, 兩者都需要學習每個高斯的權重(weight), 但兩者仍有本質上的不同, GMM的機率密度函數是學習出來的, 在高斯核模型中, 期望值(Means)和共變異數（Covariances）都是固定的, 不像在GMM中是可學習的參數, 這是由於RBF核當初設計的目的是為了做多變量插值的緣故。