機器學習公式詳解 第2版

謝文睿
北京工業大學碩士，Datawhale開源項目負責人，百度算法工程師，研究方向為機器學習與自然語言處理。

秦州
康奈爾大學計算機碩士，Datawhale成員，阿里算法專家，研究方向為圖計算與自然語言處理，
 在NeurIPS、AAAI、CIKM等會議上錄用多篇學術論文並獲得CIKM 2019 應用論文獎。

賈彬彬
工學博士，蘭州理工大學講師，研究方向為機器學習與數據挖掘，
在TKDE、TNNLS、PRJ、ICML、AAAI等期刊和會議上共發表學術論文十餘篇，並擔任ICML、
NeurIPS、ICLR、AAAI、IJCAI 等會議的程序委員會委員（PC Member）。

序（王斌 小米AI 實驗室主任、NLP 席科學家）
前言
主要符號表
資源與支持
1 章緒論 1
1.1 引言 1
1.2 基本術語 1
1.3 假設空間 5
1.4 歸納偏好 5
1.4.1 式(1.1) 和式(1.2) 的解釋 6

2 章模型評估與選擇 8
2.1 經驗誤差與過擬合 8
2.2 評估方法 9
2.2.1 算法參數（超參數）與模型參數 10
2.2.2 驗證集 10
2.3 性能度量 11
2.3.1 式(2.2) ～ 式(2.7) 的解釋 11
2.3.2 式(2.8) 和式(2.9) 的解釋 11
2.3.3 圖2.3 的解釋 11
2.3.4 式(2.10) 的推導 11
2.3.5 式(2.11) 的解釋 12
2.3.6 式(2.12) ～ 式(2.17) 的解釋 13
2.3.7 式(2.18) 和式(2.19) 的解釋 13
2.3.8 式(2.20) 的推導 14
2.3.9 式(2.21) 和式(2.22) 的推導 16
2.3.10 式(2.23) 的解釋 18
2.3.11 式(2.24) 的解釋 19
2.3.12 式(2.25) 的解釋 20
2.4 比較檢驗 22
2.4.1 式(2.26) 的解釋 22
2.4.2 式(2.27) 的推導 23
2.5 偏差與方差 26
2.5.1 式(2.37) ～ 式(2.42) 的推導 26
參考文獻 29

3 章線性模型 30
3.1 基本形式 30
3.2 線性回歸 30
3.2.1 屬性數值化 30
3.2.2 式(3.4) 的解釋 31
3.2.3 式(3.5) 的推導 32
3.2.4 式(3.6) 的推導 32
3.2.5 式(3.7) 的推導 33
3.2.6 式(3.9) 的推導 35
3.2.7 式(3.10) 的推導 36
3.2.8 式(3.11) 的推導 36
3.3 對率回歸 39
3.3.1 式(3.27) 的推導 39
3.3.2 梯度下降法 41
3.3.3 牛頓法 42
3.3.4 式(3.29) 的解釋 44
3.3.5 式(3.30) 的推導 44
3.3.6 式(3.31) 的推導 45
3.4 線性判別分析46
3.4.1 式(3.32) 的推導 46
3.4.2 式(3.37) ～ 式(3.39) 的推導 47
3.4.3 式(3.43) 的推導 48
3.4.4 式(3.44) 的推導 48
3.4.5 式(3.45) 的推導 49
3.5 多分類學習 52
3.5.1 圖3.5 的解釋 52
3.6 類別不平衡問題 52
參考文獻 52

4 章決策樹 53
4.1 基本流程 53
4.2 劃分選擇 54
4.2.1 式(4.1) 的解釋 54
4.2.2 式(4.2) 的解釋 58
4.2.3 式(4.4) 的解釋 58
4.2.4 式(4.5) 的推導 59
4.2.5 式(4.6) 的解釋 59
4.3 剪枝處理 62
4.4 連續值與缺失值 63
4.4.1 式(4.7) 的解釋 63
4.4.2 式(4.8) 的解釋 64
4.4.3 式(4.12) 的解釋 64
4.5 多變量決策樹64
4.5.1 圖4.10 的解釋 65
4.5.2 圖4.11 的解釋 65
參考文獻 66

