斯坦福统计学习理论笔记:Percy Liang带你搞定「贼难」的理论基础

CS229T/STAT231 是由斯坦福大学开设的统计学习理论课程,着重于对机器学习算法统计特性的理论理解,涉及机器学习算法何时起作用和原因、如何形式化算法从数据中学习的含义、如何使用数学思维来设计更好的机器学习方法等基本课题。今天要介绍由斯坦福大学计算机系教授 Percy Liang 近期公布的 CS229T/STAT231 的学习笔记。

笔记地址:https://github.com/percyliang/cs229t/blob/master/lectures/notes.pdf

课程 topic

  • 一致收敛(VC 维度,Rademacher 复杂性等)

  • 隐式/算法正则化神经网络的泛化理论

  • 内核方法

  • 在线学习和 bandits 问题

  • 监督学习:指数族,矩方法,GAN 的统计理论

预备知识

  • 熟悉线性代数、实分析、概率论和进行数学证明的基本能力

  • 机器学习(CS229)或统计学(STATS315A)

  • 推荐学习凸优化(EE364A)

笔记目录

1 课程概述

1.1 这门课程是关于什么的?

机器学习已成为许多应用领域中不可或缺的一部分,包括科学(生物学、神经科学、心理学、天文学等)和工程学(自然语言处理计算机视觉机器人学等)。但机器学习不是一种单一的方法;相反,它包含一系列看似完全不同的框架和范例,包括分类、回归、聚类、矩阵分解贝叶斯网络马尔可夫随机场等。本课程旨在揭示这些不同技术背后的共同统计学原理。

本课程是关于学习算法的理论分析。课程中介绍的许多分析技术(包括概率、线性代数和最优化的完美结合)值得研究,并且在机器学习之外也是有用的。

更深入的理论理解可以提供新的视角,并且可以帮助对现有算法进行修改和优化,也有助于提出新的算法。如果没有理论提供的概念性分析,这些新算法可能很难发现。

理论依赖的假设可能同时太强(例如,数据服从独立同分布条件)又太弱(例如,任何分布)。实际上,理论的目的不是为了简化成只需插入数字的公式。相反,理论应该改变思维方式。

本课程分为四个部分:渐近性、一致性收敛、核方法和在线学习。我们将从非常强的假设(假设数据是高斯的、渐近的)转变为非常弱的假设(假设数据可以对抗地在在线学习中生成)。在这方面,核方法有点不同;它更重要的在于提供表达能力,而不是统计学习。

1.2 渐近

给定基于一些未知参数向量θ*提取的数据,我们从数据中计算出θ hat,θ hat 和θ*有多接近?

对于简单的模型例如高斯均值估计和固定设计的线性回归,我们可以求出θ hat -θ*的闭式解。

对于大多数模型,例如 logistic 回归,我们不能这样做。但我们可以使用统计学中的常用工具即渐近分析。其基本思想是做泰勒级数展开以得到渐近正态性:即,sqrt(n)*(θ^−θ*) 的分布随着样本数量 n 的增加逼近于高斯分布。渐近的意义是即使θ hat 很复杂,我们也可以得到简单的结果。

我们的大多数分析都将使用最大似然估计,这种估计具有很好的统计特性(它们具有所有估计量中最小的渐近方差)。但是对于大多数隐变量模型而言,最大似然在计算上很困难,并且需要进行非凸优化。这些优化问题通常由 EM 算法解决,只能保证收敛到局部最优。我们将展示矩方法(一种可以追溯到 Pearson(1894)的参数估计经典方法)如何解决这个问题,得到能够产生全局最优解的有效算法(Anandkumar et al.,2012b)。

图 1:在渐近分析中,我们研究当一个参数估计θ hat 接近真实参数θ*时,θ hat 的行为。

1.3 一致性收敛

渐进线提供了一个很好的初值分析,并且适用于许多场景。但它有两个主要的缺点:它需要目标函数是平滑的;在渐进线开始逼近前无法确定要选择多大的样本数量 n。

一致性收敛提供了另一种视角,若考虑一个标准的监督学习问题:给定训练集 (x, y),学习算法会从所有假设 H 中选择一个最优的预测器 h : X → Y,然后我们在测试数据评估该预测器。现在有一个简单的问题:训练误差 Lˆ(h) 和测试误差 L(h) 之间的关系是什么样的?

