机器学习基础

1. 基础概念和术语

样本（$\text{sample}$）/ 实例($\text{instance}$)

我们获得的数据集中的一条数据，被称为一个 样本（$\text{sample}$）/ 实例($\text{instance}$)，在不存在数据缺失的情况下，所有样本应该具有相同的结构。
特征（$\text{feature}$）

记录样本的某种性质或者在某方面的表现的指标或变量，有时候我们直接用 原始数据的变量 作为特征（$\text{feature}$），而有的时候我们对原始变量施加一个映射，转变为一组新的变量 作为特征，这个过程也被称为 特征提取 ($\text{feature} \; \text{extraction}$)，用来 提取信息 或者进行 数据降维。
特征向量（$\text{feature} \; \text{vector}$）

一个样本的全部特征构成的向量，称为 特征向量 （$\text{feature} \; \text{vector}$）。
特征空间（$\text{feature} \; \text{space}$）/样本空间（$\text{attribute} \; \text{space}$）

由所有特征张成的空间，即特征向量所在的空间，每一维对应一个特征。被称为 特征空间（$\text{feature} \; \text{space}$）/样本空间（$\text{attribute} \; \text{space}$）
训练（$\text{training}$）

模型凭借数据提供的信息改进自身性能的过程。
测试（$\text{testing}$）

训练结束之后检验模型训练效果的过程。
测试集（$\text{testing} \; \text{set}$）

测试模型使用的数据集，其中的每一个样本称为一个 测试样本($\text{testing sample}$)
泛化能力（$\text{generalization ability}$）

在测试集上训练得到的模型，适用于训练集之外的样本的能力。
过拟合（$\text{overfitting}$）

模型 过度学习，导致 学习了过多只属于训练数据的特征，反而使得泛化能力下降。
欠拟合（$\text{underfitting}$）

模型 学习不足，导致 没有学习到训练数据中足够的一般化规律，泛化能力不足。

2. 机器学习的分类

2.1 基本分类

监督学习

监督学习（$\text{supervised} \; \text{learning}$）是指从 标注数据 中，学习预测模型的机器学习问题。

输入、输出所有可能的取值的集合分别称为输入空间、输出空间。

一个具体的输入是一个实例，通常由特征向量表示，特征向量组成的空间为特征空间。特征空间与输入空间可以为同一空间，也可以为不同空间。

监督学习举例：
- $k$ 近邻（$\text{k-NN}$）
- 线性回归（$\text{Linear Regression}$）
- 支持向量机（$\text{SVM}$）
- 决策树、随机森林
- 神经网络

无监督学习

无监督学习（$\text{unsupervised learning}$）是从 无标注数据 中学习预测模型的机器学习问题。

无监督学习是从一堆数据中学习其内在统计规律或内在结构，学习到的模型可以是类别、转换或概率。

无监督学习举例：
- $\text{K-Means}$ 聚类算法
- 主成分分析 $\text{PCA}$
- 局部线性嵌入

强化学习

强化学习（$\text{reinforcement learning}$）是指智能系统在与环境的连续互动中学习最优行为策略的机器学习问题。

半监督学习

半监督学习（$\text{semi-supervised learing}$）包含 大量未标注数据 和 少量标注数据。主要是利用未标注中的信息，辅助标注数据，进行监督学习。

主动学习

主动学习（$\text{active learning}$）是机器不断给出实例进行人工标注，然后使用标注数据学习预测模型的机器学习问题。主动学习的目标是对学习最有帮助的实例人工标注，以较小的标注代价，达到最好的学习效果.

2.2 按模型分类

概率模型 与 非概率模型

监督学习无监督学习

概率模型 $P(y/x)$ 生成模型 $P(z/x)$ 或 $P(x/z)$

非概率模型 $y = f(x)$判别模型 $z = g(x)$

概率模型举例：
- 朴素贝叶斯
- 隐马尔可夫
- 决策树
非概率模型举例：
- 感知机
- 支持向量机
- $k$ 近邻 ($\text{k-NN}$)
- $\text{K-Means}$
- 神经网络

	监督学习	无监督学习
