目录

• 目录
• 1. 第1章 绪论
• 2. 第2章 模型评估与选择
  • 2.1. 思维导图
  • 2.2. 经验误差与过拟合
  • 2.3. 评估方法
    • 2.3.1. 留出法
    • 2.3.2. 交叉验证法
    • 2.3.3. 自助法
  • 2.4. 性能度量
    • 2.4.1. 错误率与精度
    • 2.4.2. 查准率、查全率与F1
    • 2.4.3. ROC与AUC
    • 2.4.4. 代价敏感错误率与代价曲线
  • 2.5. 比较检验
    • 2.5.1. 假设检验
    • 2.5.2. 交叉验证t检验
    • 2.5.3. McNemar检验
    • 2.5.4. Friedman检验与Nemenyi后续检验
  • 2.6. 偏差与方差
• 3. 第3章 线性模型
  • 3.1. 思维导图
  • 3.2. 基本形式
  • 3.3. 线性回归
  • 3.4. 对数几率回归
  • 3.5. 线性判别分析
  • 3.6. 多分类学习
  • 3.7. 类别不平衡问题
• 4. 第4章 决策树
  • 4.1. 思维导图
    • 4.1.1. 章节导图
    • 4.1.2. 如何生成一棵决策树
  • 4.2. 基本流程
  • 4.3. 划分选择
    • 4.3.1. 信息增益
    • 4.3.2. 增益率
    • 4.3.3. 基尼指数
  • 4.4. 剪枝处理
    • 4.4.1. 预剪枝
    • 4.4.2. 后剪枝
  • 4.5. 连续与缺失值
    • 4.5.1. 连续值处理
    • 4.5.2. 缺失值处理
  • 4.6. 多变量决策树
  • 4.7. 阅读材料
• 5. 第5章 神经网络
  • 5.0. 思维导图
  • 5.1. 神经元模型
  • 5.2. 感知机与多层网络
  • 5.3. 误差逆传播算法
  • 5.4. 全局最小与局部极小
  • 5.5. 其他常见神经网络
    • 5.5.1. RBF网络
    • 5.5.2. ART网络
    • 5.5.3. SOM网络
    • 5.5.4. 级联相关网络
    • 5.5.5. Elman网络
    • 5.5.6. Boltzmann机
  • 5.6. 深度学习
• 6. 第6章 支持向量机
  • 6.0. 思维导图
  • 6.1. 间隔与支持向量
  • 6.2. 对偶问题
  • 6.3. 核函数
  • 6.4. 软间隔与正则化
  • 6.5. 支持向量回归
  • 6.6. 核方法
• 7. 第7章 贝叶斯分类器
  • 7.0. 思维导图
  • 7.1. 贝叶斯决策论
  • 7.2. 极大似然估计
  • 7.3. 朴素贝叶斯分类器
  • 7.4. 半朴素贝叶斯分类器
  • 7.5. 贝叶斯网
    • 7.5.1. 结构
    • 7.5.2. 学习
    • 7.5.3. 推断
  • 7.6. EM算法

1. 第1章 绪论

2. 第2章 模型评估与选择

2.1. 思维导图

2.2. 经验误差与过拟合

定义：

• 错误率(error rate): 如果m个样本中有a个样本分类错误，则错误率E=a/m。
• 精度(accuracy)：精度=1-错误率。
• 训练误差：学习器在训练集上的误差称为训练误差或者经验误差。
• 泛化误差(generalization error)：学习器在新样本上的误差称为泛化误差。
• 过拟合(overfitting)：当学习器把训练样本学得太好了的时候，很可能把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，这就会导致泛化性能下降。
• 欠拟合(underfitting)：对训练样本的一般性质尚未学好。

2.3. 评估方法

通常我们可通过实验测试来对学习器的泛化误差进行评估而做出选择，于是我们需要一个测试集(testing set)，然后以测试集上的测试误差作为泛化误差的近似。下面介绍一些常见的处理数据集D的方法(数据集D->训练集S+测试集T)¹

2.3.1. 留出法

• 留出发(hold-out)直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T。在S上训练出模型后，用T来评估其测试误差。
• 以采样的角度来看待数据集划分的过程，则保留类别比例的采样方式通常称为分层采样。比如1000个样本，50%的正例，50%负例，以7：3划分数据集，那么训练集包含350个正例和350个负例就是分层采样。
• 在使用留出法评估结果时，一般要采用若干次随即划分、重复进行实验评估后取平均值作为留出法的评估结果。
• 常用做法时将大约2/3~4/5的样本用于训练。

2.3.2. 交叉验证法

• 交叉验证法(cross validation)先将数据集D划分为k个大小相似的互斥子集，每个子集D_i都尽可能保持数据分布的一致性。然后每次用k-1个自己的并集作为训练集，余下的那个子集作为测试集，这样就可以获得k组训练/测试集，从而可进行k次训练和测试，最终返回的是这k个测试结果的均值。
• 交叉验证也称为k折交叉验证。k的常见取值有10、5、20。
• 留一法就是k=m，其中数据集D有m个样本。

2.3.3. 自助法

• 自助法(bootstrapping)：给定包含m个样本的数据集D，每次随机从D中挑选一个样本，将其拷贝放入D’, 然后再将该样本放回最初的数据集D中，这个过程重复执行m次后，我们获得了包含m个样本的数据集D’。我们将D’作为训练集，D\D’作为测试集。
• 不难发现大概有36.8%(m趋于无限大时)的样本在m次采样中始终不被采到。

$\lim\limits_{m\rightarrow\infty}(1-\frac{1}{m})^m = \frac{1}{e} ≈ 0.368$

• 缺点：自助法产生的数据集改变了初始数据集的分布，这样会引入估计偏差。因此，在初始数据量足够时，留出法和交叉验证法更常用一些。

2.4. 性能度量

• 对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量(performance measure)。
• 在预测任务中，给定D = {(x₁,y₁), (x₂,y₂)…(x_m,y_m)}, 其中y_i是x_i的真实标记。学习器f。
• 均方误差(mean squared error)：回归任务最常用的性能度量是均方误差：

$E(f;D)=\frac{1}{m}\sum_1^m(f(x_i)-y_i)^2$

接下来我将介绍分类任务中常用的性能度量

2.4.1. 错误率与精度

本章开头提到了错误率和精度，这是分类任务中最常用的两种性能度量，既适用于二分类任务，也适用于多分类任务。

2.4.2. 查准率、查全率与F1

• 针对二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为真正例(true positive)、假正例(false positive)、真反例(true negative)、假反例(false negative)，分别记为TP、FP、TN、FN。
• 混淆矩阵(confusion matrix)

真\预	正例	反例
正例	TP	FN
反例	FP	TN

• 查准率(precision)，记为P，它表示选择的好瓜中有多少是真正的好瓜

$P=\frac{TP}{TP+FP}$

• 查全率(recall)，记为R，它表示好瓜中有多少被选出来了

$R=\frac{TP}{TP+FN}$

• 一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。

• P-R曲线：在很多情形下，我们可根据学习器的预测结果对样例进行排序，排在前面的是学习器认为最可能是正例的样本，排在最后的则是学习器认为最不可能是正例的样本，按此顺序逐个把样本作为正例进行预测，则每次可以计算出当前的查全率、查准率，也得到了P-R图。

