搜广推学习之路（一）

研0，尝试零基础转搜广推，在此记录我的学习过程，夯实基础的同时为后来者提供经验。

机器学习

快速：基础概念、树和集成学习等（尤其是逻辑回归、bagging、boosting部分） 长期：吴恩达机器学习

绪论

基本术语

首先假定我们收集了一批关于西瓜的数据，例如（色泽=青绿；根蒂=蜷缩；敲声=浊响），（色泽=乌黑；根蒂=稍蜷；敲声=沉闷），（色泽=浅白；根蒂=硬挺；敲声=清脆）

• 数据集：这组关于西瓜数据的集合即为数据集
• 样本（示例）：每条记录是关于每个西瓜的记录，称为一个样本（示例）
• 属性（特征）：色泽、根蒂、敲声描述西瓜的性质，称为属性（性质）
• 属性值（特征值）：青绿、乌黑等为属性上的取值，称为属性值（特征值）
• 属性空间（样本空间、输入空间）：将色泽、根蒂、敲声作为坐标轴，可以形成一个描述西瓜的三维空间（d个属性即为d维），称为属性空间（样本空间、输入空间）
• 特征向量：每个西瓜在属性空间中有自己的坐标位置，对应一个坐标向量，所以一个样本也称为一个特征向量
• 训练（学习）：从数据中学得模型的过程称为学习或训练，训练过程中使用的数据称为训练数据，使用的每个样本为一个训练样本，这些训练样本的集合为训练集
• 学得模型对应了数据中的某一潜在规律，故又称为假设，该潜在规律自身，称为真实或真相，机器学习的过程就是要令假设接近真相

在上述概念基础上，如果我们想要学得的模型是一个可判断西瓜是否为好瓜的模型，那么我们应在训练样本（色泽=青绿；根蒂=蜷缩；敲声=浊响）的基础上添加“结果”信息——好瓜，如（（色泽=青绿；根蒂=蜷缩；敲声=浊响），好瓜）

• 标记（label）:关于示例结果的信息（好瓜 or 坏瓜）即为标记
• 样例：有label的示例即为样例
• 标记空间（输出空间）：所有label的集合 根据预测结果的不同，我们可以将学习任务分为两大类：
• 分类：若预测的是离散值，例如好瓜、坏瓜，此类学习任务称为分类(classification)，只有两个类别的二分类任务，通常成其中一个类别为“正类”，另一个类别为“反类”
• 回归：若预测的是连续值，例如西瓜成熟度0.97、0.35，此类学习任务称为回归(regression)
• 测试：学得模型后，用其进行预测的过程称为测试，被预测的样本称为测试样本

除此之外，即使无label，我们也可以对西瓜进行聚类，将训练集中的西瓜按照其属性分为若干组，每组称为一个“簇”。例如根据色泽，可将西瓜分为深色瓜和浅色瓜等

根据训练数据是否有label，可以将学习任务大致划分为两大类监督学习和无监督学习

• 监督学习：有label，分类和回归是监督学习的代表
• 无监督学习：无label，聚类是无监督学习的代表

机器学习的目标是通过训练数据，使模型也适用于陌生数据，所以模型适用于新样本的能力就称为泛化能力

假设空间

假设空间是由输入空间到输出空间的映射的集合。 假设空间是所有假设的集合，学习过程可以看作是在假设空间中进行搜索的过程，目的是找到与训练集匹配的假设。而现实中，由于训练集有限，所以可能会有多个假设与训练集一致，即存在一个与训练集一致的“假设集合”，称之为“版本空间”。

• 具体的例子，比如针对西瓜是否为好瓜这一问题，一个假设就是一个判断规则，比如“如果色泽=青绿，根蒂=蜷缩，那么就是好瓜”或“如果根蒂=硬挺，那么是坏瓜”等，这都是假设，而所有假设构成了假设空间。

归纳偏好

在面对新样本时，模型采用版本空间中的哪一假设？这事就涉及到了采用算法的归纳偏好，不同的算法有不同的偏好。需要注意，任何一个机器学习算法都必有其归纳偏好，否则将无法产生确定的学习结果。 同时对于算法A来说，若其在某些方面比算法B好，那么必然存在一些方面B比A好。这个结论对任何算法均成立，无一例外！所以脱离实际谈论哪个算法更好是毫无意义的。

模型评估与选择

经验误差与过拟合

• 错误率：分类错误的样本数占样本总数的比例
• 精度：1-错误率，

如果在m个样本中有a个样本分类错误，那么错误率 E = a/m，精度 = 1 - E。

