Note of PRML(1)

The background of machine learning

Posted by GwanSiu on September 1, 2017

1. Introduction

PMRL第一章简单讲述了三方面的知识:(1).Machine Learning的基本知识,包括基本名词定义,模型选择以及维度灾难;(2).贝叶斯理论和决策理论;(3).信息理论与Machine Learning的联系。
在本篇博文中,博主将结合自己所学,将书本的知识进行扩展,从而形成这一章note,希望对以后的机器学习学习者有所帮助。注意:本篇博文中,不涉及概率基础以及决策理论,基础感到困难的朋友可以先去补充概率基础,这将对机器学习的学习大有裨益。

2. The Background of Machine Learning

2.1 The definition of machine Learning

机器学习方法是计算机利用已有的经验(观测数据),解算出某个模型(规律),并利用该模型来预测未来的一种方法。该定义出发点是让计算机模拟人脑的学习过程,将观察的经验归纳总结出某种规律,并利用该规律观察自然,并改造自然。

从统计层面上理解,机器学习的过程就是数据拟合的过程,是用观察到的数据(已知),去求解产生该数据的分布的过程。已知数据$X=(x_{1},…,x_{n})$是由一个underlying function $f(x)$产生,$f(x)$是未知的,我们便利用数学上的逼近原理,构造一个$g(x;\Theta)$函数,其参数为$\Theta=(\theta_{1},…,\theta_{n})$,希望找到最优的一个$g(x;\Theta^{*})$跟$f(x)$越想近越好。即:$\text{min}_{\Theta}\lVert g(x;\Theta)-f(x)\rVert^{2}$。

从贝叶斯分析的角度出发:

其中,$P(X\arrowvert \Theta)$是后验概率(posterior), 物理意义:Underlying function $f(x)$产生观测数据$X=(x_{1},…,x_{n})$; $P(X)$是先验(Prior),它代表我们对样本的认知,先验知识;$P(\Theta\arrowvert X)$是似然(likelyhood),从数据$X=(x_{1},…,x_{n})$推理(inference)参数为$\Theta=(\theta_{1},…,\theta_{n})$,它代表$P(\Theta\arrowvert X)$与真实$P(X\arrowvert \Theta)$的相似度,如字面意思:似然。

PRML这一本书,则是从贝叶斯理论的框架下讨论一些列的机器学习问题。

2.2 The Type of Machine Learning

    1. 从输出空间$y$的类型上分类(即:任务分类):
      若$y$是离散空间(Discrete Set),则该任务为分类(Classification)
      若$y$是连续空间(Continuous Set),则该任务为回归(Regresssion)
    1. 从学习的目的上分类: 监督式学习(Supervised Learning): 有标签式学习,数据与标签成对$(x_{n},y_{n})$存在。 非监督式学习(Unsupervised Learning):无标签式学习,只有数据$X=(x_{1},…,x_{n})$,无监督式学习的目的是将相似的数据聚类(Cluster), 本质上是学习潜在的概率分布(dense estimation)。
      半监督式学习(Semi-supervised Learning):有标签的数据和无标签的数据都有,利用有标签数据辅助学习,从而学到无标签数据潜在的概率分布。
      强化学习(Reinforcement Learning):给定已知情景做决策,所做的决策是将最后得到的奖励(TReward)最大化(需要博弈论知识)。奖励(Reward)应该合理地赋予给每一个操作。强化学习的特点是在找寻exploration和exploitation的trade-off,其中exploration是系统进行新动作并查看该动作的影响,exploitation是充分利用已知动作获得最高的奖励。 在线学习(Online Learning):Sequential data(序列化数据),将过去的训练模型当做先验,在线观察新数据为后验,更新参数模型。(类似与环境交互的过程)

2.3 The Feasibility of Machine Learning

为什么机器能够学习?当时台湾大学林轩田教授曾用了好几节课去论证这个问题,感兴趣的同学可以去Cousera看看林轩田教授的机器学习基石。在本博文中,我便简明扼做一些重点的摘要。

    1. 机器学习要解决的根本问题
      • 机器学习的必要不充分条件:在训练集的数据和测试集的数据需来源同一分布或者两个相近的分布的前提下,且要做到以下两点:
      • (1) 保证训练误差$E_{train}$很小(训练过程)。
      • (2) 使得测试误差要逼近训练误差的值$E_{test}\approx E_{train}$(测试过程,保证了模型的泛化能力),这样就保证了测试误差也很小。

