機器學習公式詳解（第2版）

序（王斌 小米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

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

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

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