概论

统计学习由监督学习、无监督学习、半监督学习和强化学习组成

统计学习的三要素：模型、策略和算法

在本书中主要研究的是监督学习。

在监督学习中，输入和输出可能取值的集合称为输入空间和输出空间，每个输入是一个实例，由特征向量组成。符号表示如下：

$$ x=(x^{(1)},x^{(2)},…,x^{(i)},…,x^{(n)})^T $$

$$ x_i = (x_i^{(1)},x_i^{(2)},…,x_i^{(i)},…,x_i^{(n)})^T $$

注意两者的区别，前者是一个输入向量，后者指的是多个输入向量中的第i个，小写的"x"表示特征。对于输出向量同理，只是字母变成了“y”。

数据集的表示：

$$ T = {(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$$

监督学习的目的就是获得一个概率或非概率模型： $$P(X|Y) /y=f(x)$$

接下来依次分析统计学习的三要素：

模型

模型就是所要学习的条件概率或决策函数，但实际上，符合条件的模型并不是唯一的，而是存在一个假设空间，一般有无穷多个。符号表示如下： $$ \digamma = {f|Y=f(X)} $$ $$ \digamma = {P|P(Y|X)} $$

策略

策略是选择模型或学习的准则。对于预测的得到的结果，可能会与实际数据有所偏差，我们用一个损失函数来度量预测错误的程度，记作：$L(Y,f(X))$ 实际上，存在有多种损失函数用于使用，同时由于其不同的特点，应用场合和效果也会有所不同。

0-1损失函数 $$ L(Y,f(X)) = \begin{cases} 1,Y \neq f(X) \0,Y = f(X) \end{cases}$$ 平方损失函数 $$ L(Y,f(X)) = (Y-f(X))^2$$ 决定损失函数 $$ L(Y,f(X)) = |Y-f(x)|$$ 对数损失函数 $$ L(Y,P(Y|X)) = -logP(Y|X)$$

得到的损失函数，只能表示单一数据的评估，对于多组数据，我们利用损失函数的期望，即： $$ R_{exp}(f) = E_p[L(Y,f(X))] = \int_{x*y}L(y,f(x))P(x,y)dxdy $$ 这个公式的理解难度不大，但是问题来了，$P(x,y)$是x和y的联合分布，但是由于$P(x,y)$是未知的，所以求不出$R_{exp}$而如果知道$P(x,y)$，我们就能求得 $P(X|Y)$，显然出现了矛盾。

在这种情况下，我们不得不使用统计学的大法：经验风险(实际上就是令$P(x,y) = \frac{1}{N}$)： $$R_{emp}(f) = \frac{1}{N}\sum^N_{i=1}L(y_i,f(x_i)) $$

根据大数定律，当样本容量N趋近于无穷时$R_{emp}$近似于$R_{exp}$。

因而，只需求得最小的$R_{emp}$即可得到合适的模型，现实中最大似然估计就是经验风险最小化的一个体现。

为什么说最大似然估计是经验风险最小化的一个体现？ 最大似然估计我们在概率论的时候已经接触过了，即： $$L(\theta) = \prod_{i=1}^np(x;\theta) $$ 其思想就是找到一个参数使得损失函数最大。经验风险最小化也类似，只不过是找到参数使得其为最小值。

上述准则似乎可以满足一切问题，但是实际并非如此。当样本容量较小时，我们发现通过这种方式学习得到的模型会出现过拟合的问题。所以要存在另一个方法：结构风险： $$R_{srm}(f) = \frac{1}{N}\sum^N_{i=1}L(y_i,f(x_i))+\lambda J(f) $$ 我们可以清楚的看到，经验风险和结构风险两者之间其实并未存在较大的区别，相较于前者，后者增加了一个模型复杂度$J(f)$，$\lambda$是其中的系数用于权衡经验风险和模型复杂度。

通过上述的两个风险函数，我们将监督问题转换为了经验风险和结构风险函数的最优化问题。这时候两个函数是最优化的目标函数

算法

算法指的是学习模型的具体计算方法。这里算法主要解决的是最优化问题的解法，实际上最优解问题通常没有显示的解析解，且存在找不到全局最优解的问题。因而需要最优化算法。

模型评估

基于上述的风险函数，我们对模型进行评估。当损失函数给定的时候，训练误差和测试误差自然的就会成为学习方法评估的标准（这里有个细节，学习时采用的损失函数与评估时的损失函数未必相同）。

假设学习得到模型是$Y = \hat{f}(x)$，那么关于训练集和数据集的平均误差：

$$R_{emp}(\hat{f})=\frac{1}{N}\sum_{i=1}^NL(y_i,\hat{f}(x_i))$$

$$e_{test}=\frac{1}{N’}\sum_{i=1}^{N’}L(y_i,\hat{f}(x_i))$$

其中N和N’分别为训练样本容量和测试样本容量。然而，上述的评估方法只不过是其中的一个指标，显然，当$e_{test}$较小时模型比较好，存在的另一个东西叫做泛化能力。

用大白话讲，泛化就是通过训练得到的模型，在测试集上的效果如何。如果在训练集的效果上较好但是在测试集上不好，那就是过拟合问题，相反则是欠拟合问题。

训练误差与测试误差和模型复杂度的关系是容易理解的，对于训练误差，随着模型逐渐复杂，模型可以精准的传过每一个点，从而最终使得训练误差达到极小的情况，但是对于测试误差，在达到一定的复杂度时，测试误差会随着复杂度的增加而增加，从而弱化了泛化能力。

那么如何选择一个较为合适的复杂度，有两种方法：正则化、交叉验证

正则化

实际上，正则化的形式在结构风险函数中已经有所体现（貌似长得一样）。在正则化中也存在两种方法：L1正则和L2正则。两者就是在经验风险函数的末尾加上L1正则项和L2正则项。我们以线性回归为例，两种正则的形式如下：

$$ L(w) = \frac{1}{N}\sum ^N_{i=1}(f(x_i;w)-y_i)^2 +\frac{\lambda}{2}||w||^2 $$

$$ L(w) = \frac{1}{N}\sum ^N_{i=1}(f(x_i;w)-y_i)^2 +\lambda||w||_1 $$

前者是L2正则，后者是L1正则。这里回顾一下结构风险函数提出的意义，当输入实例较少时且模型过于复杂时，我们很容易就能得到一个较小的经验风险函数，但是显然是过拟合的，通过假如L1正则项，当复杂度较高时，会增大误差，从而降低拟合程度。

相关阅读：L1正则化和L2正则化

交叉验证

这是数据集中数据切分的方案：分别为简单交叉验证、S折交叉验证、留一交叉验证。

这部分内容不进行赘述。

泛化能力

从定义上来看，泛化能力指的是该方法学习到的模型对未知数据的预测能力。就从定义上来看，显然，如何最大化泛化能力才是学习的最终目的，那么这一概念与前文提到的内容是否冲突？泛化误差的形式如下：

$$R_{exp}(\hat{f}) = E_p[L(Y,\hat{f}(x))] = \int_{x*y}L(y,\hat{f}(x))P(x,y)dxdy $$

从形式上来看，泛化误差实际上就是模型的期望风险。对于泛化误差，我们通常比较泛化误差上界的大小来比较优劣。误差上界函数是关于样本容量的函数，容量越大，模型越难学，误差上界越大。

泛化误差上界定理：若从函数族$\digamma$中任选出函数$f$，至少有概率$1-\sigma$，使下列不等式成立：

$$R(f) \leq \hat{R}(f) + \epsilon(d,N,\sigma) $$

$$其中 \epsilon(d,N,\sigma) = \sqrt{\frac{1}{2N}(\log d + \log \frac{1}{\sigma})}$$

在上述不等式中，不等式左侧为泛化误差，右侧为上界。右侧的第一项是训练的误差，第二项是N的单调递减函数。

生成模型和判别模型

对于监督学习，就其模型学得的种类分为生成模型和判别模型。

前者主要是根据条件概率公式，在求得$P(X,Y)$之后利用条件概率公式即可。

判别模型这是直接生成决策函数$f(X)$或者$P(X|Y)$。

监督学习解决问题的种类

分类、标注、回归

三者解决的问题不同，过程也存在一定的差异，在此不多赘述。

感知机

感知机是一种二分类的线性分类模型。说起来可能比较抽象，我们先看看它的定义：

感知机：假设输入空间$\Chi \subseteq R^n$，输出空间是$Y = {+1,-1}$输入$x \in X$表示实力的特征向量，对应于输入控件的点：输出$y\in Y$表示实例的类别，由输入空间到输出空间的如下函数： $$f(x) = sign(\omega \cdot x+b)$$

称为感知机。其中$\omega$和$b$叫做感知机模型参数。$\omega$表示权值或权值向量，$b \in R$叫做偏置。$sign(x)$为符号函数，即:

$$sign(x) \begin{cases} +1,x\geq 0\-1,x<0 \end{cases}$$

如果对神经网络有所理解的话，这其实就是一个神经元。

通过上述的定义，我们暂且可以将一个感知机看作一个分类器，不同的数据进去可以得到1或-1。根据$\omega$的维度不同，$\omega \cdot x+b $是一个空间的超平面，将空间分为两类。

稍微有点知识就能知道，通过一组训练数据集，我们就可以拟合出一个较为合适的$\omega$和$b$

感知机学习策略

首先我们要知道数据集是否具有线性可分性的，这一点可以参见下图：

所谓的线性可分可见左边的图片，显然，我们可以通过一条直线将两类数据分开。对于右图线性不可分的情况，我们无法使用一条直线将两类数据分开。

那么假设现在一个数据集是线性可分的，那么感知机的目标是为了获得一个能将数据级完全分开的超平面。我们需要定义一个学习策略，根据我们在第一章中了解的。所谓策略，其实就是一个损失函数和一个风险函数的最小化，那么感知机的损失函数如何获取？

有两个思路，一是获取误分类点的个数，但是这样的问题是，总数并不是$\omega$和$b$的可导函数，没办法进行优化。因而我们使用另一个思路，获取误分类点道超平面的距离。

首先，对于任意一点$x_0$，该点到超平面的距离

$$\frac{1}{||\omega||}|\omega \cdot x_0+b|$$

其中$||\omega||$是$\omega$的$L_2$范数。

• $L_0$范数：非0元素的个数

• $L_1$范数：各个元素绝对值的和

• $L_2$范数：各个元素平方和的平方根

• 所谓范数，实际上可以理解为长度

对于误分类的数据，我们可以得到：

$$-y_i(\omega \cdot x_i +b) >0$$

这是由于误分类的点与期望分类的符号相反，所以两者之积应该小于0

所以误分类点到超平面的总距离：

$$\frac{1}{||\omega||}y_i(\omega \cdot x_0+b)$$

所有误分类点到超平面的总距离：

$$-\frac{1}{||\omega||}\sum_{x_i \in M}y_i(\omega \cdot x_0+b)$$

不考虑$\frac{1}{||\omega||}$就可以得到损失函数。

所以，对于感知机$sign(\omega \cdot x_i+b)$的损失函数：

$$L(\omega,b) = -\sum_{x_i \in M}y_i(\omega \cdot x_i+b)$$

其中M为误分类点的点集。

感知机学习算法

在获得了学习策略之后，我们要使用合适的算法对其进行迭代，即实现：

$$\min_{\omega,b}L(\omega , b) = -\sum_{x_i \in M}y_i(\omega \cdot x_i+b)$$

易得知，感知机学习的算法是误分类驱动的。在书中使用了随机梯度下降法。具体方案为，任选一个超平面$\omega_0$和$b_0$，一次随机选取一个误分类点，使其梯度下降。

那么损失函数的梯度：

$$\nabla_\omega L(\omega,b) = -\sum_{x_i \in M}y_ix_i$$

$$\nabla_\omega L(\omega,b) = -\sum_{x_i \in M}y_i$$

具体算法如下：

• 输入：训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中$x_i \in \Chi = R^n,y_i \in Y={-1,+1},i=1,2,…,N$；学习率$\eta(0<\eta\leq1);$

• 输出：$\omega,b$；感知机模型$f(x) = sign(\omega\cdot x+b)$

• (1)选取初值$\omega_0,b_0$

• (2)在训练集中选取数据$(x_i,y_i)$

• (3)如果$y_i(\omega \cdot x_i+b)\leq0$

  $$\omega\leftarrow\omega+\eta y_ix_i$$

  $$b \leftarrow b+\eta y_i$$

• (4)转至(2)直至训练集中没有误分类点。

整个过程并非十分困难，可以参考P30页的例子。

上述的学习算法是感知机学习算法的原始形式，既然如此，那么实际上确实还有一种形式，叫对偶形式。

相较于原始形式，对偶形式的基本想法是将$\omega$和$b$表示为x和y的线性组合形式，通过求解系数从而获得$\omega$和$b$的值（这里应该用到了线性代数的思想）

算法如下：

• 输入：训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中$x_i \in \Chi = R^n,y_i \in Y={-1,+1},i=1,2,…,N$；学习率$\eta(0<\eta\leq1);$

• 输出：$\alpha,b$；感知机模型$f(x) = sign(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b)$其中$\alpha = (\alpha_1,\alpha_2,…,\alpha_N)^T$

• (1)$\alpha \leftarrow 0 ,b \leftarrow 0$

• (2)在训练集中选取数据$(x_i,y_i)$

• (3)如果$y_i(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b)\leq0$

  $$\alpha_i\leftarrow\alpha_i+\eta$$

  $$b \leftarrow b+\eta y_i$$

• (4)转至(2)直至训练集中没有误分类点。

对偶形式中的训练实例仅以内积的形式出现，为了方便，可以预先将训练集中的实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵：

$$ G = [x_i \cdot x_j]_{N*N} $$

学习算法的收敛性

感知机学习算法的收敛性是指通过有限的迭代，可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型

如何证明感知机的学习算法具有收敛性。我们令$\hat{\omega}=(\omega^T,b)^T $，同时为输入向量扩充加入常数1，得到$\hat{x} = (x^T,1)^T$可以知道，$\hat{\omega} \cdot \hat{x} = \omega \cdot x +b$

那么存在定理（Novikoff定理）

• 存在满足条件的的$||\hat{\omega}{opt}||=1$的超平面$\hat{\omega}{opt} \cdot \hat{x} = \omega_{opt} \cdot x +b_{opt}=0$将训练数据集完全正确分开；且存在$\gamma >0$，对所有的$i=1,2,…,N$

  $$y_i(\hat{\omega}{opt} \cdot \hat{x}) =y_i( \omega{opt} \cdot x +b_{opt})\geq \gamma$$

• 令$R=max_{1\leq i\leq N}||\hat{x}_i||$，则感知机算法在训练集上无分类次数k满足不等式：

  $$k \leq (\frac{R}{\gamma})^2$$

由于证明过程较为繁杂，在这里不进行一步一步的列举。详见后文证明。

k近邻法

k近邻法的输入为实例的特征向量，输出为类别，且可以取多类。实际上其是将特征向量空间进行一个划分作为模型。相较于感知机，k近邻法的三个基本要素是：k值的选择、距离度量和分类决策规则。

k近邻算法

实际上，k近邻算法并不难理解。

• 输入：训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中，$x_i\in\Chi \subseteq R^n $为实例的特征向量，$y_i \in Y = {c_1,c_2,…,c_K} $为实例的类别，$i=1,2,…,N$;

• 输出：实例x所属的类y

  • (1)根据给定的距离度量，在训练集T中中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作$N_k(x)$；

  • (2)在$N_k(x)$根据分类决策规则决定x的类别y：$$y = argmax_{c_j}\sum_{x_i \in N_k(x)}I(y_i = c_j),i=1,2,…,N;j=1,2,…,K$$

    其中$I$为指示函数

下面这张图可以帮助你直观的理解k邻近法的模型：

接下来基于三要素对k近邻模型进行一个分析

距离度量

说到距离，我们通常使用平方和的平方根作为距离，我们一般将其称为欧氏距离。我们使用一个$L_p$距离来表示更一般的情况。

因为懒得写很多集合和维度的数据，设特征空间中存在两个实例$x_i,x_j$，那么两者的$L_P$距离定义为：

$$L_p(x_i,x_j) = (\sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$$

我们很容易就能看出来，当p=2时就是我们常用的两点距离公式，即欧氏距离。

当p=1时为曼哈顿距离，当$p=\infin$时各个坐标距离的最大值。$L_p$距离间的关系如下图：

从这这张图可以直观的了解p对决策的影响，p的取值不同会使一个点的最近点集不同。

k值的选择

k值的选择同样会产生较大的影响。所谓k值，就是根据距离量度得出距离该点最近的前k的点。显然，当k=N时只会被归为一类，通常，我们会取一个较小的数值，并使用交叉验证来选取最优的k值。

分类决策规则

k近邻法通常使用多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

多数表决的规则如下：假设现在的损失函数是0-1损失函数，那么误分类的概率就是：

$$P(Y \neq f(X)) = 1 - P(Y=f(X))$$

对给定的实例$x\in \Chi$，其最近邻的k个训练实例点构成集合$N_k(x)$。如果涵盖**N_k(x)**的取余类别是$c_j$，那么误分类率是：

$$\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i \neq c_j) = 1 - \frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i = c_j)$$

显然，如果想降低误分类率，我们要尽可能提高$\sum_{x_i\in N_k(x)}I(y_i = c_j)$。因而多数表决规则等价于经验风险最小化。

k近邻法的实现：kd树

与其使用线性的计算来获得距离，建议使用特殊的结构来存储训练数据。kd树就是其中一种。

构造kd树的过程是一个递归的过程，算法如下：

• 输入：k维空间数据集$T = {x_1,x_2,…,x_N},$其中$x_i = {x_i^{(1)},x_i^{(2)},…,x_i^{(k)}}^T,i=1,2,…N$

• 输出：kd树

  • 开始时构造根节点。选择$x^{(1)}$为坐标轴，以T中所有实例的$x^{(1)}$坐标的中位数为切分点，将根节点对应的区域分成两个区域。

    之后，由根节点生成深度为1的左右自己欸但，分别表示小于切分点的子区域和大于切分点的子区域，并将落在切分超平面上的实例点保存在根节点。

  • 递归：对于深度为j的结点，选择$x^{(l)}$为切分的坐标轴，切分，划分…

  • 知道两个子区域没有实例时停止。

造树并不是目的，我们的最终目的是找结点的最近邻，因而对应的kd树最近邻搜索：

• 输入：已构造的kd树；目标点x；
• 输出：x的最近邻
  • 在kd树中找考汉目标点x的叶子结点：从根节点出发，递归的向下访问到kd树。若目标点x当前位的坐标小于切分点的坐标，就坐椅，否则有意，直到子节点。
  • 那么该子节点就是x的“当前最近点”
  • 递归回退，对每个结点都进行如下操作：
    • 如果该节点的实例点比当前最近点距离目标点更近，就医该实例点为“当前最近点
    • 当前最近点一定存在于该节点的一个子结点对应的取余。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心，到当前最近点距离为半径的超球体相交。如果想叫，移动到另一个子结点，接着递归。否则，向上回退。
  • 当回退到根节点时搜索结束。最后的“当前最近点”即为x的最近邻点。

    

朴素贝叶斯法

说到这个东西，其实是一个非常基础的东西：条件概率。这个东西主要是用于分类的，理解很多简单。

朴素贝叶斯的学习和分类

现在有n个特征的N个数据和K类，我们要做的就是利用训练数据，获得一个联合概率分布，即$$P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_k)$$

