机器学习

绪论

机器学习的定义

正如我们根据过去的经验来判断明天的天气，吃货们希望从购买经验中挑选一个好瓜，那能不能让计算机帮助人类来实现这个呢？机器学习正是这样的一门学科，人的”经验”对应计算机中的”数据”，让计算机来学习这些经验数据，生成一个算法模型，在面对新的情况中，计算机便能作出有效的判断，这便是机器学习。

更准确地说，机器学习（Machine Learning, ML）是一门致力于研究如何通过计算来模拟或实现人类的学习行为，以获取新的知识或技能、重新组织已有的知识结构使之不断改善自身性能的学科。它是人工智能的核心研究领域之一，也是近年来十分活跃的研究领域。

机器学习的一些基本术语

在机器学习中，我们需要了解一些基本术语：

• 数据集（Dataset）：记录的集合，通常一个数据集包含很多样本。每个样本描述了一个事件或对象的属性。
• 样本（Sample）：也称为示例（Instance），是关于一个事件或对象的描述。例如，一个”好瓜”的样本可能包含色泽、根蒂、敲声等属性。
• 属性（Attribute）：也称为特征（Feature），反映事件或对象在某方面的表现或性质。例如”色泽”、“根蒂”、“敲声”等。
• 属性值（Attribute Value）：属性上的取值。例如”青绿”、“蜷缩”、“浊响”等。
• 属性空间（Attribute Space）：也称为样本空间或输入空间，是属性张成的空间。每个属性对应空间中的一个坐标轴，每个样本对应空间中的一个点。
• 标记（Label）：关于示例结果的信息。例如”好瓜”、“坏瓜”。
• 标记空间（Label Space）：也称为输出空间，是所有标记的集合。
• 训练集（Training Set）：用于训练学习算法的数据集合，其中每个样本称为训练样本。
• 测试集（Test Set）：用于测试学习算法性能的数据集合，其中每个样本称为测试样本。
• 假设（Hypothesis）：学得模型对应了关于数据的某种潜在规律，因此亦称假设。
• 真相（Ground Truth）：我们要学习的真正模型，但在现实任务中通常不知道真相到底是什么。
• 学习算法（Learning Algorithm）：在给定训练集上产生模型的算法。
• 归纳偏置（Inductive Bias）：算法在学习过程中对某种类型假设的偏好。

根据训练数据是否拥有标记信息，学习任务可大致划分为两大类：

• 监督学习（Supervised Learning）：训练集中的样本有标记信息，学习目标是建立输入到输出的映射关系
• 无监督学习（Unsupervised Learning）：训练集中的样本没有标记信息，学习目标是发现数据中的潜在规律

模型的评估和选择

误差与过拟合

学习器的实际预测输出与样本的真实输出之间的差异称为误差（Error）。学习器在训练集上的误差称为训练误差（Training Error）或经验误差（Empirical Error）；在新样本上的误差称为泛化误差（Generalization Error）。

我们希望得到泛化误差小的学习器，但实际上我们能做的是努力使经验误差最小化。当学习器把训练样本学得”太好”了，很可能已经把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，这样就会导致泛化性能下降，这种现象称为过拟合（Overfitting）。

与过拟合相对的是欠拟合（Underfitting），这是指对训练样本的一般性质尚未学好。过拟合是机器学习面临的关键障碍，各种学习算法都必须采取一些策略来应对过拟合。

评估方法

通常我们可通过实验测试来对学习器的泛化误差进行评估并进而做出选择。为此，需使用一个”测试集”来测试学习器对新样本的判别能力，然后以测试集上的”测试误差”作为泛化误差的近似。

训练集与测试集的划分方法

留出法

**留出法（Hold-out）**直接将数据集 D 划分为两个互斥的集合，其中一个作为训练集 S，另一个作为测试集 T。在 S 上训练出模型后，用 T 来评估其测试误差，作为对泛化误差的估计。

需要注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。常见做法是采用分层采样。

通常将大约 2/3 ～ 4/5 的样本用于训练，剩余样本用于测试。

交叉验证法

**交叉验证法（Cross Validation）**先将数据集 D 划分为 k 个大小相似的互斥子集，每个子集都尽可能保持数据分布的一致性，即从 D 中通过分层采样得到。然后，每次用 k-1 个子集的并集作为训练集，余下的那个子集作为测试集，这样就可获得 k 组训练/测试集，从而可进行 k 次训练和测试，最终返回的是这 k 个测试结果的均值。

交叉验证法评估结果的稳定性和保真性在很大程度上取决于 k 的取值，为强调这一点，通常把交叉验证法称为”k 折交叉验证”（k-fold cross validation）。k 最常用的取值是 10，此时称为 10 折交叉验证。

特殊地，假设数据集 D 中包含 m 个样本，若令 k=m，则得到了交叉验证法的一个特例：留一法（Leave-One-Out, LOO）。

自助法

**自助法（Bootstrapping）**以自助采样（bootstrap sampling）为基础。给定包含 m 个样本的数据集 D，我们对它进行采样产生数据集 D’：每次随机从 D 中挑选一个样本，将其拷贝放入 D’，然后再将该样本放回初始数据集 D 中，使得该样本在下次采样时仍有可能被采到。这个过程重复执行 m 次后，我们就得到了包含 m 个样本的数据集 D’。

显然，D 中有一部分样本会在 D’中多次出现，而另一部分样本不出现。可以做一个简单的估计，样本在 m 次采样中始终不被采到的概率是$(1-\frac{1}{m})^m$，取极限得到：

$$\lim_{m \to \infty}(1-\frac{1}{m})^m = \frac{1}{e} \approx 0.368$$

即通过自助采样，初始数据集 D 中约有 36.8%的样本未出现在采样数据集 D’中。于是我们可将 D’用作训练集，D\D’用作测试集。

调参

大多数学习算法都有些参数需要设定，参数配置不同，学得模型的性能往往有显著差别。因此，在进行模型评估与选择时，除了要对适用学习算法进行选择，还需对算法参数进行设定，这就是调参（Parameter Tuning）。

学习算法的很多参数是在实数范围内取值，因此，对每种参数配置都训练出模型来是不可行的。现实中常用的做法是对每个参数选定一个范围和变化步长。

性能度量

对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量（Performance Measure）。

最常见的性能度量

在回归任务中，最常用的性能度量是均方误差（Mean Squared Error）：

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

查准率/查全率/F1

对于二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为真正例、假正例、真反例、假反例四种情形，令 TP、FP、TN、FN 分别表示其对应的样例数，则有 TP+FP+TN+FN=样例总数。

基于这四个基本量，可以定义：

查准率（Precision）：$P = \frac{TP}{TP+FP}$

查全率（Recall）：$R = \frac{TP}{TP+FN}$

查准率和查全率是一对矛盾的度量。一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。

在一些情况下，我们希望将查准率和查全率结合起来考虑，最常用的是F1 度量：

$$F1 = \frac{2 \times P \times R}{P + R} = \frac{2 \times TP}{样例总数 + TP - TN}$$

ROC 与 AUC

**ROC 曲线（Receiver Operating Characteristic Curve）**是根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要量的值，分别以它们为横、纵坐标作图。

这两个量分别是：

• 真正例率（True Positive Rate, TPR）：$TPR = \frac{TP}{TP+FN}$
• 假正例率（False Positive Rate, FPR）：$FPR = \frac{FP}{TN+FP}$

**AUC（Area Under ROC Curve）**即 ROC 曲线下的面积。从统计学观点看，AUC 就是从所有正样本中随机选取一个样本，从所有负样本中随机选取一个样本，然后根据你的分类器对两个随机样本进行预测，把正样本预测为正的概率比把负样本预测为正的概率大的可能性。

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

在现实任务中，不同类型的错误所造成的后果往往不同。为权衡不同类型错误所造成的不同损失，可为错误赋予”非均等代价”（unequal cost）。

代价矩阵（Cost Matrix）是一个指明错误代价的矩阵。在代价敏感学习中，我们希望最小化”总体代价”，此时的代价敏感错误率为：

$$E(f;D;cost) = \frac{1}{m}\left(\sum_{x_i \in D^+}I(f(x_i) \neq y_i) \times cost_{01} + \sum_{x_i \in D^-}I(f(x_i) \neq y_i) \times cost_{10}\right)$$

比较检验

