一、SVM原问题及要变成对偶问题的解决办法

对于SVM的，我们知道其终于目的是求取一分类超平面，然后将新的数据带入这一分类超平面的方程中，推断输出结果的符号，从而推断新的数据的正负。

而求解svm分类器模型。终于能够化成例如以下的最优化问题：

<script type="math/tex; mode=display" id="MathJax-Element-1">\begin{aligned} \displaystyle{\min_{w,b}} \hspace{1cm}&{1\over 2}\parallel w \parallel ^2\s.t.\hspace{1cm}&1-y_i(w\cdot x_i +b)\leq 0\&i=1,2,...,N \end{aligned}</script>上式中。yi<script type="math/tex" id="MathJax-Element-2">y_i</script>相应样本xi<script type="math/tex" id="MathJax-Element-3">x_i</script>的标签。
我们的目的是求出上述最优化问题的最优解，w?<script type="math/tex" id="MathJax-Element-4">w^*</script>和b?<script type="math/tex" id="MathJax-Element-5">b^*</script>，从而得到分类超平面：
<script type="math/tex; mode=display" id="MathJax-Element-6">w^*\cdot x +b^* = 0</script>进而得到分类决策函
<script type="math/tex; mode=display" id="MathJax-Element-7">f(x) = sign(w^*\cdot x+b)</script>可是在求解这一最优化问题时。求解较为困难，且对于线性不可分的数据无法得到较好的分类超平面。因此依据拉格朗日对偶性，引进原最优化问题的对偶问题，通过求解对偶问题得到原始问题的最优解。

对偶问题的引进有两个方面。一是对偶问题的求解往往比原问题easy。二是对于线性不可分的数据能够通过加松弛变量、加核函数的方法，将其推广到非线性分类。

二、原始SVM的对偶问题及其求解

原始的SVM模型的原问题例如以下：

<script type="math/tex; mode=display" id="MathJax-Element-8">\begin{aligned} {\min_{w,b}} \hspace{1cm}&{1\over 2}\parallel w \parallel ^2\s.t.\hspace{1cm}&1-y_i(w\cdot x_i +b)\leq 0\&i=1,2,...,N \end{aligned}</script>为方便计算，将范数形式改写成例如以下形式：
<script type="math/tex; mode=display" id="MathJax-Element-9">\begin{aligned} \displaystyle{\min_{w,b}} \hspace{1cm}&{1\over 2}w^Tw\s.t.\hspace{1cm}&1-y_i(w\cdot x_i +b)\leq 0\&i=1,2,...,N \end{aligned}</script>要想求原始问题的对偶问题。首先构造拉格朗日函数入例如以下：
<script type="math/tex; mode=display" id="MathJax-Element-10">L(w,b,\lambda) = \frac{1}{2}w^Tw + \sum_{i=1}^N \lambda_i[ 1-y_i(w^Tx_i+b)]\\ \lambda _i\geq0, \hspace{1cm}i=1,2,...,N</script>上式中的λi<script type="math/tex" id="MathJax-Element-11">\lambda_i</script>是拉格朗日乘子。
观察上述式子。可发现
<script type="math/tex; mode=display" id="MathJax-Element-12">\lambda_i[1-y_i(w^Tx_i+b)]\leq0</script>
所以L(w,b,λ)≤12wTw<script type="math/tex" id="MathJax-Element-13">L(w,b,\lambda) \leq \frac{1}{2}w^Tw</script>，即构造的拉格朗日函数是原问题的一个下界。

依据拉格朗日对偶性。原始问题的的对偶问题是极大化极小问题：