这个东西不难理解。那么对于上述如此的数据，到底会有多少个参数（离散概率分布）呢？不妨计算一下，首先y可以分为K类，假设对于每个x，每个维度（属性）都有$S_j$个取值，呢么参数的个数就是他们相乘：$K\prod_{j=1}^nS_j$

当然，我们是学过概率论的，朴素贝叶斯法对条件概率分布做了条件独立性的假设。优点是让这种算法的逻辑十分简单，但是缺点就是，当属性之间存在关系是，分类效果会很差。这是后话。这个假设表示出来长这样：$$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_k)=\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)$$

在进行统计学习算法的学习时，我们都是根据想要的结果进行算法的推导，对于朴素贝叶斯，器分类器表示为：$$y=f(x)=argmax_{c_k}\frac{P(Y=c_k)\prod_jP(X^{(j)}|Y=c_k)}{\sum_kP(Y=c_k)\prod_jP(X^{(j)}|Y=c_k)}$$

看上去很复杂，实际上是这样的：$$P(Y|X) = \frac{P(Y)\prod_{i=1}^NP(X_i|Y)}{P(X)}$$

也就是说，我们最后要获得一个概率表，这样理解起来确实不难吧。贝叶斯算法的原理是以比较复杂的推导过程，会写到最后的证明部分。

