C-SVM

SVM(Support Vector Machines)是基于空间度量的线性分割面，最优的分割面原则为：间隔宽度最大化+最小分错样本书

定义模型

计算间隔求出分界面

$$w \cdot (x^+ - x^-) =2 \\ ||w|| \times ||x^+ - x^-|| \times \cos \theta = 2 \\ d = ||x^+ - x^-|| \times \cos \theta$$

目标函数

$$\min_{w}\quad \frac{1}{2} ||w||^2\\ s.t.\quad y_i(w^{T}x_{i})-1 \ge 0,\quad i=1,2,...,N$$

trick:将b整合进w

这就是一个二次规划问题 点到直线距离公式的几种推导

...

线性不可分

若训练数据是线性可分（不存在任何线性分类器可以将其正确分类），或者数据存在噪声。 线性不可分意味着某些样本点不能满足函数间隔大于等于1的约束条件。

目标函数

$$\min_{w}\quad \frac{1}{2} w^Tw + C\sum_{i}\xi_{i}\\ s.t.\quad y_i(w^{T}x_{i})-1+\xi_{i} \ge 0,\quad i=1,2,...,N \\ s.t. \quad \xi_{i} \ge 0$$

Hinge Loss

对于标签t和分类的输出的分数y，Hinge Loss就是 $f(y) = \max (0, 1-ty)$ 当分类正确时，$f(y)=0$

Hinge loss 中文版 Hinge loss

求解

求出目标函数的最优值

拉格朗日函数

对原问题每个约束条件引入拉格朗日乘子 $\alpha_{i} , \mu_i$ 得到:

$$L(w,\xi,\alpha,\mu) = \frac{1}{2}w^Tw +C\sum_{i}\xi_{i} - \sum_{i} \alpha_{i}(y_i(w^{T}x_{i})-1+\xi_{i})- \sum_{i}\mu_{i}\xi_{i} \\ s.t. \quad \alpha_i \ge 0 , \mu_i \ge 0$$

• 对偶函数：$g(\alpha,\mu) = \min_{w,\xi} L(w,\xi,\alpha,\mu)$

• 对偶问题：$\max_{\alpha_{i} \ge 0 , \mu \ge 0} g(\alpha,\mu)$

• 弱对偶定理不等式：

$$\frac{1}{2}w^Tw +C\sum_{i}\xi_{i} \ge L(w,\xi,\alpha,\mu) \ge \min_{w,\xi} L(w,\xi,\alpha,\mu) = g(\alpha,\mu)$$

最小化不等式的左边，最大化不等式的右边

• 弱对偶性定理：原问题的最优值恒大于等于对偶问题的最优值

• 对偶间隙：原问题的最优值和对偶问题最优值的差

• 强对偶性定理：对偶间隙为0，弱对偶定理不等式中的等号全部成立。

$$\frac{1}{2}w^Tw +C \sum_{i} \xi_{i} = L(w,\xi,\alpha,\mu) = \min_{w,\xi} L(w,\xi,\alpha,\mu) = g(\alpha,\mu)$$

• 原问题最优解：$w,\xi$

• 对偶问题最优解：$\alpha,\mu$

对于任何一个非负的实值函数，其极大-极小化与极小-极大化之间存在如下关系 $\max_{x} \min_{y} f(x,y) \le \min_{y} \max_{x} f(x,y)$

• $L$ 对 $w,\xi$ 的导数等于零：

$$\frac{\partial L}{\partial w} = w - \sum_{i} \alpha_{i} y_{i} x_{i} = 0 \Rightarrow w = \sum_{i} \alpha_{i} y_{i} x_{i} ,\\ \frac{\partial L}{\partial \xi_{i}} = C - \alpha_{i} - \mu_{i} =0$$

• 代入w到L：