假设检验

在很多时候，我们并非仅做一次留出法估计或交叉验证，而是通过多次重复留出法或是交叉验证等进行多次训练/测试，此时可使用t 检验（t-test）。

交叉验证 t 检验

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

McNemar 检测

对于二分类问题，使用留出法不仅能估计出学习器的性能，还能获得学习器分类结果的差别。McNemar 检验假设两学习器的性能相同，即$e_{01} = e_{10}$。

Friedman 检测与 Nemenyi 后续检验

Friedman 检验是一种非参数检验方法，它不需要假设样本来自正态分布。当要在一组数据集上对多个算法进行比较时，一种做法是在每个数据集上分别使用交叉验证法来得到每个算法的性能，然后用 Friedman 检验。

偏差与方差

**偏差-方差分解（Bias-Variance Decomposition）**是解释学习算法泛化性能的一种重要工具。对测试样本 x，令$y_D$为 x 在数据集中的标记，y 为 x 的真实标记，$f(x;D)$为训练集 D 上学得模型 f 在 x 上的预测输出。

以回归任务为例，学习算法的期望预测为：

$$\bar{f}(x) = E_D[f(x;D)]$$

使用样本数相同的不同训练集产生的方差为：

$$var(x) = E_D[(f(x;D) - \bar{f}(x))^2]$$

噪声为：

$$\varepsilon^2 = E_D[(y_D - y)^2]$$

期望输出与真实标记的差别称为偏差：

$$bias^2(x) = (\bar{f}(x) - y)^2$$

线性模型

线性模型是机器学习中最基础也是最重要的模型之一。它试图学得一个通过属性的线性组合来进行预测的函数。

线性回归

给定数据集$D = \{(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)\}$，其中$x_i = (x_{i1}; x_{i2}; \ldots; x_{id})$，线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。

一元线性回归试图学得：

$$f(x_i) = wx_i + b$$

使得$f(x_i) \simeq y_i$。

如何确定 w 和 b 呢？关键在于衡量 f(x)与 y 之间的差别。均方误差是回归任务中最常用的性能度量，因此我们可试图让均方误差最小化：

$$(w^*, b^*) = \arg\min_{(w,b)} \sum_{i=1}^{m}(f(x_i) - y_i)^2 = \arg\min_{(w,b)} \sum_{i=1}^{m}(y_i - wx_i - b)^2$$

这称为最小二乘法（Least Square Method）。

对于多元线性回归，我们有：

$$f(x_i) = w^T x_i + b$$

同样使用最小二乘法，可得：

$$w^* = (X^TX)^{-1}X^Ty$$

当$X^TX$为满秩矩阵或正定矩阵时，上式有唯一解。

线性几率回归

虽然线性回归简单且具有很好的可解释性，但它只能用于回归任务。对于分类任务，我们需要找到单调可微函数将分类任务的真实标记 y 与线性回归模型的预测值联系起来。

考虑二分类任务，其输出标记$y \in \{0, 1\}$。线性回归模型产生的预测值$z = w^Tx + b$是实值，我们需将实值 z 转换为 0/1 值。最理想的是”单位阶跃函数”，但该函数不连续，不能直接用作广义线性模型中的联系函数。

**对数几率函数（Logistic Function）**是常用的替代函数：

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

将其代入，得到：

$$y = \frac{1}{1 + e^{-(w^Tx + b)}}$$

这样的模型称为逻辑回归（Logistic Regression）或对数几率回归。

线性判别分析

**线性判别分析（Linear Discriminant Analysis, LDA）**的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。

给定数据集$D = \{(x_i, y_i)\}_{i=1}^m$，令$X_i$、$\mu_i$、$\Sigma_i$分别表示第 i 类示例的集合、均值向量、协方差矩阵。

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

同时考虑二者，则可得到 LDA 的最大化目标：

$$J = \frac{\|w^T\mu_0 - w^T\mu_1\|_2^2}{w^T\Sigma_0 w + w^T\Sigma_1 w} = \frac{w^TS_bw}{w^TS_ww}$$

多分类学习

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

一对一（One vs One, OvO）：将 N 个类别两两配对，产生$\frac{N(N-1)}{2}$个二分类任务。

一对其余（One vs Rest, OvR）：每次将一个类的样例作为正例、所有其他类的样例作为反例来训练 N 个分类器。

多对多（Many vs Many, MvM）：每次将若干个类作为正类，若干个其他类作为反类。

类别不平衡问题

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

类别不平衡就是指分类任务中不同类别的训练样例数目差别很大的情况。不失一般性，假设正类样例较少，负类样例较多。

**再缩放（Rescaling）**是类别不平衡学习的一个基本策略。在用$y = \frac{1}{1 + e^{-(w^Tx+b)}}$进行预测时，事实上是在用预测出的 y 值与一个阈值进行比较，通常该阈值取为 0.5。当训练集中正、负样例的数目不同时，令$m^+$表示正例数目，$m^-$表示负例数目，则观测几率是$\frac{m^+}{m^-}$，由于我们通常假设训练集是真实样本总体的无偏采样，因此观测几率就代表了真实几率。

决策树

决策树是一类常见的机器学习方法，它基于树形结构来进行决策。

决策树基本概念

**决策树（Decision Tree）**是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的”纯度”越来越高。

决策树的构造

ID3 算法

ID3 算法使用**信息增益（Information Gain）**来选择划分属性。

给定样本集合 D，假定当前样本集合 D 中第 k 类样本所占比例为$p_k (k=1,2,\ldots,|y|)$，则 D 的信息熵定义为：

$$Ent(D) = -\sum_{k=1}^{|y|}p_k \log_2 p_k$$

信息熵的值越小，则 D 的纯度越高。

假定离散属性 a 有 V 个可能的取值$\{a^1, a^2, \ldots, a^V\}$，若使用 a 来对样本集 D 进行划分，则会产生 V 个分支节点，其中第 v 个分支节点包含了 D 中所有在属性 a 上取值为$a^v$的样本，记为$D^v$。

用属性 a 对样本集 D 进行划分所获得的信息增益为：

$$Gain(D, a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$

ID3 算法在每个节点选择信息增益最大的属性作为划分属性。

C4.5 算法

C4.5 算法使用**增益率（Gain Ratio）**来选择最优划分属性，以校正信息增益准则对可取值数目较多的属性的偏好问题。

增益率定义为：

$$Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}$$

其中：

$$IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$$

称为属性 a 的”固有值”。属性 a 的可能取值数目越多，则$IV(a)$的值通常会越大。

CART 算法

CART 算法使用**基尼指数（Gini Index）**来选择划分属性。

数据集 D 的纯度可用基尼值来度量：

$$Gini(D) = \sum_{k=1}^{|y|}\sum_{k' \neq k}p_k p_{k'} = 1 - \sum_{k=1}^{|y|}p_k^2$$

直观来说，$Gini(D)$反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小，则数据集 D 的纯度越高。

属性 a 的基尼指数定义为：

$$Gini\_index(D, a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)$$

剪枝处理

**剪枝（Pruning）**是决策树学习算法对付”过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得”太好”了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。

剪枝策略有”预剪枝”和”后剪枝”：

**预剪枝（Prepruning）**是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

**后剪枝（Post-pruning）**是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

连续值与缺失值处理

连续值处理：由于连续属性的可取值数目不再有限，因此不能直接根据连续属性的可取值来对结点进行划分。连续属性离散化的一种最简单的策略是采用二分法对连续属性进行处理。

缺失值处理：现实任务中经常会遇到不完整样本，即样本的某些属性值缺失。有时若简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，这显然是对数据信息极大的浪费。

神经网络

神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。

神经元模型

神经网络中最基本的成分是**神经元（Neuron）**模型。在生物神经网络中，每个神经元与其他神经元相连，当它”兴奋”时，就会向相连的神经元发送化学物质，从而改变这些神经元内的电位；如果某神经元的电位超过了一个阈值，那么它就会被激活，即”兴奋”起来，向其他神经元发送化学物质。

最简单的神经元模型是MP 神经元模型：

$$y = f\left(\sum_{i=1}^{n}w_i x_i - \theta\right)$$

其中：

• $x_i$是输入信号
• $w_i$是连接权重
• $\theta$是阈值
• $f$是激活函数

常用的激活函数包括：

