1.1 机器学习的发展与应用

1.1.1机器学习的发展

图1 传统机器学习方法的发展历程

James(1890)-神经元相互连接：

    人脑中当两个基本处理单元同时活动，或两个单元靠得比较近时，一个单元的兴奋会传到另一个单元。而且一个单元的活动程度与他周围的活动数目与活动密度成正比。

McCulloch, Pitts(1943)：

    描述了一个简单的人工神经元模型的活动是服从二值（兴奋和抑制）变化的。

Hebb学习律：

    认为学习的过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。若两个神经元输出兴奋，则之间的连接权加强，反之减少。

感知机：

1957年定义了一个神经网络结构，称为感知器(perceptron)。

 

图2 左图为神经元连接及二值变化公式、右图为感知机表示方法

Widrow-Madaline模型：

     对线性不可分问题，放弃划分样本集的决策分类面是光滑且连续的条件，代之以分段的平面。

BP (back propagation)算法：

    1986年，神经网络的反向传播学习算法。

   

PAC-Probably Approximately Correct 概率近似正确

给定实数ε,δ满足0<ε,δ<1。如果对任意的目标概念c∈H和样本分布D,若只需多项式p1(ε,δ)个样本且在多项式p2(ε,δ)时间内,学习算法 L 将至少以1-ε的概率输出一个假设h∈H，使得errorD(h)<ε,则称L是PAC学习的。

Schapire -弱学习定理

如果一个概念是弱可学习的，充要条件是它可以强可学习的。

图3 神经网络结构图

1.1.2机器学习的应用

图4 机器学习的应用领域

美国航空航天局JPL实验室的科学家在《Science》（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，……，该领域在今后的若干年内将取得稳定而快速的发展。

1.2 机器学习问题的统一表达

1.2.1机器学习的定义

•  Simon(1983)认为：“如果一个系统能够通过执行某个过程改进它的性能，这就是学习。” 这个概念相当广泛，涵盖了计算系统、控制系统及人系统等。Learning denotes changes in the system that are adaptive in the sense that they enable the system to do the same task (or tasks drawn from a population or similar tasks) more efficiently and more effectively the next time. 

•  Minsky (1985)认为：“学习是在我们头脑中（心里内部）进行有用的变化。”
•  Nilsson(1996):”A machine learns whenever it changes its structure, program, or data in such a manner that its expected future performance improves”
• 令 W 是给定世界的有限或无限的所有观测对象的集合，由于我们观察能力的限制，我们只能获得这个世界的一个有限的子集，称为样本集。机器学习就是根据这个样本集，推算这个世界的模型，使它对于这个世界(尽可能地)为真。

                        ——王珏等. 机器学习及其应用

    一致：假设世界W与样本集Q具有相同的性质。譬如，如果学习过程基于统计原理，独立同分布(i.i.d)就是一类一致条件。
    划分：将样本集放到n维空间，寻找一个定义在该空间上的决策面，使对象分在不同的区域。

    泛化：泛化能力是对这个模型为真程度的指标。从有限样本集合，计算一个模型，使得该指标最大（小）。

1.2.1机器学习的统一表达

1.2.1.1表达形式

图6  机器学习统一表达形式

1.2.1.2学习过程

根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。

产生器 G, 产生随机向量  ,它们是从固定但未知的概率分布函数 中独立抽取的；
系统S, 对每个 x  返回一个输出值 y ，产生输出的根据是同样固定但未知的条件分布函数。 

学习器LM, 它能够实现一定的函数集 ，其中是参数集合。

1.2.1.3函数评价

损失函数 loss function (L, Q)：the error of a given function on a given example

风险泛函 risk functional (R)：the expected loss of a given function on examples drawn from F(x,y) 

1.2.1.4学习目标

风险最小化：  学习的目的在于使期望风险最小化。

 经验风险最小化归纳原则(The Empirical Risk Minimization (ERM) Inductive Principle)

  核心思想：用样本定义经验风险

• Define the empirical risk (sample/training error):
• Define the empirical risk minimizer:
• Least-squares and Maximum-likelihood are realizations of ERM

1.3 几种学习问题

1.3.1 模式分类问题

    输出y是类别标号，两类情况下y={1, 0}，预测函数为指示函数(Indicator Function)，损失函数定义见下式，使经验风险最小就是Bayes决策中使错误率最小。

给定：m个类，训练样本和未知数据                目标：给每个输入数据标记一个类属性

两个阶段：
建模/学习：基于训练样本学习分类规则.

分类/测试：对输入数据应用分类规则

1.3.2 回归问题

输出y是连续变量，它是x的函数，损 失函数定义如式:

损失函数：         风险：

经验风险：

1.3.3 概率密度估计问题

根据训练样本确定x的概率分布p(x,w)，则损失函数可定义为:

最大似然估计：

1.4 学习算法的评价

机器学习问题在使用了某些算法得到效果以后，需要依据某些标准去评价算法的效果好坏。我们引入了Occam's razor（奥卡姆剃刀）

图8 奥卡姆剃刀的基本原则

1.4.1 预测精度分析

图9 线性拟合可视化分析

从上面四个图分析可知，M=0,1时拟合程度明显不足，也就是欠拟合，这样总的误差会很大；M=3时，预测的曲线与实际的曲线很接近，说明拟合效果较好；M=9时，每个观察到的数据点都能成功的经过拟合的曲线，但是该曲线显得过于复杂，在遇到新的数据时，预测效果会显得很差，也就是说训练精度很高，测试精度很低。

1.4.2交叉验证法

当样本足够多时，可以将数据分成三份

• 训练集：估计模型的参数
• 校验集：估计模型的预测误差(Validation set is like your test set. You use it to select your algorithm or model.)
• 测试集：被测试(Test data is your future data. Put it away as far as possible don’t look at it.)

但通常没有足够多样本，而且也很难说明多少足够数据是足够的（依赖于基础数据的信噪比和模型的复杂程度）

K-fold cross validation

交叉验证的基本思想：把在某种意义下将原始数据(dataset)进行分组,一部分做为训练集(train set),另一部分做为验证集(validation set or test set),首先用训练集对模型进行训练,再利用验证集来测试模型的泛化误差。另外，现实中数据总是有限的，为了对数据形成重用，从而提出k-折叠交叉验证。

交叉验证的目的：在实际训练中，模型通常对训练数据好，但是对训练数据之外的数据拟合程度差。用于评价模型的泛化能力，从而进行模型选择。

1）.首先将数据集划分成k份，通常是平均分成k份，彼此不交叉