• 如果一个学习器的P-R曲线被另一个学习器的曲线完全包住，则可断言后者的性能优于前者。如果两者曲线相交，则可以通过比较平衡点(break-even-point)来比较，越大越好。

• F1度量：F1综合考虑了查准率和查全率，是他们的调和平均

$F1=\frac{2*P*R}{P+R}$

• F1的一般形式：有时候我们希望赋予查准率和查重率不同的权重：

$F_\beta=\frac{(1+\beta^2)*P*R}{\beta^2*P+R}$

其中β大于1表示查全率有更大影响

• 有时候我们有多个二分类混淆矩阵，我们希望在这n个混淆矩阵上综合考虑查准率和查全率，那么我们有以下的度量

• 宏查准率macro-P，宏查全率macro-R，宏F1：

$macro-P=\frac{1}{n}\sum_1^nP_i$ $macro-R=\frac{1}{n}\sum_1^nR_i$

• 微查准率micro-P，微查全率micro-P，微F1：

对TP、FP、TN、FN进行平均

$micro-P=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$ $micro-P=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$

2.4.3. ROC与AUC

• 很多学习器是为测试样本产生一个实值或概率预测，然后将这个预测值与一个分类阈值进行比较，若大于阈值则分为正类，否则为反类。

• ROC曲线是从排序角度来出发研究学习器的泛化性能的工具。ROC的全称是Receiver Operating Characteristic。

• 与P-R曲线类似，我们根据学习器的预测结果进行排序，按此顺序逐个把样本作为正例进行预测，计算出真正例率TPR(true positive rate)与假正例率FPR(false positive rate)并以它们分别为横纵坐标画出ROC曲线

$TPR=\frac{TP}{TP+FN}$ $FPR=\frac{FP}{FP+TN}$

• 同样的，如果一个学习器的ROC曲线被另一个学习器完全包住，则认为后者的性能优于前者。若两个曲线相交，则比较曲线下的面积AUC(area under curve)

• 形式化的看，AUC考虑的是样本预测的排序质量，那么我们可以定义一个排序损失l_rank

AUC=1-l_rank

2.4.4. 代价敏感错误率与代价曲线

• 有时候将正例误判断为负例与将负例误判断为正例所带来的后果不一样，我们赋予它们非均等代价
• 代价矩阵(cost matrix)

真\预	第0类	第1类
第0类	0	cost01
第1类	cost10	0

其中cost_ij表示将第i类样本预测为第j类样本的代价

• 代价敏感错误率

• 在非均等代价下，ROC曲线不能直接反映出学习器的期望总代价，而代价曲线则可达到此目的，横轴是正例概率代价，纵轴是归一化代价

 

 

2.5. 比较检验

我们有了实验评估方法与性能度量，是否就可以对学习器的性能进行评估比较了呢？实际上，机器学习中性能比较这件事比大家想象的要复杂很多，我们需要考虑多种因素的影响，下面介绍一些对学习器性能进行比较的方法，本小节默认以错误率作为性能度量。(但我觉得似乎同一个数据集下就可以比较)

2.5.1. 假设检验

• 假设检验中的假设是对学习器泛化错误率分布的某种猜想或者判断，例如“ε=ε₀”这样的假设
• 现实任务中我们并不知道学习器的泛化错误率，我们只能获知其测试错误率$\hat{\epsilon}$，但直观上，两者接近的可能性比较大，因此可根据测试错误率估推出泛化错误率的分布。
• 泛化错误率为$\epsilon$的学习器被测得测试错误率为$\hat{\epsilon}$的概率：

• 我们发现$\epsilon$符合二项分布

• 二项检验：我们可以使用二项检验(binomial test)来对“$\epsilon$<0.3”这样的假设进行检验，即在$\alpha$显著度下，$1-\alpha$置信度下判断假设是否成立。

• t检验：我们也可以用t检验(t-test)来检验。

• 上面介绍的都是针对单个学习器泛化性能的假设进行检验

2.5.2. 交叉验证t检验

• 对于两个学习器A和B，若我们使用k折交叉验证法得到的测试错误率分别是$\epsilon_1^A$, $\epsilon_2^A$…$\epsilon_k^A$和$\epsilon_1^B$, $\epsilon_2^B$…$\epsilon_k^B$。其中$\epsilon_i^A$和$\epsilon_i^B$是在相同第i折训练集上得到的结果。则可以用k折交叉验证“成对t检验”来进行比较检验。

• 我们这里的基本思想是若两个学习器的性能相同，则它们使用相同的训练测试集得到的错误率应该相同，即$\epsilon_i^A=\epsilon_1^B$

• $\Delta_i$ = $\epsilon_i^A$ - $\epsilon_i^B$，然后对$\Delta$进行分析

2.5.3. McNemar检验

• 对于二分类问题，使用留出法不仅可以估计出学习器A和B的测试错误率，还可获得两学习器分类结果的差别，即两者都正确、都错误…的样本数

• 若我们假设两学习器性能相同，则应有e₀₁=e₁₀，那么变量|e₀₁-e₁₀|应该服从正态分布/卡方分布，然后用McNemar检验

2.5.4. Friedman检验与Nemenyi后续检验

• 交叉验证t检验与McNemar检验都是在一个数据集上比较两个算法的性能，但是很多时候，我们会在一组数据集上比较多个算法。

• 当有多个算法参与比较时，一种做法是在每个数据集上本别列出两两比较的结果。另一种方法则是基于算法排列的Friedman检验

• 假定我们用D₁, D₂, D₃, D₄四个数据集对算法A、B、C进行比较。首先，使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果。然后在每个数据集上根据测试性能由好到坏排序，并赋予序值1,2,…若算法的测试性能相同，则平分序值。

• 然后使用Fredman检验来判断这些算法是否性能都相同，若相同，那么它们的平均序值应当相同。r_i表示第i个算法的平均序值，那么它的均值和方差应该满足…

• 若“所有算法的性能相同”这个假设被拒绝，则说明算法的性能显著不同，这时需要后续检验(post-hoc test)来进一步区分各算法，常用的有Nemenyi后续检验

• Nemenyi检验计算出平均序值差别的临界值域

• 在表中找到k=3时q_0.05=2.344，根据公式计算出临界值域CD=1.657，由表中的平均序值可知A与B算法的差距，以及算法B与C的差距均未超过临界值域，而算法A与C的差距超过临界值域，因此检验结果认为算法A与C的性能显著不同，而算法A与B以及算法B与C的性能没有显著差别。

2.6. 偏差与方差

• 对学习算法除了通过实验估计其泛化性能，人们往往还希望了解它“为什么”具有这样的性能。偏差-方差分解是解释学习算法泛化性能的一种重要工具

• 偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力
• 方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响

• 噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度

• 一般来说，偏差与方差是有冲突的，也就是偏差大的方差小，偏差小的方差大

3. 第3章 线性模型

3.1. 思维导图

3.2. 基本形式

• 给定由d个属性描述的示例$x=(x_1;x_2;…x_d)$，这是一个列向量，其中$x_i$是$x$在第i个属性上的取值。

• 线性模型(linear model)试图学得一个通过属性线性组合来进行预测的函数：

• 向量形式：

$f(x)=\omega^Tx+b$

其中$\omega=(\omega_1;\omega_2…\omega_d)$

• 当$\omega$和b学得后，模型就得以确定