5 章神經網絡 67
5.1 神經元模型 67
5.2 感知機與多層網絡 67
5.2.1 式(5.1) 和式(5.2) 的推導 67
5.2.2 圖5.5 的解釋 70
5.3 誤差逆傳播算法 70
5.3.1 式(5.10) 的推導 70
5.3.2 式(5.12) 的推導 70
5.3.3 式(5.13) 的推導 71
5.3.4 式(5.14) 的推導 72
5.3.5 式(5.15) 的推導 73
5.4 全局小與局部小 73
5.5 其他常見神經網絡 73
5.5.1 式(5.18) 的解釋 73
5.5.2 式(5.20) 的解釋 73
5.5.3 式(5.22) 的解釋 74
5.5.4 式(5.23) 的解釋 74
5.6 深度學習 74
5.6.1 什麼是深度學習 75
5.6.2 深度學習的起源 75
5.6.3 怎麼理解特徵學習75
參考文獻 75

6 章支持向量機 77
6.1 間隔與支持向量 77
6.1.1 圖6.1 的解釋 77
6.1.2 式(6.1) 的解釋 77
6.1.3 式(6.2) 的推導 78
6.1.4 式(6.3) 的推導 78
6.1.5 式(6.4) 的推導 80
6.1.6 式(6.5) 的解釋 80
6.2 對偶問題 80
6.2.1 凸優化問題 80
6.2.2 KKT 條件 80
6.2.3 拉格朗日對偶函數81
6.2.4 拉格朗日對偶問題82
6.2.5 式(6.9) 和式(6.10) 的推導 85
6.2.6 式(6.11) 的推導 85
6.2.7 式(6.13) 的解釋 86
6.3 核函數 87
6.3.1 式(6.22) 的解釋 87
6.4 軟間隔與正則化 87
6.4.1 式(6.35) 的推導 87
6.4.2 式(6.37) 和式(6.38) 的推導 87
6.4.3 式(6.39) 的推導 87
6.4.4 式(6.40) 的推導 88
6.4.5 對率回歸與支持向量機的關係 88
6.4.6 式(6.41) 的解釋 89
6.5 支持向量回歸89
6.5.1 式(6.43) 的解釋 89
6.5.2 式(6.45) 的推導 90
6.5.3 式(6.52) 的推導 91
6.6 核方法 92
6.6.1 式(6.57) 和式(6.58) 的解釋 92
6.6.2 式(6.65) 的推導 92
6.6.3 式(6.66) 和式(6.67) 的解釋 93
6.6.4 式(6.70) 的推導 94
6.6.5 核對率回歸 98
參考文獻 99

7 章貝葉斯分類器 100
7.1 貝葉斯決策論 100
7.1.1 式(7.5) 的推導 100
7.1.2 式(7.6) 的推導 100
7.1.3 判別式模型與生成式模型100
7.2 大似然估計 101
7.2.1 式(7.12) 和式(7.13) 的推導 101
7.3 樸素貝葉斯分類器 104
7.3.1 式(7.16) 和式(7.17) 的解釋 104
7.3.2 式(7.18) 的解釋 104
7.3.3 貝葉斯估計 105
7.3.4 Categorical 分佈 105
7.3.5 Dirichlet 分佈 106
7.3.6 式(7.19) 和式(7.20) 的推導 106
7.4 半樸素貝葉斯分類器110
7.4.1 式(7.21) 的解釋 110
7.4.2 式(7.22) 的解釋 111
7.4.3 式(7.23) 的推導 111
7.4.4 式(7.24) 和式(7.25) 的推導 112
7.5 貝葉斯網 112
7.5.1 式(7.27) 的解釋 112
7.6 EM 算法 113
7.6.1 Jensen 不等式113
7.6.2 EM 算法的推導 113
參考文獻 121

