机器学习笔记E1--术语理论

这是机器学习笔记的第一篇，主要介绍了机器学习的一些常用术语和基础知识
由于水平有限，有时候笔记显得像是板书一样把所有的东西都堆叠在一起，在完成了完整的笔记之后，我会回过头再来整理

基本术语

先来了解一下机器学习的基本知识（参考于西瓜书）
假设我们收集了一批关于西瓜的数据

序号	色泽	根蒂	敲声
001	青緑	蜷缩	浊响
002	乌黑	稍蜷	沉闷
003	浅白	硬挺	清脆
...	...	...	...

对于数据来讲

• 对于这组记录的数据而言，这组记录的集合称之为 数据集（data set） 。
• 其中每条记录是关于一个事件或者对象（这里是每一个西瓜）的描述，称为一个 示例（instance） 或 样本（sample） 。
• 而反映每个样本在某一方面的表现，例如色泽、根蒂和敲声，称为 特征（feature） 或 属性（attribute） 。属性的取值，如青緑、乌黑，称为 属性值（attribute value） 。属性张成的空间称为 属性空间（attribute space） 、 样本空间（sample space） 或 输入空间 。
• 例如我们把色泽、根蒂，敲声做为三个坐标轴，则他们张成一个用于描述西瓜的三维空间，每个西瓜可以在这个空间里面找到对应的坐标位置，而空间中每一个点都对应一个坐标向量，因此我们也把一个样本称为一个 特征向量（feature vector） 。

对于机器学习部分

• 如果我们希望借由西瓜的以上特征来 预测（prediction） 一个没剖开的瓜的好坏的话，仅有这些示例数据是不够的，我们还需要训练样本的结果信息，例如001号瓜的三个特征得到的结果是它是一个”好瓜“，那这里“好瓜”就是一个 标记（label） ；拥有标记信息的示例，称之为 样例（example）
• 若将标记看作为对象本身的一部分，那其实样例也可以称作样本。术语只是为了方便更专业的沟通，表达和理解到位就行，这里没必要太过于纠结。
• 对于预测的结果而言，如果我们预测的是离散值，例如“好瓜”和”坏瓜“，此类学习任务我们称之为 分类（classification） ；若预测的是连续值，例如西瓜的成熟度0.8、0.9、0.95,此类学习任务就称之为 回归（regression）
• 对只涉及两个类别的 二分类（binary classification） 任务，通常称其中一个类为 正类（positive class） ，另外一个类为 反类（negative class） 。有趣的是，在吴恩达老师的介绍中，正类在英语的表述上往往是具有某种东西，而不是中文心理偏向上具有“好”的这一正面性质的东西。例如对于预测患者是否有肿瘤这一问题，常说的正类为“有肿瘤”，反类是“无肿瘤”，同样的，术语而已，没必要纠结。
• 分类问题在涉及多个类别时，则称为 多分类（multi-class classification） 任务。
• 我们还可以对西瓜做 聚类（clustering） ，即将训练集中西瓜分成若干组，每组称为一个 簇（cluster） ；这些自动形成的簇可能对应一些潜在的概念划分，例如“浅色瓜”、“外地瓜”，这样的学习过程有利于我们了解数据的内在规律。在聚类学习中 ，“浅色瓜”、“外地瓜”这样的概念我们事先是不知道的，而且学习过程中使用的训练样本通常不拥有标记信息。

机器学习分类

根据训练数据是否拥有标记信息，学习任务可大致分为两大类： 监督学习（supervised learning） 和 无监督学习（unsupervised learning） ，分类和回归是监督学习的代表，而聚类则是无监督学习的代表。
此外还有半监督学习和强化学习，后续补充

输入空间、特征空间、输出空间

前面有讲到， 特征 张成的空间称为 输入空间 ，简单来讲， 输入空间 和 **输出空间 **即是学习中输入和输出所有可能取值的集合。所以特征向量存在的空间称为 特征空间 。特征空间中每一维对应于一个特征。有时候输入空间和特征空间是相同的，有时候需要在输入空间中提取特征。模型都是定义在特征空间上的。

假设空间、版本空间与归纳偏好

在监督学习中，学习的目的是为了学习一个由输入到输出的映射，而为了得到这个映射，我们会提出关于这个映射的一种假设，而这个假设的所有可能性就组成了一个假设空间。

例如我们在数据集中增加一项标记项，标记该样本是否为好瓜（是，不是）。假设是否为“好瓜”可有“色泽”、“根蒂”、“敲声”完全确定，那么对于西瓜的特征，色泽可能的取值有“青緑”“乌黑”“浅白”以及“无所谓色泽”（这里只针对三个样本构成的训练集而言）四种取值，那么此时假设空间的规模为4×4×4=64，此外，存在一种极端情况，“好瓜”根本是一个伪命题，世界上根本不存在所谓“好瓜”，这种假设我们类似于空集的意义，所以最终的假设空间的大小为64+1=65。对于没见过的瓜（不在训练集中的样本），我们可以把学习过程看作一个在假设空间中进行搜索的过程，搜索目标是找到与训练集匹配的假设。在多个训练集样本的影响下不断修正，最后找到能够将训练集中的瓜判断正确的假设

