转载请注明出处:http://blog.csdn.net/luoshixian099/article/details/51073885

<script type="math/tex; mode=display" id="MathJax-Element-36">\color{Blue}{CSDN-勿在浮沙筑高台}</script>
支持向量机(Support Vector Machine)以前在分类、回归问题中非常流行。支持向量机也称为最大间隔分类器，通过分离超平面把原始样本集划分成两部分。

首先考虑最简单的情况：线性可分支持向量机。即存在一个超平面能够把训练样本分开。

1.线性可分支持向量机

1.考虑一个线性二分类的问题；例如以下左图，在二维平面上有两种样本点x，目标值分别标记为{-1,1}。能够作出无数条直线wTx+b=0<script type="math/tex" id="MathJax-Element-175">w^Tx+b=0</script>,直线上方的点标记为{+1}的带入直线公式会得到wTx+b>0<script type="math/tex" id="MathJax-Element-176">w^Tx+b>0</script>,下方的点。标记为{-1}带入直线公式会得到wTx+b<0<script type="math/tex" id="MathJax-Element-177">w^Tx+b<0</script>，因此能够用wTx+b<script type="math/tex" id="MathJax-Element-178">w^Tx+b</script>的符号决定点的分类，写成决策函数为f(x,w,b)=sign(wTx+b)<script type="math/tex" id="MathJax-Element-179">f(x,w,b)=sign(w^Tx+b)</script>把两类点分开。可是个採用哪个直线最好呢？
2.一般来说，当样本点离直线越远。则分类正确的确信度越大；例如以下右图所看到的，A,B,C三个样本点都被预測分类到‘×’类中。可是对于A的分类正确的确信度比C大。因为点C里分类直线wTx+b=0<script type="math/tex" id="MathJax-Element-180">w^Tx+b=0</script>非常近，当直线的斜率稍一点变化，即会导致C被分到还有一类中。
综上。我们想要得到的直线是离样本点最远。同时又能保证正确划分的直线<script type="math/tex" id="MathJax-Element-181">\color{red}{综上，我们想要得到的直线是离样本点最远，同一时候又能保证正确划分的直线}</script>。

1.1函数间隔与几何间隔

由二维直线wTx+b=0<script type="math/tex" id="MathJax-Element-44">w^Tx+b=0</script>扩展到高维被称为超平面(w,b)<script type="math/tex" id="MathJax-Element-45">(w,b)</script>。

一个点距离超平面的远近能够表示分类预測的确信程度。在超平面wTx+b=0<script type="math/tex" id="MathJax-Element-46">w^Tx+b=0</script>确定的情况下，|wTx+b|<script type="math/tex" id="MathJax-Element-47">|w^Tx+b|</script>能够相对地表示点x距离超平面的远近。并且假设分类正确。则y(i)<script type="math/tex" id="MathJax-Element-48">y^{(i)}</script>与wTx(i)+b<script type="math/tex" id="MathJax-Element-49">w^Tx^{(i)}+b</script>的符号一致,即y(i)(wTx(i)+b)>0<script type="math/tex" id="MathJax-Element-50">y^{(i)}(w^Tx^{(i)}+b)>0</script>，同一时候表示分类的正确性以及确信度。
函数间隔：超平面(w,b)<script type="math/tex" id="MathJax-Element-51">(w,b)</script>关于样本点(x(i),y(i))<script type="math/tex" id="MathJax-Element-52">(x^{(i)},y^{(i)})</script>的函数间隔为

<script type="math/tex; mode=display" id="MathJax-Element-53">\color{Green}{函数间隔:}\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)</script>
定义超平面关于样本集S的函数间隔为超平面(w,b)与S中全部样本点的函数间隔的最小值
<script type="math/tex; mode=display" id="MathJax-Element-54">\hat{\gamma}=min_{i=1,2,...m}\ \hat{\gamma}^{(i)}</script>
定义γ^<script type="math/tex" id="MathJax-Element-55">\hat{\gamma}</script>是为了最大化间隔，γ^<script type="math/tex" id="MathJax-Element-56">\hat{\gamma}</script>表示关于超平面与训练集中样本的函数间隔最小值，以下仅仅要最大化γ^<script type="math/tex" id="MathJax-Element-57">\hat{\gamma}</script>就可以。
注意到函数间隔实际上并不能表示点到超平面的距离，因为当超平面(w,b)<script type="math/tex" id="MathJax-Element-58">(w,b)</script>參数扩大同样的倍数后，如(2w,2b)<script type="math/tex" id="MathJax-Element-59">(2w,2b)</script>，超平面的位置并没有改变，可是函数间隔也变大了同样的倍数2γ^(i)<script type="math/tex" id="MathJax-Element-60">2\hat{\gamma}^{(i)}</script>.
几何间隔：

