前言

书上的题目相对简单，没有要求相对位置不改变，而在牛客网上的题目有要求。以牛客网的为准。

题目(调整数组顺序使奇数位于偶数前面)

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

算法思路

算法思路一

利用冒泡排序的思想，此时我们比较的是只要遇到奇数和偶数，那么就交换元素。

算法思路二

借助辅助数组。我们从前往后扫描数组将奇数放入数组中，再扫描一遍将偶数放入数组中，最后对数组赋值辅助数组。

算法思路三

利用双向队列的特性，即可以高效的在头尾两段插入和删除元素，我们可以从后往前扫描数组，将奇数依次往前插到队列，然后从后往前扫描数组，将偶数往后插入队列中，在保证顺序不变的同时得到所求。

算法实现

算法实现一

算法实现二

算法实现三

复杂度分析

算法一中，使用的过程类似冒泡排序，时间复杂度为 O(n^2)，空间复杂度为 O(1)；算法二中，对数组只有遍历，所以时间复杂度为 O(n)，另外使用了辅助数组，所以空间复杂度为 O(n)；算法三也是遍历一遍数组，时间复杂度为 O(n)，另外使用了双端队列，空间复杂度为 O(n)。

参考

<<剑指offer2>>

前言

在前一篇文章中介绍的 SVM 基本型，其实还可以进行优化。主要是利用核函数对向量内积的计算进行优化。另外，我们还将详细分析拉格朗日乘子法与KKT条件,以及KKT条件对SVM分类的作用。那我们先来看看核函数是什么。

核函数

在异或问题中，由于 \(0\oplus 0=0\)、\(1\oplus 1=0\)、\(0\oplus 1=1\)、\(1\oplus 0=1\)，所有只有两类结果，我们将 0 标记为负号，将 1 标记为正号，并且将这四种情况形象地标注在下图左侧中。可以看到，对于这类样本点，我们无法找到线性可分的超平面，而只能绘制一条非线性曲线将他们划分开。那么有什么办法可以将他们划分开呢？这时候，核方法(kernel trick)就出场啦。

所谓的核方法，其实就是将样本从原始的特征空间映射到一个高维的特征空间，以使得样本在高维特征空间中仍然线性可分。正如下图中所示，我们对 \(x\) 使用一个映射函数 \(\phi\)，得到映射到高维特征空间的特征向量 \(\phi \left( x\right) \)，然后这些样本点在三维空间的确可以找到一个平面将样本点线性可分(黑色实线所画的平面)。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。那么其实我们只要找到映射函数，就可以将线性不可分的样本转为线性可分的情况了。但是，这个映射函数很难寻找，SVM 模型没有直接硬来，而是巧妙的引入核函数来间接地解决实现这种变换。

那么接下来我们看看核函数如何应用于模型上。

在前一篇文章中的 SVM 对偶问题为:

$$\max _{\alpha }\sum ^{m}_{i=1}\alpha _{i}-\dfrac {1}{2}\sum ^{m}_{i=1}\sum ^{m}_{j=1}\alpha _{i}\alpha _{j}y_{i}y_{j} x_{i}^{T}x_{j}\quad \alpha _{i}\geq 0$$

可以看到，我们需要计算第 i 和第 j 两个样本的内积。
另外，对应的分类决策函数的公式为：

$$\begin{aligned}f\left( x\right) =w^{T}x+b\\ =\sum ^{m}_{i=1}\alpha _{i}y_{i}x_{i}^{T}x+b\end{aligned}$$

我们也需要计算总样本 X 和样本 i 之间的内积。我们发现，这里其实存在着重复的内积计算，并且在高维中内积计算非常耗时，可不可以只算一次？事实上，是可以的，我们完全可以提前将两两样本间以及样本与自身的内积都算出来并存储下来，下次使用时只需直接取出使用即可，这大大提高了计算效率。但是，现在问题是当样本点映射到高维空间中内积计算的问题。这里，就巧妙引入了核函数,替代了向量内积。它可表示为:

$$k\left( x_{i},x_{j}\right) =\phi \left( x_{i}\right) ^{T}\phi \left( x_{j}\right)$$

那么引入核函数后，对偶问题变为:

$$\max _{\alpha }\sum ^{m}_{i=1}\alpha _{i}-\dfrac {1}{2}\sum ^{m}_{i=1}\sum ^{m}_{j=1}\alpha _{i}\alpha _{j}y_{i}y_{j}\phi \left( x_{i}\right)^{T}\phi \left( x_{j}\right)=\max _{\alpha }\sum ^{m}_{i=1}\alpha _{i}-\dfrac {1}{2}\sum ^{m}_{i=1}\sum ^{m}_{j=1}\alpha _{i}\alpha _{j}y_{i}y_{j}k\left( x_{i},x_{j}\right)\quad \alpha _{i}\geq 0$$

分类决策函数变为:

$$\begin{aligned}f\left( x\right) =w^{T}x+b\\ =\sum ^{m}_{i=1}\alpha _{i}y_{i}\phi \left( x_{i}\right)^{T}\phi \left( x_{j}\right)+b\end{aligned}=\sum ^{m}_{i=i}\alpha _{i}y_{i}k\left( x,x_{i}\right)+b$$

所以我们只需要计算核函数的值即可，而核函数的计算只需套用公式。常用的核函数有线性核(\(k\left( x_{i},x_{j}\right) =x_{i}^{T}x_{j}\))以及高斯核(\(k\left( x_{i},x_{j}\right) =\exp \left( -\dfrac {\left| x_{i}-x_{j}\right| ^{2}}{2\sigma ^{2}}\right) \))

注意到大部分的拉格朗日乘子 \(\alpha_{i}\) 都是0。因为大部分的样本都会被分类正确，只有少部分的样本被误分类，也就说只要被分类正确，\(\alpha_{i}=0\)，该样本不会出现在分类决策函数的求和公式中，自然不会对最终的决策结果产生任何影响。

最后，支持向量机的决策过程也可以看做一种相似性比较的过程。首先，输入样本与一系列模板样本进行相似性比较，模板样本就是训练过程决定的支持向量，而采用的相似性度量就是核函数。样本与各支持向量比较后的得分进行加权后求和，权值就是训练时得到的各支持向量的系数 \(\alpha_{i}\) 和类别标号的成绩。最后根据加权求和值大小来进行决策。而采用不同的核函数，就相当于采用不同的相似度的衡量方法。

到这里，SVM 的理论基础基本都介绍完了。总的来说，首先进行特征空间的非线性映射，然后在这个新的空间中求最优分类面即最大间隔分类面，而这种非线性映射是通过定义适当的内积核函数来巧妙实现的。

接下来，我们介绍下凸优化问题中涉及的KKT条件。

KKT 条件（Karush–Kuhn–Tucker conditions）

什么是 KKT

KKT 是一组不等式约束，主要应用在凸优化问题上。其实大家在高数中曾使用过拉格朗日乘子法求解带等式约束的优化问题，而KKT条件解优化问题就是升级版啦。

拉格朗日乘子法

假设有如下带等式约束的优化问题：

$$\min f\left( x\right) \quad s.t.h_{i}\left( x\right) =0\quad i=1,2,\ldots ,m$$

我们使用拉格朗日乘子法通过引入拉格朗日乘子将等式约束的优化问题转化为无等式约束的优化问题。
所以我们通过一个拉格朗日乘子组成的行向量 \(\alpha\)(其中 \(\alpha=\left[ \alpha _{1},\alpha_{2},\ldots ,\alpha_{n}\right] \))，将目标函数和等式约束组合成 \(L\left( \alpha ,x\right) =f\left( x\right) +\alpha^{T} \cdot h\),其中\(h\left( x\right) =\left[ h_{1}\left( x\right),h_{2}\left( x\right),\ldots ,h_{m}\left( x\right)\right] ^{T}\)。然后就可以求最优值，也就是利用费马引理，将函数 L 对各个参数求导取零，然后等式联立进行求解。

KKT条件

假设有如下带不等式约束的优化问题:

$$\min f\left( x\right) \quad s.t.g_{i}\left( x\right) \leq0\quad i=1,2,\ldots ,n\quad h_{j}\left( x\right)=0\quad j=1,2,\ldots ,m$$

我们同样先将约束问题转化为无约束的优化问题，得到函数:

$$L\left( \alpha ,\beta ,x\right) =f\left( x\right) +\alpha g\left( x\right) +\beta h\left( x\right)$$

其中\(\alpha\)、\(\beta\)为行向量，\(g\left( x\right)\)、\(h\left( x\right)\)均为列向量。那么 KKT 条件的作用就是，该问题的最优解必须满足以下条件:

1. \(L\left( \alpha ,\beta ,x\right)\) 对 \(x\) 的导数为零；
2. \(h\left(x\right)=0\)；
3. \(\alpha g\left( x\right)\leq 0\)。

这样之后就能求得最优值。其中第三个式子比较有意思。由于 \(g\left(x\right) \leq0\)，因此只有 \(\alpha=0\) 或 \(g\left(x\right)=0\) 时，等式才成立。而这里是 SVM 中很多重要性质的来源，比如支持向量的概念。后面我们在介绍KKT条件与 SVM 的关系时再具体解释。那为什么拉格朗日乘子法和KKT条件能够得到最优值?

拉格朗日乘子法和KKT条件能够得到最优值的原因

对于拉格朗日乘子法，假设目标函数为 \(f\left(x,y\right)\),要求其极值，且满足 \(g\left(x,y\right)=c\) (c为常数)。假设 \(d_{n}=f\left(x,y\right)\)，其中 \(d_{n}\) 可以取不同的值。不难看出，当\(d_{n}\)取不同的值时，我们可以得到不同的等高线(如上图所示)。(其实等高线主要针对二维输入而只有一维输出的，由于三维曲面难以分析，因此，我们利用水平横切面将切面投影到 xoy 平面上而形成等高线)。
而对于方程 \(g\left(x,y\right)=c\) 的可行集，假设他们构成了一条曲线。由于在无解的时候这条曲线和等高线是不会相交的，只有有解的时候，曲线和等高线就会相交。由于等高线可以变大或变小，所以只有等高线与曲线相切的时候，等高线才能确定下来，也才能找到最优解。否则相交的时候会存在多个等高线，那么便无法找到最优解。那么，相切意味者切线必须平行，同时也意味着两者的梯度平行。此时引入一个未知标量 \(\lambda \)。有：

$$\nabla \left[ f\left( x,y\right) +\lambda \left( g\left( x,y\right) -c\right) \right] =0 \quad \lambda\neq0$$

到这里，其实这个式子就对应到了 \(L\left( \alpha ,x\right)\)对 \(x\) 的导数为零；

对于KKT条件，它是解决凸优化问题的必要条件。我们以上文提到的带不等式约束的优化问题为例。其实，\(f\left( x\right) =\max _{\alpha,\beta}L\left( \alpha ,\beta ,x\right)\)。为什么呢？由于有约束条件\(h_{j}\left(x\right)=0\) 且 \(\alpha g\left(x\right)\leq 0\)，所以只有当\(g_{j}\left(x\right)=0\) 时，函数L 才会在满足约束条件下取得最大值。诶？刚好这个最大值是 \(f\left(x\right)\)。所以现在我们要最小化的 \(f\left(x\right)\) 就可以写为 \(\min_{x}\max _{\alpha,\beta}L\left( \alpha ,\beta ,x\right)\) 。然后，由于我们的优化是满足强对偶的,即可以利用对偶式子来求解原问题的最优解，所以式子又可以写为 \(\max_{\alpha,\beta}\min _{x}L\left( \alpha ,\beta ,x\right)\)。那么当式子在 \(x_{0}\) 处取得最小值的时候，根据费马引理，有\(L\left( \alpha ,\beta ,x\right)\)对 \(x\) 的导数必须为零，这就是 KKT 的第一个条件,而 \(h\left(x\right)=0\) 为已知条件作为 KKT 的第二个条件，接着 \(\alpha g\left( x\right)=0\)为必须满足的 KKT 的第三个条件，另外 KKT 乘子\(\alpha _{i}\)、\(\beta _{i}\)均需要大于等于零。所有上述说明，满足强对偶条件的优化问题的最优值都必须满足 KKT 条件。

SVM 与 KKT 条件分析

在 SVM 软间隔基本型的优化问题中，要满足的 KKT 条件为：

