《统计学习方法》

[toc]

统计学习

1. 以计算机和网络为平台
2. 对象：数据为研究对象
3. 目的：对数据进行预测和分析
4. 方法：构建模型
5. 多学科交叉

基本假设：同类数据具有一定的统计规律性。

方法：基于数据构建统计模型从而对数据进行分析与预测。

• 监督学习
• 非监督学习
• 半监督学习
• 强化学习

概括：

从给定的、有限的、用于学习的训练数据集合出发，假设数据是独立同分布产生的；并且假设要学习的模型属于某个函数的集合，称为假设空间；应用某个评价标准，从假设空间中选取一个最优的预测；最优模型的选取由算法实现。最优模型的选取由算法实现。三要素：模型，策略，算法。

步骤：

1. 训练集（搜集数据）
2. 确定假设空间（挑选函数，比如ANN，k近邻）
3. 确定准则（确定损失函数）
4. 确定求解算法（梯度下降法等）
5. 学习到最优模型（求解，学习）
6. 使用模型

监督学习

基本概念

输入空间：输入可能的所有的取值的集合

输出空间：输出可能的取值的集合

一个样本，称为一个实例 $x$, $x$由特征向量表示：

$x = [x^{(1)},x^{(2)},x^{(3)},...,x^{(n)}]^T$

数据集：

$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$

针对不同的数据类型，预测任务有不同的名称：1. 回归任务，2. 分类问题，3. 标注问题。

联合概率分布

$$P(X,Y)$$

输入变量和输出变量是依据联合概率分布产生的，这是一个基本假设。

假设空间：

假设空间就是x是如何映射到y的，这是未知的。我们使用模型来“近似”这个空间。

分为概率模型和非概率模型： $$ Y=f(x)\ P(y|x) $$ 决策函数，条件概率就是我们需要学习的模型。

统计学习的三要素

统计学习 = 模型 + 策略 + 算法

模型

假设空间包含所有可能的决策函数以及条件概率分布： $$ \mathcal{F}=\left{f \mid Y=f_{\theta}(X), \theta \in \mathbf{R}^{n}\right}\ \mathcal{F}=\left{P \mid P_{\theta}(Y \mid X), \theta \in \mathbf{R}^{n}\right} $$

策略

损失函数用于度量模型预测一次的好坏；

风险函数度量平均意义下模型预测的好坏。

常用的损失函数：

1. 0-1损失函数
2. 平方损失函数
3. 绝对损失函数
4. 对数损失函数，概率模型

期望损失：

X,Y 从联合概率P中生成： $$ R_{\exp }(f)=E_{P}[L(Y, f(X))]=\int_{x \times y} L(y, f(x)) P(x, y) \mathrm{d} x \mathrm{~d} y $$ 很显然，我们并不知道联合概率分布P，所以我们无法计算期望损失。我们采用蒙特卡洛方法，求期望的近似： $$ E_P(X)\approx 1/n\sum^n_{i=1} X_i $$ 那么期望损失的近似，经验损失为： $$ R_{\mathrm{emp}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right) $$ 选择模型的准则：

1. 经验风险最小化

$$\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)$$

1. 结构风险最小化

$$R_{\mathrm{smm}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$$

$$\min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f)$$

算法

根据策略，找到假设空间中的最优模型。

模型评估与模型选择

1. 正则化
2. 交叉验证
3. 简单交叉验证
4. s折交叉验证
5. 留一交叉验证
6. 留一交叉验证

泛化能力

由该方法学习到的模型对未知数据的预测能力。

生成模型与判别模型

生成模型的学习目标是联合概率分布$P(X,Y)$，最后求出条件概率分布

例子有：朴素贝叶斯法，隐马尔可夫模型

判别模型直接学习$f(X),P(Y|X)$,

例子有：k近邻，感知机，决策树，逻辑斯蒂回归，最大熵模型，支持向量机，提升方法等。

分类问题

二分类问题的评价指标：

