《机器学习》理论——速读学习1 基础知识

该系列文章系个人读书笔记及总结性内容，任何组织和个人不得转载进行商业活动！

Time: 2021-12-05

学习目标：我需要了解神经网络除了工程化部分之外的更多内容，以便于在实际有效数据中可以获得抽象模型的能力；

目录

清华-周志华 2016年出版的，从时间上看，算是比较古老的一本书；

从目录上看，内容涵盖了模型设计和评估设计的主要算法，应该比学习视频中所能学习到的更加深入和深刻；也包含了神经网络、特征工程的内容，监督学习、半监督学习、强化学习等内容也有讲到；结合目前我所处阶段，还是十分实用的；

书中复杂理论、数学推导，试着理解，目前无法理解的直接略过

序言

人工智能 -》分支：机器学习-》手段：神经网络

其他手段：

• 符号机器学习（认知结构）
• 统计机器学习（统计技术）

Q：样本数据独立同分布假设；

大数据处理：收集 分析 和 预测；

前言

本书定位：机器学习入门教科书，便于读者理解机器学习；

大体分三部分：

• 1~3章，机器学习基础知识
• 4~10章，机器学习常用方法
• 11~16章，一些进阶知识

第1章 绪论

1.1

积累经验 =》有效预判

机器学习：研究如何通过计算手段，利用经验来改善系统性能；计算机中经验通常以数据形式存在；

机器学习的主要研究内容，是关于在计算机上从数据中产生模型的算法，即学习算法；

模型model、算法algorithm

1.2 基本术语

数据集 包含 示例样本，样本包含很多特征属性，属性的取值称为属性值，属性张成的空间称为 属性空间或样本空间；空间中的每个点对应一个坐标向量，因此我们也把一个示例称为一个特征向量；

属性数即为特征向量维数；

维数dimensionality

从训练数据/训练集中学习到了模型对应了数据的某种潜在的规律，因此模型也称为假设；这种潜在规律自身，称为真相或真实，学习过程就是为了找出或逼近真相；

假设hypothesis、真相ground-truth、预测prediction、样本标记label

模型也称为学习器learner，可看做学习算法在给定数据和参数空间上的实例化；

拥有标记信息的示例，称为样例；所有标记的集合，称为标记空间或输出空间；

标记空间label space

• 预测离散值：此类学习任务称为 分类classification
• 预测连续值：此类学习任务称为 回归regression

二分类binary classification、正类positive class、反类negative class、多分类multi-class classification

预测是希望通过对训练集的学习，建立一个从输入空间到输出空间的映射

聚类：

• 将训练样本分组，每组一个簇cluster；
• 这些自动形成的组对应一些潜在的概念划分；
• 这样的学习过程，有助于了解数据内在的规律，为更深入的分析数据建立基础；
• 聚类的训练样本通常不拥有标记信息；

监督学习supervised learning、无监督学习unsupervised learning

分类和回归属于监督学习，聚类数据无监督学习；

从训练集中学习到的模型适用于新样本的能力，称为泛化generalization 能力，强泛化能力意味着从训练集样本空间而来的模型可以很好的适用于整个样本空间；

如果样本有20个属性，每个属性10个值，样本空间规模就是10的20次方；

因此，训练集通常需要能反应出整个样本空间的特性；

分布distribution

假设样本空间中全体样本服从一个位置分布，我们的训练集样本最好都是独立地从这个分布上采样获取，即独立同分布independent and identically distributed；

一般而言训练样本越多，得到的分布样本信息越多，越有助于提高模型的泛化能力；

1.3 假设空间

归纳induction 与 演绎deduction 是科学推理的两大基本手段：

• 归纳：从具体事实归结出一般性规律（特殊到一般）；
• 演绎：从基础原理推演出具体状况（一般到特殊）；

从样本中学习是一个归纳过程，也称为归纳学习；

从训练数据中学得概念（概念学习），而不是要记住每一个样本（机械学习）；

