概率与统计：计算机科学视角

对现代计算机科学家来说，理解概率和统计是非常重要的. 如果你爱好理论，则需要知道很多概率知识（例如，了解随机算法，理解图论中的概率方法，理解有关近似的大量知识，等等），并至少要有足够的统计知识. 如果你爱好实践，则会发现自己在不断地探寻统计技术（特别是分类、聚类和回归）.例如，很多现代人工智能技术都是建立在统计的基础之上. 再例如，有关海量数据集的统计推断的思考对人们设计现代计算机系统产生了巨大的影响. 
传统上，计算机科学专业的本科生需要学习概率论课程（这一课程通常由数学系教师讲授），或者需要学习统计学课程（这一课程通常由统计系教师讲授）. 计算机科学专业的课程委员会决定对这些课程进行修改，因此，我讲授了该课程的实验版本. 为此，我撰写了一些笔记，基于这些笔记编写了这本书. 本书中没有关于概率或统计的新知识，但其主题是我选择的，我认为这与大家在很多其他书中见到的内容有很大的不同. 
选择主题的关键原则是揭示概率和统计的思想，我认为这些思想是每一名计算机科学专业的本科生都应当了解的，而不管他们以后选择什么专业或从事什么职业. 这意味着本书内容的范围非常广，但对很多领域的介绍并不深入. 我认为这样很好，因为我的目的就是保证所有人都有足够的见识，都能够知道找到一个分类包就可以解决很多问题. 因此，本书覆盖了足够多带你入门的基础知识，并会让你认识到需要了解更多知识. 
我写的这些笔记对研究生也是有益的. 根据我的经验，很多人在并未意识到它们多么有用的情况下学习了本书中的部分或全部内容，然后就忘记了. 如果这样的事情发生在你的身上，希望本书能唤起你的记忆. 你应该掌握本书中的所有内容，又或许应该知道得更多，但绝不应该知道得更少. 
阅读和讲授本书 
本书适合从头至尾进行讲授或者阅读，但不同的教师或者读者可能有不同的需求，因此下面将对本书内容进行简要概述并指出哪些内容可以略过. 
部分 数据集的描述 
这一部分涵盖: 
. 各种描述性统计量（均值、标准差、方差）及一维数据集的可视化方法 
. 散点图、相关性及二维数据集的描述
多数读者可能看到过这些内容的一部分，以我的经验，使人们真正意识到使用图片的方法表示数据集多么有用是需要花费一些时间的. 我尝试通过范例研究不同的数据集来特别强调这一点. 在讲授这些内容时，我缓慢且仔细地推进这些章节. 
第二部分 概率 
这一部分涵盖: 
. 离散型概率 
. 条件概率，需要特别强调其中的例子，因为人们发现这些主题是与直觉相悖的 
. 随机变量与期望 
. 部分连续型概率内容（概率密度函数及如何解释） 
. 马尔可夫不等式、切比雪夫不等式及弱大数定律 
. 各种有用概率分布的部分性质 
. 对较大的 N，二项分布的正态逼近 
我非常认真地以形式化方式介绍了离散型概率. 很多人发现条件概率是与直觉相悖的（或至少在他们看来是如此的 —— 你仍然可以对 Monty Hall 问题继续发起讨论），因此，我使用了一些（有时令人吃惊的）例子来强调在此处认真思考是多么重要. 根据我的经验，范例是能够帮助学习的，但在一节中给出过多的范例会让读者分散注意力，因此，我会用一整节来介绍额外范例. 除了这些额外范例，你不能忽略此处的任何内容. 
有关随机变量的一章主要包含一些常规内容，但此处也涵盖了马尔可夫不等式、切比雪夫不等式及弱大数定律. 根据我的经验，计算机科学专业的本科生喜欢仿真（当可以编写程序时，为什么要去做加法?），并且非常喜欢使用弱大数定律. 你可以略过这些不等式，只介绍弱大数定律. 很多学生在后续的理论课程中将会学习这些不等式，经验表明，如果学生之前曾经见过这些不等式，他们通常更容易掌握它们. 
有关有用的概率分布的一章也主要包含一些常规内容. 在我讲授这门课程时，这一章会讲得很快，主要让学生自己阅读. 但是，对具有较大 N 的二项分布的正态逼近会进行详细的讨论. 根据我的经验，没有人喜欢推导，但你应当知道这个逼近是成立的，并知道它的原理. 我主要通过一些例子来详细讲授这一主题. 
第三部分 推断 
这一部分涵盖: 
. 样本和总体 
. 总体均值抽样估计的置信区间 
. 统计显著性，包括 t 检验，F 检验及 χ2 检验 
. 简单的实验设计，包括单向和双向实验 
. 实验的 ANOVA（方差分析）
. 极大似然推断 
. 简单贝叶斯推断 
. 过滤简介 
有关样本的内容仅包含有放回抽样，这是学习更复杂的内容的基础. 学生不太喜欢置信区间，也许是因为它的真正定义过于微妙，但是理解它的一般思想是至关重要的. 这些主题确实不应当被略过. 
你也不应当略过统计显著性的部分，尽管你很想略过. 我从来没有与次接触统计显著性就感到愉悦的人（这样的人可能在一个非常大的总体内是存在的）打过交道. 但这一思想非常有用且非常有价值，以至于你不得不学习. 
我通常不讲简单的实验设计和方差分析，但回想起来，这是一个错误. 方差分析的思想是非常直接且实用的. 我们通常使用别人的数据集进行实验设计教学，然而正确的选择应该是要求学生去设计并进行实验，但在正常的课程中通常没有足够时间来安排这个. 
后，你不应当略过极大似然推断或贝叶斯推断，即便很多人并不需要知道过滤. 
第四部分 工具 
这一部分涵盖: 
. 主成分分析 
. 使用主坐标分析的简单多维放缩 
. 分类的基本思想 
. 近邻分类 
. 朴素贝叶斯分类 
. 使用经随机梯度下降法训练过的线性 SVM 进行分类 
. 使用随机森林进行分类 
. 维度灾难 
. 聚合和分裂聚类 
. k 均值聚类 
. 向量量化 
. 多元正态分布 
. 线性回归 
. 分析与改进回归方法的一些技巧 
. 近邻回归 
. 简单马尔可夫链 
. 隐马尔可夫模型 
我所在学院的学生在学习本课程的同时也在学习线性代数课程. 当我讲授该课程的时候，将时间进行了调整，以便学生可以在他们刚刚学完特征值和特征向量之后学习主成分分析. 你不应当略过主成分分析. 我讲授的主坐标分析是非常浅显的，仅仅描述了它是做什么的以及为什么它是有用的. 
我经常被比较强硬地告知不能向本科生讲授分类问题. 在我看来，这必须学，学生对此也非常喜爱. 给学生讲授非常有用和非常容易做到的内容时，他们真的会进行反馈. 请一定不要略过这一部分的任何内容. 
聚类的相关内容非常简单且容易讲授. 根据我的经验，如果没有应用，这个主题就有点让人费解. 我通常会设置一个编程练习，让学生编写一个使用了向量量化方法导出特征的分类器. 这是一个确定人们理解了某件事情的非常好的方法，但并不真实. 很多学生发现该练习很有挑战性，因为他们必须同时使用很多概念. 但很多学生克服了困难并非常开心地看到这些部分良好地结合起来. 多元正态分布在此处不过是说说而已，我认为你不能略过本章中的任何知识. 
与回归有关的内容也非常简单且容易讲授. 此处的主要障碍是学生觉得越复杂的事情越需要不断学习. 不是只有他们是这么想的，我也认为你不能略过本章中的任何知识. 
根据我的经验，计算机科学专业的学生发现简单的马尔可夫链使用起来很自然（尽管他们可能发现这个记号很烦人），并且会建议在教学开始之前就模拟一个链. 使用马尔可夫链生成自然语言的例子（特别是 Garkov 和葡萄酒评价）是非常有趣的，并且你真的可以在课程中向他们演示. 你可以略去网页排名的讨论. 我接手的班级中，大约有一半的学生认为隐马尔可夫模型是简单且自然的，另一半则期望期末好快点到来. 如果你不太喜欢这一部分，可以略过它们，并让那些可能对此感兴趣的人自学. 
第五部分 其他数学知识 
这一部分汇总了一些读者可能会发现有用的数学事实，也包括一些关于决策树构造的更深入的知识. 不需要讲授这部分内容. 