$$\begin{cases}\alpha _{i}\geq 0,\quad \mu_{i}\geq 0\\ y_{i}f\left( x_{i}\right) -1+\xi _{i}\geq 0\\ \alpha _{i}\left( y_{i}f\left( x_{i}\right) -1+\xi _{i}\right) =0\\ \xi _{i}\geq 0,u_{i}\xi _{i}=0\end{cases}$$

再结合求解出的约束 \(0\leq \alpha _{i}\leq C\) 以及 \(C=\alpha_{i}+\mu_{i}\)。
那么，对于任意一个样本 \(\left(x _{i},y _{i}\right)\)，由括号中的第三个条件可知，总有 \(\alpha _{i}=0\) 或者 \(y_{i}f\left( x_{i}\right)=1-\xi _{i}\);
那么当 \(\alpha _{i}=0\)，即样本被分类正确，它们处在边界的外面，不会影响到函数 f,即 \(y_{i}\left( w^{T}x_{i}+b\right) \geq 1\);
当 \(\alpha_{i}>0\) 时，该样本是支持向量;
若 \(0<\alpha _{i}0\)，推出 \(\xi_{i}=0\),所以 \(y_{i}f\left( x_{i}\right)=1-\xi _{i}\)，即该样本恰好落在最大间隔的边界线上，即 \(y_{i}\left( w^{T}x_{i}+b\right)=1\);
若 \(\alpha_{i}=C\)，则有 \(\mu_{i}=0\)，那么此时若 \(\xi_{i}\leq 1\)，则样本落在最大间隔的内部，否则该样本被错误分类了，即它跑到了对面的间隔边界外了，即 \(y_{i}\left( w^{T}x_{i}+b\right) \leq 1\)。
总之，软间隔的支持向量可以在边界上，边界内或者错误的边界外。

注意硬间隔支持向量与软间隔支持向量的区别。

参考

[1] <<机器学习>> by 周志华
[2] <<统计学习方法>> by 李航
[3] 机器学习算法与Python实践之（三）支持向量机（SVM）进阶
[4] 深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件
[5] 浅谈最优化问题的KKT条件
[6] 拉格朗日乘数Wiki

前言

如果面试题是关于 n 为的整数并且没有限定 n 的取值范围，或者输入任意大小的整数，那么可能需要考虑大数问题。而字符串是一种简单、有效地表示大数的方法。

题目(打印从 1 到最大的 n 位数)

题目:输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的3 位数即 999。

算法思路

本题没有给定 n 的范围，因此需要考虑大数问题。

算法思路一(字符串模拟)

用字符串表示数字的时候，最直观的方法就是字符串里每个字符都是 ‘0’-‘9’ 之间的某一个字符，用来表示数字中的任一位。因为数字最大是 n 位的，因此我们需要一个长度为 n+1 的字符串(字符串中最后一位是结束符号 ‘\0’)。并且将字符串的每一位初始化为 ‘0’，但要注意的是，最后打印的时候，前半部分的 0 需要过滤掉。

接下来，我们就对字符串的最后一位一直加 1 ，然后再判断是否需要进位，如果需要进位，那么就需要把字符串最后一位变为 ‘0’，而前一位的字符也要跟着加 1，然后继续判断是否需要继续进位，一直到直接加 1，不需要进位，或者遇到了最大的 n 位数退出外层循环。

算法思路二(递归法)

将问题转换成按数字排列，也就是所对于字符串的每一位都可以有 10 种选择—-‘0’-‘9’。也就是说，我们把数字的每一位都从 0 到 9 依次排列一遍，就得到所有的十进制数。最后打印的时候只要从第一个非 0 的字符开始打印即可。

算法实现

字符串模拟

递归法

复杂度分析

算法一的时间消耗主要在 while 循环上，由于需要打印出从 1 到最大的 n 位数，因此若设这些数共有 m 个，那么时间复杂度为 O(m)；而算法二采用递归思想，时间复杂度也为 O(m)，差不多共有 10^n 个组合。空间复杂度都为 O(n)。

参考

<<剑指offer2>>

前言

支持向量机 SVM 是一种可以进行二分类、多分类以及回归分析的强大工具，并且 SVM 可以称得上表现较出色的监督学习算法，因此，我们一定得好好分析其原理，为啥它能够表现出色呢?

