依林軒田「機器學習基石」與「機器學習技法」兩門 MOOC 一堂一篇導讀：基石 16 堂、技法 16 堂，每篇依該堂的官方講義與影片寫成，每一節附上對應的影片，把推導走完、把課堂小測驗解完。從 PLA、VC 維度、線性模型、正則化與驗證，一路讀到 SVM、kernel、aggregation、樹模型與神經網路，並用公開的 Fall 2024 HW0–HW7 與期末專題當練習；Fall 2026 的課另外對照。
基石用 16 堂回答四個問題：機器什麼時候學得會、為什麼學得會（Hoeffding、成長函數、VC 維度）、怎麼學（線性迴歸、邏輯迴歸、非線性轉換）、怎麼學得更好（正則化、驗證）。技法再用 16 堂講三種處理特徵的方法：kernel 把特徵嵌進高維（SVM）、aggregation 把多個假說合起來（AdaBoost、隨機森林、GBDT）、extraction 從資料學出隱藏特徵（神經網路、矩陣分解）。130 支 YouTube 影片免費；練習用 Fall 2024 公開的 HW0–HW7。
基石第 1 堂把機器學習定義成「用資料算出一個接近目標 f 的假說 g」，並給出判斷該不該用它的三個條件：有可學的模式、寫不出程式定義、手上有資料。整堂課的骨架是一張流程圖：未知的 f 產生資料 D，演算法 A 從假說集合 H 裡挑出 g；A 加 H 合稱學習模型，之後 15 堂都在這張圖上換零件。
這堂課給第 1 堂的流程圖填上第一組具體內容：假說集合 H 是所有的線（感知器），演算法 A 是 PLA，看到分錯的點就把 w 加上 yₙxₙ。資料線性可分時，從 w₀ = 0 出發最多修正 R²/ρ² 次就會停；資料分不開時改用 pocket，把看過錯最少的那條線留在口袋裡。
這堂課把第 1 堂的學習流程圖沿四個方向各換一次：輸出空間 Y（二元分類、多類別分類、迴歸、結構化學習）、標籤 yₙ（監督式、非監督式、半監督式、強化學習）、資料交給演算法的方式（batch、online、active）、輸入空間 X（具體、原始、抽象特徵）。四個方向各有一個核心選項，合起來是基石之後的主場：批次、監督式、具體特徵的二元分類與迴歸。
這堂課先證明只靠資料 D 推不出 D 以外的答案（No Free Lunch），再加上一個假設：資料與未來的輸入都從同一個分布獨立抽出。Hoeffding 不等式於是保證，一個事先固定的假說 h，E_in 與 E_out 相差超過 ε 的機率不超過 2exp(−2ε²N)。演算法要從 M 個假說裡挑，上界乘上 M 變成 2M exp(−2ε²N)；假說有限、資料夠多、E_in 又小，學習就可行。
上一堂的保證裡有假說個數 M，感知器有無限多條線，M 是無限大。這堂課改數這些線在 N 筆資料上排得出幾種 ○× 組合（dichotomy），對所有擺法取最大值得到成長函數 m_H(N)：positive rays 是 N+1，positive intervals 是 ½N²+½N+1，convex sets 是 2ᴺ，二維感知器在 4 個點上最多 14 種。成長函數第一次到不了 2ᴺ 的點數叫 break point，講義猜它會把成長函數壓成多項式，證明留到下一堂。
假說集合只要有 break point k，N 個點上最多能產生的 dichotomy 數 B(N, k) 就滿足 B(N, k) ≤ B(N−1, k) + B(N−1, k−1)，由此推出 B(N, k) ≤ C(N, 0) + … + C(N, k−1)，最高次是 N 的 k−1 次方。再用三個步驟把成長函數放進 Hoeffding，得到 VC bound：壞事機率 ≤ 4·m_H(2N)·exp(−ε²N/8)。二維感知器的 break point 是 4，所以學得起來。
這堂課把「最大的非 break point」命名為 VC 維度 d_VC，用可逆矩陣與線性相依兩段證明 d 維感知器的 d_VC = d + 1，再把 VC bound 改寫成 E_out ≤ E_in + Ω：d_VC 愈大，E_in 愈容易壓低，但複雜度的懲罰 Ω 也愈大。照 bound 算，ε = δ = 0.1、d_VC = 3 要 29,300 筆資料，大約是 10,000 倍的 d_VC；實務上 10 倍常常就夠。
這堂課把固定的目標函數換成目標分布 P(y|x)：只要 (x, y) 是從同一個聯合分布獨立抽出來的，VC bound 在有雜訊時照樣成立。誤差衡量 err 和 P(y|x) 一起決定每個 x 上最理想的預測，0/1 誤差選機率最大的 y，平方誤差選加權平均。CIA 指紋辨識把誤放罰 1000 倍，這種加權分類等於把 −1 的資料複製 1000 次再做一般分類。
線性迴歸把平方誤差寫成 (1/N)‖Xw − y‖²，令梯度為零就得到 w_LIN = X†y，不必迭代。hat matrix H = XX† 把 y 投影到 X 的直行張成的空間，trace(I − H) = N − (d+1)，由此得到平均 E_in = σ²(1 − (d+1)/N)、平均 E_out = σ²(1 + (d+1)/N)。平方誤差又是 0/1 誤差的上界，所以 w_LIN 也能拿來做二元分類。
邏輯迴歸用 θ(wᵀx) 估計 P(+1|x)，資料卻只有圈與叉。這堂課用最大概似推出 cross-entropy 誤差 ln(1 + exp(−y wᵀx))，用連鎖律算出梯度是 −yₙxₙ 的 θ 加權平均；令梯度為零是 w 的非線性方程式，沒有閉式解，所以改用固定學習率的梯度下降 w ← w − η∇E_in(w) 一步一步走到谷底。
PLA、線性迴歸、邏輯迴歸都先算分數 s = wᵀx，三種誤差都能寫成 ys 的函數。平方誤差與換成 log₂ 的 cross-entropy 都壓在 0/1 誤差上面，所以把迴歸的 E_in 做小，分類的 E_out 也跟著有保證。接著把梯度裡的 N 筆平均換成隨機抽一筆，得到每步 O(1) 的 SGD；再用 OVA（K 個分類器、取分數最高）與 OVO（K(K−1)/2 個分類器、投票）把二元分類器組成多類別分類器。
資料用直線切不開時，不必重新設計演算法：先用特徵轉換 Φ 把 x 換成 z，在 Z 空間照常跑線性模型，Z 空間的直線就是 X 空間的二次或更高次曲線。Q 次多項式轉換會把維度拉到 d̃ = C(Q+d, d) − 1，計算、儲存與 VC 維度（至多 d̃+1）都跟著漲，所以這堂課的結論是先試線性模型，不夠再往高次走。
過擬合指的是換到更強的模型時 E_in 下降、E_out 卻上升的過程。這堂課用只會 2 次與會 10 次多項式的兩位學習者做實驗，得到四個成因：資料太少、隨機雜訊太大、確定性雜訊太大（目標太複雜）、模型能力過剩，並解釋為什麼完全沒有雜訊的資料也會過擬合。對策先講資料清理、修剪與 virtual examples，正則化與驗證留給後兩堂。
從 10 次多項式退回 2 次，等於在 10 次的問題上加限制式。把限制放軟成 ‖w‖² ≤ C 之後，最佳解上 E_in 的負梯度必須和 w 平行，由此得到 w_REG = (ZᵀZ + λI)⁻¹Zᵀy，也等於最小化 E_aug = E_in + (λ/N)wᵀw，這就是 weight decay。λ 愈大，等效的 C 愈小，有效 VC 維度 d_EFF 跟著變小；換成 L1 則會得到稀疏解。
用 E_in 選模型一定偏向最複雜的那個，用 E_test 選又拿不到測試資料。這堂課從手上的 N 筆切出 K 筆當驗證集，得到 E_out(g_m*) ≤ E_out(g⁻_m*) ≤ E_val(g⁻_m*) + O(√(log M / K))，說明選完為什麼要用全部資料重訓、K 為什麼取 N/5；再把 K 推到 1 得到幾乎無偏的 leave-one-out，最後用 5-fold 或 10-fold 交叉驗證把計算量降回可行。
基石最後一堂不教新演算法，講三個讓前十五堂的保證失效的情況。簡單的模型很難碰巧把亂標的資料分開：10 個點配隨機標籤，decision stump 分得開的機率只有 20/1024，所以分得開才有意義。訓練與測試不是同一個分布時 VC 保證不成立；資料只要影響過學習流程的任何一步，就不能再拿來評估結果。最後用 Power of Three 把整門課收成五組三。
Fall 2024 的基石作業共六份：HW0 是 20 題數學先修選擇題；HW1–HW5 每份 12 題加 1 題 bonus，Q1–4 自動批改、Q5–12 助教批改，程式題用 LIBSVM 網站上的 rcv1、cpusmall、mnist 資料，HW5 要用 LIBLINEAR。HW1、HW2 各有一題要你拿 ChatGPT 類工具的回答來反駁。Fall 2026 已公開 hw0 與 hw1：hw1 改成 16 題全選擇題、抽 4 題由助教細改，資料換成課程自己給的 hw1_train.dat；新 policy 允許用 AI 與 vibe coding，但 AI 產生的程式要逐段用自己的話寫註解。兩個學期都沒有公開官方解答。
把資料全部分對的線有很多條，這堂課挑離最近的資料點最遠、也就是最胖的那一條。把 (b, w) 縮放到 min yₙ(wᵀxₙ+b)=1 之後，最大的 margin 等於最小化 ½wᵀw，限制式是每個點 yₙ(wᵀxₙ+b)≥1，可以直接交給二次規劃的解算器。胖的好處有兩種解釋：它是 E_in=0 範圍內的 weight decay，也讓能產生的 dichotomy 變少。
hard-margin SVM 的原始問題有 d̃+1 個變數，特徵維度一大就解不動。這堂課用拉格朗日對偶把它換成只有 N 個變數、N+1 條限制的二次規劃，再用 KKT 條件從 α 算回 w 與 b；只有 α 大於 0 的支援向量會影響答案。對偶問題的矩陣裡還留著 d̃ 維的內積，所以特徵維度要到下一堂才真的擺脫。
對偶 SVM 的變數個數已經和特徵維度 d̃ 無關，但 Q 矩陣的每個元素還是一次 d̃ 維內積。這堂課把「轉換＋內積」合成一個 kernel 函數 K(x, x′)，二次轉換的內積只要 O(d) 就能算完；訓練、算 b、預測三個地方全部換成 K 之後，SVM 不再碰 Z 空間。同一招推到極限，Gaussian kernel 對應無限多維的轉換，代價是 γ 選太大照樣過擬合。
hard-margin SVM 堅持把資料完全分開，所以會去擬合雜訊。這堂課替每個點加一個違反量 ξₙ，用參數 C 權衡邊界寬度與違反總量，得到 soft-margin SVM；它的對偶問題和 hard-margin 只差 αₙ 多了上界 C。αₙ 的值把資料分成非支援向量、free SV、bounded SV 三類，算 b 要用 free SV；C 與 γ 用交叉驗證選，支援向量的比例 #SV/N 是 leave-one-out 誤差的上界。
soft-margin SVM 的 ξₙ 可以直接寫成 max(1 − yₙ(wᵀzₙ + b), 0)，整個問題就變成 ½wᵀw 加上 C 乘以 hinge 誤差的總和，是一個 L2 正則化模型，C 對應 1/(2λ)。hinge 誤差和邏輯迴歸的 cross-entropy 都是 0/1 誤差的凸上界，所以 SVM 近似於 L2 正則化邏輯迴歸。要機率輸出有兩條路：Platt 的兩層學習只多學兩個數字 A 與 B；representer theorem 則保證最佳的 w 是 zₙ 的線性組合，可以直接在 Z 空間做 kernel 邏輯迴歸，代價是 N 個 βₙ 通常都不是 0。
用 representer theorem 把 ridge regression 換成解 β，得到 kernel ridge regression 的解析解 β = (λI + K)⁻¹y，但 N 個 βₙ 幾乎都不是 0。把平方誤差換成 ε-insensitive 的管狀誤差，照 soft-margin SVM 的路線寫成 QP 再取對偶，就得到支援向量迴歸（SVR）：對偶有 2N 個變數，嚴格落在管子裡的點 βₙ 一定是 0。
手上有 T 個假說 gₜ 時，除了用 validation 挑一個，還可以一人一票（uniform blending）、學一組票數（linear blending）或再學一個模型來組合（any blending，也叫 stacking）。這堂用一段六行的代數證明：平方誤差下，平均後的 G 不會比 gₜ 的平均表現差，差距就是 gₜ 之間的分散程度，也就是 variance。最後用 bootstrap 從唯一一份資料重抽出 T 份，各訓練一個 gₜ 再投票，就是 bagging。
這堂把 bagging 的 bootstrap 改看成替每筆資料加權，再刻意把權重調到讓上一輪的 gₜ 加權錯誤率剛好 1/2，逼下一輪學出不一樣的假說。做法是答錯的資料乘上 ◆ₜ = √((1−εₜ)/εₜ)、答對的除以它，並用 αₜ = ln ◆ₜ 當票數做線性投票，這就是 AdaBoost。基礎演算法只要每一輪都比亂猜好一點，E_in 會在 O(log N) 輪內降到 0；搭配 decision stump，六筆資料手算三輪就看得到。
決策樹是邊學邊做 conditional aggregation 的模型：每條從根到葉的路徑是一個條件，葉子是一個常數。C&RT 每次用一個 decision stump 把資料切成兩份，挑加權不純度最小的切法，切到不能再切為止；這樣長出來的樹 E_in 幾乎都是 0，所以要用「E_in 加 λ 乘葉子數」剪枝，λ 用 validation 選。同一套遞迴還能處理多類別、類別特徵與缺值。
隨機森林是 bagging 套在完全長成的 C&RT 上，再讓每次分支只看隨機投影出來的少數特徵。bootstrap 抽 N 次時，每筆資料約有 1/e ≈ 36.8% 的機率沒被某棵樹用到，這些 out-of-bag 資料可以直接算出 E_oob，當作不用另外切資料、不用重新訓練的驗證；再配上 permutation test 就得到每個特徵的重要度。代價是結果會隨亂數種子晃動，樹要加到 G 穩定為止。
AdaBoost 每一輪的權重總和，剛好是指數誤差 exp(−ys) 的總和。這堂課由此推出：基礎演算法找的 gₜ 是近似的函數梯度方向，票數 αₜ 是那個方向上的最佳步長。把指數誤差換成平方誤差，同一套推導變成「每一輪對殘差 yₙ − sₙ 做迴歸，再用單變數線性迴歸定步長」，基礎模型用砍弱的 C&RT 就是 GBDT。
感知器的線性組合做得出 AND、OR，做不出 XOR；再疊一層就可以，這就是多層感知器。這堂課把中間的 sign 換成 tanh、輸出層接線性迴歸，再用連鎖律推出反向傳播：先正向算出每一層的輸出 x，再從輸出層往回算 δ，每個權重的梯度就是前一層的 x 乘上這一層的 δ。最後處理訓練的兩個麻煩：E_in 非凸，初始權重要小而且隨機；d_VC 大約是 O(VD)，要靠 weight elimination 與提早停止防過擬合。
網路疊深之後，每一層只要做一點事，但結構、模型複雜度、最佳化與計算量都變難。這堂課挑初始化與正則化兩件事來講：用 d—d̃—d 的 autoencoder 一層一層預訓練權重，讓每一層先學會保留資訊的編碼；在輸入加人工雜訊訓練，當成一種正則化；最後把 autoencoder 換成線性的，推出最佳的 W 就是 XᵀX 最大的 d̃ 個 eigenvector，資料先減平均就是 PCA。
Gaussian SVM 的結果可以讀成「以支援向量為中心的 Gaussian 做線性投票」，把中心與票數都放開來學就是 RBF 網路。N 筆資料全當中心時，迴歸的最佳票數是 β = Z⁻¹y，訓練誤差剛好是 0，所以要靠 ridge 或把中心減到 M ≪ N 個代表點來正則化；代表點用 k-means 找，它輪流做「每筆資料歸到最近的中心」與「中心改成群內平均」兩步，直到分群不再變動。
推薦系統的輸入只有使用者編號。把編號做 binary vector encoding、丟進拿掉 tanh 的 N-d̃-M 線性網路，假說就是 h(x) = WᵀVx，等於把評分矩陣寫成 R ≈ VᵀW。學 V 與 W 有兩條路：交替最小平方每輪解 M+N 個線性迴歸，SGD 每次只用一筆評分更新一位使用者與一部電影的向量。最後把 boosting、神經網路、RBF 網路、矩陣分解與 k 近鄰收成一張萃取模型的地圖。
技法第 16 堂沒有新模型，它把前 15 堂的模型改用三個問題重新分類：特徵藏在哪裡（kernel、aggregation、extraction、低維投影）、誤差怎麼降下來（梯度、等價問題、拆成多步）、模型太強時怎麼踩煞車（正則化、驗證）。本文用八個點把 PCA 加 AdaBoost-Stump 從頭算完，三個問題各對一次答案；最後保留 Fall 2024 校內課補上的 ReLU、Xavier／He 初始化、momentum、RMSProp 與 Adam。
Fall 2024 技法段有兩份作業和一個期末專題，題目 PDF 都公開。HW6 練 kernel、soft-margin SVM 與 aggregation，程式題用 LIBSVM 在 mnist.scale 的 3 對 7 子問題上數支援向量、算 margin、跑 128 次 validation。HW7 練 bootstrap、impurity、AdaBoost、gradient boosting 與神經網路，程式題是在 madelon 上實作 500 輪 AdaBoost-Stump。期末專題是虛構的 HTMLB 棒球勝負預測，分兩個 Kaggle stage，交一份最多 7 頁的英文報告，至少比較四種方法。沒有官方解答；Kaggle 競賽頁在 2026-09-30 未登入時回 404，校外讀者大概拿不到 HTMLB 資料，只能照同樣的切分方式換一份公開資料自評。