• 阶跃函数：$f(x) = \begin{cases} 1 & x \geq 0 \\ 0 & x < 0 \end{cases}$
• Sigmoid 函数：$f(x) = \frac{1}{1+e^{-x}}$
• ReLU 函数：$f(x) = \max(0, x)$
• tanh 函数：$f(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$

感知机与多层网络

**感知机（Perceptron）**由两层神经元组成，输入层接收外界输入信号后传递给输出层，输出层是 MP 神经元。感知机能容易地实现逻辑与、或、非运算。

但是，感知机只能处理线性可分问题。对于线性不可分问题（如异或问题），需要使用多层感知机（Multi-layer Perceptron, MLP）。

常见的神经网络是形如”输入层-隐藏层-输出层”的层级结构，每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接。这样的神经网络结构通常称为多层前馈神经网络（Multi-layer Feedforward Neural Networks）。

BP 神经网络算法

误差逆传播（Error Backpropagation，简称 BP）算法是训练多层前馈神经网络的经典算法。

对于包含隐层的多层前馈神经网络，由于其包含隐层神经元，而隐层神经元的输出不能直接观测到，所以其学习能力比感知机强得多。

BP 算法的基本思想：首先将错误从输出层逐层向前传播，在传播过程中逐层调整神经元间的连接权值，使得网络输出更接近期望输出。

BP 算法的主要步骤：

1. 前向传播：输入样本从输入层经隐层传播至输出层
2. 计算误差：计算输出层神经元的误差
3. 反向传播：将误差逐层向前传播，计算各层误差
4. 权值更新：根据各层误差调整连接权值

对于输出层神经元 j 的权值更新公式：

$$\Delta w_{hj} = \eta g_j b_h$$

其中$g_j = \hat{y}_j(1-\hat{y}_j)(y_j - \hat{y}_j)$是输出层神经元 j 的梯度项，$\eta$是学习率。

对于隐层神经元 h 的权值更新公式：

$$\Delta v_{ih} = \eta e_h x_i$$

其中$e_h = b_h(1-b_h)\sum_{j=1}^{l}w_{hj}g_j$是隐层神经元 h 的梯度项。

全局最小与局部最小

神经网络的训练过程可看作一个参数寻优过程，即在参数空间中寻找一组最优参数使得训练集上的累积误差最小。

在现实任务中，人们常采用以下策略来试图”跳出”局部最小：

• 多组不同参数值初始化多个神经网络，取其中误差最小的解作为最终参数
• 模拟退火（Simulated Annealing）：在每一步都以一定的概率接受比当前解更差的结果
• 随机梯度下降：在计算梯度时加入了随机因素
• **遗传算法（Genetic Algorithms）**等进化计算方法也常用来训练神经网络以更好地逼近全局最优

深度学习

理论上，参数足够多的前馈神经网络能以任意精度逼近任意复杂度的连续函数，但这并不意味着学习能力随网络层数的增加而提高，因为学习能力除了与网络的逼近能力有关，还与学习算法有关。

深度学习（Deep Learning）通常是指很多隐层的神经网络。无监督逐层训练是多隐层网络训练的有效手段，其基本思想是每次训练一层隐结点，训练时将上一层隐结点的输出作为输入，而本层隐结点的输出作为下一层的输入，这称为预训练（Pre-training）。

典型的深度学习模型包括：

• 深度信念网络（Deep Belief Network, DBN）
• 卷积神经网络（Convolutional Neural Network, CNN）
• 循环神经网络（Recurrent Neural Network, RNN）
• 长短时记忆网络（Long Short-Term Memory, LSTM）

支持向量机

支持向量机（Support Vector Machine, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。

函数间隔与几何间隔

函数间隔

对于给定的训练数据集 T 和超平面$(w, b)$，定义超平面关于样本点$(x_i, y_i)$的函数间隔为：

$$\hat{\gamma}_i = y_i(w \cdot x_i + b)$$

定义超平面关于训练数据集 T 的函数间隔为超平面关于 T 中所有样本点的函数间隔的最小值：

$$\hat{\gamma} = \min_{i=1,\ldots,N} \hat{\gamma}_i$$

几何间隔

对于给定的训练数据集 T 和超平面$(w, b)$，定义超平面关于样本点$(x_i, y_i)$的几何间隔为：

$$\gamma_i = y_i \left(\frac{w}{\|w\|} \cdot x_i + \frac{b}{\|w\|}\right)$$

定义超平面关于训练数据集 T 的几何间隔为超平面关于 T 中所有样本点的几何间隔的最小值：

$$\gamma = \min_{i=1,\ldots,N} \gamma_i$$

函数间隔和几何间隔的关系是：

$$\gamma = \frac{\hat{\gamma}}{\|w\|}$$

最大间隔与支持向量

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

对线性可分的训练数据集，线性可分支持向量机的学习目标是在线性可分约束条件下，求解几何间隔最大化问题：

$$\max_{w,b} \gamma$$ $$s.t. \quad y_i \left(\frac{w}{\|w\|} \cdot x_i + \frac{b}{\|w\|}\right) \geq \gamma, \quad i = 1,2,\ldots,N$$

这等价于最小化$\frac{1}{2}\|w\|^2$：

$$\min_{w,b} \frac{1}{2}\|w\|^2$$ $$s.t. \quad y_i(w \cdot x_i + b) \geq 1, \quad i = 1,2,\ldots,N$$

在线性可分支持向量机中，使约束条件$y_i(w \cdot x_i + b) - 1 = 0$的样本点$(x_i, y_i)$称为支持向量（Support Vector）。

从原始优化问题到对偶问题

通过拉格朗日乘数法，可以将原始的约束优化问题转化为对偶问题。

构造拉格朗日函数：

$$L(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^{N} \alpha_i [y_i(w \cdot x_i + b) - 1]$$

其中$\alpha_i \geq 0$是拉格朗日乘数。

对偶问题为：

$$\max_{\alpha} W(\alpha) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)$$ $$s.t. \quad \sum_{i=1}^{N} \alpha_i y_i = 0, \quad \alpha_i \geq 0, \quad i = 1,2,\ldots,N$$

根据 KKT 条件，最优解需要满足：

$$\alpha_i[y_i(w \cdot x_i + b) - 1] = 0$$

这意味着如果$\alpha_i > 0$，则必有$y_i(w \cdot x_i + b) = 1$，即对应的$x_i$是支持向量。

核函数

当训练数据线性不可分时，支持向量机通过使用**核技巧（Kernel Trick）**将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

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

$$f(x) = w^T\phi(x) + b$$

**核函数（Kernel Function）**定义为：

$$\kappa(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle = \phi(x_i)^T \phi(x_j)$$

常用的核函数包括：

线性核：$\kappa(x_i, x_j) = x_i^T x_j$

多项式核：$\kappa(x_i, x_j) = (x_i^T x_j)^d$

高斯核（RBF 核）：$\kappa(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)$

拉普拉斯核：$\kappa(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|}{\sigma}\right)$

软间隔支持向量机

在前面的讨论中，我们假设训练样本是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

**软间隔（Soft Margin）**支持向量机允许某些样本不满足约束：

$$y_i(w^T x_i + b) \geq 1 - \xi_i$$

其中$\xi_i \geq 0$是松弛变量（Slack Variable）。

软间隔支持向量机的目标函数为：

$$\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{m} \xi_i$$

其中$C > 0$是正则化参数。当$C$无穷大时，所有样本都必须满足约束，等价于硬间隔支持向量机；当$C$取有限值时，允许一些样本不满足约束。

贝叶斯分类器

贝叶斯分类器是一类概率框架下的统计学习分类器，它基于贝叶斯定理来进行分类决策。

贝叶斯决策论

**贝叶斯决策论（Bayesian Decision Theory）**是概率框架下实施决策的基本方法。

假设有 N 种可能的类别标记，即$\mathcal{Y} = \{c_1, c_2, \ldots, c_N\}$，$\lambda_{ij}$是将一个真实标记为$c_j$的样本误分类为$c_i$所产生的损失。基于后验概率$P(c_i|x)$可获得将样本$x$分类为$c_i$所产生的期望损失，即在样本$x$上的条件风险（Conditional Risk）：

$$R(c_i|x) = \sum_{j=1}^{N} \lambda_{ij} P(c_j|x)$$

我们的任务是寻找一个判定准则$h: \mathcal{X} \mapsto \mathcal{Y}$以最小化总体风险：

$$R(h) = E_x[R(h(x)|x)]$$

显然，对每个样本$x$，若$h(x) = \arg\min_{c \in \mathcal{Y}} R(c|x)$，则总体风险$R(h)$也将被最小化。这就产生了贝叶斯判定准则（Bayes Decision Rule）：为最小化总体风险，只需在每个样本上选择那个能使条件风险$R(c|x)$最小的类别标记。

此时$h(x) = \arg\min_{c \in \mathcal{Y}} R(c|x)$称为贝叶斯最优分类器（Bayes Optimal Classifier），与之对应的总体风险$R(h^*)$称为贝叶斯风险（Bayes Risk）。

极大似然法

**极大似然估计（Maximum Likelihood Estimation, MLE）**是根据数据采样来估计概率分布参数的经典方法。

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

$$P(D_c|\theta_c) = \prod_{x \in D_c} P(x|\theta_c)$$

对$\theta_c$进行极大似然估计，就是去寻找能最大化似然$P(D_c|\theta_c)$的参数值$\hat{\theta}_c$。直观上看，极大似然估计是试图找到能使观测数据（即训练集）出现可能性最大的参数值。

$$\hat{\theta}_c = \arg\max_{\theta_c} P(D_c|\theta_c)$$

由于连乘操作易造成下溢，通常使用对数似然：

$$LL(\theta_c) = \log P(D_c|\theta_c) = \sum_{x \in D_c} \log P(x|\theta_c)$$

朴素贝叶斯分类器

朴素贝叶斯（Naive Bayes）分类器采用了”属性条件独立性假设”：对已知类别，假设所有属性相互独立。换言之，假设每个属性独立地对分类结果发生影响。

基于属性条件独立性假设，贝叶斯公式可重写为：

$$P(c|x) = \frac{P(c)P(x|c)}{P(x)} = \frac{P(c)}{P(x)} \prod_{i=1}^{d} P(x_i|c)$$

其中 d 为属性数目，$x_i$为$x$在第 i 个属性上的取值。

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

$$h(x) = \arg\max_{c \in \mathcal{Y}} P(c) \prod_{i=1}^{d} P(x_i|c)$$

这就是朴素贝叶斯分类器的表达式。

对于离散属性，令$D_{c,x_i}$表示在第 c 类样本中在第 i 个属性上取值为$x_i$的样本组成的集合，则条件概率$P(x_i|c)$可估计为：

$$P(x_i|c) = \frac{|D_{c,x_i}|}{|D_c|}$$

对于连续属性，可考虑概率密度函数，假定$p(x_i|c) \sim \mathcal{N}(\mu_{c,i}, \sigma_{c,i}^2)$，其中$\mu_{c,i}$和$\sigma_{c,i}^2$分别是第 c 类样本在第 i 个属性上取值的均值和方差。

为了避免其他属性携带的信息被训练集中未出现的属性值”抹去”，在估计概率值时通常要进行平滑（Smoothing），常用拉普拉斯修正（Laplacian Correction）：

$$\hat{P}(c) = \frac{|D_c| + 1}{|D| + N}$$ $$\hat{P}(x_i|c) = \frac{|D_{c,x_i}| + 1}{|D_c| + N_i}$$

其中$N$表示训练集 D 中可能的类别数，$N_i$表示第 i 个属性可能的取值数。

EM 算法

**EM 算法（Expectation-Maximization Algorithm）**是一种迭代算法，用于含有隐变量（hidden variable）的概率模型参数的极大似然估计，或极大后验概率估计。

EM 算法思想

EM 算法是一种迭代优化策略，由于它的计算方法中交替进行求期望（E）和求极大（M），所以有此名。

给定观测变量数据 Y，隐变量 Z，联合分布$P(Y,Z|\theta)$，条件分布$P(Z|Y,\theta)$，EM 算法通过迭代求$L(\theta) = \log P(Y|\theta)$的极大似然估计。

每次迭代包含两步：

• E 步（Expectation）：求期望，即求$\log P(Y,Z|\theta)$关于在给定观测数据 Y 和当前参数$\theta^{(i)}$下对未观测数据 Z 的条件概率分布$P(Z|Y,\theta^{(i)})$的期望
• M 步（Maximization）：求极大，即极大化在 E 步求得的期望，得到新的参数值$\theta^{(i+1)}$

EM 算法数学推导

设观测数据为$Y = (Y_1, Y_2, \ldots, Y_N)$，隐变量为$Z = (Z_1, Z_2, \ldots, Z_N)$，参数为$\theta$。

观测数据的似然函数为：

$$L(\theta) = \log P(Y|\theta) = \log \sum_Z P(Y,Z|\theta)$$

由于$\sum_Z P(Y,Z|\theta)$包含未观测的隐变量 Z，直接优化$L(\theta)$通常困难。

EM 算法采用逐步近似极大似然估计的方法：假设在第 i 次迭代后$\theta$的估计值是$\theta^{(i)}$，希望新估计值$\theta$能使$L(\theta)$增加，即$L(\theta) > L(\theta^{(i)})$。

考虑两者的差：

$$L(\theta) - L(\theta^{(i)}) = \log \left(\sum_Z P(Y,Z|\theta)\right) - \log P(Y|\theta^{(i)})$$

利用 Jensen 不等式可以得到$L(\theta)$的下界，进而通过优化下界来优化$L(\theta)$。

EM 算法流程

输入：观测变量数据$Y$，隐变量数据$Z$，联合分布$P(Y,Z|\theta)$，条件分布$P(Z|Y,\theta)$

输出：模型参数$\theta$

1. 选择参数的初值$\theta^{(0)}$，开始迭代
2. E 步：记$\theta^{(i)}$为第 i 次迭代参数$\theta$的估计值，在第 i+1 次迭代的 E 步，计算 $$Q(\theta, \theta^{(i)}) = E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}] = \sum_Z \log P(Y,Z|\theta) P(Z|Y,\theta^{(i)})$$
3. M 步：求使$Q(\theta, \theta^{(i)})$极大化的$\theta$，确定第 i+1 次迭代的参数的估计值$\theta^{(i+1)}$ $$\theta^{(i+1)} = \arg\max_\theta Q(\theta, \theta^{(i)})$$
4. 重复第 2 步和第 3 步，直到收敛