• 线性模型的优点：形式简单，易于建模，良好的可解释性(comprehensibility)

3.3. 线性回归

• 对离散属性的处理，若属性值存在“序”的关系，可通过连续化将其转化为连续值，比如高、矮变成1、0；2.若不存在序的关系，可转化为k维向量。

• 均方误差是回归任务中最常用的性能度量，试图让均方误差最小化：

• 均方误差有非常好的几何意义，它对应了欧氏距离。基于均方误差最小化来进行模型求解的方法称为最小二乘法(least square method)。在线性回归中，最小二乘法就是试图找到一条直线，使得样本到直线上的欧氏距离之和最小

• 首先观察一个属性值的情况。求解$\omega$和$b$使得均方误差最小化的过程，称为线性回归的最小二乘“参数估计”，我们令均方误差分别对$\omega$和$b$求导令其为零，可以得到最优解的闭式解(closed-form),即解析解

 

• 更一般的情况是d个属性，称其为“多元线性回归”，同样的步骤，只是$\omega$变成向量形式，自变量写成m*(d+1)的矩阵形式，m对应了m个样本，d+1对应了d个属性和偏置。同样的求导为0然后得出$\hat{\omega}$最优解的闭式解，其中$\hat{\omega}=(\omega;b)$。当$X^TX$为满秩矩阵²或正定矩阵时，有唯一的解：

 

 

 

 

• 然而现实任务中往往不是满秩矩阵，例如在许多任务中我们会遇到大量的变量其数目甚至超过样例数。那么我们会求出$\hat{\omega}=(\omega;b)$的多个解，它们都能使均方误差最小化。选择哪一个解作为输出与学习算法的归纳偏好决定，常见的做法是引入正则化(regularization)

• 广义线性模型(generalized linear model):

$g(y)=\omega^Tx+b$

其中g()单调可微，被称为联系函数。比如当g()=ln()时称为对数线性回归

3.4. 对数几率回归

• 上一节讨论的是线性回归进行回归学习。那么如果我们要做的是分类任务应该怎么改变？我们只需要找到一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值联系起来。

• 考虑二分类问题，那么我们可以用单位阶跃函数/Heaviside函数联系y与z，其中y是真是标记，z是预测值，$z=\omega^Tx+b$

• 但是它有个问题就是不连续，所以我们希望找到能在一定程度上近似它的替代函数。

• 对数几率函数(logistic function)就是一个替代函数：

$y=\frac{1}{1+e^{-z}}$

• 那么这个式子可以转化为：可以把y视为样本x作为正例的可能性，则1-y是其反例的可能性，两者的比值称为几率(odds)：

• 若将y视为类后验概率估计。则式子可以重写为：

• 接下来我们可以通过极大似然法(maximum likelihood method)来估计$\omega$和$b$。给定数据集，对数似然函数³为：

即每个样本属于其真实标记的概率越大越好。

• 推导过程：

上面有个式子应该有问题，(3.26)应该是

$p(y_i|x_i;\omega,b) = p_1(\hat{x_i};\beta)^{y_i}p_0(\hat{x_i};\beta)^{1-y_i}$

因为$\beta$是高阶可导连续凸函数，根据凸优化理论，经典的数值优化算法如梯度下降法(gradient descent method)和牛顿法都可以求得最优解

3.5. 线性判别分析

• 线性判别分析(Linear Discriminant Analysis，简称LDA)是一种经典的线性学习方法。

• LDA的思想非常朴素: 给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离;在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。

• 令$X_i$、$\mu_i$、$\Sigma_i$分别表示第i类示例的集合、均值向量⁴、协方差矩阵⁵。

• 欲使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小，即$\omega^T\Sigma_0\omega+\omega^T\Sigma_1\omega$尽可能小;而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即$||\omega^T\mu_0-\omega^T\mu_1||$尽可能大:

• 剩余推导过程：

 

• 值得一提的是，LDA可从贝时斯决策理论的角度来阐释，并可证明，当两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类。

3.6. 多分类学习

• 现实中常遇到多分类学习任务，有些二分类学习方法可直接推广到多分类，但在更多情形下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题。

• 不失一般性，考虑N个类别$C_1$、$C_2$…$C_N$，多分类学习的基本思路是”拆解法”，即将多分类任务拆为若干个二分类任务求解。具体来说，先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器;在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果。

• 这里我们着重介绍如何拆分，最经典的拆分策略有三种：一对一(One vs One)、一对其余(One vs Rest)、多对多(Many vs Many)

• 一对一：将这N个类别两两配对，从而产生 N(N-1)/2个二分类任务。在测试阶段，新样本将同时提交给所有分类器，于是我们将得到N(N-1)/2个分类结果，最终结果可通过投票产生:即把被预测得最 多的类别作为最终分类结果。

• 一对其余：OvR则是每次将一个类的样例作为正例，所有其他类的样例作为反例来训练N个分类器。在测试时若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果。若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果。

• 多对多MvM是每次将若干个类作为正类，若干个其他类作为反类。这里我们介绍一种最常用的MvM技术：纠错输出码(ECOC)

• ECOC是将编码的思想引入类别拆分，主要分为两步：

  1.编码： 对N个类别做M次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集;这样一共产生M个训练集，可训练出M个分类器

  2.解码：:M个分类器分别对测试样本进行预测，这些预测标记组成一个编码.将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。

• 类别划分通过编码矩阵指定。编码矩阵有多种形式，常见的有二元码和三元码，前者将每个类别分别指定为正类和反类，后者在正、反类之外，还可指定“停用类”

3.7. 类别不平衡问题

• 前面介绍的分类学习方法都有一个共同的基本假设：即不同类别的训练样例数目相当。如果不同类别的样例数差别很大，会对学习过程造成困扰。

• 类别不平衡(class-imbalance)就是指分类任务中不同类别的训练样例数目差别很大的情况。

• 再缩放(rescaling)是类别不平衡中的一个基本策略：比如在最简单的二分类问题中，我们假设y大于0.5为正例，y小于0.5为负例，但是在类别不平衡时，我们可以改变阈值来达到再平衡：

  将

  变成

• 现有的解决类别不平衡的技术大体上有三类做法(这里我们均假设正例样本少):

  1.第一类是直接对训练集里的反类样例进行”欠采样” (undersampling)，即去除一些反例使得正、反例数日接近，然后再进行学习;

  2.第二类是对训练集里的正类样例进行”过采样” (oversampling)，即增加一些正例使得正、反例数目接近，然后再进行学习;

  3.第三类则是直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将上面的公式(改变阈值)嵌入到其决策过程中，称为”阔值移动” (threshold-moving)

• 需注意的是，过采样法不能简单地对初始正例样本进行重复来样，否则会招致严重的过拟合；过采样法的代表性算法SMOTE是通过对训练集里的正例进行插值来产生额外的正例.另一方面，欠采样法若随机丢弃反例可能丢失一些重要信息;欠采样法的代表性算法EasyEnsemble则是利用集成学习机制，将反例划分为若干个集合供不同学习器使用，这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息。

4. 第4章 决策树

4.1. 思维导图

4.1.1. 章节导图

4.1.2. 如何生成一棵决策树

4.2. 基本流程