可视化的二分类问题

我们来看看下面这张图：

假设红色的圈表示样本正例，绿色的圈表示样本反例。此时我们需要找到一条直线将这两类样本划分开(先忽略新样本点)。从图中可以看出我们可以有很多条直线可以划分样本。但是，究竟要选择哪一条呢，依据的标准是什么？
嗯，可以肯定地说红色的那条线会是最好的那条。我们注意到图中有两条黑色的线恰好分别将样本隔住，而假设这条红色的线就处在两条直线的正中间，那么，你可能会想黑色的线也能隔住，为啥选红色的线？其实选择红色的线有点考虑到要去适应新来的样本分类了。假如来了一个新样本点恰好落在图中所示的位置，那么对于蓝色的线来说，它已经将新样本错误分类了，但是对于红色的线来说并没有任何影响。也就说，红色的线它相比于其他任何线对于新样本的分类准确率更高。(专业一点就说泛化能力更强一些，对数据的容忍度较好)，因此我们没有任何理由不选红色的这个线来划分数据集。所以呢，我们要对样本进行分类就是要找这样的线，在三维中，要找的是划分的平面，而在大于三维的时候，由于维数太高超出了人的想象空间，此时我们要找的那个面都称为超平面。但在讨论的时候，无论在低维还是在高维找划分的面，我们都直接称超平面。

间隔与支持向量

你可能发现了上图中有个挺大(挺胖)的间隔，它由两条黑色的线围成。没错，这个就是我们现在要介绍的间隔。在介绍之前，我们来对此类问题建立数学模型，以数学公式的形式来进行分析。

假设给定训练集 D={(x1,y1),(x2,y2),…,(xm,ym)}，样本标签 $y_{i}\in \left\{ +1,-1\right\}$ (以 +1 表示正例样本，-1 表示反例样本)。在样本空间中，划分超平面由线性方程:\(w^{T}x+b=0\) 确定,其中 w={w1;w2;…;wd} 为法向量，决定了超平面的方向，b为位移项(也就是超平面的偏移)

对于 SVM 分类问题，我们要寻找的其实就是一个分类函数 \(f\left(x\right)\)，它能够根据输入输出分类结果，那么当 \(f\left( x\right) =sign\left(w^{T}x+b\right) \),如果结果大于 0，则被归为 +1 类，如果结果小于 0，则被归为 -1 类(其中 sign() 为符号函数)。然后，我们还需要两个超平面来形成上述这个间隔，其中这两个超平面(由两个方程\(w^{T}x+b=1\)) 和 \(w^{T}x+b=-1\)给出) 到划分超平面的距离是相等的,而这个距离仅考虑的是离划分超平面最近的那些点到划分超平面的距离。那么这时候我们引入支持向量的定义：那些点就是支持向量(support vector)。如上图所示，这个距离为\(\dfrac {1}{\left| w\right| }\)，怎么计算呢？如果是两条直线:ax+by=c1 与 ax+by=c2,那么其距离就是\(\dfrac {\left| c_{1}-c_{1}\right| }{\sqrt {a^{2}+b^{2}}}\)，这里是二维的情况。而对于向量 w={w1;w2}来说，假如有 \(w_{1}x_{1}+w_{2}x_{2}=1\) 和 \(w_{1}x_{1}+w_{2}x_{2}=0\) 两个方程，那么他们之间的距离就是 \(\dfrac {1}{\sqrt {w^{2}_{1}+w^{2}_{2}}}\)，而分母实际上是向量 \(w\) 的模长||w||，所以随后的距离就是 \(\dfrac {1}{\left| w\right| }\)，那么推广到 w={w1;w2;w3,..,wd} 的情况也是成立的。所以可以算出我们要寻找的这个间隔的距离为 \(\dfrac {2}{\left| w\right| }\)。

那么，我们就得到了间隔的距离函数。为了寻找最大间隔，即这个距离要最长，问题首先转化为最小化 ||w|| 这个问题。另外，这里还有个约束就是：如果要将训练样本划分正确，也就是不落在间隔内，对于正例样本来说，必须满足 \(w^{T}x_{i}+b\geq 1\)；对于反例样本来说，必须满足 \(w^{T}x_{i}+b\leq -1\) ,总之就是我们既要间隔最大，又要让样本能够分类正确，所以必须得有这样的约束。

