你的進度
0/ 25 節已標記完成
下一節: PAC 學習、有限假設類與 VC 維數
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI4230 筆記裏的內容
- 定理卡
- 50
- 定義
- 34
- 反例
- 26
- 概念視角
- 8
- 思想史
- 2
- 證明透視
- 27
數字只算這門課 25 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 50 · 定義 34 · 反例 26 · 概念視角 8 · 思想史 2 · 證明透視 27
第 1 章 · 5 節
PAC 學習
PAC 學習
- 1.1
PAC 學習、有限假設類與 VC 維數
用一致學習、奧卡姆(Occam)界與打散區分統計保證和計算效率。
- 1.2
單調合取式的 PAC 學習
構造刪除式學習器並證明其分布無關的可實現情形 PAC 保證。
- 1.3
從正樣本學習座標軸平行盒子
構造一致學習器並證明適用於含原子分布的分布無關 PAC 保證。
- 1.4
學習帶符號文字的決策列表
構造一致的決策列表學習器,並證明有限類 PAC 保證。
- 1.5
固定寬度 DNF 的 PAC 學習
以一致的刪除算法學習固定寬度布爾(Boolean)析取合取式,並區分樣本保證和運行時間保證。
第 2 章 · 5 節
VC 理論
VC 理論
- 2.1
增長函數、VC 維數與一致收斂
證明 Sauer–Shelah 計數界,並用對稱化同時控制經驗誤差與總體誤差。
- 2.2
半空間與座標軸平行盒子的 VC 維
利用仿射相關和座標極值證明幾何打散界。
- 2.3
未見樣本點與 PAC 學習下界
利用打散集合上的隨機標籤與稀有事件證明樣本下界。
- 2.4
由含噪標籤得到的不可知學習下界
通過把學習歸約為二元檢驗,證明維數除以精度平方的樣本下界。
- 2.5
Rademacher 複雜度與一致泛化
利用隨機符號、對稱化和有界差控制函數類。
第 3 章 · 1 節
模型選擇
模型選擇
- 3.1
使用類權重的結構風險最小化
為可數多個有限類建立同時成立的界,並證明依賴數據的模型選擇的預言機不等式。
第 4 章 · 1 節
樣本壓縮
樣本壓縮
- 4.1
樣本壓縮與泛化
證明一致壓縮界,計入指標和附加資訊的代價,並構造閾值學習器。
第 5 章 · 4 節
在線學習
在線學習
- 5.1
在線錯誤界與加權多數法
證明可實現情形的折半保證與加權多數保證,再將逐次錯誤連接到期望總體誤差。
- 5.2
感知器更新與間隔錯誤上界
由幾何可分性證明有限的錯誤次數上界,並區分它與統計風險保證。
- 5.3
指數權重與相對專家的遺憾
對有界損失的隨機化全資訊預測,推導加性遺憾上界。
- 5.4
從在線學習到批量學習的高概率轉換
把序貫錯誤界轉化為已保存預測器隨機混合的風險保證。
第 6 章 · 2 節
提升法與統計查詢
提升法與統計查詢
- 6.1
提升法與統計查詢
分析加權投票的訓練誤差界,以及統計查詢可從隨機樣本獲得的資訊精度。
- 6.2
通過重加權將弱學習轉化為強學習
證明總體層面的 boosting 保證,並從新鮮樣本模擬自適應的重加權分布。
第 7 章 · 2 節
統計查詢
統計查詢
- 7.1
統計查詢為何難以學習奇偶函數
用正交性證明有限統計查詢下界,並與使用單個有標籤樣本的學習方法比較。
- 7.2
分類噪聲下的統計查詢
從獨立翻轉的標籤模擬自適應乾淨統計查詢,並量化噪聲代價。
第 8 章 · 1 節
主動學習
主動學習
- 8.1
主動學習:查詢與標籤複雜度
分析閾值的自適應標籤請求,與被動樣本比較,並辨明比較何時失效。
第 9 章 · 1 節
含噪聲的學習
含噪聲的學習
- 9.1
帶隨機分類噪聲的學習
推導獨立標籤翻轉的影響,證明有限類學習保證,並辨明噪聲模型的作用。
第 10 章 · 1 節
密碼學困難性
密碼學困難性
- 10.1
偽隨機函數與高效 PAC 學習的限制
將假想的 PAC 學習器歸約為預言機區分器,並處理有限定義域上的重複輸入。
第 11 章 · 1 節
保形預測
有限樣本預測集合及邊際覆蓋。
- 11.1
分割保形預測與邊際覆蓋率
證明有限樣本秩保證,並區分邊際和群組覆蓋。
第 12 章 · 1 節
AdaBoost 提升法
在固定樣本上推導自適應投票及訓練誤差界。
- 12.1
AdaBoost:自適應權重、間隔與訓練誤差界
推導自適應投票與正規化,證明有條件的有限訓練誤差界,並計算具體輪次。