Foundations of Machine Learning

《Foundations of Machine Learning》一书是一本很好的机器学习教材，

作者: Mohri,Rostamizeadeh, Talwalkar.

Machine Learning Foundation:

特点：

理论性强，书中公式极多，基础性机器学习书籍

chapter 1: Introduction [总体介绍]

part:

机器学习应用场景

机器学习任务

机器学习元素定义和学习场景

模型泛化性

part1: Applications [机器学习应用场景]

包括: 文本分类[text or document classification],  NLP[这里的nlp主要是指句子成分分析,词性标注等技术], 语音识别[Speech processing applications], 计算机视觉[Computer vision applications], 生物学模式识别[Computational biology applications]等。不一一列举

part2: Standard Learning Tasks [机器学习经典任务和学习场景]

classification[分类]： 分类任务是很多机器学习算法和理论的基础，许多问题都可以抽象成一个分类任务加以建模

Regression[回归]:  回归任务和分类任务的区别,是回归任务预测的目标是一个real value,而不是一个分类标签[this is the problem of predicting a real value for each item.]

Ranking[排序]: 排序任务, 如网页搜索的场景. [this is the problem of learning to order items according to some criterion.]

Clustering[聚类]: 将一个数据集按照一定的规则划分成N个子集. 一般针对比较大的数据集对数据分析 [this is the problem of partitioning a set of items.]

Dimensionality reduction or manifold learning[降维]:  将一个样本的表示做降维处理. [this problem consists of transforming an initial representation of items into a lower-dimensional representation]

part3: Learning stages[学习阶段]

机器学习基本元素的定义列举如下:

Examples: 样本.  用于做训练和测试[Items or instances of data used for learning or evaluation].

Features: 特征.  属性集合，一般用向量表示, 用于表示一个样本. [The set of attributes, often represented as a vector, associated to an example]

Labels: 标签，也就是要学习的目标.[Values or categories assigned to examples]

Hyperparameters: 超参数. 一些在算法model中没有被定义，需要特殊定义和初始化的参数.

Training sample: 训练样本 [Examples used to train a learning algorithm.]

validation  sample: 校验样本，用于作为确定模型参数的标准样本[Examples used to tune the parameters of a learning algorithm.]

test sample: 测试样本, 用户作为衡量模型效果的样本[Examples used to evaluate the performance of a learning algorithm.]

Loss function: 损失函数[A function that measures the difference] 说的直白点，就是衡量y与y1的差距.

这里可以展开一下：

Loss function一般有哪一些？

再进一步想一个问题：为什么在深度学习的过程中，一般使用交叉熵，而不采用平方差等loss的形式呢？

还是要推导loss公式反向传播看一下:

一般y_pred是由sigmoid函数得到:

从上面的推导可以看出, 若将sigmoid之前的输出值看做x，则L对x的导数可以变成上面那种简单的形式。梯度求导计算简单又好传递. 有兴趣的话，还可以推导一下squares loss的dL/dx, 结果比较复杂在这里就不表述了.

言归正传，机器学习元素这一块，还需要有以下的注意：

特征的提取是机器学习的关键。它是作为machine learning的input出现的。在样本不足的情况下，根据知识人工提取有用的特征，是防止过拟合的一种重要手段.

Reference: This is a critical step in the design of machine learning solutions. Useful features can effectively gude the learning algorithm, while poor or uninformative ones can be misleading.Although it is critical, to a large extent, the choice of the features is left ot the user. This choice reflects the user's prior knowledge about the learning task which in practice can have a dramatic effect on the performace result.

学习场景[learning scenarios]

机器学习算法运行的具体场景定义，和学习过程有关。 分为：监督学习，无监督学习，半监督学习，转导推理，线上学习，强化学习，主动学习等。

监督学习： 对有标注的一批样本进行学习，验证和测试

无监督学习：对没有标注的样本进行学习分析，比较有代表性的是cluster.

半监督学习：这种学习场景，一般出现在有一部分标注样本和大量的未标注样本，标注的成本较高。半监督学习的目的就是怎样将大量的未标注样本，用于帮助标注样本取得更好的学习效果。这一主题下衍生出大量的现代理论和机器学习研究成果，是目前研究的一大焦点。

转导推理：类似于无监督学习，有一部分标注样本和未标注样本。但转导推理的目标是给这一部分未标注的样本做推理和打标签。未标注样本即是可以帮助标注样本做预测的集合，又是推理的目标。

在线学习：在线学习的集合是多轮变化的，在每一轮中，都有一批未标注的样本，使用model对样本进行预测之后，对预测的样本打label，得到一批新的学习样本，在线学习的目标是保证多轮累加loss [cumulative loss] 的最小化。

强化学习：强化学习的场景，学习器和环境进行不断的交互，接受者将正负反馈传递给学习器，学习器会逐渐选择奖励最多的一条路径。

主动学习：主动学习的一个关键就是定向采样。由于标注的代价较高，为了减少标注成本，学习者会主动定向针对需要学习的任务采样代表性的样本，并采用定向增强的方式，将更有价值的样本做标注采样，替换随机取样的方式。这一系列的过程称为active learning.

part4: 模型泛化性

我们学习machine learning的目的就是为了提升模型的泛化性[Machine learning is fundamentally about generalization.] 注意, machine learning的目的不是为了拟合训练数据，而是在没有见过的测试数据上也可以做正确的预测。因此就有了欠拟合和过拟合的概念，这决定了假设集，也就是学出来的模型的复杂度的选择：

过拟合：当一个模型学习的太复杂，导致一些有一些不重要的特征都作为划分依据，会导致拟合过度而泛化能力降低。比如你拿了一批小学生的样本，有身高，体重，运动成绩等。如果样本分布不均衡，采样到了一批运动成绩普遍不强的小学生的样本，模型在学习的时候，会误把运动成绩差作为样本是小学生的feature，过拟合了.

欠拟合：欠拟合的直观感受就是，学到的特征太少，分隔曲线过于简单。

因此,样本大小，分布和模型复杂度在ML里面扮演重要角色。如果样本数目本来不多，选择参数较大的复杂模型，容易导致模型缺乏泛化性，也就是过拟合。

接下来引入本书的一个重要评价概念：PAC Learning Framework

PAC: Probably Approximately Correct [假设集正确率衡量]

意义：根据获得近似解所需的样本点数来定义可学习概念的类别，从而定义平衡模型的复杂度，以及模型的性能。

[PAC helps defines the class of learnable concepts in terms of the number of sample points needed to achieve an approximate solution.]

PAC 定义:

这两个误差之间的关系：

ES∈Dm[Rs(h)]=R(h)

泛化误差是经验误差在各个样本集合中的期望.

下面就可以给出PAC-learnable的定义：

对于一个h,c,D集合, 如果对于任何给定的

就可以说，这个按照c标准进行标注的集合D，对于h来说，是可以学习的。

有关PAC的进一步介绍和举例，请看下篇更新.