朴素贝叶斯如何学习

这一部分更为科学的说法是：朴素贝叶斯法的参数估计，实际上就是获得每个离散点的条件概率，这里我们使用最大似然估计法。那么条件概率的最大似然估计是：

$$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum^N_{i=1}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum^N_{i=1}I(y_i=c_k)}$$

但是在计算条件概率的时候，我们还需要使用$Y=c_k$的概率，它的计算方法也十分容易：

$$P(Y=c_k)=\frac{\sum^N_{i=1}I(y_i=c_k)}{N}$$

之所以这么简单是因为这里的损失为0-1损失函数，更复杂的不多说明，可能也用不到。

那么确定实例x的类：

$$y = argmax_{c_k}P(Y=c_k)\prod_{j=1}^nP(X^{(j)}=x(j)|Y=c_k)$$

贝叶斯估计

显然，上述最大似然估计会出现概率为0的情况，当然，解决方案也很简单——采用贝叶斯估计

$$P_\lambda(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}$$

至于剩下的内容，就与朴素贝叶斯一样了。

至此，看起来复杂的贝叶斯就算理解了。

决策树

与朴素贝叶斯相反，这个东西看上去简单，实际上并不简单。通过代码我们可以很容易的生成一棵决策树，但是其实现原理有两个重点：特征的选择和剪枝。