EM 算法的一个重要性质是：如果$P(Y,Z|\theta)$有上界，则$L(\theta^{(i)})$单调递增，即$L(\theta^{(i+1)}) \geq L(\theta^{(i)})$。

集成学习

**集成学习（Ensemble Learning）**通过构建并结合多个学习器来完成学习任务。集成学习的一般结构是：先产生一组”个体学习器”，再用某种策略将它们结合起来。

个体与集成

集成学习把多个学习器结合起来，常可获得比单一学习器显著优越的泛化性能。这对”弱学习器”尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也被直接称为弱学习器。

要获得好的集成，个体学习器应”好而不同”，即个体学习器要有一定的准确性，即学习器不能太坏，并且要有多样性，即学习器间具有差异。

Boosting

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

AdaBoost 算法是 Boosting 算法的典型代表：

1. 初始化训练数据的权值分布：$D_1 = (w_{11}, \ldots, w_{1i}, \ldots, w_{1N})$，$w_{1i} = \frac{1}{N}$，$i = 1,2,\ldots,N$
2. 对$m = 1,2,\ldots,M$：
   • 使用具有权值分布$D_m$的训练数据集学习，得到基分类器$G_m(x)$
   • 计算$G_m(x)$在训练数据集上的分类误差率：$e_m = \sum_{i=1}^N P(G_m(x_i) \neq y_i) = \sum_{i=1}^N w_{mi}I(G_m(x_i) \neq y_i)$
   • 计算$G_m(x)$的系数：$\alpha_m = \frac{1}{2}\log\frac{1-e_m}{e_m}$
   • 更新训练数据集的权值分布：$D_{m+1} = (w_{m+1,1}, \ldots, w_{m+1,i}, \ldots, w_{m+1,N})$ 其中$w_{m+1,i} = \frac{w_{mi}}{Z_m}\exp(-\alpha_m y_i G_m(x_i))$，$Z_m$是规范化因子