<script type="math/tex; mode=display" id="MathJax-Element-14">\max _{\lambda}\min_{w,b}L(w,b,\lambda)</script>上式所表达的意思是，先求L(w,b,λ)<script type="math/tex" id="MathJax-Element-15">L(w,b,\lambda)</script>对w,b<script type="math/tex" id="MathJax-Element-16">w,b</script>的极小，再求对λ<script type="math/tex" id="MathJax-Element-17">\lambda</script>的极大。
首先。求minw,bL(w,b,λ)<script type="math/tex" id="MathJax-Element-18">\min _{w,b}L(w,b,\lambda)</script>：
我们知道。对于一阶可导函数，其在导数值为0的地方。取到极大或极小值，对于我们构造的拉格朗日函数，其偏导导数为0的点，一定是极小值。故：
<script type="math/tex; mode=display" id="MathJax-Element-19">\begin{aligned} &0=\frac{\partial}{\partial w}L(w,b,\lambda)=w+\sum_{i=1}^N\lambda_i(-y_i x_i)\Rightarrow w= \sum_{i=1}^N\lambda_iy_i x_i\&0=\frac{\partial}{\partial b}L(w,b,\lambda)=-\sum_{i=1}^N\lambda_iy_i\Rightarrow \sum_{i=1}^N\lambda_iy_i = 0 \end{aligned}</script>将求得的w<script type="math/tex" id="MathJax-Element-20">w</script>代入拉格朗日函数，可得
<script type="math/tex; mode=display" id="MathJax-Element-21"> L(w,b,\lambda)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i \-\sum_{i=1}^N\lambda_iy_i\left(\sum_{j=1}^N\lambda_jy_jx_j^Tx_i+b \right) </script>由于∑Ni=1λiyi=0<script type="math/tex" id="MathJax-Element-22">\sum_{i=1}^N\lambda_iy_i = 0</script>，故
<script type="math/tex; mode=display" id="MathJax-Element-23"> L(w,b,\lambda)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i </script>所以
<script type="math/tex; mode=display" id="MathJax-Element-24"> g(\lambda)=\min_{w,b}L(w,b,\lambda)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i </script>依据拉格朗日对偶的极大极小的性质，可知对偶问题的目标是：
<script type="math/tex; mode=display" id="MathJax-Element-25"> \max_{\lambda} \hspace{1cm}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i\</script>如今再找约束条件，即在前面的推导过程中。遇到与λ<script type="math/tex" id="MathJax-Element-26">\lambda</script>有关的等式或不等式，且该等式或不等式中不含原问的目标变量。
可发现，在对b求偏导是得到∑Ni=1λiyi=0<script type="math/tex" id="MathJax-Element-27">\sum_{i=1}^N\lambda_iy_i = 0</script>，故这是一个约束条件，另外在构造拉格朗日函数时。约定了λi≥0<script type="math/tex" id="MathJax-Element-28">\lambda_i\geq0</script>，故原问题的对偶问题能够写成例如以下形式：
<script type="math/tex; mode=display" id="MathJax-Element-29">\begin{aligned} \displaystyle \max_{\lambda} \hspace{1cm}&-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i\s.t. \hspace{1cm}&\sum_{i=1}^N\lambda_iy_i = 0\&\lambda_i\geq0,\hspace{0.5cm}i=1,2,...,N \end{aligned}</script>故此得到了原始的SVM的对偶形式。如今考虑怎样从对偶问题中求得原问题的最优解。

考虑对偶问题的最优化问题。存在λ?<script type="math/tex" id="MathJax-Element-30">\lambda^*</script>是对偶的最优解。又由于

<script type="math/tex; mode=display" id="MathJax-Element-31">w= \sum_{i=1}^N\lambda_iy_i x_i</script>
故能够解得
<script type="math/tex; mode=display" id="MathJax-Element-32">w^*= \sum_{i=1}^N\lambda_i^*y_i x_i</script>
同一时候依据KTT条件原理（这里不做解释，能够自行查阅资料，不论什么关于最优化理论、凸优化的书都会说到这个），可解得b的值：
<script type="math/tex; mode=display" id="MathJax-Element-33">b^*=y_j-\sum_{i=1}^N\lambda_i^*y_ix_i^Tx_j</script>故分离超平面为：
<script type="math/tex; mode=display" id="MathJax-Element-34">\sum_{i=1}^N\lambda_i^*y_ix_i^Tx+b=0</script>分类决策函数为：
<script type="math/tex; mode=display" id="MathJax-Element-35">f(x)=sign\left(\sum_{i=1}^N\lambda_i^*y_ix_i^Tx+b \right)</script>

三、加松弛变量SVM的对偶问题

如上文所述。对于线性可分的数据，能够构造SVM模型。并将其转换为一个最优化问题，且这个优化问题的约束条件是对于全部的样本。都有1?yi(wTxi+b)≤0<script type="math/tex" id="MathJax-Element-36">1-y_i(w^Tx_i+b)\leq0</script>。则对于线性不可分的数据。在数学形式的解释为存在某个样本(x,y)使上述的约束不成立，即1?y(wTx+b)>0<script type="math/tex" id="MathJax-Element-37">1-y(w^Tx+b)>0</script>。
既然约束条件不成立，那是否能增加一个松弛变量ξ，ξ≥0<script type="math/tex" id="MathJax-Element-38">\xi，\xi\geq0</script>,使得1?y(wTx+b)?ξ≤0<script type="math/tex" id="MathJax-Element-39">1-y(w^Tx+b)-\xi\leq0</script>？
正是基于这个思想，出现了加松弛变量的SVM，其原始问题的形式例如以下：

