↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』原创

作者：华校专

作者信息：

华校专，曾任阿里巴巴资深算法工程师、智易科技首席算法研究员，现任腾讯高级研究员，《Python 大战机器学习》的作者。

编者按：

算法工程师必备系列更新啦！继上次推出了算法工程师必备的数学基础后，小编继续整理了必要的机器学习知识，全部以干货的内容呈现，哪里不会学哪里，老板再也不用担心你的基础问题！

第一部分：机器学习基础及线性模型

第一章：机器学习方法概论

1. 机器学习的对象是：具有一定的统计规律的数据。

2. 机器学习根据任务类型，可以划分为：

监督学习任务：从已标记的训练数据来训练模型。主要分为：分类任务、回归任务、序列标注任务。
无监督学习任务：从未标记的训练数据来训练模型。主要分为：聚类任务、降维任务。
半监督学习任务：用大量的未标记训练数据和少量的已标记数据来训练模型。
强化学习任务：从系统与环境的大量交互知识中训练模型。

3. 机器学习根据算法类型，可以划分为：

传统统计学习：基于数学模型的机器学习方法。包括SVM、逻辑回归、决策树等。

这一类算法基于严格的数学推理，具有可解释性强、运行速度快、可应用于小规模数据集的特点。

深度学习：基于神经网络的机器学习方法。包括前馈神经网络、卷积神经网络、递归神经网络等。

这一类算法基于神经网络，可解释性较差，强烈依赖于数据集规模。但是这类算法在语音、视觉、自然语言等领域非常成功。

4. 没有免费的午餐定理(No Free Lunch Theorem:NFL)：对于一个学习算法A，如果在某些问题上它比算法B好，那么必然存在另一些问题，在那些问题中B比A更好。

因此不存在这样的算法：它在所有的问题上都取得最佳的性能。因此要谈论算法的优劣必须基于具体的学习问题。

一、基本概念

1.1 特征空间

1. 输入空间：所有输入的可能取值；输出空间：所有输出的可能取值。

特征向量表示每个具体的输入，所有特征向量构成特征空间。

2. 特征空间的每一个维度对应一种特征。

3. 可以将输入空间等同于特征空间，但是也可以不同。绝大多数情况下，输入空间等于特征空间。

模型是定义在特征空间上的。

1.2 样本表示

1. 通常输入实例用表示，真实标记用表示，模型的预测值用 ,表示。具体的输入取值记作 , ；具体的标记取值记作；具体的模型预测取值记作。

2. 所有的向量均为列向量，其中输入实例的特征向量记作（假设特征空间为 n 维）：

这里为的第 i 个特征的取值。第 i 个输入记作，它的意义不同于。

3. 训练数据由输入、标记对组成。通常训练集表示为：。

输入、标记对又称作样本点。
假设每对输入、标记对是独立同分布产生的。

4. 输入和标记可以是连续的，也可以是离散的。

为连续的：这一类问题称为回归问题。
为离散的，且是有限的：这一类问题称之为分类问题。
和均为序列：这一类问题称为序列标注问题。

二、监督学习

2.1 监督学习

1. 监督学习中，训练数据的每个样本都含有标记，该标记由人工打标，所以称之为监督 。

2. 监督学习假设输入与标记遵循联合概率分布，训练数据和测试数据依联合概率分布独立同分布产生。

学习过程中，假定这个联合概率分布存在，但是具体定义未知。

3. 监督学习的目的在于学习一个由输入到输出的映射，该映射由模型表示。

模型属于由输入空间到输出空间的映射的集合，该集合就是解空间。解空间的确定意味着学习范围的确定。

4. 监督学习的模型可以为概率模型或者非概率模型：

概率模型由条件概率分布表示。
非概率模型由决策函数表示。

5. 监督学习分为学习和预测两个过程。

给定训练集，其中为输入值，是标记值。假设训练数据与测试数据是依据联合概率分布独立同分布的产生的。

学习过程：在给定的训练集上，通过学习训练得到一个模型。该模型表示为条件概率分布或者决策函数
预测过程：对给定的测试样本，给出其预测结果：
对于概率模型，其预测值为：
对于非概率模型，其预测值为：

6. 可以通过无监督学习来求解监督学习问题

首先求解无监督学习问题来学习联合概率分布
然后计算：。

2.2 生成模型和判别模型

1. 监督学习又分为生成方法和判别方法，所用到的模型分别称为生成模型和判别模型。

2. 生成方法：通过数据学习联合概率分布，然后求出条件概率分布作为预测的模型。

即生成模型为：

