第一章 統計學習方法概論
1.1 統計學習
- 統計學習由監督學習（主要包括用于分類、标注與回歸問題）、非監督學習、半監督學習、強化學習等組成
- 統計學習方法三要素：模型、政策、算法
- 統計學習方法步驟：1、得到一個有限的訓練資料集合。2、确定包含所有可能的模型的假設空間，即學習模型的集合。3、确定模型選擇的準則，即學習的政策。4、實作求解最優模型的算法，即學習的算法。5、通過學習方法選擇最優模型。6、利用學習的最優模型對新資料進行預測或分析。
1.2 監督學習
監督學習的任務是學習一個模型，使模型能夠對任意給定的輸入，對其相應的輸出做出一個好的預測。每一個具體的輸入時一個執行個體，通常由特征向量表示。這時，所有特征向量存在的空間稱為特征空間，特征空間的每一維對應于一個特征。
輸入輸出變量通常用大寫字母表示，習慣上輸入變量寫作X，輸出變量寫作Y，輸入、輸出變量值用小寫字母表示。
本書預設向量為列向量，
訓練資料集通常表示為：
- 輸入變量與輸出變量均為連續變量的預測問題稱回歸問題
- 輸出變量為有限個離散變量的預測問題稱為分類問題
- 輸入變量與輸出變量均為變量序列的預測問題稱為标注問題
監督學習假設輸入與輸出的随機變量X和Y遵循聯合機率分布P(X,Y),P(X,Y)表示分布函數。對于學習系統來說，聯合機率分布的具體定義是未知的。統計學習假設資料存在一定的同意規律，X和Y具有聯合機率分布的假設就是監督學習關于資料的基本假設。
監督學習的目的在于學習一個又輸入到輸出的映射，這一映射由模型來表示。模型屬于由輸入空間到輸出空間 映射的集合，這個集合就是假設空間。假設空間的确定意味着學習範圍的确定。
監督學習的模型可以是機率模型或非機率模型，由條件機率分布P(Y|X)或決策函數Y=f(X)表示，随具體學習方法而定。
監督學習中，假設訓練資料與測試資料是依聯合機率分布P(X,Y)獨立同分布産生的。
1.3 統計學習的三要素
方法=模型+政策+算法
1.3.1 模型
在監督學習過程中，模型就是所要學習的條件機率分布或決策函數。模型的假設空間包含所有可能的條件機率分布或決策函數。
在本書中，稱由決策函數表示的模型為非機率模型，由條件機率模型表示的模型為機率模型。
假設空間可以定義為決策函數的集合：
其中，X和Y是定義在輸入空間和輸出空間上的變量。這時，F通常是由一個參數向量确定的函數族：
參數向量θ取值于n維歐式空間，稱為參數空間。
假設空間也可定義為條件機率的集合：
其中，X和Y是定義在輸入空間和輸出空間上的變量。這時，F通常是由一個參數向量決定的條件機率分布族：
參數向量θ取值于n維歐式空間，稱為參數空間。
1.3.2 政策
統計學習的目标在于從假設空間中選取最優模型。
首先引入損失函數與風險函數的概念。損失函數度量模型一次預測的好壞，風險函數度量平均意義下模型預測的好壞。
損失函數是f(X)和Y的非負實值函數，記作L(Y,f(X))，其中，f(X)為這個輸出的預測值，Y為真實值。常見損失函數有以下幾種：1-4，見筆記本
由于模型的輸入輸出(X,Y)是随機變量，遵循聯合分布P(X,Y)，是以損失函數的期望是：
這是理論上模型f(X)關于聯合分布P(X,Y)的平均意義下的損失，稱為風險函數或期望損失。學習的目标就是選擇期望風險最小的模型。由于聯合分布是未知的，是以期望不能直接計算，是以才需要進行學習。這樣一來，一方面根據期望風險最國小習模型要用到聯合分布，另一方面聯合分布又是未知的，是以監督學習就成為一個病态問題。
給定一個訓練資料集：
模型f(X)關于訓練資料集的平均損失稱為經驗風險或經驗損失，記作
R e m p R_{emp} Remp
R e m p ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) R_{emp}\left ( f \right )=\frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f\left ( x_{i} \right ) \right ) Remp(f)=N1i=1∑NL(yi,f(xi))
期望風險是模型關于聯合分布的期望損失，經驗風險是模型關于訓練樣本集的平均損失。根據大數定律，當樣本容量趨于無窮時，經驗風險趨于期望風險。是以可以用經驗風險估計期望風險。但是，由于現實中訓練樣本數目有限，甚至很小，是以用經驗風險估計期望風險常常不理想，要對經驗風險進行一定矯正。這就關系到監督學習的兩個基本政策：經驗風險最小化和結構風險最小化。
經驗風險最小化的政策認為，經驗風險最小的模型是最優的模型。根據這一政策，按照經驗風險最小化求最優模型就是求解最優化問題：
m i n 1 N ∑ i = 1 N L ( y i , f ( x i ) ) min \frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f\left ( x_{i} \right ) \right ) minN1i=1∑NL(yi,f(xi))
當樣本容量足夠大時，經驗風險最小化能夠保證有很好的學習效果，在現實中被廣泛采用。比如極大似然估計就是經驗風險最小化的例子。當模型是條件機率分布，損失韓式是對數損失函數時，經驗風險最小化就等價于極大似然估計。 但是當樣本容量小時，經驗風險最小化學習的效果就未必好，可能出現後面叙述的“過拟合”現象。
結構風險最小化是為了防止過拟合而提出的政策。結構風險最小化等價于正則化。結構風險在經驗風險上加上表示模型複雜度的正則化項或罰項。 結構風險的定義是：
R s r m ( f ) = 1 N ∑ i = 1 N L ( y i , f ( x i ) ) + λ J ( f ) R_{srm}\left ( f \right )=\frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f\left ( x_{i} \right ) \right )+\lambda J\left ( f \right ) Rsrm(f)=N1i=1∑NL(yi,f(xi))+λJ(f)
其中，J(f)為模型的複雜度，是定義在假設空間F上的泛函。模型f越複雜J(f)就越大。也就是說，複雜度表示了對複雜模型的懲罰。λ>=0是系數，用于權衡經驗風險和模型複雜度。結構風險小需要經驗風險與模型複雜度同時小。結構風險小的模型往往對訓練資料以及未知的預測資料都有較好的預測。
比如貝葉斯估計中的最大後驗機率估計（MAP）就是結構風險最小化的一個例子。當模型是條件機率分布，損失韓式是對數損失函數、模型複雜度由模型的先驗機率表示時，結構風險最小化就等價于最大後延機率估計。
同理，結構風險最小化的政策認為結構風險最小的模型是最優的模型。這樣，監督學習問題就變成了經驗風險或結構風險函數的最優化問題和。這是經驗或結構風險函數式最優化的目标函數。
1.3.3 算法
算法是指學習模型的具體計算方法。統計學習問題歸結為最優化問題，統計學習的算法成為求解最優化問題的算法。如果最優化問題有顯式的分析解，這個最優化問題就比較簡答。但通常解析解不存在，這就需要用數值計算的方法求解。
1.4 模型評估與模型選擇
選擇模型時，該模型要對已知資料和未知資料都有很好的預測能力。那麼該如何評估模型的好壞呢？下面給出兩個基于損失函數的學習方法評估标準：模型的訓練誤差、模型的預測誤差。
訓練誤差
假設學習到的模型為 Y = f 1 ( X ) Y=f^{1}\left ( X \right ) Y=f1(X)
訓練誤差是模型f1關于訓練資料集的平均損失： R e m p ( f 1 ) = 1 N ∑ i = 1 N L ( y i , f 1 ( x i ) ) R_{emp}\left ( f^{1} \right )=\frac{1}{N}\sum_{i=1}^{N}L\left ( y_{i},f^{1}\left ( x_{i} \right ) \right ) Remp(f1)=N1i=1∑NL(yi,f1(xi))
其中，N是訓練樣本的容量。
測試誤差
測試誤差是模型 Y = f 1 ( X ) Y=f^{1}\left ( X \right ) Y=f1(X)關于測試資料集的平均損失：
e e m p = 1 N ′ ∑ i = 1 N ′ L ( y i , f 1 ( x i ) ) e_{emp}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}L\left ( y_{i},f^{1}\left ( x_{i} \right ) \right ) eemp=N′1i=1∑N′L(yi,f1(xi))
其中N撇是測試樣本容量。
例如，當損失函數是0-1損失（見1.3）時，測試誤差就變成了常見的測試資料集上的誤差率 e t e s t = 1 N ′ ∑ i = 1 N ′ I ( y i ≠ f ′ ( x i ) ) e_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}I\left ( y_{i}\neq f^{'}\left ( x_{i} \right ) \right ) etest=N′1i=1∑N′I(yi=f′(xi))
這裡I為訓示函數，當真實的測試資料不等于模型估計出的資料時，訓示函數的值為1，否則為0。
相應地，常見的測試資料集上的準确率為： r t e s t = 1 N ′ ∑ i = 1 N ′ I ( y i = f ′ ( x i ) ) r_{test}=\frac{1}{N^{'}}\sum_{i=1}^{N^{'}}I\left ( y_{i}=f^{'}\left ( x_{i} \right ) \right ) rtest=N′1i=1∑N′I(yi=f′(xi))
顯然， r t e s t + e t e s t = 1 r_{test}+e_{test}=1 rtest+etest=1
訓練誤差的大小，是判斷給定的問題是不是一個容易學習的問題，不重要。測試誤差反映了學習方法對未知的測試資料集的預測能力，重要。顯然，當給定兩種學習方法時，測試誤差小的方法具有更好的預測能力，更有效。通常，将學習方法對未知資料的預測能力稱為泛化能力（1.6中講）。
過拟合與模型選擇
模型複雜度。參數個數越多，模型的複雜程度越高。假設存在一個“真”模型，我們所選擇的模型應該與真模型有相同個數的參數，所選擇模型的向量與真模型的參數向量應相近。如果一味追求對資料的預測能力，所選模型複雜度往往會比真模型高，這種現象稱為過拟合。過拟合是指學習時選擇的模型所包含的參數過多，以至于這一模型對已知資料預測的很好，對未知資料預測的很差的現象。我們應該在給定模型複雜度的情況下，按照經驗風險最小胡的政策求解模型中的參數。
模型選擇時，不僅應該考慮對已知資料的預測能力，也應該考慮對未知資料的預測能力。随着模型複雜度的增加，訓練誤差會減小，直至趨向于0，但是測試誤差會先減小後增大。應選擇複雜度适當的模型，以達到使測試誤差最小。
1.5 正交化與交叉驗證（常用的模型選擇的方法）
1.5.1 正則化
正則化是結構風險最小化政策的實作。正則化一般有如下形式： L ( y i , f ( x i ) ) + λ J ( f ) L\left ( y_{i},f\left ( x_{i} \right ) \right )+\lambda J\left ( f \right ) L(yi,f(xi))+λJ(f)其中，第一項為經驗風險，第二項是正則化項或罰項，λ>=0為調整兩者之間關系的系數。正則化項一般是模型複雜度的單調遞增函數，一般模型越複雜，正則化值越大。比如，正則化項可以是模型參數的向量的範數。
正則化項在回歸中，損失函數是平方損失，正則化項可以是參數向量L2範數： L ( w ) = 1 N ∑ i = 1 N ( f ( x i ; w ) − y i ) 2 + λ 2 ∥ w ∥ 2 L\left ( w \right )=\frac{1}{N}\sum_{i=1}^{N}\left ( f\left ( x_{i} ;w\right )-y_{i} \right )^{2}+\frac{\lambda }{2}\left \| w \right \|^{2} L(w)=N1i=1∑N(f(xi;w)−yi)2+2λ∥w∥2||w||表示參數向量w的L2範數。正則化項是參數向量的L1範數時： L ( w ) = 1 N ∑ i = 1 N ( f ( x i ; w ) − y i ) 2 + λ ∥ w ∥ 1 L\left ( w \right )=\frac{1}{N}\sum_{i=1}^{N}\left ( f\left ( x_{i} ;w\right )-y_{i} \right )^{2}+\lambda \left \| w \right \|_{1} L(w)=N1i=1∑N(f(xi;w)−yi)2+λ∥w∥1||w||1表示參數向量w的L1範數。
當第1項的經驗風險較小時，模型可能較複雜（有多個非零參數），這時第二項的模型複雜度會較大。正則化的作用是同時選擇經驗風險與模型複雜度同時較小的模型。
奧卡姆剃刀原理：在所有可能選擇的模型中，能夠很好地解釋已知資料并且此模型很簡單，這樣的模型是最好的模型。從貝葉斯估計角度看，正則化項對應于模型的先驗機率。可以假設複雜的模型有較小的先驗機率，簡單的模型有較大的先驗機率。
1.5.2 交叉驗證
當資料充足時，可以将資料集切分為3部分，訓練集（用于訓練模型）、驗證集（用于選擇模型）、測試集（用于最終對學習方法的評估）。我們應選擇對驗證集有最小預測誤差的模型。
但是在實際中，資料是不充足的，是以用到交叉驗證方法，其思想是：重複地使用資料；把給定的資料進行切分，将切分的資料集組合為訓練集與測試集，在此基礎上反複地進行訓練、測試及模型選擇。交叉驗證方法有三種：
- 簡單交叉驗證。首先随機地将已給資料分為兩部分（訓練集和測試集）。例如70%是訓練集，30%為測試集。然後用訓練集在各種條件下（例如，不同的參數個數）訓練模型，進而得到不同模型。最後在測試集上評價各個模型的誤差，選測試誤差最小的那個模型。
- S折交叉驗證。此方法應用最多。将資料集分成互不相交大小相同的S份，其中S-1個資料集的資料用于訓練模型，剩下的一個資料集用于測試模型。将這一過程對可能的S種選擇重複進行，最後選出S次評測中平均測試誤差最小的模型。
- 留一交叉驗證.這種情形是S=N，通常在資料缺乏情況下用。其中N是給定資料集的容量。
1.6 泛化能力
泛化能力是指由該方法學習到的模型對未知資料的預測能力。最常用的是通過測試誤差來評價學習方法的泛化能力。但是由于資料的有限，是以有局限性。
泛化誤差的定義：如果學到的模型是f尖，那麼用這個模型對未知資料預測的誤差即為泛化誤差 R e x p ( f ^ ) = E p [ L ( Y , f ^ ( X ) ) ] = ∫ x ∗ y L ( y , f ^ ( x ) ) P ( x , y ) d x d y R_{exp}\left ( \widehat{f} \right )=E_{p}\left [ L\left ( Y,\widehat{f}\left ( X \right ) \right ) \right ]=\int _{x*y}L\left ( y,\widehat{f}\left ( x \right ) \right )P\left ( x ,y\right )dxdy Rexp(f
)=Ep[L(Y,f
(X))]=∫x∗yL(y,f
(x))P(x,y)dxdy
泛化誤差反映了學習方法的泛化能力，泛化誤差越小，模型越好。事實上，泛化誤差就是所學到的模型的期望風險。
學習方法的泛化能力往往是通過研究泛化誤差的機率上界進行的。即通過比較兩種學習方法的泛化誤差上界的大小來比較他們的優劣。泛化誤差上界通常有以下性質：
- 是樣本容量的函數，當樣本容量增加時，泛化上界趨于0.
- 它是假設空間容量的函數，假設空間容量越大，泛化誤差上界越大。
二分類問題的泛化誤差上界
假設空間是函數的有限集合 £ = { f 1 , f 2 , ⋯ , f d } \pounds =\left \{ f_{1},f_{2},\cdots ,f_{d} \right \} £={f1,f2,⋯,fd}，d是函數個數。fn的泛化能力為： R ( f N ) = E [ L ( Y , f N ( X ) ) ] R\left ( f_{N} \right )=E\left [ L\left ( Y,f_{N}\left ( X \right ) \right ) \right ] R(fN)=E[L(Y,fN(X))]
對于二分類問題，當假設空間是有限個函數的集合，對任意一個函數f，至少以機率1-δ，以下不等式成立： R ( f ) ⩽ R ^ ( f ) + ε ( d , N , δ ) R\left (f \right )\leqslant \widehat{R}\left ( f \right )+\varepsilon \left ( d,N,\delta \right ) R(f)⩽R
(f)+ε(d,N,δ) ε ( d , N , δ ) = 1 2 N ( l o g d + l o g 1 δ ) \varepsilon \left ( d,N,\delta \right )=\sqrt{\frac{1}{2N}\left ( logd+log\frac{1}{\delta } \right )} ε(d,N,δ)=2N1(logd+logδ1)
不等式左端是泛化誤差，右側為泛化誤差上界。在泛化誤差上界中，第一項是訓練誤差，訓練誤差越小，泛化誤差越小。第二項是N的單調遞減函數，當N趨于無窮時趨于0.同時它也是sqrt（logd）階的函數，假設空間包含的函數越多，其值越大。
1.7 生成模型與判别模型
監督學習的任務就是學習一個模型，應用這個模型，對給定的輸入預測相應的輸出。這個模型的一般形式為決策函數Y=f(X)，或者條件機率分布P(Y|X).
監督學習的方法可分為生成方法和判别方法。所學到的模型分别稱為生成模型與判别模型。
生成方法由資料學習聯合機率分布P(X,Y),生成模型為 P ( Y ∣ X ) = P ( X , Y ) P ( X ) P(Y|X)=\frac{P\left ( X,Y \right )}{P\left ( X \right )} P(Y∣X)=P(X)P(X,Y)典型的生成模型有樸素貝葉斯法和隐馬爾科夫模型。
判别方法由資料直接學習決策函數f(X)或者條件機率分布P(Y|X)作為預測的模型，即判别模型。判别方法關心的問題是給定輸入的X，應該預測出什麼樣的Y。典型的判别模型有：k近鄰法，感覺機，決策樹，邏輯斯蒂回歸模型，最大熵模型，支援向量機，提升方法和條件随機場等。
生成方法特點：能還原聯合機率分布、學習收斂速度快（當樣本容量增加時，學到的模型可以更快地收斂于真實模型）、當存在隐變量時，仍可以用生成學習方法（判别方法不能用）。
判别方法特點：直接學習決策函數f(X)或者條件機率分布P(Y|X)，直接面對預測，學習的準确率更高，可以對資料進行各種程度上的抽象、定義特征并使用特征，可以簡化學習問題。
1.8 分類問題
當輸出的Y取有限個離散值時，預測問題就變成分類問題。輸入變量X可以離散可以連續。分類問題包括兩個過程：
- 學習。通過訓練資料集利用有效的學習方法學習一個分類器。
- 分類。通過分類器，對新的輸入進行分類。
評價分類器性能的名額一般是分類準确率（分類器正确分類的樣本數與總樣本數之比）。對于二分類問題，常用的評價名額是精确率與召回率。通常關注的類為正類，其他類為負類。
TP(true positive)–将正類預測為正類數 FN(false negative)–将正類預測為負類數
FP–将負類預測為負類數 TN–将負類預測為負類數
精确率定義為： P = T P T P + F P P=\frac{TP}{TP+FP} P=TP+FPTP召回率定義為： R = T P T P + F N R=\frac{TP}{TP+FN} R=TP+FNTP
F1值是精确率和召回率的調和均值，即： 2 F 1 = 1 P + 1 R \frac{2}{F1}=\frac{1}{P}+\frac{1}{R} F12=P1+R1 F 1 = 2 T P 2 T P + F P + F N F1=\frac{2TP}{2TP+FP+FN} F1=2TP+FP+FN2TP當精确率和召回率都高時，F1也會高。
1.9 标注問題
标準問題是分類問題的推廣，也是更複雜的結構預測問題的簡單形式。标注問題的輸入是一個觀測序列，輸出是一個标記序列或狀态序列。标注問題的目标在于學習一個模型，使它能夠對觀測序列給出标記序列作為預測。注意，可能的标記個數是有限的，但其組合縮成的标記序列的個數是依序列長度呈指數級增長的。
給定訓練資料集： T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T=\left \{ \left ( x_{1},y_{1} \right ), \left ( x_{2},y_{2} \right ), \cdots , \left ( x_{N},y_{N} \right ) \right \} T={(x1,y1),(x2,y2),⋯,(xN,yN)}輸入觀測序列（i=1，…，N）： x i = ( x i ( 1 ) , x i ( 2 ) , ⋯ , x i ( n ) ) T x_{i}=\left ( x_{i}^{\left ( 1 \right )} ,x_{i}^{\left ( 2 \right )},\cdots ,x_{i}^{\left ( n \right )} \right )^{T} xi=(xi(1),xi(2),⋯,xi(n))T相應的輸出标記序列（n是序列的長度）： y i = ( y i ( 1 ) , y i ( 2 ) , ⋯ , y i ( n ) ) T y_{i}=\left ( y_{i}^{\left ( 1 \right )} ,y_{i}^{\left ( 2 \right )},\cdots ,y_{i}^{\left ( n \right )} \right )^{T} yi=(yi(1),yi(2),⋯,yi(n))T學習系統基于訓練資料集建構一個模型，表示為條件機率分布: P ( Y ( 1 ) , Y ( 2 ) , ⋯ , Y ( n ) ∣ X ( 1 ) , X ( 2 ) , ⋯ , X ( n ) ) P\left ( Y^{\left ( 1 \right )} ,Y^{\left ( 2 \right )} ,\cdots ,Y^{\left ( n \right )}|X^{\left ( 1 \right )} ,X^{\left ( 2 \right )} ,\cdots ,X^{\left ( n \right )} \right ) P(Y(1),Y(2),⋯,Y(n)∣X(1),X(2),⋯,X(n))這裡每個Xi取值為所有可能的觀測，每個Yi取值為所有可能的标記，一般n遠小于N。标注系統按照學習得到的條件機率分布模型，對新的輸入觀測序列找到相應的輸出标記序列。對于每個 x N + 1 = ( x N + 1 ( 1 ) , x N + 1 ( 2 ) , ⋯ , x N + 1 ( n ) ) T x_{N+1}=\left ( x_{N+1}^{\left ( 1 \right )} ,x_{N+1}^{\left ( 2 \right )},\cdots ,x_{N+1}^{\left ( n \right )} \right )^{T} xN+1=(xN+1(1),xN+1(2),⋯,xN+1(n))T找到使條件機率P（N+1）最大的标記序列 y N + 1 = ( y N + 1 ( 1 ) , y N + 1 ( 2 ) , ⋯ , y N + 1 ( n ) ) T y_{N+1}=\left ( y_{N+1}^{\left ( 1 \right )} ,y_{N+1}^{\left ( 2 \right )},\cdots ,y_{N+1}^{\left ( n \right )} \right )^{T} yN+1=(yN+1(1),yN+1(2),⋯,yN+1(n))T評價标注模型的名額與評價分類模型的名額一樣，常用的有标注準确率、精确率和召回率。
标注常用的統計學習方法有：隐馬爾科夫模型、條件随機場。
1.10 回歸問題
按照輸入變量的個數，分為一進制回歸和多元回歸。按照輸入變量和輸出變量之間的關系的類型，可分為線性回歸和非線性回歸。