西瓜书概念

第12章 计算学习理论

  • Page267: 计算学习理论(computational learning theory)

    计算学习理论研究的是关于通过“计算”来进行“学习”的理论,即关于机器学习的理论基础,其目的是分析学习任务的困难本质,为学习算法提供理论保证,并根据分析结果指导算法设计。

  • Page268: Jensen不等式

    期望的函数小于函数的期望

  • Page268: Hoeffding不等式

    个独立随机变量,且满足,则对于任意有:

  • Page268: McDiarmid 不等式

    个独立随机变量,且对任意,函数满足

则对任意{% math %}\epsilon\geqq 0{% endmath %},有
{% math %}P(f(x_1,...,x_m)-E(f(x_1,...,x_m))\geqq \epsilon)\leqq exp(\frac{-2\epsilon^2}{\sum_i c_i^2}){% endmath %}
{% math %}P(\mid f(x_1,...,x_m)-E(f(x_1,...,x_m))\mid \geqq \epsilon)\leqq exp(\frac{-2\epsilon^2}{\sum_i c_i^2}){% endmath %}
  • Page268: 概率近似正确
  • Page268: 概念类(concept class)

    令c表示概念,这是从样本空间到标记空间的映射,它决定示例x的真实标记y,若对任何样例(x,y)有c(x)=y成立,则称c为目标概念,所有我们希望学得的目标概念所构成的集合称为概念类,用符号表示。

  • Page268: 假设空间(hypothesis space)

给定学习算法,它所考虑的所有可能概念的集合称为“假设空间”,用符号表示。由于学习算法事先并不知道概念类的真实存在,因此假设空间和概念类往往不同。

  • Page269: PAC辨识(PAC Identify)

    对于,所有和分布,若存在学习算法,其输出假设满足

    则称学习算法能从假设空间中PAC辨识概念类,这样的学习算法能从假设空间中PAC辨识概念类.

  • Page269: PAC可学习(PAC Learnable)

    表示从分布中独立同分布采样得到的样例数目,,对所有分布,若存在学习算法和多项式函数,使得对于任何, 能从假设空间中PAC辨识概念类,则称概念类对假设空间而言是PAC可学习的,也简称概念类是PAC可学习的。对于计算机算法来说,必须考虑时间复杂度,于是:

  • Page270: PAC学习算法(PAC Learning Algorithm)

    若学习算法使概念类为PAC可学习的,且的运行时间也是多项式函数,则称概念类是高效PAC可学习的,称为概念类的PAC学习算法。

  • Page269: 时间复杂度

    假定学习算法处理每个样本的时间为常数,则的时间复杂度等价于样本复杂度。

  • Page270: 样本复杂度

    满足PAC学习算法所需的中最小的m,称为学习算法的样本复杂度。

  • Page269: 不可分(272)(non-seperable)

    对于较为困难的学习问题,目标概念往往不存在于假设空间中,假定对于任何,也就是说,中的任意一个假设都会在训练集上出现或多或少的错误。中不存在任何假设能将所有示例完全正确分开,则称该问题对于学习算法是不可分的,亦称不一致的。

  • Page269: 不一致(non-consistent)

    即不可分。

  • Page269: 可分(270)(seperable)

    可分情形意味着目标概念属于假设空间, 即 中存在假设能将所有示例按与真实标记一致的方式完全分开,我们将该问题对学习算法是可分的,亦称一致的。

  • Page270: 恰PAC可学习(properly PAC learnable)

    若学习算法使概念类为PAC可学习的,且的运行时间也是多项式函数,则称概念类是高效PAC可学习的,称为概念类的PAC学习算法。若在PAC学习中假设空间与概念类完全相同,称为恰PAC可学习,这意味着学习算法的能力与学习任务恰好匹配。

  • Page270: 有限假设空间

    一般而言,越大,其包含任意目标概念的可能性越大,但从中找到某个具体概念的难度也越大,有限时,我们称为有限假设空间,否则称为“无限假设空间”。

  • Page273: 不可知PAC可学习(agnostic PAC learnable)

    表示从分布中独立同分布采样得到的样例数目,,对所有分布,若存在学习算法和多项式函数,使得对于任何能从假设空间中输出满足的假设h,则称假设空间是不可知PAC可学习的。

  • Page273: 增长函数

    给定假设空间和示例集中每个假设h都能对中示例赋予标记,标记结果可表示为

    随着m的增大,中所有假设对D中的示例所能赋予标记的可能结果数也会增大。

    对所有,假设空间的增长函数,表示假设空间对m个示例所能赋予标记的最大可能结果数,可能结果数越大,假设空间的表示能力越强,对学习任务的适应能力也越强,可以利用增长函数来估计经验误差与泛化误差之间的关系。

  • Page273: 对分

    假设空间中不同的假设对于中示例赋予标记的结果可能相同,也可能不同;尽管可能包含无穷多个假设,但其对中示例赋予标记的可能结果是有限的。对m个示例,最多有个可能结果,对二分类问题来说,中的假设对中示例赋予标记的每种可能结果称为对的一种对分。

  • Page273: 打散

    若假设空间能实现示例集上的所有对分,即,则称示例集能被假设空间打散。

  • Page273: VC维(274)

    假设空间的VC维是能被打散的最大示例集的大小,即,可用于度量假设空间的复杂度。

  • Page278: 经验风险最小化(Empirical Risk Minimization, ERM)

    令h表示学习算法输出的假设,若满足,则称为满足经验风险最小化原则的算法。

  • Page279: Rademacher复杂度

    经验误差最小的假设是

    ,然而现实任务中的标记y有时候会收到噪声影响,不再是真实标记,再此情形下,选择假设空间中在训练集上表现最好的假设,有时还不如选择中事先考虑了随机噪声影响的假设。考虑随机变量,它以0.5的概率取值-1,0.5的概率取值+1,称为Rademacher随机变量,基于可将上式改写为,期望为,考虑实值函数空间,令,其中替换成可得,函数空间g关于的经验Rademacher复杂度

    ,其衡量了函数空间与随机噪声在集合中的相关性。对所有从独立同分布采样而得的大小为m的集合Z求期望可得函数空间关于上分布的Rademacher复杂度。

  • Page284: 稳定性

    算法在输入发生变化时,输出是否会随之发生较大的变化。

  • Page285: 均匀稳定性

    对任何,若学习算法满足

    ,则称关于损失函数满足均匀稳定性。

    其中l为泛化损失,为移除中第i个样例得到的集合。

results matching ""

    No results matching ""