8 章集成學習 122
8.1 個體與集成 123
8.1.1 式(8.1) 的解釋 123
8.1.2 式(8.2) 的解釋 123
8.1.3 式(8.3) 的推導 123
8.2 Boosting 124
8.2.1 式(8.4) 的解釋 125
8.2.2 式(8.5) 的解釋 125
8.2.3 式(8.6) 的推導 126
8.2.4 式(8.7) 的推導 126
8.2.5 式(8.8) 的推導 127
8.2.6 式(8.9) 的推導 127
8.2.7 式(8.10) 的解釋 128
8.2.8 式(8.11) 的推導 128
8.2.9 式(8.12) 的解釋 129
8.2.10 式(8.13) 的推導 129
8.2.11 式(8.14) 的推導 130
8.2.12 式(8.16) 的推導 131
8.2.13 式(8.17) 的推導 131
8.2.14 式(8.18) 的推導 132
8.2.15 式(8.19) 的推導 132
8.2.16 AdaBoost 的個人推導 133
8.2.17 進一步理解權重更新公式137
8.2.18 能夠接受帶權樣本的基學習算法 139
8.3 Bagging 與隨機森林 140
8.3.1 式(8.20) 的解釋 140
8.3.2 式(8.21) 的推導 140
8.3.3 隨機森林的解釋 141
8.4 結合策略 141
8.4.1 式(8.22) 的解釋 141
8.4.2 式(8.23) 的解釋 141
8.4.3 硬投票和軟投票的解釋 141
8.4.4 式(8.24) 的解釋 142
8.4.5 式(8.25) 的解釋 142
8.4.6 式(8.26) 的解釋 142
8.4.7 元學習器的解釋 142
8.4.8 Stacking 算法的解釋 143
8.5 多樣性 143
8.5.1 式(8.27) 的解釋 143
8.5.2 式(8.28) 的解釋 143
8.5.3 式(8.29) 的解釋 143
8.5.4 式(8.30) 的解釋 144
8.5.5 式(8.31) 的推導 144
8.5.6 式(8.32) 的解釋 144
8.5.7 式(8.33) 的解釋 145
8.5.8 式(8.34) 的解釋 145
8.5.9 式(8.35) 的解釋 145
8.5.10 式(8.36) 的解釋 145
8.5.11 式(8.40) 的解釋 145
8.5.12 式(8.41) 的解釋 146
8.5.13 式(8.42) 的解釋 146
8.5.14 多樣性增強的解釋 146
8.6 Gradient Boosting、GBDT、XGBoost的聯繫與區別 147
8.6.1 從梯度下降的角度解釋AdaBoost 147
8.6.2 梯度提升 149
8.6.3 梯度提升樹(GBDT) 151
8.6.4 XGBoost 152
參考文獻 152

9 章聚類 153
9.1 聚類任務 153
9.2 性能度量 153
9.2.1 式(9.5) 的解釋 153
9.2.2 式(9.6) 的解釋 155
9.2.3 式(9.7) 的解釋 155
9.2.4 式(9.8) 的解釋 156
9.2.5 式(9.12) 的解釋 156
9.3 距離計算 156
9.3.1 式(9.21) 的解釋 156
9.4 原型聚類 157
9.4.1 式(9.28) 的解釋 157
9.4.2 式(9.29) 的解釋 157
9.4.3 式(9.30) 的解釋 158
9.4.4 式(9.31) 的解釋 159
9.4.5 式(9.32) 的解釋 159
9.4.6 式(9.33) 的推導 160
9.4.7 式(9.34) 的推導 161
9.4.8 式(9.35) 的推導 162
9.4.9 式(9.36) 的解釋 164
9.4.10 式(9.37) 的推導 164
9.4.11 式(9.38) 的推導 165
9.4.12 圖9.6 的解釋 166
9.5 密度聚類 166
9.5.1 密度直達、密度可達與密度相連 167
9.5.2 圖9.9 的解釋 168
9.6 層次聚類 168

10 章降維與度量學習 170
10.1 預備知識 170
10.1.1 符號約定 170
10.1.2 矩陣與單位陣、向量的乘法170
10.2 矩陣的F 範數與跡 171
10.3 k 近鄰學習 173
10.3.1 式(10.1) 的解釋 173
10.3.2 式(10.2) 的推導 174
10.4 低維嵌入 175
10.4.1 圖10.2 的解釋 175
10.4.2 式(10.3) 的推導 175
10.4.3 式(10.4) 的推導 176
10.4.4 式(10.5) 的推導 177
10.4.5 式(10.6) 的推導 177
10.4.6 式(10.10) 的推導 178
10.4.7 式(10.11) 的解釋 179
10.4.8 圖10.3 關於MDS 算法的解釋179
10.5 主成分分析180
10.5.1 式(10.14) 的推導 180
10.5.2 式(10.16) 的解釋 184
10.5.3 式(10.17) 的推導 186
10.5.4 根據式(10.17) 求解式(10.16) 188
10.6 核化線性降維 188
10.6.1 式(10.19) 的解釋 189
10.6.2 式(10.20) 的解釋 189
10.6.3 式(10.21) 的解釋 190
10.6.4 式(10.22) 的解釋 190
10.6.5 式(10.24) 的推導 190
10.6.6 式(10.25) 的解釋 191
10.7 流形學習 191
10.7.1 等度量映射(Isomap) 的解釋 191
10.7.2 式(10.28) 的推導 192
10.7.3 式(10.31) 的推導 194
10.8 度量學習 196
10.8.1 式(10.34) 的解釋 196
10.8.2 式(10.35) 的解釋 197
10.8.3 式(10.36) 的解釋 197
10.8.4 式(10.37) 的解釋 198
10.8.5 式(10.38) 的解釋 198
10.8.6 式(10.39) 的解釋 198
參考文獻 199