• 决策树是基于树结构来进行决策，其中包含一个根结点，多个内部结点和多个叶结点
• 叶结点对应决策结果，其他每个结点都对应一个属性测试
• 每个结点包含的样本集合根据属性测试被划分到子结点中，那么根结点包含样本全集
• 决策树学习的目的是为了产生一棵泛化能力强的决策树
• 决策树的生成是一个递归过程，下面这张图展示了递归的过程：

对于每个结点，首先判断该结点的样本集是否属于同一个类别C，如果是，则将该结点标记为C类叶结点。再判断该结点的样本集的属性值是否完全相同(或者是否为空集)，如果是，则将该结点标记为D类叶结点，其中D类是这些样本中最多的类别。如果该结点即不是同属于一个类别也不是属性值取值相同，那么则需要继续划分，选择一个最优的划分属性$a_*$,创建新的分支，对于每个分支结点首先判断是否为空，如果为空则判定为E类叶结点，其中E类是父结点中类别最多的类。如果子结点不为空则递归。

4.3. 划分选择

可以发现生成决策树最关键的步骤就是选择最优划分属性，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高。我们有很多指标来确定选择哪一个属性作为最优划分选择，下面将分别介绍：

4.3.1. 信息增益

• 信息熵(information entropy)是度量样本集合纯度最常用的一种指标。下面是信息熵的定义公式：

  其中$p_k$表示第k类样本在样本集D中所占比例，信息熵越小表示D的纯度越高。

• 假设离散属性a有V个可能的取值${a^1,a^2…a^V}$,那么我们可以计算出在使用a作为划分属性前后的信息熵差别，也就是信息增益(information gain)：

  对每一个子结点$D^v$都赋予权重同时相加。

• 著名的ID3决策树学习算法就是以信息增益作为准则来选择划分属性，我们希望找到信息增益最大的属性。

• 书上使用信息增益划分的例子：

4.3.2. 增益率

• 信息增益对可取值数目较多的属性有所偏好，比如我们使用编号这一属性来划分，每一个编号都只有一个样本，那么信息增益肯定增大了，但是决策树的泛化能力显然下降了。

• 增益率(gain ratio)，我们通过对信息增益除以IV来平衡属性数目带来的影响，增益率的定义如下：

  IV(intrinsic value)的定义如下：

  IV是属性a的固有值，属性a可取的数值数目越多，那么IV就越大

• 但是增益率也有问题，那就是对于可取值数目较少的属性有偏好，所以著名的C4.5决策树算法并不是直接使用增益率，而是先从候选划分属性中找出信息增益高于平均水平的属性，然后再从中选择增益率最高的属性

4.3.3. 基尼指数

• CART决策树使用基尼指数来选择划分属性
• 数据集D的纯度定义如下

  直观来说，Gini反映了从数据集随便抽取两个样本，它们类别不一致概率

• 基尼指数定义如下：

  很明显，我们希望基尼指数越小越好，所以我们选择基尼指数最小的属性最为最优划分属性。

4.4. 剪枝处理

• 不难发现，上面对于属性的划分很容易过拟合，所以针对过拟合现象，决策树选择剪枝(pruning)来对付过拟合
• 剪枝就是去掉一些分支来降低过拟合的风险，剪枝可以分为预剪枝和后剪枝
• 预剪枝(prepruning):在决策树生成的过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分
• 后剪枝(postpruning):从训练集生成了一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

4.4.1. 预剪枝

• 如何判断决策树泛化性能？可以使用留出法预留一部分数据用作验证集进行性能评估，性能度量可以用之前介绍的那些，本小节使用精度作为性能度量
• 预剪枝生成的决策树：

• 可以发现预剪枝显著减少了分支的数量，这样可以减少决策树的训练时间开销。但是这样也有一个问题，就是有些分支的当前划分虽然不能提升泛化性能，但是后续划分却有可能导致性能显著提高，这样就带来了欠拟合的风险

4.4.2. 后剪枝

• 首先生成决策树，然后对每个结点进行评估是否需要剪枝

• 虽然后剪枝决策树的欠拟合风险小，泛化性能也往往优于预剪枝决策树，但是后剪枝的时间开销大

4.5. 连续与缺失值

4.5.1. 连续值处理

• 到目前为止仅讨论了基于离散属性来生成决策树，但是现实学习任务中通常会遇到连续属性
• 很明显连续属性不能根据连续属性的可取值来对结点进行划分，我们需要用到连续属性离散化的技术，最简单的策略是二分法
• 给定样本集D和和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大排序，然后每次选择每两个数的中位数t作为划分点，那么连续值就可以当作离散值来处理了，分出的子样本集分别记作$D_t^+$和$D_t^-$

• 划分结果：

• 需要注意的是：连续属性在划分后并不会被丢失，后续划分仍然可以使用

4.5.2. 缺失值处理

• 在实际数据中一般都有很多缺失值，所以我们需要考虑如何对含有缺失值的数据进行学习
• 给几个定义：$\tilde{D}$表示D中属性a上没有缺失值的样本子集，假设属性值a可取值{$a^1$,$a^2$…$a^V$}, $\tilde{D}^v$表示$\tilde{D}$中属性值a取值为$a^v$的子集，$\tilde{D}_k$表示样本子集，我们为每个样本赋予权重$\omega_x$(决策树开始阶段，根结点中权重初始化为1)并定义：

• 直观地看，对属性a，$\rho$表示无缺失值样本所占比例，$\tilde{p}_k$表示无缺失样本中第k类样本所占的比例，$\tilde{r}_v$表示无缺失值样本在属性上取值为$a^v$所占的比例

• 那么我们可以将信息增益的公式推广为

 

• 那么对于那些在该属性上缺失的值如何处理呢？分两种情况：若样本$x$在划分属性$a$上的取值己知, 则将$x$划入与其取值对应的子结点，且样本权值在于结点中保持为$\omega_x$, 若样本$x$在划分属性$a$上的取值未知，则将$x$同时划入所有子结点, 且样本权值在与属性值$a^v$对应的子结点中调整为$\tilde{r}_v*\omega_x$，直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

• C4.5就是使用了上述的解决方法

4.6. 多变量决策树

• 若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界，决策树生成的分类边界有个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成

• 这样的决策树由于要进行大量的属性测试，预测时间开销会很大，所以我们希望使用如下图红线所示的斜划分。多变量决策树就是能实现这样斜划分甚至更复杂划分的决策树

• 以实现斜划分的决策树为例，非叶结点不再是仅对某一个属性，而是对属性的线性组合进行测试

4.7. 阅读材料

• 多变量决策树算法主要有OC1，还有一些算法试图在决策树的叶结点上嵌入神经网络，比如感知机树在每个叶结点上训练一个感知机

• 有些决策树学习算法可进行“增量学习”(incrementallearning)，即在接收到新样本后可对己学得的模型进行调整，而不用完全重新学习。主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构，代表性算法ID4、ID5R、ITI等。增量学习可有效地降低每次接收到新样本后的训练时间开销，但多步增量学习后的模型会与基于全部数据训练而得的模型有较大差别。

5. 第5章 神经网络

5.0. 思维导图

5.1. 神经元模型

• 神经网络定义: 神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应
• 神经网络中最基本的成分是神经元模型(neuron)
• M-P神经元模型:

• 在这个模型中，神经元接收来自n个其他神经元传递过来的输入信号，这些输入信号通过带权重的连接进行传递，神经元接收到的总输入值将与神经元的阈值进行比较，然后通过激活函数处理以产生神经元的输出
• 激活函数: 有阶越函数和Sigmoid函数等等

