5.1 学习算法

算法分类（粗分类）：

• Classification：将输入x映射到类别y的一类中（通常也输出类别的概率分布）
• Classification with missing inputs：在分类任务中，输入x存在feature缺失的情况（在传统算法中，我们要设计多个函数集来匹配不同缺失情况的x，但在机器学习中，我们可以学习所有变量的分布，通过边缘化缺失变量来解决）
• Regression：给定输入x，输出一个确定的数值y
• Transcription：观察非结构化表示的数据，将信息转录成离散的文本形式（例如OCR）
• Machine Translation：输入某种语言的一串连续符号序列，将它转换成另一种语言的符号序列
• Structured Output：输出的数据结构各个元素之间有很强的联系
• Anomaly Detection：观察一系列的对象，找到异常数据
• Synthesis and Sampling：生成一个与训练数据类似的新样本
• Imputation of Missing Value：缺失值估计
• Denoising：去噪
• Density Estimation：密度估计

监督学习/非监督学习/半监督学习：

• Supervised Learning：给定数据X、以及每个样本对应的标签Y

• Unsupervised Learning：只给定数据X，在无监督的情况下，学习数据的结构以及有用的特征信息、以及整体的概率分布

• Blur：监督学习通常预测P(y|x)，非监督学习通常预测P(x)，但它们两者的界限其实非常模糊。例如非监督学习P(x)可以转为了n个监督学习的例子，如下图：
  
  监督学习也可以使用无监督方法直接学习到整体的概率分布P(x,y)，然后根据下式进行推断：
  通常，将分类、回归或者结构化输出作为监督学习，而密度估计作为非监督学习。

• Semi-supervised Learning：样本有些包含标签，有些没包含标签。（具体分类：不完全监督：只有一部分训练数据具备标签；不确切监督：训练数据只具备粗粒度标签；不准确监督：给出的标签并不总是真值）

强化学习：

• 是与环境交互的，而不是拟合数据
• 根据行为给予奖励/惩罚（模拟决策的过程）
• 输出无监督、奖励延迟

5.2 容量、过拟合和欠拟合

泛化能力：在未知数据上的拟合能力称为泛化，通常我们期望获得更好的泛化能力。机器学习不同于优化问题，我们更关心如何得到更低的泛化误差(test error)。

统计学习理论： 既然期望得到更好的泛化效果，那么我们怎么通过trainset的训练来判断性能的好坏呢？

• 需要设置一些假设：1.训练集和测试集来自同一生成过程；2.数据集各样本独立同分布；3.将共享的潜在分布称为数据生成分布，记作P_data
• 这个概率框架和独立同分布假设能够允许我们在数学上研究训练误差和测试误差之间的关系

训练误差和测试误差： 在上面的假设下，对于一个固定参数w的模型，对于训练集和测试集，他们的误差应该是一致的，因为它们属于独立同分布，并且数据生成过程也一致。但是！问题在于我们并不会提前确定参数w，w是在训练集上学习到的。

决定机器学习算法好坏的因素： 1.训练误差足够小；2.训练误差与测试误差的差距足够小。这也就导致了存在两个挑战：

• 欠拟合：训练误差过大

• 过拟合：训练误差小，但测试误差大

  我们可以通过控制模型的容量来消除欠拟合和过拟合现象

容量： 容量就是模型拟合不同函数的能力，例如线性拟合，多项式项数越高，模型的拟合能力也就越强。

• 训练误差和测试误差之间差异的上界随着模型容量的增长而增加，但随着样本的增多而下降（数据越多，模型效果越好）。

• 在机器学习中，受优化算法的限制，通常我们很难去衡量一个模型的容量。

• 奥卡姆剃刀：有很多可以解释现有现象的假设中，选择最简单的那个（泛化效果最好）。

• VC维：衡量二元分类器的容量，如下图所示，线性分类器的VC为3。
  

• 容量和误差的典型关系：
  