生成方法的优点：能还原联合概率分布，收敛速度快，且当存在隐变量时只能用生成方法。
生成方法有：朴素贝叶斯法，隐马尔可夫链。

3. 判别方法：直接学习决策函数或者条件概率分布的模型。

判别方法的优点：直接预测，一般准确率更高，且一般比较简化问题。
判别方法有：逻辑回归，决策树。

三、机器学习三要素

1. 机器学习三要素：模型、策略、算法。

3.1 模型

1. 模型定义了解空间。监督学习中，模型就是要学习的条件概率分布或者决策函数。

模型的解空间包含了所有可能的条件概率分布或者决策函数，因此解空间中的模型有无穷多个。

模型为一个条件概率分布：

解空间为条件概率的集合：。其中： , 为随机变量，为输入空间，为输出空间。

通常是由一个参数向量决定的概率分布族：其中：只与有关，称为参数空间。

模型为一个决策函数：

解空间为决策函数的集合：。其中：为变量，为输入空间，为输出空间。

通常是由一个参数向量决定的函数族：。其中：只与有关，称为参数空间。

2. 解的表示一旦确定，解空间以及解空间的规模大小就确定了。

如：一旦确定解的表示为：，则解空间就是特征的所有可能的线性组合，其规模大小就是所有可能的线性组合的数量。

3. 将学习过程看作一个在解空间中进行搜索的过程，搜索目标就是找到与训练集匹配的解。

3.2 策略

1. 策略考虑的是按照什么样的准则学习，从而定义优化目标。

3.2.1 损失函数

1. 对于给定的输入，由模型预测的输出值与真实的标记值可能不一致。此时，用损失函数度量错误的程度，记作，也称作代价函数。

2. 常用损失函数：

0-1 损失函数：

平方损失函数MSE：
绝对损失函数MAE：
对数损失函数：。
其物理意义是：二分类问题的真实分布与模型分布之间的交叉熵。
一个简单的解释：因为样本易经出现，所以理论上。

如果它不为 1，则说明预测存在误差。越远离1，说明误差越大。

3. 训练时采用的损失函数不一定是评估时的损失函数。但通常二者是一致的。

因为目标是需要预测未知数据的性能足够好，而不是对已知的训练数据拟合最好。

3.2.2 风险函数

1. 通常损失函数值越小，模型就越好。但是由于模型的输入、标记都是随机变量，遵从联合分布，因此定义风险函数为损失函数的期望：

其中分别为输入空间和输出空间。

2. 学习的目标是选择风险函数最小的模型。

3. 求的过程中要用到 ,但是是未知的。

实际上如果它已知，则可以轻而易举求得条件概率分布，也就不需要学习。

3.2.3 经验风险

1. 经验风险也叫经验损失。

给定训练集，模型关于的经验风险定义为：

经验风险最小化 (empirical risk minimization:ERM ) 策略认为：经验风险最小的模型就是最优的模型。即：

2. 经验风险是模型在上的平均损失。根据大数定律，当。

但是由于现实中训练集中样本数量有限，甚至很小，所以需要对经验风险进行矫正。

3. 结构风险是在经验风险上叠加表示模型复杂度的正则化项（或者称之为罚项）。它是为了防止过拟合而提出的。

给定训练集，模型关于 \mathbb D 的结构风险定义为：

其中：

为模型复杂度，是定义在解空间上的泛函。越复杂，则越大。
为系数，用于权衡经验风险和模型复杂度。

4. 结构风险最小化 (structurel risk minimization:SRM) 策略认为：结构风险最小的模型是最优的模型。即：

5. 结构风险最小化策略符合奥卡姆剃刀原理：能够很好的解释已知数据，且十分简单才是最好的模型。

3.2.4 极大似然估计

1. 极大似然估计就是经验风险最小化的例子。

2. 已知训练集，则出现这种训练集的概率为：。根据出现概率最大，有：

定义损失函数为：，则有：

即：极大似然估计 = 经验风险最小化。

3.2.5 最大后验估计

1. 最大后验估计就是结构风险最小化的例子。

2. 已知训练集，假设已知参数的先验分布为，则出现这种训练集的概率为:

根据出现概率最大：

定义损失函数为：；定义模型复杂度为；定义正则化系数为。则有：

即：最大后验估计 = 结构风险最小化。

3.3 算法

1. 算法指学习模型的具体计算方法。通常采用数值计算的方法求解，如：梯度下降法。

第二章：线性模型

给定样本，其中，为样本的第 i 个特征，特征有 n 种。线性模型(linear model) 的形式为：。其中为每个特征对应的权重生成的权重向量。
线性模型的优点是：