如上图所看到的：设样本点A坐标为x(i)<script type="math/tex" id="MathJax-Element-61">x^{(i)}</script>,点A到超平面的垂直距离记为γ(i)<script type="math/tex" id="MathJax-Element-62">\gamma^{(i)}</script>,分离超平面wTx(i)+b=0<script type="math/tex" id="MathJax-Element-63">w^Tx^{(i)}+b=0</script>的单位法向量为w||w||<script type="math/tex" id="MathJax-Element-64">\frac{w}{||w||}</script>,因此点B的坐标为x(i)?γ(i)w||w||<script type="math/tex" id="MathJax-Element-65">x^{(i)}-\gamma^{(i)}\frac{w}{||w||}</script>，且点B在直线上，带入直线公式有：
<script type="math/tex; mode=display" id="MathJax-Element-66">w^T(x^{(i)}-\gamma^{(i)}\frac{w}{||w||})+b=0。解得:\gamma^{(i)}=\frac{(w^Tx^{(i)}+b)}{||w||}</script>
假设点被正确分类。y(i)<script type="math/tex" id="MathJax-Element-67">y^{(i)}</script>与(wTx(i)+b)||w||<script type="math/tex" id="MathJax-Element-68">\frac{(w^Tx^{(i)}+b)}{||w||}</script>的符号一致，由此
<script type="math/tex; mode=display" id="MathJax-Element-69">同理定义 \color{Green}{几何间隔}:\gamma^{(i)}=y^{(i)}\left(\frac{w^Tx^{(i)}+b}{||w||}\right)</script>
<script type="math/tex; mode=display" id="MathJax-Element-70">超平面与样本集S的几何间隔为\gamma=min_{i=1,2,...m}\ \gamma^{(i)}</script>
几何间隔不随着超平面參数的变化而变化，比如超平面參数(w,b)变为(2w,2b)。函数间隔γ^(i)<script type="math/tex" id="MathJax-Element-71">\hat{\gamma}^{(i)}</script>变为2γ^(i)<script type="math/tex" id="MathJax-Element-72">2 \hat{\gamma}^{(i)}</script>,而几何间隔γ(i)<script type="math/tex" id="MathJax-Element-73">\gamma^{(i)}</script>保持不变。
函数间隔与几何间隔的关系：γ(i)=γ^(i)||w||<script type="math/tex" id="MathJax-Element-74">\gamma^{(i)}=\frac{\hat\gamma^{(i)}}{||w||}</script>；γ=γ^||w||<script type="math/tex" id="MathJax-Element-75">\gamma=\frac{\hat\gamma}{||w||}</script>，若||w||=1,函数间隔与几何间隔同样。

1.2间隔最大化

如上所述。支持向量机的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。γ<script type="math/tex" id="MathJax-Element-76">\gamma</script>表示分离超平面与训练集中样本的几何间隔的最小值。为了间隔最大化。仅仅须要最大化γ<script type="math/tex" id="MathJax-Element-77">\gamma</script>，同一时候全部样本的几何间隔必须满足γ(i)≥γ,i=1,2,...,m<script type="math/tex" id="MathJax-Element-78">\gamma^{(i)}\geq\gamma,i=1,2,...,m</script>;

<script type="math/tex; mode=display" id="MathJax-Element-79">max_{w,b}\ \gamma</script>
<script type="math/tex; mode=display" id="MathJax-Element-80">s.t.\ y^{(i)}\left(\frac{w^Tx^{(i)}+b}{||w||}\right)\geq\gamma</script>
上述问题，能够转变为一个凸二次规划问题。这是支持向量机的一个重要属性，局部极值即为全局最值。
考虑函数间隔与几何间隔的关系：

上述优化问题中，当超平面參数(w,b)同一时候变为(2w,2b)，函数间隔也会变为2γ^<script type="math/tex" id="MathJax-Element-81">2\hat{\gamma}</script>,目标函数的解并不会变化。即γ^<script type="math/tex" id="MathJax-Element-82">\hat{\gamma}</script>的取值不影响优化问题的解。因此令γ^=1<script type="math/tex" id="MathJax-Element-83">\hat{\gamma}=1</script>。目标函数变为最大化1||w||<script type="math/tex" id="MathJax-Element-84">\frac{1}{||w||}</script>，即最小化||w||2<script type="math/tex" id="MathJax-Element-85">||w||^2</script>。为了后面的求解方便，加入因子12<script type="math/tex" id="MathJax-Element-86">\frac12</script>也不影响目标函数的解；