11 章特徵選擇與稀疏學習 200
11.1 子集搜索與評價 200
11.1.1 式(11.1) 的解釋 200
11.1.2 式(11.2) 的解釋 200
11.2 過濾式選擇201
11.3 包裹式選擇201
11.4 嵌入式選擇與L1 正則化 202
11.4.1 式(11.5) 的解釋 202
11.4.2 式(11.6) 的解釋 202
11.4.3 式(11.7) 的解釋 203
11.4.4 式(11.8) 的解釋 203
11.4.5 式(11.9) 的解釋 203
11.4.6 式(11.10) 的推導 203
11.4.7 式(11.11) 的解釋 205
11.4.8 式(11.12) 的解釋 205
11.4.9 式(11.13) 的解釋 205
11.4.10 式(11.14) 的推導 205
11.5 稀疏表示與字典學習 208
11.5.1 式(11.15) 的解釋 208
11.5.2 式(11.16) 的解釋 208
11.5.3 式(11.17) 的推導 208
11.5.4 式(11.18) 的推導 208
11.6 壓縮感知 213
11.6.1 式(11.21) 的解釋 213
11.6.2 式(11.25) 的解釋 213
參考文獻 214

12 章計算學習理論 215
12.1 基礎知識 215
12.1.1 式(12.1) 的解釋 216
12.1.2 式(12.2) 的解釋 216
12.1.3 式(12.3) 的解釋 216
12.1.4 式(12.4) 的解釋 216
12.1.5 式(12.5) 和式(12.6) 的解釋 216
12.1.6 式(12.7) 的解釋 217
12.2 PAC 學習 217
12.2.1 式(12.9) 的解釋 218
12.3 有限假設空間 218
12.3.1 式(12.10) 的解釋 219
12.3.2 式(12.11) 的解釋 219
12.3.3 式(12.12) 的推導 219
12.3.4 式(12.13) 的解釋 220
12.3.5 式(12.14) 的推導 220
12.3.6 引理12.1 的解釋 221
12.3.7 式(12.18) 的推導 221
12.3.8 式(12.19) 的推導 221
12.3.9 式(12.20) 的解釋 222
12.4 VC 維223
12.4.1 式(12.21) 的解釋 223
12.4.2 式(12.22) 的解釋 223
12.4.3 式(12.23) 的解釋 224
12.4.4 引理12.2 的解釋 224
12.4.5 式(12.28) 的解釋 226
12.4.6 式(12.29) 的解釋 227
12.4.7 式(12.30) 的解釋 227
12.4.8 定理12.4 的解釋 228
12.5 Rademacher 複雜度 229
12.5.1 式(12.36) 的解釋 229
12.5.2 式(12.37) 的解釋 229
12.5.3 式(12.38) 的解釋 230
12.5.4 式(12.39) 的解釋 230
12.5.5 式(12.40) 的解釋 231
12.5.6 式(12.41) 的解釋 231
12.5.7 定理12.5 的解釋 231
12.6 定理12.6 的解釋 233
12.6.1 式(12.52) 的證明 235
12.6.2 式(12.53) 的推導 235
12.7 穩定性 235
12.7.1 泛化損失/經驗損失/留一損失的解釋 236
12.7.2 式(12.57) 的解釋 236
12.7.3 定理12.8 的解釋 236
12.7.4 式(12.60) 的推導 237
12.7.5 經驗損失小化 237
12.7.6 定理12.9 的證明的解釋 237
參考文獻 238