那么，由于 $y_{i}\in \left\{ +1,-1\right\}$，我们可以将上述约束合并在一起：

$$y_{i}\left( w^{T}x_{i}+b\right) \geq 1,i=1,2,\ldots ,m$$

所以 SVM 分类最终的问题就是优化下述问题：

$$\min _{w,b}\dfrac {1}{2}\left\| w\right\| ^{2}\quad s.t. y_{i}\left( w^{T}x_{i}+b\right) \geq 1,i=1,2,\ldots ,m$$

那么这个公式就是支持向量机的基本型了。

上述问题其实是一个凸二次规划问题，属于凸优化的一个特例。那什么是凸优化？它必要条件是什么？凸优化解决的是凸集中凸函数的最优化问题，且凸优化中局部最优值必定是全局最优值。而它的必要条件要求目标函数是凸函数，并且变量的约束函数是凸函数（不等式约束时），或者是仿射函数（等式约束时）。而对于凸二次规划问题，目标函数为二次函数，目前可以通过 QP(Quadratic Programming) 工具来进行求解。但是由于其求解效率的低效，因此我们寻求利用对偶问题来进行转化求解。即将原问题通过拉格朗日乘子法转化为对偶问题(c此时为线性分类下的SVM分类问题的对偶问题)，再利用对偶问题来求解原问题的最优解。毋庸置疑，后者一般会比直接使用 QP 工具来得高效。那么使用的对偶问题能带来哪些好处？其一，是对偶问题往往更容易求解；其二是可以方便地引入核函数，进而推广到非线性的 SVM 分类问题。

那什么是对偶问题？

注：为了更好优化||w||，我们对式子进行变形以方便计算，但不会影响最后的优化结果。

对偶问题

首先我们将上述支持向量机的基本型中的每个约束条件加上拉格朗日乘子 \(\alpha _{i}\),且 \(\alpha _{i}\geq 0\) ，那么我们得到的拉格朗日函数可写为:

$$L\left(w,b, \alpha \right) =\dfrac {1}{2}\left\| w\right\| ^{2}+\sum ^{m}_{i=1}\alpha _{i}\left( 1-y_{i}\left( w^{T}x_{i}+b\right) \right)$$

其中 \(\alpha =\left( \alpha _{1};\alpha _{2};\ldots ;\alpha _{m}\right)\)。
此时令目标函数 \(L\) 对 \(w\) 和 \(b\) 的偏导均为零可得:

\(w=\sum ^{m}_{i=1}\alpha _{i}y_{i}x_{i}\quad,\quad0=\sum ^{m}_{i=1}\alpha _{i}y_{i}\)
接下来带入 \(0=\sum ^{m}_{i=1}\alpha _{i}y_{i}\)，消去 \(b\) 后得:

$$L\left(w,\alpha \right) =\dfrac {1}{2}\left\| w\right\| ^{2}+\sum ^{m}_{i=1}\alpha _{i}\left( 1-y_{i}w^{T}x_{i}\right)$$

再带入\(w=\sum ^{m}_{i=1}\alpha _{i}y_{i}x_{i}\)，消去 w，即：

$$\begin{aligned}L\left( \alpha \right) =\dfrac {1}{2}\left\| w\right\| ^{2}+\sum ^{m}_{i=1}\alpha _{i}-\sum ^{m}_{i=1}w^{T}\alpha _{i}y_{i}x_{i}\\ =\dfrac {1}{2}w^{T}w+\sum ^{m}_{i=1}\alpha _{i}-w^{T}w\\ =\sum ^{m}_{i=1}\alpha _{i}-\dfrac {1}{2}w^{T}w\end{aligned}$$

再来，先取一个固定的 \(\alpha ‘\quad \alpha ‘_{i}\geq 0\)，由于 \(\max L\left(w,b, \alpha \right) \geq L\left(w,b, \alpha ‘\right) \)，即函数 \(L\) 的最大值一定会大于等于其任意函数值,那么如果先对 \(w\) 和 \(b\) 最小化时，即等式两边分别加上 \(\min _{w,b}\)，则有：