<script type="math/tex; mode=display" id="MathJax-Element-40">\begin{aligned} \displaystyle{\min_{w,b}} \hspace{1cm}&{1\over 2}w^Tw+C\sum_{i=1}^N\xi_i\s.t.\hspace{1cm}&1-y_i(w\cdot x_i +b)-\xi_i\leq 0\&-\xi_i\leq0\&i=1,2,...,N \end{aligned}</script>当中C为常数，ξi<script type="math/tex" id="MathJax-Element-41">\xi_i</script>为松弛变量。
由于我在约束中加了松弛变量，可是我们希望我们所加的松弛变量越小越好。这样越接近于原约束条件。故把“松弛变量越小越好”这一期望，放在目标函数中，由于目标函数是求最小值，故加上C∑Ni=1ξi<script type="math/tex" id="MathJax-Element-42">C\sum_{i=1}^N\xi_i</script>，这一项也被称为“惩处项”。能够理解为增加的松弛变量越大。对目标函数的惩处力度越高。
现要求其对偶问题。相似于前面的解法，首先构造拉格朗日函数例如以下：
<script type="math/tex; mode=display" id="MathJax-Element-43">L(w,b,\xi,\lambda,\beta)=\frac{1}{2}w^Tw+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N \lambda_i[ 1-y_i(w^Tx_i+b)-\xi_i]\\+\sum_{i=1}^N\beta_i(-\xi_i)</script>相同。求偏导可得：
<script type="math/tex; mode=display" id="MathJax-Element-44">\begin{aligned} &0=\frac{\partial}{\partial w}L(w,b,\lambda)=w+\sum_{i=1}^N\lambda_i(-y_i x_i)\Rightarrow w= \sum_{i=1}^N\lambda_iy_i x_i\&0=\frac{\partial}{\partial b}L(w,b,\lambda)=-\sum_{i=1}^N\lambda_iy_i\Rightarrow \sum_{i=1}^N\lambda_iy_i = 0\&0=\frac{\partial}{\partial \xi_i}=C-\lambda_i-\beta_i\Rightarrow\lambda_i=C-\beta_i\leq C \end{aligned}</script>将结果代回拉格朗日函数。可得例如以下形式：
<script type="math/tex; mode=display" id="MathJax-Element-45"> L(w,b,\lambda)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i \+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\lambda_i\xi_i-\sum_{i=1}^N\beta_i\xi_i </script>由于C?λi?βi=0<script type="math/tex" id="MathJax-Element-46">C-\lambda_i-\beta_i=0</script>。所以
<script type="math/tex; mode=display" id="MathJax-Element-47">C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\lambda_i\xi_i-\sum_{i=1}^N\beta_i\xi_i=0</script>故
<script type="math/tex; mode=display" id="MathJax-Element-48"> g(\lambda,\beta)=\min_{w,b}L(w,b,\lambda)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i </script>则对偶形式为
<script type="math/tex; mode=display" id="MathJax-Element-49">\begin{aligned} \displaystyle \max_{\lambda} \hspace{1cm}&-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i\s.t. \hspace{1cm}&\sum_{i=1}^N\lambda_iy_i = 0\&0\leq\lambda_i\leq C,\hspace{0.5cm}i=1,2,...,N \end{aligned}</script>观察上式可发现，对于原问题。加了松弛变量后，其对偶形式变化比較小，仅仅是在约束条件上有些许变化。从这点也可发现将原问题化成对偶问题的优点，即原问题形式的变化非常大，可是对偶问题变化却非常小，方便求解。

所以非常多优化问题。假设在原问题上较为难实现，则能够考虑转化为对偶问题。

四、加核函数SVM的对偶问题

加核函数的思想是：
通过一个非线性变化将输入空间映射到一个更高维的特征空间（希尔伯特空间），使得在输入空间中的超曲面模型相应希尔伯特空间中的超平面模型。

