动机
数据量大,可以指记录太多而无法全部放入内存,也可以指记录持续到达,根本没有读取“全部数据”的时刻。平均数的公式虽然包含每个观测,计算时却不必保留每个观测。关键是:处理完一块数据之后,哪些信息必须留下,才足以回答下一步的问题?
假设多台机器各自处理一批传感器读数,最后要合并平均数与离散程度。只保存各机器的平均数并不足够,因为不同机器可能处理不同数目的记录。即使再保存方差,若没有记录数,仍无法正确加权。此外,总体的变动同时包括块内变动,以及不同块的平均数之间的距离;第二部分不能忽略。
数值计算还有另一个难点。当读数都靠近一个很大的偏移量,方差可能远小于读数的平方。用两个几乎相同的大数相减,可能把想要的有效信息消掉。因此,实数上的代数等价,不代表浮点数上同样准确。我们先证明精确恒等式,再分清它们在有限精度下能保证什么。
定义
定义 1.1.1
(数据块摘要)
对非空有限数据块 ,定义记录数、均值与中心平方和:
的摘要是三元组 。
这批记录的描述性总体方差是 。如果记录是来自有限方差分布的独立同分布样本,而且 ,无偏样本方差则是 。分母不同,是因为估计的对象及解释不同。没有抽样假设时,后一个式子仍能计算,但不能直接声称无偏。
流式算法依次读取记录,保留大小不随记录数目增长的状态。这里的状态包含一个整数与两个实数累加器。“常数内存”采用固定字长模型;若要求任意长数据流的精确整数计数,所需比特数仍会增长。实现时要分别检查整数溢出与浮点舍入。
定义 1.1.2
(分块归约)
分块归约把记录分成互不重叠的块,先计算每块摘要,再沿一棵以各块为叶节点的合并树,反复以二元合并组合摘要。空块的记录数为零,作为单位元处理:与另一摘要合并时直接返回后者。
空块的平均数没有必须指定的数学值;若随意填零后套用除以总记录数的公式,两块皆空时就会出错。
除非特别说明,下文先用精确实数运算。浮点运算会把结果舍入到可表示的数。相对误差模型在远离上溢与下溢时很有用,但不会让相近数相减变得良态。相近数相减本身可能暴露早先累积的误差;如果输入转换时已把不同读数舍入成同一个数,后面的方差递推也无法恢复失去的差异。
定理 / 命题
命题 1.1.3
(加入一个观测)
设 是非空块的摘要,加入 ,并设 。新摘要为
第一条记录的摘要是 。平方和的增量也可写成 ,故在精确运算下非负。
定理 1.1.4
(合并两个非空块)
两个互不重叠的数据块,摘要分别为 与 ,其中 。令 、,则合并后
在精确实数运算下,不同合并树或输入排列都得到整个多重集的同一摘要。
概念视角代数
用可加坐标表示摘要
非空摘要与幂和 相互决定,其中 ,。不相交数据块的幂和直接相加,所以在这组坐标下合并就是向量加法,结合律、交换律以及空数据块作为单位元都一目了然。合并定理正是把这一加法改写到坐标 中。两种描述在精确算术中一致;在浮点运算中则更宜采用中心化坐标,因为由 还原 恰好就是大偏移例子所示的抵消。
证明思路
证明
(在块均值处拆分每个偏差)
均值公式由两块的总和直接相加而得:,故 。对中心平方和,把块 中的偏差写成 ,平方后求和。交叉项为零,因为相对于块平均数的偏差总和是零。因此该块贡献 。块 同理,贡献 。又有 、,故两个位移平方项相加恰为
至于最后一个断言,对叶节点为互不重叠非空块的合并树作归纳。每个叶节点持有其块的精确摘要。若某节点的两个子节点分别持有各自叶节点(互不重叠)并集的精确摘要,合并公式便给出该节点以下全部叶节点并集的精确摘要。因此根节点持有整个多重集的摘要。这个摘要只依赖多重集,所以树形及叶节点次序都不会改变它。
证明
(加入只有一条记录的块)
加入 ,即与 、、 的块合并,于是 、。合并公式给出 及 。又 ,故 ,证明了递推的另一种写法。它只涉及中心附近的差,避免先平方整个大读数。
证明透视
精确性与互不重叠在哪里起作用
唯一不显然的一步,是把相对于总均值的偏差在块均值处拆分。交叉项 之所以为零,是因为 正是块 的均值;非空条件在这里用到,因为空块没有可供拆分的均值。互不重叠用于把合并数据的中心平方和写成 上的和加 上的和:每条记录只计一次。树的归纳能够闭合,是因为每个内部节点收到的都是互不重叠叶节点集合的精确摘要。在浮点数下,归纳假设在第一次舍入合并时已经失效,所以不继承与树无关的性质:固定的树可以让结果可重现,却不会让结果变成精确值。
公式也揭示了为何不能只平均各块的方差:不同块均值的位移会带来额外的平方和,而在精确运算下这部分非负。
反例模式
块大小相同也不能直接平均块方差
断言:若两块大小相同,合并后的描述性方差等于两块描述性方差的平均。取 、。两块的中心平方和都是 ,方差都是 ,平均为 。合并时 、,,故合并方差为 ;直接看,相对于均值 的偏差是 。把合并公式除以 ,便得 时的正确结论:合并方差等于块方差的平均加上 。只有块均值相同时,原断言才成立。
例题详解
例题 1.1.5
(块大小不等时的完整核查)
取 、。摘要分别是 、,故 、。新均值为 ,中心平方和为 。描述性方差是 ;若有相应的抽样解释,样本方差是 。
直接核查:相对于 的偏差是 ,平方和确为 。两个块均值的不加权平均是 ,连总均值也不正确。平均块方差则还会漏掉两组之间很大的位置差异。
例题 1.1.6
(大偏移量与细小离散程度)
考虑 。均值是 ,中心平方和是 ,描述性方差是 。虽然实数恒等式成立,
左边却要用约 的量相减来取回个位数量级的答案。逐项相加的直接 binary64 计算可以得到 ;这是某个具体运算次序的结果,并非所有语言与函数库必然输出同一错值。
中心递推的均值依次为 、、、,中心平方和依次为 。此例的差值容易准确表示。它展示了原始二阶矩公式的失败机制,并不证明中心递推对任何输入都完全无误。
例题 1.1.7
(把归约计划与资源成本分开计算)
把 条记录分成 个非空块,每个工作节点最多缓冲 条。单次摘要的总算术工作为 ,每个节点在输入缓冲之外只需 状态。每个节点返回三个摘要字段,总摘要通信量为 ,无须把全部原始记录送到归约器;但最初读取及分发输入的成本仍在。
串行合并需 次操作,依赖链长度也是 。平衡二叉树的总操作数相同,但在工作节点及通信条件允许并行时,深度为 。八块需要七次合并、三层。较浅的树可减少相互依赖的舍入阶段,但单靠树形不能为所有数据给出相对误差界。延迟、负载不均及调度都可能主导实际耗时。
若某节点超时后重试,归约器必须只接纳该块一次。把相同摘要合并两次,在代数上确实算出了“重复数据”的摘要,却不是原任务的数据。正确的公式不能代替恰好一次的记录处理约定。
实现可从空状态起步,以第一个有效有限读数初始化,其后套用更新。对缺失值及非有限值,必须事先制定处理策略。直接跳过缺失值可能改变目标总体,直接接纳非有限值则可能污染其后所有摘要。除了接纳的记录数,也可保留拒绝的记录数,让读者知道统计量到底描述了什么。
有意义的检查包括:单个记录、常数数据、大小不等的块、大偏移量、空分区,以及重复的分区标识符。比较多种合并树可以找出程序错误及评估数值敏感度;要求任意树的结果逐比特相同,却是在要求普通浮点加法本来就没有的性质。
常见错误
常见错误
(精确不变性不等于数值可重现性)
要分清数学不变性与数值可重现性。精确摘要只依赖多重集;浮点摘要也可能依赖排列、树形、精度及编译选项。更改工作节点数目可能改变合并树,即使输入与随机种子不变。需要重现时,应记录相关选择。
常见错误
(负的计算方差是诊断信号)
把负的计算方差视为负的变异是错的。精确平方和非负。微小负值须按已记录的数值容差调查;很大的负值可能表示溢出、程序错误或不稳定公式。把所有负值一概改成零,可能掩盖故障。只有一条数据时, 也不是定义良好的样本方差。
常见错误
(摘要不能决定数据本身)
记录数、均值与中心平方和不能重建分位数、异常值位置或多峰形状。例如 与 的记录数都是 、均值都是 、中心平方和都是 ,但前者是两个分开的簇,后者中间有一对相同值。保留什么状态,应由下游问题决定;若要研究分布形状,就需要更丰富的摘要或保留原始记录。
总结
记录数、均值与中心平方和足以精确合并均值和方差。块均值差的修正项计入块间变动。中心递推避开一种重要的相消机制,而有限精度、输入有效性与重复处理仍须各自核查。总工作量、并行深度、内存、输入搬移及摘要通信是不同的资源指标。
练习
快速检查
(从 的摘要开始,加入 。计算新均值、中心平方和、描述性方差及样本方差,并用相对于最终均值的偏差核查。)
解答 · 答案
原均值为 ,平方和为 。新偏差为 ,新均值为 ,新平方和为 。描述性方差为 ,样本方差为 。最终偏差 的平方和也是 ;核查时必须用最终均值而非旧均值。
快速检查
( 有四个 , 有两个 ,两块方差皆为零。求总均值及描述性方差,并解释平均块方差为何失败。)
解答 · 答案
总均值为 。块均值差为 ,故 ,描述性方差为 。直接计算也得四个 加两个 ,即 。块内无变动,块间却有距离;零方差的平均把全部距离漏掉。
快速检查
(证明每个观测同加常数 后,均值增加 ,而 不变。再解释为何极大的偏移仍可能改变浮点计算的方差。)
解答 · 答案
新均值为 。每个偏差都是 ,平方和因此不变。浮点输入却可能在存储时已舍入;当可表示数的间距大于原读数之差,原本不同的观测会合并成同一值。其后相减不能恢复差异;即使输入仍可分辨,不同的舍入路径也可能造成微小差别。
快速检查
(有十六个非空分区。串行与平衡归约各需多少次合并、依赖链多深?若重试时分区 5 被加入两次,固定的树能否修复统计错误?指出一项必要的数据处理不变量。)
解答 · 答案
两者都需十五次合并;串行深度为十五,平衡深度为四。重复分区改变了多重集,通常也改变统计量。固定的树只能稳定地重现错误,不能识别重复。可要求:对固定的输入版本,每个预期的分区标识符恰好贡献一份被接纳的摘要。先核查标识符与记录数,再作数值合并,才符合定理的互不重叠假设。