$$\min _{w,b}\left( \max_{\alpha} L\left( w,b,\alpha \right) \right) \geq \min _{w,b}L\left( w,b,\alpha '\right) \quad \alpha _{i}\geq 0$$

接着对于上述不等式，我们只需要比右边的最大值大就行，因此得到：

$$\min _{w,b}\left( \max_{\alpha} L\left( w,b,\alpha \right) \right) \geq \max_{\alpha '}\left(\min _{w,b}L\left( w,b,\alpha '\right)\right) \quad \alpha _{i}\geq 0$$

这个式子的左侧和右侧刚好是最大化和最小化互换，我们把右边这个式子称为左边问题的对偶问题。那么只要我们只要把对偶问题解决了，也就得到了左侧式子即原问题的下限。
当我们通过对 \(w\) 和 \(b\) 求导并消去 \(L\) 中的 \(w\) 和 \(b\) 时，可以进一步简化上式，得到:

$$\min _{w,b}\left( \max_{\alpha} L\left( w,b,\alpha \right) \right) \geq \max_{\alpha '}L\left( \alpha '\right)$$

那么我们便可以很轻松地推出，此时我们只需求出上述不等式右边的这个最大化问题就可以了。其中这个最大化问题就是原问题(primal problem)的对偶问题(dual problem)
最终带入 \(w\) 等式后我们得到对偶问题的公式为:

$$\max _{\alpha }\sum ^{m}_{i=1}\alpha _{i}-\dfrac {1}{2}\sum ^{m}_{i=1}\sum ^{m}_{j=1}\alpha _{i}\alpha _{j}y_{i}y_{j}x_{i}^{T}x_{j}\quad \alpha _{i}\geq 0$$

解出 \(\alpha\) 后，求出\(w\)和\(b\)即可得到模型

$$f\left( x\right) =w^{T}x+b=\sum ^{m}_{i=1}\alpha _{i}y_{i}x_{i}^{T}x+b$$

事实上，上述模型我们是建立在训练样本都能够正确分类，且是线性可分的前提之上。那么，如果训练样本中有部分样本不能够正确分类时，又应该怎么做？那么我们便引入了松弛向量和软间隔。

注：上述公式中的 w,x,\(\alpha\),\(\alpha ‘\) 均为向量。

松弛向量与软间隔最大化

如果我们遇到下图中的情况，存在离群点。其中蓝色的线是为了能够将训练样本正确分类而不得不变成非线性划分，而红色的线是我们上述情况中的线性可分的情况，那这两种分法哪个更好呢？我们训练模型的最终目标都是为了能够进行预测，也就要求了其泛化能力要好，如果选择了蓝色的线，那么对于训练样本来说确实划分得很正确，通俗地说就是模型学得太好了，但是对于预测样本来说，它们被误分类的概率将比使用红色的线进行划分来得更高。这是因为模型学得太好了，以至于适应不了某些特殊的预测样本(例如，离群点)。通常这种情况就称为过拟合。那么解决它的方法其实也很简单，我们需要允许某些离群点可以稍微偏移超平面，即允许这些离群点在间隔之内被误分类，那么它们到分类面的距离就可以小于1。为此，我们对每个训练样本 \(\left( x_{i},y_{i}\right) \) 引入了一个松弛变量 \(\xi_{i}\geq 0 \)

那么原线性可分情况下的 SVM 基本型就改为：

$$\min _{w,b}\dfrac {1}{2}\left\| w\right\| ^{2}+C\sum ^{m}_{i=1}\xi _{i}\quad s.t.\quad y_{i}\left( w^{T}x_{i}+b\right) \geq 1-\xi _{i}\quad \xi _{i}\geq 0,i=1,2,\ldots ,m$$

首先，这个最小化目标函数使得 \(\dfrac {1}{2}\left| w\right| ^{2}\) 最小化即将间隔最大化，同时使得 \(\sum ^{m}_{i=1}\xi _{i}\) 控制误分类的样本点尽量少，而参数 C(C>0) 用来平衡这二者的关系，使整体达到一个最好的结果，一般称之为惩罚参数，就好像模型犯错后就要给它一个 C 来惩罚似的。而当 C 越大的时候，表明离群点对目标函数的影响越大，也就是越不希望看到离群点。那么，为了分类它，间隔也会很小，但大部分样本点仍然遵守限制条件。另外，约束条件中的 \(1-\xi_{i}\) 时，其实放松了约束。因为当 \(\xi _{i}<1\)，样本点也可以落在间隔之内了。