我们可以把学习过程看作是一个在所有假设hypothesis 组成的空间中进行搜索的过程，最终找到与训练集匹配的假设；

现实问题的假设空间会很大，基于有限样本训练的假设可能有多个，即假设集合，我们称之为版本空间version space；

1.4 归纳偏好

通过学习得到的模型对应了假设空间中的一个假设；对一个具体算法产生的模型是否更好，算法本身的“偏好”就会起到关键的作用；

机器学习算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”（inductivebias），简称偏好；

任何一个有效的机器学习算法必有其归纳偏好，这样模型才能对具体的样本进行进行明确的区分（偏好对应了你要对应何种区分）；

归纳偏好可看作是学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或“价值观”；

一般的引导建立这种价值观的一个直接方式是：若有多个假设与观察一致，则选最简单的那个；（即 奥卡姆剃刀 原则，但一般如何评价哪个更简单，并不容易）

事实上，归纳偏好对应了学习算法本身所做出的关于“什么样的模型更好”的假设；而这个假设是否成立，即算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能（泛化能力是否更好）；

NFL定理：没有免费午餐定理（No Free Lunch Theorem），对于所有潜在且同等重要的问题，学习算法的期望性能都跟随机胡猜差不多，所有学习算法都一样好；

NFL定理最重要的寓意是：脱离实际问题，空泛的谈论什么学习算法更好毫无意义；

1.5 发展历程

• 推理期的人工智能
• 知识期的人工智能，知识工程瓶颈（把人总结的知识，灌输给机器很难）
• 机器自主学习

感知机Perceptron、符号主义symbolism

机器学习的一个分支就是从样例中学习；

从样例中学习，也就是广义的归纳学习，是本书内容的主要范畴，其历程：

• 符号主义学习，代表包括 决策树（decisiontree）和基于逻辑的学习；

典型的决策树学习以信息论为基础，以信息熵最小化为目标，模拟人对概念判定的树形流程；

基于逻辑的学习的代表是 归纳逻辑层序设计（Inductive Logic Programming，ILP），使用一阶逻辑（即谓词逻辑）进行知识表示，通过修改和扩充逻辑表达式，来完成对数据的归纳；

• 连接主义学习（基于神将网络）：关键词“黑箱”、“缺乏严格的理论基础”、“试错性”、“大量参数”、“调参”；
• 统计学习：代表技术是支持向量机（Support Vector Machine，SVM）以及一般的“核方法”（kernel methods）；

核方法也是目前机器学习的基本内容之一；

• 多层神经网络，深度学习：大数据量、强计算能力；

1.6 应用现状

机器学习在计算机应用领域，如计算机视觉、自然语言处理等，主键称为最重要的技术之一；

机器学习提供数据分析能力，云计算提供数据处理能力，众包（crowdsourcing）提供数据标记能力；

数据挖掘：

• 数据库 提供 数据管理
• 机器学习和统计学 提供 数据分析

1.7 阅读材料

迁移学习transfer learning、集成学习ensemble learning

国际机器学习会议（ICML）、国际神经信息处理系统会议（NIPS）、国际学习理论会议（COLT）；国际学术期刊 Journal of Machine Learning Research、Machine Learning、Neural Computation；

中国机器学习大会（CCML）、机器学习机器应用研讨会（MLA）；

第2章 模型评估与选择

2.1 经验误差与过拟合

• 错误率（error rate）：分类错误的样本/样本总数；
• 精度（accuracy） = 1 - 错误率；

学习器实际预测输出 与 样本真实输出之间的差异称为 误差（error）；

• 训练误差（training error）/经验误差（empirical error）：学习器在训练集上的误差；
• 泛化误差（generalization）：在新样本上的误差；

新样本很难确定，更多的努力是使经验误差最小化；但我们希望的目标仍然是在新样本上能表现的很好的学习器；

对于这个目标：实际从训练样本中学到的应该是适用于所有潜在样本的普遍规律，但如果学习器把训练样本学得太好，把训练样本自身的一些特点学到了（不具有普遍性），导致泛化能力下降，这种现象就是过拟合overfitting；

