跳到正文

MATH3330

大数据计算

数据流统计、摘要与抽样、Monte Carlo 模拟与方差缩减、大规模优化、随机数值线性代数,以及分布式与外部内存计算。

17 章 · 24 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 24 节已标记完成

下一节: 1.1 数据流统计与稳定的分块归约

完成记录保存在此浏览器中。

这门课在网上

MATH3330 笔记里的内容

定理卡
54
定义
45
反例
26
概念视角
19
思想史
1
证明透视
27

有思想史的节

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 24 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 54 · 定义 45 · 反例 26 · 概念视角 19 · 思想史 1 · 证明透视 27

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 24 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 2 节

数据流统计

推导单次扫描及可合并的均值—方差摘要,解释相消与归约次序,并核查流式实现的成本及正确性。

定理 4 · 定义 3反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    数据流统计与稳定的分块归约

    推导单次扫描及可合并的均值—方差摘要,解释相消与归约次序,并核查流式实现的成本及正确性。

  2. 1.2

    Count–Min 草图:数据流中的频率估计

    在明确哈希及更新假设下,证明单侧频率估计和固定查询的误差界。

第 2 章 · 1 节

数学模拟

建立无偏模拟估计量,证明有限样本不确定性界,公平比较对偶抽样,并区分可重现性与统计有效性。

定理 2 · 定义 5反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    Monte Carlo 模拟:不确定性与可重现性

    建立无偏模拟估计量,证明有限样本不确定性界,公平比较对偶抽样,并区分可重现性与统计有效性。

第 3 章 · 1 节

大规模优化

推导条件小批量方差及光滑随机下降界,再以明确预算比较批量大小、内存、通信与优化进度。

定理 2 · 定义 3反例 2视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    小批量优化与资源取舍

    推导条件小批量方差及光滑随机下降界,再以明确预算比较批量大小、内存、通信与优化进度。

第 4 章 · 5 节

数学数据管线

建立可执行的有限内存合成数据管线,证明中心充分统计量更新,并分清结构有效性、数值准确度与模型拟合。

定理 10 · 定义 7反例 5视角 5证明透视 5

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    从记录到拟合模型的流式数据管线

    建立可执行的有限内存合成数据管线,证明中心充分统计量更新,并分清结构有效性、数值准确度与模型拟合。

  2. 4.2

    高瘦最小二乘问题的分块 QR

    以正交变换逐块压缩数据,同时保留多变量最小二乘的整个目标函数。

  3. 4.3

    奇异值分解、最小二乘与截断正则化

    利用奇异方向理解秩、最小范数最小二乘解,以及舍弃不稳定方向的代价。

  4. 4.4

    稀疏矩阵:存储与矩阵向量乘法

    按行表示稀疏记录,计算正向和转置乘积,并分析实际成本。

  5. 4.5

    用共轭梯度法求解稀疏正定方程组

    用矩阵向量乘法求解正定二次问题,理解精确算术保证与实际停止准则。

第 5 章 · 1 节

分布式计算

实现精确的带标识符归约,证明调度与浮点求和界,并区分算术工作量、通信、负载倾斜及确定性执行。

定理 3 · 定义 3反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    分区、合并与并行归约的限制

    实现精确的带标识符归约,证明调度与浮点求和界,并区分算术工作量、通信、负载倾斜及确定性执行。

第 6 章 · 1 节

随机数值线性代数

实现重要性抽样矩阵乘法,证明精确均方误差,推导有限向量的随机符号保证,并区分无偏矩阵与无偏解。

定理 4 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    随机矩阵乘积与有限草图

    实现重要性抽样矩阵乘法,证明精确均方误差,推导有限向量的随机符号保证,并区分无偏矩阵与无偏解。

第 7 章 · 1 节

方差缩减与几何

实现快照方差缩减,证明强凸情况下的整轮收缩,并推导固定预条件器如何改变几何与光滑假设。

定理 3 · 定义 2反例 1视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    方差缩减与预条件优化

    实现快照方差缩减,证明强凸情况下的整轮收缩,并推导固定预条件器如何改变几何与光滑假设。

第 8 章 · 1 节

8. 方差降低

运用控制变量,区分独立试运行与重用样本。

定理 1 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    控制变量与独立试运行

    推导使方差最小的控制系数,区分固定、独立试运行及重用样本的选择。

第 9 章 · 1 节

有限 Markov 计算

建立有限目标抽样器,证明细致平衡及实际收敛,并在不假装独立的情况下计算平稳平均方差。

定理 3 · 定义 4反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    有限 Metropolis–Hastings、Gibbs 更新与相依误差

    建立有限目标抽样器,证明细致平衡及实际收敛,并在不假装独立的情况下计算平稳平均方差。

第 11 章 · 1 节

流式抽样

证明单次扫描的不放回均匀抽样,以超几何分配合并分区蓄水池,并在明确内存界限下实现有限随机来源的精确决策。

定理 4 · 定义 2反例 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 11.1

    蓄水池抽样与分区的加权合并

    证明单次扫描的不放回均匀抽样,以超几何分配合并分区蓄水池,并在明确内存界限下实现有限随机来源的精确决策。

第 13 章 · 1 节

数据流秩次与分位数

用均匀蓄水池同时估计有限序列的所有秩次,并解释有并列值时的分位数。

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 13.1

    用蓄水池样本估计数据流秩次

    证明有限总体上同时成立的秩次界,并解释有相同数值时的近似分位数。

第 14 章 · 1 节

正负更新数据流的摘要

在明确的随机函数假设下,证明正负指定键查询的方差及中位数置信保证。

定理 2 · 定义 3反例 1视角 1思想史 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 14.1

    有正负更新的 CountSketch:方差与置信保证

    构造可估计正负频数的摘要,证明其余坐标平方质量的方差界,再用独立行与中位数提高成功概率。

第 15 章 · 1 节

找出数据流中的高频键值

以确定性计数摘要和精确重算找出所有严格高频键值。

定理 3反例 2证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 15.1

    用 k 个计数器确定性地找出高频键值

    证明 k 计数器高频项摘要的计数恒等式与误差界,说明所有严格高频键值均会保留,并以第二次扫描精确剔除假阳性。

第 16 章 · 1 节

概率式成员判断

理解单侧成员过滤器及其有限随机模型保证。

定理 3 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 16.1

    用布隆过滤器判断可能成员

    在明确哈希模型下推导单侧成员保证及有限大小的精确误报概率。

第 17 章 · 1 节

滑动窗口

分析近期数据流的有界内存摘要。

定理 1 · 定义 2反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 17.1

    滑动窗口中的近似计数

    用确定性的桶摘要控制最近二元事件的内存用量与误差。

第 18 章 · 1 节

数据流加权抽样

构造及合并不等权重的固定容量样本。

定理 2 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 18.1

    用指数竞赛作加权抽样

    推导固定容量的加权不放回样本,以及分区样本的精确合并规则。

第 20 章 · 3 节

外部内存算法

分析输入超过工作内存时的计算。

定理 5 · 定义 4反例 3视角 3证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 20.1

    外部合并排序与块传输

    推导内存受限排序的轮数、块传输量与稳定性。

  2. 20.2

    含重复键的外部排序合并连接

    合并已排序文件、暂存相同键的分组,并在多重集语义下计算块传输次数。

  3. 20.3

    外部哈希分割连接

    按键分割两个文件,保留重复配对,并分析偏斜与输入输出量。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情