前置任务

为了方便我们后续的理解，先简述一些内容。

决策树模型：是一种树形结构，其实有点类似朴素贝叶斯，但是与之最大的不同是，朴素贝叶斯实际上是解决离散的数据分类，无法解决连续的特征数据分类，二决策树可以通过划分一个范围来解决这个问题。

叶节点，样本点：这两个东西虽然都是模型末端的东西，可以见下图：

在这个图片中，叶节点有三个，但是类别只有两个。在叶节点之下的ABCDEFG即为样本点。还有一点要注意的是，虽然ABCD最后都是百万富翁，但是其判断的路径是不同的。

那么接下来就正式开始。

信息增益

这里涉及到了熵的概念，熵是表示速记变量不确定性的度量，当然，在之前的一篇文章中我较为详细的说明了熵的概念，可以移步到那篇文章。

对于有n个特征数的随机变量X，其熵的定义为：

$$H(X) = -\sum^n_{i=1}p_ilogp_i$$

由于熵依赖的是X的分布而非X的取值，因而式子其实也可以改为：

$$H(p) = -\sum^n_{i=1}p_ilogp_i$$

通过上述决策树模型的例子，我们看得出来，CD成为百万富翁，其实是在资金流小于100万的情况下成为百万富翁，所以存在这着一个条件概率。所以有一个条件熵的概率$H(Y|X)$表示在抑制随机变量X的条件下Y的不确定性，定义为X在给定条件下Y的条件概率分布的熵对X的数学期望（两种表述一个意思）：

$$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$$

当我们通过数据集得到熵和条件熵时，此时他们称作经验熵和条件经验熵。

决策树生成核心的地方是如何选择特征作为划分的条件，从直觉上来说，我们肯定会选择类别之间差距较大的特征作为顶层的分类条件。事实上，决策树也确实是这样进行决策选择的。那么如何表示“类别之间差距较大的特征”这一东西？我们使用信息增益：

所谓信息增益，就是得知特征X的信息而使得类Y的信息的不确定性减少的程度。现有特征A对训练集的D的信息增益$g(D,A)$，定义为集合D的经验熵$H(D)$与特征A在给定条件下D的经验条件熵$H(D|A)$之差：

$$g(D,A)=H(D)-H(D|A)$$

如何根据数据集进行不同特征的信息增益，如下：

• 设训练数据集为D，$|D|$表示其样本容量。现设K个类$C_k$，$k=1,2,…,K$,$|C_k|$为属于类$C_k$的样本个数，$\sum_{k=1}^K|C_k| = |D|$。设A有n个不同的取值${a_1,a_2,…,a_n}$，根据特征A的取值将D划分为n个子集$D_1,D_2,…,D_n$，同样有$\sum_{i=1}^n|D_i|=|D|$记自己$D_i$中属于类$C_k$的样本的集合为$D_{ik}$，$|D_{ik}|$那么信息增益分三步计算。

• 首先计算D的经验熵：

  $$H(D)=-\sum_{k=1}^K \frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$

• 其次计算特征A对数据集D的经验条件熵:

  $$H(D|A) = \sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$$

• 最后进行信息增益的计算：

  $$g(D,A)=H(D)-H(D|A)$$

信息增益值是相对于训练数据集的，没有绝对意义，分类越困难，信息增益会越大。为了校正，我们可以使用信息增益比：

$$g_R(D,A) = \frac{g(D,A)}{H(D)}$$

决策树的生成

如果我们只得到了每一层需要进行分类的特征，那么我们最后得到的实际上会是一个完全二叉树，会将每一个类型都分类，显然这样是没有意义的，也就是说存在一个递归停止的条件：即对分类影响不大的特征，这里叫他阈值。

所以综合上述的内容，我们可以生成一棵决策树。根据特征的信息增益方式不同，决策树的生辰也有不同的算法。

ID3算法是直接使用信息增益进行树生成的算法，当信息增益值大于阈值时，会以此结点为根节点生成两个（或多个）子结点，之后将满足不同子结点条件的样本分配至子结点，若小于阈值，则将其作为根节点。

C4.5算法则是使用信息增益比来进行结点划分的条件，同样也存在一个阈值。由于对其做了D的经验熵的除，不仅进行了归一，同时也可以减弱ID3算法出现过拟合的情况。

就像最开始说的，如果不分配阈值或者阈值分配过小，那么很容易就会生成大量的结点，从而导致过拟合，同时ID3算法只是做差也难得到一个标准，即使时C4.5也存在过拟合的情况。为什么，原因有二，当存在噪声且该噪声被分配到样例数量较小的类别是，该噪声就会为该分支开辟一个新的分支。其次，即使不存在噪声，当较少的样本被分到一个分支时，如果他们中的大部分表现出了惊人的规律，使得一些属性恰巧可以很好地分割样例，同样会出现过拟合。所以总结一下，就是样例较少的分支，容易由于部分数据差别较大而开辟新的分支从而过拟合。

