机器学习【西瓜书/南瓜书】--- 第1章绪论+第二章模型选择和评估（学习笔记+公式推导）

【西瓜书+南瓜书】task01: 第1、2章2天

第一章 绪论

主要符号表

下述这些符号在本书中将频繁的使用务必牢记于心各个特殊符号所具有的的含义

🌟对上述部分定义做一下解释

向量有维度其中的元素是有序的
变量集是集合集合中的元素是无序的

空间可以简单的理解为集合假设空间是一个超集全集
全集的一部分被称为假设集可以认为假设集是假设空间的一个子集

逗号分割行向量
分号分割列向量

**

1.1 引言

**
你会判断一个西瓜是否是一颗好瓜么
如果你不知道那么我告诉你一个好瓜的判断条件色泽青绿、根蒂蜷缩、敲声浊响 的瓜就是一颗好瓜这不是我信口开河这是我们在生活中所总结出的经验再比如我们通过往常的学习经验可以知道如果你刻苦学习弄清概念做好作业就可以取得好成绩

不难看出我们能做出有效的判断是因为我们积累的经验。

机器学习就是如此一门学科它致力于通过计算的手段利用经验来改善 系统自身的性能。
计算机有经验么有的对于计算机而言经验就是 数据

根据上述两点可以知道机器学习就是通过 数据产生 模型(model) 的算法所谓 模型 泛指从数据中心学得的结果产生 模型 的算法即 学习算法。有了 学习算法我们只需要给它数据经验它可以基于这些数据产生模型在以后面对一个新的西瓜可以判断出它是好瓜还是坏瓜。

1.2 基本术语

💥枯燥且重要的知识来了

我们给出几组关于西瓜的记录

色泽 = 青绿根蒂 = 蜷缩敲声 = 浊响
色泽 = 乌黑根蒂 = 稍蜷敲声 = 沉闷
色泽 = 浅白根蒂 = 硬挺敲声 = 清脆
数据集data set上述记录的集合称为数据集数据集亦被称为一个“样本”
示例instance每条记录称为一个示例
属性attribute/ 特征feature如 色泽根蒂敲声
属性值attribute value如 青绿 蜷缩 浊响
属性空间attribute space/ 样本空间sample space/ 输入空间input space属性所张成的空间
特征向量feature vector我们把上述属性色泽根蒂敲声作为坐标轴就可以构建出一个三维空间每个西瓜在这个空间中都可以找到自己的坐标位置由于该空间中的每个点都对应一个坐标向量故我们也把一个示例称为特征向量
一般地令 D = {x1x2…xm}【行向量】 表示含有 m 个示例的数据集比如上述例子中就是含有3个示例的数据集其中每个示例都是由 d 个属性所描述比如上述例子中每个西瓜都有3个属性色泽根蒂敲声故对于每个示例我们可以表达为xi = {xi1xi2…xid}【列向量】其中 d 称为样本 xi 的 维数dimensionality

学习learning/ 训练training从数据中获得模型
训练数据training data训练过程中使用的数据
训练样本training sample每个样本都被称为训练样本
训练集training set训练样本组成的集合
假设hypothesis学得模型对应了关于数据的某种潜在规律故亦被称为假设
真相 / 真实ground-truth指这种潜在的规律的自身
学习器leaner就是模型可看作学习算法在给定数据和参数空间上的实例化
假设就是模型映射就是模型
假设要逼近真相
我们使用我们的数据集去构造一个假设并且我们希望这个假设是逼近真相的
假设并不唯一比如我从北京到上海我可以开车高铁飞机步行我们的目的是在一系列假设之中按照相关的要求去选择一个“好”的假设

🌟还记得我们的 “初心” 么判断一个瓜是否为好瓜显然我们光有示例数据是远远不够的我们还需要训练样本的结果信息来建立关于 预测prediction 的模型例如色泽 = 青绿根蒂 = 蜷缩敲声 = 浊响好瓜在这里关于示例结果的信息好瓜被称为 标记label 拥有了标记信息的示例则被称为 样例example

示例 + 标记 = 样例