上述问题为一个凸优化问题，通过某些优化算法能够求解。

以下继续介绍拉格朗日对偶算法，能够更进一步优化上述问题，同一时候自然引入核函数，推广到高维数据。

1.3拉格朗日对偶性

有时考虑解决原始问题的对偶问题会更高效。

原始问题
f(w),gi(w),hi(w)<script type="math/tex" id="MathJax-Element-87">f(w),g_i(w),h_i(w)</script>均为连续可微：

写出拉格朗日函数。当中αi≥0,β≥0<script type="math/tex" id="MathJax-Element-88">\alpha_i\geq0,\beta\geq0</script>称为拉格朗日乘子：

定义关于w<script type="math/tex" id="MathJax-Element-89">w</script>的函数θP(w)=maxα,βL(w,α,β)<script type="math/tex" id="MathJax-Element-90">\theta_P(w)=max_{\alpha,\beta}L(w,\alpha,\beta)</script>;能够证明假设w<script type="math/tex" id="MathJax-Element-91">w</script>满足上述约束条件gi(w)≤0,hi(w)=0<script type="math/tex" id="MathJax-Element-92">g_i(w)\leq0,h_i(w)=0</script>，则有θP(w)=f(w)<script type="math/tex" id="MathJax-Element-93">\theta_P(w)=f(w)</script>

由此原始问题的约束最优化问题变为极小极大问题：

设原始问题的最优解记为p?=minwf(w)=minwθp(w)<script type="math/tex" id="MathJax-Element-94">p^*=min_wf(w)=min_w\theta_p(w)</script>.
对偶问题
把上述极小极大问题minw maxα,βL(w,α,β)<script type="math/tex" id="MathJax-Element-95">min_w\ max_{\alpha,\beta}L(w,\alpha,\beta)</script>,改为极大极小变为对偶问题，即：
定义：

设此极大极小问题的最优解记为d?<script type="math/tex" id="MathJax-Element-96">d^*</script>,能够证明

为了使得对偶问题与原始问题的最优解相等d?=p?<script type="math/tex" id="MathJax-Element-97">d^*=p^*</script>，必须满足下述几个条件。称为KKT条件

1.4最优间隔分类器

回想原始问题：

写成拉格朗日函数。因为仅仅有不等式约束所以仅仅包括拉格朗日乘子αi<script type="math/tex" id="MathJax-Element-98">\alpha_i</script>：

原始问题最优解p?=minw,b maxαL(w,b,α)<script type="math/tex" id="MathJax-Element-99">p^*=min_{w,b}\ max_\alpha L(w,b,\alpha)</script>;对偶问题的最优解d?=maxα minw,bL(w,b,α)<script type="math/tex" id="MathJax-Element-100">d^*=max_\alpha\ min_{w,b}L(w,b,\alpha)</script>
对偶问题先求关于參数w,b的最小值，再求关于參数α<script type="math/tex" id="MathJax-Element-101">\alpha</script>的最大值。

首先，分别对w,b求偏导数并令为0。得：


把上述结果带入拉格朗日函数L(w,b,α)<script type="math/tex" id="MathJax-Element-102">L(w,b,\alpha)</script>

注意到上述是仅仅关于參数α<script type="math/tex" id="MathJax-Element-103">\alpha</script>的函数，记为W(α)<script type="math/tex" id="MathJax-Element-104">W(\alpha)</script>,由对偶函数。下一步即最大化W(α)<script type="math/tex" id="MathJax-Element-105">W(\alpha)</script>

以下的目的是解决上述优化问题。通常採用SMO算法，本篇文章暂不做介绍。假如已经得到最优解α=(α1,α2,...,αm)<script type="math/tex" id="MathJax-Element-106">\alpha=(\alpha_1,\alpha_2,...,\alpha_m)</script>,带回到上面对w求偏导得到的公式，能够得到w<script type="math/tex" id="MathJax-Element-107">w</script>的值。以下要求得b得值，考虑KKT条件有：αi[y(i)(wTx(i)+b)?1]=0。i=1,2..m<script type="math/tex" id="MathJax-Element-108">\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]=0，i=1,2..m</script>,当中必定存在一个αj≠0<script type="math/tex" id="MathJax-Element-109">\alpha_j\neq0</script>,（否则w=0<script type="math/tex" id="MathJax-Element-110">w=0</script>,不是原始解）。