概率模型	\(P(y/x)\) 生成模型	\(P(z/x)\) 或 \(P(x/z)\)
非概率模型	\(y = f(x)\)判别模型	\(z = g(x)\)

线性模型 与 非线性模型

机器学习模型中，尤其是非概率模型，可以分为 线性模型 （$\text{linear model}$）和 非线性模型 （$\text{non-linear model}$）

函数 $y = f(x)$ 为线性函数，则为 线性模型；函数 $y = f(x)$ 为非线性函数，则为 非线性模型。

线性模型举例：
- 感知机
- 线性 $\text{SVM}$
- $k$近邻（$\text{k-NN}$）
- $\text{K-Means}$ 聚类算法
非线性模型举例：
- 核函数 $\text{SVM}$
- 神经网络

参数化模型 与 非参数化模型

参数化模型 （$\text{parametric model}$）假设模型参数的 维度固定，由有限维参数完全刻画；非参数化模型 （$\text{non-parametric model}$）假设参数 维度不固定或者无穷大，随训练数据量的增加而不断增大。

参数化模型举例：
- 感知机
- 朴素贝叶斯
- $\text{K-Means}$ 聚类算法
非参数化模型举例：
- 支持向量机 $\text{SVM}$
- $k$ 近邻（$\text{k-NN}$）
- 决策树

2.3 按算法分类

按算法分类也是看是否可以从传入的数据流中进行增量学习。按照此种分类分为 在线学习 与 批量学习。

批量学习是把所有可用数据进行训练，这需要大量时间和计算资源，通常都是离线完成的。缺点是不能应对快速变化的数据以及较少的计算资源(CPU、内存空间、磁盘空间、磁盘I/O、网络I/O等)。

在线学习是每次接受一个或者小批量的数据，进行训练，整个过程通常是离线完成的，可以将其当做增量学习。

利用 随机梯度下降的感知机学习算法 就是 在线学习 算法。在线学习算法通常比批量学习更难，很难学到预测准确率更高的模型。

2.4 按技巧分类

贝叶斯学习

贝叶斯学习主要想法是在概率模型的学习和推理中，利用贝叶斯定理，计算在给定数据条件下模型的条件概率，即后验概率，并应该这个原理进行模型的估计和对数据进行预测。使用模型的先验分布是贝叶斯学习的特点。
核方法

核方法 （$\text{kernel method}$）是使用 核函数 表示和学习非线性模型的一种机器学习方法，可以应用于监督学习与无监督学习。比如 核函数支持向量机（核函数 $\text{SVM}$）

假设 $x_1$ 和 $x_2$ 两个输入样本，其内积为 $\left \langle x_1, x_2 \right \rangle $。将 $x_1$ 和 $x_2$ 映射到一个特征空间，分别为 $\phi(x_i)$ 和 $\phi(x_j)$，其内积为 $\left \langle \phi(x_1), \phi(x_2) \right \rangle $。

核方法直接在输入空间中定义核函数 $\kappa(x_1, x_2)$，使其满足 $\kappa(x_1, x_2) = \left \langle \phi(x_1), \phi(x_2) \right \rangle$。

3. 机器学习三要素

机器学习的三要素分别为模型，策略和算法。

\[机器学习方法 = 模型 + 策略 + 算法 \]

模型

模型是机器学习方法的核心，也是学习过程的最终结果。

围绕模型，有如下的基本概念:
- 假设空间 ($\text{hypothesis space}$)：机器学习的目的是学习一个模型，我们把所有可能的模型构成的集合称为假设空间，所以，我们进行机器学习的目的，是利用训练集从假设空间中得到一个最优的模型。
- 版本空间 ($\text{version space}$)：由于训练集是有限集合，我们有可能得到不止一个最优模型，我们把训练集上得到的所有最优模型构成的集合称为版本空间，它是假设空间的一个子集。
- 归纳偏好 ($\text{inductive bias}$)：当版本空间中存在不止一个最优模型时，如何给出最终的模型？为了缩小我们的选择范围，往往需要在学习前对模型 添加一些约束或者假设，这些约束或假设就称为归纳偏好。