相对的还有欠拟合（underfitting），指的是对训练样本的一般性质都没有学好；

过拟合是机器学习面临的关键障碍，过拟合是无法彻底避免的，只能缓解；

模型选择（model selection）：

• 对候选模型的泛化误差进行评估，选择最小的那个；（泛化误差无法直接得到）

2.2 评估方法

测试机（testing set）：即用来测试学习器对新样本的判别能力；一般以测试机上的测试误差作为泛化误差的近似；

通常假设测试样本也是从样本真是分布中独立同分布采样而得；但须与训练集互斥；

从原始数据集中拆分出训练集和测试机的方法：

• 留出法（hold-out）：
  • 直接按比例划分出互斥的数据集；
  • 尽可能保证数据分布的一致性；
  • 对于分类问题，保留类别比例的采样方式通常称为“分层采样”（stratified sampling）

使用留出法时，一般要采用若干次随机划分、重复进行试验评估后取平均值作为留出法的评估结果，因为单次留出法得到的评估结果往往不够稳定；

对于训练集和测试集的比例，一般使用3:2、5:4；

• 交叉验证法（cross validation）
  • 先将数据集划分为k个大小相似的互斥子集，每个子集还要尽量保证数据分布的一致性；
  • 每次使用k-1个子集做训练，其他做测试，最终得到的k个测试结果取均值；
  • 这个方法中k值的选择很重要，一般也把此法称为k折交叉验证（k-fold cross validation），常用取值是10；
  • 由于每次划分的子集还有可能不同，因此一般要将这个划分过程重复p次，如“10次10折交叉验证”，结果再取均值；

特殊的交叉验证法——留一法（Leave one out），即k等于数据集样本的个数；

• 自助法，即自主采样法（bootstrap sampling）：
  • 之前的两种方法的训练集都只是数据集的一部分，会引入因训练样本规模不同而导致的估计偏差；
  • 自主采样是一个比较好的解决方案，对于有m个样本的数据集，随机取m次，在m次采样中始终不被采到的概率是(1-1/m)^m，约为0.368，即初始数据集中约有36.8%的样本不会被采出来，使用采出来的63.2%部分作为训练集，其余做测试集；这个测试结果也称为“包外估计”（out-if-bag estimate）；
  • 自助法在数据集较小、难以有效划分训练/测试集时很有用；但是自助法产生的训练集改变了初始数据集的分布，会引入估计偏差，在初始数据量足够时，前两种方法更常用；

调参与最终模型：

• 算法的参数，即超参数，数量较少，为每个参数人工设定多个候选值，产生模型；
• 模型的参数，可能很多，机器学习产生多个候选模型；

通常，学得模型在实际使用中遇到的数据成为测试数据，为了加以区分，模型评估和选择中用于评估测试的数据集常称为“验证集”（validation set）；即基于验证集上的表现进行模型选择和调参，基于测试机来判别泛化能力；

2.3 性能度量

性能度量（performance measure）：

• 模型泛化能力的评价标准；
• 性能度量反映了任务需求；

回归任务最常用的性能度量是均方误差（mean squared error，MSE）；

分类任务中常用的性能度量有以下几种：

• 错误率和精度
  • 他们是分类任务中最常用的两种性能度量；
  • 错误率：分类错误的样本占样本总数的比例；
  • 精度：分类正确的样本数占样本总数的比例；
• 查准率（precision）、查全率（recall）与F1
  • 查准率 也叫准确率；查全率 也叫召回率；
  • 适用场景：“检索出的信息中有多少比例是用户感兴趣的——查全率”、“用户感兴趣的信息中有多少被检索出来了——查准率”；

对于二分类问题，样例的真实类别、样例的学习器预测类别，两两组合可以分为：

• 真正例（true positive，TP），正样本——预测为正
• 假正例（false positive，FP），负样本——预测为正
• 真反例（true negative，TN），负样本——预测为负
• 假反例（false negative，FN），正样本——预测为负

