前言
一直以来都想系统学习机器学习和深度学习，但因为自制力不够，加上时间紧张，总是没能正式开始。书架上的瓜书和花书已经落了灰。虽然很多人说入门机器学习不难，网上也有很多开源项目和学习资源，但我始终觉得如果想有所建树，还是得从基础一步步打牢。这学期总算能挤出些时间，所以决定从今天开始，在这里记录自己的学习过程，也算是给自己一个督促和坚持下去的理由。
基本术语
瓜书封面是西瓜，绪论一开始举例也是西瓜，看得出来作者很喜欢西瓜()。
数据、数据集
数据，也就是一些可以用来分类、含有某种特点的信息，比如西瓜的一些信息（色泽=青绿；根蒂=蜷缩；敲声=浊响）…，一对括号内称为一条记录，“=”也就是“取值为”。
一组记录的集合称为数据集(data set)，每条记录是关于一个事件/对象的描述，称为示例(instance)或样本(sample)，每个样本中“=”左边的是反应事件或对象在某方面的表现或性质的事项，称为属性(attribute)或特征(feature)，右边则是取值，称为属性值(attribute value)。属性张成的空间称为属性空间(attribute space)、样本空间(sample space)或输入空间。每一个属性可以看成一个维度，多个属性取值构成的集合，也就是示例，就可以称为特征向量(feature vector)。
令$D = \{\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_m \}$ 表示包含$m$个示例的数据集，每个示例由$d$个属性描述，则每个示例$\mathbf{x}_i = (x_{i1};x_{i2};\dots;x_{id})$ 是$d$ 维样本空间$\chi$ 中的一个向量，$x_i \in \chi$ ，其中$x_{ij}$ 是$x_i$ 在第$j$ 个属性上的取值，$d$ 称为样本$x_i$ 的维数(dimensionality)。
学习/训练
学习和训练就是从数据中学得模型的过程，通过某个算法来完成。训练使用的数据称为训练数据，也就是训练集，训练集中的样本就是训练样本。模型对应了数据的某种潜在规律，也称为假设(hypothesis)，这种潜在规律自身称为真相或真实(ground-truth)，学习过程就是要逼近真相。
要得到模型仅有数据是不够的，还要有模型的输出信息，例如“好瓜”、“坏瓜”，称为标签(label)，拥有标签的示例，称为样例(example)，一般用$(\mathbf{x}_i, y_i)$ 表示第$i$ 个样例，其中$y_i \in {\cal Y}$ 是示例$\mathbf{x}_i$ 的标记，$\gamma$ 是所有标记的集合，称为标记空间(label space) 或输出空间。
预测离散值的学习任务称为分类，预测连续值的学习任务称为回归 。只涉及两个类别（正类、反类）的任务称为 “二分类(binary classification)”任务 ；设计多个类别，则称为 “多分类(multi-class classification)”任务 。
一般地，预测任务是希望通过对训练集$\{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2),\dots, (\mathbf{x}_n, y_n) \}$ 进行学习，建立一个从输入空间$\chi$ 到输出空间$\gamma$ 的映射$f:\chi \mapsto {\cal Y}$ 。对于二分类任务，通常令${\cal Y} = \{-1, +1 \}$ 或$\{0, 1\}$ ；对于多分类任务，$|{\cal Y}|>2$ ；对回归任务，${\cal Y} = {\Bbb R}$ ，${\Bbb R}$ 为实数集。
学得模型后，使用其进行预测的过程称为测试(testing) ，被预测的样本称为测试样本(testing sample) 。例如：$y = f(\mathbf{x})$ ，其中$f$ 是模型，$\mathbf{x}$ 是测试样本，$y$ 是预测标记。
将训练集中的数据分成若干组的过程叫做聚类(clustering) ，每组称为一个簇(cluster)。这些簇可能对应一些潜在的概念划分，能帮我们了解数据的内在规律。注意： 在聚类之前，对分类的情况我们是不知道的，且学习过程中使用的训练样本通常不拥有标记信息。
监督学习(supervised learning) 使用的训练数据拥有标记信息，例如分类和回归；无监督学习(unsupervised learning) 使用的训练数据则没有标记信息，例如聚类。
学得模型适用于新样本的能力，称为泛化(generalization)能力 ，我们希望得到具有强泛化能力的模型，即可以很好的适用于整个样本空间。
通常假设样本空间中全体样本服从一个未知"分布"(distribution)${\cal D}$，我们获得的样本都是独立地从这个分布上采样获得的，即独立同分布(independent and identically distributed，简称$i.i.d.$)。
一般而言，我们得到的关于${\cal D}$ 的信息越多，就越有可能通过学习获得具有强泛化能力的模型。
假设空间
演绎(deduction) 是从一般到特殊的特化过程，即从基础原理推演出具体状况。如在数学公理系统中，基于一组公理和推理规则推导出与之相洽的定理。
归纳(induction) 是从特殊到一般的泛化过程，即从具体的事实归结出一般性规律，如“从样例中学习”就是一个归纳的过程，所以也称为“归纳学习(inductive learning)”。
广义的归纳学习大体相当于从样例中学习，而狭义的归纳学习则要求从训练数据中学得概念(concept)，因此也称为“概念学习”或“概念形成”。
概念学习中最基本的是布尔概念学习，即对“是” “不是”这样的可表示为0/1布尔值的目标概念的学习。我们可以把学习过程看做一个在所有假设(hypothesis)组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配(fit)”的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。
可以有许多策略对这个假设空间进行搜索，例如自顶向下、从一般到特殊，或是自底向上、从特殊到一般，搜索过程中可以不断删除与正例不一致的假设，和（或）与反例一致的假设。最终将会获得与训练集一致（即对所有训练样本能够进行正确判断）的假设，就是我们学得的结果。
所谓假设空间，其实就是我们建立出的模型，例如对同一个数据集可以有$y = wx+b$的一元一次函数关系，该函数关系就是假设空间，当然也可能会有$y = w ^2 x+b$的二次函数关系，这意味着可能有多个假设与训练集一致，且都有可能学得与数据集拟合的模型，我们将所有能够拟合训练集的模型构成的集合称为 “版本空间”。
归纳偏好
机器学习算法在学习过程中对某种类型假设的偏好，称为**“归纳偏好”**，例如使用一元线性回归算法，学得的模型是一元一次函数，使用多项式回归算法时，学得的模型是一元二次函数。
归纳偏好可看做学习算法自身对假设进行选择的启发式或“价值观”。有时会使用奥卡姆剃刀来引导算法的“正确”偏好，即：若有多个假设与观察一致，则选最简单的那个。但是怎样来定义“简单”又是一个困难的问题。因此我们最常用的方法是基于模型在测试集上的表现来评判模型之间的优劣。 但是在不同的情境下，模型的表现也有不同的评判准则，因此学习算法之间没有绝对的优劣，我们可以作如下讨论：
假设样本空间${\cal X}$和假设空间${\cal H}$都是离散的，令$P(h \mid X,{\cal L_a})$代表算法${\cal L_a}$基于训练数据$X$产生假设$h$的概率，令$f$代表我们希望学习的真实目标函数。${\cal L_a}$在训练集之外所有样本上的误差为
$$ E_{ote}({\cal L_a}\mid X,f)=\sum_h \sum_{x \in {\cal X} - X} P(x){\Bbb I}(h(x) \neq f(x))P(h \mid X, {\cal L_a}) $$笔者注： 在这里误差是由概率的乘积来表示的，与我们熟知的差值，即$|h(x)-f(x)|$的形式不符，这是因为传统意义上的误差指的是预测值与真实值之间的差值，而在机器学习中，我们通常关心的是模型在所有可能数据点上的平均性能，即 期望误差，所以要将所有数据点的误差加权平均来计算。在该公式中，误差并没有具体的值，而是使用指示函数${\Bbb I}(\cdot)$来表示，若$\cdot$为真则取值$1$，否则取值$0$，也就是将每个样本的误差都用$1$来表示了。
考虑二分类问题，且真实目标函数可以是任何函数${\cal X} \mapsto \{0,1 \}$，函数空间为$\{0,1 \}^{|{\cal X}|}$，对所有可能的$f$按均匀分布对误差求和，有
$$ \begin{align*} \sum_f E_{ote}({\cal L_a}\mid X,f) &= \sum_f \sum_h \sum_{x \in {\cal X} - X} P(x) {\Bbb I}(h(x) \neq f(x))P(h\mid X,{\cal L_a}) \\ &= \sum_{x \in {\cal X} - X} P(x) \sum_h P(h \mid X, {\cal L_a}) \sum_f {\Bbb I}(h(x) \neq f(x)) \\ &= \sum_{x \in {\cal X} - X}P(x)\sum_h P(h \mid X, {\cal L_a}) \frac{1}{2}2^{|{\cal X}|} \\ &= \frac{1}{2}2^{|{\cal X}|} \sum_{x \in {\cal X} - X}P(x)\sum_h P(h \mid X, {\cal L_a}) \\ &= 2^{|{\cal X}| - 1} \sum_{x \in {\cal X} - X}P(x) \cdot 1 \end{align*} $$
笔者注： 从第一步到第二步，能将三重求和分开来进行一次求和，首先是因为 $P(h \mid X, {\cal L_a})$与 $x$ 和 $f$ 没有关系，可以直接对$h$进行求和，且遍历整个随机变量的取值求和之后为$1$ ，其次${\Bbb I}(h(x) \neq f(x))$ 的取值只有$1$和$0$，可以直接提出来，不影响其他项的求和。
至于$\sum_f {\Bbb I}(h(x) \neq f(x))$ 的结果，我们知道假设$f$是任何能将样本映射到$\{0, 1 \}$的函数，且假设$f$服从均匀分布，即每个$f$出现的概率相等，所有$f$的数量为$2 ^ {|\cal X|}$（即${\cal X}$中每个样本取$0$或$1$，遍历所有结果），对于某个$x_1$，$h(x_1)$显示的预测不管是$0$还是$1$，一定有一半的$f$有同样的预测，另一半有不同的预测（即$x_1$取$0$或$1$，两种情况是等可能的），所以$\sum_f {\Bbb I}(h(x) \neq f(x)) = \frac{1}{2}2^{|{\cal X}|}$
最后的结果$\sum_f E_{ote}({\cal L_a}\mid X,f) = 2^{|{\cal X}| - 1} \sum_{x \in {\cal X} - X}P(x) \cdot 1$ 显示出，总误差与学习算法无关，不同的算法最后的期望性能是相同的。这就是 “没有免费的午餐"定理(No Free Lunch Theorem，简称NFL定理) 。
当然，实际情况要复杂得多，NFL定理的重要前提是所有“问题”出现的机会相等、或所有的问题同等重要，这在是实际情形中显然是不可能的。其次，NFL的论述过程中假设$f$是服从均匀分布的，但是实际情况中我们通常只认为能高度拟合已有样本数据的函数才是真实目标函数。
所以，NFL定理的意义是让我们意识到不能脱离实际谈问题，要谈论学习算法的优劣，必须要针对具体的学习问题。
结语
第一章绪论的内容涉及大量术语，且很多术语都有多个叫法，通读一遍后感觉脑子像被犁了一遍，很多概念还是需要结合具体例子才更容易懂。在这一章大致建立了机器学习的框架，包括数据集、学习种类、训练方法等，虽然还没有真正进入机器学习的领域，但也算迈出了第一步，希望接下来的学习能带来更多的收获。