1. 精确率（预测正，正确的概率）
2. 召回率（真正的正中，预测到的）
3. F1值

标注问题

标注问题其实就是多分类问题。

回归问题

函数拟合

感知机

模型

$$f(x)=\operatorname{sign}(w \cdot x+b)$$

$$\operatorname{sign}(x)= \begin{cases}+1, & x \geqslant 0 \\ -1, & x<0\end{cases}$$

策略

假设数据是线性可分的

损失函数写为： $$ L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right) $$

算法

随机梯度下降法

K近邻

模型

距离度量，k值，分类决策规则。

如果k=1，那么就是最近邻算法，预测为和最近的$x$一类。

如果k = k，那么就找到与x最近的k个x，进行投票选择。

距离度量

衡量两个向量之间的距离，或者说相似度：

1. Lp距离
2. 欧式距离，平方开根号
3. 曼哈顿距离，差值的绝对值相加

k值

一般采用交叉验证来确定k值

分类决策规则

一般是多数表决

策略

最优化k值，使得 $$ \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right) $$ 达到最大

算法

k近邻的参数是k，一般采用多折交叉验证的方式来确定，主要面临的问题是如何对数据进行高效的k近邻搜索。

预测（kd树）

kd树用于对数据进行高效的k近邻搜索。

kd树是一个二叉树，用于实现搜索。

kd树的平均搜索时间复杂度为$O(logn)$, 相比起全部遍历一遍，节约时间。

二叉树的左枝叶小于父节点，右枝叶大于父节点，通过与父节点比较，递归地向左右枝叶递归。达到叶子节点或者目标值后，再回溯找到k近邻。有点类似于堆的思想

朴素贝叶斯

模型

朴素贝叶斯的假设：每个特征都是符合条件独立，所以其贝叶斯网络结构是个简单的树结构。

朴素贝叶斯法是一个生成模型，用于学习$P(X, Y)$

根据上面的假设，我们可以写出似然概率： $$ P(X|Y)=P(x_1,x_2,...,x_n|Y) $$ 也可以给定先验概率： $$ P(Y) $$ 那么就可以计算出后验概率： $$ P(Y|X) \propto P(X|Y)P(Y)=P(x_1,x_2,...,x_n|Y)P(Y) $$

$$P(Y|X) \propto P(x_1|Y)P(x_2|Y)P(X_3|Y)...P(Y)$$

模型包括概率分布的形状及其参数，有了这些可以用x预测y，也可以由y计算x，这就是生成模型。

分类器可以写为：

$$ y=f(x)=\arg \max {c{k}} \frac{P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)}{\sum_{k} P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} \mid Y=c_{k}\right)} $$ 可以看到，其实是看哪一个类别$c_k$，可以让后验概率达到最大。

策略

最大似然估计：我们需要知道条件概率与先验概率，可以采用极大似然法进行估计。

对于离散的遍历，极大似然可以根据观测样本估计出表格式的条件概率与先验概率。

贝叶斯估计：采用极大似然估计，可能出现概率值为0的极端情况。

贝叶斯估计的条件概率如此表示，拉普拉斯平滑

$$P_{\lambda}\left(X^{(j)}=a_{j l} \mid Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l}, y_{i}=c_{k}\right)+\lambda}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+S_{j} \lambda}$$

算法

主要是概率分布的估计与计算

总结：

1. 特征变量的相互独立，极大地缩小了条件概率的复杂度

决策树

决策树是一种基本的分类、回归方法。

特点：模型具有可读性，分类速度快。

模型

决策树是if-then规则的集合

节点和有向边组成。

互斥且完备：每一个可能的实例都要被包括，而且只能被一条路径包括。

策略

决策树的学习本质上是从训练集合上归纳出一组分类规则，与训练集不矛盾的分类规则不止一种，也可能一个都没有。

特征选择，决策树的生成，剪枝这三个过程

特征选择：

根据信息论的原理进行选择。

熵：一个随机变量的熵描述了其“不确定度”。

