西瓜书第六章 -SVM

第一部分：硬间隔
第二部分：软间隔与正则化问题
- Loss函数的设计
- 正则化公式：
  - 对于惩罚数$C$值的讨论：
  - 为什么不用对数损失函数去替代损失函数？
第三部分高斯核函数
第四部分：二分类判别扩展成多分类

SVM算法其实不难主要是思路不好整理。本篇博客的资料来源于西瓜书，邹博，白板书笔记三处。具体的理论背景就不做具体介绍了，直接上公式。

SVM这章的内容主要打算分为三块：

硬间隔
软间隔
Kernel 核方法

第一部分：硬间隔

知识点一：从单边Margin开始讲起：

SVM的目标就是找到一个划分超平面把两类数据划分开来，通过下面这张图可以发现这样的超平面有非常多，但是凭直觉发现粗的那跟线（超平面）划分效果最好。

补充：超平面的公式？？

单边margin的计算：【即，点到直线距离公式】

公式描述：

公式中的直线方程为$Ax+By+C=0$，点$P$的坐标为$(x_0,y_0)$。

\[d=\left|\frac{A x_{0}+B y_{0}+C}{\sqrt{A^{2}+B^{2}}}\right|
\]

根据点到直线的距离，每一类样本中的所有样本点到直线的距离为：

\[margin = r = \frac{\left|w^{T} x_{i}+b\right|}{\|w\|}
\]

将上述最小的值（min）作为单侧的 $margin$

双侧margin的计算

\[margin = 2 \times \min _{w, b, x_{i}} \frac{\left|w^{T} x_{i}+b\right|}{\|w\|}
\]

注1：刚开始学总以为单侧margin可以取到0，实际上这里漏加了一个条件。设置标签$y_i\in\{-1,+1\}$

