跳到正文

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 與儲存詳情