条件熵：描述了在给定某个变量的时候，这个变量的不确定性。

信息增益：在未给定Y，与给定Y，这两个情况下，X的熵的差。 $$ g(D, A)=H(D)-H(D \mid A) $$ 信息增益比： $$ g_{R}(D, A)=\frac{g(D, A)}{H(D)} $$ 根据信息增益来进行特征选择：数据集D，计算每个变量的信息增益，选择信息增益最大的特征。

计算信息增益：

1. 计算D的熵
2. 计算A对数据集D的条件熵
3. 求差

信息增益最大的变量A：如果给定A，会使得数据的熵减小最多。

算法

ID3算法

使用信息增益来选择特征，递归构建决策树。

输入：数据集D，特征集A，阈值$\mathcal{E}$

1. 计算最大信息增益的特征$A_g$
2. 如果$A_g>\mathcal{E}$：
3. 依据该特征将D进行分割，在以此数据集递归执行ID3
4. 如果小于$\mathcal{E}$，
5. 作为叶子节点

剪枝算法：

最小化整棵树的损失函数： $$ C_{\alpha}(T)=\sum_{t=1}^{|T|} N_{t} H_{t}(T)+\alpha|T| $$ $H()$是每个叶子节点上的经验熵，展开写为： $$ H_{t}(T)=-\sum_{k} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}} $$ 可以发现，如果叶子节点上直落了一类样本，那么经验熵为0。

$N()$是该叶子节点的样本点

后面是一个对复杂树的惩罚

通过减少枝叶来最小化整棵树的损失函数。

CART算法

判别模型，学习出的是P(Y|X)。

1. 基于数据集生成决策树，决策树要尽量大
2. 决策树剪枝，用验证数据集对已经生成的树进行剪枝并选择最优子树，这时使用损失函数最小作为剪枝标准。

回归树

树模型实际上是对空间的划分，假设划分为M个单元，每个单元对应的输出值为$c_m$ $$ f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right) $$ 损失函数： $$ \hat{c}{m}=\operatorname{ave}\left(y{i} \mid x_{i} \in R_{m}\right) $$ 如何找到最优切分点，就是构建树的过程：