无参数模型： 模型可以达到任意容量，因为它们的容量与参数无关，例如最近邻回归（只与样本数量有关）。

• 最近邻回归：存储了训练集中所有的X和y，当需要对测试点x分类时，查询训练集中离该点最近的样本，并返回相关的回归目标。

贝叶斯误差： 理想模型是我们能够预先知道生成数据的真实分布，但由于数据分布中含有重叠/噪声等，这样会引入很多误差。从预先知道真实分布p(x,y)预测而出现的误差被称为贝叶斯误差（无法避免的误差，理论上最低的误差）。

增加数据量带来的影响： 1.泛化误差不会因为训练样本的增加而增加；2.对于非参数模型，数据量越大泛化能力越强；3.对于固定参数的模型，小于最佳容量的模型会随着数据量的增加，会渐近到大于贝叶斯误差的误差值。

近似正确定理： 机器学习算法能够在有限个训练样本中很好地泛化，它只保证找到在所关注大多数样本上近似正确的规则。

没有免费的午餐定理： 在所有可能的数据生成分布平均之后，每一个分类算法在未事先观察的点上具有相同的错误率（没有一种能够适应所有数据分布的算法），所以在机器学习中，我们不去寻找那种通用的学习算法。

正则化： 没有免费午餐定理已经表明了所设计的学习算法只应适用于某种特定任务中，我们可以通过对学习算法设置**“偏好”**来达到这个要求，当偏好与学习问题相吻合时所表现性能最好。目前，我们采用的方法都是增加或减少学习算法可选假设空间的函数来增加或减少模型的表示容量。算法的效果不仅很大程度上取决于假设空间的函数数量，也取决于这些函数的具体形式。

• 权重衰减：例如在线性回归时，加入权重衰减会使得函数偏向于平方L²范数较小的权重（这会学习到的权重weight波动更小，曲线更平滑，输出对输入就越不敏感）。
  
• 正则化主要是用来减小泛化误差，而非训练误差。不同任务所选取的正则化方法也应该不用。

5.3 超参数和验证集

超参数存在的原因： 1. 难以通过学习算法优化；2.不适合放在学习算法中进行优化。

验证集：验证集是从训练集中直接分割出来的一个独立子集。通常我们会将训练数据集分割为训练集和验证集（通常为4:1），一个用来学习模型的参数，另一个在训练中或训练后用于评估模型的泛化误差，从而更新超参数(验证集是必须的，训练集用来证明模型的拟合能力，验证集用来证明模型的泛化能力，测试集用于测试模型的泛化能力。要根据验证集的结果来调整model的泛化能力，而不是测试集)。

交叉验证： 当数据集比较小时，分割为固定的训练集和测试集是有问题的，小规模的测试集意味着平均测试误差估计的统计不确定性，这将很难去判断算法A与算法B在这个任务上的优劣性（数据集超过十万计或者更多时无需考虑这个问题）。但数据集过小时，也有替代方法允许我们使用所有的样本估计平均测试误差，代价是计算量的增加。

• K-折交叉验证：将数据集分成k个不重合的子集。测试误差可以估计为k次计算后的平均测试误差，第i次测试时，
  数据的第i个子集用于测试集，其他用于训练集（不存在平均误差方差的无偏估计，通常通过近似来解决）。

5.4 估计、偏差和方差

点估计： 点估计试图为一些感兴趣的量提供一个最优预测。感兴趣的量可以为：1.单个参数；2.一个参数向量(例如线性回归的权重)；3.整个函数。

• 点估计也可以指输入和输出变量之间关系的估计，这种类型的估计称为函数估计。例如多项式线性回归，可以被解释为估计参数w，也可以解释为估计x到y的函数映射f。
• 点估计最常研究的性质：偏差、方差。

偏差： 定义如下，采样得到的数据的期望与真实值之间的偏差。

• 如果bias为0，为无偏估计

• 如果m->∞时，bias为0，为渐进无偏