一般地用(xiyi表示第 i 个样例其中 yi ∈ 𝓨 是示例 xi 的标记𝓨 是所有标记的集合亦被称为 标记空间label space/ 输出空间output space

(xi, yi)向量标量

分类classification预测离散值如好瓜坏瓜的学习任务
回归regression预测连续值如西瓜的成熟度 0.95、0.37 的学习任务
yi是离散分类
yi是连续回归

对于只涉及两个类别的 二分类binary classification 任务称其中的一个类为 正类positive class另一个类为 反类negative class亦被称为 反类

所谓二分类就是判断是和不是是否为好瓜是否为三好学生
在定义“正类”和“反类”负类时我们既可以把好瓜定义为“正类”也可以把好瓜定义为“反类”负类这里的正反仅仅是用来起到区分的作用并不涉及好坏之差

涉及多个类别时被称为 多分类multi-class classification

预测任务是希望通过对训练集{(x1y1)(x2y2)…(xmym)} 进行学习建立一个从输入空间 𝓧 到输出空间 𝓨 的映射 f 𝓧 → 𝓨 对于二分类的任务我们通常令𝓨 = {-1 +1} 或 {0 1}对于多分类任务 |𝓨 | > 2对于回归任务𝓨 = RR为实数集

测试clustering学得模型之后使用其进行预测的过程
测试样本testing sample被预测的样本
例如在学得 f 后对测试例 x可得到测试标记 y = f(x)

❗️ 注意并不是所有的数据都有标签yi 的对于没有 yi 的数据我们就不能对其进行探索了么非也我们可以对数据做“聚类”

聚类clustering将训练集中的西瓜分组
簇cluster分成的组每组被称为一个簇
这些自动形成的簇可能对应一些潜在的概念划分例如“浅色瓜”“深色瓜”甚至“本地瓜”“外地瓜”。这样的学习过程有助于我们了解数据的内在规律。在聚类学习中“浅色瓜”“深色瓜” 这样的概念是我们事先不知道的而且在学习过程中使用的训练样本通常是不拥有标记信息的

根据训练数据 是否拥有标记信息 可分为

监督学习supervised learning
无监督学习unsupervised learning
分类和回归是监督学习的代表
聚类是无监督学习的代表

⭐️机器学习的目标是使学得的模型能很好地适用于新样本而不仅仅是在训练样本上工作的更好

泛化generalization能力学得模型适用于新样本的能力
具有强泛化能力的模型能很好地适用于整个样本空间于是尽管训练集通常只是样本空间的一个很小的采样我们仍希望它能够很好地反映出样本空间的特征。

通常假设样本空间中全体样本服从一个未知 分布distribution𝓓
我们获得的每个样本都是独立地从这个分布上采样获得的即 独立同分布independent and identically distributed简称 i.i.d.
一般来说训练样本越多我们得到的关于 𝓓 的信息越多这样就越有可能通过学习获得具有 强泛化能力 的模型.

1.3 假设空间

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

所谓归纳就是由特殊到一般的 泛化generalization 过程
所谓演绎就是由一般到特殊的 特化inductive learning 过程

归纳学习
广义从样例中学习
狭义从训练数据中学得 概念concept因此亦被称为 概念学习 或 概念形成

现实常用的技术大多是产生 黑箱 模型

概念学习中最基本的是布尔概念学习即 是不是 这样的可表示 0/1 布尔值的目标概念的学习

我们可以把学习过程看作是一个在所有假设组成的空间中进行搜索的过程搜索目标则是找到与训练集 匹配fit 的假设假设的表示一旦确定假设空间及规模大小就确定了

可以有很多的策略对假设空间进行搜索例如自顶向下、从一般到特殊、自底向上、从特殊到一般搜索过程中可以不断删除与正例不一致的假设、和或与反例一致的假设最终将会获得与训练集一致即堆所有训练样本能够进行正确判断的假设。

1.4 归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好称为 归纳偏好inductive bias或简称为偏好
任何一个有效的机器学习算法必有其归纳偏好否则它将被假设空间中看似在训练集上“等效”的假设所迷惑而无法产生确定的学习结果

还是拿西瓜举例子判断一个好瓜到底是 根蒂 重视还是对 敲声 更重视这是对属性进行选择被称为 特征选择feature selection机器学习中的特征选择仍是基于对训练样本的分析进行的这里对某种属性的信赖可视为基于某种领域知识而产生的归纳偏好

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

💥重点来喽
奥卡姆剃刀Ocam’s razor 是一种常用的、自然科学研究中 最基本 的原则即如有多个假设与观察一直则选最简单的那个。

然而奥卡姆剃刀并非唯一可行的原则奥卡姆剃刀本身存在不同的诠释使用奥卡姆剃刀原则并不平凡或者你可以理解为在如何判断 简单 这个问题上并不简单。

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

对于下图而言
1.4 归纳偏好
机器学习算法在学习过程中对某种类型假设的偏好称为 归纳偏好inductive bias或简称为偏好
任何一个有效的机器学习算法必有其归纳偏好否则它将被假设空间中看似在训练集上“等效”的假设所迷惑而无法产生确定的学习结果

还是拿西瓜举例子判断一个好瓜到底是 根蒂 重视还是对 敲声 更重视这是对属性进行选择被称为 特征选择feature selection机器学习中的特征选择仍是基于对训练样本的分析进行的这里对某种属性的信赖可视为基于某种领域知识而产生的归纳偏好

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

💥重点来喽
奥卡姆剃刀Ocam’s razor 是一种常用的、自然科学研究中 最基本 的原则即如有多个假设与观察一直则选最简单的那个。

然而奥卡姆剃刀并非唯一可行的原则奥卡姆剃刀本身存在不同的诠释使用奥卡姆剃刀原则并不平凡或者你可以理解为在如何判断 简单 这个问题上并不简单。

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

对于下图而言

对于两股曲线你可以想当然的认为曲线A是更平滑的即更简单的我们期待 𝓛a 比 𝓛b 更好确实图a显示出与 B 相比A 与训练集外的样本更一致换言之A 的泛化能力比 B 强。

But !对于图b而言我们又可以直观的感受到 𝓛b 比 𝓛a 更好

换言之对于一个学习算法 𝓛a若它在某些问题上比 𝓛b 好则必然存在另一些问题在那里 𝓛b 比 𝓛a 好我们接下来去证明它

我们设样本空间𝓧假设空间𝓗都是离散的令 P(h|X, 𝓛a) 代表算法 𝓛a 基于训练数据 X 产生假设 h 的概率再令 f 代表我们希望学习的真实目标函数 . 𝓛a 的“训练集外误差”即 𝓛a 在训练集之外的所有样本上的误差为

公式说明首先两个求和符号的解释我们最终的结果是 产生 h 的所有情况的和并且我们的训练集外的样本空间为𝓧 - X要考虑所有情况故也需要求和P(h|X, 𝓛a) 是基于训练数据产生假设 h 的概率即对于每一个 h 都对应一个概率 P(h|X, 𝓛a) 从训练集外所有的样本中挑选 𝔁 的概率为 P(𝔁) 这时我们已经挑选了一个 𝔁 我们需要把 𝔁 分别带入到 h(𝔁) 和 f(𝔁) 中去比较实际值和估计值是否相等不相等运算结果为 P(𝔁) * 1 * P(h|X, 𝓛a) 相等运算结果为 P(𝔁) * 0 * P(h|X, 𝓛a) 最终按照前述求和即可。
接下来我们来考虑二分类问题且真实目标函数可以是任何函数 𝓧 → {0,1}函数空间为{0,1}|𝓧|对所有可能的 f 按 均匀分布 对误差求和有

公式说明从公式的第一行到公式的第二行就是把第一个公式进行带入的结果然后从第二行到第三行则是类似量词辖域收缩扩张公式的推导从公式第三行到第四行我们进行举例讲解
首先我们需要知道此时假设 f 是任何能将样本映射到 {01}的函数存在不止一个 f 时 f 服从 均匀分布 即对于每个 f 出现的概率都是相等的假设我们的样本空间只有两个样本时 𝓧 = {x1x2}| 𝓧 | = 2那么所有可能的真实目标函数 f 如下

f1 f1(x1) = 0f1(x2) = 0
f2 f2(x1) = 0f2(x2) = 1
f3 f3(x1) = 1f3(x2) = 0
f4 f4(x1) = 1f4(x2) = 1
一共有 2|𝓧| = 22 = 4 个可能的真实目标函数所以此时通过算法 𝓛a 学习出来的模型 h(x) 对于每个样本无论预测值是 0 或是 1都必然有且只有一半的 f 与它的预测值相等
从最终得到的式子中我们可以发现总误差与学习算法无关训练集外误差仅和数据集本身数据集取得集外数据xi的概率相关和算法La无关 → 训练集外的误差和算法所构建的模型没有关系故我们对于任意的两个学习算法 𝓛a 和 𝓛b我们都有

也就是说无论学习算法 𝓛a 多么的聪明 𝓛b 多么的笨拙它们的期望值是始终相同的这就是 “没有免费的午餐”定理No Free Lunch Theorem简称 NFL定理

❗️ NFL 定理有一个重要的前提所有问题出现的机会相同或所有问题同等重要即我们假设了f 服从 均匀分布 但是实际生活中并不是这样很多时候我们只关注自己正在试图解决的问题例如某个具体应用任务希望为它找到一个解决方案至于这个解决方案在别的问题甚至在相似的问题上是否为好方案我们并不关心。就拿推导过程中的 f1 f2 f3 f4 举例通常我们只认为能高度拟合已有样本数据的函数才是真实目标函数例如现在已有的样本数据为{(x10)(x21)}那么此时只有 f2 才是我们认为的真实目标函数由于没有收集到或者根本不存在 {(x10)(x20)}{(x11)(x20)}{(x11)(x21)} 这类样本所以 f1 f3 f4 都不算是真实的目标函数。
🌟 所以NFL 定理最重要的寓意是让我们认识到脱离具体问题空泛地谈论“什么学习算法更好”毫无意义因为若考虑所有潜在的问题则所有学习算法都一样好要谈论算法的相对优劣必须针对 具体 的学习问题在某些问题上表现好的学习算法在另一些问题上却可能不尽如人意学习算法自身的归纳偏好与问题是否匹配往往会起到决定性作用。

1.5 发展历程机器学习

    推理期
        连接主义1950s
        符号主义1960s

    知识期1970s
    机器学习1980s符号主义
    ｜ 机械学习、示教学习+类比学习、归纳学习监督or无监督
        决策树
        BP算法

    统计学习1990s
        SVM

    深度学习2000s连接主义
        神经网络

第二章 模型评估与选择

2.1 经验误差与过拟合

经验误差与过拟合
经验误差训练误差学习器在训练集上的误差
泛化误差在新样本上的误差
欠拟合模型没有很好地捕捉到数据特征不能够很好地拟合数据
过拟合将数据学习得太彻底把噪声数据的特征也学习了不能很好地识别数据

2.2评估方法

2.2.1留出法
2.2.2 交叉验证法**

特例: 留一法leave-one-out (LOO) 往往比较准确但未必永远最准确NFL定理

2.2.3自助法 bootstrapping

    ｜ 用于 小数据集难以划分训练、测试集上

2.2.4调参

        训练集划分为训练集+验证集基于验证集的性能调参
        实数范围内取值对每个参数选定范围和步长

2.3 性能度量

有效可行的实验估计方法衡量模型泛化能力的评价标准

混淆矩阵

二分类

        P选尽可能对的R选尽可能全的。P与R是矛盾的。P高则R低P低则R高。
        平衡点Break-Event Point (BEP) : P=R.  
        学习器C的BEP是0.64 B的是0.72A是0.80学习器A最优

将BEP优化一下可以得到F1

多分类
宏查准、宏查全、宏F1
｜ 分成N个二分类后 分别计算P\R\F1 然后求均值
微查准、微查全、微F1
｜ 分成N个二分类后 分别 求均值 然后算P\R\F1

2.3.3 ROC \ AUC

ROC : 直观的反应模型性能但是难以比较不同模型的差异。

         横轴TPR真正例率
             TPR=TP/(TP+FN)
         纵轴FPR假正例率
             FPR=FP/(TN+FP)

AUC :ROC曲线的下方的面积求和而得 考虑样本预测的排序质量与排序误差有紧密联系。南瓜书公式2.20公式2.21