\[\left\{ \begin{array}{l}
w^Tx_i+b>0\\
w^Tx_i+b<0\\
\end{array} \right. \begin{array}{c}
y_i=+1\\
y_i=-1\\
\end{array}
\]

加入了这个条件后，保证了分类一定正确。
注2：这里的$y$的标签一定为{+1，-1} ？
答：否，y只是一个标签而已，可以为其余值，只需要满足上式的分类准则而已。但是这里取1，确实为了计算方便，见下面如何去掉绝对值的过程，就能体会到y为啥取正负1

去除margin中的绝对值

根据注1可以推导出，条件满足于$y_i(w^Tx_i+b)\ge0$,$y_i$与$(w^Tx_i+b)$同号

\[margin = 2 \times \min _{w, b, x_{i}} \frac{\left|w^{T} x_{i}+b\right|}{\|w\|} = 2 \times \min _{w, b, x_{i}} \frac{y_i(w^Tx_i+b)}{\|w\|}
\]

决策函数：让这个$margin$最大

\[\begin{array}{l}{\max _{w, b} \frac{1}{\|w\|} 2 \times \min _{x_{i}, y_{i}} y_{i}\left(w^{T} x_{i}+b\right)} \\ {\text { s.t. }} \\ {y_{i}\left(w^{T} x_{i}+b\right) > 0, i=1, \ldots, m}\end{array}
\]

关键难点：让单边margin强制为1，则条件也跟着变,条件取等号代表分界线过支持向量

\[y_i(w^Tx_i+b)>0 \Rightarrow \exists \gamma>0 ,\ s.t.\ min\ y_i(w^Tx_i+b)=\gamma
\]

令$\gamma = 1:$

\[s.t.\ min\ y_i(w^Tx_i+b)=\gamma\\
\Rightarrow y_i(w^Tx_i+b) \ge 1,i=1,\dots,N
\]

上述可以这样做的原因：

$y_i$是标签，之前已经讲过了这是一个无意义的值，可大可小
$y_i(w^Tx+b)$没有物理意义，需要除以$\|w\|$才是模
设置为1，首先保证$y_i(w^Tx+b)$一定不为0，即肯定存在margin（类似于高数中的极小值，无论有多小，但是总是存在一个值，这里的$\gamma$也是起的这个作用。）【因为点到直线的绝对距离在每次做SVM中都不一样，有点类似于归一化的味道，归一化点到直线的最小距离为1这个标准。】
$y_i(w^Tx+b)$的取值除了取决于$x,y$还取决于$w$，相当于对$\|w\|$做出了约束。

综上上述条件可以变为：

\[\begin{array}{l}{\max _{w, b} \frac{2}{\|w\|}} \\ {\text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1, \quad i=1,2, \ldots, m}\end{array}
\]

进一步可以简化为：

\[\begin{array}{l}{\min _{w, b} \frac{1}{2}\|w\|^{2}} \\ {\text {s.t.} y_{i}\left(w^{T} x_{i}+b\right) \geq 1, \quad i=1,2, \dots, m}\end{array}
\]

知识点二：对偶问题(dual problem)

凸二次规划问题：

上述的基本目标函数是二次的，约束条件是线性的，这是一个凸二次规划问题
- 当目标函数和约束条件都为变量的线性函数 — 线性规划问题
- 当目标函数为：变量的二次函数 ；当约束条件为：变量的线性函数 — 二次规划问题
- 当目标函数和约束条件都为非线性函数 — 非线性规划问题

不等式条件约束转换为拉格朗日函数：

\[L(w, b, \alpha)=\frac{1}{2}\|w\|^{2}+\sum_{i=1}^{m} \alpha^{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right)\\
s.t. \alpha_i \ge 0
\]

构造出拉格朗日函数之后，与原问题的联系【让上式中右项为0】：

\[f(x)=\frac{1}{2}\|w\|^2=\max_{\alpha} L(w,b,\alpha)
\]

则目标函数则变为：

\[\min_{w,b}\frac{1}{2}\|w\|^2=\min_{w,b}\max_{\alpha}L(w,b,\alpha)
\]

参考文章： https://www.cnblogs.com/ooon/p/5723725.html

根据两个补充知识点一、二（本节最后） 可得对偶条件：

\[\min _{w, b} \max_{\alpha}L(w,b,\alpha) \Leftrightarrow \max_{\alpha}\min _{w, b}L(w,b,\alpha) \\ s.t. \alpha_i \ge 0
\]

⭐插入KKT条件：

列出 Lagrangian 得到无约束优化问题：

\[L(x, \alpha, \beta)=f(x)+\sum_{i=1}^{m} \alpha_{i} h_{i}(x)+\sum_{j=1}^{n} \beta_{i} g_{i}(x)
\]

$KKT$条件：

\[\begin{aligned} \nabla_{x} L(x, \alpha, \beta) &=0 \\ \beta_{j} g_{j}(x) &=0, j=1,2, \ldots, n \\ h_{i}(x) &=0, i=1,2, \ldots, m \\ g_{j}(x) & \leq 0, j=1,2, \ldots, n \\ \beta_{j} & \geq 0, j=1,2, \ldots, n \end{aligned}
\]

介绍KKT条件比较好的博客：https://www.cnblogs.com/ooon/p/5721119.html

根据$KKT$第一个结论可有：

\[\min _{w,b}L\left( w,b,\alpha \right) \ \rightarrow \ \nabla _w/\nabla _bL\left( w,b,\lambda \right) =0
\]

求导后可得：

\[\begin{aligned}
\hat w = & \sum_{i=1}^n \alpha_iy_ix_i\\
0 = & \sum_{i=1}^n \alpha_iy_i
\end{aligned}
\]

将$\hat w$代入拉格朗日条件：

\[\begin{aligned}
L\left( w,b,x \right) = & \frac{1}{2}\lVert w \rVert ^2+\sum_{i=1}^n{\alpha ^i\left( 1-y_i\left( w^Tx_i+b \right) \right)}\\
= & \frac{1}{2}\sum_{i,j=1}^n{\alpha _i}\alpha _jy_iy_jx_{i}^{T}x_j+\sum_{i=1}^n{\alpha ^i-\sum_{i=1}^n{\alpha ^iy_i\left( \sum_{i=1}^n{\alpha _iy_ix_{i}^{T}x_j} \right) -\sum_{i=1}^n{\alpha ^iy_ib}}}\\
=&-\frac{1}{2}\sum_{i,j=1}^n{\alpha _i}\alpha _jy_iy_jx_{i}^{T}x_j+\sum_{i=1}^n{\alpha ^i}
\end{aligned}
\]

求$\hat b$ ：【根据SVM最大间隔分界线可得】

\[y_i(w^Tx_i+b)-1 =0\\
y_iy_i(w^Tx_i+b)-y_i=0\\
\hat b = y_i – w^Tx_i
\]

其实这里省略了很多能内容，为啥子b是在最大间隔分界上求到的b，因为根据KKT的松弛互补条件，可知只有在分界线上拉格朗日乘子$\alpha _i$才有可能大于0，分界线外的样本对建模无意义，所以$\hat{b}$必满足与等式$y_i(w^Tx_i+b)-1 =0$，在正则化那章有过更为详细的分析，见下。

⭕综上整理可得：

第一步：根据$SVM$天生满足极大极小充要于极小极大条件。故第一步先 $\Rightarrow \min_{w,b}$
第二步：求偏导等于0：

\[\begin{aligned}
\hat w ={} & \sum_{i=1}^n \alpha_iy_ix_i\\
\hat b ={} & y_i – w^Tx_i
\end{aligned}
\]

第三步：将$\hat w$可以代入拉格朗日方程可得，对偶问题【dual problem】

\[L\left( w,b,x \right)=-\frac{1}{2}\sum_{i,j=1}^n{\alpha _i}\alpha _jy_iy_jx_{i}^{T}x_j+\sum_{i=1}^n{\alpha ^i} \\
s.t. \sum_{i=1}^n \alpha_iy_i=0,
\alpha_i \ge 0,i=1,2,\dots,n
\]

最后一步：通过$SMO$算法求出 $\alpha_i$【太难看不懂】
最终可求解出模型$f(x)$：

\[\begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}+b \end{aligned}
\]

