线性可分支持向量机对偶算法

算法
导出思路

算法

$\qquad$ 输入：线性可分训练集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $x_i\in \Bbb R^n,y_i\in\{-1,+1\}$

$\qquad$ 输出：分离超平面和分类决策函数

$\qquad$ (1) 构造并求解约束最优化问题

$\begin{aligned}&\min_\alpha \quad\frac 1 2 \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N \alpha_i\\ &\text {s.t.}\qquad \sum_{i=1}^N\alpha_iy_i=0\\ &\alpha_i \ge 0,\quad i=1,2,\cdots,N\end{aligned}$

求得最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)^T$ .

$\qquad$ (2) 计算

$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$

并选择 $\alpha^*$ 的一个正分量 $\alpha_j^* \gt 0$ ，计算

$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$

$\qquad$ (3) 求得分离超平面

$w^*\cdot x+b^*=0$

分类决策函数：

$f(x)=\text {sign}(w^*\cdot x+b^*)$

导出思路

通过原始算法的最优化问题，构造拉格朗日函数：

$L(w,b,\alpha)=\frac 1 2\|w\|^2-\sum_{i=1}^N \alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i,\quad \alpha_i \ge 0$

对偶问题为极大极小问题：

$\max_\alpha\min_{w,b}L(w,b,\alpha)$

(1) 求 $\min_{w,b}L(w,b,\alpha)$

$\left. \begin{array}{l} \ \nabla_wL(w,b,\alpha)=0\\ \ \nabla_bL(w,b,\alpha)=0 \end{array} \right\} \Rightarrow \left\{ \begin{array}{l} \ w=\sum_{i=1}^N\alpha_iy_ix_i\\ \ \sum_{i=1}^N\alpha_iy_i=0 \end{array} \right.$

$\Rightarrow\min_{w,b}L(w,b,\alpha)=-\frac 1 2\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$

(2)求 $\min_{w,b}L(w,b,\alpha)$ 对 $\alpha$ 的极大，并将极大转换为极小，最终得到最优化问题：

$\begin{align}&\min_\alpha \quad\frac 1 2 \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N \alpha_i\\ &\text {s.t.}\qquad \sum_{i=1}^N\alpha_iy_i=0\\ &\alpha_i \ge 0,\quad i=1,2,\cdots,N\end{align}$

$b^*$ 由 KKT 条件得出 .

线性可分支持向量机对偶算法

算法

导出思路

留言