• 伯努利分布：bias为0，无偏估计
  

• 均值的高斯分布估计：bias为0，无偏估计
  

• 方差的高斯分布估计：

  • 有偏估计：
    
  • 无偏估计：
    
  • 可以看到一个是有偏的，一个是无偏的，尽管无偏估计显然令人满意的，但它不总是“最好”的估计，我们经常会使用其他具有重要性质的有偏估计。

方差和标准差： 估计的另一个重要性质，能够告诉我们，当独立地从潜在的数据生成过程中重采样数据集时，期望估计如何变化。

• 方差的平方就是标准差。

• 均值的标准差被记作：

• 样本方差的平方根和方差无偏估计的平方根都不是标准差的无偏估计，尽管是有偏估计，但近似是合理的，广泛应用于实际

• 均值的标准差在机器学习实验中非常有用，通常使用测试集样本的误差均值来估计泛化误差。根据中心极限定理，均值会接近于一个高斯分布，我们可以用标准差计算出真实期望落在选定区间的概率。例如，以均值为中心的95%置信区间是
  
  在机器学习中，我们说算法A比算法B好，是指算法A的误差的95%置信区间的上界小于算法B的误差的95%置信区间的下界。

衡量偏差和方差以最小化均方误差： 偏差和方差度量着估计量的两个不同误差来源，偏差度量着偏离真实函数或参数的误差期望，而方差度量着数据上任意特定采样可能导致的估计期望的偏差。

• 期望得到的偏差以及方差都足够小；

• 如果出现权衡的话，使用交叉验证进行抉择，或者使用最小化均方误差（同时包含了偏差和方差），如下式：
  

• 偏差/方差的关系和机器学习容量、过拟合、欠拟合：增加容量会增加方差（可能过拟合，通过测试集误差可以看出来），降低偏差（增加拟合能力，通过训练集误差可以看出来），简单的模型bias大，variance小，underfitting；复杂模型bias小，variance大，overfitting。
  
  一致性： 当数据集中数据点的数量m增加时，点估计会收敛到对应参数的真实值。一致性保证了估计量的偏差会随数据样本数目的增多而减少。
  

5.5 最大似然估计

很多时候，我们希望有些准则可以让我们从不同模型中得到特定函数（学习得到），从而作为好的估计，而不是自己去猜测函数，最常用的就是最大似然估计(假设真实数据分布的参数是固定的，根据经验样本分布情况，估计最大可能发生的真实分布情况参数)。

多个概率的乘积由于很多原因会导致计算不便，所以转换为似然对数：
又因为我们对代价函数进行缩放不会影响到argmax，可以除以m得到和训练数据经验分布相关的期望作为准则：
一种解释最大似然估计的观点是将它看作最小化训练集上的经验分布和模型分布之间的差异，两者之间的差异程度可以通过KL散度度量：
最小化KL散度其实就是在最小化分布之间的交叉熵。

可以将最大似然看作是使模型分布尽可能地和经验分布相匹配的尝试。理想情况下，我们希望匹配真实的数据生成分布。

条件对数似然： 最大似然估计很容易扩展到估计条件概率P(y|x; Θ)，从而给定x预测y。这是实际中最常见的一种情况，构成了监督学习基础。

最大似然估计的性质： 最大似然估计作为机器学习中的首选估计(一致性、统计效率)，最吸引人的地方在于，它被证明：当样本数目m->∞时，就收敛率而言是最好的渐进估计。在合适的条件下，最大似然估计满足一致性：

• 真实分布必须在模型族中（模型的拟合能力足够强），否则没有估计可以还原真实分布。
• 真实分布必须刚好对应一个Θ值，否则，最大似然估计恢复出真实分布后，也不能决定数据生成过程中使用哪个Θ。

5.6 贝叶斯统计

频率派统计： 基于单一值Θ的估计，然后基于该估计作所有的映射。（认为Θ是固定的一个值，方法都是探索"哪个值最可能是真实值"，最大似然估计、置信区间）