策略

策略是从假设空间里学习最优模型的准则。损失函数 度量模型 一次预测的好坏，风险函数 度量 平均意义 下模型预测的好坏。
- $\text{0-1}$ 损失函数
  
  \[L(Y, f(X)) = \begin{cases} 1, \quad Y \ne f(X) \\ 0, \quad Y = f(X) \end{cases} \]
- 平方损失函数
  
  \[L(Y, f(X)) = (Y - f(X))^2 \]
- 绝对损失函数
  
  \[L(Y, f(X)) = |Y - f(X)| \]
- 对数损失函数
  
  \[L(Y, P(Y|X)) = -\text{log}\;P(Y|X) \]
损失函数 值越小，模型就越好。
- 期望风险/期望损失
  
  \[R_{\text{exp}}(f) = E_P[L(Y, f(X))] \]
- 经验风险/经验损失
  
  \[R_{\text{emp}}(f) = \frac{1}{N}\sum_{i=1}^NL(y_i, f(x_i)) \]
期望风险 是模型关于联合分布的期望损失；经验风险 是模型关于训练样本集的平均损失。

经验风险最小化 （$\text{empirical risk minimization}$）的策略认为，经验风险最小的模型是最优模型。在 样本容量足够大 时，经验风险最小化可以 保证较好的学习效果；在 样本容量较小 时，会产生 过拟合 的现象。

结构风险最小化 （$\text{structual risk minimization}$）是为了 防止过拟合 而提出的策略。结构风险最小化等价于 正则化 （$\text{regularization}$）。结构风险在经验风险的基础上增加了一个 正则化项 或罚项。结构风险最小化 的策略认为，结构风险最小的模型是最优模型。

算法

机器学习的算法是 基于训练集，根据学习策略，在假设空间上 根据策略优化模型 的 具体计算方法，基本上属于优化问题，可以使用一些已有的最优化算法，有时也需要结合模型设计新算法。

4. 模型选择

4.1 模型选择方法

模型选择 ($\text{model selection}$)有两层含义：一是在假设空间上 训练得到的模型可能不止一个，需要从中进行选择；二是对于一个具体问题，我们可能希望 尝试不同方法，于是就有了不同的模型，在这些模型训练结束后，我们需要决定使用哪一个，但这种模型选择往往 需要结合模型评估方法，因为对于某种归纳偏好，不同方法下的不同模型的实现各不相同，只能根据在测试集上的最终表现效果来选择。

监督学习中两大类模型选择的方法：正则化 和 交叉验证。

4.1 正则化

在模型选择中，正则化方法 也同样被用来对模型复杂度进行惩罚，避免模型由于过度追求训练集上的效果而过度偏向复杂模型，从而 避免出现过拟合，泛化能力降低的情况。

正则化一般有如下形式：

\[\min \frac{1}{N}\sum_{i=1}^NL(y_i, f_(x_i)) + \lambda J(f) \]

其中 $\frac{1}{N}\sum_{i=1}^NL(y_i, f_(x_i))$ 是 经验风险，$\lambda J(f)$ 是 正则化项，$\lambda$ 为 惩罚系数，用于调整前两者之间的关系，控制正则化过程对误差的调整程度。

比如在经典的线性回归问题中，正则化项 可以是 $L_1$ 范数和 $L_2$ 范数，也分别对应着两种线性回归方法，即 $\text{LASSO}$回归 和 岭回归（$\text{Ridge Regression}$）。

LASSO回归

\[L(w) = \frac{1}{N}\sum_{i=1}^N(y_i - f_{w}(x_i))^2 + \lambda||w||_1 \]
岭回归

\[L(w) = \frac{1}{N}\sum_{i=1}^N(y_i - f_{w}(x_i))^2 + \frac{\lambda}{2}||w||^2_2 \]

4.2 交叉验证

在样本量足够大的理想情况下，应当把数据集分割为三部分：训练集 ($\text{training set}$)、验证集 ($\text{validation set}$)和 测试集 ($\text{testing set}$)，分别用于 模型训练、模型选择和模型评估，用于评估模型泛化能力的测试集只出现在最后的模型评估环节。