• 误差：更一般地，把学习器的实际预测输出与样本的真实输出之间的差异称为误差。学习器在训练集上的误差称为训练误差或经验误差，在新样本上的误差称为泛化误差。
• 过拟合：学习能力过强，把训练数据中的非普遍性特征甚至随机噪声都当成了普遍的规律来学习。
• 欠拟合：学习能力低下

评估方法

我们在选择模型时希望选择泛化误差小的模型，因此我们需要一个测试集来测试学习器对于新样本的判别能力，然后使用测试误差作为泛化误差的近似。注意，训练集和测试集要尽量互斥。 我们拥有一个数据集D（大小为m），通过以下几种方法对数据集D进行处理，从中产生训练集S和测试集T：

• 留出法：直接将数据集D划分为两个互斥的集合，其中一个作为训练集S，另一个作为测试集T，一般将约2/3 ~ 4/5的样本用于训练，剩余样本用于测试。且由于单次留出法的估计结果往往不够稳定可靠，使用留出法时一般采用若干次随机划分、重复进行试验评估后取平均值作为留出法的评估结果。
• 交叉验证法：将数据集D划分为k个大小相似的互斥子集，然后每次用k-1个子集的并集作为训练集，剩下的那个子集作为测试集，这样就可以得到k组训练、测试集，从而进行k次训练和测试，最终返回这k次测试的均值。
• 自助法：从数据集D中随机有放回地抽取m次样本，得到一个新的数据集（大小也是m），这个新的数据集可能包含重复的样本。使用这个新的数据集来训练模型，剩下的没有被抽取的样本作为测试集。（根据数学计算，大概有1/3的数据可用于测试）

性能度量

• 均方误差：在回归任务中，最常用的指标就是均方误差。

接下来介绍分类任务中常用的性能指标

• 错误率与精度：错误率是分类错误的样本数占样本总数的比例，精度是分类正确的样本数占样本总数的比例。
• 查准率(precision)、查全率(recall)与F1：查准率也叫做准确率，查全率也叫做召回率。对于二分类问题，根据分类器在测试集上的预测正确与否，将样本划分为四类：

1. TP (True Positive)：真正例，正确预测为正类的样本数量。
2. TN (True Negative)：真负例，正确预测为负类的样本数量。
3. FP (False Positive)：假正例，错误预测为正类的样本数量。
4. FN (False Negative)：假负例，错误预测为负类的样本数量。 查准率P与查全率R定义如下：

由混淆矩阵易得，查准率指模型预测为正类的样本中，实际为正类的比例，查全率指实际为正类的样本中，被模型正确预测为正类的比例。 一般来说，查全率和查准率是一对矛盾的度量，我们将查准率为纵轴，查全率为横轴作图，就可以得到查准率-查全率曲线，简称“P-R曲线”。如图，A将C完全“包住”，所以A的性能显然优于C，但对于A和B来讲，两者有交叉，无法直观比较两者的优劣，这时会采用平衡点（BEP）来度量，认为A优于B，在平衡点的基础上，进一步优化，得到更常用的F1度量。

线性回归

假设有n个样本，每个样本有d个属性，例如 x⁽ⁱ⁾ = (x₁⁽ⁱ⁾; x₂⁽ⁱ⁾; ...; x_d⁽ⁱ⁾)^T，其中x_j⁽ⁱ⁾是x⁽ⁱ⁾在第j个属性上的取值，线性模型希望学得预测函数 ŷ⁽ⁱ⁾ = w₁x₁⁽ⁱ⁾ + w₂x₂⁽ⁱ⁾ + ... + w_dx_d⁽ⁱ⁾ + b（使用ŷ⁽ⁱ⁾表示y⁽ⁱ⁾的预测值），一般写作向量形式 ŷ⁽ⁱ⁾ = w^Tx⁽ⁱ⁾ + b，其中w = (w₁; w₂; ...; w_d)^T，当w和b确定时，线性模型也就确定了。 由于实际情况中得到ŷ⁽ⁱ⁾ = y⁽ⁱ⁾是很难的，所以我们需要一个度量指标来判断模型对数据的拟合程度。损失函数就可以量化目标的实际值与预测值之间的差距。通常我们使用非负数来作为损失，数值越小损失越小拟合程度越好，当完美预测时损失值为0。回归问题中最常用的损失函数为平方误差函数，对于样本i，预测值为 ŷ⁽ⁱ⁾，真实标签值为 y⁽ⁱ⁾，那么平方误差SE就表示为

