【人工智能】非线性分类器（QDU）

2023-12-09 23:18:09

转载请务必经过我的同意

非线性分类器

支持向量机（SVM，support vector machine）

boosting算法

支持向量机

简介

支持向量机（support vector machines）是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解。由简至繁的模型包括：

当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机；（也称硬间隔 SVM或线性可分 SVM）
当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机；（也称软间隔 SVM或线性不可分 SVM）
当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机；（也称核函数或非线性 SVM）

间隔最大化准则

“间隔最大化”是用于确定最优超平面的方法，其要求找到一个超平面能够将训练样本没有错误地分开，并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的，则我们把这个超平面称作最优分类超平面（Optimal Seperating Hyperplanc)，简称最优超平面(Optimal Hyperplanc)。两类样本中离分类面最近的样本到分类面的距离之和称作分类间隔(margin)，最优超平面也称作最大间隔超平面。

上述“间隔最大化准则”是SVM的基本思想，在训练样本具有不同特征的情况下会有所不同，下面的硬间隔和软间隔中会有体现。

硬间隔 SVM （线性可分 SVM）

硬间隔部分可以通过下图来理解：

给定一组数据 ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) , … , ( x ( m ) , y ( m ) ) {(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)},…,(x^{(m)},y^{(m)})} (x(1),y(1)),(x(2),y(2),…,(x(m),y(m))，其中 x ( i ) x^{(i)} x(i)为 d d d维列向量， x ( i ) ∈ R d x^{(i)}∈R^d x(i)∈Rd， y ( i ) y^{(i)} y(i)是一个数， y ( i ) ∈ { − 1 , + 1 } y^{(i)}∈\{−1,+1\} y(i)∈{−1,+1} 。如果两类样本线性可分，即存在一个超平面 w ⊤ x + b = 0 w^⊤x+b=0 w⊤x+b=0 将两类样本分隔开，这样可以得到：
{ w ⊤ x ( i ) + b > 0 , i f y ( i ) = + 1 w ⊤ x ( i ) + b < 0 , i f y ( i ) = − 1 \begin{cases} w^⊤x^{(i)}+b>0, && if && y^{(i)} = +1 \\ w^⊤x^{(i)}+b<0, && if && y^{(i)} = -1 \\ \end{cases} {w⊤x(i)+b>0,w⊤x(i)+b<0,ifify(i)=+1y(i)=−1
将两个式子合并成一个式子后才方便后续的一些计算，所以合并可得：
y ( i ) s i g n ( w ⊤ x ( i ) + b ) = 1 ⟺ y ( i ) ( w ⊤ x ( i ) + b ) > 0 ( 1.1 ) y^{(i)}\space sign(w^⊤x^{(i)}+b)=1\space\space\space⟺\space\space\space y^{(i)}(w^⊤x^{(i)}+b)>0 \tag{$1.1$} y(i) sign(w⊤x(i)+b)=1 ⟺ y(i)(w⊤x(i)+b)>0(1.1)
对于任意的 ζ > 0 ζ>0 ζ>0 ， ( 1.1 ) (1.1) (1.1) 式等价于 y ( i ) ( ζ w ⊤ x ( i ) + ζ b ) > 0 y^{(i)}(ζw^⊤x^{(i)}+ζb)>0 y(i)(ζw⊤x(i)+ζb)>0，则说明 ( w , b ) (w,b) (w,b) 具有放缩不变性，为了后面优化方便，令 m i n ∣ w ⊤ x + b ∣ = 1 min|w^⊤x+b|=1 min∣w⊤x+b∣=1，即：
{ w ⊤ x ( i ) + b ≥ + 1 , i f y ( i ) = + 1 w ⊤ x ( i ) + b ≤ − 1 , i f y ( i ) = − 1 \begin{cases} w^⊤x^{(i)}+b≥+1, && if && y^{(i)} = +1 \\ w^⊤x^{(i)}+b≤-1, && if && y^{(i)} = -1 \\ \end{cases} {w⊤x(i)+b≥+1,w⊤x(i)+b≤−1,ifify(i)=+1y(i)=−1
( 1.1 ) (1.1) (1.1) 式就转化为
y ( i ) ( w ⊤ x ( i ) + b ) ≥ 1 ( 1.2 ) y^{(i)}(w^⊤x^{(i)}+b)≥1 \tag{$1.2$} y(i)(w⊤x(i)+b)≥1(1.2)
要实现间隔最大化（不知道大家能不能理解“间隔最大化”的目的？目的是得到最优分类面，即 w ∗ w^* w∗和 b ∗ b^* b∗），就需要先表示出间隔。刚刚也提到了间隔就是两类样本中距离分类面最近的样本的距离和，通过类似于平面中点到直线的距离公式可以类比得到 d d d维中间隔为离分类面最近的正样本点到分类面和离分类面最近的负样本点到分类面的距离之和，或者可以理解为上图中两条虚线的距离，即 1 ∣ ∣ w ∣ ∣ + 1 ∣ ∣ w ∣ ∣ = 2 ∣ ∣ w ∣ ∣ \frac{1}{||w||}+\frac{1}{||w||} = \frac{2}{||w||} ∣∣w∣∣1+∣∣w∣∣1=∣∣w∣∣2。（ ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣为 w w w的二范数）

因此，线性SVM的优化目标为：
max ⁡ w , b 2 ∣ ∣ w ∣ ∣ ⟹ min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 \max \limits_{w,b} \frac{2}{||w||}\space\space\space ⟹\space\space\space \min \limits_{w,b} \frac{1}{2}||w||^2 \\ w,bmax∣∣w∣∣2 ⟹ w,bmin21∣∣w∣∣2

s . t . y ( i ) ( w ⊤ x ( i ) + b ) ≥ 1 , i = 1 , 2 , … , m ( 1.3 ) s.t. \space\space\space\space\space\space y^{(i)}(w^⊤x^{(i)}+b)≥1,\space\space\space\space\space i=1,2,…,m \tag{$1.3$} s.t. y(i)(w⊤x(i)+b)≥1, i=1,2,…,m(1.3)

这是一个凸二次规划（convex quadratic programming）问题，可用现成的二次规划问题优化方法求解（如：Interior point method、Active set method、Gradient projection method等），但是现有求解方法都比较低效，尤其是在处理大数量的训练样本时。所以现实中一般采用对偶算法（dual algorithm），通过求解原始问题（primal problem）的对偶问题（dual problem），来获得原始问题的最优解。这样做的优点，一是对偶问题往往更容易求解，二是能自然地引入核函数，进而高效地解决高维非线性分类问题。

有关问题的转化了解即可。

原始的优化问题 ( 1.3 ) (1.3) (1.3) 式与对偶问题的转换关系如下，

由拉格朗日乘子法，注意这里有 m m m 个样本，于是为每条约束引入拉格朗日乘子 α i ≥ 0 \alpha_i≥0 αi≥0 ， ( 1.3 ) (1.3) (1.3) 式的拉格朗日函数为：
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m α i ( 1 − y i ( w T x i + b ) ) ( 2.1 ) L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^m \alpha_i(1-y_i(w^Tx_i+b)) \tag{$2.1$} L(w,b,α)=21∣∣w∣∣2+i=1∑mαi(1−yi(wTxi+b))(2.1)
其中， α = ( α 1 , α 2 , . . . , α m ) T ∈ R + m \alpha=(\alpha_1,\alpha_2,...,\alpha_m)^T∈R_+^m α=(α1,α2,...,αm)T∈R+m，称为 L a g r a n g e Lagrange Lagrange乘子。

其相应的对偶问题为：
max ⁡ α min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m α i ( 1 − y i ( w T x i + b ) ) s . t .        α i ≥ 0 ,       i = 1 , 2 , . . . , m ( 2.2 ) \max \limits_{\alpha} \min \limits_{w,b} \frac{1}{2}||w||^2+\sum_{i=1}^m \alpha_i(1-y_i(w^Tx_i+b)) \tag{$2.2$} \\ s.t.\space\space\space\space\space\space \alpha_i≥0,\space\space\space\space\space i=1,2,...,m αmaxw,bmin21∣∣w∣∣2+i=1∑mαi(1−yi(wTxi+b))s.t.      αi≥0,     i=1,2,...,m(2.2)
上式内层对 ( w , b ) (w,b) (w,b) 的优化属于无约束优化问题，由极值条件可知，偏导等于零：
∂ L ∂ w = 0     ⟹     w = ∑ i = 1 m α i y i x i ∂ L ∂ b = 0     ⟹     ∑ i = 1 m α i y i = 0 \frac{∂L}{∂w}=0 \space\space\space⟹\space\space\space w=\sum_{i=1}^m\alpha_iy_ix_i \\ \frac{∂L}{∂b}=0 \space\space\space⟹\space\space\space \sum_{i=1}^m\alpha_iy_i=0 \\ ∂w∂L=0   ⟹   w=i=1∑mαiyixi∂b∂L=0   ⟹   i=1∑mαiyi=0
代入 ( 2 , 2 ) (2,2) (2,2) 式得：
max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j s . t .        α i ≥ 0 ,       i = 1 , 2 , . . . , m ∑ i = 1 m α i y i = 0 ( 2.3 ) \max \limits_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_jx_i^Tx_j \\ \\ s.t.\space\space\space\space\space\space \alpha_i≥0,\space\space\space\space\space i=1,2,...,m \\ \tag{$2.3$} \sum_{i=1}^m\alpha_iy_i=0 αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxjs.t.      αi≥0,     i=1,2,...,mi=1∑mαiyi=0(2.3)

推导过程：
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m α i ( 1 − y i ( w T x i + b ) ) = 1 2 w T w + ∑ i = 1 m ( α i − α i y i w T x i − b α i y i ) = 1 2 w T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i − w T ∑ i = 1 m α i y i x i − b ∑ i = 1 m α i y i = ∑ i = 1 m α i − 1 2 w T ∑ i = 1 m α i y i x i = ∑ i = 1 m α i − 1 2 ( ∑ i = 1 m α i y i x i ) T ∑ i = 1 m α i y i x i = ∑ i = 1 m α i − 1 2 ∑ i = 1 m α i y i x i T ∑ i = 1 m α i y i x i = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j < x i , x j > L(w,b,\alpha) \\\\ =\frac{1}{2}||w||^2+\sum_{i=1}^m \alpha_i(1-y_i(w^Tx_i+b))\\\\ = \frac{1}{2}w^Tw+\sum_{i=1}^m (\alpha_i-\alpha_iy_iw^Tx_i-b\alpha_iy_i) \\\\ =\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i + \sum_{i=1}^m \alpha_i-w^T\sum_{i=1}^m\alpha_iy_ix_i-b\sum_{i=1}^m\alpha_iy_i \\\\ =\sum_{i=1}^m \alpha_i-\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i \\\\ =\sum_{i=1}^m \alpha_i-\frac{1}{2}(\sum_{i=1}^m\alpha_iy_ix_i)^T\sum_{i=1}^m\alpha_iy_ix_i \\\\ =\sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\alpha_iy_ix_i^T\sum_{i=1}^m\alpha_iy_ix_i \\\\ =\sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_jx_i^Tx_j \\\\ =\sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j<x_i,x_j> \\\\ L(w,b,α)=21∣∣w∣∣2+i=1∑mαi(1−yi(wTxi+b))=21wTw+i=1∑m(αi−αiyiwTxi−bαiyi)=21wTi=1∑mαiyixi+i=1∑mαi−wTi=1∑mαiyixi−bi=1∑mαiyi=i=1∑mαi−21wTi=1∑mαiyixi=i=1∑mαi−21(i=1∑mαiyixi)Ti=1∑mαiyixi=i=1∑mαi−21i=1∑mαiyixiTi=1∑mαiyixi=i=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxj=i=1∑mαi−21i=1∑mj=1∑mαiαjyiyj<xi,xj>

说明：

第一个等号后的式子为原式

第二个等号后的式子：将向量的二范数化为向量乘法的形式（内积），即 ∣ ∣ w ∣ ∣ 2 = w T w ||w||^2=w^Tw ∣∣w∣∣2=wTw；将求和符号中的式子展开

第三个等号后的式子：代入 w = ∑ i = 1 m α i y i x i w=\sum_{i=1}^m\alpha_iy_ix_i w=∑i=1mαiyixi；由于 w w w和 x x x为向量，其余变量均为数，所以化为如此样式

第四个等号后的式子：代入 ∑ i = 1 m α i y i = 0 \sum_{i=1}^m\alpha_iy_i=0 ∑i=1mαiyi=0，并合并同类项

第五个等号后的式子：代入 w = ∑ i = 1 m α i y i x i w=\sum_{i=1}^m\alpha_iy_ix_i w=∑i=1mαiyixi

第六个等号后的式子：由于 α i \alpha_i αi和 y i y_i yi为数值， x i x_i xi为向量，所以相当于对 x i x_i xi 转置

第七个等号后的式子：将两个求和合并

第八个等号后的式子： x i T x j = < x i , x j > x_i^Tx_j=<x_i,x_j> xiTxj=<xi,xj>， < a , b > <a,b> <a,b>表示两向量的内积，结果为数值

$ (2.2)$ 式的最优解应满足 KKT 条件（不证明），由 KKT 条件中的互补松弛条件（不说明）可知 α i ( 1 − y i ( w T x i + b ) ) = 0 \alpha_i(1-y_i(w^Tx_i+b))=0 αi(1−yi(wTxi+b))=0。当 α i > 0 \alpha_i>0 αi>0时， y i ( w T x i + b ) = 1 y_i(w^Tx_i+b)=1 yi(wTxi+b)=1，说明这些样本点 ( x i , y i ) (x_i,y_i) (xi,yi) 一定在间隔边界上，它们被称为“支持向量”，这些点共同决定了分离超平面。这是 svm 的一个重要特性： 训练完成后，大部分训练样本不需要保留，最终模型仅与支持向量有关。

于是可根据支持向量求 w w w：
w = ∑ i = 1 m α i y i x i = ∑ i : α i = 0 m 0 ⋅ y i x i + ∑ i : α i > 0 m α i y i x i = ∑ i ∈ S V α i y i x i ( 2.4 ) w\\\tag{$2.4$} =\sum_{i=1}^m\alpha_iy_ix_i \\ =\sum_{i:\alpha_i=0}^m 0·y_ix_i+\sum_{i:\alpha_i>0}^m \alpha_iy_ix_i \\ =\sum_{i∈SV} \alpha_iy_ix_i w=i=1∑mαiyixi=i:αi=0∑m0⋅yixi+i:αi>0∑mαiyixi=i∈SV∑αiyixi(2.4)
其中 S V SV SV 代表所有支持向量的集合。对于任意支持向量 ( x s , y s ) (x_s,y_s) (xs,ys)，都有 y s ( w T x s + b ) = 1 y_s(w^Tx_s+b)=1 ys(wTxs+b)=1。将 ( 2.4 ) (2.4) (2.4)式代入，并利用 y s 2 = 1 y_s^2=1 ys2=1：
y s ( ∑ i ∈ S V α i y i x i T x s + b ) = y s 2 ⟹ b = y s − ∑ i ∈ S V α i y i x i T x s y_s(\sum_{i∈SV} \alpha_iy_ix_i^Tx_s+b)=y_s^2 \space\space\space⟹\space\space\space b=y_s-\sum_{i∈SV}\alpha_iy_ix_i^Tx_s ys(i∈SV∑αiyixiTxs+b)=ys2 ⟹ b=ys−i∈SV∑αiyixiTxs
实践中，为了得到对 b b b 更稳健的估计，通常对所有支持向量求解得到 b b b 的平均值：
b = 1 ∣ S V ∣ ∑ s ∈ S V ( y s − ∑ i ∈ S V α i y i x i T x s ) b= \frac{1}{|SV|} \sum_{s∈SV}(y_s-\sum_{i∈SV}\alpha_iy_ix_i^Tx_s) b=∣SV∣1s∈SV∑(ys−i∈SV∑αiyixiTxs)

于是线性 svm 的分类决策函数可表示为：
f ( x ) = s i g n ( ∑ i ∈ S V α i y i x i T x + b ) f(x)=sign(\sum_{i∈SV} \alpha_iy_ix_i^Tx+b) f(x)=sign(i∈SV∑αiyixiTx+b)

QDU的PPT中：

输入：线性可分训练集 T = ( x 1 , y 1 ) , . . . , ( x m , y m ) T={(x_1,y_1),...,(x_m,y_m)} T=(x1,y1),...,(xm,ym)，其中 x i ∈ ℵ = R n x_i∈\aleph=R^n xi∈ℵ=Rn， y i ∈ γ = − 1 , + 1 , i = 1 , 2 , . . . , m y_i∈\gamma={-1,+1},i=1,2,...,m yi∈γ=−1,+1,i=1,2,...,m

输出：最大间隔分离超平面和分类决策函数

（1）构建并求解约束最优化问题（化成极小值形式）
min ⁡ α 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j − ∑ i = 1 m α i s . t . α i ≥ 0 , i = 1 , 2 , . . . , m ∑ i = 1 m α i y i = 0 \min \limits_{\alpha}\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^m \alpha_i \\\\ s.t.\space\space\space\space\space\space \alpha_i≥0,\space\space\space\space\space i=1,2,...,m \\ \sum_{i=1}^m\alpha_iy_i=0 αmin21i=1∑mj=1∑mαiαjyiyjxiTxj−i=1∑mαis.t. αi≥0, i=1,2,...,mi=1∑mαiyi=0
求得最优解 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α m ∗ ) \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_m^*) α∗=(α1∗,α2∗,...,αm∗)

（2）计算
w ∗ = ∑ i = 1 m α i ∗ y i x i b ∗ = − 1 2 ( max ⁡ i : y i = − 1 w T x i + min ⁡ i : y i = 1 w T x i ) w^*=\sum_{i=1}^m \alpha_i^*y_ix_i \\ \\ b^*=-\frac{1}{2}(\max \limits_{i:y_i=-1}w^Tx_i + \min \limits_{i:y_i=1}w^Tx_i) w∗=i=1∑mαi∗yixib∗=−21(i:yi=−1maxwTxi+i:yi=1minwTxi)

max ⁡ i : y i = − 1 \max \limits_{i:y_i=-1} i:yi=−1max 对应的是负样本点一侧的支持向量，即最上面的图片中穿过负样本点的虚线；

max ⁡ i : y i = 1 \max \limits_{i:y_i=1} i:yi=1max 对应的是正样本点一侧的支持向量，即最上面的图片中穿过正样本点的虚线；

（3）得到分离超平面
w ∗ x + b ∗ = 0 w^*x+b^*=0 w∗x+b∗=0
得到分类决策函数
f ( x ) = s i g n ( w ∗ x + b ∗ ) f(x)=sign(w^*x+b^*) f(x)=sign(w∗x+b∗)

缺点：1. 不适用于线性不可分数据集。 2. 对离群点（outlier）敏感。

比如下图就无法找到一个超平面将蓝点和紫点完全分开：

下图显示加入了一个离群点后，超平面发生了很大的变动，最后形成的间隔变得很小，这样最终的泛化效果可能不会太好。

软间隔 SVM（近似线性可分 SVM）

为了缓解这些问题，引入了 “软间隔（soft margin）”，即允许一些样本点跨越间隔边界甚至是超平面。如下图中一些离群点就跨过了间隔边界。

于是为每个样本点引入松弛变量 ξ i ξ_i ξi，优化问题变为：

min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i s . t . y i ( w T x i + b ) ≥ 1 − ξ i ξ i ≥ 0 , i = 1 , 2 , . . . , m ( 3.1 ) \min \limits_{w,b,ξ}\frac{1}{2}||w||^2+C\sum_{i=1}^mξ_i \\\\ \tag{$3.1$} s.t.\space\space\space\space\space\space y_i(w^Tx_i+b)≥1-ξ_i \\ ξ_i≥0,\space\space\space\space\space\space i=1,2,...,m w,b,ξmin21∣∣w∣∣2+Ci=1∑mξis.t. yi(wTxi+b)≥1−ξiξi≥0, i=1,2,...,m(3.1)
由上式可以看出：

离群点的松弛变量值越大，点就离间隔边界越远。
所有没离群的点松弛变量都等于0，即这些点都满足 y i ( w ⊤ x i + b ) ⩾ 1 y_i(w^⊤x_i+b)⩾1 yi(w⊤xi+b)⩾1
C > 0 C>0 C>0 被称为惩罚参数，即为 scikit-learn 中的 svm 超参数C。当C设的越大，意味着对离群点的惩罚就越大，最终就会有较少的点跨过间隔边界，模型也会变得复杂。而C设的越小，则较多的点会跨过间隔边界，最终形成的模型较为平滑。

该优化问题的求解方法与硬间隔类似，为每条约束引入拉格朗日乘子： α i ⩾ 0 \alpha_i⩾0 αi⩾0， β i ⩾ 0 \beta_i⩾0 βi⩾0， α i ⩾ 0 \alpha_i⩾0 αi⩾0， β i ⩾ 0 \beta_i⩾0 βi⩾0 ， ( 3.1 ) (3.1) (3.1) 式的拉格朗日函数为：
L ( w , b , ξ , α , β ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i + ∑ i = 1 m α i [ 1 − ξ i − y i ( w T x i + b ) ] + ∑ i = 1 m β i ( − ξ i ) ( 3.2 ) L(w,b,ξ,\alpha, \beta)=\frac{1}{2}||w||^2+C\sum_{i=1}^mξ_i+\sum_{i=1}^m\alpha_i[1-ξ_i-y_i(w^Tx_i+b)]+\sum_{i=1}^m\beta_i(-ξ_i)\tag{$3.2$} L(w,b,ξ,α,β)=21∣∣w∣∣2+Ci=1∑mξi+i=1∑mαi[1−ξi−yi(wTxi+b)]+i=1∑mβi(−ξi)(3.2)
其对偶问题为：
max ⁡ α , β min ⁡ w , b , ξ L ( w , b , ξ , α , β ) s . t . α i ≥ 0 , i = 1 , 2 , . . . , m β i ≥ 0 , i = 1 , 2 , . . . , m ( 3.3 ) \tag{$3.3$} \\ \max \limits_{\alpha, \beta}\min\limits_{w, b, ξ}L(w,b,ξ,\alpha,\beta)\\ s.t.\space\space\space\space\space\space \alpha_i≥0,\space\space\space\space\space\space i=1,2,..., m\\ \space\space\space\space\space\space\space\space\space\space\space\space\space \beta_i≥0,\space\space\space\space\space\space i=1,2,..., m\\ α,βmaxw,b,ξminL(w,b,ξ,α,β)s.t. αi≥0, i=1,2,...,m βi≥0, i=1,2,...,m(3.3)
上式内层对 ( w , b , ξ ) (w,b,ξ) (w,b,ξ) 的优化属于无约束优化问题，则令偏导为零：
∂ L ∂ w = 0 ⟹ w = ∑ i = 1 m α i y i x i ( 3.4 ) \frac{∂L}{∂w}=0\space\space\space⟹\space\space\space w=\sum_{i=1}^m\alpha_iy_ix_i \tag{$3.4$} ∂w∂L=0 ⟹ w=i=1∑mαiyixi(3.4)

∂ L ∂ b = 0 ⟹ ∑ i = 1 m α i y i = 0 ( 3.5 ) \frac{∂L}{∂b}=0\space\space\space⟹\space\space\space \sum_{i=1}^m\alpha_iy_i=0 \tag{$3.5$} ∂b∂L=0 ⟹ i=1∑mαiyi=0(3.5)

∂ L ∂ ξ = 0 ⟹ β i = C − α i ( 3.6 ) \frac{∂L}{∂ξ}=0\space\space\space⟹\space\space\space \beta_i=C-\alpha_i \tag{$3.6$} ∂ξ∂L=0 ⟹ βi=C−αi(3.6)

将 ( 3.4 ) ∼ ( 3.6 ) (3.4)∼(3.6) (3.4)∼(3.6) 式代入 ( 3.2 ) (3.2) (3.2) 式得：
L ( w , b , ξ , α , β ) = 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j + C ∑ i = 1 m ξ i + ∑ i = 1 m α i ( 1 − ξ i ) − ∑ i = 1 m ( C − α i ) ξ i = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j L(w,b,ξ,\alpha,\beta)=\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j+C\sum_{i=1}^mξ_i+\sum_{i=1}^m\alpha_i(1-ξ_i)-\sum_{i=1}^m(C-\alpha_i)ξ_i \\ =\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j L(w,b,ξ,α,β)=21i=1∑mj=1∑mαiαjyiyjxiTxj+Ci=1∑mξi+i=1∑mαi(1−ξi)−i=1∑m(C−αi)ξi=i=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxj
又由 ( 1.6 ) (1.6) (1.6) 式： β i = C − α i ⩾ 0 β_i=C−α_i⩾0 βi=C−αi⩾0 ，因而 0 ⩽ α i ⩽ C 0⩽α_i⩽C 0⩽αi⩽C ，于是最后的优化问题化简为：
max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j s . t . ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , m ( 3.7 ) \max\limits_{\alpha} \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j \\\\ \tag{$3.7$} s.t.\space\space\space\space\space\space \sum_{i=1}^m\alpha_iy_i=0\\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space0≤\alpha_i≤C,\space\space\space\space\space\space i=1,2,...,m αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxjs.t. i=1∑mαiyi=0 0≤αi≤C, i=1,2,...,m(3.7)
求得 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α m ∗ ) T \alpha^*=(\alpha^*_1, \alpha^*_2,...,\alpha^*_m)^T α∗=(α1∗,α2∗,...,αm∗)T中对应于 α i ∗ > 0 \alpha_i^*>0 αi∗>0的样本点 $ (x_i,y_i)$的实例 x i x_i xi。
ξ i ≥ 0 ⟺ { ξ i = 0 , x i 在间隔边界上 0 < ξ i < 1 , x i 在间隔边界于分离超平面之间 ξ i = 1 , x i 在分离超平面上 ξ i > 1 , x i 在分离超平面误分类一侧 ξ_i≥0\space\space\space\space\space\space ⟺\space\space\space\space\space\space \begin{cases} ξ_i=0, \space\space\space\space\space\space x_i在间隔边界上\\ 0<ξ_i<1,\space\space\space\space\space\space x_i在间隔边界于分离超平面之间 \\ ξ_i=1,\space\space\space\space\space\space x_i在分离超平面上 \\ ξ_i>1,\space\space\space\space\space\space x_i在分离超平面误分类一侧 \\ \end{cases} ξi≥0 ⟺ ⎩⎪⎪⎪⎨⎪⎪⎪⎧ξi=0, xi在间隔边界上0<ξi<1, xi在间隔边界于分离超平面之间ξi=1, xi在分离超平面上ξi>1, xi在分离超平面误分类一侧

软间隔SVM允许样本有一定程度的误分类。但其实本质依然是线性分类器。

核方法（线性不可分 SVM）

前面展示的硬间隔和软间隔 svm 主要是用于处理线性分类问题，然而现实中很多分类问题是非线性的，如下图所示，无论怎样一个线性超平面都无法很好地将样本点分类：

所以在此引入核函数（kernel function），构造非线性svm，如下图所示，左图使用的是多项式核函数，右图使用的是高斯核函数，二者均能将样本点很好地分类：

核函数的主要作用是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。下图显示原来在二维空间不可分的两类样本点，在映射到三维空间后变为线性可分：

但回到原来的二维空间中，决策边界就变成非线性的了：

核函数是如何将原始空间映射到高维的特征空间的？下面先举个例子：

假设做一个2维到3维的映射， Φ : R 2 ⟶ R 3 Φ:R^2⟶R^3 Φ:R2⟶R3
ϕ ( x ) = ϕ ( x 1 x 2 ) = ( x 1 2 2 x 1 x 2 x 2 2 ) \phi(x)= \phi \left( \begin{matrix}{} x_1\\x_2 \end{matrix} \right)= \left( \begin{matrix}{} x_1^2\\\sqrt{2}x_1x_2\\x_2^2 \end{matrix} \right) ϕ(x)=ϕ(x1x2)=⎝⎛x122 x1x2x22⎠⎞

求 ϕ ( a ) ϕ(a) ϕ(a) 和 ϕ ( b ) ϕ(b) ϕ(b) 的内积：
ϕ ( a ) T ϕ ( b ) = ( a 1 2 2 a 1 a 2 a 2 2 ) T ⋅ ( b 1 2 2 b 1 b 2 b 2 2 ) = a 1 2 b 1 2 + 2 a 1 b 1 a 2 b 2 + a 2 2 b 2 2 = ( a 1 b 1 + a 2 b 2 ) 2 = ( ( a 1 a 2 ) T ( b 1 b 2 ) ) 2 = ( a T b ) 2 \phi(a)^T\phi(b)= \left( \begin{matrix}{} a_1^2\\\sqrt{2}a_1a_2\\a_2^2 \end{matrix} \right)^T · \left( \begin{matrix}{} b_1^2\\\sqrt{2}b_1b_2\\b_2^2 \end{matrix} \right) \\= a_1^2b_1^2 + 2a_1b_1a_2b_2+a_2^2b_2^2 =(a_1b_1+a_2b_2)^2= \left( \begin{matrix}{} \left( \begin{matrix}{} a_1\\a_2 \end{matrix} \right)^T \left( \begin{matrix}{} b_1\\b_2 \end{matrix} \right) \end{matrix} \right)^2= (a^Tb)^2 ϕ(a)Tϕ(b)=⎝⎛a122 a1a2a22⎠⎞T⋅⎝⎛b122 b1b2b22⎠⎞=a12b12+2a1b1a2b2+a22b22=(a1b1+a2b2)2=((a1a2)T(b1b2))2=(aTb)2
可以看出转换后向量的内积等于原向量内积的平方，即 ϕ ( a ) T ϕ ( b ) = ( a T b ) 2 ϕ(a)^Tϕ(b)=(a^Tb)^2 ϕ(a)Tϕ(b)=(aTb)2。

函数 κ ( a , b ) = ( a T b ) 2 κ(a,b)=(a^Tb)^2 κ(a,b)=(aTb)2 被称为二次多项核函数，于是如果想计算高维特征空间的内积 ϕ ( a ) T ϕ ( b ) ϕ(a)^Tϕ(b) ϕ(a)Tϕ(b)，我们只需计算核函数，即原向量内积的平方 ( a T b ) 2 (a^Tb)^2 (aTb)2 就可以了。这样做的好处有：

将样本点由原始空间映射到高维空间后，有大概率使原来线性不可分的问题变为线性可分。
核函数的计算是在低维特征空间计算的，它避免了在高维特征空间下计算内积的超高计算量。

接下来对问题作正式的定义：数据在原始特征空间 R d R^d Rd 不是线性可分的，则希望通过一个映射 Φ : R d ⟶ R d ~ Φ:R^d⟶R^{\tilde{d}} Φ:Rd⟶Rd~

，使得数据在新的特征空间 R d ~ R^{\tilde{d}} Rd~ 中线性可分，则软间隔 svm 基本型变为：
min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i s . t . y i ( w T ϕ ( x i ) + b ) ≥ 1 − ξ i , i = 1 , 2 , . . . , m ξ i ≥ 0 , i = 1 , 2 , . . . , m \min \limits_{w,b,ξ}\frac{1}{2}||w||^2+C\sum_{i=1}^mξ_i \\\\ s.t. \space\space\space\space\space y_i(w^T\phi(x_i)+b)≥1-ξ_i, \space\space\space\space\space i=1,2,...,m\\ ξ_i≥0,\space\space\space\space\space i=1,2,...,m w,b,ξmin21∣∣w∣∣2+Ci=1∑mξis.t. yi(wTϕ(xi)+b)≥1−ξi, i=1,2,...,mξi≥0, i=1,2,...,m
找到一个核函数 κ ( x i , x j ) = ϕ ( x i ) ⊤ ϕ ( x j ) κ(x_i,x_j)=ϕ(x_i)^⊤ϕ(x_j) κ(xi,xj)=ϕ(xi)⊤ϕ(xj) ，则相应的对偶型转化为核函数型：
max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ϕ ( x i ) ⊤ ϕ ( x j ) s . t . ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , m ⟹ max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j κ ( x i , x j ) s . t . ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , m \max \limits_{\alpha} \sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jϕ(x_i)^⊤ϕ(x_j) \\\\ s.t.\space\space\space\space\space \sum_{i=1}^m\alpha_iy_i=0 \\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space 0≤ \alpha_i ≤ C,\space\space\space\space\space i=1,2,...,m \\\\⟹\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\\\\ \max \limits_{\alpha} \sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jκ(x_i,x_j) \\\\ s.t.\space\space\space\space\space \sum_{i=1}^m\alpha_iy_i=0 \\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space 0≤ \alpha_i ≤ C,\space\space\space\space\space i=1,2,...,m αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjϕ(xi)⊤ϕ(xj)s.t. i=1∑mαiyi=0 0≤αi≤C, i=1,2,...,m⟹ αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjκ(xi,xj)s.t. i=1∑mαiyi=0 0≤αi≤C, i=1,2,...,m
这样使得计算复杂度由 O ( d ~ ) O(\tilde{d}) O(d~) 降为 O ( d ) O(d) O(d) 。求解后的分离超平面为：
f ( x ) = w T ϕ ( x ) + b = ∑ i ∈ S V α i y i ϕ ( x i ) T ϕ ( x ) + b = ∑ i ∈ S V α i y i κ ( x i , x ) + b f(x)=w^T\phi(x)+b \\\\ =\sum_{i∈SV}\alpha_iy_i\phi(x_i)^T\phi(x)+b \\\\ =\sum_{i∈SV}\alpha_iy_iκ(x_i,x)+b f(x)=wTϕ(x)+b=i∈SV∑αiyiϕ(xi)Tϕ(x)+b=i∈SV∑αiyiκ(xi,x)+b
其中 S V SV SV 代表所有支持向量的集合。这样我们就能以较小的计算量解决非线性分类问题，甚至都不需要知道低维空间的数据是怎样映射到高维空间的，只需要在原来的低维空间计算核函数就行了。

名称	形式	优点	缺点
线性核	κ ( x i , x j ) = x i T x j κ(x_i,x_j)=x_i^Tx_j κ(xi,xj)=xiTxj	速度快，可解释性强。	无法解决非线性可分问题。
多项式核	κ ( x i , x j ) = ( λ x i T x j + η ) d κ(x_i,x_j)=(\lambda x_i^Tx_j+\eta)^d κ(xi,xj)=(λxiTxj+η)d	比线性核更一般， d d d 直接描述了被映射空间的复杂度。	参数多（有 λ λ λ， η η η， d d d 要选），且当 d d d 很大时会导致计算不稳定。
径向基函数（RBF 核函数）	κ ( x i , x j ) = e x p ( − ∥ x i − x j ∥ 2 2 σ 2 ) κ(x_i,x_j)=exp(-\frac{\\|x_i-x_j\\|^2}{2\sigma^2}) κ(xi,xj)=exp(−2σ2∥xi−xj∥2)	只有一个参数，无计算不稳定问题，拟合能力强。	可解释性差，计算慢，易过拟合。

boosting 算法

boosting是一种集成学习算法，由一系列基本分类器按照不同的权重组合成为一个强分类器，这些基本分类器之间有依赖关系。

boosting算法包括：

Adaboost算法

提升树

GBDT算法

boosting 算法的基本思想：

从图中可以看出，Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

Adaboost 算法的基本思路

假设训练集样本是
T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } T = \{(x_1, y_1), (x_2, y_2), ..., (x_m,y_m)\} T={(x1,y1),(x2,y2),...,(xm,ym)}
训练集的在第 k k k个弱学习器的输出权重为
D ( k ) = ( w k 1 , w k 2 , . . . , w k m ) k ≠ 1 D ( 1 ) = ( w 11 , w 12 , . . . , w 1 i , . . . , w 1 m ) , w 1 i = 1 m i = 1 , 2 , . . . , m D(k)=(w_{k1}, w_{k2},..., w_{km}) \space\space\space\space\space\space\space\space\space\space\space\space k≠1 \\\\ D(1)=(w_{11}, w_{12},...,w_{1i},..., w_{1m}), \space\space w_{1i}=\frac{1}{m} \space\space\space\space\space\space \space\space\space\space\space\space i=1,2,...,m D(k)=(wk1,wk2,...,wkm) k=1D(1)=(w11,w12,...,w1i,...,w1m), w1i=m1 i=1,2,...,m
第 k k k 个分类器根据输入的特征预测标签，用 D k ( x ) D_k(x) Dk(x)表示。

计算学习误差率 e e e：

对于二分类而言，输出为 { − 1 , + 1 } \{-1,+1\} {−1,+1}，则第 k k k 个弱分类器 G k ( x ) G_k(x) Gk(x) 在训练集上的加权误差率为
e k = P ( G k ( x i ) ≠ y i ) = ∑ i = 1 m w k i I ( G k ( x i ) ≠ y i ) e_k=P(G_k(x_i)≠y_i)\\\\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space=\sum_{i=1}^m w_{ki}I(G_k(x_i)≠y_i) ek=P(Gk(xi)=yi) =i=1∑mwkiI(Gk(xi)=yi)

其中 I ( ⋅ ) I(·) I(⋅)的作用与C语言中bool类型转换为int类型的作用一致，即若表达式 ⋅ · ⋅ 为真，则 I ( ⋅ ) I(·) I(⋅)的值为1，否则为0。

上面式子将全部误判的点的权重加起来。

弱学习器权重系数α：

对于二分类问题，第 k k k个弱分类器的权重系数为
α k = 1 2 l o g 1 − e k e k \alpha_k=\frac{1}{2}log\frac{1-e_k}{e_k} αk=21logek1−ek
从上式可以看出，如果分类误差率 e k e_k ek 越大，则对应的弱分类器权重系数 α k α_k αk 越小。也就是说，误差率小的弱分类器权重系数越大。

更新样本权重 D D D：

假设第 k k k个弱分类器的样本集权重系数为 D ( k ) = ( w k 1 , w k 2 , . . . w k m ) D(k)=(w_{k1},w_{k2},...w_{km}) D(k)=(wk1,wk2,...wkm)，则对应的第 k + 1 k+1 k+1个弱分类器的样本集权重系数为
w k + 1 , i = w k i Z K e x p ( − α k y i G k ( x i ) ) w_{k+1,i}=\frac{w_{ki}}{Z_K}exp(-\alpha_ky_iG_k(x_i)) wk+1,i=ZKwkiexp(−αkyiGk(xi))
其中， Z K Z_K ZK是规范化因子
Z K = ∑ i = 1 m w k i e x p ( − α k y i G k ( x i ) ) Z_K = \sum_{i=1}^mw_{ki}exp(-\alpha_ky_iG_k(x_i)) ZK=i=1∑mwkiexp(−αkyiGk(xi))
从 w k + 1 , i w_{k+1,i} wk+1,ii计算公式可以看出，如果第i个样本分类错误，则 y i G k ( x i ) < 0 y_iG_k(x_i)<0 yiGk(xi)<0，导致样本的权重在第 k + 1 k+1 k+1 个弱分类器中增大，如果分类正确，则权重在第 k + 1 k+1 k+1个弱分类器中减少。

弱分类器的结合策略：

Adaboost 分类采用的是加权表决法，最终的强分类器为
f ( x ) = s i g n ( ∑ k = 1 K α k G k ( x i ) ) f(x)=sign(\sum_{k=1}^K\alpha_kG_k(x_i)) f(x)=sign(k=1∑KαkGk(xi))

G k ( x ) G_k(x) Gk(x) 的确定：

每个弱分类器都是一个单层决策树，这也就是为什么说“一个特征对应一个弱分类器”。

对于二分类问题
G k ( x ) = { 1 p f ( x ) < p θ 0 e l s e G_k(x)= \begin{cases} 1 & pf(x)<p\theta \\ 0 & else \end{cases} Gk(x)={10pf(x)<pθelse
其中， p p p用于控制不等式的符号，如果 p = − 1 p=-1 p=−1，那么 p f ( x ) < p θ pf(x)<p\theta pf(x)<pθ与 f ( x ) > θ f(x)>\theta f(x)>θ具有相同的含义，引入该变量只是为了方便格式统一； f ( x ) f(x) f(x)表示图像 x x x的某个特征值； θ \theta θ为阈值，即当特征值大于（当 p = − 1 p=-1 p=−1时）阈值时，该分类器判断该样本的标签为1。

出现了三个问题：

① 一个弱分类器对应一个特征（但可能存在多个弱分类器对应同一个特征的情况），那么如何确定该弱分类器要使用哪个特征进行判别？

② 如何确定阈值 θ \theta θ？

③ 如何确定符号 p p p？

误差率：是指全部预测错误的样本的权重之和（样本权重就是上面讲到的 D D D）；

最小误差率：与阈值 θ \theta θ和符号 p p p的选取息息相关的，当 p = 1 p=1 p=1时，某特征下特征值小于 θ \theta θ的全部样本将被预测成1，其余均为预测成0；类似地，当 p = − 1 p=-1 p=−1时，某特征下特征值大于 θ \theta θ的全部样本将被预测成1，其余均为预测成0；那么最小误差率，就是选取合适的 θ \theta θ和 p p p使某个特征下的误差率最小。

解决以上三个问题的整体思路：从众多特征中，选择最小误差率最小的特征作为该弱分类器的决策特征（而为保证最小误差率，阈值 θ \theta θ和符号 p p p已经确定）。

解决以上三个问题的步骤，即确定 G k ( x ) G_k(x) Gk(x)的步骤：

step1：遍历全部特征（值）

step2：得到全部样本该特征的最大值和最小值。选取一定的步长，让阈值 θ \theta θ从最大值变化到最小值，目的是观察每一种 θ \theta θ的选取得到的误差率

step3：判断符号 p p p是选1得到的误差率小还是选-1得到的误差率小

step4：记录最小误差率最小的特征，该特征将作为该弱分类器的决策特征，同时也要记录（更新）对应阈值 θ \theta θ和符号 p p p

很显然，step1、step2和step3对应着三层嵌套循环。

以下是一段训练弱分类器的代码以方便理解过程：

def buildStump(datMat,classLabels,D):
    dataMatrix = mat(datMat); labelMat = mat(classLabels).T
    m,n = shape(dataMatrix)
    numSteps = 10.0; # theta变化的步数
    bestStump = {}; # 保存该弱分类器对应的决策特征、阈值、符号
    bestClasEst = mat(zeros((m,1))) # 最终会保存训练好的弱分类器对全部样本的预测标签
    minError = inf #最小错误率初始化为无穷大
    for i in range(n): # 遍历全部特征
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max(); # 全部样本该特征的最大值与最小值
        stepSize = (rangeMax-rangeMin)/numSteps # 步长
        for j in range(-1,int(numSteps)+1): # 遍历阈值theta
            for inequal in ['lt', 'gt']:  # 遍历符号p
                threshVal = (rangeMin + float(j) * stepSize) # 当前遍历到的阈值
                
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) # 在第i个特征下，用当前遍历到的阈值theta和符号p，预测一下样本标签
                errArr = mat(ones((m,1)))
                errArr[predictedVals == labelMat] = 0 # 误判的都为1，正确的都为0
                weightedError = D.T*errArr  # 计算误差率，即误判的样本权重和
                
                if weightedError < minError: # 更新最小误差率
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst

haar-like 特征

虽然adaboost算法与harr-like特征会一起使用，但是二者是完全不同的方向，一种是分类算法，一种是特征提取算法。因此，将两部分完全分开讲解。

基本haar特征

Haar-like特征最早是由Papageorgiou等应用于人脸表示，Viola和Jones在此基础上，使用3种类型4种形式的特征。

Haar特征分为三类：边缘特征、线性特征、中心特征和对角线特征，组合成特征模板。特征模板内有白色和黑色两种矩形，并定义该模板的特征值为白色矩形像素和减去黑色矩形像素和。Haar特征值反映了图像的灰度变化情况。例如：脸部的一些特征能由矩形特征简单的描述，如：眼睛要比脸颊颜色要深，鼻梁两侧比鼻梁颜色要深，嘴巴比周围颜色要深等。但矩形特征只对一些简单的图形结构，如边缘、线段较敏感，所以只能描述特定走向（水平、垂直、对角）的结构。

对于图中的A, B和D这类特征，特征数值计算公式为： v = S u m 白 − S u m 黑 v=Sum_白-Sum_黑 v=Sum白−Sum黑，而对于C来说，计算公式如下： v = S u m 白 − 2 ∗ S u m 黑 v=Sum_白-2*Sum_黑 v=Sum白−2∗Sum黑；之所以将黑色区域像素和乘以2，是为了使两种矩形区域中像素数目一致。

通过改变特征模板的大小和位置，可在图像子窗口中穷举出大量的特征。上图的特征模板称为“特征原型”；特征原型在图像子窗口中扩展（平移伸缩）得到的特征称为“矩形特征”；矩形特征的值称为“特征值”。

扩展haar特征

Lienhart R．等对Haar-like矩形特征库作了进一步扩展，加入了旋转45°角的矩形特征。扩展后的特征大致分为4种类型：边缘特征、线特征环、中心环绕特征和对角线特征：

这些扩展特征主要增加了旋转性，能够提取到更丰富的边缘信息。

haar-like 特征计算

积分图计算

2001年，Viola阐述了利用积分图在相同的时间内，快速计算不同Haar特征值的问题，从而在很大程度上提高了检测速度。
第一步： 首先根据图像计算出积分图像：积分图像中任意一点的值都是原图像中该点左上方所有点的值的累加和。

第二步： 利用积分图可以快速计算图像中任意区域像素值的累加和，进而更快的求得矩形特征的特征值。

如：记区域A、B、C、D的像素和分别为 I A I_A IA、 I B I_B IB、 I C I_C IC、 I D I_D ID。

则有：
i i 1 = I 1 = I A i i 2 = I 2 = I A + I B i i 3 = I 3 = I A + I C i i 4 = I 4 = I A + I B + I C + I D ii_1=I_1=I_A \\\\ ii_2=I_2=I_A+I_B \\\\ ii_3=I_3=I_A+I_C \\\\ ii_4=I_4=I_A+I_B+I_C+I_D \\\\ ii1=I1=IAii2=I2=IA+IBii3=I3=IA+ICii4=I4=IA+IB+IC+ID
由上述的方程组得到区域D的像素和：
I D = I 4 + I 1 − ( I 2 + I 3 ) I_D=I_4+I_1-(I_2+I_3) ID=I4+I1−(I2+I3)
又如：记区域A、B的像素和分别为 I A I_A IA、 I B I_B IB。

I A = I 4 + I 1 − ( I 2 + I 3 ) I B = I 6 + I 3 − ( I 4 + I 5 ) I_A=I_4+I_1-(I_2+I_3) \\\\ I_B=I_6+I_3-(I_4+I_5) \\\\ IA=I4+I1−(I2+I3)IB=I6+I3−(I4+I5)
其特征值为：
I = I A − I B = ( I 4 − I 3 ) − ( I 2 − I 1 ) + ( I 4 − I 3 ) − ( I 6 − I 5 ) I=I_A-I_B=(I_4-I_3)-(I_2-I_1)+(I_4-I_3)-(I_6-I_5) I=IA−IB=(I4−I3)−(I2−I1)+(I4−I3)−(I6−I5)
所以，Haar特征值计算，只和端点的积分图有关，而与图像坐标值无关。在计算过程中，无论矩形特征尺度如何，计算所需时间是一定的。所以说积分图的引入提高了检测的速度。

级联分类器

级联分类器本质上并非只能应用于Adaboost算法中。

问题1：在实际应用中，由于Adaboost算法存在退化现象，导致随着弱分类器个数的增加，强分类器的分类能力反而会降低，所以需要对传统的Adaboost算法进行改进。

问题2：Adaboost在待检图像检测过程中，要对每一个位置的每一种尺寸的窗口进行检测，检测量极大；同时，在实际图片中，人脸区域只占整张图片的较小比例，检测时也会花大量的时间在这些无人脸区域上。

问题3：AdaBoost训练出来的强分类器一般具有较小的误识率，但检测率并不很高，一般情况下，高检测率会导致高误识率，这是强分类阈值的划分导致的，要提高强分类器的检测率既要降低阈值，要降低强分类器的误识率就要提高阈值，这是个矛盾的事情。

基于这些问题，人们提出了级联分类器的思想：

联合多个强分类器，对输入的大量子窗口图像，通过级联分类器中的每个强分类器一层一层地过滤掉非人脸的图像，最终留下人脸图像。在级联分类器的前几级构造小型、高效的强分类器用来滤除大量的负样本（非人脸），这样待检测的窗口会越来越少，再调用后面相对复杂的强分类器，达到较低的误检率，从而实现高效地识别。

**级联分类器需要注意的问题：**增加分类器个数可以在提高强分类器检测率的同时降低误识率，所以级联分类器在训练时要考虑如下平衡，一是弱分类器的个数和计算时间的平衡，二是强分类器检测率和误识率之间的平衡。

举个例子来说明为什么级联分类器可行：

级联分类器由若干个简单的AdaBoost分类器串接得来。假设AdaBoost分类器要实现99%的正确率，1%的误检率需要200维特征，而实现具有99.9%正确率和50%的误检率的AdaBoost分类器仅需要10维特征，那么通过级联，假设10级级联，最终得到的正确率和误检率分别为：
T P R = ( 0.999 ) 10 = 99.0 % F P R = ( 0.5 ) 10 = 0.1 % TPR=(0.999)^{10}=99.0\%\\\\ FPR = (0.5)^{10}=0.1\% TPR=(0.999)10=99.0%FPR=(0.5)10=0.1%
可以看到通过级联Adaboost分类器们能够使用较少的特征和较简单的分类器更快更好的实现分类。另外在检测的过程中，因为 T P R TPR TPR较高，所以一旦检测到某区域不是目标就可以直接停止后续检测，这样大部分检测窗口都能够很快停止，分类速度得到很大的提高。

训练过程：

这部分参考了许多资料都无法理解，这里附上多篇博客中的伪代码。

伪代码1：

	具体的训练过程如下：
	确定每级的最大误识率f，最小要达到的检测率d；
	最终级联分类器的误识率Ftarget；
	P=正样本
	N=负样本
	F0=1.0，D0=1.0
	i=0
	For Fi<Ftarget
		i=i+1
		ni=0；Fi=Fi-1
		For Fi < f*Fi-1
		    ni=ni+1
			利用Adaboost在P与N上训练出ni弱分类器
			权衡当前级联分类器的检出率Di与误检率Fi
			For 前级联分类器的检出率达到d*Di
				降低第i层的强分类器的阈值
				权衡当前级联分类器的检出率Di与误检率Fi
			End
		End
		N=0
		利用当前级联分类器检测负样本，将误识样本放入N
	End

伪代码2：