人工智能系列教材

  • 未来人工智能将进一步改变人类生活的方方面面。
    2017年,《国务院关于印发新一代人工智能发展规划的通知》指出,我国新一代人工智能发展的战略目标为,“到2030年人工智能理论、技术与应用总体达到世界领先水平,成为世界主要人工智能创新中心,智能经济、智能社会取得明显成效,为跻身创新型国家前列和经济强国奠定重要基础”。
  • 清华大学交叉信息研究院计算机科学实验班(姚班)和人工智能班(智班)教学团队
  • 每一章均配备习题与编程实验,让同学们在实践中进一步深化对原理与内容的理解。
  • 适用于高中人工智能课程教材,以及人工智能教育培训教材,亦可作为大众普及读物。
新 闻
大 / 事 / 件

姚期智院士领衔 清华大学推出面向高中生的人工智能教材

2020年1月7日上午,由图灵奖得主、中国科学院院士、清华大学交叉信息研究院院长姚期智领衔主编的教材《人工智能(高中版)》,在清华大学信息技术大楼举办正式出版签约仪式。姚期智院士,图灵奖得主John Hopcroft(约翰·霍普克罗夫特)院士,以及清华大学出版社社长宗俊峰出席签约仪式并致辞。签约仪式由教材副主编、交叉信息院智班项目主任黄隆波副教授主持。

影 响 力
学 / 者 / 寄 / 语
  • 姚期智
    图灵奖得主、中国科学院院士
    清华大学交叉信息研究院院长

    ”人工智能已成为本世纪最重要的新兴科学之一,其重要程度可与前两个世纪中数学、物理所占据的角色一样,会对各个学科产生无比深远的影响。如何让中学生在科学启蒙阶段接受正确的人工智能观念,是中国也是全世界正在探究的问题。
    我们有责任共同解决这一问题。”
  • John Hopcroft
    美国科学院、美国工程院
    美国艺术与科学院三院院士

    ”世界正在发生颠覆性改变,而人工智能就是这一转变的核心动力,如何教育下一代去理解并为未来的工作做好准备,是非常重要的,并且这类教育工作启动得越早越好。未来世界最宝贵的财富是人才,从国家层面来讲,人才培养尤为重要。该教材将对中国的教育产生“根本性的影响”。”
  • 宗俊峰
    清华大学出版社社长

    ”该教材将是人工智能教育和教材出版中里程碑式的引领,这一基础教材对于促进高中与大学教学的有机衔接、推动全民智能教育项目及中小学人工智能相关课程建设的开展具有非常重要的意义。清华大学出版社将与交叉信息研究院强强联手、密切合作,为广大中学生推出此精品教材。”

人工智能(高中版)第一版 · 章节概要

主编:姚期智    出版社:清华大学出版社

