机器学习导论

总结►机器学习 , 评论

一、机器学习概论

机器学习方法三要素

方法模型策略算法

1. 模型

模型就是要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。

2. 策略

机器学习需要考虑按照什么准则学习或选择最优的模型。机器学习的目标在于从假设空间中选择最优模型。

损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

1. 损失函数和风险函数

监督学习问题是在假设空间 中选取模型 作为决策函数，对于给定的输入 ，由 给出相应的输出 ，这个输出的预测值 和真实值 可能一致也可能不一致，用一个损失函数或代价函数来度量预测错误的程度。损失函数是 和 的非负实值函数，记作

损失函数值越小，模型就越好。由于模型的输入输出 是随机变量，遵循联合分布 ，所以损失函数的期望是 这是理论上模型 关于联合分布 的平均意义下的损失，称为风险函数或期望损失

给定一个训练数据集 模型 关于训练数据集的平均损失称为经验风险或经验损失 根据大数定律，当样本容量 区域无穷时，经验风险 趋于经验风险 。但是由于现实中训练样本数目有限，所以用经验风险估计期望风险常常不理想，要对经验风险进行一定矫正。这就关系到监督学习两个基本策略：经验风险最小化和结构风险最小化。

2. 经验风险最小化与结构风险最小化

经验风险最小化的策略认为，经验风险最小的模型是最优的模型。即求解最优化问题 但是当样本容量很小时，经验风险最小化的学习效果未必很好，会产生“过拟合”现象

结构风险最小化是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化。结构风险在经验风险上加上不出模型复杂度的正则化项或罚项。在假设空间、损失函数及训练数据集确定的情况下，结构风险的定义是 其中 为模型的复杂度，是定义在假设空间 上的泛函。

是系数，用以权衡经验风险和模型复杂度。

结构风险最小化的策略认为结构风险最小的模型是最优的模型，即求解最优化问题

3. 算法

算法是指学习模型的具体计算方法。机器学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要考虑用什么样的计算方法求解最优模型。这时机器学习问题归结为最优化问题，机器学习的算法称为求解最优化问题的算法。

泛化性

学习方法的泛化能力是指该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。现实中采用最多的是通过测试误差来评价学习方法的泛化能力。但这种评价依赖于有限的测试数据集，可能不可靠。机器学习理论试图从理论上对学习方法的泛化能力进行分析。

若学到的模型是 ，那么用这个模型对位置数据预测的误差即为泛化误差 泛化误差反映了学习方法的泛化能力，如果一种方法学习的模型比另一种方法学习的模型具有更小的泛化误差，那么这种方法就更有效。事实上，泛化误差就是所学习到的模型的期望风险。

模型选择

当假设空间含有不同复杂度（如不同参数个数）的模型时，就要面临模型选择的问题。我们希望选择或学习一个合适的模型。如果在假设空间中存在真模型，那么所选择的模型应逼近镇魔性。具体地，所选择的模型要与真模型的参数个数相同，所选择的模型的参数向量与真模型的参数向量相近。

若一味追求提高对训练数据的预测能力，所选模型的复杂度往往会比真模型更高，这种现象称为过拟合。过拟合是指学习时选择的模型所包含的参数过多，以至于出现这一模型对已知数据预测的很好，但未知数据预测很差的现象。可以说模型选择旨在避免过拟合并提高模型的预测能力。

当模型复杂度增大时，训练误差会逐渐减少并趋向于 ；而测试误差会先减小，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。这样在学习时就要防止过拟合，进行最优的模型选择，即选择复杂度适当的模型，以达到使训练误差最小的学习目的。

正则化与交叉验证

模型选择的典型方法是正则化。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项或罚项。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值越大。比如正则化项可以是模型参数向量的范数。

例如，在回归问题中，损失函数是平方损失，正则化项可以是参数向量的 范数 也可以是参数向量的 范数 另一项常用的模型选择方法是交叉验证。

