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
外部雜湊分割連接
按鍵分割兩個檔案,保留重複配對,並分析偏斜與輸入輸出量。