因此，在输入空间的非线性分类问题能够变成希尔伯特空间中的线性分类问题，故能够继续使用SVM模型。

核函数的定义：
设X<script type="math/tex" id="MathJax-Element-50">\mathbb X</script>是输入空间（欧式空间Rn<script type="math/tex" id="MathJax-Element-51">R^n</script>的子集或离散集合），又设H<script type="math/tex" id="MathJax-Element-52">\mathbb H</script>为特征空间（希尔伯特空间）。假设存在一个从X<script type="math/tex" id="MathJax-Element-53">\mathbb X</script>到H<script type="math/tex" id="MathJax-Element-54">\mathbb H</script>的映射：

<script type="math/tex; mode=display" id="MathJax-Element-55">\phi(x):\mathbb X\rightarrow \mathbb H</script>使得对全部的x,y∈X<script type="math/tex" id="MathJax-Element-56">x,y\in\mathbb X</script>，函数K(x,y)<script type="math/tex" id="MathJax-Element-57">K(x,y)</script>满足条件
<script type="math/tex; mode=display" id="MathJax-Element-58">K(x,y)=<\phi(x),\phi(y)></script>其中<?(x),?(y)><script type="math/tex" id="MathJax-Element-59">当中<\phi(x),\phi(y)></script>表示内积。
核技巧的想法是：
在学习预測中，仅仅定义核函数K(x,y)<script type="math/tex" id="MathJax-Element-60">K(x,y)</script>。而不是显式的定义映射函数?<script type="math/tex" id="MathJax-Element-61">\phi</script>。

通常，直接计算K(x,y)<script type="math/tex" id="MathJax-Element-62">K(x,y)</script>比較easy，而通过?(x)<script type="math/tex" id="MathJax-Element-63">\phi(x)</script>和?(y)<script type="math/tex" id="MathJax-Element-64">\phi(y)</script>计算K(x,y)<script type="math/tex" id="MathJax-Element-65">K(x,y)</script>并不easy。比較经常使用的核函数——高斯核函数：

<script type="math/tex; mode=display" id="MathJax-Element-66">K(x,y)=exp\left( -\frac{\|x-y\|^2}{2\sigma^2}\right)</script>基于核函数的思想，先定义原SVM模型例如以下：
<script type="math/tex; mode=display" id="MathJax-Element-67">\begin{aligned} \displaystyle{\min_{w,b}} \hspace{1cm}&{1\over 2}w^Tw+C\sum_{i=1}^N\xi_i\s.t.\hspace{1cm}&1-y_i(w\cdot \phi(x_i) +b)-\xi_i\leq 0\&-\xi_i\leq0\&i=1,2,...,N \end{aligned}</script>当中?(xi)<script type="math/tex" id="MathJax-Element-68">\phi(x_i)</script>是映射将原输入样本映射到希尔伯特空间的特征。
转化为对偶形式例如以下：；
<script type="math/tex; mode=display" id="MathJax-Element-69">\begin{aligned} \displaystyle \max_{\lambda} \hspace{1cm}&-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_j\phi^T(x_i)\phi(x_j)+\sum_{i=1}^N\lambda_i\s.t. \hspace{1cm}&\sum_{i=1}^N\lambda_iy_i = 0\&0\leq\lambda_i\leq C,\hspace{0.5cm}i=1,2,...,N \end{aligned}</script>终于化为带核函数形式：
<script type="math/tex; mode=display" id="MathJax-Element-70">\begin{aligned} \displaystyle \max_{\lambda} \hspace{1cm}&-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jK(x_i,x_j)+\sum_{i=1}^N\lambda_i\s.t. \hspace{1cm}&\sum_{i=1}^N\lambda_iy_i = 0\&0\leq\lambda_i\leq C,\hspace{0.5cm}i=1,2,...,N \end{aligned}</script>通过观察发现，由原始的输入的内积xTix<script type="math/tex" id="MathJax-Element-71">x_i^Tx</script>，转换到映射空间的内积?T(xi)?(xj)<script type="math/tex" id="MathJax-Element-72">\phi^T(x_i)\phi(x_j)</script>，再转换为核函数形式，整个学习的过程是隐式的在特征空间（希尔伯特空间）进行的吗，而我们得到的显式的结果是用核函数显式的表达，这样的技巧称为核技巧。

其实。仅仅要是学习算法中涉及输入项的内积的函数，都能够用核函数的方法取代内积操作。