• 真实参数Θ是未知的定值，而点估计是考虑数据集上函数（可以看出是随机的）的随机变量。

贝叶斯统计： 在做预测时会考虑所有的Θ。（认为Θ本身就是不确定的，设法找到参数空间中每个值的概率（使用概率来反应知识的确定性程度），并且其都应对模型有影响。）

• 数据是直接可以被观测到的，所以不是随机的；其次参数是未知/不确定的，是随机变量。
• 将Θ的已知知识表示成先验概率分布，一般而言，机器学习实践者会选择一个相当宽泛的（即，高熵的）先验分布，反映在观测到任何数据前参数的高度不确定性。

贝叶斯估计： 在贝叶斯估计常用的情景下，先验开始是相对均匀的分布或高熵的高斯分布，观测数据通常会使后验的熵下降，并集中在参数的几个可能性很高的值。相比于最大似然估计，有以下两点重要区别：

• 第一个是：最大似然方法预测时使用Θ的点估计，贝叶斯方法使用Θ的全分布，例如，在观测到m个样本后，下一个数据样本x(m+1) 的预测分布如下：
  
  如果我们仍然非常不确定Θ的值，那么这个不确定性会直接包含在我们所做的任何预测中。频率派方法解决给定点估计Θ的不确定的方法是评估方差，估计的方差评估了观测数据重新从观测数据中采样后，估计可能如何变化。贝叶斯派的答案是积分，这往往会防止过拟合。

• 第二个最大区别是由贝叶斯先验分布造成的，先验能够影响概率质量密度朝参数空间中偏好先验的区域偏移。实践中，先验通常表现为偏好更简单或更光滑的模型。

• 当训练数据很有限时，贝叶斯方法通常泛化得更好，但是当训练样本数目很大时，通常会有很大的计算代价。

最大后验估计： 希望使用点估计的一个常见原因是，对于大多数有意义的模型而言，大多数涉及到贝叶斯后验的计算是非常棘手的，点估计提供了一个可行的近似解，但我们仍然可以让先验影响点估计的选择来利用贝叶斯方法的优点，而不是简单地回到最大似然估计：MAP。MAP估计选择后验概率最大的点（或在Θ是连续值的更常见情况下，概率密度最大的点）。

其中，log p(x|θ) 是标准对数似然项，log p(θ) 对应着先验分布。如果先验是N(w;0, (1/λ)I²) ，那么上式的对数先验项正比于熟悉的权重衰减乘法λw^Tw，加上一个不依赖于w也不会影响学习过程的项。高斯先验权重的MAP贝叶斯推断对应着权重衰减。（MAP贝叶斯推断提供了一个直观的方法来设计复杂但可解释的正则化项）

• MAP的优势在于能够利用无法从训练数据获得的先验信息，相比于最大似然估计，减少了方差（但增加了偏差）。

5.7 监督学习算法

我个人觉得花书监督学习/非监督学习这两节讲得并不好，但是毕竟它是注重于深度学习，所以也无可厚非，对应的内容可以看李航或者周志华的书。

支持向量机： 类似于线性回归，使用基于线性函数w^Tx+b，但不输出概率，只输出类别。w^Tx+b>0为+，w^Tx+b<0为-。

• 核技巧是SVM的重要创新，它观察到许多机器学习都可以写成样本间点积的形式，例如支持向量机中的线性函数可以重写为：

• 重写为这种形式之后允许我们将x替换为特征函数ϕ(x)的输出，点积替换为被称为核函数的函数k(x,x⁽ⁱ⁾) = ϕ(x)· ϕ(x⁽ⁱ⁾)。

• 使用核估计替代点积后，我们可以使用以下函数进行预测：

• 这个函数关于x 是非线性的，关于ϕ(x) 是线性的，α和f(x)之间的关系也是线性的。核函数完全等价于：用ϕ(x)预处理所有的输入，然后在新的转换空间学习线性模型。