补充条件

补充1：KKT(互补松弛条件)【slackness complementory】

这是不等式的条件约束问题化为无条件约束问题。

当$(1-y_{i}\left(w^{T} x_{i}+b\right)\le0$时，则$\max_{\alpha}\ \alpha^i(1-y_{i}\left(w^{T} x_{i}+b\right)=0$ $\Rightarrow \min_{w,b}L=\frac{1}{2}\|w\|^2$
当$(1-y_{i}\left(w^{T} x_{i}+b\right)>0$时，则$\max_{\alpha}\ \alpha^i(1-y_{i}\left(w^{T} x_{i}+b\right)\rightarrow+\infty$ $\Rightarrow$再求最小值无意义。

故经过上述分析，可以得若要满足上述，天然满足1这个条件。

补充2：对偶问题【极大极小值互换】

这里若要讲清楚还是比较有困难的。对偶关系分为两类，强对偶关系以及弱对偶关系。

弱对偶关系【简单记忆：鸡头凤尾】

\[min \ max\ L(w,b,\alpha) \ge max \ min \ L(w,b,\alpha)
\]
强对偶关系：若等号存在，则为强对偶。【$SVM$ 天生满足强对偶条件】

故这里极小极大等价于极大极小。

第二部分：软间隔与正则化问题

允许分类存在一点点的错误

Loss函数的设计

把分类错误的个数作为损失函数

\[Loss ={} \sum_{i=1}^N I\{y_i(w^Tx_i+b)<1\}
\]

令$z = y_i(w^Tx_i+b)<1$作为分类正确，则计数为1，损失函数显见为 0-1损失，这是一个非凸的函数，在求解的过程中，存在很多的不足，通常在实际的使用中将0-1损失函数作为一个标准。

然而，$l_{0/1}$非凸、非连续、数学性质不好，不容易直接求解，于是用其余的函数来替代$l_{0/1}$,称为“替代损失”(surrogate loss)。替代损失函数具有较好的额数学性质，通常凸的连续函数且是$l_{0/1}$的上界。西瓜书提供了三种常用的替代损失函数：

$Loss：$hinge损失函数（见上图）

根据距离的远近设置损失函数。

\[\left\{ \begin{array}{l}
y_i(w^Tx_i+b)\ge1\\
y_i(w^Tx_i+b) <1\\
\end{array} \right. \begin{array}{l}
Loss =0\\
Loss =1-y_i(w^Tx_i+b)\\
\end{array}
\]

可以发现上面的公式，就是$hinge$损失嘛!

\[Loss = max \{0,1-y_i(w^Tx_i+b\}
\]

其余两个替代损失函数：
- 指数损失（exponential loss）：$\ell_{e x p}(z)=\exp (-z)$
- 对数损失（logistic loss）：$\ell_{l o g}(z)=\log (1+\exp (-z))$

正则化公式：

若采用的是hinge损失：

\[min \frac{1}{2}w^Tw+C\cdot loss = min \frac{1}{2}w^Tw+ C \cdot \sum_{i=1}^nmax \{0,1-y_i(w^Tx_i+b\}
\]

一般我们不用上述合页损失的公式。

令$\xi_i=1-y_i(w^Tx_i+b)$，故可有$\xi_i\ge 0$

最终可以推出：

\[\Rightarrow min \frac{1}{2}w^Tw+ C\sum_{i=1}^n \xi(i)\\
s.t.y_i(w^Tx_i+b)\ge1-\xi(i),i=1,2,\dots,n \\
s.t.\ \xi_i \ge 0
\]

拉格朗日乘子法：

\[\begin{aligned} L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})=& \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ &+\sum_{i=1}^{m} \alpha_{i}\left(1-\xi_{i}-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)-\sum_{i=1}^{m} \mu_{i} \xi_{i} \end{aligned}
\]

其中,$\alpha_i\ge0,\mu_i\ge0$是拉格朗日乘子。

直接求偏导：

\[\begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \\ C &=\alpha_{i}+\mu_{i} \end{aligned}
\]

得对偶问题(dual problem):

\[\begin{array}{cl}{\max _{\alpha}} & {\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}} \\ {\text { s.t. }} & {\sum_{i=1}^{m} \alpha_{i} y_{i}=0} \\ {} & {0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2, \ldots, m}\end{array}
\]

与硬间隔的区别是对偶变量的约束不同：前者$0 \leqslant \alpha_{i} \leqslant C$，后者是$0 \leqslant \alpha_{i}$

KKT条件：

\[\left\{\begin{array}{l}{C\geqslant\alpha_{i} \geqslant 0, \quad \mu_{i} \geqslant 0} \\ {y_{i} f\left(x_{i}\right)-1+\xi_{i} \geqslant 0} \\ {\alpha_{i}\left(y_{i} f\left(x_{i}\right)-1+\xi_{i}\right)=0} \\ {\xi_{i} \geqslant 0, \mu_{i} \xi_{i}=0}\end{array}\right.
\]

根据之前已经得到的公式：

\[\begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}+b \end{aligned}
\]

模型取决于$w$，进一步取决于$\alpha_i$

可以经过以下四种分析：

当$\alpha_i=0$时，$y_{i} f\left(x_{i}\right)-1+\xi_{i}$可等于零，也可以大于0。说明：边界外的样本权重必为零，即对模型没有影响。
当$\alpha_i>0$时，$y_{i} f\left(x_{i}\right)-1+\xi_{i}$必为零，说明边界上的权重不为零，即模型建模主要却决与支持向量。
当$\alpha_i=C$时，则$\mu_i$必为零【根据公式：$C=\alpha_i+\mu_i$】，则$\xi_i$取值任意。
- $\xi_i>1$：错误分类
- $\xi_i\leqslant1$：样本落在最大间隔的内部。
当$\alpha_i<C$时，$\mu_i$必大于零【根据公式：$C=\alpha_i+\mu_i$】，进一步必有$\xi_i=0$。即样本就在最大分类边界上。

总结对于支持向量的结论：

支持向量$\Rightarrow$ $\xi_i=0,y_{i} f\left(x_{i}\right)-1+\xi_{i}=0 \Rightarrow$ 错误分类为0
很明显的看的出，$C$值越大，$\alpha_i$可取的值越大，即建模的时候越看重支持向量，即越不能分错。

对于惩罚数$C$值的讨论：

C 趋近与无穷大，只需要 min 右边的惩罚项式子（即，新增损失项）就可以让整个式子非常小。【极限：硬分类】
C 趋近与0，相当于无论我怎么犯错，右项都可以很小，那我只要负责左项最小即可，但是注意条件，相当于比起之前，扩展了margin区域，而这种扩展后带来的错误又可以被忽略，也就是强行不管有没有错，我就是要扩展，没人来约束我。【极限：软分类】

现在的问题就是，假设C=0，这种margin扩展，就是在之前的边界上平行远离吗？

相关博客：https://blog.csdn.net/lin_limin/article/details/81135754

为什么不用对数损失函数去替代损失函数？

若使用对率损失函数来替代0/1损失，几乎可以得到对率回归模型（Logisitc回归）

其优点：

1. 输出具有自然概率意义。

2. 可用于处理多分类任务

而SVM的输出不具备概率意义且多分类任务需要推广。对率损失是光滑的单调递减函数，SVM的解要求具有稀疏性，hinge有一块平坦的区域可以满足这个条件。而若需要用对率回归则需要更多的训练样本，开销大【这部分理解的不是很好，但是是西瓜书的内容，就记在这把！】

【我对这句话的理解】：

对hinge损失求导，一定是一个常数。而对sigmoid求导，则是一系列连续值。

\[\nabla _{\xi \left( i \right)}L=C-\alpha _i-\mu _i=0
\]

第三部分高斯核函数

核函数的意义：

将相近的点映射到一个空间，将远的点分到另一个空间

核函数的诀窍在于解决了映射后高维空间中样本距离$\left\|\Phi\left(x_{i}\right)-\Phi\left(x_{j}\right)\right\|$的计算，但又不显式地展示出映射函数$\Phi(\cdot)$。

通常表示为：

\[\kappa\left(x_{1}, x_{2}\right)=<\Phi\left(x_{1}\right), \Phi\left(x_{2}\right)>
\]

从而有：

\[\begin{aligned}\left\|\Phi\left(x_{i}\right)-\Phi\left(x_{j}\right)\right\|^{2} &=<\Phi\left(x_{1}\right)-\Phi\left(x_{2}\right), \Phi\left(x_{1}\right)-\Phi\left(x_{2}\right)>\\ &=<\Phi\left(x_{1}\right), \Phi\left(x_{1}\right)>-2<\Phi\left(x_{1}\right), \Phi\left(x_{2}\right)>+<\Phi\left(x_{2}\right), \Phi\left(x_{2}\right)>\\ &=\kappa\left(x_{1}, x_{1}\right)-2 \kappa\left(x_{1}, x_{2}\right)+\kappa\left(x_{2}, x_{2}\right) \end{aligned}
\]

高斯核函数将原始特征空间映射成了无限维空间

多项式核

取$\kappa(x, z)=<x, z>^{2}$，这里$x=(x_1,x_2)$,$z=(z_1,z_2)^T \in R^2$故有；

\[\begin{aligned} \kappa(x, z) &=<x, z>^{2} \\ &=\left(x_{1} z_{1}+x_{2} z_{2}\right)^{2} \\ &=\left(x_{1} z_{1}\right)^{2}+2 x_{1} x_{2} z_{1} z_{2}+\left(x_{2} z_{2}\right)^{2} \end{aligned}
\]

取$\Phi(x)=\left(x_{1}^{2}, x_{1} x_{2}, x_{2}^{2}\right)$.则有成$\kappa(x, z)=<\Phi(x), \Phi(z)>$成立。也就是说此时映射函数将二维特征空间$\left(\begin{array}{l}{x_{1}} \\ {x_{2}}\end{array}\right)$映射成了三维空间$\left(\begin{array}{l}{x_{1}^{2}} \\ {x_{1} x_{2}} \\ {x_{2}^{2}}\end{array}\right)$ $\Phi: R^{2} \rightarrow R^{3}$。

高斯核

\[\kappa(x, z)=\exp \left(-\frac{\|x-z\|^{2}}{2 \sigma^{2}}\right)
\]

指数泰勒展开：

\[e^{x}=1+\frac{x}{1 !}+\frac{x^{2}}{2 !}+\frac{x^{3}}{3 !}+\ldots=\sum_{n=0}^{\infty} \frac{x^{n}}{n !}
\]

根据泰勒级数，展开高斯核：

\[\begin{aligned} \kappa(x, z) &=\exp \left(-\frac{\|x-z\|^{2}}{2 \sigma^{2}}\right) \\ &=\exp \left[-\frac{1}{2 \sigma^{2}}<x-z, x-z>\right] \\ &=\exp \left[-\frac{1}{2 \sigma^{2}}\left(\|x\|^{2}+\|z\|^{2}-2 x^{T} z\right)\right] \\ &=\exp \left(\gamma\|x\|^{2}\right) * \exp \left(\gamma\|z\|^{2}\right) * \exp \left(-2 \gamma x^{T} z\right), \gamma=-\frac{1}{2 \sigma^{2}} \end{aligned}
\]

其中指数部分根据泰勒展开：

\[\begin{aligned} \exp \left(\gamma\|x\|^{2}\right) &=\sum_{n=0}^{\infty} \frac{\left(\gamma\|x\|^{2}\right)^{n}}{n !} \\ &=\sum_{n=0}^{\infty} \frac{\gamma^{n\left(x_{1}^{2}+x_{2}^{2}+\ldots x_{k}^{2}\right)^{n}}}{n !}, x=\left(x_{1}, x_{2} \cdots x_{k}\right)^{T} \end{aligned}
\]

K 是有限数，指数可以映射为无限维空间。

也就是说，$\exp \left(\gamma\|x\|^{2}\right)$含有了无穷多项的多项式，对应的映射函数$\Phi(\cdot)$将k维空间映射成了无限维空间，即：：$\Phi: R^{k} \rightarrow R^{\infty}$。

$\sigma$的理解

区分：$\gamma$

\[\gamma=-\frac{1}{2 \sigma^{2}}
\]

情况一：（分的太细）

\[\sigma \rightarrow 0,-\frac{\|x-z\|^{2}}{2 \sigma^{2}} \rightarrow-\infty, \kappa(x, z) \rightarrow 0
\]

\[|\Phi(x)-\Phi(z)|^{2}=\kappa(x, x)-2 \kappa(x, z)+\kappa(z, z)=2-2 \kappa(x, z)=2
\]

两个相同的点高斯核为1，不同点的高斯核为0，推出不同的点映射后距离都为2，故不存在聚类，自成一类。

情况二：（完全分不出）

\[\sigma \rightarrow \infty,-\frac{\|x-z\|^{2}}{2 \sigma^{2}} \rightarrow 0, \kappa(x, z) \rightarrow 1
\]

\[|\Phi(x)-\Phi(z)|^{2}=\kappa(x, x)-2 \kappa(x, z)+\kappa(z, z)=2-2 \kappa(x, z)=0
\]

不同点的高斯核为1，推出：不同点映射后得距离都为0，故聚类为一点。

综上： 参数$\sigma$越小，分的类别会越细，也就是说越容易导致过拟合；参数$\sigma$越大，分的类别会越粗，导致无法将数据区分开来。

这部分内容来源于：https://blog.csdn.net/lin_limin/article/details/81135754

第四部分：二分类判别扩展成多分类

SVM多分类的判别是基于二分类的基础上的。

拆分策略：

One vs one : N(N-1)/2 【投票】
One vs Rest: N 【结果比对：一正余负】

说明：当类别N很大，尽管one vs one 需要训练的分类器多，但是每次训练的时候，只需要把两个类别的训练数据取出来生成模型。判断的时候将单个样本的数据输入训练好的分类器进行投票。故反而比OvR速度要快很多。

识别率上面： 要看样本而定，基本差不多。

Many vs Many

缺点：上面两个决策思路，正类总是只是一个分类。而 $MvM$ 的思路上将 $OvR$ 再进行扩展将多个分类视作正类

核心：编码思想引入类别拆分。

注意观察：测试示例与$C_3$进行比较，发现$f2$分类器分类错了，但是最后欧氏距离依然最小。则说明MvM有一丝的容错性。

特点：

码长越长，需要训练的分类器就越多，纠错能力更强。（但太长，就失去意义了因为组合数目是有限的）

我的理解：在上例中，一共只有四个类别。而编码方式只有0000(十进制:10)-1111(十进制:15)种组合，故这里极限是训练16个分类器。
纠错能力好，但是可能导致的问题就是训练的难度比较大。因为不同的划分类别子集的区分性不同。最终的模型性能谁强谁弱没有最后的结果。

本文链接：https://www.cnblogs.com/wangjs-jacky/p/11819458.html