【机器学习 吴恩达】CS229课程笔记notes4翻译-Part VI学习理论

CS229课程笔记 吴恩达

Part VI 学习理论 1 偏差/方差权衡 当我们谈论线性回归,我们讨论它是否拟合一个简单的模型,比如线性模型“y=θ0+θ1x”,或者更复杂的模型,比如多项式模型“y=θ0+θ1x+θ2x2+θ3x3+θ4x4+θ5x5”。见下例。

拟合一个5阶的多项式(最右图)不会得到一个好的模型,即使5阶的多项式由训练集中的x(即,居住面积)到y(即,房屋价格)预测的很好,我们也不认为当房屋价格不在训练集中时,它会预测的很好。换句话说,训练集中学习到的东西对其他房屋并不具有一般化。对于训练集中的样本,假设的泛化误差是我们不想要的误差。 上面的最左图和最右图都有很大的泛化误差,然而,两个模型非常不同。如果y和x之间的关系不是线性的,即使我们对一个非常大的训练数据拟合了一个线性模型,这个线性模型仍然不能准确地捕获数据中的结构。非正式地,我们定义一个模型的偏差bias为泛化误差,即使我们使用的是一个非常大的(或者无限大的)训练集来拟合。因此,对于上面的问题,线性模型有一个很大的偏差,导致对数据的欠拟合。 除了偏差,泛化误差有第二个组件,即模型拟合过程的方差。特别地,在最右图中拟合一个5阶的多项式时,有很大可能是因为我们是在一个小的有限的训练集上拟合数据,并不反映x和y之间的广泛关系,这可能是因为训练集中的数据可能碰巧比平均值稍贵,或者碰巧比平均值稍便宜。通过拟合这些训练集中不合理的模式,我们又会获得一个具有较大泛化误差的模型,我们说这时的模型拥有大的方差。 通常,偏差和方差之间有一个权衡。如果我们的模型太简单,有很少的参数,它可能有大的偏差(但是小的方差),如果模型太复杂,有很多参数,它可能有大的方差(但是小的偏差)。在上面的例子中,拟合一个二次函数比1阶或5阶多项式更好。

2 准备工作 在这份笔记中,我们从学习理论开始。我们将寻求一些问题的答案:首先,我们会做出正式的偏差/方差权衡吗?我们将讨论模型的选择方法,自动地决定用几阶多项式拟合一个训练集。第二,在机器学习中我们关心泛化误差,但绝大多数学习算法都能够将模型拟合到训练集。我们应该将训练集上的误差与泛化误差相关吗?最后,在哪些条件下我们可以证明学习算法工作的很好? 我们用两个简单但非常有用的引理开始。 引理1(联合边界引理)让A1,A2,…,Ak是k个不同的事件(可能不独立)。那么

P(A1∪···∪Ak)≤P(A1)+···P(Ak)

在概率论中,联合边界引理通常认为是一个公理(不需要证明),但我们也有直观的感觉:k个事件中的任何一个发生的概率最多是k个不同事件的概率和。 引理2(霍芬不等式)让Z1,…,Zm是m个独立且独立同分布的随机变量,服从伯努利分布。例如,P(Zi=1)=φ,P(Zi=0)=1-φ。让

为这些随机变量的平均值,让任何γ>0为固定值。然后,

该引理(在学习理论中叫做霍芬不等式)表明,如果我们取为m个伯努利随机变量的平均值——是我们对φ的估计,那么我们离开真值的概率很小,只要m很大。其他方式,如果你有一个有偏差的硬币,落在你头上的机会为φ,如果你投掷硬币m次,计算它落在头上的次数,这很大程度上将是φ的一个很好的估计(如果m很大)。 使用这两个引理,我们将能够证明一些学习理论中最深的和最重要的结果。 为了简化我们的阐述,让我们将我们的注意力集中到二值分类问题上,标签是y∈{0,1}。我们这里将说的一切都具有一般意义,包括回归和多类别分类问题。 我们假定给定大小为m的训练集S={(x(i),y(i));i=1,…,m},训练样本(x(i),y(i))服从概率分布D。对于假设h,我们定义训练误差(也叫做学习理论中的经验风险或经验误差)为

这只是h个误分类训练样本中的一部分。当我们想要在训练集S上做出明确的依赖

,我们可以写为

。我们定义泛化误差为

例如,如果我们从分布D得到一个新的样本(x,y),ε(h)是h对该样本误分类的概率。 注意,我们假定训练数据服从相同的分布D,我们将评估我们的假设(泛化误差的定义中)。这有时也指的是PAC假设中的一个。 考虑线性分类的环境,让hθ(x)=1{θTx≥0}。拟合参数θ的合理方式是什么?一种方法是试图最小化训练误差,挑选

我们叫这个过程为经验风险最小化(ERM),通过学习算法得到的假设输出为

。我们认为ERM是最基本的学习算法,它将是我们在这些笔记中关注的算法。(如logistic回归这样的算法也可以被看作经验风险最小化的近似。) 在我们对学习理论的研究中,从特定的假设参数和是否我们正在使用一个线性分类器的问题中抽象出经验风险最小化。我们定义假设类H,用于学习算法,作为它考虑的所有分类器的集合。对于线性分类器,H={hθ:hθ(x)=1{θTx≥0},θ∈Rn+1}因此是X(输入域)上所有分类器的集合,其中决策边界是线性的。更广泛的,如果我们正在学习神经网络,那么我们能够让H为所有分类器的集合,由某个神经网络体系结构代表。 经验风险最小化被认为是函数H的类的最小值,其中学习算法为如下假设:

3 有限的H的情形 我们开始考虑一种学习算法,我们有一个有限的假设类H={h1,…,hk},包括k各假设。因此,H仅仅是k个函数的集合,从X映射到{0,1},经验风险最小化选择为这k个函数无论哪个有最小的训练误差。 我们想要给出泛化误差h的保证。我们的策略包括两部分:首先,

是所有h的可靠估计。第二,这意味着泛化误差的上界。 取任一固定的hi∈H,考虑伯努利随机变量Z,其分布定义如下。样本(x,y)服从分布D。然后,我们设置Z=1{hi(x)≠y},让Z表示hi是否误分类。简单地,我们也定义Zj=1{hi(x(j)≠y(j)}。由于我们的训练集服从D分布,Z和Zj有相同的分布。 我们看到误分类概率ε(h)是Z(和Zj)的期望值。此外,训练误差写为

因此,

是m个随机变量Zj的平均值,服从伯努利分布,平均值为ε(hi)。因此,我们应用霍芬不等式,获得

这显示,对于我们特殊的hi,训练误差在很高的概率下接近泛化误差,假定m很大。但是对于一个特定的hi,我们不仅仅想要保证ε(hi)以很高的概率靠近

。我们想要证明对于所有的h∈H,这都是正确的。让Ai代表事件

。我们已经展示,对于任何特殊的Ai,P(Ai)≤2exp(-2γ2m)都是正确的。因此,使用联合边界,我们有

如果我们从1提取两边,我们发现

(符号

代表“非”)因此,概率至少为1-2k exp(-2γ2m),对于所有的h∈H,ε(h)将在

的γ中。这叫做一致收敛结果,对于所有的h∈H,这是一个共同的边界。 在上面的讨论中,对于特殊值m和γ,依概率给定一个边界,对于某个h∈H,

这里存在三个感兴趣的量:m,γ和概率误差;我们可以依据其中一个得到另外两个。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券