图 2:我们希望最小化期望风险 L 以获得最优的 h*,但是我们实际上只能最小化经验风险 L ^以获得 h^。

对于固定的 h ∈ H,训练误差 Lˆ(h) 为独立同分布随机变量(每一个样本的损失)的均值,它将收敛到测试误差 L(h),且收敛率由 Hoeffding 不等式或中心极限定理决定。

但问题是我们假设基于训练数据选择一个最佳的假设,并不是使用固定的 h。具体而言,如果考虑经验风险最小化(ERM),我们需要最小化训练误差,从而获得最优的经验预测器:

直观而言,训练误差应该比测试误差小,因此可靠性也低一些。我们可以使用一致性收敛将这一直观理解形式化为:

这些泛化边界在某种意义上是统计学习理论的核心。但是在这个过程中,我们可以发展出广泛有用的不等式,它的应用范围甚至超越了机器学习

1.4 核方法

现在我们先绕过学习算法的误差分析,并考虑我们到底应该学习什么样的模型。现实数据非常复杂,所以我们需要极具表达能力的模型。核方法提供了一种严格的数学框架,它可以构建复杂、非线性的模型,而且还只需要基于线性模型的机制。

核方法提供了另一种方法定义函数。我们一般定义一个半正定的核函数 k(x, x' ),它将捕捉 x 和 x'之间的相似性,并通过对比一组样本而定义整个函数:

核方法允许我们构建复杂的非线性函数,例如高斯核函数和径向基核函数等。它们是通用的方法,且能逼近任意连续的函数。而对于序列、树型及图等数据结构,我们可以定义核函数以利用动态规划实现高效计算。

最后,核方法都是在函数层面上进行操作的,我们可以定义函数的整体空间为再生核希尔伯特空间(RKHS),它允许我们将函数视为向量并执行线性代数的计算规则。

事实证明,所有这三个概念都在描述相同的东西,它们之间相互有联系:

图 3:核方法中的三个关键数学概念。

1.5 在线学习(Lecture 1)

真实世界是动态的,使用基于渐近和一致性收敛的早期分析会错失某些重要性质。在线学习试图以两种方式解决这个问题:

目前为止,为了分析一个学习算法的误差,我们必须假设训练样本是独立同分布的。然而在实践中,数据点可能是互相依赖的,甚至更糟,即它们可能是对抗生成的。

此外,我们目前考虑的都是批量学习设置,即拿到一个训练集,学习一个模型,然后部署模型。但在实践中,数据可能是以流的形式存在的,此时我们需要交替学习和预测。

图 4:在线学习游戏。

入门统计学习方法算法Percy Liang课程斯坦福大学
7
相关数据
动态规划技术

动态规划(也称为动态优化),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题,只解决一次子问题并存储它的解决方案(solution),下一次遇到同样的子问题时无需重新计算它的解决方案,而是简单地查找先前计算的解决方案,从而节省计算时间。动态规划适用于有最优子结构(Optimal Substructure)和重叠子问题(Overlapping Subproblems)性质的问题。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

高斯分布技术

正态分布是一个非常常见的连续概率分布。由于中心极限定理(Central Limit Theorem)的广泛应用,正态分布在统计学上非常重要。中心极限定理表明,由一组独立同分布,并且具有有限的数学期望和方差的随机变量X1,X2,X3,...Xn构成的平均随机变量Y近似的服从正态分布当n趋近于无穷。另外众多物理计量是由许多独立随机过程的和构成,因而往往也具有正态分布。

核函数技术

核函数包括线性核函数、多项式核函数、高斯核函数等,其中高斯核函数最常用,可以将数据映射到无穷维,也叫做径向基函数(Radial Basis Function 简称 RBF),是某种沿径向对称的标量函数。最常应用于SVM支持向量机中

神经科学技术

神经科学,又称神经生物学,是专门研究神经系统的结构、功能、发育、演化、遗传学、生物化学、生理学、药理学及病理学的一门科学。对行为及学习的研究都是神经科学的分支。 对人脑研究是个跨领域的范畴,当中涉及分子层面、细胞层面、神经小组、大型神经系统,如视觉神经系统、脑干、脑皮层。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

最大似然估计技术

极大似然估计是统计学中用来估计概率模型参数的一种方法

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

计算机视觉技术

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

机器人技术技术

机器人学(Robotics)研究的是「机器人的设计、制造、运作和应用,以及控制它们的计算机系统、传感反馈和信息处理」 [25] 。 机器人可以分成两大类:固定机器人和移动机器人。固定机器人通常被用于工业生产(比如用于装配线)。常见的移动机器人应用有货运机器人、空中机器人和自动载具。机器人需要不同部件和系统的协作才能实现最优的作业。其中在硬件上包含传感器、反应器和控制器;另外还有能够实现感知能力的软件,比如定位、地图测绘和目标识别。之前章节中提及的技术都可以在机器人上得到应用和集成,这也是人工智能领域最早的终极目标之一。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

线性回归技术

在现实世界中,存在着大量这样的情况:两个变量例如X和Y有一些依赖关系。由X可以部分地决定Y的值,但这种决定往往不很确切。常常用来说明这种依赖关系的最简单、直观的例子是体重与身高,用Y表示他的体重。众所周知,一般说来,当X大时,Y也倾向于大,但由X不能严格地决定Y。又如,城市生活用电量Y与气温X有很大的关系。在夏天气温很高或冬天气温很低时,由于室内空调、冰箱等家用电器的使用,可能用电就高,相反,在春秋季节气温不高也不低,用电量就可能少。但我们不能由气温X准确地决定用电量Y。类似的例子还很多,变量之间的这种关系称为“相关关系”,回归模型就是研究相关关系的一个有力工具。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

中心极限定理技术

中心极限定理是概率论中的一组定理。中心极限定理说明,在适当的条件下,大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布。这组定理是数理统计学和误差分析的理论基础,指出了大量随机变量之和近似服从正态分布的条件。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

马尔可夫随机场技术

具有马尔可夫性质的随机场。 随机场:当给每一个位置(site)按照某种分布随机赋予相空间(phase space)的一个值之后,其全体就叫做随机场

独立同分布技术

在概率论与统计学中,独立同分布(缩写为IID)是指一组随机变量中每个变量的概率分布都相同,且这些随机变量互相独立。一组随机变量独立同分布并不意味着它们的样本空间中每个事件发生概率都相同。例如,投掷非均匀骰子得到的结果序列是独立同分布的,但掷出每个面朝上的概率并不相同。

正则化技术

当模型的复杂度增大时,训练误差会逐渐减小并趋向于0;而测试误差会先减小,达到最小值后又增大。当选择的模型复杂度过大时,过拟合现象就会发生。这样,在学习时就要防止过拟合。进行最优模型的选择,即选择复杂度适当的模型,以达到使测试误差最小的学习目的。

自然语言处理技术

自然语言处理(英语:natural language processing,缩写作 NLP)是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

线性代数技术

线性代数是数学的一个分支,它的研究对象是向量,向量空间(或称线性空间),线性变换和有限维的线性方程组。向量空间是现代数学的一个重要课题;因而,线性代数被广泛地应用于抽象代数和泛函分析中;通过解析几何,线性代数得以被具体表示。线性代数的理论已被泛化为算子理论。由于科学研究中的非线性模型通常可以被近似为线性模型,使得线性代数被广泛地应用于自然科学和社会科学中。

贝叶斯网络技术

贝叶斯网络(Bayesian network),又称信念网络或是有向无环图模型,是一种概率图型模型。例如,贝叶斯网络可以代表疾病和症状之间的概率关系。 鉴于症状,网络可用于计算各种疾病存在的概率。

再生核希尔伯特空间技术

在功能分析(数学分支)中,再生核希尔伯特空间(RKHS)是点估算是连续线性泛函的函数的希尔伯特空间。

在线学习技术

在计算机科学中,在线学习是一种机器学习方法。和立即对整个训练数据集进行学习的批处理学习技术相反,在线学习的数据按顺序可用,并在每个步骤使用未来数据更新最佳预测器。

隐变量技术

在统计学中,隐变量或潜变量指的是不可观测的随机变量。隐变量可以通过使用数学模型依据观测得的数据被推断出来。

统计学习理论技术

统计学习理论是统计学和功能分析领域的机器学习框架。统计学习理论处理基于数据建立预测函数的问题,且已经在算机视觉,语音识别,生物信息学等领域得到了成功应用。

推荐文章
暂无评论
暂无评论~