COUNT(TP + FP + TN + FN) = 样例总数；

查准率P定义为：TP/(TP + FP)，即所有预测为正的样本中 标签也为正的样本 比例；

查全率R定义为：TP/(TP+FN)，即所有标签为正的样本中 预测也为正样本 的比例；

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

举个例子：
有一车瓜，其中有好瓜，也有不好的瓜；
我们希望通过模型预测结果，选出好瓜；
如果想让 查准率高，我们可以让模型预测的瓜是一车瓜中看起来更像好瓜的瓜，这样，查出好瓜的比例就多了，查准率就高了；
如果想让 查全率高，也就是选出来的好瓜尽可能的多，那就可以把一车瓜全部都送入模型，选出来的好瓜肯定也就更多了，查全率就高了，但是查出来的好瓜中真正是好瓜的比例却会降低，即查准率低了；

一般只有在一些简单任务中，两者才会都很高；

P-R曲线：查全率、查准率的关系图；

• 根据预测结果对样例排序，最可能是正例的排前面，按次序进行预测；
• 查全率为横轴，查准率为纵轴；
• 进行曲线比较时，若一个学习器的PR曲线被另一个完全包住，则可断言后者性能优于前者；
• 如果两个学习器的PR曲线有交叉，这难以一般性的断言孰优孰劣，此时也可以比较面积的大小它在一定程度上表征了学习器在查准率和查全率上取得上高的比例；
• 优于面积之一般不太容易估算，因而也使用“平衡点”（Break—Even Point，BEP）进行度量，它是“查准率=查全率”时的取值，此值越大，则学习器越优；

考虑到BEP值还是有些简化，更常用的是F1度量：

• F1 = 2*P*R/(P+R)=2*TP/(样例总数+TP-TN)
• F1是基于查准率和查全率的调和平均（harmonic mean）：1/F1 = 1/2 * (1/P + 1/R)；

一些应用场景，对查准率和查全率的关注不同：

• 商品推荐中，为少打扰用户，推荐的内容尽可能是用户感兴趣的，查准率就更重要；
• 逃犯信息检索中，希望少漏掉逃犯，此时查全率更重要；

为了表达这种偏好，F1也使用形式Fß=(1+ß^2)*P*R/(ß^2*P + R)，方便表达对查准率和查全率的不同偏好：

• Fß是加权调和平均，1/Fß = 1/(1+ß^2) * (1/P + ß^2/R)
• 与算数平均(P+R)/2、几何平均(P*R)^0.5相比，调和平均更重视较小值；
• ß大于0 小于1：查准率影响更大；
• ß等于1：即标准的F1；
• ß大于1：查全率影响更大；

估计算法的全局性能：

• 宏查准率macro-P、宏查准率macro-R、宏F1（macro-F1）：多组查重率、查准率的均值；
• 多组TP FP TN FN计算均值，在基于这些均值计算出 微查准率micro-P、微查准率micro-R、微F1（micro-F1）；

这个调和平均很有意思，在榜单歌曲中试了下排名，还不错，而且还支持加权；

ROC与AUC：

• 学习器预测样本的结果，一般使用阈值（threshold）进行比较分类：正类或反类；
• 根据预测结果进行排序，阈值对应了一个截断点；
• 更重视查准率，则截断位置靠前选；更重视查全率，截断位置靠后选；

ROC受试者工作特征（Receiver Operating Characteristic）曲线：

• 更具学习器预测结果对样例进行排序，按次序把样本作为正例预测，每次计算TPR（真正例率True Positive Rate）作为纵轴、FPR（假正例率False Positive Rate）作为横轴，即ROC曲线；
• TPR = TP/(TP + FN)
• FPR = FP/(TN + FP)
• 横纵轴的取值范围都是0~1，从0，0到1，1的对角线，即TPR=FPR，对应了随机猜测；点0，1则对应了将所有正例排在所有反例之前的“理想模型”；