模型简单。
可解释性强，权重向量直观地表达了各个特征在预测中的重要性。

很多功能强大的非线性模型(nolinear model) 可以在线性模型的基础上通过引入层级结构或者非线性映射得到。

一、线性回归

1.1 问题

给定数据集
。

线性回归问题试图学习模型：
该问题也被称作多元线性回归(multivariate linear regression)
对于每个，其预测值为。采用平方损失函数，则在训练集上，模型的损失函数为：
优化目标是损失函数最小化，即：。

1.2 求解

可以用梯度下降法来求解上述最优化问题的数值解，但是实际上该最优化问题可以通过最小二乘法获得解析解。
令：

则有：

令：
则：
令。为求得它的极小值，可以通过对求导，并令导数为零，从而得到解析解：

1）当为满秩矩阵时，可得：。
其中的逆矩阵。
最终学得的多元线性回归模型为：。
2）当不是满秩矩阵。此时存在多个解析解，他们都能使得均方误差最小化。究竟选择哪个解作为输出，由算法的偏好决定。
比如（样本数量小于特征种类的数量），根据的秩小于等于 N,n 中的最小值，即小于等于 N（矩阵的秩一定小于等于矩阵的行数和列数）；而矩阵大小的，它的秩一定小于等于 N，因此不是满秩矩阵。
常见的做法是引入正则化项：
1） L_1 正则化：此时称作Lasso Regression ：
为正则化系数，调整正则化项与训练误差的比例。
2） L_2 正则化：此时称作Ridge Regression：
为正则化系数，调整正则化项与训练误差的比例。
3）同时包含 L_1,L_2 正则化：此时称作Elastic Net：
其中：

为正则化系数，调整正则化项与训练误差的比例。
为比例系数，调整 L_1 正则化与 L_2 正则化的比例。

1.3 算法

多元线性回归算法：
1）输入：
a. 数据集
b. L_2 正则化项系数

2）输出模型：
3）算法步骤：
令：

求解：
最终学得模型：

二、广义线性模型

2.1 广义线性模型的函数定义

考虑单调可微函数，令，这样得到的模型称作广义线性模型 (generalized linear model)。
其中函数称作联系函数 (link function) 。
对数线性回归是广义线性模型在时的特例。即：。

它实际上是试图让) 逼近 y 。
它在形式上仍是线性回归，但是实质上是非线性的。

2.2 广义线性模型的概率定义

如果给定和之后，之后， y 的条件概率分布服从指数分布族，则该模型称作广义线性模型。
指数分布族的形式为：。

是的线性函数：
为的函数
为的函数

2.3 常见分布的广义线性模型

2.3.1 高斯分布

高斯分布：

令：

则满足广义线性模型。

2.3.2 伯努利分布

伯努利分布（二项分布，y 为 0 或者 1，取 1的概率为 \phi ）：

令：

则满足广义线性模型。
根据，有。则得到：
因此 logistic 回归属于伯努利分布的广义形式。

2.3.3 多元伯努利分布

假设有 K 个分类，样本标记。每种分类对应的概率为。则根据全概率公式，有

a. 定义为一个维的列向量：

b. 定义示性函数 : 表示属于分类；表示不属于分类。则有：
c. 构建概率密度函数为：
c. 令

则有：
令，则满足广义线性模型。
根据：

则根据：

于是有：

三、对数几率回归

线性回归不仅可以用于回归任务，还可以用于分类任务。

3.1 二分类模型

考虑二分类问题。
给定数据集
。

a. 考虑到取值是连续的，因此它不能拟合离散变量。
可以考虑用它来拟合条件概率，因为概率的取值也是连续的。
b. 但是对于（若等于零向量则没有什么求解的价值），取值是从，不符合概率取值为，因此考虑采用广义线性模型。
最理想的是单位阶跃函数：

c. 但是阶跃函数不满足单调可微的性质，不能直接用作。
对数几率函数(logistic function)就是这样的一个替代函数：

