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

2018 年 12 月 18 日 机器之心
斯坦福统计学习理论笔记:Percy Liang带你搞定「贼难」的理论基础

选自 GitHub

机器之心整理

参与:刘晓坤、思源


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:在线学习游戏。



登录查看更多
20

相关内容

Percy Liang,斯坦福大学计算机科学与统计系副教授,他的研究方向是自然语言处理和统计机器学习。 个人网页:https://cs.stanford.edu/~pliang/

【导读】纽约大学开设的离散数学课程,这是一门运用于计算机科学的离散数学课程。这只是一门一学期的课程,所以有很多话题是它没有涉及到的,或者没有深入讨论。但我们希望这能给你一个技能的基础,你可以在你需要的时候建立,特别是给你一点数学的成熟——对数学是什么和数学定义和证明如何工作的基本理解。

成为VIP会员查看完整内容
0
83

计算机科学正在发展,以利用新的硬件,如GPU、TPUs、CPU和大型商品集群。许多子领域,如机器学习和优化,已经调整了它们的算法来处理这样的集群。

课程主题包括分布式和并行算法: 优化、数值线性代数、机器学习、图分析、流式算法,以及其他在商用集群中难以扩展的问题。该类将重点分析程序,并使用Apache Spark和TensorFlow实现一些程序。

本课程将分为两部分: 首先,介绍并行算法的基础知识和在单多核机器上的运行时分析。其次,我们将介绍在集群机器上运行的分布式算法。

地址: http://stanford.edu/~rezab/dao/

主讲:

Reza Zadeh是斯坦福大学计算与数学工程学院的客座教授,同时也是Matroid公司的CEO。他的主要工作集中于机器学习理论与应用,分布式计算,以及离散数学。

http://stanford.edu/~rezab/

课程目录:

成为VIP会员查看完整内容
0
81

课程内容:

  • 数学基础:矩阵、向量、Lp范数、范数的几何、对称性、正确定性、特征分解。无约束最优化,graident下降法,凸函数,拉格朗日乘子,线性最小二乘法。概率空间,随机变量,联合分布,多维高斯。

  • 线性分类器:线性判别分析,分离超平面,多类分类,贝叶斯决策规则,贝叶斯决策规则几何,线性回归,逻辑回归,感知机算法,支持向量机,非线性变换。

  • 鲁棒性:对抗性攻击、定向攻击和非定向攻击、最小距离攻击、最大允许攻击、基于规则的攻击。通过纳微扰。支持向量机的鲁棒性。

  • 学习理论:偏差和方差,训练和测试,泛化,PAC框架,Hoeffding不等式,VC维。

参考书籍:

  • Pattern Classification, by Duda, Hart and Stork, Wiley-Interscience; 2 edition, 2000.
  • Learning from Data, by Abu-Mostafa, Magdon-Ismail and Lin, AMLBook, 2012.
  • Elements of Statistical Learning, by Hastie, Tibshirani and Friedman, Springer, 2 edition, 2009.
  • Pattern Recognition and Machine Learning, by Bishop, Springer, 2006.

讲者: Stanley Chan 教授 https://engineering.purdue.edu/ChanGroup/stanleychan.html

课程目标: 您将能够应用基本的线性代数、概率和优化工具来解决机器学习问题

•你将了解一般监督学习方法的原理,并能评论它们的优缺点。 •你会知道处理数据不确定性的方法。 •您将能够使用学习理论的概念运行基本的诊断。 •您将获得机器学习算法编程的实际经验。

成为VIP会员查看完整内容
0
141

对因果推理的简明和自成体系的介绍,在数据科学和机器学习中越来越重要。

因果关系的数学化是一个相对较新的发展,在数据科学和机器学习中变得越来越重要。这本书提供了一个独立的和简明的介绍因果模型和如何学习他们的数据。在解释因果模型的必要性,讨论潜在的因果推论的一些原则,这本书教读者如何使用因果模型:如何计算干预分布,如何从观测推断因果模型和介入的数据,和如何利用因果思想经典的机器学习问题。所有这些主题都将首先以两个变量的形式进行讨论,然后在更一般的多元情况下进行讨论。对于因果学习来说,二元情况是一个特别困难的问题,因为经典方法中用于解决多元情况的条件独立不存在。作者认为分析因果之间的统计不对称是非常有意义的,他们报告了他们对这个问题十年来的深入研究。