（注意：这里的1/2不会带来本质差别，其存在的意义是之后对损失函数求导后可令系数为1，在形式上简单一些） 上述为度量一个样本，为度量模型在整个数据集上的质量，我们需要计算训练集在n个样本上的损失均值，即均方误差MSE为： 有了度量指标，那么我们的目标就是找到w和b使得训练集上的总损失最小：

接下来为实现损失最小化，首先，我们将偏置b合并到参数w中，令b = w_d + 1,合并方法是在包含所有参数的矩阵中附加一列，如图所示。 首先为参数的初始状态： 我们将b合并到w中： 我们将所有样本合并起来： 令X = x^T： 所以均方误差可转换为下列形式：

因此我们的目标就是最小化||Xw − y||²，我们令MSE关于w的导数为0可以得到解析解，（正规方程，这里不再赘述，感兴趣的可以自行了解），但实际情况不是所有问题都有解析解存在，所以我们采用梯度下降的方法。

梯度下降的思想：开始时随机选择w和b，计算损失函数，然后寻找下一个能让损失函数减少最多的参数组合（当前参数的梯度（即偏导数的向量）的反方向，梯度指明了损失函数最陡峭上升的方向。），持续这么做可以找到一个局部最小值，但这个值不一定为全局最小值，所以采取不同的初始参数组合，可能会得到不同的局部最小值。

随机梯度下降（SGD）：在一次SGD更新中，随机选取一个训练样本(x⁽ⁱ⁾, y⁽ⁱ⁾)用这个样本计算w的梯度并更新。

其中，α为学习率，决定了每次更新的步长。

在我们实际应用中，我们会将所有样本都遍历一遍来得到最后的w，这就导致执行速度很慢，因此产生了变体小批量随机梯度下降，我们在每次更新时随机抽取一小批样本ℬ,它是由固定数量的训练样本组成的。 然后，我们计算小批量的平均损失关于模型参数的导数（也可以称为梯度）。

逻辑回归

逻辑回归是一种广泛应用于分类问题的统计学习方法，尽管名字中带有“回归”，但它实际上是一种用于二分类问题的算法。 逻辑回归通过使用逻辑函数（也称为 Sigmoid 函数）将线性回归的输出映射到 0 和 1 之间，从而预测某个事件发生的概率。 逻辑回归广泛应用于各种分类问题，例如：

• 垃圾邮件检测（是/不是）
• 肿瘤预测（恶性/良性）

sigmoid函数是一个S形函数：

在逻辑回归中，其输入形式上等同于线性回归的输出，即:

在逻辑回归中，我们将正类标记为1，反类标记为0。h_w(x)函数的作用就是给定输入变量，计算出输出等于1的可能性，即h_w(x) = P(y = 1|x; w)。

• 例如对一个肿瘤的样本，计算得到 h_w(x) = 0.7，也就是该肿瘤有70%的可能是恶性的。

一般我们会设置阈值为0.5，当h_w(x) ≥ 0.5时，预测y=1；当h_w(x) < 0.5时，预测y=0。

• 例如：假设现在有一个模型，参数w是向量[-3 1 1]。则当 -3+x1+x2 ≥ 0 ，即 x1+x2 ≥ 3 时，模型将预测 y=1 。我们可以绘制直线 x1+x2=3 ，这条线便是我们模型的分界线，将预测为1的区域和预测为0的区域分隔开。 如下图：

同线性回归，为找到合适的w，我们需要定义逻辑回归的损失函数，如果我们沿用线性回归中的均方误差为损失函数，将h_w(x)带入其中，会发现我们得到的损失函数是一个非凸函数，如图所示： 在这种情况下，损失函数存在许多局部最小值，会影响梯度下降法寻找全局最小值，所以我们不能使用均方误差作为逻辑回归的损失函数，我们重新定义损失函数。

首先，我要先介绍一下极大似然估计

极大似然估计是一种在统计学中用于估计概率模型参数的方法。其基本思想是：给定一组数据和一个概率模型，最大似然估计会找到模型参数的值，使得这组数据在该模型下出现的概率（即“似然性”）最大。

已知模型参数(θ₁, θ₂, ..., θ_k)，以及数据集D=x₁, x₂, ..., x_n，极大似然估计就是要找到θ̂使得数据集D出现的概率最大，所以定义似然函数：

然后对似然函数求导，令导数为0得到的θ̂即为所求，为方便计算，我们一般对等式两侧取对数然后再计算。

在我们的逻辑回归中，存在下列关系： 综合起来可写成：