3. 构建基分类器的线性组合：$f(x) = \sum_{m=1}^M \alpha_m G_m(x)$
4. 得到最终分类器：$G(x) = \text{sign}(f(x)) = \text{sign}\left(\sum_{m=1}^M \alpha_m G_m(x)\right)$

Bagging 与 Random Forest

Bagging

**Bagging（Bootstrap Aggregating）**是并行式集成学习方法最著名的代表。它直接基于自助采样法，给定包含 m 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过 m 次随机采样操作，我们得到含 m 个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。

Bagging 算法流程：

1. 从原始样本集中使用 Bootstrapping 方法随机抽取 n 个训练集，每个训练集的样本数量是 m（有放回抽样）
2. 基于每个训练集训练出一个基学习器
3. 将 n 个基学习器进行结合：分类问题使用投票方式，回归问题使用平均方式

随机森林

**随机森林（Random Forest）**是 Bagging 的一个扩展变体。RF 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

具体来说，传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性；而在 RF 中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 k 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数 k 控制了随机性的引入程度：若令 k=d，则基决策树的构建与传统决策树相同；若令 k=1，则是随机选择一个属性用于划分；一般情况下，推荐值$k = \log_2 d$。

结合策略

学习器结合可能从三个方面带来好处：

• 统计的方面：学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险
• 计算的方面：学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险
• 表示的方面：某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似

平均法（回归问题）

简单平均法：

$$H(x) = \frac{1}{T}\sum_{i=1}^T h_i(x)$$

加权平均法：

$$H(x) = \sum_{i=1}^T w_i h_i(x)$$

其中$w_i$是个体学习器$h_i$的权重，通常要求$w_i \geq 0$，$\sum_{i=1}^T w_i = 1$。

投票法（分类问题）

绝对多数投票法：若某标记得票过半数，则预测为该标记；否则拒绝预测。

相对多数投票法：预测为得票最多的标记，若同时有多个标记获得最高票数，则从中随机选取一个。

加权投票法：

$$H(x) = \arg\max_{y \in \mathcal{Y}} \sum_{i=1}^T w_i \mathbb{I}(h_i(x) = y)$$

学习法

当训练数据很多时，一种更为强大的结合策略是使用”学习法”，即通过另一个学习器来进行结合。Stacking是学习法的典型代表。这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器。

Stacking 先从初始训练集训练出初级学习器，然后”生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

多样性（diversity）

误差-分歧分解说明，个体学习器准确性越高、多样性越大，则集成越好。

多样性度量：多样性度量（diversity measure）是用于度量集成中个体分类器的多样性的方法，典型做法是考虑个体分类器的两两相似/不相似性。

常见的多样性度量包括：

• 不合度量：$dis_{ij} = \frac{b + c}{m}$
• 相关系数：$\rho_{ij} = \frac{ad - bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}$
• Q-统计量：$Q_{ij} = \frac{ad - bc}{ad + bc}$
• κ-统计量：$\kappa = \frac{p_1 - p_2}{1 - p_2}$

其中$p_1 = \frac{a+d}{m}$是两个分类器取得一致的概率，$p_2 = \frac{(a+b)(a+c) + (c+d)(b+d)}{m^2}$是两个分类器偶然取得一致的概率。

聚类

在”无监督学习”中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是”聚类”。

**聚类（Clustering）**试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个”簇（cluster）“。通过这样的划分，每个簇可能对应于一些潜在的概念（类别）。

距离度量

对函数$dist(\cdot, \cdot)$，若它是一个”距离度量（distance measure）“，则需满足一些基本性质：

• 非负性：$dist(x_i, x_j) \geq 0$
• 同一性：$dist(x_i, x_j) = 0$当且仅当$x_i = x_j$
• 对称性：$dist(x_i, x_j) = dist(x_j, x_i)$
• 直递性：$dist(x_i, x_j) \leq dist(x_i, x_k) + dist(x_k, x_j)$

给定样本$x_i = (x_{i1}; x_{i2}; \ldots; x_{in})$与$x_j = (x_{j1}; x_{j2}; \ldots; x_{jn})$，最常用的是闵可夫斯基距离（Minkowski distance）：

$$dist_{mk}(x_i, x_j) = \left(\sum_{u=1}^n |x_{iu} - x_{ju}|^p\right)^{\frac{1}{p}}$$

当$p=2$时，闵可夫斯基距离即欧氏距离（Euclidean distance）：

$$dist_{ed}(x_i, x_j) = \|x_i - x_j\|_2 = \sqrt{\sum_{u=1}^n (x_{iu} - x_{ju})^2}$$

当$p=1$时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）：

$$dist_{man}(x_i, x_j) = \|x_i - x_j\|_1 = \sum_{u=1}^n |x_{iu} - x_{ju}|$$

性能度量

聚类性能度量亦称聚类”有效性指标（validity index）“。与监督学习中的性能度量作用相似，聚类性能度量用于评估聚类结果的好坏。

外部指标

**外部指标（external index）**是将聚类结果与某个”参考模型”（reference model）进行比较，通常参考模型由领域专家给出。

假定聚类给出的簇划分为$\mathcal{C} = \{C_1, C_2, \ldots, C_k\}$，参考模型给出的簇划分为$\mathcal{C}^* = \{C_1^*, C_2^*, \ldots, C_s^*\}$。相应地，令$\lambda$与$\lambda^*$分别表示与$\mathcal{C}$和$\mathcal{C}^*$对应的 0-1 矩阵，其中$\lambda_{ij} = 1$若$x_i$与$x_j$属于同一个簇，否则$\lambda_{ij} = 0$。

可将样本对$(x_i, x_j)$分为以下四种情况：

• $SS$：$x_i$与$x_j$在$\mathcal{C}$中属于相同簇，在$\mathcal{C}^*$中也属于相同簇
• $SD$：$x_i$与$x_j$在$\mathcal{C}$中属于相同簇，在$\mathcal{C}^*$中属于不同簇
• $DS$：$x_i$与$x_j$在$\mathcal{C}$中属于不同簇，在$\mathcal{C}^*$中属于相同簇
• $DD$：$x_i$与$x_j$在$\mathcal{C}$中属于不同簇，在$\mathcal{C}^*$中也属于不同簇

基于这四种情况，常用的外部指标有：

Jaccard 系数（JC）：

$$JC = \frac{a}{a + b + c}$$

FM 指数（FMI）：

$$FMI = \sqrt{\frac{a}{a + b} \cdot \frac{a}{a + c}}$$

Rand 指数（RI）：

$$RI = \frac{2(a + d)}{m(m-1)}$$

其中$a = |SS|$，$b = |SD|$，$c = |DS|$，$d = |DD|$，且$a + b + c + d = \frac{m(m-1)}{2}$。

内部指标

**内部指标（internal index）**直接考察聚类结果而不利用任何参考模型。考虑聚类结果的簇划分$\mathcal{C} = \{C_1, C_2, \ldots, C_k\}$，定义：

• 簇内距离：$avg(C) = \frac{2}{|C|(|C|-1)} \sum_{1 \leq i < j \leq |C|} dist(x_i, x_j)$
• 簇间距离：$d_{min}(C_i, C_j) = \min_{x_i \in C_i, x_j \in C_j} dist(x_i, x_j)$
• 簇间距离：$d_{cen}(C_i, C_j) = dist(\mu_i, \mu_j)$

其中$\mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x$是簇$C_i$的中心。

基于上述定义，常用的内部指标有：

DB 指数（DBI）：

$$DBI = \frac{1}{k} \sum_{i=1}^k \max_{j \neq i} \left(\frac{avg(C_i) + avg(C_j)}{d_{cen}(C_i, C_j)}\right)$$

Dunn 指数（DI）：

$$DI = \min_{1 \leq i \leq k} \left\{ \min_{j \neq i} \left(\frac{d_{min}(C_i, C_j)}{\max_{1 \leq l \leq k} diam(C_l)}\right) \right\}$$

其中$diam(C) = \max_{x_i, x_j \in C} dist(x_i, x_j)$是簇 C 的直径。

原型聚类

**原型聚类（prototype-based clustering）**亦称”基于原型的聚类”，此类算法假设聚类结构能通过一组原型刻画。

K-Means

给定样本集$D = \{x_1, x_2, \ldots, x_m\}$，k 均值（k-means）算法针对聚类所得簇划分$\mathcal{C} = \{C_1, C_2, \ldots, C_k\}$最小化平方误差：