这样的模型称作对数几率回归(logistic regression或logit regression）模型。
由于，则有：

a. 比值表示样本为正例的可能性比上反例的可能性，称作几率(odds）。几率反映了样本作为正例的相对可能性。
几率的对数称作对数几率(log odds，也称作logit）。
b. 对数几率回归就是用线性回归模型的预测结果去逼近真实标记的对数几率。
虽然对数几率回归名字带有回归，但是它是一种分类的学习方法。其优点：

直接对分类的可能性进行建模，无需事先假设数据分布，这就避免了因为假设分布不准确带来的问题。
不仅预测出来类别，还得到了近似概率的预测，这对许多需要利用概率辅助决策的任务有用。
对数函数是任意阶可导的凸函数，有很好的数学性质，很多数值优化算法都能直接用于求取最优解。

3.2 参数估计

给定训练数据集，其中。可以用极大似然估计法估计模型参数，从而得出模型。
为了便于讨论，将参数吸收进中。
令：
令
则似然函数为：。
对数似然函数为：
由于，因此：
则需要求解最优化问题：

最终 logistic 回归模型为：
logistic 回归的最优化问题，通常用梯度下降法或者拟牛顿法来求解。

3.3 多分类模型

可以推广二分类的 logistic 回归模型到多分类问题。
设离散型随机变量 y 的取值集合为：，则多元 `logistic` 回归模型为：

其中。
其参数估计方法类似二项 logistic 回归模型。

四、线性判别分析

线性判别分析Linear Discriminant Analysis:LDA 基本思想：

训练时：给定训练样本集，设法将样例投影到某一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。要学习的就是这样的一条直线。
预测时：对新样本进行分类时，将其投影到学到的直线上，在根据投影点的位置来确定新样本的类别。

4.1 二分类模型

考虑二类分类问题。设数据集为：

4.1.1 投影

设表示类别为 0 的样例的集合，这些样例的均值向量为，这些样例的特征之间协方差矩阵为（协方差矩阵大小为。
设表示类别为 1 的样例的集合，这些样例的均值向量为，这些样例的特征之间协方差矩阵为（协方差矩阵大小为）
假定直线为：，其中
这里省略了常量，因为考察的是样本点在直线上的投影，总可以平行移动直线到原点而保持投影不变，此时。
将数据投影到直线上，则：
由于直线是一维空间，因此上面四个值均为实数

两类样本的中心在直线上的投影分别为和
两类样本投影的方差分别为和

根据线性判别分析的思想：

要使得同类样例的投影点尽可能接近，则可以使同类样例投影点的方差尽可能小，即尽可能小
要使异类样例的投影点尽可能远，则可以使异类样例的中心的投影点尽可能远，即尽可能大
同时考虑两者，则得到最大化的目标：

4.2 多分类模型

可以将线性判别分析推广到多分类任务中。
假定存在 M 个类，属于第 i 个类的样本的集合为中的样例数为。其中：，为样本总数。
1）定义类别的均值向量为：所有该类别样本的均值：

类别的样例的特征之间协方差矩阵为（协方差矩阵大小为）。
2）定义是所有样例的均值向量。
定义各类别的类内散度矩阵、总的类内散度矩阵、总的类间散度矩阵：
1）定义类别的类内散度矩阵为：
它实际上就等于样本集的协方差矩阵，刻画了同类样例投影点的方差。
2）定义总的类内散度矩阵为：。
它刻画了所有类别的同类样例投影点的方差。
3）定义总的类间散度矩阵为：。
它刻画了异类样例的中心的投影点的相互距离。
注意：也是一个协方差矩阵，它刻画的是第 i 类与总体之间的关系。
a）由于这里有不止两个中心点，因此不能简单的套用二分类线性判别分析的做法。
这里用每一类样本集的中心点与总的中心点的距离作为度量。
b）考虑到每一类样本集的大小可能不同（密度分布不均），对这个距离施加权重，权重为每类样本集的大小。
根据线性判别分析的思想，设是投影矩阵。经过推导可以得到最大化的目标：

其中 tr(.) 表示矩阵的迹。

一个矩阵的迹是矩阵对角线的元素之和，它是一个矩阵不变量，也等于所有特征值之和。
还有一个常用的矩阵不变量就是矩阵的行列式，它等于矩阵的所有特征值之积。

与二分类线性判别分析不同，在多分类线性判别分析中投影方向是多维的，因此使用投影矩阵。

二分类线性判别分析的投影方向是一维的（只有一条直线），所以使用投影向量。

上述最优化问题可以通过广义特征值问题求解：

的个最大广义特征值所对应的特征向量组成的矩阵。
多分类线性判别分析将样本投影到维空间。
通常远小于数据原有的特征数，LDA因此也被视作一种经典的监督降维技术。

本文福利

可以在本公众号后台 回复关键词：“ 网盘 ”获取大量由我平台编辑精心整理的学习资料，如果觉得有用，请勿吝啬你的留言和赞哦！

—— 完 ——

文章须知

文章作者：华校专

责任编辑：周岩 logic

审核编辑：阿春

微信编辑：logic

本文由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知

数据科学 | 算法工程师必备的机器学习--线性模型（上）