当αj≠0<script type="math/tex" id="MathJax-Element-111">\alpha_j\neq0</script>时y(i)(wTx(i)+b)=1<script type="math/tex" id="MathJax-Element-112">y^{(i)}(w^Tx^{(i)}+b)=1</script>,能够解出b<script type="math/tex" id="MathJax-Element-113">b</script>的代数式。b=y(j)?∑mi=1αiy(i)(x(i),x(j))<script type="math/tex" id="MathJax-Element-114">b=y^{(j)}-\sum_{i=1}^{m}\alpha_iy^{(i)}(x^{(i)},x^{(j)})</script>，也能够对全部採用满足条件的b<script type="math/tex" id="MathJax-Element-115">b</script>加和求平均；然后就可以得到最佳分类超平面：

依据KKT条件有αi[y(i)(wTx(i)+b)?1]=0，i=1,2..m<script type="math/tex" id="MathJax-Element-116">\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]=0，i=1,2..m</script>，当αi>0<script type="math/tex" id="MathJax-Element-117">\alpha_i>0</script>时,必定有y(i)(wTx(i)+b)=1<script type="math/tex" id="MathJax-Element-118">y^{(i)}(w^Tx^{(i)}+b)=1</script>，即该样本点的函数间隔为1。例如以下图所看到的，落在直线wTx+b=±1<script type="math/tex" id="MathJax-Element-119">w^Tx+b=\pm1</script>上。此向量即称为支持向量。对于落在直线wTx+b=±1<script type="math/tex" id="MathJax-Element-120">w^Tx+b=\pm1</script>以内的点，函数间隔y(j)(wTx(j)+b)>1<script type="math/tex" id="MathJax-Element-121">y^{(j)}(w^Tx^{(j)}+b)>1</script>,必定有αj=0<script type="math/tex" id="MathJax-Element-122">\alpha_j=0</script>，当计算函数最优切割超平面參数w,b时。这些点相应的αj=0<script type="math/tex" id="MathJax-Element-123">\alpha_j=0</script>。所以对參数没有影响。仅仅有支持向量，即落在wTx+b=±1<script type="math/tex" id="MathJax-Element-124">w^Tx+b=\pm1</script>上数据影响着最优超平面的计算。

2.线性支持向量机

以上讨论的内容是建立在数据是线性可分的情况。即存在一个分离超平面能够把训练数据分为两部分。实际上数据并不会这么理想，例如以下图所看到的。即存在某些样本点不能满足函数间隔大于等于1这个条件。

这时能够为每一个数据点设置一个松弛因子ξi≥0<script type="math/tex" id="MathJax-Element-125">\xi_i\geq0</script>,使得函数间隔γi<script type="math/tex" id="MathJax-Element-126">\gamma_i</script>加上松弛因子ξi<script type="math/tex" id="MathJax-Element-127">\xi_i</script>大于等于1.即y(i)(wTx(i)+w0)≥1?ξi<script type="math/tex" id="MathJax-Element-128">y^{(i)}(w^Tx^{(i)}+w_0)\geq1-\xi_i</script>,同一时候对每一个松弛因子ξi<script type="math/tex" id="MathJax-Element-129">\xi_i</script>支付一个代价ξi<script type="math/tex" id="MathJax-Element-130">\xi_i</script>。由此原始问题变为：

C称为惩处參数(C>0)。C值越大对误分类的惩处越大。因为当C为无穷大时，即成为了线性可分问题。
採用与线性可分同样的过程。建立拉格朗日函数：

由对偶函数得。首先分别对w,b,ξi<script type="math/tex" id="MathJax-Element-131">w,b,\xi_i</script>求偏倒数，并令为0，能够得到上面右式，带回到拉格朗日函数中，因为μi≥0<script type="math/tex" id="MathJax-Element-132">\mu_i\geq0</script>,且αi=C?μi<script type="math/tex" id="MathJax-Element-133">\alpha_i=C-\mu_i</script>,所以有：

由上述KKT条件能够得到：

3.非线性支持向量机

3.1 概念

如上图所看到的，原始样本数据线性不可分，即无法用一条直线或分离超平面将两类分开。

可是对原始数据採用非线性变换?(x)<script type="math/tex" id="MathJax-Element-134">\phi(x)</script>，非线性变换将原始数据从低维映射到高维，高维上数据就可能变得线性可分。