• SVM为什么要使用核函数?

  1. 它使我们能够使用保证有效收敛的凸优化技术来学习非线性模型（关于x 的函数）
  2. 核函数的实现方法通常比直接构建ϕ(x)再算点积高效很多

• 高斯核函数

  它是最常用的核函数，也称为径向基函数核，其对应于无限维空间中的点积。

• 缺点：1.训练样本增加时，训练时间增加；2.通用核函数很难泛化。

K近邻算法： 可以用于分类和回归，非参数学习算法，关于训练数据的一个简单函数。

• 回归：在测试阶段我们希望在新的测试输入x上产生y，我们需要在训练数据X上找到x的k-最近邻。然后我们返回训练集上对应的y值的平均值。
• 分类：找测试样本x的k-最近邻，然后关于one-hot编码向量c求平均，均值为类别的概率分布。
• 优点：数据量越大，容量越高
• 缺点：它不能学习出哪一个特征比其他更具识别力

决策树： 将输入空间分成不同的区域，每个区域有独立参数的算法

5.8 无监督学习算法

通常与密度估计相关，学习从分布中采样、学习从分布中去噪、寻找数据分布的流形或是将数据中相关的样本聚类

• 一个经典的无监督学习任务是找到数据的‘‘最佳’’ 表示：在比本身表示的信息更简单或更易访问而受到一些惩罚或限制的情况下，尽可能地保存关于x 更多的信息。
• 最常见的三种表示：低维表示、稀疏表示和独立表示。1. 低维表示尝试将x 中的信息尽可能压缩在一个较小的表示中。 2. 稀疏表示将数据集嵌入到输入项大多数为零的表示中。 3.独立表示试图分开数据分布中变化的来源，使得表示的维度是统计独立的。

主成分分析：PCA学习一种比原始输入维数更低的表示，它也学习了一种元素之间彼此没有线性相关的表示。

• 主要步骤：
  
• PCA学习一种线性投影，使得最大方差的方向和新空间的轴对齐。
• 虽然相关性是数据元素间依赖关系的一个重要范畴，但我们对于能够消除更复杂形式的特征依赖的表示学习也很感兴趣。

K-均值聚类： 将训练集分成k个靠近彼此的不同样本聚类。

• 算法图示：
• 优缺点：
• 花书上提到一个观点很有意思，就是关于聚类问题本身是有问题的（没有单一的标准去衡量聚类的数据在真实世界中效果如何）。我们可能希望找到和一个特征相关的聚类，但是得到了一个和任务无关的，同样是合理的不同聚类。

5.8 随机梯度下降

几乎所有的深度学习都用到了一个非常重要的算法：随机梯度下降，是梯度下降法的一个扩展。（花书里提到的随机梯度下降SGD应该是小批量梯度下降）

梯度下降：

梯度下降法的计算瓶颈：数据越多，泛化能力越强，但训练时参数upgrade时间越长。

• Cost Function是所有样本loss的总和，对应地，梯度下降也需要计算所有样本的梯度，这样随着数据的增加，耗时也呈线性增加。

随机梯度下降的核心是：梯度是期望，既然是期望，那就可以使用小规模的样本来近似估计。

• 每一步SGD更新时，我们只从训练集中均匀抽出一小批量（minibatch）样本，并且这个批量是固定的
  

• 然后使用下式进行梯度下降：
  

• 优点：梯度下降很慢，并且直接应用于非凸优化问题的优化可能是鲁莽的，SGD解决了训练时间的问题，虽然不能保证找到局部最优解，但其能在有限的时间内快速地找一个代价函数很小的模型。

• 当训练样本m趋向于无穷大时，该模型最终会在随机梯度下降抽样完训练集上的所有样本之前收敛到可能的最优测试误差，继续增加m不会延长达到模型可能的最优测试误差的时间。从这点来看，我们可以认为用SGD训练模型的渐近代价是关于m的函数的O(1) 级别。

