機器學習原理（2）

機器學習的統計模型

任何一門學科都是由三個部分組成的：學習/研究的對象、對象之間的結合關係、控製這些關係的準則/公理。數學研究的是數與形，關係有代數、順序和拓撲（集合之間的包含），公理是針對具體的量/形而提出的；比如距離三公理：非負、對稱、三角不等式。物理研究自然物體（人類可見可感知的東西），物體之間如何分分合合，控製準則是力或能量。

機器學習是一門跨越多種學科的綜合學科；涉及概率統計、線性代數、數學分析、數理邏輯、圖論、優化理論、哲學、信息論、計算複雜性、控製論、生物學，等等。其研究對象是任務/問題的集合，目的是要搞清楚：什麽是學習，機器能夠學習嗎？怎麽學習？結合關係表現為算法，它揭示知識之間的邏輯關係；給出各種任務的快捷算法是機器學習的根本目標。控製公理基於人類或動物的道義準則或價值觀；對於魔道，吃人的算法才是公理。

一個算法包括輸入和輸出兩部分。對於一個能夠學習的算法，其輸入包括三部分：（1）需要認識的對象集X，比如一個地區的某個物種。在數字化的世界裏，物種需要用一些數量特征來刻畫；比如顏色、密度、表麵張力等，這些信息可以用向量或張量來表示。（2）需要識別的特征Y，比如物種的味道、人的好壞、動物的凶殘程度等。特征的量化表示不可能準確，實際上是學習者主觀意識的反映，數學上可以看作是一個隨機變量。（3）訓練數據集T = {(xi, yi): i = 1, 2, …, n} ；也就是集合X × Y的一個隨機樣本。

學習算法的輸出是一個預測規則p：X →Y，要對X中的每個對象x給出一個標識y。基於訓練集T，自然要求p(xi) = yi，i= 1, 2, …, n。從X到Y的所有對應規則/函數的集合記為Y^X, 它的基數為|Y|^|X|。當X為無限集時，函數集達到連續基數c；即使當X，Y為有限集時，計算複雜度也可能是NP（非多項式）的。我們可以基於經驗或計算的簡便，提出一個預先假定的規則集H（ 潛規則) ，比如多項式函數甚至線性函數，把H嵌入到實數集R，再從R映射到Y。一個H所代表的，就是一種學習模型；一個算法是否具有學習能力，指的是能否從H中找出最佳的一個預測規則。

對於一個學習者，全體對象集X是未知的，其中個體x的正確標識 y =: b(x)  Y更是未知的。我們把 (x，y) = z看成一個隨機向量，滿足某種未知的概率分布D；樣本S假設是獨立、隨機同分布的，所滿足的分布記為D^n。D在X上的邊緣分布可以記為DX。

我們需要給出p的評估標準（Performance measure）。用p(x) 去預測x的正確標識y時，會有風險（risk）。風險函數R(p, D)) 通常定義為平均損失：E {L(p, z): z ~ D} = Integral {L(p, z) dF(z)}，其中F(z) 是z ~ D的累計概率分布函數；損失函數L(p，(x, y))有多種定義方法，任何表明p(x)與y的偏差的函數都行；比如數量的平方損失 (p(x) – y)^2, 向量的模損失 ||p(x) – y||，0-1損失 L = 0, 若p(x) = y; L = 1, 若 p(x) ≠ y。

為了評估預測p的質量，我們提出一個精度參數ε>0, 如果R(p, D) ≤ ε ，就稱p是近似正確的；如果R(p, D) > ε , 則p稱為學習者/p的失敗。但分布D是未知的，風險函數R的值是無法計算的。我們隻能用樣本/訓練數據集T去估計和驗證。

基於某個樣本T的風險函數R(p，T)，其值定義為 1/|T| { Sigma [L(p, (xi, yi)): i = 1, 2, …, |T|]} 。如果對該樣本T，恰有p(xi) = yi對所有i，則R值為0；T對p過度 “適應” 了。然而，對於其它樣本S, 就不一定有R(p, S) = 0了。我們需要的是接近R(p, D)的樣本S：|R(p, S) – R(p, D)| ≤ ε。如果對於任何未知分布D，都有|R(p, S) – R(p, D)| ≤ ε, 樣本S就具有 “ε-代表性”。在樣本空間X × Y中，取到一個具有 “ε-代表性 “的樣本的概率的下限，稱為學習規則集H的信任度, 1 – δ。δ也是取到非代表性樣本的概率上限。

