机器学习基础算法 -- 支持向量机（Support Vector Machines）

本文主要记录 SVM 相关算法核心公式推导。

原问题

原始最优化问题一般形式为：

其中， 在 上连续可微。

引入广义 Lagrange 函数：

， 是 Lagrange 乘子，

原问题的等价无约束形式为：

对偶问题

定义

注意，对偶问题是关于 的最大化问题，而原问题是关于 的最大化问题。

由于

所以下述不等式恒成立

当 时，为强对偶；当 时，为弱对偶。

强对偶需要满足 Karush-Kuhn-Tucker (KKT) 条件，具体包括

• 原始问题的约束条件；
• Lagrange 函数约束条件；
• 互补松弛条件；
• Lagrange 函数极值必要条件（梯度为 0）；

硬间隔 SVM

其一般表达式为

引入 Lagrange 函数：

其对偶形式为

满足强对偶关系的 KKT 条件为：

软间隔 SVM

其一般表达式为

引入 Lagrange 函数：

其对偶形式为

满足强对偶关系的 KKT 条件为：

核函数

其基本定义为，对于输入空间 中的任意样本 ，存在一个函数 ，始终满足

其中，函数 作用是完成低维到高维空间的映射。

Reference

机器学习 (nju.edu.cn)

统计学习方法 (豆瓣) (douban.com)

支持向量机通俗导论（理解 SVM 的三层境界）_结构之法 算法之道-CSDN 博客_svm

Karush–Kuhn–Tucker conditions - Wikipedia