13 章半監督學習 240
13.1 未標記樣本240
13.2 生成式方法240
13.2.1 式(13.1) 的解釋 241
13.2.2 式(13.2) 的推導 241
13.2.3 式(13.3) 的推導 242
13.2.4 式(13.4) 的推導 242
13.2.5 式(13.5) 的解釋 242
13.2.6 式(13.6) 的解釋 243
13.2.7 式(13.7) 的解釋 244
13.2.8 式(13.8) 的解釋 246
13.3 半監督SVM 248
13.3.1 圖13.3 的解釋 248
13.3.2 式(13.9) 的解釋 248
13.3.3 圖13.4 的解釋 248
13.3.4 式(13.10) 的解釋 250
13.4 圖半監督學習 250
13.4.1 式(13.12) 的推導 251
13.4.2 式(13.13) 的推導 252
13.4.3 式(13.14) 的推導 253
13.4.4 式(13.15) 的推導 253
13.4.5 式(13.16) 的解釋 254
13.4.6 式(13.17) 的推導 254
13.4.7 式(13.18) 的解釋 254
13.4.8 式(13.20) 的解釋 254
13.4.9 式(13.21) 的推導 255
13.5 基於分歧的方法 259
13.5.1 圖13.6 的解釋 259
13.6 半監督聚類260
13.6.1 圖13.7 的解釋 260
13.6.2 圖13.9 的解釋 260
參考文獻 260

14 章概率圖模型 261
14.1 隱馬爾可夫模型 261
14.1.1 生成式模型和判別式模型261
14.1.2 式(14.1) 的推導 262
14.1.3 隱馬爾可夫模型的三組參數263
14.2 馬爾可夫隨機場 263
14.2.1 式(14.2) 和式(14.3) 的解釋 263
14.2.2 式(14.4) ～ 式(14.7) 的推導 264
14.2.3 馬爾可夫毯 264
14.2.4 勢函數 265
14.2.5 式(14.8) 的解釋 265
14.2.6 式(14.9) 的解釋 265
14.3 條件隨機場265
14.3.1 式(14.10) 的解釋 265
14.3.2 式(14.11) 的解釋 266
14.4 學習與推斷266
14.4.1 式(14.14) 的推導 266
14.4.2 式(14.15) 和式(14.16) 的推導 266
14.4.3 式(14.17) 的解釋 267
14.4.4 式(14.18) 的推導 267
14.4.5 式(14.19) 的解釋 267
14.4.6 式(14.20) 的解釋 268
14.4.7 式(14.22) 的推導 268
14.4.8 圖14.8 的解釋 269
14.5 近似推斷 269
14.5.1 式(14.21) ～ 式(14.25) 的解釋 269
14.5.2 式(14.26) 的解釋 270
14.5.3 式(14.27) 的解釋 270
14.5.4 式(14.28) 的推導 270
14.5.5 吉布斯採樣與MH 算法 271
14.5.6 式(14.29) 的解釋 272
14.5.7 式(14.30) 的解釋 272
14.5.8 式(14.31) 的解釋 273
14.5.9 式(14.32) ～ 式(14.34) 的推導 273
14.5.10 式(14.35) 的解釋 274
14.5.11 式(14.36) 的推導 274
14.5.12 式(14.37) 和式(14.38) 的解釋 276
14.5.13 式(14.39) 的解釋 277
14.5.14 式(14.40) 的解釋 277
14.6 話題模型 278
14.6.1 式(14.41) 的解釋 278
14.6.2 式(14.42) 的解釋 279
14.6.3 式(14.43) 的解釋 279
14.6.4 式(14.44) 的解釋 279
參考文獻 279

15 章規則學習280
15.1 剪枝優化 280
15.1.1 式(15.2) 和式(15.3) 的解釋 280
15.2 歸納邏輯程序設計 281
15.2.1 式(15.6) 的解釋 281
15.2.2 式(15.7) 的推導 281
15.2.3 式(15.9) 的推導 281
15.2.4 式(15.10) 的解釋 281
15.2.5 式(15.11) 的解釋 281
15.2.6 式(15.12) 的解釋 282
15.2.7 式(15.13) 的解釋 282
15.2.8 式(15.16) 的推導 282

16 章強化學習283
16.1 任務與獎賞283
16.2 K-搖臂*博機 283
16.2.1 式(16.2) 和式(16.3) 的推導 283
16.2.2 式(16.4) 的解釋 283
16.3 有模型學習284
16.3.1 式(16.7) 的解釋 284
16.3.2 式(16.8) 的推導 284
16.3.3 式(16.10) 的推導 285
16.3.4 式(16.14) 的解釋 285
16.3.5 式(16.15) 的解釋 285
16.3.6 式(16.16) 的推導 285
16.4 免模型學習286
16.4.1 式(16.20) 的解釋 286
16.4.2 式(16.23) 的解釋 286
16.4.3 式(16.31) 的推導 286
16.5 值函數近似287
16.5.1 式(16.33) 的解釋 287
16.5.2 式(16.34) 的推導 287
參考文獻 287