$$E = \sum_{i=1}^k \sum_{x \in C_i} \|x - \mu_i\|_2^2$$

其中$\mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x$是簇$C_i$的均值向量。

k 均值算法采用了贪心策略，通过迭代优化来近似求解上式。算法流程如下：

1. 从 D 中随机选择 k 个样本作为初始均值向量$\{\mu_1, \mu_2, \ldots, \mu_k\}$
2. repeat
3. 令$C_i = \emptyset (1 \leq i \leq k)$
4. for $j = 1, 2, \ldots, m$ do
5. 计算样本$x_j$与各均值向量的距离：$d_{ji} = \|x_j - \mu_i\|_2$
6. 根据距离最近的均值向量确定$x_j$的簇标记：$\lambda_j = \arg\min_{i \in \{1,2,\ldots,k\}} d_{ji}$
7. 将样本$x_j$划入相应的簇：$C_{\lambda_j} = C_{\lambda_j} \cup \{x_j\}$
8. end for
9. for $i = 1, 2, \ldots, k$ do
10. 计算新均值向量：$\mu_i' = \frac{1}{|C_i|} \sum_{x \in C_i} x$
11. if $\mu_i' \neq \mu_i$ then
12. 将当前均值向量更新为$\mu_i'$
13. else
14. 保持当前均值向量不变
15. end if
16. end for
17. until 当前均值向量均未更新

学习向量量化（LVQ）

**学习向量量化（Learning Vector Quantization，简称 LVQ）**也是试图找到一组原型向量来刻画聚类结构，但与一般聚类算法不同的是，LVQ 假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

给定样本集$D = \{(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)\}$，每个样本$x_j$是由 n 个属性描述的特征向量$(x_{j1}; x_{j2}; \ldots; x_{jn})$，$y_j \in \mathcal{Y}$是样本$x_j$的类别标记。LVQ 的目标是学得一组 n 维原型向量$\{p_1, p_2, \ldots, p_q\}$，每个原型向量代表一个聚类簇，簇标记$t_i \in \mathcal{Y}$。

高斯混合聚类

与 k 均值、LVQ 用原型向量来刻画聚类结构不同，高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型。

对 n 维样本空间$\mathcal{X}$中的随机向量$x$，若$x$服从高斯分布，其概率密度函数为：

$$p(x) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}} e^{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)}$$

其中$\mu$是 n 维均值向量，$\Sigma$是$n \times n$的协方差矩阵。

密度聚类

**密度聚类（density-based clustering）**亦称”基于密度的聚类”，此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

**DBSCAN（Density-Based Spatial Clustering of Applications with Noise）**是一种著名的密度聚类算法，它基于一组”邻域”参数$(ε, MinPts)$来刻画样本分布的紧密程度。

层次聚类

**层次聚类（hierarchical clustering）**试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用”自底向上”的聚合策略，也可采用”自顶向下”的分拆策略。

**AGNES（AGglomerative NESting）**是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数。

降维与度量学习

在现实的机器学习任务中，我们往往会遇到维数很高的数据。在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为”维数灾难”。

**降维（dimension reduction）**是缓解维数灾难的一个重要途径。

K 近邻学习

k 近邻（k-Nearest Neighbor，简称 kNN）学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 k 个训练样本，然后基于这 k 个”邻居”的信息来进行预测。

在分类任务中，可使用”投票法”，即选择这 k 个样本中出现最多的类别标记作为预测结果；在回归任务中，可使用”平均法”，即将这 k 个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

k 近邻学习的一个明显优点是其天然能够处理多分类任务。

MDS 算法

**多维缩放（Multiple Dimensional Scaling，简称 MDS）**要求原始空间中样本之间的距离在低维空间中得以保持。

假定 m 个样本在原始空间的距离矩阵为$D \in \mathbb{R}^{m \times m}$，其第$(i,j)$元素$dist_{ij}$为样本$x_i$到$x_j$的距离。我们的目标是获得样本在$d'$维空间（$d' \leq d$）的表示$Z \in \mathbb{R}^{d' \times m}$，且任意两个样本在$d'$维空间中的欧氏距离等于原始空间中的距离，即$\|z_i - z_j\| = dist_{ij}$。

主成分分析（PCA）

**主成分分析（Principal Component Analysis，简称 PCA）**是最常用的一种降维方法。PCA 的主要思想是将 n 维特征映射到 k 维上（k<n），这 k 维是全新的正交特征。这 k 维特征称为主成分，是重新构造出来的 k 维特征，而不是简单地从 n 维特征中去除其余 n-k 维特征。

给定数据集$D = \{x_1, x_2, \ldots, x_m\}$，$x_i \in \mathbb{R}^n$。PCA 的目标是将这些样本投影到一个$d'$维超平面上，使得投影后样本的方差最大。不失一般性，设投影超平面的法向量为$w = (w_1; w_2; \ldots; w_n)$，$\|w\|_2 = 1$。

样本点$x_i$在这个超平面上的投影是$w^T x_i$，若所有样本点的投影能尽可能分开，应该使投影后样本的方差最大化：

$$\max_w \sum_{i=1}^m (w^T x_i)^2 - \left(\sum_{i=1}^m w^T x_i\right)^2$$

核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而，在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入。

**核化线性降维（Kernelized Linear Dimensionality Reduction）**的推广是非线性降维的重要途径。

流形学习

**流形学习（manifold learning）**是一类借鉴了拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间，换言之，它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。

等度量映射（Isomap）

**等度量映射（Isometric Mapping，简称 Isomap）**的基本出发点是认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。

Isomap 认为低维流形上两点间的距离就是”测地线”距离，即在流形上两点之间最短路径的长度。

局部线性嵌入（LLE）

**局部线性嵌入（Locally Linear Embedding，简称 LLE）**试图保持邻域内样本之间的线性关系。

度量学习

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应在样本上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。

**度量学习（metric learning）**这正是这样一类方法，它直接学习出一个合适的距离度量。

特征选择与稀疏学习

在现实机器学习任务中，获得数据之后通常先要进行特征选择。进行特征选择有两个很重要的原因：首先，我们经常会遇到”维数灾难”问题；其次，去除不相关特征往往会降低学习任务的难度。

子集搜索与评价

特征选择过程主要由三个重要环节组成：子集搜索、子集评价、停止准则。其中子集搜索与子集评价是关键环节。

子集搜索：给定特征集合$\{a_1, a_2, \ldots, a_d\}$，我们可将其任一子集记为特征子集。显然，d 个特征共有$2^d$个不同的子集。如何从这$2^d$个候选特征子集中选取包含无关特征、无冗余特征的特征子集，这就是子集搜索问题。

常见的子集搜索策略有：

• 前向搜索（Forward Selection）：从空集开始，每次选择一个特征加入当前特征子集
• 后向搜索（Backward Selection）：从全集开始，每次从当前特征子集中移除一个特征
• 双向搜索（Bidirectional Search）：同时进行前向搜索和后向搜索，在某处相遇时停止

子集评价：给定数据集 D，假定 D 中第 i 类样本所占的比例为$p_i (i=1,2,\ldots,|\mathcal{Y}|)$。对属性子集 A，假定根据其取值将 D 分成了 V 个子集$\{D^1, D^2, \ldots, D^V\}$，每个子集中第 i 类样本所占的比例为$p_i^v$。于是，子集 A 的信息增益为：

$$Gain(A) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)$$

其中$Ent(D) = -\sum_{i=1}^{|\mathcal{Y}|} p_i \log_2 p_i$。

过滤式选择（Relief）

过滤式（Filter）特征选择先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。**Relief（Relevant Features）**是一种著名的过滤式特征选择方法。

Relief 的关键思路是：对每个特征，如果它与同类样本的距离小、与异类样本的距离大，则说明该特征对区分同类与异类样本很有用，应当给它较大的权重；反之，如果它与同类样本的距离大、与异类样本的距离小，则说明该特征起负面作用，应当给它较小的权重。

Relief 算法流程：

1. 从训练集 D 中随机选择一个样本$x_i$，找出$x_i$的同类最近邻样本（称为”near-hit”）$x_{i,nh}$和异类最近邻样本（称为”near-miss”）$x_{i,nm}$
2. 更新每个特征的权重： $$w^j = w^j - \frac{(x_i^j - x_{i,nh}^j)^2}{m} + \frac{(x_i^j - x_{i,nm}^j)^2}{m}$$
3. 重复上述过程 m 次
4. 最终，权重大于某个阈值 θ 的特征将被选择