对于$x^{(j)}$来说，切分为两部分$R_1$,$R_2$： $$ R_{1}(j, s)=\left{x \mid x^{(j)} \leqslant s\right} \quad \text { 和 } \quad R_{2}(j, s)=\left{x \mid x^{(j)}>s\right} $$ 最优切分点为： $$ \min {j, s}\left[\min {c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min {c{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right] $$

最小二乘回归树：

1. 遍历遍历$x_j$与切分点$s$，使之损失函数最小

$$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$$

1. 根据已经确定好的j, s 确定划分区域的输出值

1. 继续往下划分，直到满足终止条件。

分类树

分类树用基尼系数来选择最优特征。 $$ \operatorname{Gini}(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2} $$ 对于一个样本集（其实指的是$P(D)$），其基尼系数为： $$ \operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2} $$ 基尼系数表示集合的不确定性，基尼指数$Gini(D,A)$表示经过A分割后集合D的不确定性。

$D_1$和$D_2$是依据特征A的分割点a来确定的。 $$ \operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right) $$

CART生成算法

1. 遍历各个特征，以及特征a的分割点，找到最优的A，与分割点a。
2. 生成两个子节点
3. 递归的使用该算法，知道节点的样本数少于阈值

CART剪枝

计算子树的损失函数： $$ C_{\alpha}(T)=C(T)+\alpha|T| $$ 某个节点的损失函数： $$ C_{\alpha}(t)=C(t)+\alpha $$

如果说T是一个棵树，t是一个单节点，那么存在一个足够大的$\alpha$使得：

$$C_{\alpha}\left(T_{t}\right)=C_{\alpha}(t)$$

此时：

$$\alpha=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$$

把这个数值作为剪枝的标准g(t):

$$g(t)=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$$

这个数字越大，说明越需要依赖正则项优势，所以最小的$g(t)$, 是我们需要减去的。

越是拥有大的$\alpha$ 越是会剪枝，所以对应于$\alpha_1, \alpha_2,...,\alpha_n$都有一颗子树

找到最优子树（使用交叉验证）， 就可以确定$\alpha$ 了。

Logistic 回归

logistic distribution：

$$\begin{aligned} &F(x)=P(X \leqslant x)=\frac{1}{1+\mathrm{e}^{-(x-\mu) / \gamma}} \\ &f(x)=F^{\prime}(x)=\frac{\mathrm{e}^{-(x-\mu) / \gamma}}{\gamma\left(1+\mathrm{e}^{-(x-\mu) / \gamma}\right)^{2}} \end{aligned}$$

二项分类模型

二项逻辑斯蒂回归是一个判别模型，拟合P(Y|X)，其模型的显式表达为：

$$\begin{aligned} &P(Y=1 \mid x)=\frac{\exp (w \cdot x+b)}{1+\exp (w \cdot x+b)} \\ &P(Y=0 \mid x)=\frac{1}{1+\exp (w \cdot x+b)} \end{aligned}$$

有参数$w,b$。可以将b整合到输入向量中，得到

$$\begin{aligned} &P(Y=1 \mid x)=\frac{\exp (w \cdot x)}{1+\exp (w \cdot x)} \\ &P(Y=0 \mid x)=\frac{1}{1+\exp (w \cdot x)} \end{aligned}$$

一个事件发生的概率与不发生的概率的比值，是该事件的几率（odds）。

$$odds = p/(1-p)$$

那么对于逻辑斯蒂回归而言，事件的对数几率：

$$\log \frac{P(Y=1 \mid x)}{1-P(Y=1 \mid x)}=w \cdot x$$

这既是说：逻辑斯蒂模型输出Y=1的对数几率是输入向量x的线性函数。

策略

参数使用最大似然估计。

记：

$$P(Y=1 \mid x)=\pi(x), \quad P(Y=0 \mid x)=1-\pi(x)$$

似然函数写为：

$$ \prod_{i=1}^{N}\left[\pi\left(x_{i}\right)\right]^{y_{i}}\left[1-\pi\left(x_{i}\right)\right]^{1-y_{i}} $$ 将其展开，并结合上文提到的性质，最终似然函数可以写为：

$$L(w) =\sum_{i=1}^{N}\left[y_{i}\left(w \cdot x_{i}\right)-\log \left(1+\exp \left(w \cdot x_{i}\right)\right]\right.$$

算法

$$\max_w L(w)$$

一般使用牛顿法或者梯度下降法。

多项分类模型

$$\begin{gathered} P(Y=k \mid x)=\frac{\exp \left(w_{k} \cdot x\right)}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} \cdot x\right)}, \quad k=1,2, \cdots, K-1 \\ P(Y=K \mid x)=\frac{1}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} \cdot x\right)} \end{gathered}$$

前K-1个的分子是$exp(w_k\cdot x)$, 第K个是1。

最大熵模型

熵：一个随机变量的熵描述了其“不确定度”。

一个概率分布的熵计算公式：

$$H(P)=-\sum_{x} P(x) \log P(x)$$

当X取均匀分布的时候，熵最大。

条件熵：描述了在给定某个变量的时候，这个变量的不确定性。

$$H(Y \mid X)=\sum_{i=1}^{n} p\left(x_{i}\right) H\left(Y \mid X=x_{i}\right)=-\sum_{i=1}^{n} p\left(x_{i}\right) \sum_{j=1}^{m} p\left(y_{j} \mid x_{i}\right) \log p\left(y_{j} \mid x_{i}\right)$$

最大熵可以作为我们模型选择的准则。

现假设数据的联合概率为：

$$ P(X,Y) $$ 根据观测数据，我们可以得到经验联合概率分布为：