David Forsyth 
美国伊利诺伊州厄巴纳

本书针对计算机科学专业的本科生，旨在揭示概率和统计的思想。全书共分为五部分，第I部分数据集的描述，涵盖各种描述性统计量（均值、标准差、方差）、一维数据集的可视化方法，以及散点图、相关性和二维数据集的描述；第II部分概率，内容涵盖离散型概率、条件概率、连续型概率、Markov不等式、Chebyshev不等式及弱大数定律等；第III部分推断，涵盖样本、总体、置信区间、统计显著性、试验设计、方差分析和简单贝叶斯推断等；第IV部分工具，涵盖主成分分析、zui近邻分类、朴素贝叶斯分类、K均值聚类、线性回归、隐Markov模型等；第V部分零散的数学知识，汇总了一些有用的数学事实。

大卫·福赛斯（David Forsyth）　曾在艾奥瓦大学任教3年，在加州大学伯克利分校任教10年，之后到伊利诺伊大学任教。他是2000、2011、2018年IEEE计算机视觉和模式识别会议（CVPR）的程序委员会共同主席，2006年CVPR和2019年IEEE国际计算机视觉会议（ICCV）的大会共同主席，2008年欧洲计算机视觉会议（ECCV）的程序委员会共同主席，而且是所有主要的计算机视觉国际会议的程序委员会成员。此外，他还在SIGGRAPH程序委员会任职了6届。他于2006年获得IEEE技术成就奖，并分别于2009年和2014年成为IEEE会士和ACM会士。

