支持向量机对偶问题推导

支持向量机对偶问题推导支持向量机(SupportVectorMachine,SVM)是一个强大且常用的机器学习算法，它可以用于分类和回归问题。SVM是一种非概率性的二分类模型，其基本思想是找到一个最优的超平面，将两个类别的样本分开。

在SVM中，原始问题可以被转化为一个对偶问题。对偶问题的求解速度更快，并且可以引入核函数，使得SVM可以处理非线性可分的问题。下面将推导出SVM的对偶问题。

假设给定一个训练集$D=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$，其中$x_i$为输入样本，$y_i\in\{-1,1\}$为对应的标签。我们的目标是找到一个超平面$w\cdotx+b=0$，使得将样本正确地分开，并且使得超平面到最近的样本点的距离最大化。

我们定义样本到超平面的距离为$|w\cdotx+b|/||w||$，其中$||w||$是$w$的范数。我们将这个距离记为$\gamma$。

我们的目标是最大化$\gamma$，即

$$

\begin{align*}

\max_{w,b,\gamma}\quad&\gamma\\

\text{s.t.}\quad&y_i(w\cdotx_i+b)\geq\gamma,\quadi=1,2,...,n\\

&||w||=1

\end{align*}

$$

根据几何性质，我们可以将上述问题转化为：

$$

\begin{align*}

\max_{w,b,\gamma}\quad&\frac{\gamma}{||w||}\\

\text{s.t.}\quad&y_i(w\cdotx_i+b)\geq\gamma,\quadi=1,2,...,n\\

\end{align*}

$$

我们令$\rho=\frac{\gamma}{||w||}$，将上述问题转化为：

$$

\begin{align*}

\max_{w,b,\rho}\quad&\rho\\

\text{s.t.}\quad&y_i(w\cdotx_i+b)\geq\rho,\quadi=1,2,...,n\\

&||w||=\frac{1}{\rho}

\end{align*}

$$

我们在约束条件中引入松弛变量$\xi_i\geq0$，使得约束条件变为：

$$

y_i(w\cdotx_i+b)\geq\rho-\xi_i,\quadi=1,2,...,n

$$

我们最终的优化目标变为：

$$

\begin{align*}

\min_{w,b,\rho,\xi}\quad&\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i\\

\text{s.t.}\quad&y_i(w\cdotx_i+b)\geq\rho-\xi_i,\quadi=1,2,...,n\\

&\xi_i\geq0,\quadi=1,2,...,n

\end{align*}

$$

其中，$C$是一个超参数，控制了对误分类的惩罚程度。较大的$C$值会使得模型更关注于正确分类，而较小的$C$值会使得模型更关注于找到较大的间隔。

通过拉格朗日对偶性，我们引入拉格朗日乘子$\alpha_i\geq0$和$\beta_i\geq0$，并构建拉格朗日函数：

$$

L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w\cdotx_i+b)-\rho+\xi_i)-\sum_{i=1}^n\beta_i\xi_i

$$

对偶问题的目标是最小化拉格朗日函数关于原始问题的变量，即：

$$

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

$$

通过对$\alpha,\beta$求偏导并令导数为0，可以推导出对偶问题：

$$

\begin{align*}

\max_{\alpha}\quad&\tilde{L}(\alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^ny_iy_j\alpha_i\alpha_j(x_i\cdotx_j)\\

&0\leq\alpha_i\leqC\\

&\sum_{i=1}^n\alpha_iy_i=0

\end{align*}

$$

在求解对偶问题后，通过$\alpha_i$可以计算出最优的$w$和$b$，并进一步用于新样本点的分类。

在支持向量机的实际应用中，常常会使用核函数来将特征空间映射到更高维的空间，使得非线性可分的问题变为线性可分的问题。最常见的核函数是径向基函数(RadialBasisFunction,RBF)。通过引入核函数，SVM可以处理复杂的数据集并取得更好的分类效果。