Chapter 12. Support Vector Machines and Flexible Discriminants
终于来到大名鼎鼎的 SVM。其实在2010年左右,已经好奇了解过 SVM,网络上看过很多的解释。当时感觉就是个平面分类,就是在学习之前,先把数据映射到高维空间,好让他们可以被不同的平面分割。其实我的理解没错,但似懂非懂。这才是最糟糕的,你以为你懂了,但那只是皮毛。
SVM 的精髓在于 support vector,以及该算法背后严密的数学逻辑(求解凸优化问题),让其自成一派。
$$ \max_{\beta, \beta_0, \|\beta\|=1 } M \\ s.t. \ y_i(x_i^T \beta + \beta_0) \geq M, i=1,2,\cdots,M $$
$$ \max_{\beta, \beta_0, \|\beta\|=1 } M \\ s.t. \ y_i(x_i^T \beta + \beta_0) \geq M(1-\xi_0), i=1,2,\cdots,M \\ \sum_{i=1}^N \xi_i \leq constant $$
$$ \min \|\beta\| \\ s.t. \ y_i(x_i^T \beta + \beta_0) \geq (1-\xi_0), i=1,2,\cdots,M \\ \xi_i\geq 0,\sum_{i=1}^N \xi_i \leq constant $$ SVM 优势之一:问题的最优解只与那些落在边界内部的点相关,而每个点对应一个 support vector;与落在边界外面的点无关($\xi_i =0$)。点的总数越少,算法估计就越快。
SVM 优势之二:数学严格的最优化求解过程。
$$ \min_{\beta, \beta_0} \frac{1}{2}\|\beta\| + C \sum_{i=1}^N \xi_i \\ s.t. \ y_i(x_i^T \beta + \beta_0) \geq (1-\xi_0), i=1,2,\cdots,M \\ \xi_i\geq 0 $$
\begin{align} \alpha_i [y_i(x_i^T\beta + \beta_0) - (1-\xi_i)] = & 0 \\ \hat{\beta} = & \sum_{i=1}^N \hat{\alpha}_i y_i x_i \end{align} 这里非零的 $\hat{\alpha}_i$ 就是 support vectors。请留意到,对于边界外的点,$y_i(x_i^T\beta + \beta_0) = 1$,所以有 $\alpha_i = 0$.
\begin{align} f(x) =& h(x)^T\beta+\beta_0 \\ =& \sum_{i=1}^N \hat{\alpha}_i y_i K(x,x_i) + \hat{\beta}_0 \end{align} 关于 kernel 的理解可以参考第六章节。Kernel 的妙处是,不管映射的空间有多少维,无穷也行,最终的计算都是一个有限维度 $N \times N$ 的内积。
$$ ASR = \frac{1}{N} \sum_{l=1}^L \left[ \sum_{i=1}^N (\theta_l(g_i) - \eta_l(x_i))^2 + \lambda J(\eta_l)\right] $$
$$ ASR = \frac{1}{N} \sum_{l=1}^L \left[ \sum_{i=1}^N (\theta_l(g_i) - h^T(x_i)\beta_l )^2 + \lambda\beta_l^T \mathbf{\Omega}\beta_l \right] $$
好吧,不可否认 LDA 玩的溜很重要。但是,这几个 LDA 的衍生版本,根本不配与 SVM 相提并论。可能,在作者看来,这些都与 LDA 有关联,但是,这几个 FDA,PDA, MDA 都不存在严谨的数学逻辑。属于打补丁性质。