对于为了减少过拟合，使生成树分类效果更加，我们有两种方法：树的剪枝和CART树

树的剪枝

从上文我们知道分支多的树会过拟合，那很简单，我们只需要减去一些会导致过拟合的分支即可，也就是说这是个优化问题，我们需要一个优化函数（在此我们叫他损失函数吧）

我们假设树T的结点个数为$|T|$，t是树T的叶结点，该结点有$N_t$个样本点，其中k类的样本点有$N_{tk}$个，$H_t(T)$为叶节点t上的经验熵，$\alpha\geq0$为承诺书，那么决策树学习的损失函数为：

$$C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$$

我们可以令：

$$C(T) = \sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}$$

所以就可以得到：

$$C_\alpha(T)=C(T)+\alpha|T|$$

这个东西有点眼熟是吧，其实它第一次出现在概论里面，就是加了结构风险的损失函数。

既然有了损失函数，我们就要使用一些方法来减小损失函数，算法如下：

• 计算每个结点的经验熵
• 递归的从树的叶结点向上回缩，如果会所之后得到的损失是函数下降，就进行剪枝，直至得到损失函数最小的子树。

CART算法

CART算法叫做分类与回归树，是我们现在使用比较广泛的一种决策树算法，是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。假设决策树是二叉树，内部结点的特征取值为“是”和“否”。算法如下：

• 基于数据集生成尽可能大的决策树
• 剪枝

从CART的名字我们可以看出来，其实际上分为两部分，分别为分类树和回归树，分类树的功能就是分类，回归树的功能是拟合，更加细节的内容可以自己查阅相关博文。

决策树的生成就是递归的构建二叉决策树的过程，其中，对于回归树，我们使用平方误差最小化准则，对于分类树，我们使用基尼指数最小化。接下来就是两种树的生成算法和剪枝算法。

回归树的生成算法

回归树最后的结果是一个回归函数，但是由于决策树的性质，实际上得到的结果是有限的。回归树的模型可以表示为：

$$f(x)=\sum^M_{m=1}c_mI(x\in R_m)$$

当划分确定时，我们使用平方误差来表示误差，那么我们很容易得知，单元$R_m$上的最优值$\hat{c}_m$就是输入实例$x_i$对应的输出$y_i$的均值。即：

$$\hat{c}_m=ave(y_i|x_i\in R_m)$$

那么该如何进行决策树的划分。这里采用的是启发式的方法，选择第j个变量$x^{(j)}$和它的取值s，作为切分向量和切分点，并定义两个区域：$$R_1(j,s)={x|x^{(j)}\leq s}和R_2(j,s)={x|x^{(j)} > s}$$

所以使用最小二乘回归树生成的算法：

然后寻找最优切分变量j和最优切分点s，具体的算法如下：

• (1)选择最优切分变量j和切分点s，求解：

$$min_{j,s}[min_{c_1}\sum_{x\in R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x\in R_2(j,s)}(y_i-c_2)^2]$$

需要遍历变量j，对固定的划分变量j扫描划分s。

• (2)优选定的对(j,s)划分区域并决定相应的输出值。

$$R_1(j,s)={x|x^{(j)}\leq s}和R_2(j,s)={x|x^{(j)} > s}$$

$$\hat{c}m=\frac{1}{N_m}\sum{x_i\in R_m(j,s)}y_i,x\in R_m,m=1,2$$

• 反复进行上述不走，直至满足停止条件。

• 生成决策树：

  $$f(x)=\sum^M_{m=1}c_mI(x\in R_m)$$

分类树的生成

分类树使用基尼指数选择最优特征，同时决定该特征的队友二值切分点。所以我们先了解一下基尼指数是什么：

• 假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为：

  $$Gini(p) = \sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$

  所以，对于给定的样本集合D，其基尼指数为：

  $$Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2$$

  如果样本集合D根据特征A是否取某一可能值a被分割成$D_1$和$D_2$两部分，即

  $$D_1 = {(x,y)\in D|A(x)=a}，D_2=D-D_1$$

  那么在特征A的情况下，集合D的基尼指数为：

  $$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

从基尼指数关于集合D的公式，我们不难看出其表示的是集合D经A分割后集合D的不确定性，其实是有点类似熵的。

那么二叉决策树的生成方法：

• 计算现有特征对数据集的基尼指数，同时对于每一个特征A，对其可能取的两个值a，根据样本点对A=a的测试分成两部分，并计算A=a时的基尼指数。

• 在上述得到的A特征和切分点中，选择基尼指数最小的特征及其对应切分点作为最优特征与最优切分点。

• 递归的对子结点进行上述的运算，直至满足停止条件。

  CART剪枝

从整体树$T_0$开始剪枝，对$T_0$的任意内部结点t，以t为单结点树的损失函数：

$$C_\alpha(t)=C(t)+\alpha$$

以t为根结点的子树$T_t$的损失函数为：

$$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$$

显然，$\alpha$充分小时，有不等式：

$$C_\alpha(T_t)<C_\alpha(t)$$

所以我们只要找到某一时刻的$\alpha$使得式子左右两边相等。

当$\alpha$继续增大时，我们将式子反向，可以得到$\alpha = \frac{C(t)-C(T_t)}{|T_t|-1}$，此时说明两个树有相同的损失函数值。而t的结点更少，因而取t，对$T_t$剪枝。

获得不同的子树序列后，我们使用独立的验证序列集（交叉验证法）来选取最优子树。

综上所述，CART的剪枝算法如下：

• (1)令$\alpha = \infin$,$k=0$,$T=T_0$

• (2)计算$C(T_t)$,$|T_t|$以及:

  $$g(t) = \frac{C(t)-C(T_t)}{|T_t|-1}$$

  $$\alpha = min(\alpha,g(t))$$

• (3)自下而上的访问树的内部节点t。如果有$g(t)=\alpha$则对其进行剪枝，并对叶节点t以多数表决法决定其类。

• (4)令k=k+1,$\alpha_k=\alpha$,$T_k=T$

• (5)如果T不是根节点组成的树，返回第3步

• 采用交叉烟瘴发在子树序列$T_0,T_1,…,T_n$中选取最优子树$T_\alpha$

逻辑斯谛回归与最大熵模型

在之前的内容，我们了解到了最大熵作为概率模型学习的一个准则。最大熵模型属于对数线性模型，另一个是逻辑斯谛回归模型，这两个内容也是接下来需要讲解的。

逻辑斯谛回归模型