5.10 构建机器学习算法

配方：特定数据集、代价函数、优化过程、模型

5.11 促使深度学习发展的挑战

维数灾难： 当数据的维数很高时，很多机器学习问题会变得困难。

• 随着维度的增加，分类的性能逐步上升，到达某点之后，其性能反而下降(泛化误差)。对于一个分类问题，维数增加后，更容易在高维空间找到线性分类平面，但其实将高维空间向低维进行投影，其实决策函数会是一个复杂的非线性分类器，这样会存在过拟合的现象。

• 另一个角度来说，高维会带来数据稀疏性的问题：在高维空间中参数配置数目远大于样本数目，但大部分单元格中没有样本，这样会影响到学习算法的泛化能力（大多数传统机器学习算法只是简单地假设在一个新点的输出，应和最接近的训练点的输出大致相同）

  参考链接：https://blog.****.net/qq_39521554/article/details/80653712

局部不变性和平滑正则化：

先验信念帮助机器学习算法能够更好地泛化，它引导函数往那个方面学习。最广泛使用的叫局部不变形(也叫平滑正则化)，这个先验表明学习的函数不应在小区域内发生很大的变化。换言之，如果我们知道对应输入x的答案，那么该答案对于x的邻域应该也适用。

• 假设，我们现在需要学习一个表示区间数大于样本数的复杂函数，并且希望它具有一定的泛化性。仅靠局部不变性的假设，我们是很难达到这一点的，问题关键在于我们通过额外假设生成数据的分布来建立区域间的依赖关系，那么O(k)个样本足以描述多如O(2k) 的大量区间。
• 一些其他的机器学习方法往往会提出更强的，针对特定问题的假设(例如周期性等特征，但很难由这些简单的特征去解决复杂的任务)。而深度学习的核心思想是假设数据由因素或特征组合产生，这些因素或特征可能来自一个层次结构的多个层级。

流形学习：
流形是指连接在一起的区域，机器学习倾向于更松散地定义一组点，只需要考虑少数嵌入在高维空间中的自由度或维数就能很好地近似。

如果我们希望机器学习算法学习整个Rⁿ上有趣变化的函数，那么很多机器学习问题看上去都是无望的。流形学习（manifold learning）算法通过一个假设来克服这个障碍，该假设认为Rⁿ中大部分区域都是无效的输入，有意义的输入只分布在包含少量数据点的子集构成的一组流形中，而学习函数的输出中，有意义的变化都沿着流形的方向或仅发生在我们切换到另一流形时。

数据位于低维流行的假设不总是对的，但是在一些人工智能场景中(语音、图像、文本)，它是近似对的。

• 流形假设的观察是现实生活中的图像、文本、声音的概率分布都是高度集中的。

• 我们至少能够非正式地想象这些邻域和变换。

优点：

1. 高维空间有冗余，低维空间没冗余。也就是说，流形可以作为一种数据降维的方式(非线性降维)。
2. 流形能够刻画数据的本质（将数据从高维空间降维到低维空间，还能不损失信息）。

• 比如我们现在要刻画地球上任意两个城市之间的距离，其实地球是在一个三维空间中的，但是直接用三维空间来解决这个问题是很冗余的(大部分区域都是无效的输入，因为城市只可能出现在地球的表面上)。这样，我们更愿意使用经纬度、或者将地球表面拉平，展开。在三维空间中，使用欧式距离来衡量是不准确的，比如有两个城市，他们关于地心对称，但是我们不可能用三维空间中的欧式距离去衡量。所以，当数据位于低维流形中时，使用流形中的坐标而非Rⁿ中的坐标表示机器学习数据更为自然。

• 自编码器（流形学习）
  

流行学习考虑：

1. 如何找到这个从高维到低维的映射。
2. 哪怕不能直接找到这个映射，那我们可以找到某种方法，在高维空间处理数据，等效于“将高维空间映射到低维空间、再处理数据、再映射回高维空间” 的这种操作。