$$ \begin{aligned} &\tilde{P}(X=x, Y=y)=\frac{v(X=x, Y=y)}{N} \ &\tilde{P}(X=x)=\frac{v(X=x)}{N} \end{aligned} $$ 对于判别模型$P(y|x)$

$$\sum_{x, y} \tilde{P}(x) P(y \mid x) f(x, y)=\sum_{x, y} \tilde{P}(x, y) f(x, y)$$

对于满足这个条件的模型$P(y|x)$，我们都可以认为它是“有效”的，但不一定是最好的。

举个例子:

对于x=0,y=?

p(y=1|x=0)=1,p(y=1|x=0)=0 是一种模型；

p(y=1|x=0)=0.75,p(y=1|x=0)=0.25 也是一种模型；

它们都可以正确地估计出y=1这个结果，但是哪个模型更好呢？

记

$$ \mathcal{C} \equiv\left{P \in \mathcal{P} \mid E_{P}\left(f_{i}\right)=E_{\tilde{P}}\left(f_{i}\right), \quad i=1,2, \cdots, n\right} $$ 这个集合里的所有模型都是有效的，具有最大熵的模型为：

$$H(P)=-\sum_{x, y} \tilde{P}(x) P(y \mid x) \log P(y \mid x)$$

最大化这个式子，得到的P(Y|X)是具有最大熵的“有效”模型。

这就是最大熵模型选择。

策略

用拉格朗日乘子法进行求解。（等号约束是一种强约束，如果是小于等于的弱约束则使用KKT定理）

支持向量机SVM

模型

SVM是一种二分类模型。

当数据线性可分的时候，使用过硬间隔最大化学习一个线性分类器；

当数据近似线性可分时，使用软间隔最大化学习一个线性分类器；

当数据 线性不可分时，使用核方法和软间隔最大化，学习非线性支持向量机。

线性可分支持向量机

假设数据是线性可分的，这是一种非常强的假设。

如果这个超平面为：

$$w^{*} \cdot x+b^{*}=0$$

支持向量机模型可写为：

$$f(x)=\operatorname{sign}\left(w^{*} \cdot x+b^{*}\right)$$

策略

函数间隔，描述样本点与超平面的距离：

$$\hat{\gamma}_{i}=y_{i}\left(w \cdot x_{i}+b\right)$$

在此，复习一下点到直线的距离计算公式：

Ax+By+C=0, 点$(x_0,y_0)$

距离d为：$d=\frac{\left|A x_{0}+B y_{0}+C\right|}{\sqrt{A^{2}+B^{2}}}$

所以对于平面 wx+b=0, 距离正比于 $wx_i+b$

所有间隔中最小值为：

$$\hat{\gamma}=\min _{i=1, \cdots, N} \hat{\gamma}_{i}$$

函数间隔会受到 w,b的影响，如果把w,b变为两倍，超平面位置不变，但是距离增加了两倍。所以一般采用几何间隔：

$$\gamma_{i}=y_{i}\left(\frac{w}{\|w\|} \cdot x_{i}+\frac{b}{\|w\|}\right)$$

间隔最大化：对训练数据集找到几何间隔最大的超平面意味着已充分的的确信度对训练数据进行分类。

考虑到几何间隔和函数间隔的关系，问题可以转化为：

算法

最大间隔法来学习“线性可分支持向量机”。

证明：最大间隔分离超平面的存在性，唯一性。

支持向量，训练数据集的样本中与分离超平面距离最近的样本点的实例称为支持向量。

$$y_{i}\left(w \cdot x_{i}+b\right)-1=0$$

间隔边界依赖于法向量w：

$$\frac{2}{\|w\|}$$

决定分离超平面时，只有支持向量起作用，而其他实例并不起作用，所以支持向量机由很少的“重要样本”决定。

针对上面的最优化问题（被证明为凸），先转化为对偶问题，使用拉格朗日乘子法或者KKT定理，进行求解：

1. 构造对偶问题，并求解约束优化问题：

求得：