包裹式选择（LVW）

包裹式（Wrapper）特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能的特征子集。

**LVW（Las Vegas Wrapper）**是一种典型的包裹式特征选择方法。LVW 在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则。

嵌入式选择与正则化

嵌入式（Embedded）特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。

给定数据集$D = \{(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)\}$，我们考虑最简单的线性回归模型，以平方误差为损失函数，则优化目标为：

$$\min_w \sum_{i=1}^m (y_i - w^T x_i)^2$$

当样本特征很多、样本数相对较少时，很容易陷入过拟合。**正则化（Regularization）**是缓解过拟合的常用手段。

$L_2$正则化：

$$\min_w \sum_{i=1}^m (y_i - w^T x_i)^2 + \lambda \|w\|_2^2$$

$L_1$正则化：

$$\min_w \sum_{i=1}^m (y_i - w^T x_i)^2 + \lambda \|w\|_1$$

其中$\lambda > 0$称为正则化参数。$L_1$正则化倾向于产生稀疏解，即求得的 w 会有较少的非零分量；$L_2$正则化倾向于产生稠密解，即求得的 w 的分量会比较平滑、接近但非零。

稀疏表示与字典学习

当样本具有稀疏表示时，对学习任务来说会有不少好处，例如线性分类器的分离超平面仅由少数样本确定，这样不仅降低了计算开销，也大大降低了过拟合的风险。

**字典学习（Dictionary Learning）**试图找到一个字典，使得样本能被字典很好地表示。给定数据集$D = \{x_1, x_2, \ldots, x_m\}$，字典学习最简单的形式为：

$$\min_{B,\alpha_i} \sum_{i=1}^m \|x_i - B\alpha_i\|_2^2 + \lambda \sum_{i=1}^m \|\alpha_i\|_1$$

其中$B \in \mathbb{R}^{d \times k}$为字典矩阵，$k$称为字典的大小，通常由用户指定，$\alpha_i \in \mathbb{R}^k$则是样本$x_i \in \mathbb{R}^d$的稀疏表示。

压缩感知

**压缩感知（Compressed Sensing）**是近年来极为热门的领域，在信号处理、统计学习、计算机视觉等领域都有重要应用。

压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。具体来说，假定有长度为 m 的离散信号$x \in \mathbb{R}^m$，我们仅能观测到$y = \Phi x \in \mathbb{R}^n$，其中$\Phi \in \mathbb{R}^{n \times m}$是”感知矩阵”，$n \ll m$。压缩感知要解决的问题是：如何基于$\Phi$和$y$来恢复$x$。

计算学习理论

**计算学习理论（Computational Learning Theory）**试图分析学习任务的困难本质，为学习算法提供理论保证，并帮助人们理解机器学习的能力与局限。

PAC 学习

计算学习理论中最基本的是概率近似正确（Probably Approximately Correct, PAC）学习理论。

在 PAC 学习中，我们考虑这样的情形：学习算法能够以较高的概率学得目标概念的近似。这里，“概率”指的是对所有可能的训练集而言，学习算法能产生满足要求的假设的可能性；“近似”指的是学习算法产生的假设与目标概念之间存在一定的误差，但这个误差不超过事先设定的上界。

令$\mathcal{X}$表示样本空间，$\mathcal{H}$表示假设空间。给定训练集$D$，学习算法$\mathfrak{L}$能从假设空间$\mathcal{H}$中返回一个假设$h$，使得该假设尽可能接近目标概念$c$。

对$0 < \varepsilon, \delta < 1$，所有$c \in \mathcal{C}$和分布$\mathcal{D}$，如果存在学习算法$\mathfrak{L}$和多项式函数$poly(\cdot, \cdot, \cdot, \cdot)$，使得对于任何$m \geq poly(1/\varepsilon, 1/\delta, size(x), size(c))$，学习算法$\mathfrak{L}$能从假设空间$\mathcal{H}$中 PAC 辨识概念类$\mathcal{C}$，则称概念类$\mathcal{C}$对假设空间$\mathcal{H}$而言是 PAC 可学习的。

有限假设空间

可分情形

我们先考虑一种比较简单的情形，即目标概念$c \in \mathcal{H}$，且训练集$D$与概念$c$一致（即对训练集中的每个样本$(x,y)$都有$c(x) = y$），这称为”一致”的情形。

令$h$为学习算法$\mathfrak{L}$返回的假设。由于学习算法$\mathfrak{L}$只能观察到训练样本，若$h$在训练集上的表现与$c$一致，那么$\mathfrak{L}$将无法区别$h$和$c$。

对任何$h \in \mathcal{H}$，$h$的”泛化误差”定义为：

$$E(h) = \Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)]$$

不可分情形

现实学习任务往往面临不一致的训练集，即不存在$h \in \mathcal{H}$使训练集上的误差为零。此时学习算法无法再通过训练误差为零来确定假设，而必须考虑如何从训练误差非零的假设中进行选择。

一个自然的想法是选择在训练集上误差最小的假设，这就是经验风险最小化（Empirical Risk Minimization, ERM）原则。

VC 维

现实学习任务所面临的通常是无限假设空间，欲对此种情形的可学习性进行研究，需度量假设空间的复杂度。最常用的办法是考虑假设空间的VC 维（Vapnik-Chervonenkis dimension）。

给定假设空间$\mathcal{H}$和示例集$D = \{x_1, x_2, \ldots, x_m\}$，$\mathcal{H}$中每个假设$h$都能对 D 中示例赋予标记，标记的结果可表示为：

$$h|_D = (h(x_1), h(x_2), \ldots, h(x_m)) \in \{0,1\}^m$$

随着$\mathcal{H}$中假设的变化，我们得到：

$$\Pi_\mathcal{H}(D) = \{h|_D : h \in \mathcal{H}\}$$

这表示假设空间$\mathcal{H}$对示例集 D 所能赋予标记的所有可能结果。一般来说，$|\Pi_\mathcal{H}(D)| \leq 2^m$。

假设空间$\mathcal{H}$的 VC 维是能被$\mathcal{H}$”打散”的最大示例集的大小，即：

$$VC(\mathcal{H}) = \max\{m : \Pi_\mathcal{H}(D) = 2^m\}$$

直观地说，如果假设空间$\mathcal{H}$的 VC 维是$d$，那么存在大小为$d$的示例集能够被假设空间$\mathcal{H}$中的假设按所有可能的$2^d$种方式分开，但不存在任何大小为$d+1$的示例集能被假设空间$\mathcal{H}$按所有可能的$2^{d+1}$种方式分开。

稳定性

**稳定性（Stability）**考虑的是算法在训练集发生变化时，其输出假设的变化情况。直观地看，一个稳定的学习算法对训练集的微小变化应该不敏感，即其输出假设应该比较相似。

半监督学习

现实学习任务中经常会遇到这样的情形：有大量的未标记样本和少量的标记样本。由于标记样本较少，单纯基于标记样本训练往往不能得到好的学习结果；由于未标记样本很多，将其全部标记代价又太高。能否利用未标记样本来辅助学习呢？**半监督学习（Semi-supervised Learning）**正是研究如何利用少量的标记样本和大量的未标记样本进行学习的方法。

生成式方法

生成式（Generative）方法是基于生成式模型的半监督学习方法。此类方法假设所有数据（无论是否有标记）都是由同一个潜在的模型”生成”的。于是，我们可根据已标记数据来估计模型参数，再用这个模型为未标记样本产生标记。

假定样本由高斯混合模型生成：对每个类别，样本先以先验概率$P(y=i)$选择第$i$个高斯成分，再根据高斯分布$\mathcal{N}(\mu_i, \Sigma_i)$生成样本。

在标记数据$(x_i, y_i)$上，参数$\Theta = \{(\alpha_i, \mu_i, \Sigma_i)\}_{i=1}^N$的对数似然为：

$$LL_l(\Theta) = \sum_{i=1}^l \log P(x_i, y_i|\Theta)$$

在未标记数据$\{x_j\}_{j=l+1}^{l+u}$上，对数似然为：