由极大似然估计的原理可写出单个样本i的对数似然函数： 最大化对数似然函数就可以求得最符合数据的模型参数w，而我们的损失函数是要最小化，所以我们在对数似然函数前加个负号就可以作为损失函数，同时我们使用整个数据集，得到逻辑回归的损失函数函数：

我们的目标就是最小化J(w)，具体方法也可采用梯度下降，具体推导不再赘述，与线性回归类似。

决策树

决策树是一种基于树形结构的监督学习算法。它通过从数据中学习并构建一套简单的“如果…那么…”决策规则，来模拟人类的决策过程，从而对实例进行预测。

定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

在这里给出一个判断给出特征的动物是否是猫咪的例子，我们通过动物的耳朵形状、面部形状和是否有胡须这些特征来判断是否是猫咪。

通过决策树算法我们可能会得到下图这些决策树：

这些决策树都满足给出的表格，但最终只能选择一个作为最终结果，那么我们该如何挑选出最好的那棵决策树？关键就在于我们在每个结点处该选择哪个特征来对数据进行切割。

在继续学习之前，我们先需要了解熵的概念。熵是衡量数据纯度的指标。

这是一个具体的例子：

条件熵

在了解熵和条件熵后，我们就可以引入信息增益的概念。在构建决策树时，初始数据集的熵H(D)代表了其类别的不确定性。当在某个节点处根据一个特征A对数据进行划分后，会产生多个数据子集。计算这些子集的加权平均熵H(D∣A)，即条件熵。初始熵与条件熵的差值H(D)−H(D∣A)被称为信息增益。它量化了通过特征A 、进行划分所获得的信息量，信息增益越大，意味着该特征对类别不确定性的减少越多，该特征对数据集划分所获得的“纯度提升”越大。所以信息增益可以用于决策树划分属性的选择，即选择信息增益最大的属性。

信息增益算法

如下图所示，在选择猫咪判断的根节点时，由于耳朵形状带来的信息增益最大，所以我们在构建决策树时，选择耳朵形状作为根节点。

以信息增益作为划分数据集的特征，存在偏向选择取值较多的特征的问题，对于取值很多的特征，它会将数据分割成 n 个小盒子。即使这些划分在本质上没有提供任何信息，但只要 n 足够大，就总会有很大概率创造出许多纯的或近乎纯的小盒子（尤其是当样本量有限时），从而拉低整体的H(D | A)，使得信息增益变大。 在这里举一个极限的例子，假设我们有一个数据集（n个数据），目的是判断一个人是否喜欢玩游戏。其中有一个特征叫 “身份证号”。

• 初始熵 H(D)：假设喜欢和不喜欢的人各占一半，熵很高。
• 使用“身份证号”进行划分：由于每个人的身份证号都独一无二，这个特征会有n个取值。划分后，每个子集（每个身份证号对应的那个人）都只包含一个样本。
• 划分后的熵 H(D | 特征)：每个子集内部只有一个样本，纯度是100%（要么喜欢，要么不喜欢），所以每个子集的熵都为0。这些子集的加权平均熵（条件熵）也为 0。
• 信息增益 = H(D) - 0 = H(D)。信息增益达到了理论上的最大值！ 如果根据信息增益来选择特征，“身份证号”这个毫无意义的特征会被选为根节点。

因此，引入信息增益比的概念：

使用信息增益比替代信息增益，用于决策树划分属性的选择，即选择信息增益比最大的属性。

接下来我们继续介绍基尼系数

如下图所示，基尼系数与熵的定义相比，二者的趋势一致，只是具体计算方式不同，所以我们也可将基尼系数理解为描述体系的混乱程度，基尼系数越大，不确定性越大。

类似条件熵，对于基尼系数，同样存在Gini(D, A)来描述经过特征A划分后的混乱程度。

使用Gini(D, A)替代信息增益比，用于决策树划分属性的选择，即选择Gini(D, A)小的的属性。这与信息增益和信息增益比不同，A^* = arg min Gini(D, A)。

到此，我们将决策树中常用的三种划分属性（信息增益、信息增益比、基尼系数）介绍完毕。其中使用信息增益作为划分属性的即为ID3算法，使用信息增益比作为划分属性的即为C4.5算法，使用基尼系数作为划分属性的为CART算法。

接下来我们继续介绍剪枝，这是决策树对付“过拟合”的主要手段。

