参考资料：
李航《统计学习方法》
《机器学习实战》

1.前言

这一节主要是一些最常用、最基本的知识和概念，以理论为主，虽然学习起来比较枯燥，但是磨刀不误砍柴工。机器学习研究的对象是数据，在数据量指数性增长和爆炸的今天，它的重要性不言而喻。机器学习最基本的三个要素是模型（model）、策略（strategy）和算法（algorithm）。模型是是指数据输入（即输入集）和输出（即输出集）之间的函数映射，策略是模型选择的准则，最优模型的选取由算法实现。

2. 机器学习模型的分类

2.1 基本分类：监督学习、无监督学习和强化学习

监督学习（supervised learning）是我们最常接触到的机器学习，是指从已标注好的数据中学习预测模型的机器学习问题。将数据的输入X与输出Y的所有可能取值的集合分别称为输入空间（input space）和输出空间（output space），监督学习假设X和Y遵循联合概率分布P(X,Y)。对于每个输入变量x来说，都由一个特征向量x=(x^{(1)},x^{(2)},\cdots,x^{(i)},\cdots,x^{(n)})^T来表示，所有的特征向量则构成了特征空间（feature space）。需要注意的是，特征空间和输入空间实质上是不同的空间，数据预处理（如归一化）的过程就是将输入空间向特征空间进行映射的过程，这时我们得到的模型实质上是特征空间到输出空间之间的映射。所有模型的集合称为假设空间（hypothesis space）。

如果监督学习的模型由条件概率分布P(Y|X)决定，则该监督学习模型为概率模型；如果监督学习模型由决策函数Y=f(X)表示，则该监督学习模型为非概率模型。进一步的，根据输入变量X和输出变量Y的不同取值类型，又可分为回归问题、分类问题和标注问题。

相对应的，无监督学习（unsupervised learning）是指从未标注的数据中学习预测模型，其本质是学习数据中的统计规律或潜在结构。无监督学习模型可以实现对数据的聚类、降维或者概率估计。

强化学习（reinforcement learning）实质上是寻找最优序贯决策的过程。强化学习的马尔可夫决策过程可以看做是一个五元组(S,A,P,r,\gamma)，其中：S是有限状态（state）的集合；A是有限动作（action）的集合；P是状态转移概率（transition probability）函数P(s\prime|s,a)=P(s_{t+1}=s\prime|s_t=s,a_t=a)；r是奖励函数（reward function），r(s,a)=E(r_{t+1}|s_t=s,a_t=a)；\gamma是衰减系数（discount factor），\gamma \in [0,1]，表示奖励会有衰减。在这个马尔可夫决策过程中，下一个状态只依赖于前一个状态与动作。

假设决策过程为\pi，定义这个决策过程产生的价值函数（value function）或者状态价值函数（state value function）定义为决策过程\pi从某一个状态s开始的长期积累奖励的数学期望：

v_\pi(s)=E_\pi[r_(t+1)+\gamma r_{t+2}+{\gamma}^2 r_{t+3}+\cdots|s_t=s]

类似的，定义其动作价值函数为从某一个状态s和动作a开始的长期积累奖励的数学期望：

q_\pi(s,a)=E_\pi[r_(t+1)+\gamma r_{t+2}+{\gamma}^2 r_{t+3}+\cdots|s_t=s,a_t=a]

也就是说，强化学习就是在寻找一个最优\pi的过程。强化学习通常从一个状态或者动作（即从一个具体价值函数）开始，通过搜索最优的价值函数进行。

此外还有半监督学习（semi-supervised learning）和主动学习（active learning），这两种学习更接近于监督学习。

2.2 其他分类方式

（1）概率模型和非概率模型

概率模型取条件概率分布形式P(y|x)，非概率模型去函数形式y=f(x)。在监督学习中，概率模型是生成模型，非概率模型是判别模型。实质上，条件概率分布P(y|x)和函数y=f(x)是可以相互转化的，条件概率分布P(y|x)取最大值即可得到函数分布y=f(x)，函数y=f(x)通过归一化又可得到条件概率分布。

（2）线性模型和非线性模型

非概率模型进一步可以分为线性模型和非线性模型，如果函数分布y=f(x)是线性函数，则为线性模型，如果是非线性函数，则为非线性模型。

（3）参数化模型和非参数化模型

参数化模型假设模型可以由有限维参数完全刻画，模型参数的维度是固定的，比较适合简单的问题；而非参数化模型假设模型参数的维度是不固定或者是无限的，随着训练数据量的增加不断增大，对于复杂问题更加有效。

3. 机器学习的策略：损失函数和风险函数

损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

在监督学习过程中，我们会得到一个预测值，这个预测值f(X)和真实值Y之间会存在一定的误差，这个误差通常通过损失函数（loss function）或者代价函数（cost function）来描述。学习的目标就是希望期望风险（损失）最小。

常用的函数有以下几种：

（1）0-1损失函数

L(Y,f(X))=1, \text{ when }Y \neq f(X)

L(Y,f(X))=0, \text{ when }Y=f(X)

（2）平方损失函数

L(Y,f(X))=(Y-f(X))^2

（3）绝对损失函数

L(Y,f(X))=|Y-f(X)|

（4）对数损失函数/对苏似然损失函数

L(Y,P(Y|X))=-\log P(Y|X)

4. 模型评估与模型选择

4.1 训练误差、测试误差与泛化误差

一般来说，机器学习的数据集会按照比例分为训练集和测试集。模型在测试集上产生的误差为训练误差，在测试集上产生的误差为测试误差。对于一个学习方法来说，它对未知数据的预测能力称为泛化能力（generalization ability），那么模型对于未知数据预测的误差称为泛化误差。

我们学习的目的是使测试误差更小。然而，如果一味地追求更小的测试误差，模型的复杂度可能会上升，进而导致过拟合的问题，如下图所示：

途中可以看到，当模型的复杂度为0或时，模型是一条直线，测试误差很大，无法很好的拟合点的分布，这就属于欠拟合。而如果模型的复杂度很大很大，如M=9时，虽然模型的测试误差很小，但是可以明显地看到它模拟的不是实际的分布，这就属于过拟合的情况。

因此，在学习的时候，不仅要选择最优的模型，也要选择复杂度适当的模型。常用的模型选择方法为正则化和交叉验证。

4.2 正则化

我们将我们的损失函数加上一个正则化项（regularizer）或罚项（penalty term）\lambda J(f)，即：

\min_{f \in F} L(Y,f(X))=\frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i)) + \lambda J(f)

其中\lambda \ge 0。

正则项可以取不同的形式，一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。

4.3 交叉验证

如果样本数据充足，则可以将数据随机分为三部分——训练集（training set）、验证集（validation set）和测试集（test set）。训练集用来训练模型，验证集用于模型选择，测试集用于最终对学习方法的评估。在学习到的不同复杂度的模型中，选择对验证集有最小预测误差的模型。

如果数据不充足，可以采用交叉验证的方法，如简单交叉验证、K-fold交叉验证和留一交叉验证。

5. 开发机器学习程序的步骤