5-科学思维-样例-PAC算法-李廉-20220819.pdf

大数据计算中的计算思维——PAC算法

李廉合肥工业大学

能力的评估：本案例能够置于Bloom分类法知识维度的“程序性知识”位置，学生学习后能

够达到Bloom分类法认知过程维度的“分析”层次（针对大三学生，需先修概率论与数理统

计）。

一、本案例课程思政的关注点

1.本案例内容在计算学科课程思维总体框架中的位置

2.科学思维可拆分为可衡量、可检验的抽象、理论和设计三个过程（学科形态，或工作

范式）。本例包含抽象及理论形态的内容，其中，PAC算法描述、误差和可靠性定义可划分

到抽象形态，PAC算法中关于误差、可靠性及随机抽取样本数之间的关系公式的证明属于理

论形态。学习该案例后，学生对抽象、理论和设计三个学科形态如何区分将有进一步的认知，

这种认知将为我国在三个学科形态方面的工具（含思想与方法）的创新，实现“0到1”的

突破种下科学思维的种子。

3.在本案例中，要求教师将11个品行元素中的“目标驱动、专业性、严谨”与该案例

绑定在一起进行可操作性解释。

目标驱动：在大数据集中找到其中的最大元素，不能简单采用常规的有哪些信誉好的足球投注网站算法，因为会

消耗过多的计算资源。如何在消耗资源较少的前提下，找到事实上可以接受的目标，是驱动

的目标；

专业性：从概率学的角度理解这种近似算法的科学性、合理性；

严谨：对PAC算法能给出严谨的数学证明。

二、本案例的具体内容（讲解脚本）

1.背景介绍

⚫同学们好，本讲介绍一种大数据计算中的计算思维方法，即PAC算法。

⚫S

我们来看这样一个大数据计算中的典型问题：设是超大规模数据集合（包括流

数据），如何找出其中的最大元素。

⚫传统的方法（数学思维）是通过反复比较，保留当前的最大元素，直到整个数据被

NN

扫描一遍。当数据集合的元素个数为时，这个算法需要步。在大数据场景中，

这个算法有时难以实现。

⚫由于数据量巨大，存储空间和计算时间都受到了限制，无法满足精确计算的要求，

这时放弃计算最优解的数学思维，利用局部数据，进行不精确计算，求得可行解，

从而极大减少计算所需要的资源。

⚫也就是寻找近似算法，综合考虑资源优化，使得最后得到的结果保证在一定的误差

之内。

⚫在这样的目标驱动下，数学家和计算机科学家们尝试使用各种方法，希望达到这样

的目标：通过抽取大数据集中的一小部分数据，找出与集合中最大元素充分接近的

元素。

⚫PAC

本讲要介绍的“算法”，就是一种典型的近似算法，通过引入两个概念，即求

解结果的误差（近似性），以及小于这个结果的概率（可靠性），设计充分小的误差

和充分大的可靠性，找出事实上可以接受的解决答案。这个方法称为概率近似正确

方法（ProbablyApproximatelyCorrect，简记为PAC方法）。

⚫本讲的案例参考了我国著名数学家、计算机科学家李廉教授关于PAC算法的论文。

2.PAC算法的形式化描述

⚫我们把PAC算法所想要解决的问题再描述一下：

S||=∞

设是一个数据集合，具有海量的数据，甚至无穷多数据，即（），或者

是一个流动的数据集，随着时间不断有数据流入，这时如何计算最大元素。

⚫在抽象形态层面，可以形式化地描述PAC算法如下：

算法称为PAC算法，如果对于0,1，

[]