本书对具有机器学习或统计学背景的读者开放,可用于研究生课程或作为研究人员的参考。文本包括可以复制和粘贴的代码片段、练习和附录,其中包括最重要的技术概念摘要。

首先,本书主要研究因果关系推理子问题,这可能被认为是最基本和最不现实的。这是一个因果问题,需要分析的系统只包含两个可观测值。在过去十年中,作者对这个问题进行了较为详细的研究。本书整理这方面的大部分工作,并试图将其嵌入到作者认为对研究因果关系推理问题的选择性至关重要的更大背景中。尽管先研究二元(bivariate)案例可能有指导意义,但按照章节顺序,也可以直接开始阅读多元(multivariate)章节;见图一。

第二,本书提出的解决方法来源于机器学习和计算统计领域的技术。作者对其中的方法如何有助于因果结构的推断更感兴趣,以及因果推理是否能告诉我们应该如何进行机器学习。事实上,如果我们不把概率分布描述的随机实验作为出发点,而是考虑分布背后的因果结构,机器学习的一些最深刻的开放性问题就能得到最好的理解。
成为VIP会员查看完整内容
0
317

本文为大家带来了一份斯坦福大学的最新课程CS234——强化学习,主讲人是斯坦福大学Emma Brunskill,她是斯坦福大学计算机科学助理教授,任职斯坦福大学人类影响力实验室、斯坦福人工智能实验室以及统计机器学习小组,主要研究强化学习。要实现人工智能的梦想和影响,需要能够学会做出正确决策的自主系统。强化学习是这样做的一个强有力的范例,它与大量的任务相关,包括机器人、游戏、消费者建模和医疗保健。本课程通过讲课、书面作业和编码作业的结合,学生将精通强化学习的关键思想和技术。

1.课程介绍(Description)

要实现人工智能的梦想和影响,需要能够学会做出正确决策的自主系统。强化学习是这样做的一个强有力的范例,它与大量的任务相关,包括机器人、游戏、消费者建模和医疗保健。本课程将为强化学习领域提供扎实的介绍,学生将学习包括通用化和探索在内的核心挑战和方法。通过讲课、书面作业和编码作业的结合,学生将精通强化学习的关键思想和技术。作业将包括强化学习和深度强化学习的基础,这是一个极有前途的新领域,将深度学习技术与强化学习相结合。此外,学生将通过期末专题来增进对强化学习领域的理解。

课程地址:

https://web.stanford.edu/class/cs234/schedule.html

2.预备知识(Prerequisites)

1)熟练Python

所有的课程都将使用Python(使用numpy和Tensorflow,也可以使用Keras)。这里有一个针对那些不太熟悉Python的人的教程。如果你有很多使用不同语言(如C/ c++ / Matlab/ Javascript)的编程经验,可能会很好。

2)大学微积分,线性代数(如 MATH 51, CME 100)

你应该能够熟练地进行(多变量)求导,理解矩阵/向量符号和运算。

3)基本概率及统计(例如CS 109 或同等课程)

你应该了解基本的概率,高斯分布,均值,标准差等。

4)机器学习基础

我们将阐述成本函数,求导数,用梯度下降法进行优化。CS 221或CS 229均可涵盖此背景。使用一些凸优化知识,一些优化技巧将更加直观。

3.主讲:Emma Brunskill

Emma Brunskill是斯坦福大学计算机科学助理教授,任职斯坦福大学人类影响力实验室、斯坦福人工智能实验室以及统计机器学习小组。

主要研究强化学习系统,以帮助人们更好地生活。并处理一些关键技术。最近的研究重点包括:1)有效强化学习的基础。一个关键的挑战是要了解代理商如何平衡勘探与开发之间的局限性。2)如果要进行顺序决策,该怎么办。利用巨大数量的数据来改善在医疗保健,教育,维护和许多其他应用程序中做出的决策,这是一个巨大的机会。这样做需要假设/反事实推理,以便在做出不同决定时对潜在结果进行推理。3)人在回路系统。人工智能具有极大地扩大人类智能和效率的潜力。我们正在开发一个系统,用其他众包商(CHI 2016)生产的(机器)固化材料对众包商进行训练,并确定何时扩展系统规格以包括新内容(AAAI 2017)或传感器。我们也有兴趣研究确保机器学习系统在人类用户的意图方面表现良好(Arxiv 2017),也被称为安全和公平的机器学习。

个人主页:https://cs.stanford.edu/people/ebrun/