$$LL_u(\Theta) = \sum_{j=l+1}^{l+u} \log P(x_j|\Theta) = \sum_{j=l+1}^{l+u} \log \sum_{i=1}^N P(x_j, y_j=i|\Theta)$$

半监督 SVM

半监督支持向量机（Semi-supervised Support Vector Machine, S3VM）是半监督学习的重要方法，其中最著名的是TSVM（Transductive Support Vector Machine）。

TSVM 考虑这样的假设：若两个样本很相似，则其输出标记也应相似。于是，TSVM 试图找到能将两类标记样本分开，且穿过数据稀疏区域的划分超平面。

基于分歧的方法

基于分歧的方法使用多个学习器，学习器间的”分歧”对未标记样本进行标记。**协同训练（Co-training）**是其典型代表。

协同训练假设数据具有两个充分冗余的视图，即每个视图都足以训练出好的学习器，且两个视图相对独立。协同训练先基于不同视图分别训练一个分类器，然后让分类器去标记只在其视图中置信度高的未标记样本，并将这些样本加入另一个分类器的训练集中。

半监督聚类

**半监督聚类（Semi-supervised Clustering）**指在聚类过程中利用一些监督信息来辅助聚类。

监督信息通常有两种类型：

• Must-link 约束：两个样本必须在同一个簇中
• Cannot-link 约束：两个样本不能在同一个簇中

概率图模型

**概率图模型（Probabilistic Graphical Model）**是一类用图来表达变量相关关系的概率模型。它以图为表示工具，以概率论为理论基础，以数据为分析对象。

隐马尔可夫模型（HMM）

**隐马尔可夫模型（Hidden Markov Model, HMM）**是结构最简单的动态贝叶斯网，它是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。

HMM 中的变量可分为两组：第一组是状态变量$\{y_1, y_2, \ldots, y_n\}$，其中$y_i \in \mathcal{Y}$表示第$i$时刻的系统状态。通常假定状态变量是隐藏的、不可被观测的，因此状态变量亦称隐变量；第二组是观测变量$\{x_1, x_2, \ldots, x_n\}$，其中$x_i \in \mathcal{X}$表示第$i$时刻的观测值。

在 HMM 中有两个重要的假设：

• 齐次马尔可夫假设：任意时刻的隐状态只依赖于其前一个隐状态
• 观测独立假设：任意时刻的观测只依赖于该时刻的隐状态

HMM 评估问题

给定 HMM 参数$\lambda = (A, B, \pi)$和观测序列$O = o_1 o_2 \cdots o_T$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda)$。

可以用前向算法求解：

定义前向概率：$\alpha_t(i) = P(o_1 o_2 \cdots o_t, i_t = q_i | \lambda)$

前向算法步骤：

1. 初值：$\alpha_1(i) = \pi_i b_i(o_1), \quad i = 1, 2, \ldots, N$
2. 递推：$\alpha_{t+1}(j) = \left[\sum_{i=1}^N \alpha_t(i) a_{ij}\right] b_j(o_{t+1}), \quad t = 1, 2, \ldots, T-1; \quad j = 1, 2, \ldots, N$
3. 终止：$P(O|\lambda) = \sum_{i=1}^N \alpha_T(i)$

HMM 解码问题

给定 HMM 参数$\lambda = (A, B, \pi)$和观测序列$O = o_1 o_2 \cdots o_T$，求最有可能的状态序列$I^* = i_1^* i_2^* \cdots i_T^*$。

可以用**维特比算法（Viterbi Algorithm）**求解：

定义在时刻$t$状态为$q_i$的所有单个路径$(i_1, i_2, \ldots, i_t)$中概率最大值为：

$$\delta_t(i) = \max_{i_1, i_2, \ldots, i_{t-1}} P(i_1, i_2, \ldots, i_{t-1}, i_t = i, o_1, o_2, \ldots, o_t | \lambda)$$

HMM 学习问题

已知观测序列$O = o_1 o_2 \cdots o_T$，估计模型$\lambda = (A, B, \pi)$的参数，使得在该模型下观测序列概率$P(O|\lambda)$最大。

可以用Baum-Welch 算法（EM 算法的一个特例）求解。

马尔可夫随机场（MRF）

**马尔可夫随机场（Markov Random Field, MRF）**是典型的马尔可夫网，它是一种著名的无向图模型。图中每个结点表示一个变量，两个变量之间若有边连接，则说明它们有概率依赖关系。

条件随机场（CRF）

**条件随机场（Conditional Random Field, CRF）**试图对多个变量在给定观测值后的条件概率进行建模。设$X = \{x_1, x_2, \ldots, x_n\}$和$Y = \{y_1, y_2, \ldots, y_n\}$分别为观测变量集合和状态变量集合，条件随机场的目标是构建条件概率模型$P(Y|X)$。

学习与推断

变量消去

**变量消去（Variable Elimination）**是精确推断的基本方法。其基本思想很简单：利用乘法对加法的分配律，将多个变量的联合边际分布的计算问题，转化为对部分变量求和的一系列”局部”计算问题。

信念传播

**信念传播（Belief Propagation, BP）**算法将边际分布的计算转化为消息传递过程。

LDA 话题模型

**隐狄利克雷分配（Latent Dirichlet Allocation, LDA）**是话题模型的典型代表，它是一种著名的概率图模型。

LDA 对文档集合中的话题进行建模。它将每篇文档看作是由多个话题混合而成，每个话题则对应词汇上的一个概率分布。

强化学习

**强化学习（Reinforcement Learning）**研究的是智能体（agent）如何在环境（environment）中学习，以获得最大的累积奖赏。

基本要素

强化学习任务通常用**马尔可夫决策过程（Markov Decision Process, MDP）**来描述。

具体来说，机器处于环境$E$中，状态空间为$\mathcal{X}$，其中每个状态$x \in \mathcal{X}$是机器感知到的环境的描述；机器的动作空间为$\mathcal{A}$，其中每个动作$a \in \mathcal{A}$是机器可以采取的动作。若某个动作$a$在状态$x$下不可行，则用$\mathcal{A}(x) \subseteq \mathcal{A}$表示状态$x$下可行的动作集合。

在强化学习中，机器要学习的是一个”策略”$\pi: \mathcal{X} \mapsto \mathcal{A}$，即状态到动作的映射，它指定了在每个状态下应该执行什么动作。

K 摇摆赌博机

**k 摇摆赌博机（k-armed bandit）**是强化学习中的一个经典问题。该问题可以很好地体现强化学习所面临的”探索-利用窘境”（exploration-exploitation dilemma）。

ε-贪心

**ε-贪心（ε-greedy）**算法基于一个概率来对探索和利用进行折中：以$\varepsilon$的概率进行探索，即以均匀概率随机选取一个摇臂；以$1-\varepsilon$的概率进行利用，即选择当前平均奖赏最高的摇臂。

Softmax

Softmax算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中，若摇臂$i$的平均奖赏为$\overline{v}_i$，则选取该摇臂的概率为：

$$P(i) = \frac{e^{\overline{v}_i / \tau}}{\sum_{j=1}^k e^{\overline{v}_j / \tau}}$$

其中$\tau > 0$称为”温度”。$\tau$越小，平均奖赏高的摇臂被选取的概率越高。

有模型学习

如果能构建出环境模型，即转移概率$P_{ss'}^a$和奖赏函数$R_s^a$已知，那么强化学习任务就转化为了规划问题。

对于这种情况，能使用动态规划（Dynamic Programming）方法来求解，最常用的有策略迭代（Policy Iteration）和值迭代（Value Iteration）。

策略评估

给定策略$\pi$，**策略评估（Policy Evaluation）**要计算出该策略的价值函数，即确定$V^\pi(s)$。

根据 Bellman 等式：

$$V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(s,a) \sum_{s' \in \mathcal{S}} P_{ss'}^a \left[ R_s^a + \gamma V^\pi(s') \right]$$

蒙特卡罗强化学习

蒙特卡罗（Monte Carlo）强化学习方法通过在环境中采样来学习最优策略，而无需建立环境模型。

蒙特卡罗方法通过采样获得完整序列后再更新价值估计，即：在一个采样序列$s_1, a_1, r_1, s_2, a_2, r_2, \ldots, s_T, a_T, r_T$结束后，对其中出现的每个状态-动作对$(s,a)$，统计其后续得到的累积奖赏，并以此作为$Q(s,a)$的新估计。