但很多时候数据不够充足，这种时候可以取消验证集，采用 交叉验证 方法（$\text{cross validation}$），通过反复划分训练集和测试集来避免用同一批数据训练和评估一个模型。

简单交叉验证 ($\text{hold out}$)

将数据集按一定比例 随机分为两部分：训练集 和 测试集。用训练集在不同参数条件下进行模型训练，从而得到不同模型；在测试集上测试不同模型，选出测试误差最小的模型。
K 折交叉验证 ($\text{k-flod cross validation}$)

将数据集随机划分为 $K$ 个 大小相同或基本相同 、互不相交 的子集。总共进行 $K$ 组训练，利用划分出来的 $K - 1$ 个子集进行每一组的模型训练，利用剩下的 $1$ 个子集进行每一组的模型测试。并且必要时会进行 多次K折交叉验证，选出平均测试误差最小的模型。
留一交叉验证 ($\text{leave-one-out cross validation}$)

K折交叉验证的特例，将K取为样本量N，也即把每个样本单独作为测试集，其余样本作为训练集。计算量较大，一般仅用于数据稀少的情况。

5. 准确率、精确率、召回率

5.1 混淆矩阵

混淆矩阵 （$\text{confusion matrix}$）也称误差矩阵，是表示精度评价的一种标准格式，用 $n \times n$ 的矩阵形式来表示。具体评价指标有总体精度、制图精度、用户精度等，这些精度指标从不同的侧面反映了图像分类的精度。

在机器学习中，混淆矩阵特别用于监督学习，在无监督学习一般叫做匹配矩阵。

对于一个二分类系统，将实例分为正类（$\text{Positive}$）、负类（$\text{Negative}$）

模式分类器有四种分类结果:

$\text{TP}$ （$\text{True Positive}$）：将正类预测为正类
$\text{FN}$ （$\text{False Negative}$）：将 正类判定为负类
$\text{FP}$ （$\text{False Positive}$）：将 负类判定为正类
$\text{TN}$ （$\text{True Negative}$）：将负类判定为负类

5.2 准确率

所有的预测正确（正类负类）的占总的比重。

\[\text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN} \]

虽然准确率能够判断总的正确率，但是在样本不均衡的情况下，并不能作为很好的指标来衡量结果。

5.3 精确率

也称为 查准率，即 正类预测为正 的占 全部预测为正（正类预测为正 + 负类预测为正）的比例。

\[\text{Precision} = \frac{\text{TP}}{\text{TP + FP}} \]

精确率代表对正样本结果中的预测准确程度。

5.4 召回率

即 正确预测为正 的占 全部实际为正（正类预测为正 + 正类预测为负）的比例。

\[\text{Recall} = \frac{\text{TP}}{\text{TP + FN}} \]

5.5 $F_1$ 值

精确率和召回率互相影响，理想状态下肯定追求两个都高，但是实际情况是两者相互“制约”：追求精确率高，则召回率就低；追求召回率高，则通常会影响精确率。

因此有了 $F_1$ 值：

\[\begin{split} & \frac{2}{F_1} = \frac{1}{\text{Precision}} + \frac{1}{\text{Recall}} \\\\ & F_1 = \frac{2 \text{TP}}{2 \text{TP + FP + FN}} \end{split} \]

PS: 李航的《机器学习方法》中，应该是将 精确率 和 准确率 写反了。一直以来网上也有争议，此板块以网上大多部分文章的定义为准。

6. 熵、交叉熵

6.1 熵

信息论中熵的概念首次被香农提出，目的是寻找一种高效/无损地编码信息的方法：以编码后数据的平均长度来衡量高效性，平均长度越小越高效；同时还需满足“无损”的条件，即编码后不能有原始信息的丢失。这样，香农提出了熵的定义：无损编码事件信息的最小平均编码长度。

如果 熵比较大 (即平均编码长度较长)，意味着这一信息有较多的可能状态，相应的每个状态的可能性比较低；因此每当来了一个新的信息，我们很难对其作出准确预测，即有着 比较大的混乱程度/不确定性/不可预测性。