步骤：首先使用非线性变换将原始数据集映射到新空间中。称为特征空间，在特征空间中数据将变的线性可分，然后採用线性支持向量机的方法训练分离超平面參数。

但在高维上计算量会急剧增大。会造成维数灾难，自然引入核技巧(kernal trick)。

3.2 核技巧

观察线性支持向量机的对偶问题为：

上述目标函数中。仅仅包括原始数据的内积形式<x(i),x(j)>=(x(i))T(x(j))<script type="math/tex" id="MathJax-Element-135">=(x^{(i)})^T(x^{(j)})</script>。

由上述分析，仅仅须要找到一个合适的非线性变换?(x)<script type="math/tex" id="MathJax-Element-136">\phi(x)</script>，将原始数据x(i)<script type="math/tex" id="MathJax-Element-137">x^{(i)}</script>映射到高维特征空间?(x(i))<script type="math/tex" id="MathJax-Element-138">\phi(x^{(i)})</script>中。内积形式变为为<?(x(i)),?(x(j))><script type="math/tex" id="MathJax-Element-139"><\phi(x^{(i)}),\phi (x^{(j)})></script>。
定义核函数K(x,z)=?(x)T?(z)<script type="math/tex" id="MathJax-Element-140">K(x,z)=\phi(x)^T\phi(z)</script>。表示两个原始数据x,z<script type="math/tex" id="MathJax-Element-141">x,z</script>分别变换到特征空间中的内积值。

核技巧的方法即不用构造非线性映射?(x)<script type="math/tex" id="MathJax-Element-142">\phi(x)</script>而直接给定一个核函数K(x,z)<script type="math/tex" id="MathJax-Element-143">K(x,z)</script>,降低了计算量。如以下样例一个核函数等于两个非线性变换的内积：

<script type="math/tex; mode=display" id="MathJax-Element-144">Eg:x,z\in R^n ,\ K(x,z)=(x^Tz)^2=\sum_{i,j=1}^n(x_ix_j)(z_iz_j),相应\phi(x)=(x_1x_1,x_1x_2...,x_1x_n,x_2x_1,...x_nx_n)^T</script>
经常使用几个核函数：
<script type="math/tex; mode=display" id="MathJax-Element-145">多项式核函数：K(x,z)=(x^Tz+1)^q,q>0</script>
<script type="math/tex; mode=display" id="MathJax-Element-146">高斯核函数：K(x,z)=exp\left(-\frac{||x-z||^2}{2\sigma^2}\right),称为高斯径向基函数分类器，即上面图中採用方法</script>
<script type="math/tex; mode=display" id="MathJax-Element-147">双曲正切函数：K(x,z)=tanh(\beta x^Tz+\gamma)。为满足Mercer定理。一组可能的參数\beta=2,\gamma=1</script>

4.SVM后验概率输出

SVM分类器中判决函数y^=sign(f(x))=sign(wTx+b)<script type="math/tex" id="MathJax-Element-148">\hat{y}=sign(f(x))=sign(w^Tx+b)</script>。能够採用f(x)与sigmoid函数结合。把f(x)=wTx+b<script type="math/tex" id="MathJax-Element-149">f(x)=w^Tx+b</script>解释成y=1<script type="math/tex" id="MathJax-Element-150">y=1</script>的对数几率,SVM分类器概率输出(Platt 2000)：

<script type="math/tex; mode=display" id="MathJax-Element-151">p(\hat{y}=1|x)=\sigma(Af(x)+B)</script>
參数A,B通过最大释然的方法求解，为防止过拟合。求解A,B參数的样本数据应独立于训练分类的样本。因为在训练分类器阶段，没有考虑后验概率的问题，因此SVM后验概率结果不可靠。

5.几种损失函数的比較

如图：0-1损失是二分类问题的真正损失函数，合页损失与logistic损失是对0-1的损失函数的近似。最小二乘损失强化了分类点在正确分类边界处。

5.1合页损失函数

对于线性支持向量机。目标函数是最小化12||w||2+C∑mi=1ξi<script type="math/tex" id="MathJax-Element-152">\frac12||w||^2+C \sum_{i=1}^m\xi_i</script>,当中ξi<script type="math/tex" id="MathJax-Element-153">\xi_i</script>为每一个样本支付的代价；能够定义ξi=[1?y(i)(wTx(i)+b)]+<script type="math/tex" id="MathJax-Element-154">\xi_i=[1-y^{(i)}(w^Tx^{(i)}+b)]_+</script>；下标’+’表示取正值函数。假设z>0,[z]+=z;否则[z]+=0<script type="math/tex" id="MathJax-Element-155">z>0,[z]_+=z;否则[z]_+=0</script>，因此目标函数能够定义为：