上面讲到,机器学习是一个数据拟合,发觉数据真实分布的过程。由贝叶斯分析可知:$P(X\arrowvert \Theta)\propto P(X)P(\Theta\arrowvert X)$,训练的过程便是根据训练数据,最大化似然概率$P(\Theta\arrowvert X)$。不同的$\theta_{i}$对应不同的似然概率$P(\theta_{i}\arrowvert X)$,因此,训练过程便是在$P(\Theta\arrowvert X)$函数空间中找到一个函数$P(\theta_{i}\arrowvert X)$与真实分布$P(X\arrowvert \Theta)$最相近,即:使得训练误差最小,$E_{train}\downarrow$。

如何保证$E_{test}\approx E_{train}$?这要涉及到VC-dimension的理论,这里直接抛出结论,具体推导亦在机器学习基石课程中有:

其中,$E_{test}$是测试误差,$E_{train}$是训练误差,$N$为样本数目,$\delta$是置信度,$d_{vc}$是vc维度,物理意义是模型的复杂度。

由(3)式可知,训练误差和测试误差之间在理论上存在一个gap:model penalty, $\Omega(N,H,\delta)$。

VC维度的讨论

  1. 当数据样本$N$一定时,若d_{vc}(H) 很高,说明学习到的模型复杂度高,这会导致$E_{train}$很小,但$\Omega(N,H,\delta)$很大便导致$E_{test} < E_{train}$, 条件(2)不能满足。这属于过拟合现象。从上式可知解决过拟合现象有两种方法,一是增大样本量$N$,二是减少vc维度,$d_{vc}$,即:Regulization.

  2. 当数据样本$N$一定时,若d_{vc}(H)很小,说明学习到的模型复杂度低,这会使得$E_{train}$很高,即使条件(2)可以满足:$E_{test}\approx E_{train}$,但$E_{test}$很大,学习效果很差。这属于欠拟合现象,解决方法是增大vc维度。

可见,当样本数量$N$一定时,d_{vc}(H)过大会造成模型过拟合,d_{vc}(H)太小会造成模型欠拟合。这说明,机器学习的训练过程是一个VC维度trade-off的过程。一般,validation set便是用来调整模型之用。

过拟合是由于模型的VC维度太高造成的,通过直接减少模型参数数量可以有效降低VC维度,但这样做会导致模型不够灵活捕捉到高维度的信息。因此,通过会使用regularization的方法,进行weight decay从而降低VC维度。

从bias和variance讨论欠拟合和过拟合

我们通过构建参数模型$g(x,w)$对真实的分布 $f(x)$ 进行逼近,由于对参数$w$,我们通常采用的是点估计,因此数据量的大小便会影响对参数$w$估计的准确度,当数据量N无穷大时,参数模型$g(x,w)$可以无限逼近真实分布 $f(x)$。但实际情况,我们拥有的数据量是有限的,我们所构建的参数模型$g(x,w)$并不完全等于$h(x)$。

从贝叶斯分析的角度上理解,参数模型$y(x,w)$的不确定性是由后验概率中参数$w$所确定的。因为$w$是由于数据集 $X$ 进行点估计,因此数据集 $X$ 的不同会造成参数$w$的不同,因此会造成不同square loss:

基本思想:通过least square error, 将$E_{test}$分解成bias和covariance。

其中, $\text{bias(x)}=E_{x}[(\hat{g}^{D}(x)-f(x))^{2}]$,
$\text{Var(x)}=E_{D}[g^{D}(x)^{2}]-\hat{g}^{D}(x)^{2}$.

其中$\text{bias(x)}$指的是函数空间均值点距离$f(x)$的远近,而$\text{Var(x)}$指的是函数空间的离散程度。如下图所示:

bias很大,说明所构造的函数空间的均值点$E[g^{D}(x)]$离&f(x)$距离远,模型因此欠拟合;Variance很大,说明所构造的函数空间虽然包含$f(x)$,但是空间很大,离散程度高,模型容易过拟合。