ROC曲线的绘制过程：给定m+个正例和m-个反例，初始阈值设为最大，让所有预测均为反例，此时TPR和FPR均为0；然后依次将分类阈值设为每个样例的预测值，即依次将每个样例划分为正例；设前一点x,y，若当前点为真正例，这标记点坐标为x,y+1/m+，若当前点为假正例，则标记点为x+1/m-,y；

与PR曲线类似，面积越大的性能越优，ROC曲线的面积，即为AUC（Area UnderROC Curve）；

形式化的看，AUC考虑的是样本预测的排序质量，因此与排序误差有紧密联系；

代价敏感（cost-sensitive）错误率与代价曲线(cost curve)：

• 非均等代价（unequal cost）：衡量不同类型错误所造成的不同损失；

2.4 比较验证

机器学习中的性能比较复杂，统计假设检验（hypothesis test）为我们进行学习器性能比较提供了重要依据；基于其结果，若在测试集上表现的更好，往往说明泛化能力也更好，以及这个结论有多大把握；

默认以错误率为性能度量；

2.5 偏差与方差

回归任务中，偏差-方差分解（bias-variance decomposition）是解释学习算法泛化性能的一种重要工具；

泛化误差可以分解为 偏差、方差、噪声之和；

• 偏差 对量了 学习算法的期望预测与真实结果间的偏离程度，即学习算法本身的拟合能力；
• 方差 度量了 同样大小的训练集变动所导致的学习性能的变化，即数据扰动造成的影响；
• 噪声 表达了当前任务上任何学习算法所能达到的期望泛化误差的下界，即学习问题本身的难度；

偏差-方差分解 说明：泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度共同决定的；

对于给定的任务，为了良好的泛化能力，使偏差较小，即能够充分拟合数据，并使方差较小，即数据扰动产生的影像小；

偏差-方差窘境：一个给定的学习任务，在训练不足时，学习器拟合能力不够，数据扰动不足以让学习器产生明显变化，此时偏差主导泛化错误率；当训练程度加深时，学习器拟合能力增强，熟练数据的扰动逐渐被学到，此时方差逐渐主导泛化错误率；当训练程度十分充足时，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合；

应该在欠拟合 到 过拟合的中间位置，选取训练好的模型；

2.6

机器学习过程设计许多类型代价：误差分类代价、测试代价、标记代价、属性代价等；

代价敏感学习 专门研究非均等代价下的学习；

第3章 线性模型

3.1 基本形式

线性函数：

• 基本形式：f(x) = w1*x1 + w2*x2 + ... + b
• 向量形式：f(x) = wT*x + b

x为n个属性描述的取值，w和b确定后，该线性模型就得以确定；

线性模型蕴含了机器学习中重要的基本思想；许多功能更为强大的非线性模型（nonlinear model）可在线性模型的基础上通过引入层级结构或高维映射而得；

由于权重w的值更加直观，线性模型通常具有很好的可解释性（comprehensibility）；

接下来介绍 回归任务、二分类和多分类任务中几种经典的线性模型；

3.2 线性回归

线性回归（linear regression）：

• f(x) = w*x + b
• 试图学得一个线性模型，以尽可能准确的预测实值输出；
• 对于离散属性
  • 如果属性值存在序关系，可转化为连续值，如高、矮对应1、0；
  • 如果不存在序关系，可转化为多维向量；如瓜类取值西瓜、南瓜对应（1，0）（0，1）；
• 要学得线性模型，需要确定w和b，关键在于衡量f(x)和y之间的差别；
• 均方差 是回归任务中最常用的性能度量，视图让均方误差最小化；

均方差的几何意义对应了欧氏距离（Euclidean distance）；基于均方误差最小化来进行模型求解的方法称为“最小二乘法”（least square method）；

在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小；因而，求解w和b的过程，称为 线性回归模型的最小二乘“参数估计”（parameter estimation）；

对于f(x) = wT*x + b形式，称为“多元线性回归”（multivariate linear regression）；