首先，我觉得有必要说明一下为什么又逻辑斯谛回归。第二章的时候我们接触到了感知机，但是感知机十分的弱鸡，只能进行-1和1的选择，两个结果的差距很大，同时感知机的函数在0点处无法微分，基于上述原因，有必要提出逻辑斯蒂芬必得函数。

逻辑斯谛分布的定义如下：设X是连续随机变量，X服从逻辑斯蒂分布是指X具有下列分布函数和密度函数：

$$F(x)=P(X\leq x)=\frac{1}{1+e^{x-\mu/\gamma}}$$

$$f(x)=F’(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}$$

其中$\mu$为位置参数，$\gamma>0$为形状参数。

接下来看看对应的二项逻辑斯蒂回归模型，作为一种分类模型，我们使用条件概率分布来表示：

$$P(Y=1|x)=\frac{exp(\omega \cdot x +b)}{1+exp(\omega \cdot x+b)}$$

$$P(Y=0|x)=\frac{1}{1+exp(\omega \cdot x+b)}$$

看上去复杂，我们可以这样理解，首先，概率的范围是一个0~1的区间，所以需要归一化，同时其还得有指数的特征，因而就可以得到这个东西。

那么继续，接下来是一个叫做几率的概念，这个东西是指事件发生的概率和该事件不发生的概率的比值，综合上面的两个式子，可以这样推导：

$$logit(p)= log\frac{p}{1-p}=w \cdot x$$

综上所述，不难得知，逻辑斯谛回归模型破除了传统的感知机的限制，而是可以扩宽到极大的定义域和值域。我们不难分析出，线性函数$w \cdot x +b$的值越大，条件概率就越接近1（而不是像感知机一样草率的将结果等于1）。

模型参数估计

我们大致得知了模型长什么样，显然接下来就是使用数据来获取较好的模型参数。即参数估计。在此，我们仍然使用（对数）似然函数来进行模型参数的估计。

我们首先设：$$P(Y=1|x)=\pi(x) \space P(Y=0|x)=1- \pi(x)$$

那么对数似然函数就是：