前言
致谢
作者简介
符号和约定
部分 数据集的描述
第1章 查看数据的个工具 2
1.1 数据集 2
1.2 正在发生什么？绘制数据的图形 3
1.2.1 条形图 5
1.2.2 直方图 5
1.2.3 如何制作直方图 6
1.2.4 条件直方图 7
1.3 汇总一维数据 8
1.3.1 均值 8
1.3.2 标准差 9
1.3.3 在线计算均值和标准差 12
1.3.4 方差 13
1.3.5 中位数 13
1.3.6 四分位距 15
1.3.7 合理使用汇总数据 16
1.4 图形和总结 16
1.4.1 直方图的一些性质 17
1.4.2 标准坐标和正态数据 19
1.4.3 箱形图 21
1.5 谁的更大？澳大利亚比萨调查 22
问题 26
编程练习 26
第2章 关注关系 28
2.1 二维数据绘图 28
2.1.1 分类数据、计数和图表 28
2.1.2 序列 32
2.1.3 空间数据散点图 33
2.1.4 用散点图揭示关系 33
2.2 相关 37
2.2.1 相关系数 40
2.2.2 用相关性预测 43
2.2.3 相关性带来的困惑 46
2.3 野生马群中的不育公马 47
问题 49
编程练习 51
第二部分 概率
第3章 概率论基础 56
3.1 实验、结果和概率 56
3.2 事件 57
3.2.1 通过计数结果来计算事件概率 58
3.2.2 事件概率 60
3.2.3 通过对集合的推理来计算概率 62
3.3 独立性 64
3.4 条件概率 68
3.4.1 计算条件概率 69
3.4.2 检测罕见事件是困难的 71
3.4.3 条件概率和各种独立形式 73
3.4.4 警示例子：检察官的谬论 74
3.4.5 警示例子：Monty Hall 问题 75
3.5 更多实例 77
3.5.1 结果和概率 77
3.5.2 事件 78
3.5.3 独立性 78
3.5.4 条件概率 79
问题 81
第4章 随机变量与期望 86
4.1 随机变量 86
4.1.1 随机变量的联合概率与条件概率87
4.1.2 只是一个小的连续概率 90
4.2 期望和期望值 92
4.2.1 期望值 92
4.2.2 均值、方差和协方差 94
4.2.3 期望和统计 96
4.3 弱大数定律 97
4.3.1 独立同分布样本 97
4.3.2 两个不等式 98
4.3.3 不等式的证明 98
4.3.4 弱大数定律的定义 100
4.4 弱大数定律应用 101
4.4.1 你应该接受下注吗 101
4.4.2 赔率、期望与博彩：文化转向 102
4.4.3 提前结束比赛 103
4.4.4 用决策树和期望做决策 104
4.4.5 效用 105
问题 107
编程练习 110
第5章 有用的概率分布 112
5.1 离散分布 112
5.1.1 均匀分布 112
5.1.2 伯努利随机变量 112
5.1.3 几何分布 113
5.1.4 二项分布 113
5.1.5 多项分布 115
5.1.6 泊松分布 115
5.2 连续分布 117
5.2.1 均匀分布 117
5.2.2 贝塔分布 117
5.2.3 伽马分布 118
5.2.4 指数分布 119
5.3 正态分布 119
5.3.1 标准正态分布 120
5.3.2 正态分布 120
5.3.3 正态分布的特征 121
5.4 逼近参数为$N$的二项式 122
5.4.1 当$N$取值很大时 124
5.4.2 正态化 125
5.4.3 二项分布的正态逼近 127
问题 127
编程

本书针对计算机科学专业的本科生，旨在揭示概率和统计的思想。全书共分为五部分，第I部分数据集的描述，涵盖各种描述性统计量（均值、标准差、方差）、一维数据集的可视化方法，以及散点图、相关性和二维数据集的描述；第II部分概率，内容涵盖离散型概率、条件概率、连续型概率、Markov不等式、Chebyshev不等式及弱大数定律等；第III部分推断，涵盖样本、总体、置信区间、统计显著性、试验设计、方差分析和简单贝叶斯推断等；第IV部分工具，涵盖主成分分析、zui近邻分类、朴素贝叶斯分类、K均值聚类、线性回归、隐Markov模型等；第V部分零散的数学知识，汇总了一些有用的数学事实。

大卫·福赛斯（David Forsyth）　曾在艾奥瓦大学任教3年，在加州大学伯克利分校任教10年，之后到伊利诺伊大学任教。他是2000、2011、2018年IEEE计算机视觉和模式识别会议（CVPR）的程序委员会共同主席，2006年CVPR和2019年IEEE国际计算机视觉会议（ICCV）的大会共同主席，2008年欧洲计算机视觉会议（ECCV）的程序委员会共同主席，而且是所有主要的计算机视觉国际会议的程序委员会成员。此外，他还在SIGGRAPH程序委员会任职了6届。他于2006年获得IEEE技术成就奖，并分别于2009年和2014年成为IEEE会士和ACM会士。