ln(y) = wT*x + b形式，即示例所对应的输出标记是在指数尺度上变化，那就可将输出标记的对数作为线性模型逼近的目标，这就是“对数线性回归”（log-linear regression）；虽然形式上仍是线性回归，但实质上已经是在求取输入空间到输出空间的非线性函数映射；

广义线性模型，指的是对wT*x + b应用一个单调可微的函数，得到的f(x)到y的对应关系，对数线性回归中这个函数是ln()；

3.3 对数几率回归

前文使用线性模型进行回归学习，但对分类任务，则需要使用 广义线性模型，即找到一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值z联系起来；

如二分类的标记为1或0，则需将z = wT*x + b得到的实值z转换为0/1值，这里理想的是“单位阶跃函数”（unit-step function）；

y = 0, z < 0
  = 0.5, z = 0
  = 1, z > 0

但由于 单位阶跃函数 不连续，因此不能直接用作关联函数，我们希望找到一个类似单位阶跃函数的“替代函数”，并且单调可微；对数几率函数（logistic function）正是这样一个常用的替代函数；

y = 1/ (1 + e^-z)

对数几率函数 是一种Sigmoid函数，可将z值转化为一个接近0或1的y值，并且输出值在z=0附近很陡峭；

对数几率回归（logistic regression）：

• 在用线性回归模型的预测结果去逼近真实标记的对数几率；
• 注意，虽然名字上有回归，但它实际上是一种分类学习方法；

经典的数值优化算法如梯度下降法（gradient descent method）都可用于求解高阶可导连续凸函数；

3.4 线性判别分析

线性判别分析（Linear Discriminant，LDA），是一种经典的线性学习方法；

LDA的思想：给定训练样例集，设法将样例投影到一条直线上，同类的样例投影点尽可能接近、异类样例的投影点尽可能远离；

二分类任务中两类数据满足高斯分布且方差相同时，线性判别分析产生贝叶斯最优分类器；

LDA将样本投影到n维空间，n远远小于数据原有的属性维数，即可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息，因此LDA也常被视为一种经典的监督降维技术；

3.5 多分类学习

分类学习器通常称为分类器（classifier）；

对分类学习的基本思路是拆解法：

• 将多分类任务拆为若干个二分类任务求解；
• 拆分方法有一对一、一对多、多对多等；

3.6 类别不平衡问题

前文的分类学习方法都有一个基本假设，即不同类别的训练样例数相当；一般的不同类别训练样例数目差别不大时，影响也不大，但若差别很大，就会对学习过程造成困扰

类别不平衡（class-imbalance）：指分类任务中不同类别的训练样例数目差别很大的情况；

类别不平衡学习的基本策略——再缩放（rescaling）：

• （正例可能性y/反例可能性（1-y））*（反训练样例数/正训练样例数）
• 再缩放思想虽然简单，但操作并不平凡，主要是因为“训练集是真实样本总体的无偏采样”这个假设往往不成立；对此现在技术大概有三类做法：
  • 1.直接对训练集里的反类进行“欠采样”（undersampling），即去除一些反例，使得正、反例数量接近；
  • 2.对训练集里的正类样例进行“过采样”（oversampling），即增加一些正例使得正、反例数量接近；
  • 3.直接基于原始训练集进行学习，但在用分类器事，将其嵌入决策过程，称为“阈值移动”（threshold-moving）；

过采样不能简单对正样例进行重复采样，否则将会导致严重的过拟合；一般使用SMOTE算法对训练集中的正例进行插值来产生额外的正例；

欠采样一般使用EasyEnsemble算法，将反例划分若干集合供不同学习器使用，这样对每个学习器来看都进行了欠采样，但是在全局看不丢失重要信息；

注意：本书的出版时间时2016年，成书时间则更早；

3.7

稀疏表示（sparse representation）

• 稀疏性问题本质对应了L0范数的优化，这在通常条件下是NP难问题；LASSO通过L1范数来近似L0范数，是求取稀疏解的重要技术；

多分类学习中每个样本仅属于一个类别，但如果希望一个样本同时预测出多个类别标记，就不再是多分类学习，而是“多标记学习”（multi-label learning）；