在决策树学习中，为了尽可能正确分类训练样本，不断重复划分节点的过程，如果让它无限制地生长，它会为了拟合训练数据中的每一个细节，甚至包括“噪声”和“特例”，而创造出非常复杂、分支众多的树。所以剪枝的核心思想就是主动去掉树的一些分支（子树或叶子节点），以降低树的复杂度和规模。

剪枝有两种策略：

• 预剪枝：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
• 后剪枝：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。

刚才我们一直在做分类问题。考虑当特征标签是连续的情况，即此时若我们是在做回归问题，该怎么解决？如下图例子所示：

集成学习

单个决策树有一个显著的缺点：它们对训练数据中的微小变化高度敏感。如图所示，仅仅改变一个训练样本的标签（从猫变成狗），就可能导致学习算法构建出一棵结构完全不同的决策树。为了解决单个决策树不稳定的问题，我们可以使用树集成的方法。通过结合多个模型的预测结果，使整体性能优于任何单个模型。这一思想的核心是“众人拾柴火焰高”———多个弱模型结合后可以形成一个强模型。

常见的集成学习分为三大类：Stacking(堆叠)，Boosting(提升)，Bagging(Bootstrap aggregating，袋装)。

Boosting

Boosting的工作机制：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最后将这T个基学习器进行加权结合。

Boosting算法最著名的就是AdaBoost，接下来我们将介绍该算法。

AdaBoost通过顺序训练多个弱分类器来构建一个强分类器。其核心流程是：

1. 首先为所有训练样本赋予相同的初始权重；
2. 随后，在每一轮迭代中

    (a)基于当前的样本权重分布训练一个弱分类器

    (b)计算该弱分类器的加权错误率

    (c)进而确定其在最终组合中的权重系数

    (d)之后，根据本轮分类结果更新样本权重——增加被错误分类样本的权重，降低正确分类样本的权重，从而使后续弱分类器更聚焦于之前未能正确处理的样本

    重复以上过程直至完成预设轮数的训练

3. 最终，将所有弱分类器按其对应权重系数进行加权组合，形成强分类器。

输入：训练数据集T = (x₁, y₁), (x₂, y₂), ..., (x_N, y_N)，x_i为实例，y_i ∈  − 1,  + 1；弱学习算法。 输出：最终分类器G(x)

(1)初始化训练数据的权值分布D₁ = (w₁₁, w₁₂, ..., w_1N)，w_1i = 1/N

(2)循环训练M个弱分类器，对m=1, 2, …, M

   (a)使用样本权值分布为D_m的训练数据集学习，得到基本分类器

   (b)计算G_m(x)在训练数据集上的分类误差率

   (c)计算G_m(x)的系数，这是关于分类错误率e_m的单减函数，所以分类错误率低，即更准确的弱分类器在最终分类器中的权重高，符合直觉。

   (d)更新训练集的权值分布，若该样本点被预测正确，那么y_iG_m(x)为1，exp( − α_m)小于1，该样本点在下一轮训练时可以弱化，反之，若样本点被预测错误则强化。Z_m起归一化的作用。

(3)根据步骤2得到的各分类器即其系数进行组合，构建最终分类器。

Bagging

随机森林是通过构建多棵决策树并集成其结果的机器学习算法，核心是Bagging + 特征随机性。

输入参数：

• 训练集 D = {(x₁, y₁), (x₂, y₂), ..., (x_N, y_N)}
• 弱学习器（决策树）数量 T
• 特征子集大小 m（通常为总特征数 M 的平方根或对数）

对于每棵树 t = 1, 2, ..., T：

(1)Bootstrap行采样

   从原始训练集D中有放回地随机抽取N个样本，形成自助采样集D_t，因为每个样本被抽中的概率为 1 − (1 − 1/N)^N ≈ 63.2%，所以有约36.8%的样本成为袋外数据（OOB），可用于模型验证

(2)构建决策树 对于树中的每个节点：

   (a)从全部 M 个特征中随机选择 m 个特征（m ≪ M）

   (b)在选中的 m 个特征中寻找最优分裂点，然后使用指标（基尼指数、信息增益等）评估分裂质量，最后选择最佳特征和分裂阈值进行节点分裂

   (c)递归执行上述过程，直到满足停止条件： - 节点中样本数少于最小分裂样本数 - 节点深度达到最大值 - 节点中样本属于同一类别 - 不纯度减少量小于阈值

   (d)随机森林中的决策树通常完全生长，不进行剪枝

在最终预测时，对于分类问题就使用T个决策树对输入进行独立预测，将结果进行投票，少数服从多数得到最终结果。对于回归问题就将每个决策树的结果进行求平均值作为最终输出。