这就是软间隔支持向量机的基本型了，而前述的支持向量机亦称之为硬间隔支持向量机。

这时候，经过同样的推导，对偶问题最终变为：

$$\max _{\alpha }\sum ^{m}_{i=1}\alpha _{i}-\dfrac {1}{2}\sum ^{m}_{i=1}\sum ^{m}_{j=1}\alpha _{i}\alpha _{j}y_{i}y_{j}x_{i}^{T}x_{j}\quad s.t.\quad \sum ^{m}_{i=1}\alpha _{i}y_{i}=0,0\leq \alpha _{i}\leq C,i=1,2,\ldots ,m$$

那么我们得到的拉格朗日函数可写为:

$$L\left(w,b, \alpha,\xi,\mu \right) =\dfrac {1}{2}\left\| w\right\| ^{2}+C\sum ^{m}_{i=1}\xi _{i}+\sum ^{m}_{i=1}\alpha _{i}\left( 1-\xi_{i}-y_{i}\left( w^{T}x_{i}+b\right) \right)-\sum ^{m}_{i=1}\mu_{i}\xi_{i} \quad \alpha_{i}\geq 0,\mu_{i}\geq 0$$

注意到，硬间隔与软间隔的对偶问题差异就在于，前者是 \(0\leq \alpha_{i}\),后者是 \(0\leq \alpha _{i}\leq C\),且需要满足 \(C=\alpha_{i}+\mu_{i}\) 。另外需要注意的是，b 的求值公式也发生改变了。我们在之后的 SMO 算法详解中会进一步推导。

下一篇我们将深入了解核函数、对偶问题的求解及其原理。

参考

[1] <<机器学习>> by 周志华
[2] <<统计学习方法>> by 李航
[3] 机器学习算法与Python实践之（三）支持向量机（SVM）初级

前言

位运算是把数字用二进制表示之后，对每一位上 0 或 1 的运算。二进制及其位运算非常重要，在很多底层技术中频繁出现。那么面试题更不例外了。

位运算总共有 5 种运算，与、或、异或、左移和右移。关于与 (&)、或 (|)和异或 (\(\oplus\)) 的规律可总结为:

1. 与：只要有 0就是 0，否则为 1；
2. 或：只要有 1 就是 1，否则为 0；
3. 异或：两个二进制位不同为 1，相同为 0。

左移运算符 m<>n，表示把 m 右移 n 位。若为负数，则高位补 0，否则高位补 1。

题目(二进制中1的个数)

题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把 9 表示成二进制 1001，有 2 位是 1 。因此，如果输入 9，则该函数输出 2。

算法思路

算法思路一

我们把输入的二进制数的最后一位与 1 进行位与运算，如果是 1，就计数；然后将二进制数右移一位，再进行同样的操作，直到整数为 0 退出循环。此思路只能针对输入的整数是正整数，否则会陷入死循环。

算法思路二

由于正数和负数的二进制数 n 移位规律不同，因此采用右移来计数较为麻烦。那现在我们就不移动输入整数的二进制表示，而是利用一个无符号的数 1，然后先和 n 的最低位相与，判断最低位是否为 1；然后接着把 1 左移一位，再和 n 做与运算，就能判断 n 的次低位是不是1，这样一直操作，直到循环 n 的二进制位数次。

算法思路三

我们发现将 n 减去 1 再和 n 位与可以去掉 n 中最右的 1，那么 n 中有几个这样的 1 ，就需要去掉几次。

注：把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制的问题都可以用这种思路解决。

算法实现

算法实现一

算法实现二

算法实现三

复杂度分析

算法一的时间主要消耗在对二进制的移位上，时间复杂度为 O(logn)；算法二需要进行循环 n 次(输入的二进制有 n 位)，因此时间复杂度为 O(n);若输入数的二进制表示中 1 的个数为 n，那么算法三仅需循环 n 次，时间复杂度最好达到 O(1)，最坏达到 O(n)。另外空间复杂度均为 O(1)。

参考

<<剑指offer2>>