$$\alpha^{*}=\left(\alpha_{1}^{*}, \alpha_{2}^{*}, \cdots, \alpha_{N}^{*}\right)^{\mathrm{T}}$$

1. 计算w,b

$$w^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i}\\ b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left(x_{i} \cdot x_{j}\right)$$

1. 带入的到模型

$$f(x)=sign(w^*\cdot x+b^*)$$

非线性支持向量机

使用核技巧，使得支持向量机适用于非线性的分类问题。

什么是线性可分问题？

对于数据$x=R^n$,在$R^n$中可以用一个超平面将正负例正确分开，则线性可分。

如果说用一个超曲面将正负例分开，则为非线性可分问题。

$Ax^2+By^2=1$ 进行一个变换： $$ z=\phi(x)=\left(\left(x^{(1)}\right)^{2},\left(x^{(2)}\right)^{2}\right)^{\mathrm{T}} $$ 从而得到： $$ Az_1+Bz_2=1 $$ 这样就成了一个线性可分得问题。

核函数

存在一个这样的映射： $$ \phi(x): \mathcal{X} \rightarrow \mathcal{H} $$ 对于任意$x, z \in \mathcal{X}$, 满足： $$ K(x, z)=\phi(x) \cdot \phi(z) $$ 则称$K(x,z)$为核函数，$\phi(x)$为映射函数。

比如说前面椭圆形变直线的案例，$\phi(x)：x^2\rightarrow z$, 核函数为：$K(x,z)=x^2 \cdot z^2$

由于SVM用对偶算法求解，对偶问题中的目标表函数只涉及到内积，所以都可以用核函数。

正定核

对于 $$ K(x, z) $$ 它关于$x_1,x_2,...,x_m$的gram矩阵是半正定的。

常用核函数

多项式核函数；

高斯核函数；

字符串核函数；

策略

与线性相同，都是一个凸二次规划问题。

算法

与线性的支持向量机相同，只是修改了内积部分为核函数。

SMO序列最小最优化算法

SMO主要用于求解凸二次规划问题。

SMO有点类似于坐标上升算法，把多元问题转化为一元问题。

SMO算法是一种启发式算法，其基本思想是：

如果所有变量的解都满足最优化问题的KKT条件，那么这个最优化问题的解就找到了。

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。必要！！

提升方法 Boosting

概念：

1. 强可学习：在概率近似正确学习的框架中，一个概念如果存在一个多项式的学习算法能够学习他，且正确率很高，则称之为抢课学习的。
2. 弱可学习的。

这里不涉及模型与策略，只讲到算法，用于使现在的模型达到更好的效果。

提升方法要做两件事：

如何更新数据的权值。

如何将弱分类器组合成一个强分类器。

AdaBoost算法

1. 初始化训练数据的权值分布，均匀分布。
2. 对m个基本分类器：
3. $G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\}$
4. 计算其误差$e_m$
5. 通过误差计算分类器的系数：$\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}$
6. 更新数据集的权值分布：
7. 构建分类器的线性组合
8. 最终得到分类器

说明：

误差定义分类器的系数，误差差小的分类器系数大，误差大的分类器系数小。

被分类器错误分类的数据会得到更高的权重。

AdaBoost

在仅仅作为一个算法的同时，也有学者将其建模为加法模型。

模型

$$f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)$$

其中b为基函数，$\beta$为系数，这是一个加法模型

策略

经验风险最小化： $$ \min {\beta{m}, \gamma_{m}} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right) $$

算法

由于这涉及到基函数，求解上面的加法模型，采用的思想为前向分步算法：从前向后，每一步只学习一个基函数和其系数，逐步优化： $$ \min {\beta, \gamma} \sum{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right) $$ 前向分布算法：

提升树

提升树是以分类树或回归树为基本分类器的提升方法，被认为是性能最好的方法之一。

模型

基模型为一个根节点，两个叶子节点构成的简单决策树。 $$ f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right) $$

算法

最终得到提升树模型 $$ f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right) $$

隐马尔可夫模型