6.2 交叉熵

交叉熵 是一种在信息理论与机器学习中常用的测量方式，用于度量两个概率分布间的“距离”。它的定义基于信息熵的概念。

熵的公式如下：

\[H(p) = - \sum p(x) \; \text{log}(p(x)) \]

其中，$p(x)$ 是某件事件 $x$ 发生的概率。

然而，当我们有两个概率分布 $p$ 和 $q$（例如，一个是真实分布，另一个是我们的模型 预测出的分布 ），并且我们想度量这两个分布之间的相似度时，我们可以使用“交叉熵”。交叉熵 的定义是：

\[H(p, q) = - ∑ p(x) \; \text{log}(q(x)) \]

其中，$p(x)$ 是某件事件 $x$ 发生的 真实概率，$q(x)$ 是我们的 模型估计出的该事件发生的概率。可以看出，交叉熵实质是针对真实分布 $p$，以 $q$ 的视角对事件进行编码的期望长度。

在 机器学习 中，特别是 分类问题，可以使用交叉熵作为损失函数，通过计算真实分布和预测分布之间的交叉熵，然后尽可能地减小这个交叉熵，从而使得我们的模型预测分布尽可能地接近真实分布。这是许多神经网络分类模型常用的优化方式。

7. 核函数

核函数 往往作用于 降低运算复杂度。

设想一个函数：

\[\kappa(x_i, x_j) = \left \langle \phi(x_i),\phi(x_j) \right \rangle = \phi(x_i)^T\phi(x_j) \]

即 $x_i$ 和 $x_j$ 在 特征空间的内积等于它们在原始的样本空间中通过函数 $\kappa$ 计算得出的结果。这就避免了高维度的计算。

然而一般情况下，我们不知道 $\phi$ 的具体形式。我们有如下定理：

令 $\chi$ 为输入空间，$\kappa$ 为定义在 $\chi \times \chi$ 的对称函数，则 $\kappa$ 是 核函数 当且仅当对于任意数据 $D = \{x_1, x_2, ... , x_n\}$ ，核矩阵 ($\text{kernel}$ $\text{matrix}$) $K$ 总是半正定的:

\[K = \begin{bmatrix} \kappa(x_1, x_1) & \cdots & \kappa(x_1, x_n) \\\\ \vdots & \ddots & \vdots \\\\ \kappa(x_n, x_1) & \cdots & \kappa(x_n, x_n) \end{bmatrix} \]

只要一个对称函数对应的核矩阵半正定，其可作为 核函数 使用。

常用核函数：

线性核函数

\[\kappa(x_i, x_j) = x_i^Tx_j \]

多项式核函数

\[\kappa(x_i, x_j) = (x_i^Tx_j)^d, \qquad d \ge 1 \]

高斯核函数(也称径向基RBF函数)

\[\kappa(x_i, x_j) = \text{exp}(- \frac{||x_i - x_j||^2_2}{2 \sigma^2}), \qquad \sigma > 0 \]

拉普拉斯核函数*

\[\kappa(x_i, x_j) = \text{exp}(- \frac{||x_i - x_j||_1}{\sigma}), \qquad \sigma > 0 \]

$\text{sigmoid}$ 核函数*

\[\kappa(x_i, x_j) = \text{tanh}(\beta x_i^Tx_j + \theta), \qquad \beta > 0, \; \theta > 0 \]

上述的核函数，也可以通过线性组合等方式，组成新的核函数。

8. 常用矩阵求导公式

这里偷懒就不做证明了（￣︶￣）

公式 1

\[\frac{\partial(x^TA)}{\partial x} = \frac{\partial (A^Tx)}{\partial x} = A \]
公式 2

\[\frac{\partial (x^Tx)}{\partial x} = 2x \]
公式 3

\[\frac{\partial (x^TAx)}{\partial x} = (A + A^T)x \]
公式 4

\[\frac{\partial (a^Txx^Tb)}{\partial x} = \frac{\partial (x^Tab^Tx)}{\partial x} = (ab^T + ba^T)x \]