一個學習任務/模型就表示為了：給定一個三元組 (Z, H, L), Z =X × Y，要求一個對應規則p, 使得：對於任意給定的 ε, δ, 都存在一個正整數N(ε, δ)（稱為樣本複雜度），當樣本數 n = |S| ≥ N時，對於Z上的任何分布D，都有，事件|R(p, S) – R(p, D)| >  發生的概率P，小於δ；此時就稱預測函數p是可能近似正確的（Probably Approximately Correct）, 假設規則集H是PAC可學習的。

找p的辦法有多種，一種是使得最大平均損失極小化，也就是概率論中極小極大估計的思想。對於事先選定的訓練集T = {（Tx, Ty）} ，可以要求p(Tx) = Ty；那就有R(p, T) = 0。對於任何一個獨立同分布的樣本S ~ D^n，樣本數n = |S| > |T|; 在上確界Sup {R(p, S): S ~ D^n }中，尋找使其達到極小的預測函數p*: Sup { R(p*, S): S ~ D^n} = Inf _{p  H} [Sup { R(p, S): S ~ D^n}]；這就轉化為了和式的條件極值問題，可以用線性規劃、Lagrange乘子法、變分法等求解。

可以證明，當H為有限集合，Y隻有二元標識{0， 1}時，可以取N = [ln(2|H|/δ)]/2ε²；也就是說，有限的潛規則集都是PAC可學習的。

對於無窮集H（X必為無窮集），可以把它先限製在X的一個有限子集C上：H|C = {h(C): h  H}, 其基數為|Y|^|C|。如果H|C包含了從C到Y的所有函數，就稱H遮蔽（shatters）C。能夠被H遮蔽的有限集C的最大基數|C|, 稱為H的VC維度（由Valdimir Vapnik 和 Alexey Chervonenkis在1970年提出）。如果H可以遮蔽任意大的子集C，它的VC維度就是無窮大。可以證明，H是PAC可學習的，當且僅當它的VC維度是有限的。

這在潛規則集H與樣本複雜度|S|之間就得有一個折衷（trade off）：選擇廣泛與低風險不可兼得；因為沒有免費的午餐。具體來說，對於任何一個無限集X和二元標識Y = {0， 1}，設L為0-1損失函數；A是任何一個推導預測函數p的算法；一定存在X × Y上的一個概率分布D，使得，有一個預測函數f滿足R（f, D） = 0, 以及至少1/7的概率取到一個樣本S，其基數< |X|/2，滿足R(p，S) >=1/8。

我們還可以使用Bayes估計：憑經驗或專家的意見，對X提出某類先驗分布DX（比如均勻分布、正態分布等），按照預定規則集H（其中的函數必須滿足訓練數據集T）去計算Y（標識符）的分布（可以稱為後驗分布），然後在H中選取一個使得風險函數R(p, D)達到最小的預測p。再選擇一個有代表性的樣本S，來加以驗證: R(p, S) < R(p, D) + ε。

按照經驗風險極小化（ERM）方法推導預測函數的算法A，還需要考慮其運行時間/計算複雜度。對於給定的一個學習任務（Z，H， L），以及學習精度和信任度ε, δ ∈ (0, 1)，我們說算法A在時間O（F(ε, δ）)內完成了任務，如果（1）A本身的運算次數不超過F的一個常數倍，（2）A導出的預測函數p給任何一個樣本S|X作出標識的運算次數不超過F的一個常數倍，（3）p是PAC的：事件R(p, D) ≤ min _{p* ∈H} R(p*, D) + ε的概率至少為 1 – δ。

一個算法A稱為有效的，如果它能在多項式P(n，1/ε, 1/δ)內解決一係列的學習任務（Zn, Hn, Ln）, n = 1, 2, …. . 對於可實現的Hn, 即Hn包含一個函數p, 它在訓練集T上無偏差，p(Tx) = Ty，ERM算法是有效的。如果不作此假定，那麽許多常見的函數類H，ERM算法都是非多項式的。除非P = NP，我們不可能找到有效的算法。化NP為P，就成了人類的終極挑戰。