4.课程安排

01: 强化学习导论(Introduction to Reinforcement Learning)

02: 表格MDP规划(Tabular MDP planning)

03: 表格RL政策评估(Tabular RL policy evaluation)

04: Q-learning

05: 带函数逼近的强化学习(RL with function approximation)

06: 带函数逼近的强化学习(RL with function approximation)

07: 带函数逼近的强化学习(RL with function approximation)

08: 从马尔可夫决策过程到强化学习(Policy search)

09: 从马尔可夫决策过程到强化学习(Policy search)

10: 课堂中期(In-class Midterm)

11: 模仿学习/探索(Imitation learning/Exploration)

12: 探索/开发(Exploration/Exploitation)

13: 探索/开发(Exploration/Exploitation)

14: 批处理强化学习(Batch Reinforcement Learning)

15: 嘉宾讲座:Craig Boutilier(Guest Lecture: Craig Boutilier)

16: 课堂测验(In-class Quiz)

17: 蒙特卡洛树搜索算法(Monte Carlo Tree Search)

18: 墙报展示(Poster presentations)

成为VIP会员查看完整内容
0
61

课程名称: Artificial Intelligence: Principles and Techniques

课程简介:

网络搜索、语音识别、人脸识别、机器翻译、自动驾驶和自动调度有什么共同之处?这些都是复杂的现实世界问题,而人工智能(AI)的目标就是用严格的数学工具来解决这些问题。在本课程中,您将学习驱动这些应用程序的基本原则,并练习实现其中一些系统。具体的主题包括机器学习、搜索、马尔科夫决策过程、约束满足、图形模型和逻辑。这门课程的主要目标是让你具备解决生活中可能遇到的新人工智能问题的工具。

课程部分大纲:

  • 课程简介
  • 机器学习
    • 线性分类
    • 损失最小化
    • 随机梯度下降法
    • 章节:优化,概率,Python(综述)
    • 特性和非线性
    • 神经网络,最近邻
  • 搜索
  • 马尔可夫决策过程
    • 政策评估,政策改进
    • 策略迭代,值迭代
    • 强化学习
  • 博弈
  • 约束满足问题(Dorsa, Reid)
  • 贝叶斯网络
  • 逻辑
  • 结论

讲师介绍:

Percy Liang,斯坦福大学计算机科学与统计系副教授,他的研究方向是自然语言处理和统计机器学习。 个人网页:https://cs.stanford.edu/~pliang/

成为VIP会员查看完整内容
0
23
小贴士
相关论文
A Review on Generative Adversarial Networks: Algorithms, Theory, and Applications
Jie Gui,Zhenan Sun,Yonggang Wen,Dacheng Tao,Jieping Ye
43+阅读 · 2020年1月20日
Bernhard Schölkopf
10+阅读 · 2019年11月24日
Keyphrase Generation for Scientific Articles using GANs
Avinash Swaminathan,Raj Kuwar Gupta,Haimin Zhang,Debanjan Mahata,Rakesh Gosangi,Rajiv Ratn Shah
7+阅读 · 2019年9月24日
gym-gazebo2, a toolkit for reinforcement learning using ROS 2 and Gazebo
Nestor Gonzalez Lopez,Yue Leire Erro Nuin,Elias Barba Moral,Lander Usategui San Juan,Alejandro Solano Rueda,Víctor Mayoral Vilches,Risto Kojcev
5+阅读 · 2019年3月14日
One-Shot Federated Learning
Neel Guha,Ameet Talwalkar,Virginia Smith
7+阅读 · 2019年3月5日
Zhiming Zhou,Jiadong Liang,Yuxuan Song,Lantao Yu,Hongwei Wang,Weinan Zhang,Yong Yu,Zhihua Zhang
8+阅读 · 2019年2月15日
Yao Quanming,Wang Mengshuo,Jair Escalante Hugo,Guyon Isabelle,Hu Yi-Qi,Li Yu-Feng,Tu Wei-Wei,Yang Qiang,Yu Yang
6+阅读 · 2018年10月31日
Zhen Yang,Wei Chen,Feng Wang,Bo Xu
6+阅读 · 2018年4月24日
Ngoc-Trung Tran,Tuan-Anh Bui,Ngai-Man Cheung
9+阅读 · 2018年3月23日
Behnaz Nojavanasghari,Yuchi Huang,Saad Khan
4+阅读 · 2018年1月30日
Top