基本型
用一个超平面去分割空间中的点，任意点x到超平面的距离可表示为:
\[r = \frac{|\textbf{w}^T\textbf{x}+b|}{||\textbf w||}
\]
为了把正负样本分开，引入两个支持平面，使正负样本在两个支持平面两侧，定义线性映射后的表达式为
\[\begin{cases}
\textbf{w}^T\textbf{x}+b \geq +1, & & y=+1 \\textbf{w}^T\textbf{x}+b \leq -1, & & y=-1 \\end{cases}
\ \ \ \ \to \ \ \ \
y(\textbf{w}^T\textbf{x}+b)\geq1
\]
表达式中，两支持平面之间的距离为
\[\gamma = \frac{2}{||\textbf{w}||}
\]
这样就能得到支持向量机的基本型
\[\max \limits_{\textbf{w},b} \frac{2}{||\textbf{w}||}
\ \ \ \ \to \ \ \ \
\min \limits_{\textbf{w},b} \frac 12 {||\textbf{w}||}^2
\\ s.t.\ \ y_i(\textbf{w}^T\textbf{x}_i+b) \geq 1
, \ \ \ \ i= 1,2,...m
\]
拉格朗日乘子法-不等式约束
给定如下不等式，并使用拉格朗日乘子
\[\min \limits_{x} f(x), \ \ \ \ s. t. \ g(x) \leq0 \\]
现在考虑
- 如果解在 g(x)=0 边界上，那么约束有效果
- 如果解在 g(x)<0 内部，那么这个约束没有任何作用
- f(x) 梯度与 g(x) 梯度是反向
因此，如论如何，都有
\[\lambda g(x)=0, \ \ \lambda \geq 0
\]
于是可用等式约束的方法
\[L = f(x)+\lambda g(x)
\]
对偶问题
使用拉格朗日乘子法，得到
\[L = \frac 12 {||\textbf{w}||}^2
+\sum_{i=1}^m \alpha_i(1-y_i(\textbf{w}^T\textbf{x}_i+b))\\frac{\partial L}{\partial \textbf{w}} = 0
\ \ \to \ \ \textbf{w}=\sum_{i=1}^m\alpha_iy_i\textbf{x}_i \\frac{\partial L}{\partial b} = 0
\ \ \to \ \ \sum_{i=1}^m\alpha_iy_i = 0
\]
消去参数w和b，转换成对偶问题
\[\max \limits_{\alpha} \sum_{i=1}^m\alpha_i-\frac 12
\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\textbf{x}_i^T\textbf{x}_j\s.t. \ \sum_{i=1}^m\alpha_iy_i = 0 \f(\textbf{x}) = \textbf{w}^T\textbf{x}+b=
\sum_{i=1}^m\alpha_iy_i\textbf{x}_i^T\textbf{x}+b\\]
需要满足的条件（KKT）
\[\begin{cases}
\alpha_i \geq 0 \y_i f(x_i)-1 \geq 0 \\alpha_i(y_if(x_i)-1)=0
\end{cases}
\]
支持向量机（SVM）
原文：https://www.cnblogs.com/xytpai/p/12849293.html