5.2. 感知机与多层网络

• 感知机(perceptron)由两层神经元组成，如下图所示

• 权重$\omega_i$以及阈值$\theta$可通过学习得到

• 感知机的学习规则非常简单，对训练样例(x, y)，若当前感知机的输出为$\hat{y}$, 则感知机权重将这样调整

• 其中$\eta$称为学习率(learning rate)
• 感知机只有输出层神经元进行激活函数处理，即只拥有一层功能神经元，其学习能力非常有限
• 要解决非线性可分问题，需考虑使用多层功能神经元，比如下图，输入层和输出层之间的一层神经元被称为隐含层(hidden layer)，隐含层和输出层神经元都是拥有激活函数的功能神经元

• 多层前馈神经网络(multi-layer feedforward neural networks): 每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接

5.3. 误差逆传播算法

• 误差逆传播算法(error BackPropagation)简称BP算法，可用于很多类型的神经网络

• 误差采用均方误差:

• BP算法基于梯度下降(gradient descent)策略，以目标的负梯度方向对参数进行调整

• 学习率控制着算法每一轮迭代中的更新步长，若太大则容易振荡，太小则收敛速度又会过慢

• 上面介绍的标准BP算法每次仅针对一个训练样例更新连接权和阈值，我们也可以简单推出基于累积误差最小化的更新规则，就得到了累积BP算法
• 正是由于其强大的表达能力，BP神经网络经常遭遇过拟合，其训练误差持续降低，但测试误差却可能上升，由两种策略常用来缓解BP网络的过拟合。
  • 第一种策略是早停(early stopping): 若训练集误差降低但验证集误差升高，则停止训练
  • 第二种策略是正则化，其基本思路是在误差目标函数中增加一个用于描述网络复杂度的部分，例如连接权和阈值的平方和，那么误差目标函数变成:

5.4. 全局最小与局部极小

• 我们常常会谈到两种最优: 局部极小(local minimum)和全局最小(global minimum)
• 直观地看，局部极小解是参数空间中的某个点，其领域点的误差函数值均不小于该点的函数值
• 全局最小解是指参数空间中所有点的误差函数值均不小于该点的误差函数值

• 在现实任务中，人们常采用以下策略来试图跳出局部极小，从而进一步实现全局最小
  • 以多组不同参数值初始化多个神经网络
  • 使用“模拟退火”(simulated annealing)技术，每一步都以一定概率接受比当前解更差的结果，从而有助于跳出局部极小
  • 随机梯度下降，即每次使用随机的样本进行误差计算

5.5. 其他常见神经网络

5.5.1. RBF网络

• RBF(Radial Basis Function, 径向基函数)网络是一种单隐层前馈神经网络，它使用径向基函数作为隐层神经元激活函数，而输出层则是对隐层神经元输出的线性组合
• 具有足够多隐层神经元的RBF网络能以任意精度逼近任意连续函数

5.5.2. ART网络

• 竞争型学习(competitive learning)是神经网络中一种常用的无监督学习策略，在使用该策略时，网络的输出神经元相互竞争，每一时刻仅有一个竞争获胜的神经元被激活，其他神经元的状态被抑制。这种机制亦称胜者通吃(winner-take-all)原则
• ART(Adaptive Resonance Theory，自适应谐振理论)网络是竞争型学习的重要代表。该网络由比较层、识别层、识别阔值和重置模块构成。其中，比较层负责接受输入样本，并将其传递给识别层神经元。识别层每个神经元对应一个模式类，神经元数目可在训练过程中动态增长以增加新的模式类

5.5.3. SOM网络

• SOM(Self-Organizing Map，自组织映射)网络是一种竞争学习型的无监督神经网络，它能将高维输入数据映射到低维空间(通常为二维) ，同时保持输入数据在高维空间的拓扑结构，即将高维空间中相似的样本点映射到网络输出层中的邻近神经元

5.5.4. 级联相关网络

• 一般的神经网络模型通常假定网络结构是事先固定的，训练的目的是利用训练样本来确定合适的连接权、阈值等参数。与此不同，结构自适网络则将网络结构也当作学习的目标之一，并希望能在训练过程中找到最符合数据特点的网络结构-级联相关(Cascade-Correlation)网络是结构自适应网络的重要代表

5.5.5. Elman网络

• 与前馈神经网络不同递归神经网络(recurrent neural networks)允许网络中出现环形结构，从而可让一些神经元的输出反馈回来作为输入信号。这样的结构与信息反馈过程，使得网络在t时刻的输出状态不仅与t时刻的输入有关，还与t-1时刻的网络状态有关，从而能处理与时间有关的动态变化
• Elman网络是最常用的递归神经网络之一，其结构如图所示，它的结构与多层前馈网络很相似，但隐层神经元的输出被反馈回来，与下一时刻输入层神经元提供的信号一起，作为隐层神经元在下一时刻的输入。隐层神经元通常采用Sigmoid激活函数，而网络的训练则常通过推广的BP算法进行

5.5.6. Boltzmann机

• 神经网络中有一类模型是为网络状态定义一个能量(energy)，能量最小化时网络达到理想状态，而网络的训练就是在最小化这个能量函数。Boltzmann机就是一种基于能量的模型(energy-based model)，常见结构如图所示，其神经元分为两层:显层与隐层。显层用于表示数据的输入与输出，隐层则被理解为数据的内在表达

5.6. 深度学习

• 理论上来说，参数越多的模型复杂度越高、 “容量” (capacity) 越大，这意味着它能完成更复杂的学习任务。但一般情形下，复杂模型的训练效率低，易陷入过拟合，因此难以受到人们青睐。而随着云计算、大数据时代的到来，计算能力的大幅提高可缓解训练低效性，训练数据的大幅增加则可降低过拟合风险，因此，以”深度学习”(deep learning)为代表的复杂模型开始受到人们的关注。
• 无监督逐层训练(unsupervised layer-wise training)是多隐层网络训练的有效手段，其基本思想是每次训练一层隐结点，训练时将上一层隐结点的输出作为输入，向本层隐结点的输出作为下一层隐结点的输入，这称为预训练(pre-training);在预训练全部完成后，再对整个网络进行微调(fine-tuning)训练
• 另一种节省训练开销的策略是权共享，即让一组神经元使用相同的连接权，比如CNN
• 以往在机器学习用于现实任务时，描述样本的特征通常需由人类专家来设计，这称为特征工程(feature engineering)，深度学习则通过机器学习技术自身产生好特征
• 神经网络是一种难以解释的黑箱模型

6. 第6章 支持向量机

6.0. 思维导图

6.1. 间隔与支持向量

• 给定训练样本集$D={(x_1, y_1),(x_2, y_2),…,(x_m, y_m)}$, 其中$y_i\in${$-1, +1$}, 也就是一个传统的分类问题。分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开，但能将训练样本分开的划分超平面可能有很多，如下图

• 直观上看，应该去找位于两类训练样本正中间的划分超平面，因为该划分超平面对训练样本局部扰动的容忍性最好
• 在样本空间中，划分超平面可通过如下线性方程来描述: $\omega^Tx+b=0$, 其中$\omega$为法向量, 决定了超平面的方向, b为位移项, 决定了超平面与原点的距离, 显然划分超平面可被法向量$\omega$和b确定
• 样本空间中任意点x到超平面的距离可写为

