跳到正文

CSCI4230

計算學習論

PAC 學習與 VC 理論、樣本壓縮、在線學習、提升法與統計查詢、主動學習、含噪聲的學習、密碼學困難性及保形預測。

12 章 · 25 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 25 節已標記完成

下一節: PAC 學習、有限假設類與 VC 維數

完成記錄儲存在此瀏覽器中。

這門課在網上

CSCI4230 筆記裏的內容

定理卡
50
定義
34
反例
26
概念視角
8
思想史
2
證明透視
27

有思想史的節

這些思想史還沒有放上時間線。

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 25 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 50 · 定義 34 · 反例 26 · 概念視角 8 · 思想史 2 · 證明透視 27

這些思想史還沒有放上時間線。

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 25 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 5 節

PAC 學習

PAC 學習

定理 10 · 定義 6反例 5視角 2證明透視 6

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    PAC 學習、有限假設類與 VC 維數

    用一致學習、奧卡姆(Occam)界與打散區分統計保證和計算效率。

  2. 1.2

    單調合取式的 PAC 學習

    構造刪除式學習器並證明其分布無關的可實現情形 PAC 保證。

  3. 1.3

    從正樣本學習座標軸平行盒子

    構造一致學習器並證明適用於含原子分布的分布無關 PAC 保證。

  4. 1.4

    學習帶符號文字的決策列表

    構造一致的決策列表學習器,並證明有限類 PAC 保證。

  5. 1.5

    固定寬度 DNF 的 PAC 學習

    以一致的刪除算法學習固定寬度布爾(Boolean)析取合取式,並區分樣本保證和運行時間保證。

第 2 章 · 5 節

VC 理論

VC 理論

定理 10 · 定義 5反例 5視角 1證明透視 5

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    增長函數、VC 維數與一致收斂

    證明 Sauer–Shelah 計數界,並用對稱化同時控制經驗誤差與總體誤差。

  2. 2.2

    半空間與座標軸平行盒子的 VC 維

    利用仿射相關和座標極值證明幾何打散界。

  3. 2.3

    未見樣本點與 PAC 學習下界

    利用打散集合上的隨機標籤與稀有事件證明樣本下界。

  4. 2.4

    由含噪標籤得到的不可知學習下界

    通過把學習歸約為二元檢驗,證明維數除以精度平方的樣本下界。

  5. 2.5

    Rademacher 複雜度與一致泛化

    利用隨機符號、對稱化和有界差控制函數類。

第 3 章 · 1 節

模型選擇

模型選擇

定理 1 · 定義 1反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    使用類權重的結構風險最小化

    為可數多個有限類建立同時成立的界,並證明依賴數據的模型選擇的預言機不等式。

第 4 章 · 1 節

樣本壓縮

樣本壓縮

定理 2 · 定義 1反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    樣本壓縮與泛化

    證明一致壓縮界,計入指標和附加資訊的代價,並構造閾值學習器。

第 5 章 · 4 節

在線學習

在線學習

定理 6 · 定義 6反例 4證明透視 5

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    在線錯誤界與加權多數法

    證明可實現情形的折半保證與加權多數保證,再將逐次錯誤連接到期望總體誤差。

  2. 5.2

    感知器更新與間隔錯誤上界

    由幾何可分性證明有限的錯誤次數上界,並區分它與統計風險保證。

  3. 5.3

    指數權重與相對專家的遺憾

    對有界損失的隨機化全資訊預測,推導加性遺憾上界。

  4. 5.4

    從在線學習到批量學習的高概率轉換

    把序貫錯誤界轉化為已保存預測器隨機混合的風險保證。

第 6 章 · 2 節

提升法與統計查詢

提升法與統計查詢

定理 5 · 定義 3反例 3思想史 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    提升法與統計查詢

    分析加權投票的訓練誤差界,以及統計查詢可從隨機樣本獲得的資訊精度。

  2. 6.2

    通過重加權將弱學習轉化為強學習

    證明總體層面的 boosting 保證,並從新鮮樣本模擬自適應的重加權分布。

第 7 章 · 2 節

統計查詢

統計查詢

定理 5 · 定義 4反例 2視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    統計查詢為何難以學習奇偶函數

    用正交性證明有限統計查詢下界,並與使用單個有標籤樣本的學習方法比較。

  2. 7.2

    分類噪聲下的統計查詢

    從獨立翻轉的標籤模擬自適應乾淨統計查詢,並量化噪聲代價。

第 8 章 · 1 節

主動學習

主動學習

定理 3 · 定義 2反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    主動學習:查詢與標籤複雜度

    分析閾值的自適應標籤請求,與被動樣本比較,並辨明比較何時失效。

第 9 章 · 1 節

含噪聲的學習

含噪聲的學習

定理 2 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    帶隨機分類噪聲的學習

    推導獨立標籤翻轉的影響,證明有限類學習保證,並辨明噪聲模型的作用。

第 10 章 · 1 節

密碼學困難性

密碼學困難性

定理 2 · 定義 2反例 1思想史 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 10.1

    偽隨機函數與高效 PAC 學習的限制

    將假想的 PAC 學習器歸約為預言機區分器,並處理有限定義域上的重複輸入。

第 11 章 · 1 節

保形預測

有限樣本預測集合及邊際覆蓋。

定理 2 · 定義 2反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 11.1

    分割保形預測與邊際覆蓋率

    證明有限樣本秩保證,並區分邊際和群組覆蓋。

第 12 章 · 1 節

AdaBoost 提升法

在固定樣本上推導自適應投票及訓練誤差界。

定理 2 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 12.1

    AdaBoost:自適應權重、間隔與訓練誤差界

    推導自適應投票與正規化,證明有條件的有限訓練誤差界,並計算具體輪次。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情