在许多实际应用中数据是不足的。为了选择好的模型，可以采用交叉验证方法。交叉验证的基本想法是重复地使用数据，把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试、以及模型选择

  1. 简单交叉验证

    简单交叉验证方法时：首先随机地将已给数据分为两部分，一部分非作为训练集另一部分作为测试集；然后用训练集在各种条件下（例如，不同参数个数）训练模型，从而得到不同的模型；在测试机上评价各个模型的测试误差，选出测试误差最小的模型

  2. S 折交叉验证

    应用最多的是 S 折交叉验证：首先随机地将已给数据分为 S 个互不相交，大小相同的子集；然后利用 S-1 个子集的数据训练模型，利用余下的子集测试模型；将这一过程对所有 S 中选择重复进行；最后选出 S 次评测中平均测试误差最小的模型

  3. 留一交叉验证

    S 折交叉验证的特殊情形是 S=N，称为留一交叉验证，往往在数据缺乏的情况下使用。

分类问题

准确率与召回率

二、感知机

感知机学习算法是对以下最优化问题的算法。给定一个训练数据集 其中 ，求参数 ，使其为一下损失函数极小化问题的解 其中， 为误分类点的集合

感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先，任意选取一个超平面 ，然后用梯度下降法不断地极小化目标函数。极小化过程不是一次使 中而又误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合 是固定的，那么损失函数 的梯度由 随机选取一个误分类点 ，对 进行更新 式中 是步长，在机器学习中又称为学习率

三、支持向量机

给定线性可分训练数据集，通过间隔最大化或等价地求解相应凸二次规划问题学习得到的分离超平面为 以及相应的分类决策函数 称为线性可分支持向量机

函数间隔

对于给定的训练数据集和超平面 ，定义超平面 关于样本点 的函数间隔为 定义超平面 关于训练数据集 的函数间隔为超平面 关于 中所有样本点 的函数间隔之最小值，即 但当 成比例时改变时超平面并没有改变，函数间隔却称为原来的两倍。

几何间隔

对于给定的训练数据集和超平面 ，定义超平面 关于样本点 的几何间隔为 定义超平面 关于训练数据集 的几何间隔为超平面 关于 中所有样本点 的几何间隔之最小值，即 ### 线性可分支持向量机学习算法原始形式

最优化问题 在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量是使约束条件式等号成立的点，即 对 的正例点，支持向量在超平面 上，对 的负例点，支持向量在超平面 上

之间的距离称为间隔。间隔依赖于分离超平面的法向量 ，等于 。 称为间隔边界

拉格朗日对偶形式

其中 为拉格朗日乘子向量

改写为如下最优化问题

例：正例点 负例点

解：对偶问题是 通过带入得到 对其求偏导并令其为 ，易知极值点 ，但该点不满足约束条件 ，所以最小值在边界取得

当 ，最小值 ；当 时，最小值

于是得

此时， 得对应的实例点 是支持向量，得到 分离超平面

分类决策函数

四、决策树

熵

熵是表示随机变量不确定性的度量。设 是一个取有限值的离散随机变量，其概率分布为 则随机变量 的熵定义为 若 ，则定义

通常，对数以 或 为底，这时单位分别称为比特或纳特

熵只依赖于 的分布，与取值无关，所以也可将 的熵记作 ，即 设有随机变量 其联合概率分布为 当熵和条件上中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵

信息增益

特征 对训练数据集 的信息增益 定义为集合 的经验熵 与特征 给定条件下 的经验条件熵 之差，即

根据信息增益的特征选择方法是：对训练数据集 ，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征

信息增益比

为防止选择信息增益作为划分特征时选择取值较多的特征的偏向性问题，使用信息增益比进行校正

定义 特征 对训练数据集 的信息增益比 定义为信息增益与训练数据集关于特征 的值的熵之比，即

其中 ， 是特征 取值的个数

例如 对于各特征对数据集 的信息增益

等等

ID3 算法

输入：训练数据集 ，特征集 阈值

