MATH3330
大数据计算
数据流统计、摘要与抽样、Monte Carlo 模拟与方差缩减、大规模优化、随机数值线性代数,以及分布式与外部内存计算。
你的进度
0/ 24 节已标记完成
下一节: 1.1 数据流统计与稳定的分块归约
完成记录保存在此浏览器中。
这门课在网上
MATH3330 笔记里的内容
- 定理卡
- 54
- 定义
- 45
- 反例
- 26
- 概念视角
- 19
- 思想史
- 1
- 证明透视
- 27
数字只算这门课 24 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 54 · 定义 45 · 反例 26 · 概念视角 19 · 思想史 1 · 证明透视 27
第 1 章 · 2 节
数据流统计
推导单次扫描及可合并的均值—方差摘要,解释相消与归约次序,并核查流式实现的成本及正确性。
- 1.1
数据流统计与稳定的分块归约
推导单次扫描及可合并的均值—方差摘要,解释相消与归约次序,并核查流式实现的成本及正确性。
- 1.2
Count–Min 草图:数据流中的频率估计
在明确哈希及更新假设下,证明单侧频率估计和固定查询的误差界。
第 2 章 · 1 节
数学模拟
建立无偏模拟估计量,证明有限样本不确定性界,公平比较对偶抽样,并区分可重现性与统计有效性。
- 2.1
Monte Carlo 模拟:不确定性与可重现性
建立无偏模拟估计量,证明有限样本不确定性界,公平比较对偶抽样,并区分可重现性与统计有效性。
第 3 章 · 1 节
大规模优化
推导条件小批量方差及光滑随机下降界,再以明确预算比较批量大小、内存、通信与优化进度。
- 3.1
小批量优化与资源取舍
推导条件小批量方差及光滑随机下降界,再以明确预算比较批量大小、内存、通信与优化进度。
第 4 章 · 5 节
数学数据管线
建立可执行的有限内存合成数据管线,证明中心充分统计量更新,并分清结构有效性、数值准确度与模型拟合。
- 4.1
从记录到拟合模型的流式数据管线
建立可执行的有限内存合成数据管线,证明中心充分统计量更新,并分清结构有效性、数值准确度与模型拟合。
- 4.2
高瘦最小二乘问题的分块 QR
以正交变换逐块压缩数据,同时保留多变量最小二乘的整个目标函数。
- 4.3
奇异值分解、最小二乘与截断正则化
利用奇异方向理解秩、最小范数最小二乘解,以及舍弃不稳定方向的代价。
- 4.4
稀疏矩阵:存储与矩阵向量乘法
按行表示稀疏记录,计算正向和转置乘积,并分析实际成本。
- 4.5
用共轭梯度法求解稀疏正定方程组
用矩阵向量乘法求解正定二次问题,理解精确算术保证与实际停止准则。
第 5 章 · 1 节
分布式计算
实现精确的带标识符归约,证明调度与浮点求和界,并区分算术工作量、通信、负载倾斜及确定性执行。
- 5.1
分区、合并与并行归约的限制
实现精确的带标识符归约,证明调度与浮点求和界,并区分算术工作量、通信、负载倾斜及确定性执行。
第 6 章 · 1 节
随机数值线性代数
实现重要性抽样矩阵乘法,证明精确均方误差,推导有限向量的随机符号保证,并区分无偏矩阵与无偏解。
- 6.1
随机矩阵乘积与有限草图
实现重要性抽样矩阵乘法,证明精确均方误差,推导有限向量的随机符号保证,并区分无偏矩阵与无偏解。
第 7 章 · 1 节
方差缩减与几何
实现快照方差缩减,证明强凸情况下的整轮收缩,并推导固定预条件器如何改变几何与光滑假设。
- 7.1
方差缩减与预条件优化
实现快照方差缩减,证明强凸情况下的整轮收缩,并推导固定预条件器如何改变几何与光滑假设。
第 8 章 · 1 节
8. 方差降低
运用控制变量,区分独立试运行与重用样本。
- 8.1
控制变量与独立试运行
推导使方差最小的控制系数,区分固定、独立试运行及重用样本的选择。
第 9 章 · 1 节
有限 Markov 计算
建立有限目标抽样器,证明细致平衡及实际收敛,并在不假装独立的情况下计算平稳平均方差。
- 9.1
有限 Metropolis–Hastings、Gibbs 更新与相依误差
建立有限目标抽样器,证明细致平衡及实际收敛,并在不假装独立的情况下计算平稳平均方差。
第 11 章 · 1 节
流式抽样
证明单次扫描的不放回均匀抽样,以超几何分配合并分区蓄水池,并在明确内存界限下实现有限随机来源的精确决策。
- 11.1
蓄水池抽样与分区的加权合并
证明单次扫描的不放回均匀抽样,以超几何分配合并分区蓄水池,并在明确内存界限下实现有限随机来源的精确决策。
第 13 章 · 1 节
数据流秩次与分位数
用均匀蓄水池同时估计有限序列的所有秩次,并解释有并列值时的分位数。
- 13.1
用蓄水池样本估计数据流秩次
证明有限总体上同时成立的秩次界,并解释有相同数值时的近似分位数。
第 14 章 · 1 节
正负更新数据流的摘要
在明确的随机函数假设下,证明正负指定键查询的方差及中位数置信保证。
- 14.1
有正负更新的 CountSketch:方差与置信保证
构造可估计正负频数的摘要,证明其余坐标平方质量的方差界,再用独立行与中位数提高成功概率。
第 15 章 · 1 节
找出数据流中的高频键值
以确定性计数摘要和精确重算找出所有严格高频键值。
- 15.1
用 k 个计数器确定性地找出高频键值
证明 k 计数器高频项摘要的计数恒等式与误差界,说明所有严格高频键值均会保留,并以第二次扫描精确剔除假阳性。
第 16 章 · 1 节
概率式成员判断
理解单侧成员过滤器及其有限随机模型保证。
- 16.1
用布隆过滤器判断可能成员
在明确哈希模型下推导单侧成员保证及有限大小的精确误报概率。
第 17 章 · 1 节
滑动窗口
分析近期数据流的有界内存摘要。
- 17.1
滑动窗口中的近似计数
用确定性的桶摘要控制最近二元事件的内存用量与误差。
第 18 章 · 1 节
数据流加权抽样
构造及合并不等权重的固定容量样本。
- 18.1
用指数竞赛作加权抽样
推导固定容量的加权不放回样本,以及分区样本的精确合并规则。
第 20 章 · 3 节
外部内存算法
分析输入超过工作内存时的计算。
- 20.1
外部合并排序与块传输
推导内存受限排序的轮数、块传输量与稳定性。
- 20.2
含重复键的外部排序合并连接
合并已排序文件、暂存相同键的分组,并在多重集语义下计算块传输次数。
- 20.3
外部哈希分割连接
按键分割两个文件,保留重复配对,并分析偏斜与输入输出量。