• 假设超平面能将训练样本正确分类, 即对($x_i, y_i$)$\in$D, 我们有以下结果:

• 支持向量: 距离超平面最近的几个训练样本点使得上述条件等号成立，它们就被称为支持向量(support vector), 两个异类支持向量到超平面的距离之和为间隔$\gamma$

• 图示:

• 欲找到具有最大间隔的划分超平面，也就是找到能满足约束的最大的$\gamma$

• 为了最大化间隔，仅需最大化||$\omega$||$^{-1}$, 这等价于最小化||$\omega$||$^{2}$, 于是上述式子可重写为:

• 这就是支持向量机(Support Vector Machine, SVM)的基本型

6.2. 对偶问题

• 我们注意到SVM的基本型本身是一个凸二次规划问题⁶, 能直接用现成的优化计算包求解，但我们可以有更高效的方法

• 对上述式子使用拉格朗日乘子法⁷可得到其对偶问题，则该问题的拉格朗日函数可写为

• 其中$\alpha$=($\alpha_1$;$\alpha_2$…;$\alpha_m$), 令L($\omega$, b, $\alpha$)对$\omega$和b的偏导为零可得

• 将这两个条件带入之前的拉格朗日函数中，即可将$\omega$和b消去，得到以下的对偶问题:

• 从对偶问题中解出的$\alpha_i$是拉格朗日乘子，它恰对应着训练样本($x_i$, $y_i$), 在主问题中有不等式约束，因此上述过程需满足KTT条件, 即要求:

• 解出$\alpha$后，求出$\omega$与b即可得到模型:

• 于是, 对任意训练样本($x_i$, $y_i$), 总有$\alpha_i=0$或者$y_if(x_i)=1$。若$\alpha_i=0$，则该样本将不会在最终的模型的求和中出现，也就不会对f(x)有任何影响;若$\alpha_i>0$, 则必有$y_if(x_i)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质:训练完成后, 大部分的训练样本都不需保留，最终模型仅与支持向量有关
• 那么如何求解对偶问题解出$\alpha_i$呢？这是一个二次规划问题, 可使用通用的二次规划算法求解，然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销，为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法, SMO是其中一个著名的代表
• SMO的基本思路是先固定$\alpha_i$之外的所有参数，然后求$\alpha_i$上的极值，由于存在约束$\sum_1^m\alpha_iy_i=0$,若固定$\alpha_i$之外的其他变量，则$\alpha_i$可由其他变量导出，于是SMO每次选择两个变量$\alpha_i$和$\alpha_j$，并固定其他参数。这样，在参数初始化后，SMO不断执行如下两个步骤直至收敛
  • 选取一对需更新的变量$\alpha_i$和$\alpha_j$
  • 固定$\alpha_i$和$\alpha_j$以外的参数，求解获得更新后的$\alpha_i$和$\alpha_j$
• 如何确定偏移项b呢？注意到对任意支持向量($x_s$, $y_s$)都有$y_sf(x_s)=1$:

• 其中S为所有支持向量的下标集，理论上可以选取任意支持向量来求出b，但现实任务中常采用一种更鲁棒的做法: 使用所有支持向量求解的平均值

6.3. 核函数

• 在本章前面的讨论中，我们假设训练样本是线性可分的，然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面，例如异或问题就不是线性可分的
• 对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，例如将异或问题的原始二维空间映射到一个合适的三维空间，就能找到一个合适的划分超平面。如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分

• 令$\phi(x)$表示将x映射后的特征向量，于是在特征空间中划分超平面所对应的模型可表示为

• 其中$\omega$和b是模型参数，我们有以下二次规划:

• 其对偶问题是:

• 我们观察到在对偶问题中涉及到计算$\phi(x_i)^T\phi(x_j)$, 这是样本$x_i$与$x_j$映射到特征空间之后的内积。由于特征空间维数可能很高，甚至是无穷维，因此直接计算$\phi(x_i)^T\phi(x_j)$通常是困难的，为了避开这个障碍，可以设想这样一个函数:

• 即$x_i$与$x_j$在特征空间的内积等于它们在原始样本空间中通过函数$\kappa(·,·)$计算的结果, 有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积，于是式子可重写为

• 求解后可得到:

• 上面式子显示出模型最优解可通过训练样本的核函数展开，这一展式亦称支持向量展式
• 显然，若已知合适映射$\phi(·)$的具体形式，则可写出核函数$\kappa(·,·)$，但在现实任务中我们通常不知道$\phi(·)$是什么形式，那么合适的核函数是否一定存在呢？什么样的函数能做核函数呢？我们有以下定理:

• 核函数选择成为支持向量机的最大变数，若核函数选择不合适，则意味着将样本映射到一个不合适的特征空间，很可能导致性能不佳
• 常用核函数:

• 此外，还可通过函数组合得到:
  • 两个核函数的线性组合
  • 两个核函数的直积
  
  • 若$\kappa_1$为核函数，则对任意函数g(x):
  

  也是核函数

6.4. 软间隔与正则化

• 在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分
• 缓解该问题的一个方法是允许支持向量机在一些样本上出错，为此，要引入软间隔(soft margin)的概念
• 具体来说，前面介绍的支持向量机形式都是要求所有样本均满足约束，即所有样本必须划分正确，这称为硬间隔，而软间隔则允许某些样本不满足约束
• 优化目标可写为:

• 其中C>0是一个常数，$l_{0/1}$是0/1损失函数

• 显然，当C无穷大时，上面式子迫使所有样本均满足约束，当C取有限值时，式子允许一些样本不满足约束
• 然而0/1损失函数非凸、非连续，数学性质不太好，于是人们通常用其他一些函数来替代它，下面给出三个常用的替代损失函数：

• 若采用hinge损失，则式子变成:

• 引入松弛变量$\xi_i$≥0，可将式子重写为

• 这就是常用的软间隔支持向量机，可以看出每个样本都有一个对应的松弛变量，用以表征样本不满足约束的程度
• 这仍是一个二次规划的问题，于是，通过拉格朗日乘子法可得到拉格朗日函数:

• 其中$\alpha_i≥0$, $\mu_i≥0$是拉格朗日乘子
• 偏导为0后可得到对偶问题:

• KTT条件:

• 可以发现软间隔支持向量机的最终模型仅与支持向量有关
• 我们还可以把0/1损失函数替换成别的替代损失函数以得到其他学习模型，这些模型的性质与所用的替代函数直接相关，但它们具有一个共性: 优化目标中的第一项用来描述划分超平面的间隔大小，另一项用来描述训练集上的误差

• 其中$\Omega(f)$称为“结构风险”(structural risk)，用于描述模型f的某些性质;第二项$\sum_i^ml(f(x_i),y_i)$称为“经验风险”(empirical risk)，用于描述模型与训练数据的契合程度; C用于对二者进行折中。从经验风险最小化的角度来看，$\Omega(f)$表述了我们希望获得具有何种性质的模型(例如希望获得复杂度较小的模型)，这为引入领域知识和用户意图提供了途径; 另一方面，该信息有助于削减假设空间，从而降低了最小化训练误差的过拟合风险。从这个角度来说，上面的公式为“正则化”(regularization)问题，$\Omega(f)$称为正则化项，C则称为正则化常数。$L_p$范数(norm)是常用的正则化项，其中$L_2$范数$||\omega||_2$倾向于$\omega$的分量取值尽量均衡，即非零分量个数尽量稠密，而$L_0$范数$||\omega||_0$和$L_1$范数$||\omega||_1$则倾向于$\omega$的分量尽量稀疏，即非零分量个数尽量少