<script type="math/tex; mode=display" id="MathJax-Element-156">min_{w,b}\ \sum_{i=1}^{m}[1-y^{(i)}(w^Tx^{(i)}+b)]_++\lambda||w||^2</script>
第一项关于被称为经验损失，定义z=y(i)(wTx(i)+b)<script type="math/tex" id="MathJax-Element-157">z=y^{(i)}(w^Tx^{(i)}+b)</script>;损失函数为E(z)=[1?z]+<script type="math/tex" id="MathJax-Element-158">E(z)=[1-z]_+</script>。如上图所看到的，因为图形像一个合页，被称为合页损失。
<script type="math/tex; mode=display" id="MathJax-Element-159">上述目标函数中。当\lambda=\frac1{2C}时。等价于原目标函数\frac12||w||^2+C \sum_{i=1}^m\xi_i</script>

5.2logistic回归损失

为了方便叙述，改变一下标记方法。记原始样本数据为(xi,ti)。t∈[1,?1]<script type="math/tex" id="MathJax-Element-160">(x_i,t_i)。t\in [1,-1]</script>,模型预測值为y(xi)=wTxi+b<script type="math/tex" id="MathJax-Element-161">y(x_i)=w^Tx_i+b</script>。结合sigmoid函数。能够把y(xi)<script type="math/tex" id="MathJax-Element-162">y(x_i)</script>带入sigmoid函数中，后验概率输出。

即p(t=1|y)=σ(y)<script type="math/tex" id="MathJax-Element-163">p(t=1|y)=\sigma(y)</script>,则p(t=?1|y)=1?σ(y)=σ(?y)<script type="math/tex" id="MathJax-Element-164">p(t=-1|y)=1-\sigma(y)=\sigma(-y)</script>。综上两种情况p(t|y)=σ(ty)<script type="math/tex" id="MathJax-Element-165">p(t|y)=\sigma(ty)</script>。

採用最大似然函数：

目标函数能够定义为对数似然的负数。同一时候加上一个二次正则化因子。

<script type="math/tex; mode=display" id="MathJax-Element-166">\sum_{i=1}^{m}ln[1+exp(-y_it_i)]+\lambda||w||^2</script>
第一项即为logistic回归损失函数ELR(yt)=ln[1+exp(?yt)]<script type="math/tex" id="MathJax-Element-167">E_{LR}(yt)=ln[1+exp(-yt)]</script>

5.3最小二乘损失

与线下回归相似，能够採用最小二乘损失作为目标函数：

<script type="math/tex; mode=display" id="MathJax-Element-168">\sum_{i=1}^{m}(y_i-t_i)^2+\lambda||w||^2</script>

6.SVM多分类问题

1.one-versus-the-rest

对于K个类别的问题。在训练样本上，採用SVM训练出K个分类器。每一个分类器将训练样本分成Ki<script type="math/tex" id="MathJax-Element-169">K_i</script>类与非Ki<script type="math/tex" id="MathJax-Element-170">K_i</script>类，然后採用SVM训练出模型。如上图所看到的，每一个分类器仅仅能回答是否属于Ki<script type="math/tex" id="MathJax-Element-171">K_i</script>的答案。此种方法会造成一个样本数据属于多个类别的情况，上左图阴影部分。

也能够採用：y(x)=maxk yk(x)<script type="math/tex" id="MathJax-Element-172">y(x)=max_k\ y_k(x)</script>，即採用最大的函数间隔的那个类别。但不同的分类器有可能尺度不同样，函数距离自然不能作为推断标准。

同一时候，训练样本的不平衡也可能造成分类器有误差。

2.one-versus-one

在K分类的情况下，训练出K(K?1)2<script type="math/tex" id="MathJax-Element-173">\frac{K(K-1)}{2}</script>个分类器，即每两个类别训练出一个分类器，然后依据K(K?1)2<script type="math/tex" id="MathJax-Element-174">\frac{K(K-1)}{2}</script>个分类器的结果，採用投票方法给出预測结果。
此种方法依旧造成部分数据不属于不论什么类的问题，上右图阴影部分所看到的。

3.其它方法

1.一次训练K分类的SVM。

參数多。复杂度高；(Weston and Watkins 1999)
2.DAGSVM ;(Platt 2000)

參考：
1. PRML
2. MLAPP
3. CS 229-Andrew Ng