$$\begin{aligned}L(w)&=log(\prod^N_{i=1}[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{}1-y_i)\&=\sum^N_{i=1}[y_i log\pi(x_i)+(1-y_i)log(1-\pi(x_i))]\&=\sum^N_{i=1}[y_ilog\frac{\pi(x_i)}{1-\pi(x_i)}+log(1-\pi(x_i))]\&=\sum^N_{i=1}[y_i(w \cdot x_i)-log(1+exp(w \cdot x_i)]\end{aligned}$$

只需要求$L(w)$的最大值即可获得到对应的$w$的估计值。

多项逻辑斯谛回归模型

这里就稍微提一下。

$$P(Y=k|x)=\frac{exp(w_k\cdot x)}{1+\sum_{k=1}^{k-1}exp(w_k \cdot x)},k=1,2,..,K-1$$

$$P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{k-1}exp(w_k \cdot x)}$$

最大熵模型

与逻辑斯谛类似，最大熵模型认为学习概率模型时熵最大的模型是最好的模型。很容易理解，当事件等概率分布的时候熵显然是最大的，也正是因为如此，实际的学习过程中会存在一些约束条件，来限制轻而易举的等可能来实现最大熵。同时，为了转化约束问题为非约束问题，还会使用到拉格朗日乘子法。

通过训练集，我们可以知道每种特征样本的数量占所有样本的比例以及某一类样本占所有样本的体积，即：

$$\widetilde{P}(X=x,Y=y)=\frac{v(X=x,Y=y)}{N}$$以及$$\widetilde{P}(X=x)=\frac{v(X=x)}{N}$$

在知道上述内容之后，我们就可以得到期望值：

$$E_{\widetilde P}(f) = \sum_{x,y}\widetilde{P}(x,y)f(x,y)$$

但我们要得到的是$$P(X|Y)$$，因而我们可以得到有关该条件概率的模型：

$$E_P(f)=\sum_{x,y}\widetilde P(x)P(y|x)f(x,y)$$

按道理说，我们只需要让两个期望值相等即可，事实也确实是这样的，为什么要让两个期望值相等呢？实际上，如果我们已经知道了类别和特征，那么默认均分的情况是熵最大，那么现在给定了数据集，实际上这些数据集就是约束条件，也就是说，上述的两个期望值实际是约束条件。

那么，假设满足所有约束条件的模型集合是：

$$C = {p\in P | E_P(f_i)=E_{\widetilde {p}}(f_i),i=1,2,…,n}$$

定义在条件概率分布$P(Y|X)$上的条件熵为

$$H(P)=-\sum_{x,y}\widetilde P(x)P(y|x)logP(y|x)$$

那么问题就变成了满足约束条件下的最大化$H(P)$问题。

但是我们并不善于解决这种问题，所以我们还是使用拉格朗日乘子法，通过引进拉格朗日乘子$w_0,w_1,…,w_n$，定义拉格朗日函数：

$$L(P,w) = -H(P) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^nw_i(E_{\widetilde P}(f_i)-E_P(f_i))$$

我们需要解决的就是：

$$max_wmin_{P \in C}L(P,w)$$

令其对$P(y|x)$的偏导数为0，可以得到

$$P(y|x) = \frac{exp(\sum^n_{i=1}w_if_i(x,y))}{exp(1-w_0)}$$

我们再定义一个规范化因子$Z_w(x)$，其公式为:

$$Z_w = \sum_yexp(\sum_{i=1}^nw_if_i(x,y))$$

那么上式就可以化解为：

$$P_w(y|x) = \frac{1}{Z_w(x)}exp(\sum_{i=1}^nw_if_i(x,y))$$

所以我们现在只需要最大化上式即可，可是问题来了，这个参数应该怎么学习？

这里就要提到两种方法：改进的迭代尺度法和拟牛顿法。

这两种方法在此不多说明，有兴趣的可以看看这篇博文：https://zhuanlan.zhihu.com/p/43727726

支持向量机

线性可分支持向量机和硬间隔最大化

不得不说，这是一种非常厉害的方法，但同时难度也较为大。其思想是这样的，对于一个平面数据，假设其不能被线性可分，那么就没办法了吗？SVM提供了一个升维的方法，将平面数据映射到三维乃至更高维，则必然存在一个维度有超平面可以将两者完全分开。

不难得出，对于线性可分的支持向量机，若为二分类，我们可以获得对应的分离超平面：

$$\omega^* \cdot x + b^* = 0$$

以及对应的分类决策函数。

从图中是不难看出，两侧分别是进行的二分类，此外，我们还可以用点距离超平面的远近来表示预测的确信度。这时候就要提出两个概念：函数间隔和几何间隔。

与我们求点到直线的距离有所不同，函数间隔需要在距离的基础上乘上结果自身，即： $$\hat\gamma_i = y_i(\omega \cdot x_i + b )$$

为什么要可以乘上一个$y_i$？对于已知的x和y，我们通过$\omega \cdot x_i + b$得到的是一个预测的$y_i$，所以实际上函数间隔就是预测的结果与实际结果的乘积。这样做的意义是为了确保符号。可想而知，当预测的结果与实际结果的不同时，该乘积为负数。使用函数间隔可以表示分类预测的正确性和确信度。

但是出现了一个非常有趣的问题，当我们成比例的修改$\omega$和$b$时，我们发现超平面并未发生改变，但是函数间隔却变成了两倍。所以我们引出了几何间隔：

$$\gamma_i = \frac{\omega}{||\omega||} \cdot x_i + \frac{b}{||\omega||}$$

其中的$||\omega||$是$\omega$的$L_2$范数。

对于一群线性可分的点集，超平面并非只有一个，但是我们要从中获得间隔最大的超平面。其意义为不仅将正负实例分开，同时又能有足够大的确信度。对于获取最大间隔平面，我们可以将其转化为约束最优化问题：

$$max_{\omega,b} \quad \gamma$$

$$s.t. \qquad y_i(\frac{\omega}{||\omega||} \cdot x_i + \frac{b}{||\omega||} )\geq\gamma,\quad i=1,2,…,N$$

通过使用几何间隔取代函数间隔：

$$max_{\omega,b} \quad \frac{\hat\gamma}{||\omega||}$$

$$s.t. \qquad y_i(\omega\cdot x_i +b )\geq\hat\gamma,\quad i=1,2,…,N$$

将问题转换为对应的等价问题：

$$min_{\omega,b} \quad \frac{1}{2}||\omega||^2$$

$$s.t. \qquad y_i(\omega\cdot x_i +b )-1\geq 0,\quad i=1,2,…,N$$

通过上述的操作，我们成功的构建了支持向量机和对应的学习算法。但是我们发现了一个问题，支持向量这个给概念究竟是哪里提出的？

支持向量和间隔边界

支持向量是指在线性可分情况下，训练数据集的样本点中与分离超平面最近的样本点的实例称为支持向量。即：

$$y_i(\omega \cdot x_i + b ) -(+) 1 = 0$$

如下图：

对于求解最大间隔问题，我们同样可以将其转化为对偶问题，同样使用拉格朗日乘子法。

不难构造出拉格朗日函数：

$$L(\omega , b , \alpha) = \frac{1}{2}||\omega||^2 - \sum_{i=1}^N\alpha_iy_i(\omega \cdot x_i +b)+ \sum_{i=1}^N\alpha_i$$

其中$\alpha = (\alpha_1,\alpha_2,…,\alpha_N)^T$

所以现在要解决的问题就是：

$$\max_\alpha\min_{\omega,b}L(\omega,b,\alpha)$$

推导过程过于生草，放在一些证明里参考。

最后，我们的分离超平面可以写成：

$$\sum_{i=1}^N\alpha_i^y_i(x \cdot x_i)+b^ = 0$$

从上式，我们可以看到分类决策函数的只依赖于输入$x$和训练样本输入的内积。

线性支持向量机与软间隔最大化

当我们喜滋滋的使用支持向量机进行类别的划分时，我们发现了一个bug，对于一些线性不可分的点集，我们没办法直接用当前的支持向量机，为了解决这种问题，我们首先使用这样的方法，软间隔最大化，什么意思呢？就是排除一些特异点后大部分样本点组成的集合是线性可分的即可。

实际上就是引进一个松弛变量$\xi_i \geq 0$使得：

$$y_i(\omega \cdot x_i +b )\geq 1-\xi_i$$

单是这样还不行，我们的目标函数也得因此发生变化：

$$\frac{1}{2}||\omega||^2 + C\sum_{i=1}^N\xi_i$$

对于软间隔最大化的支持向量机使用和前面支持向量机相同的学习算法，因而不多花篇幅进行推导。我们的重点不是这个方法，具体的话可以参考这篇博客：https://www.cnblogs.com/simpleDi/p/10230477.html

非线性支持向量机与核函数

对于非线性的问题，我们还可以考虑变换空间来升维的方法来进行解决，如下图：

显而易见的是，我们无法使用一条直线将左图的点集划分好，所以这就变成了非线性问题，但是由于非线性的问题并不容易求解，我们能否使用解线性分类的问题解决上述问题？

这里，我们对原空间进行一个映射，得到右图的点集。具体的操作：定义一个映射：

$$z=\phi(x)=((x^{(1)})^2,(x^{(2)})^2)$$

所以原空间的椭圆就会变成直线。

通过上述的例子，我们可以看到，我们可以通过一个变换将原空间的数据映射到新空间，之后在进行线性分类，这就是核技巧

我们对核函数的定义如下：设$\Chi$是输入控件，又设$\Eta$为特征空间，如果存在一个从$\Chi$到$\Eta$的映射:

$$\phi(x):\Chi \rightarrow\Eta$$

使得对于所有的$x,z\in\Chi$，函数满足条件：

$$K(x,z)=\phi(x)\cdot\phi(z)$$

则称$K(x,z)$为核函数，$\phi(x)$为映射函数，运算为两者内积。

这里可能会产生混淆，核函数不是一种特别复杂的东西，我们不难发现，我们可以通过映射将低维的数据映射到高维，如

$$\phi(x_1,y_1) = (x_1,\sqrt{2}x_1y_1,y_1)$$

那么

$$<\phi(x_1,y_1),\phi(x_2,y_2)> = (x_1y_1,x_2y_2)^2 $$

说到底，核函数就是一个计算公式，说明转化为高维后的点积等于低维的点集（我暂且将其理解为维度混合带来了其他特征被提取）。

那么在支持向量机中一些复杂的内积，我们就可以使用核函数来进行代替（这里带入了拉格朗日乘子后的函数）：

$$W(\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$$

书中使用了较大的篇幅说明正定核的性质，即如何确定一个函数为核函数，在此不多赘述。

那么常用的核函数有多项式核函数，高斯核函数等，对于核函数的详解可以参考这篇文章：https://blog.csdn.net/mengjizhiyou/article/details/103437423

序列最小最优化算法(SMO)

这是一个快速支持向量机学习算法。

在这一章并没有具体的列出学习算法（在最后一章有提到），我们所需要学习的对象为$\alpha_i和\alpha_j$当数据量大起来的时候，这两个参数量也会增加，那么如何求解多个参数最优解呢？

我们首先需要知道一个和SMO类似的坐标上升算法。

坐标上升算法每次更新多元函数中的一维，多次迭代直到收敛来实现优化。

即，对于一个二元函数$argmax_{x_1,x_2}f(x_1,x_2)=-x_1^2-3x_2^2+2x_1x_2+6$

我们首先对$x_1$固定，对$x_2$求偏导，之后反过来。再进行过一轮之后继续上述操作，直至收敛。

那么对于支持向量机，我们需要进行$\alpha_1,…\alpha_N$的优化。每次优化，我们选出两个参数进行优化，具体的流程同样见最后的证明。

除了优化的过程，如何选择两个参数进行优化也是一个问题，从效率上来看，我们肯定要选择两个收敛最快的参数来进行优化。这里使用内层外层循环。

第一个变量的选择为外层循环，我们寻找一个违反KKT条件最严重的样本点，将其对应的变量作为第一个变量，即得到间隔边界上的支持向量点。第二个变量为内层循环，目的是为了使该变量的变化足够大。由于$ \alpha_{new}$与$|E_1-E_2|$有关，所以我们只要遍历得到使$|E_1-E_2|$的变量即可。在特殊情况下如果找不到足够的下降，则在讲个边界处寻找样本点对应的变量作为$\alpha_2$试用，若仍然找不到，则放弃$\alpha_1$

快乐，啪，没有了。

提升方法

提升方法的思想就是：对于一个复杂任务，多个专家的综合判断比一个专家的判断效果要好。这个思想并不难理解，接下来就一个一个方法说明。

AdaBoost算法

Adaboost是从一个简单的分类器，不断迭代出新直至得到较好分类效果的算法，其步骤如下：

• 初始化训练数据的权值分布

  $$D_1 = (\omega_{11},…,\omega_{1N}),\omega =\frac{1}{N},i=1,2,…,N$$

• 对于$m=1,2,…,M$

  • 使用具有上述全职分布的数据集进行学习，得到基本分类器，之后求分类器的误差率

    $$e_m = \sum_{i=1}^NP(G_m(x_i)\neq y_i)$$

  • 计算$G_m(x)$的系数

  $$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$

  • 更新权值分布

    $$\omega_{m+1,i}=\frac{\omega_{mo}}{Z_m}exp(-\alpha_my_iG_m(x_i))$$

    其中$Z_m = \sum_{i=1}^N\omega_{mi}exp(-\alpha_my_iG_m(x_i))$为规范化因子

• 构建基本分类器的线性组合 $$f(x) = \sum_{m=1}^{M}\alpha_mG_m(x)$$

通过上述步骤即可获得一个最终的分类器。一个非常有趣的地方是，AdaBoost并不是通过多个若分类加以权值得到的，而是通过一个弱分类器改变参数和权重求和得到的。

上述的方法得到的是一个线性的分类器，实际上还有另一种说法，即AdaBoost算法是一个加法模型，使用前向分布算法即可推导出。除了AdaBoost算法，还需要知道提升树

提升树

提升方法实际采用加法模型（基函数的线性组合）与前向分布算法。提升树模型就是以决策树为基函数的提升方法。

$$f_M(x)=\sum_{m=1}^MT(x;\Theta_m)$$

对于回归问题，提升树算法如下：

• 初始化$f_0(x)=x$
• 对$m=1,2,…,M$
  • 按照$r_{mi}=y_i-f_{m-1}(x_i),i=1,2,…,N$计算残差
  • 拟合残差$r_{mi}$学习一个回归树得到$T(x;\Theta_m)$
  • 更新$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
• 得到回归问题提升树。

EM算法及其推广

一些证明

Novikoff定理及证明

• 存在满足条件的的$||\hat{\omega}{opt}||=1$的超平面$\hat{\omega}{opt} \cdot \hat{x} = \omega_{opt} \cdot x +b_{opt}=0$将训练数据集完全正确分开；且存在$\gamma >0$，对所有的$i=1,2,…,N$

  $$y_i(\hat{\omega}{opt} \cdot \hat{x}) =y_i( \omega{opt} \cdot x +b_{opt})\geq \gamma$$

• 令$R=max_{1\leq i\leq N}||\hat{x}_i||$，则感知机算法在训练集上无分类次数k满足不等式：

  $$k \leq (\frac{R}{\gamma})^2$$

（1）由于训练集是线性可分的，所以存在一个超平面能够将两者完全正确分开。所以取此超平面为$\hat{\omega}{opt} \cdot \hat{x} = \omega{opt} \cdot x +b_{opt}=0$，使$||\hat{\omega}_{opt}||=1$，那么对于$i =1,2,…,N$，均有：

$$y_i(\hat{\omega}{opt} \cdot \hat{x}) =y_i( \omega{opt} \cdot x +b_{opt})>0$$

所以存在一个$\gamma$，有

$$\gamma = \min_i{y_i(\hat{\omega}_{opt} \cdot \hat{x})}$$

使$$y_i(\hat{\omega}{opt} \cdot \hat{x}) =y_i( \omega{opt} \cdot x +b_{opt})\geq \gamma$$

（2）感知机算法是从$\hat{\omega}0 = 0$开始，出现误分类时进行权重的更新。我们令$\hat{\omega}{k-1}$是第k个误分类实例。若$(x_i,y_i)$是被$\hat{\omega}_{k-1}$误分类的数据，那么参数的更新：

$$\omega_k \leftarrow \omega_{k-1}+\eta y_ix_i$$

$$b_k \leftarrow b_{k-1}+\eta y_i$$

即$\hat{\omega}k = \hat{\omega}{k-1}+\eta y_i \hat{x}_i$

接下来推导两个不等式：

• $$\hat{\omega}k \cdot \hat{\omega}{opt} = \hat{\omega}{k-1}\cdot \hat{\omega}{opt}+\eta y_i\hat{\omega}{opt} \cdot \hat{x}i\geq\hat{\omega}{k-1}\cdot \hat{\omega}{opt} +\eta \gamma$$

  递推之，最后可得：

  $$\hat{\omega}k \cdot \hat{\omega}{opt} \geq k\eta \gamma$$

• 

  定理证明，误分类的次数k是有上界的，所以感知机学习算法的迭代是收敛的。

后验概率最大化的含义

我们假设选择0-1损失函数那么期望风险函数：$$R_{exp}(f) = E[L(Y,f(X))]$$

取条件期望：$$R_{exp}(f) = E_X\sum^{K}_{k=1}[L(c_k,f(X))]P(c_k|X)$$

为了使期望风险最小化，只需对X=x逐个极小化，由此得到：

$$\begin{aligned}f(x)&=argmin_{y\in Y}\sum_{k=1}^KL(k_k,y)P(c_k|X=x)\ &=argmin_{y\in Y}\sum_{k=1}^KP(y\neq c_k|X=x)\&=argmin_{y\in Y}(1-P(y=c_k|X=x))\ &=argmax{_y\in Y}P(y=c_k |X=x)\end{aligned}$$

所以根据期望风险最小化得到了后验概率最大化准则。这就是朴素贝叶斯的原理。

支持向量机的拉格朗日乘子法学习过程

SMO学习算法

链接：https://zhuanlan.zhihu.com/p/29212107