6.5. 支持向量回归

• 现在我们来考虑回归问题，给定训练样本$D={(x_1, y_1), (x_2, y_2), …, (x_m, y_m))}，希望学得一个形如$f(x)=\omega^Tx+b$的回归模型，使得f(x)与y尽可能接近。
• 传统回归模型通常直接基于输出f(x)与真实输出y之间的差别来计算损失，当且仅当f(x)与y完全相同时，损失才为0。与此不同，支持向量回归(Support Vector Regression, 简称SVR)假设我们能容忍f(x)与y之间最多有$\epsilon$的偏差，如下图所示，若样本落入此间隔带，则被认为预测正确

• 于是SVR问题可形式化为:

• 其中C为正则化常数，$l_{\epsilon}$是$\epsilon$-不敏感损失函数:

• 引入松弛变量$\xi_i$和$\hat{\xi_i}$，可将上述式子重写为:

• 类似地，通过引入拉格朗日乘子可得到拉格朗日函数:

• 偏导为零得到对偶问题:

• KTT条件:

• 将上述条件代入，SVR的解形如:

• 能使式子中$(\hat{\alpha}_i-\alpha_i)≠0$的样本即为SVR的支持向量，它们必落在$\epsilon$-间隔带之外
• 由KTT条件可看出，对每个样本($x_i, y_i$)都有$(C-\alpha_i)\xi_i=0$且$\alpha_i(f(x_i)-y_i-\epsilon-\xi_i)=0$，于是在得到$\alpha_i$后，若0<$\alpha_i$<C, 则必有$\xi_i=0$,进而有:

• 理论上说，可任意选取满足的$\alpha_i$来得到b，但是实践中常采用一种更鲁棒的方法: 选取多个满足0<$\alpha_i$<C的样本通过上述公式求解b后取平均值
• 若考虑特征映射，则:

6.6. 核方法

• 若不考虑偏移项b，则无论SVM还是SVR，学得的模型总能表示成核函数的线性组合。不仅如此，事实上我们有下面这个称为“表示定理”(representer theorem)的更一般的结论

• 人们发展出一系列基于核函数的学习方法，统称为核方法，最常见的是通过引入核函数来将线性学习器拓展为非线性学习器
• 支持向量机是针对二分类任务设计的，对多分类任务要进行专门的推广

7. 第7章 贝叶斯分类器

7.0. 思维导图

7.1. 贝叶斯决策论

• 贝叶斯决策论是概率框架下实施决策的基本方法。对于分类任务来说，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。
• 以多分类任务为例: 假设有N种可能的类别标记，即$Y=${$c_1, c_2,…,c_N$}, $\lambda_{ij}$是将真实标记为$c_j$的样本误分类为$c_i$所产生的损失。基于后验概率⁸$P(c_i|x)$可获得将样本x分类为$c_i$所产生的期望损失，即在样本上的条件风险:

• 我们的任务是寻找一个判定准则h: X -> Y以最小化总体风险

• 显然，对每个样本x，若h能最小化条件风险R(h(x)|x)，则总体风险R(h)也将被最小化。这就产生了贝叶斯判定准则: 为最小化总体风险，只需在每个样本上选择那个能使条件风险R(c|x)最小的类别标记，即:

• 此时，$h^*$称为贝叶斯最优分类器，与之对应的总体风险R($h^*$)称为贝叶斯风险。1-R($h^*$)反映了分类器所能达到的最好性能。

• 具体来说，若目标是最小化分类错误率，则误判损失$\lambda_{ij}$可写为:

• 此时条件风险为:

• 于是，最小化分类错误率的贝叶斯最优分类器为:

• 即对每个样本，选择能使后验概率$P(c|x)$最大的类别标记

• 不难看出，欲使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率$P(c|x)$。然而，在现实任务中这通常难以直接获得，从这个角度来看，机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率$P(c|x)$。大体来说，主要有两种策略: 给定x，可通过直接建模$P(c|x)$来预测c，这样得到的是判别式模型。也可以先对联合概率分布P(x,c)建模，然后再由此获得$P(c|x)$，这样得到的是生成式模型。

• 对于生成式模型来说，必须考虑:

• 基于贝叶斯定理，$P(c|x)$可写为:

• 其中，P(c)是类先验概率，P(x|c)是样本x相对于类标记c的类条件概率，或称为似然(likelihood)。P(x)是用于归一化的证据因子，P(x)对所有类标记均相同。因此估计P(c|x)的问题就转化为如何基于训练数据D来估计先验概率P(c)和似然P(x|c).
• 类先验概率P(c)表达了样本空间中各类样本所占的比例，根据大数定律，当训练集包含充足独立同分布的样本时，P(c)可通过各类样本出现的频率进行估计
• 对类条件概率P(x|c)来说，由于它涉及关于x所有属性的联合概率，直接根据样本出现的频率来估计将会遇到严重的困难，例如样本d个属性都是二值的，则样本空间将有$2^d$种可能取值，在现实应用中，这个值往往远大于训练样本数m，因此不能用频率估计概率

7.2. 极大似然估计

• 估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布进行参数估计。具体来说，记关于类别c的类条件概率为P(x|c)，假设P(x|c)具有确定的形式且被参数向量$\theta_c$唯一确定，则我们的任务就是利用训练集D估计参数$\theta_c$
• 概率模型的训练过程就是参数估计的过程，统计学界的两个学派提出了不同的解决方案，频率主义学派认为参数虽然未知，但却客观存在固定值，因此可以通过优化似然函数等准则来确定参数值。本节介绍源自频率主义学派的极大似然估计⁹

• 令$D_c$表示训练集D中第c类样本组成的集合，假设这些样本是独立同分布的，则参数$\theta_c$对于数据集$D_c$的似然是:

• 对$\theta_c$进行极大似然估计，就是去寻找最大化似然$P(D_c|\theta_c)$的参数值$\hat{\theta_c}$
• 上述似然中的连乘操作易造成下溢，通常使用对数似然(log-likelihood)

• 此时参数$\hat{\theta_c}$的极大似然估计$\hat{\theta_c}$为

• 例如，再连续属性情形下，假设概率密度函数p(x|c)~N($\mu_c, \sigma_c^2$)， 则参数$\mu_c$和$\sigma_c^2$的极大似然估计为:

• 也就是说，通过极大似然法得到的正态分布均值就是样本均值，方差就是$(x-\hat{mu_c})(x-\hat{\mu_c})^T$的均值
• 虽然这种参数化方法虽然能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布

7.3. 朴素贝叶斯分类器

• 不难发现，基于贝叶斯公式来估计后验概率P(c|x)的主要困难在于: 类条件概率P(x|c)是所有属性上的联合概率，难以从有限的训练样本直接估计而得。为了避开这个障碍，朴素贝叶斯分类器(naïve Bayes classifier)采用了属性条件独立性假设
• 基于这个假设，贝叶斯公式可以重写为:

• 对于所有类别来说P(x)相同，因此基于贝叶斯判定准则有:

• 对于P(c)和$P(x_i|c)$都用频率估计概率(对于离散属性而言)，对于连续属性则考虑概率密度函数为正态分布，参数由极大似然估计求出
• 但是这种方法存在一个问题: 如果某个属性值在训练样本中没有出现过，那么对概率进行连乘的时候会乘上一个零，这样显然不太合理。解决方法: 可以在估计概率值时进行平滑处理，常用拉普拉斯修正。具体来说，令N表示训练集D中所有的类别数，$N_i$表示第i个属性可能的取值数，则修正为:

• 在现实任务中朴素贝叶斯分类器有多种使用方式。例如，若任务对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来，这样在进行预测时只需”查表”即可进行判别;若任务数据更替频繁，则可采用”懒惰学习”(lazy learning)方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值;若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习

7.4. 半朴素贝叶斯分类器

• 朴素贝叶斯的假设在现实任务中往往难以实现，人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为半朴素贝叶斯分类器的方法
• 半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需要进行完全联合概率，又不至于彻底忽略了比较强的属性依赖关系。独依赖估计(one-dependent estimator 简称ODE)是半朴素贝叶斯分类器最常用的一种策略。独依赖就是假设每个属性在类别之外最多仅依赖于一个其他属性，即:

• 其中$pa_i$为属性$x_i$所依赖的属性，称为$x_i$的父属性，此时如果每个属性的父属性已知，则可采用之前的方法估计概率值，但是问题的关键在于如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器
• 最直接的做法是假设所有属性都依赖于同一个属性，称为超父，然后通过交叉验证等模型选择方法来确定超父属性，由此形成了SPODE(super parent ODE)方法。例如下图中，$x_1$是超父属性

• 另一种TAN(Tree Augmented naïve Bayes)则是最大带权生成树算法的基础上，通过以下步骤将属性间依赖关系简约为如图所示的树形结构:
  • 1.计算任意两个属性间的条件相互信息
  
  • 2.以属性为结点构建完全图，任意两个结点之间边的权重设为$I(x_i,x_j)|y$
  • 3.构建此完全图的最大带权生成树，挑选根变量，将边置为有向
  • 4.加入类别结点y，增加从y到每个属性的有向边

• TAN实际保留了强相关属性之间的依赖性
• AODE(averaged one-dependent estimator)是一种基于集成学习机制、更为强大的独依赖分类器，于SPODE通过模型选择确定超父属性不同，AODE尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果:

• 与朴素贝叶斯分类器类似，AODE的训练过程也是计数，即在训练数据上对符合条件的样本进行计数的过程
• 既然将属性条件独立性假设放松为独依赖假设可能获得泛化性能的提升，那么，能否通过考虑属性间的高阶依赖来进一步提升泛化性能呢?也就是说，将式中的属性$pa_i$替换为包含k个属性的集合$pa_i$，从而将ODE拓展为kDE。需注意的是，随着k的增加，准确估计概率$P(x_i|y,pa_i)$所需的训练样本数量将以指数级增加。因此，若训练数据非常充分，泛化性能有可能提升;但在有限样本条件下，则又陷入估计高阶联合概率的泥沼

7.5. 贝叶斯网

• 贝叶斯网亦称信念图，它借助有向无环图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合概率分布，一个贝叶斯网B由结构G和参数$\Theta$两部分组成，即$B=<G,\Theta>$

7.5.1. 结构

• 贝叶斯网结构有效地表达了属性间的条件独立性，给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是联合概率分布定义为:

• 上图中，$x_3$和$x_4$在给定$x_1$的取值时独立，简记为$x_3$⊥$x_4$|$x_1$
• 下图给出了贝叶斯网的三个变量之间的典型依赖关系

• 在顺序结构中，给定x的值，则y与z条件独立。V型结构(V-structure)亦称冲撞的结构，给定子结点$x_4$的取值，$x_1$与$x_2$必不独立，奇妙的是，若$x_4$的取值完全未知，则V型结构下$x_1$和$x_2$却是相互独立的，我们做一个简单的验证:

• 这样的独立性称为边际独立性，记为$x_1$╨$x_2$
• 为了分析有向图中变量间的条件独立性，可使用有向分离，将有向图变为无向图:
  • 找出有向图中的所有V型结构，在V型结构的两个父结点之间加上一条无向边
  • 将所有有向边改为无向边
• 这样产生的无向图称为道德图。基于道德图能直观、迅速地找到变量间的条件独立性。假定道德图中有变量x, y和变量集合z={$z_i$}，若变量x和y能在图上被z分开，即从道德图中将变量集合z去除后，x和y分属两个连通分支，则称变量x和y被z有向分离，x⊥y|z成立

7.5.2. 学习

• 若网络结构已知，即属性间的依赖关系已知，则贝叶斯网的学习过程相对简单，只需要通过对训练样本计数，估计出每个结点的条件概率表即可。但在现实应用中我们往往并不知晓网络结构，于是，贝叶斯网学习的首要任务就是根据训练数据集来找出结构最”恰当”的贝叶斯网。”评分搜索”是求解这一问题的常用办法。具体来说，我们先定义一个评分函数(score function)，以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。显然，评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好
• 细节参见书中

7.5.3. 推断

• 贝叶斯网训练好之后就能用来回答”查询”(query)，即通过一些属性变量的观测值来推测其他属性变量的取值。例如在西瓜问题中，若我们观测到西瓜色泽青绿、敲声烛响、根蒂蜷缩，想知道它是否成熟、甜度如何。这样通过已知变量观测值来推测待查询变量的过程称为”推断”(inference)，已知变量观测值称为”证据” (evidence)
• 最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，不幸的是，这样的精确推断已被证明是NP难，在现实应用中，贝叶斯网的近似推断常使用吉布斯采样来完成

7.6. EM算法

• 在前面的讨论中，我们一直假设训练样本所有属性变量的值都已被观测到，即训练样本是完整的，但在现实应用中往往会遇到不完整的训练样本，在这种存在未观测变量的情形下，是否仍能对模型参数进行估计呢？未观测变量的学名是隐变量(latent variable)
• 令X表示已观测变量集，Z表示隐变量集，$\Theta$表示模型参数，若欲对$\Theta$做极大似然估计，则应最大化对数似然:

• 然而由于Z是隐变量，上式无法直接求解，因此我们可通过对Z计算期望，来最大化已观测数据的对数边际似然(marginal likelihood)

• EM(Expectation-Maximization)算法是常用的估计隐变量的利器，它是一种迭代式的方法。其基本想法是:若参数$\Theta$己知，则可根据训练数据推断出最优隐变量Z的值(E步);反之，若Z的值已知，则可方便地对参数$\Theta$做极大似然估计(M步)
• 于是，以初始值$\Theta^0$为起点，可迭代执行以下步骤直至收敛:
  • 基于$\Theta^t$推断隐变量Z的期望，记为$Z^t$;
  • 基于已观测变量X和$Z^t$对参数$\Theta$做极大似然估计，记为$\Theta^{t+1}$;
• 这就是EM算法的原型，进一步，若我们不是取Z的期望，而是基于$\Theta^t$计算隐变量Z的概率分布$P(Z|X,\Theta^t)$, 则算法的步骤为:

---

Quehry

Student

Comments

  Write a comment ...