目录
  • 第一章:延伸阅读
  • 第二章:补充材料
  • 第三章:补充材料
  • 第四章:延伸习题
  • 第五章:补充材料
  • 第六章:计算机视觉 拓展阅读
  • 第七章:NLP补充材料
  • 第八章:补充材料
  • 第一章:延伸阅读

    1.双向A*算法

    书本里介绍的A*算法是单向搜索,即从初识状态开始,一直搜到目标状态。双向A*算法是对单向A*算法的改进,即从初识状态和目标状态同时开始分别进行A*搜索,直到相遇。

    2.局部搜索:爬山法和模拟退火算法

    书本里介绍里解释的搜索算法主要属于系统性的搜索,其特点是保存了一条从初始位置至目标的路径,并记录了每个节点是否被访问过。因此,当问题的规模很大的时候,其搜索效率会比较低。因此,当我们不需要到达目标的路径,而只需要目标本身时,我们可以只保存和利用当前节点的信息,寻找更加接近目标的下一个邻接节点,从而到达最终的目标,这种方法叫做局部搜索。

    局部搜索是解决最优化问题的一种算法。局部搜索从一个初始解出发,然后依次搜索解的邻域;如果邻域内最优的解优于当前解,则移动至邻域内最优解并继续执行搜索,否则返回当前解。局部搜索的优点是简单、灵活及易于实现,缺点是容易陷入局部最优,且解的质量与最初解和邻域的结构密切相关。爬山法和模拟退火算法是局部搜索的两种典型算法。

    爬山算法是一种经典的局部搜索算法,是对深度优先搜索的一种改进。它通过启发式的方法,对局部的空间进行有限的探索,从而在每一步中找到局部最优解。爬山法是一个简单的循环过程,不断向估计值增高的方向进行移动,并在所有临界状态的估值函数均低于当前状态时终止。

    图1.12 局部最优解与全局最优解

    爬山算法避免了遍历全部节点,在一定程度上提高了效率,但往往只能找到一个局部最优解,而不能保证全局最优解(图1.12)。为了解决此问题,可以在随机生成的初始节点多次调用爬山算法,并选取多次返回值的最优值,从而达成效率与最优解之间的一种平衡。

    爬山法的缺陷在于其永远不会“走下坡”,因此可能被困在局部最优解。相反,如果在状态空间中随机游走,则虽然最终能够找到全局最优解,但是效率非常低。模拟退火算法的思想借鉴了物理中的固体退火原理,将两种搜索方式有效地结合了起来。

    模拟退火算法由Metropolis在1953年提出,是局部搜索算法的一种扩展。Kirkpatrick等人在1983年成功地将模拟退火算法应用于求解组合优化问题。模拟退火算法被广泛地应用于运筹研究领域的优化问题求解,如排程问题、旅行商问题、特征提取、多目标问题等等,对于许多非凸优化问题、NP问题都能够提供较好的近似解。模拟退火算法的基本思想是使用温度函数作为参数,控制搜索的随机程度。模拟退火算法为每一个状态赋予了一个能量,当温度较高时,粒子的行为接近随机游动,有较大概率“走上坡”到达能量更高的状态;而当温度逐渐降低时,粒子的热运动逐渐减弱,系统的能量下降,粒子的行为逐渐变得“保守”,更倾向于停留在局部的最优解当中。这样,模拟退火算法通过控制温度函数不断下降,调整随机搜索的概率,避免了困在局部最优解的同时,也提高了搜索的效率。

  • 第二章:补充材料

    1. 关于reCAPTCHA公司在全球互联网用户的帮助下,构建巨大数据集的故事,可以观看Ted视频:Massive scale online collaboration: https://www.ted.com/talks/luis_von_ahn_massive_scale_online_collaboration

    2. MSCOCO在构建数据集方面有很多不错的思路,可以阅读它的论文: https://arxiv.org/pdf/1405.0312.pdf

    3. 除了监督学习与无监督学习,机器学习领域还有自监督、半监督学习。可以参考如下的阅读材料:
    半监督:https://bdtechtalks.com/2021/01/04/semi-supervised-machine-learning/
    自监督:https://www.fast.ai/2020/01/13/self_supervised/
    https://lilianweng.github.io/lil-log/2019/11/10/self-supervised-learning.html
    想一想,自监督与无监督有什么区别呢?

    4. 神经网络的泛化性是一个令人着迷的科研领域。人们发现,在训练阶段,神经网络可以非常容易地拟合任何噪声数据,但是这样做会损失泛化性能。另一方面,如果训练数据是真实世界的数据,神经网络往往会选择不这么做,而是采取更好方式学习到数据的特点,从而在测试数据中也有很好的表现。可以阅读如下论文了解一些基本的实验: https://arxiv.org/abs/1611.03530

    5. 目前机器学习最热门的研究领域之一就是大规模的神经网络训练。可以参考OpenAI公司的主页(https://openai.com/),他们介绍了他们训练的很多大模型的表现效果。例如,DALL·E模型可以同时对图片和文字进行智能的处理。

    6. 对于Imagenet数据集,如果不用深度学习,传统方法会怎么做分类问题?它们的局限性在哪里?

    7. 如果我们有多个不同的损失函数,应该如何把他们结合起来对函数进行优化?多个损失函数和一个损失函数相比,哪个实际效果会更好?

    8. 在实际训练的时候,我们对模型的表现进行观察之后,在什么情况下认为模型是过拟合了?什么情况下认为模型是欠拟合的?什么情况下认为数据不足,增加数据可能能够改善模型的表现?

  • 第三章:补充材料

    1. 尝试自己用Python写代码,使用梯度下降发和随机梯度下降发优化一个简单的函数。梯度下降法什么时候找不到全局最优解?

    2. 对于非凸函数,什么情况下随机梯度下降法一定能够找到全局最优解呢?尝试画一画,举几个例子。

    3. Softmax巧妙地把向量变成了一个概率。这样可能会导致什么问题呢?

    4. 如果我们把岭回归和套索回归使用的正则化函数加到一起使用,会得到什么结果?

    5. 岭回归和套索回归分别使用了‖w‖_2^2和〖‖w‖〗_1作为正则化函数。我们能不能使用别的函数?有可能会有什么效果?

    6. 在使用梯度下降法的时候,我们对函数进行了统一的光滑性假设,所以对应的也使用了固定的步长进行优化。在实际优化过程中,可是,函数的不同局部区域的光滑性不同,我们其实应该使用不同的步长进行优化,这样优化速度会更快一些。想一想,有什么办法可以让算法根据当前优化的情况自动地调整步长呢?(不一定要非常准确,非常准确是不可能的)

    7. 关于优化领域,著名学者Yurii Nesterov的著作Introductory Lectures on Convex Optimization是非常好的入门读物,有兴趣可以参考。

    8. 套索回归与压缩感知(https://en.wikipedia.org/wiki/Compressed_sensing)有着千丝万缕的关系,可以阅读压缩感知的相关材料,理解两种方法的异同。

    9. 为什么说岭回归与套索回归对应的函数都是凸函数?

    10. 正则化的方法不一定总是能够给机器学习算法带来好处。想想为什么?

  • 第四章:延伸习题

    1.如果以最小化二分类错误率为目标,我们使用f_j=∑_(i∈I_j)▒I[w_j^*≠y_i ] ,来表示叶子j贡献的目标函数值,其中w_j^*为叶子j上数量最多的类别标签。则分类树的分割条件的评价指标为 gain(j,x_p,t)=1/N [f_j-f_j1-f_j2 ] 然而,在一些经典的决策树算法中,训练二分类任务却常常使用基尼系数f_j=p_j0 (1-p_j0 )+p_j1 (1-p_j1 )=2p_j0 (1-p_j0 )(其中p_j0和p_j1分别是叶子j上的正负样本比例,且p_j0=1-p_j1)或是交叉熵f_j=-p_j0 log⁡〖p_j0 〗-p_j1 log⁡〖p_j1 〗代替f_j=∑_(i∈I_j)▒I[w_j^*≠y_i ] 。注意到基尼系数和交叉熵仅仅与正负样本比例有关,因此使用它们做评价标准时需要考虑叶子上的样本量,故评价指标变为 gain(j,x_p,t)=1/N [|I_j | f_j-|I_j1 | f_j1-|I_j2 | f_j2 ]
    请思考使用基尼系数或交叉熵有何优势?

    2. 决策树有许多变种,其中一种是用线性模型代替叶子上的常数预测值的回归树,我们称为分段线性树。普通的回归树对所有落在叶子j上的数据点都只提供一个相同的预测值w_j。分段线性树则在每个叶子j上为数据点x_j提供预测值k_j^T x_j+b_j。请思考在叶子上使用线性模型有何优缺点?

    3.本章提供的示例数据中,特征均为数值型或是仅有两种取值的离散型。对于有m种取值情况的离散型特征,可以对每一种取值都生成一个单独的分支。另一种选择是,从所有取值情况中选出一个子集S,并以数据的该特征值是否在S中作为分割条件。这样做可以保持决策树是一个二叉树结构,但是要选出最优的集合S比较困难,因为一共需要考虑2^(m-1)-1可能的子集S。幸运的是,对于最小化均方误差的回归树,我们可以利用一些统计量对特征的所有取值进行排序,然后快速地找出最优的S。对于特征p,我们按照以下统计量 s_k=(∑_(i∈I_j)▒〖y_i I[x_(i,p)=k] 〗)/(∑_(i∈I_j)▒I[x_(i,p)=k] )
    将它的所有取值排个序。换言之,对于一个特征p的取值k,s_k是所有特征p取值为k的数据的标签的均值。请证明,一定存在一个k^*,集合S^*={k|s_k≤s_(k^* ) }是所有2^(m-1)-1个集合中最优的选择。
    提示:假设存在k_1,k_2,k_3,且s_(k_1 )≤s_(k_2 )≤s_(k_3 ),如果k_1,k_3∈S,k_2∉S,或者k_1,k_3∉S,k_2∈S,则一定可以通过调整k_1,k_2,k_3中某一个与S的隶属关系来获得相同或更大的分割增益。

    4. 我们提到过GBDT也可以使用随机森林中的样本采样方法,即每个决策树只随机采样一部分的数据进行训练。这可以加快每个树的训练速度。但是如果采样率太低,会导致训练数据不能被很好地拟合,每个迭代训练误差的下降速度缓慢。随机森林中每棵树的样本采样中,每个数据点都被赋予了相同的被采样到的概率。你认为GBDT是否有更合适的采样方法,使得即使采样率较低的情况下,也能让每棵树较好地降低训练误差?

    5.对于二分类问题,GBDT常用的损失函数是交叉熵
    l(G(x),y)=-y ln⁡p(x)-(1-y) 〖ln(1-〗⁡〖p(x))〗 其中p(x)=1/(1+e^(-G(x) ) )表示样本(x,y)预测为正样本的概率。请推导出使用以上损失函数时的在GBDT第n+1轮迭代中的每个样本的负梯度表达式。

    历史回顾
    决策树是一个古老的模型,其历史可追溯到1964年Morgan和Sonquist的论文[1]。在多年的发展过程中,许多决策树的训练算法被提出,比较著名的包括CART[2]、ID3[3]、C4.5[4]等等。此外还产生了许多决策树模型的变种。决策树一开始是在统计学领域被提出,但是并没有引起广泛的注意,当时人们认为它容易过拟合。一直到后来,随着CART等具有剪枝的算法被提出,决策树才逐渐在机器学习领域被广泛使用。本章介绍的算法是CART在回归问题下的情形。
    随机森林和梯度提升树都可以追溯到一个更早的集成学习算法,AdaBoost。这三者的发展历史中有一些曲折的故事。AdaBoost由Yoav Freund提出[20],人们发现它效果很好,而且很不容易过拟合。于是计算机科学家和统计学家们试图探究AdaBoost泛化能力背后的理论原理,其中最主流的一套理论被称为间隔(margin)理论[22]。随机森林的作者Breiman一开始也从间隔理论的角度来完善对AdaBoost的解释,但是发现理论和实验结果没有办法匹配[21]。于是Breiman放弃了对AdaBoost间隔理论的研究,转而研究自己提出的新算法,就是随机森林[23]。人们也对间隔理论失去了信心。于此同时,Friedman等统计学家试图从统计学的角度,把AdaBoost解释成一个加性拟合的过程[24],即每次训练一个子模型,使得整个集成模型不断地往训练目标靠拢。这一观点当时也颇具争议,但却成为了梯度提升方法[7]的雏形。
    有趣的是,进入21世纪之后,在中外一些计算机学者的共同努力下[25,26,27],AdaBoost的间隔理论在沉寂了若干年之后被重新重视并完善,解释了之前Breiman遇到的障碍。目前,通过间隔理论,对AdaBoost的泛化能力我们已经有了比较充分的了解。但是随着XGBoost[8]、LightGBM[9]和CatBoost[10]等GBDT开源工具的实现,GBDT今天在应用领域的影响力已经远远超过了AdaBoost。虽然GBDT的理论解释不如AdaBoost完善,但是其效果更胜一筹。
    从这些故事可以看出,科学研究的过程并不是一帆风顺的,常常会遇到挫折。虽然如此,一些当时不被认可或是遇到瓶颈的研究,也许会在多年之后重新获得它们的价值。

    进阶知识点及相关阅读材料
    限于篇幅及前置知识的限制,我们不能在本章中详细介绍决策树及其集成算法的所有知识点。这里列出一些关键的或是具有启发性的知识点,并提供相关阅读材料,鼓励有兴趣的读者自行阅读学习。

    决策树
    本章正文内容中不涉及到具有超过2个类别值的离散型特征参与决策树的训练。延伸习题3中列出了一种处理离散型特征的方式。还有一种比较常用的方式,是在训练之前通过一些编码方法将离散型特征转化成数值型特征。例如,对于一个有m种取值的离散型特征,可以用m个取值为0/1的数值特征来表示,如果一个数据的该离散型特征取值情况为第k种,则对应的数值特征的第k个取值为1,其余取值全部为0。这种编码方式我们称为独热编码(one-hot encoding)。此外,还有一些基于数据标签的编码方式,CatBoost非常好地支持了这种编码[10]。
    此外,训练数据不总是完整的,有时可能存在某些数据点的某些特征值缺失的情况。对于类别特征,我们可以把缺失值当成一种额外的类别来处理。对于数值特征,常用的方式是在训练之前进行填充,例如用所有数据该特征的平均值代替缺失值。这些都属于独立于算法之外的预处理。决策树利用它的结构特点,可以比较方便地处理缺失值。例如,在CART算法[2]中,如果一个分割条件使用了有缺失值的特征,就需要为它准备一个替代分割条件,该条件使用的特征没有或很少有缺失值。
    考虑到目前决策树主要被应用在集成模型中,因此本章在介绍决策树时会考虑到集成模型中训练决策树的常用方式。其中按层训练和按叶训练的区别通常只有在集成模型中才会需要被考虑。这是因为集成模型训练许多决策树,因此需要限制每个决策树的规模大小,防止训练时间过长,这也起到了缓解过拟合的作用。经典的单棵决策树训练算法,通常不直接限制决策树的规模,因此按层训练和按叶训练并不会有区别。它们会先训练一个很大的决策树,然后通过后剪枝的方式来缓解过拟合。关于经典的决策树算法,包括CART、ID3、C4.5等等的详细介绍,参见[2][3][4]。
    决策树应用在机器学习中已经有几十年的历史,Wei-Yin Loh[5]对决策树几十年的发展历史做了详细的总结,并列出了在这个过程中决策树的各种变种。

    随机森林
    本章对随机森林的介绍相对简短,仅提供了算法和直观的理解。随机森林的核心思想涉及到偏差-方差分解。一个模型的产生涉及到一些随机性,例如训练集的采集其实是从数据的实际分布中进行随机采样,同时算法本身也可能具有一定的随机性。偏差指的是一个模型在这些随机性之下,其输出的期望值与数据标签真实值的差距。方差指的是模型在这些随机性之下输出的变化程度。偏差-方差分解的思想是一个模型的泛化误差可分解为偏差与方差之和。[12]的第2章中有关于偏差-方差分解的定义及推导。可以证明,随机森林通过综合许多差异较大的决策树,降低了模型整体的方差,进而得到了良好的泛化性能。[11]的第15章中给出了具体的证明过程。

    梯度提升与GBDT
    这一部分本章仅介绍了使用一阶梯度信息的算法。目前主流的GBDT工具都使用了二阶梯度信息,由于这涉及到函数的泰勒展开,本章不做介绍。有相关基础知识的读者可阅读XGBoost的论文[8],其中有对使用二阶梯度的GBDT的详细介绍。
    由于GBDT需要训练较多的决策树,目前主流GBDT工具都会采用一些方法对决策树的训练过程进行加速。在决策树的训练中,主要的时间开销在分割条件的评估上。假设我们有N个数据点,对于数值类型的特征,或是使用某些编码方式的类别特征,很容易就会有接近N种不同的取值情况。如果我们一一考虑所有可能的分割点,假设决策树按层训练,那么每训练一层就要完整地扫描一遍数据。一种常用的加速方法是通过对特征构建直方图。例如,一个数值型特征的范围是[0,1],那么我们可以按照某种方式把这[0,1]的区间分成若个子区间,然后只考虑子区间的边界值作为候选的分割点。每个子区间需要累积一些统计值来帮助对分割条件进行评估。一般来说,子区间的数目不需要太多,几十个就能取得不错的效果。关于直方图加速的细节可以参考论文[18]和LightGBM的文档[19]。
    在延伸习题中我们提出了一个关于决策树样本采样的问题。除了普通的用于随机森林的等概率采样,近几年有一些针对GBDT的采样方式被提出。这些方法利用数据的梯度信息来估算样本的重要性,从而决定了每个样本的采样概率,其中包括GOSS[9]、MVS[17]等等。这些采样方法可以允许GBDT在比较低的数据采样率之下(例如0.2),仍然保持较好的准确率,从而可以较大程度加速GBDT的训练。有兴趣的读者可阅读相关论文[9][17]。
    GBDT在表格类型的数据上的性能领先于神经网络。但是它也有一些缺陷,例如它不能够很自然地处理离散型特征,需要通过一些统计信息,或是手动的编码。而神经网络可以通过嵌入的方式学习出离散型特征每一个类别值的向量表示。GBDT不能够很好地处理图像、文本等具有空间或者序列依赖性的数据,而深度神经网络在这方面要成熟得多。此外,当有新的训练数据出现时,GBDT还不能够很方便地进行在线更新,因为决策树的结构一旦训练好就被固定下来。而神经网络的参数可以通过梯度回传对新数据进行微调。基于这些缺陷,近些年出现了许多将决策树、GBDT与神经网络结合[13][14],或是试图使用决策树构建深度模型的新算法[15][16]。目前看来这些算法都还没有被广泛的应用,但是它们指出了一些有意思的探索方向。

    参考文献:
    [1] Morgan J N, Sonquist J A. Problems in the analysis of survey data, and a proposal[J]. Journal of the American statistical association, 1963, 58(302): 415-434.
    [2] Breiman L. Classification and regression trees[M]. Routledge, 2017.
    [3] J.Ross Quinlan. Induction of decision trees. Machine Learning, 1(1):81–106, 1986.
    [4] J Ross Quinlan. C4. 5: programs for machine learning. Elsevier, 2014.
    [5] Loh W Y. Fifty years of classification and regression trees[J]. International Statistical Review, 2014, 82(3): 329-348.
    [6] Breiman L. Random forests[J]. Machine learning, 2001, 45(1): 5-32.
    [7] Friedman J H. Greedy function approximation: a gradient boosting machine[J]. Annals of statistics, 2001: 1189-1232.
    [8] Chen T, Guestrin C. Xgboost: A scalable tree boosting system[C]//Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016: 785-794.
    [9] Ke G, Meng Q, Finley T, et al. Lightgbm: A highly efficient gradient boosting decision tree[C]//Advances in Neural Information Processing Systems. 2017: 3146-3154.
    [10] Prokhorenkova L, Gusev G, Vorobev A, et al. CatBoost: unbiased boosting with categorical features[C]//Advances in Neural Information Processing Systems. 2018: 6638-6648.
    [11] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning[M]. New York: Springer series in statistics, 2001.
    [12] 周志华. 机器学习[M]. 清华大学出版社, 2016. [13] Ke G, Xu Z, Zhang J, et al. DeepGBM: A deep learning framework distilled by GBDT for online prediction tasks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 384-394.
    [14] Tanno R, Arulkumaran K, Alexander D, et al. Adaptive neural trees[C]//International Conference on Machine Learning. PMLR, 2019: 6166-6175.
    [15] Zhou Z H, Feng J. Deep forest: towards an alternative to deep neural networks[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017: 3553-3559.
    [16] Feng J, Yu Y, Zhou Z H. Multi-layered gradient boosting decision trees[C]//Advances in neural information processing systems. 2018: 3551-3561.
    [17] Ibragimov B, Gusev G. Minimal Variance Sampling in Stochastic Gradient Boosting[C]//Advances in Neural Information Processing Systems. 2019: 15087-15097.
    [18] Tyree S, Weinberger K Q, Agrawal K, et al. Parallel boosted regression trees for web search ranking[C]//Proceedings of the 20th international conference on World wide web. 2011: 387-396.
    [19] https://github.com/microsoft/LightGBM/blob/master/docs/Features.rst
    [20] Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of computer and system sciences, 1997, 55(1): 119-139.
    [21] Breiman L. Prediction games and arcing algorithms[J]. Neural computation, 1999, 11(7): 1493-1517.
    [22] Schapire R E, Freund Y, Bartlett P, et al. Boosting the margin: A new explanation for the effectiveness of voting methods[J]. The annals of statistics, 1998, 26(5): 1651-1686.
    [23] Breiman L. Random forests[J]. Machine learning, 2001, 45(1): 5-32.
    [24] Friedman J, Hastie T, Tibshirani R. Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors)[J]. The annals of statistics, 2000, 28(2): 337-407.
    [25] Wang L, Sugiyama M, Yang C, et al. On the margin explanation of boosting algorithms[C]//COLT. 2008: 479-490.
    [26] Gao W, Zhou Z H. On the doubt about margin explanation of boosting[J]. Artificial Intelligence, 2013, 203: 1-18.
    [27] Grønlund A, Kamma L, Larsen K G, et al. Margin-based generalization lower bounds for boosted classifiers[C]//Advances in Neural Information Processing Systems. 2019: 11963-11972.

  • 第五章:补充材料

    1. 残差网络(https://arxiv.org/abs/1512.03385)是一个非常优秀的网络结构,通过在不同的网络层之间加入跳跃连接,可以大大降低网络的优化难度,提高泛化效果。阅读相关的论文,考虑一下,如果我们需要对某个跳跃连接的强度系数(默认是1,即把输入复制一遍)求导数,应该怎么计算该导数呢?

    2. 反向传播可以通过很多很多层的网络从输出传到输入,但这并不是最复杂的计算导数的例子。人们还研究过如何针对神经网络整个优化过程求导,换句话说,如果神经网络有100层,优化了1000步,则导数需要传播1000000次!如何保证这么长的传播路径导数计算不出现问题呢?可以参考https://arxiv.org/abs/1502.03492

    3. Distill.pub这个网站有很多关于机器学习,尤其是神经网络的可视化内容,通过观看视频和图片,会对神经网络的工作机理有更好的认识。

    4. 神经网络分为很多种,卷积神经网络、图神经网络,以及我们介绍的全连接神经网络。查阅相关资料,思考一下这些神经网络有哪些不同,各自有什么特点,适合处理什么问题呢?

    5. 我们提到了,多层线性网络从表达能力的角度来看,和线性函数是一样的。线性函数一般是容易优化的,因为如果使用了平方损失函数或其他常见损失函数,得到的优化函数往往是凸的。那么多层线性网络对应的优化函数是不是也是凸的呢?在优化的过程中会不会出现局部最优点?

    6. 除了ReLU,Sigmoid,了解一下还有什么激活函数,它们各有什么特点?

    7. 常用的神经网络除了残差网络,还有密集网络(https://arxiv.org/abs/1608.06993)等等。对于具体的问题设计最合适的神经网络结构是一个非常热门的研究课题。如何自动调整神经网络结构?可以阅读相关文献了解最新进展 https://en.wikipedia.org/wiki/Neural_architecture_search

    8. 我们知道神经网络可以有数百万甚至更多的神经元。假如你可以控制神经网络中某一个神经元,你有没有可能据此影响神经网络针对某些输入的输出?

    9. 神经网络在训练的过程中,有两个常用的部件叫做Batch Normalization和Dropout。阅读相关论文了解它们的工作机理。 https://arxiv.org/abs/1502.03167 https://jmlr.org/papers/v15/srivastava14a.html

    10. 神经网络神经元非常非常多,有没有可能对它进行压缩,使得只使用一小部分的神经元,就可以得到几乎一样的预测性能? https://arxiv.org/abs/1510.00149

  • 第六章:计算机视觉 拓展阅读

    本书讲述了最基本的计算机视觉的概念,包括图像的形成、滤波、卷积、边缘检测和卷积神经网络等内容。这些概念是进一步学习更加前沿和广泛计算机视觉问题的基础。为了满足感兴趣的读者,我们在这里为大家推荐一些拓展阅读资料。这些内容覆盖的范围要远大于本书所讲述的内容。

    1.多伦多大学计算机视觉课程CSC 420 Introduction to Image Understanding CSC420是由Sanja Fidler教授所开设的图像理解入门课程。该课程介绍了更加完整的当代计算机视觉基础。这门课程注重基础知识,内容相比本书更加全面,但不涉及过多高级内容。 这门课程2019年的版本可以通过这个网址访问: http://www.cs.toronto.edu/~fidler/teaching/2019Fall/CSC420.html

    2.斯坦福大学计算机视觉课程 CS131 Foundations and Applications CS131是由多位教授在斯坦福大学开设的计算机视觉课程。其2020年的版本是由Juan Carlos Niebles和Jiajun Wu两位教授共同开设。这门课程相比于多伦多计算机视觉课程更加注重视觉的应用,例如物体分割,动态物体识别,聚类等等。学习这门课程可以对如何用计算机视觉工具解决具体问题有更多的帮助。 这门课程2020年的版本可以通过这个网址访问: http://vision.stanford.edu/teaching/cs131_fall2021/index.html

    3.Rick Szeliski所写的《Computer Vision: Algorithms and Applications》 教材。这是一本涵盖大多数计算机视觉知识的教材,其内容从经典的计算机视觉知识到近期比较新的深度学习知识都有覆盖。这本教材广泛地被国外大学本科、研究生计算机视觉课程所采用。

    如果读者希望更加深入了解计算机视觉知识,我们推荐从简单的课程开始逐渐学习,推荐从多伦多大学CSC420开始。Rick Szeliski的教材可以作为一个字典式的参考书,不必沿着其章节逐一学习。

    计算机视觉 拓展习题

    1.根据常识,我们知道一条笔直的公路的左右边缘看起来会在远处汇聚到一个点。请根据小孔相机坐标变换,证明三维世界中的一组平行线,具有同一个消失点(Vanishing Point)

    图1 消失点(Vanishing Point)示意图

    2. 假设一个单通道灰度图像I的大小是HxW,我们用一个大小为hxw卷积滤波器f对其进行卷积操作,得到了输出图像O.假设我们已知最后损失函数相对于输出图像O的偏导数∂l/∂O。它是一个和输出图像大小相同的矩阵。请尝试推导损失函数相对于输入的偏导数∂l/∂I,和损失函数相对于滤波器的偏导数∂l/∂f。

    3. 高斯微分滤波器的标准差。我们在本书正文的图6.20中展示了高斯微分滤波器的效果。不过这仅仅是一组特定的标准差σ_1=1,σ_2=2。请尝试一些不同的σ_1 σ_2,并总结一下你发现了什么?

  • 第七章:拓展阅读材料

    参考书与网课资料
    本教材着重以计算的角度介绍了自然语言处理的入门知识。自然语言处理是人工智能领域的重要组成,也是相关专业本科教育的必修方向之一。学有余力并对自然语言处理领域有着浓厚兴趣的同学,可以提前参考相关大学教材和课程。这里,笔者作简单推荐。

    教材:
    这里推荐美国斯坦福大学教授Dan Jurafsky(中文名 任韶堂)和科罗拉多大学教授James H. Martin所著的NLP领域经典教科书《Speech and Language Processing》。 Dan Jurafsky教授也在其个人网站公开了部分章节的电子版:https://web.stanford.edu/~jurafsky/slp3/ 该教材也有中译版,《自然语言处理综论(第二版)》,由电子工业出版社出版。

    课程:
    很多高校也公开了各自自然语言处理课程的教案,作业(包括代码)和讲课视频,这里推荐三个公开课程:

    1. 斯坦福大学CS124:该课程是面向斯坦福大学本科生的自然语言处理基础课程,课程网址为 http://web.stanford.edu/class/cs124/ 。 由于斯坦福大学执行quarter学制(一学年3个quarter)因此课程较短。

    2. 加州大学伯克利分校 Info256:该课程是面向伯克利本科生的自然语言课程,课程相对更加完整。http://people.ischool.berkeley.edu/~dbamman/info256.html

    3. 斯坦福大学 CS224n:该课程是面向斯坦福大学高年级本科生和研究生的自然语言进阶课程,着重介绍深度学习技术在自然语言处理中的应用,也更强调自然语言技术的前沿技术的讲解。对于编程基础更好,对自然语言处理基本概念掌握较为牢固,且对深度学习技术有着浓厚兴趣的同学可以参考。http://web.stanford.edu/class/cs224n/

    拓展阅读
    本教材着重从计算和统计建模的角度入手,阐述了自然语言处理领域的一般方法。但是,笔者这里想强调,计算和统计规律并不是自然语言的全部。语言有自己的内在逻辑和发展规律,也有自己内在的美感和历史感。统计计算确实是当代NLP领域的重要工具,虽然正是由于大数据和深度学习的兴起, NLP领域才有了巨大突破,这些技术也确实解决了许多的现实生活中的难题。但是,人是怎么理解语言的呢?数据统计方法是否是解决一切语言理解问题的万能钥匙呢?不同的学者有不同的看法,学界尚未有定论。这里我也想给有兴趣的同学介绍分析语言的不同角度。 语言有自己的独立学科,叫语言学(Linguistics),强调分析语言的内在逻辑和规律。在统计机器学习技术推广之前,自然语言处理领域的研究多是由语言学家(Linguist)参与。例如现代自然语言处理的奠基人之一,麻省理工大学退休教授,Noam Chomsky的开山之作《句法结构》(Syntactic Structures)也是语言学的著作。语言学虽然相对门槛较高,但是作为一个学科本身,也非常适合高中生参与,感受语言的魅力。比如国际语言学奥林匹克竞赛(International Linguistic Olympiad,IOL)就是与数学国际奥林匹克(IMO),物理国际奥林匹克竞赛(IPhO),信息学国际奥赛(IOI)等学科奥赛并列的12项国际中学生奥赛之一。中国从2012开始派队参赛,也取得了优异的成绩。这里,笔者抛砖引玉,介绍一些语言学相关的入门书籍,推荐有兴趣的同学深入阅读。

    1. 《食物语言学》任韶堂 Dan Jurafsky, 上海文艺出版社
    这本书是斯坦福大学Dan Jurafsky教授的另一专著。与传统教材的严谨表述不同,这本书用比较诙谐轻松的文字,讲述了一些有趣的语言现象,也从词源和历史的角度阐述了语言的变化,比如这本书中,Dan Jurafsky教授发现,在美国,菜的价格和菜名中所用的单词有着很强的关系:正面含糊词(delicious, tasty, terrific)每出现一次,平均价格就下降9美分;诱人形容词(rich, chunky, zesty)则意味着下降2美分。在比如,一些日常生活的食材,从名称就可以看出其奇异身世,如西方普遍使用以ketchup称番茄酱,这个怪异的英文单词,其实来源于闽南语的“鱼露”。“chup” 是闽南语中“酱”的音,而“ket”是“腌鱼”的意思。材料虽完全不同,语言却留下了历史的痕迹。这本书适合有兴趣的同学拓展阅读。

    2. 《语言学的邀请》塞缪尔·早川 Samuel Hayakawa / 艾伦·早川 Alan Hayakawa,北京大学出版社
    概书是非常优秀的语言学入门书籍,从语言本身,到语言背后的情感,社会和人与人的关系全面的介绍了语言的各个方面。全书从最难能可贵的是,书作者在很多举例上努力采用更靠近中国语言环境下的例子,使整个书的更加容易被中国的读者接受。这本书作为《大学的邀请》系列丛书中的一本,非常适合有兴趣的高中生阅读。

    3. 《教我如何不想她——语音的故事》朱晓农 / 焦磊,商务印书馆
    “叫我如何不想她”是中国著名语言学家刘半农先生的诗篇,后由另一个著名语言学家赵元任先生谱写成曲广为传唱。这本书作为一个科普书籍,介绍了另一个有趣的领域,语音学,的入门知识——汉语的发音是如何演变的?音标和元音是怎么发展而来的?文字和发音有什么内在联系?整本书以科普为主,以诙谐的语调简述了很多语音学的常识和小故事。作为科普课外读物推荐有兴趣的高中生阅读。

  • 第八章:补充材料

    本章中介绍了马尔可夫决策过程以及强化学习的一些核心基础,包括严格的定义和具体的算法。人们在核心框架的基础上,不断的探索这些方向的前沿,并将理论与算法设计进一步往前推进。下面,我们向读者们推荐一些扩展的学习材料,对强化学习感兴趣的读者可以进一步的学习。

    1. Suton与Barto合著的Reinforcement Learning: An Introduction, MIT Pres, 2018。这本书提供了一个非常全面的介绍,包括强化学习的历史、基本定义、以及不同场景下的关键算法并附有证明。在书本的后几章中,它也提出了强化学习与心理学和脑科学的联系,并简要介绍了强化学习在对弈游戏中的进展。

    2. Bertsekas教授(https://www.mit.edu/~dimitrib/home.html)著有多本强化学习的书,包括Reinforcement Learning and Optimal Control, Athena Scientific, 2019与Rollout, Policy Iteration, and Distributed Reinforcement Learning, Athena Scientific, 2020,从最优化控制的角度更深入地介绍了强化学习的核心理论及算法。他同时也共享了多份强化学习相关的授课讲义与视频。

    3. 网上有不少关于强化学习的优秀的本科/研究生课程资源,如Silva教授的强化学习课程(https://www.davidsilver.uk/teaching/)与Levine教授的深度强化学习课程。它们比较系统地介绍了强化学习的核心知识及相应的算法与实现。

    补充习题

    假设一个移动基站通过一个无线信道将用户的B个数据包传输给用户。每一个时刻基站可以尝试传输1个数据包。但是由于无线信道的状态的变化,每个时刻传输的成功率并不是一个定值。具体来说,每个时刻,信道独立地以相同的概率处于“好”和“坏”两个状态。当信道好的时候,如果基站采用传输功率1,那么传输的成功率为p1;当信道坏的时候,如果基站采用传输功率1,传输的成功率为p2

    图1: 基站通过无线信道向用户传输数据

    假设B个数据包需要在T>B时刻内传输完成,并假设系统的目标是希望最小化总的折扣能耗。(i)请将问题用马尔可夫决策过程进行描述,包括状态与奖励值的定义、状态转移概率与目标的设定。(ii)通过Python变成用值迭代求解。

    图2展示了CartPole-v1环境,杆子的一头连接着手推车,手推车沿着无摩擦的轨道移动。杆子的初始状态为直立状态,可行动作为对推车施加+1或-1的力来控制系统,目的是防止杆子跌落。当杆子与垂直线的夹角超过15度或手推车距中心位置超过2.4个单位以上的距离时,环境结束。

    用DQN算法求解最优策略,画出训练的return以及网络loss。其中,DQN的网络结构为3层全连接网络(非线性激活函数为ReLU函数),隐层维度大小为128,采用ε-greedy策略进行探索。Replay buffer的大小为1000,折扣因子γ为0.9。

    图2: CartPole-v1环境[ref]