输出：决策树

  1. 若 中所有实例属于同一类 ，则 为单节点树，并将类 作为该节点的类标记，返回
  2. 若 ，则 为单节点树，并将 中实例数最大的类 作为该节点的类标记，返回
  3. 否则，按照先前算法计算 中各特征对 的信息增益，选择信息增益最大的特征
  4. 如果 的信息增益小于阈值 ，则置 为单节点树，并将 中实例数最大的类 作为该节点的类标记，返回
  5. 否则，对 的每一可能值 ，依 将 分割为若干非空子集 ，将 中实例数最大的类作为标记，构建子节点，由结点及其子节点构成树 ，返回
  6. 对于第 个子节点，以 为训练集，以 为特征集，递归调用步骤 1-5，得到子树 ，返回

C4.5 算法

基本类似，只是改为以信息增益比作为选择特征

基尼指数

分类问题中，假设有 个类，样本点属于第 类的概率为 ，则概率分布的基尼指数为 对于二分类问题，样本点属于第一个类的概率是 ，则其基尼指数是 对于给定的样本集合 ，其基尼指数 如果样本集合 根据特征 是否取某一可能值 被分割为 两部分，则在特征 的条件下，集合 的基尼指数定义为 基尼指数表示集合 的不确定性，基尼指数 表示经 分割后集合 的不确定性

CART 算法

输入：训练数据集 ，停止计算的条件

输出：CART 决策树

  1. 设结点的训练数据集为 ，计算现有特征对该数据集的基尼指数。此时，对每一特征 ，对其可能取的每个值 ，根据样本点对 的测试为“是”或“否”将 分割成 两部分，利用上式计算 时的基尼指数
  2. 在所有可能的特征及其所有可能的切分点中，选择基尼指数最小的特征点及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点从现结点生成两个子节点，将训练数据集依特征分配到两个子节点中
  3. 对两个子节点递归调用步骤 1-2，直至满足停止条件

算法停止计算的条件是节点中的样本个数小于既定阈值或样本机的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征

例如

特征 的基尼指数 求特征 的基尼指数 由于 只有一个切分点，所以它们就是最优切分点

等等

五、朴素贝叶斯

朴素贝叶斯法对条件概率分布作了条件独立性的假设 朴素贝叶斯利用后验概率最大的类作为 的类输出，即 注意到分母对所有 相同，即

例如

由表计算得下列概率 对于给定的 ，计算 由于后者最大，所以

六、k 近邻

值的减小意味着整体模型变得复杂，容易发生过拟合

值过大则学习的静思误差会增大，意味着整体模型变简单

应用中一般取一个比较小的 ，采用交叉验证法选取最优的 值

kd 树的最近邻搜索

输入：已构造的 kd 树，目标点

输出： 的最近邻

  1. 在 kd 树中找出包含目标点的叶结点：从根节点出发根据切分点坐标和 当前维坐标的大小递归访问 kd 树
  2. 以此叶节点为“当前最近点”
  3. 递归往上回退
    1. 如果当前结点保存的实例点比当前点距离目标点更近，则以该实例点为“当前最近点”
    2. 检查“当前最近点”的父节点的另一个子节点的区域是否有更近的点，具体的：检测该区域与以目标点为球心，当前最近距离为半径的超球体是否相交。若相交则移动到另一子节点递归最近邻搜索。不相交向上回退
  4. 回退到根节点时搜索结束。最后的“当前最近点”即 的最近邻点

七、聚类

类或促的定义

设 为给定的整数，若对于集合 中任意两个样本 ，有 则 为一个类或簇

k 均值聚类

首先采用欧氏距离平方作为样本之间的距离 然后定义样本与其所属的类的中心之间的距离的综合为损失函数 k 均值聚类就是求解最优化问题 事实上其最优解且解问题是 NP Hard，现实中采用迭代法解决

输入： 个样本的集合

输出：样本集合的聚类

  1. 初始化。领 ，随机选择 个样本点作为初始聚类中心
  2. 对样本进行聚类。对固定的类中心，计算每个样本到类中心的距离，将每个样本支配到与其最近的中心的类中，构成聚类结果
  3. 计算新的类中心。对聚类结果 ，计算当前各个类中的样本的均值，作为新的类中心
  4. 如果迭代收敛或符合停止条件，输出 ；否则令 ，返回第二步

可以带计算器

不知不觉Acmer & Student

Never Settle