$$\min_{w,\xi} L(w,\xi,\alpha,\mu) = -\frac{1}{2} \sum_{i,j}y_i y_j \alpha_i \alpha_j x_i x_j + \sum_{i} (C-\xi_{i} - \alpha_{i})\xi_{i} + \sum_{i} \alpha_{i} \\ = \sum_{i} \alpha_{i} -\frac{1}{2} \sum_{i,j}y_i y_j \alpha_i \alpha_j \langle x_i, x_j \rangle \\ = \max_{\alpha} g(\alpha) \\ s.t. \quad 0 \le \alpha_i \le C , \forall i$$

• 最优解对应的KKT条件：

$$y_i(w^{T}x_{i})-1+\xi_{i} \ge 0 ,\\ \xi_{i} \ge 0 ,\\ \alpha_i \ge 0 ,\\ \mu_i \ge 0 ,\\ \text{约束条件} \\ C - \alpha_{i} - \mu_{i} =0 \Rightarrow C - \alpha_{i} \ge 0 ,\\ \text{驻点条件} \\ \alpha_{i}(y_i(w^{T}x_{i})-1+\xi_{i}) =0,\\ \mu_{i}\xi_{i} = 0 \Rightarrow \xi_{i}(C-\alpha_{i}) = 0 \\ \text{互补松弛性}$$

得出：

$$0 \lt \alpha_i \lt C \Rightarrow y_i f_i =1 \\ \alpha_i = 0 \Rightarrow y_i f_i \ge 1 , \xi_i = 0 \\ \alpha_i = C \Rightarrow y_i f_i \le 1 , \xi_i \ge 0 \\$$

如何理解拉格朗日乘子法

非线性SVM

对偶函数

$$\max_{\alpha} g(\alpha) = \sum_{i} \alpha_{i} -\frac{1}{2} \sum_{i,j}y_i y_j \alpha_i \alpha_j K \langle \phi (x_i), \phi (x_j) \rangle \\ s.t. \quad 0 \le \alpha_i \le C , \forall i$$

核函数

• 线性核: $K \langle x_i, x_j \rangle = x_i^T x_j$

• 多项式核: $K \langle x_i, x_j \rangle = (1 + x_i^T x_j)^p$

• 高斯核（Radial basis function kernel，简称RBF）: $K \langle x_i, x_j \rangle = \exp(- \frac{||x_i - x_j||^2}{2\sigma^2})$

• sigmoid核: $K \langle x_i, x_j \rangle = tanH(\beta_0 x_i^T x_j +\beta_1)$

  为什么Gaussian kernel为无线维。因为e是一种极限。对$e^x$泰勒展开、即是用多项式逼近，得：$e^x = \lim_{n \to \infty} \sum_{i=0}^n \frac {x^i}{i!}$ e=2.7…是怎么算出来的 数学里的 e 为什么叫做自然底数 数学中以e为底的指数函数f(x)=exp(x)求导后为什么还是它本身

机器学习里的kernel是指什么 典型的再生核 Hilbert 空间理论（RKHS）

径向基(Radial basis function)神经网络、核函数的一些理解

对于多分类问题以及核函数的选取，以下经验规则可以借鉴：

• 如果如果特征数远远大于样本数的情况下,使用线性核就可以了.

• 如果特征数和样本数都很大,例如文档分类,一般使用线性核, LIBLINEAR比LIBSVM速度要快很多.

• 如果特征数远小于样本数,这种情况一般使用RBF.但是如果一定要用线性核,则选择LIBLINEAR较好,而且使用-s 2选项

  《机器学习技法》上说，实战中应先用简单的kernel，拟合效果不好的话，再用更强大的高斯核

怎么形象地理解对偶空间(Dual Vector Space) 看了这篇文章你还不能理解对偶空间算我输 线性泛函 关于 L^p 空间的对偶问题

求解对偶函数

对偶函数统一形式

$$\min_{\alpha} \frac{1}{2} \alpha^T Q \alpha - e^T\alpha \\ subject to \quad 0 \le \alpha_i \le C , \forall i$$

障碍函数法

将不等式约束条件作为惩罚项，然后用障碍函数法迭代求解。 但是，原目标函数也是可以用障碍函数法求解的。就SVM而言，在对偶空间中障碍函数法会快速收敛，远快于原目标函数。 其他算法会不会也在对偶空间中迭代会快速？