这里我可能说的不太清楚，实际上假设是一种“假设函数”，是学习的结果，如

y = ax + b

a有无穷种取值，b也有无穷种取值，这个函数的假设空间也是无穷大的，但是通过训练集中给出的x和y值，我们最终会找到一个能够与训练集相匹配的a、b的值，得出一个确定的线性方程。即找到与训练集匹配的假设。

可以有很多策略对这个假设空间进行搜索，例如自顶而下、从一般到特殊，搜索过程中可以不断删除与正例不一致的假设、与反例一致的假设，最终将会获得与训练集一致（即对所有训练样本能够进行正确判断）的假设，这就是学习的最终结果。

实际上，现实问题中我们面对的假设空间常常是很大的，但学习过程是基于有限样本训练的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”，称之为 版本空间 。

例如，现在对应训练集有三个假设与之一致，分别为

y=2x+1、y=1.5x+1.5、y=3x

对于训练集（例如x=1），这三种假设都能做到与之一致（y=3）。在面临新的样本（例如x=2）的时候，很显然，这三种结果对应的y值（5,4.5,6,）显然不同，那我们到底该采用哪一种模型（假设）呢？

仅根据现有的训练集，无法断言哪种模型更好，这时候，学习算法本身的“偏好”就会起到关键作用，例如，算法比较“喜欢”极端的模型，那它可能会选择y=3x;“喜欢”平衡的模型，那它可能选择y=1.5x+1.5。机器学习算法在学习过程中对某种类型假设具有偏好，称为 归纳偏好（inductive bias）。一般来讲，所有的学习算法都是有归纳偏好的，而且一般偏好于那些形式简单的假设（奥卡姆剃刀Occam's razor：若有多个假设与观察一致，则选最简单的那个）。

理论

统计学习的三要素

来自于《统计学习方法》
统计学习方法都是由模型、策略加算法构成：

方法 = 模型 + 策略 + 算法

模型

统计学习首先要考虑的问题就是学习什么样的模型，模型确定了，模型的假设空间就确定了，后面要做的就是从假设空间中搜索最优假设，这也是统计学习的目标。

策略

我们判断空间中一个假设优于另一个的标准有两个： 经验风险最小 和 结构风险最小 。
经验风险最小化就是指我们的假设关于训练数据集平均损失最小化。经验风险过大会出现欠拟合的问题
另一方面，相对于整个样本空间，训练集是很小的，而且训练集中的数据又难免会遭到噪声干扰，所以基于训练集去拟合真实函数，及时在训练集上的经验风险已经最小了，但在测试集上做预测的误差也可能会很大，易出现 过拟合 的问题。所谓过拟合即是太强调与训练集数据的一致，构建出一个经验风险很小但结构过于复杂的函数，虽然与训练集数据完美拟合，但在测试集数据上却不理想。
结构风险最小化就是为了解决过拟合的问题。结构风险是指假设函数的结构的复杂程度，假设函数的结构越复杂，结构风险越大。结构风险小需要假设函数的经验风险和结构的复杂度同时小。

如何把结构风险化的思想带入到模型中呢？
答案是通过在经验风险的基础上引入一个正则化项（或称惩罚项）来限制假设函数的结构，结构越复杂惩罚也就越大。

算法

统计学习中算法是指学习模型的具体计算方法。例如求解最优化问题的，如果这个最优化问题有解析解不存在就需要用数值计算的方法求数值解了，比如梯度下降法、拟牛顿法等，使用类似的迭代方法时，如何保证找到全局最优解并且使求解过程非常高效是一个非常重要的问题。算法如果迭代的特别慢或者压根就收敛不了那就没有意义

NFL定理

在看这个定理的时候，很多文章对定理的引入都是由读者“既然统计学习中模型确定了，假设空间就确定了，剩下的就是找最优解，那有不有一种最强的模型呢？”我觉得这个问题有点多余呀，真的有一劳永逸的事情吗？
言归正传，NFL（No Free Lunch）直译为“没有免费的午餐”，指在机器学习算法中，不针对具体问题的情况下，训练集之外的所有样本的误差与学习算法无关，他们的期望性能都是相同的。即没有那种算法胜过另一种算法。
这里的推导选用了西瓜书上的推导过程：

image
image

计算学习理论

< Unfinished>
参考西瓜书第十二章

PAC学习理论

前面讲到，经验风险和结构风险过大的时候容易造成欠拟合和过拟合的问题，为什么会这样呢？
为什么我们认定按照训练集训练出来的模型能对训练集之外的数据切实有效呢？
带着这两个问题我们再来看PAC（可能近似正确，probably approximate correct）学习理论。

什么是PAC学习理论

简单来讲，

之后补充，放链接
30分钟了解PAC学习理论
机器学习有效性

后续需要完善的事情

1. 大且繁，分篇
2. 精简语言
3. 其他方法和理论 如交叉验证，判断一个算法的优缺点 等等
   《机器学习（周志华）》学习笔记（二）

理论很多，全部都涉及会把自己累死，第一章定篇 #1902191113