什麼叫做泛函空間的大數定律？

12-27

今年一次會議上聽張鈸院士講，大數定律從函數空間推廣到泛函空間是機器學習理論的一個里程碑。對於泛函空間的大數定律，該如何理解？

這個問題問得很深刻，人們花了很長的時間才領悟到這個問題的答案，所以解釋起來有點費力。我這裡嘗試性地做一個解釋。
首先，我們需要搞明白三件事情：什麼是一個學習問題、什麼是風險最小化、什麼是經驗風險最小化歸納原則。

什麼是學習問題？
對於一個學習問題而言，給定了訓練樣本 $(x_1,y_1),(x_2,y_2), ... , (x_l,y_l)$ ，而訓練的樣本是根據聯合分布 $F(x,y)=F(x)F(y|x)$ 抽取的 $l$ 個獨立同分布的觀測。學習問題就是從給定的函數集 $f(x,alpha),alpha in Lambda$ 中選出能夠最好地逼近訓練樣本的函數，換句話說，就是用最優函數估計樣本背後蘊含的統計規律——用 $f(x,alpha)$ 估計 $y$ 。
注意， $Lambda$ 是參數集合，參數 $alphainLambda$ 並不一定必須是向量，可以是任意多抽象參數。

什麼是風險最小化？
風險最小化是用損失函數 $L(y,f(x,alpha))$ 表示輸入的真實響應 $y$ 與預測 $f(x,alpha)$ 之間的差異，它的期望又被叫做風險泛函： $R(alpha)=int_{}^{} L(y,f(x,alpha))dF(x,y), alpha in Lambda$
由於我們的概率測度 $F(x,y)$ 未知，所有可用的信息都來自訓練樣本。
所以學習，又可以說成是在經驗數據（訓練樣本）的基礎上，最小化風險泛函。

什麼是經驗風險最小化歸納原則？
顯然，我們並不知道概率測度，所以風險泛函並不能直接的計算和最小化。
根據大數定理，人們就很自然的想到用算術平均來代替風險泛函，從而又定義了經驗風險泛函 $R_{emp}(alpha)=frac{1}{l}sum_{i=1}^{l}{L(y_i,f(x_i,alpha))}$ ，用使得經驗風險最小的函數 $f(x,alpha)$ 逼近使得風險泛函最小的函數 $f(x,alpha_0)$ 。
這個原則就被稱作經驗風險最小化（之後我們簡稱ERM）歸納原則。
對於一個歸納原則，如果任何給定的觀測數據，學習機器都依照這一原則來選擇逼近，則我們就可以說這個歸納原則定義了一個學習過程。

那麼關鍵問題來了，為什麼需要推廣大數定律？
傳統的概率統計，包括大數定律，研究的都是漸近理論，換句話說就是當樣本數趨向於無窮大時的極限特性。同樣的，傳統的模式識別幾乎所有的方法都是建立在大數定律基礎之上。但是，一個顯然的條件是，對於任何一個實際問題來說，訓練樣本的數量，只能是有限的。這裡就隱含了一個命題：在樣本趨於無窮這個假設下得到的結論，當樣本數有限的時候，任然是有效的，或者，至少是一種不錯的近似。
一個很自然的想法，就是利用有限樣本估計分布，從而得到樣本空間的分布規律，這就是傳統模式識別的基本出發點。這種在分布已知或在估計分布的基礎上進行推斷的方式，屬於演繹推理。比如Bayes決策，是基於樣本的概率分布，可以獲得最優結果，保證期望風險最小。
實際上，樣本空間的分布規律如果已知的話，所有的學習問題在理論上都可以迎刃而解了。
所以，這時候人們發展了很多密度估計的方法，比如最大似然估計、最鄰近估計等等，這些對概率分布都是很好的估計方法，是一種很不錯的近似。然而，強的結果需要強的已知條件，Bayes方法、最大似然估計等都需要非常強的先驗知識，在實際問題當中，這是很難滿足的。
而核密度估計等非參數方法，需要的觀測數目又得足夠多，才能保證得到對以來關係較好的逼近，當樣本數量有限時，非參數方法的漸近特性也不再成立。
基於大數定律，先估計密度，然後用估計的密度來構造待求得函數，這種策略在利用有限樣本解決問題時，存在缺陷，傳統的模式識別裡面，發展了很多的方法去「直接」尋找待求得函數（比如LDA、NN等）。這種在分布未知並不在估計分布的基礎上進行推斷的方式屬於歸納推理。
通用的方法，都是是建立某一標準判據函數，執行梯度下降（現在的部分Deep Learning有用的是Hinton在這個世紀提出的CD演算法），達到判據最優值。
選取不同的判據函數，對於計算和收斂性就會出現不同的優劣，但都是執行相同的歸納原則——隨機逼近原則。這類演算法的迭代停止標準，都是當學習過程達到飽和，即對訓練數據中所有元素梯度值都非常小，以至於學習過程無法繼續。
然而，這些的這些，基本思想是都是用ERM代替實際中無法實現的風險泛函最小化。所以，其隱含的命題是，學習過程的一致性是顯然的！也就是說，概率論中的大數定律顯然能夠推出：對於以給定函數序列 $Q(z,alpha),l=1,2,...$ （其中 $z$ 代表數據對 $(x,y)$ ），ERM收斂到最小可能的風險泛函。這一命題似乎符合人們的直觀認識，但是卻很長時間裡沒有被人們注意到，這是沒有被證明的。

所以，實際上傳統的模式識別的統計基礎，實際上是有兩個硬傷的：
（1）並沒有對ERM原則下統計學習的一致性進行分析，不能保證：經驗風險的下確界能夠概率收斂到風險泛函的下確界。
（2）大數定理能夠保證演算法的漸進性，但是只考慮了漸近性，解決樣本有限的問題時，描述的僅僅只是一個極限過程，並沒有對收斂速度進行分析，並不一定能夠得到好的近似。

那麼人們就迫切的需要解決這麼幾個問題：
（1）ERM原則成立的條件是什麼；
（2）學習過程收斂速度的界；
（3）小樣本如何進行歸納推理；
（4）如何控制學習過程的推廣能力；

對這些問題的研究，一共構成了學習理論的四個核心部分：
（1）學習過程的一致性。
（2）學習過程收斂速度的非漸近。
（3）控制學習過程的推廣能力。
（4）構造學習演算法。

關於泛函空間的大數定律，就包含在第一個部分當中，學習過程的一致性，注意，這就是當下所有統計學習理論的基礎，所以說它是里程碑，不是泛泛而談。

那麼，如何保證學習過程的一致性？
只有當滿足一致性條件，才能保證在ERM原則下得到的最優方法當樣本無窮大時趨於使得風險泛函的最優結果，只有滿足一致性條件，才能說明我們的學習方法是有效的。

在看一個關鍵性的定理之前，我們需要確切的描述到底什麼才是一致：
對於損失函數集 $Q(z,alpha),alphainLambda$ 的任意非空子集 $Lambda(c)={alpha|int_{}^{}Q(z,alpha)dF(Z)>c,alphainLambda },cin(-infty,infty)$ 都有
$inf_{alphainLambda(c)}R_{emp}(alpha) xrightarrow{P} inf_{alphainLambda(c)}R(alpha),(l ightarrowinfty)$
成立，我們就說ERM方法對函數集 $Q(z,alpha),alphainLambda$ 和概率分布函數 $F(z)$ 是一致的。

那麼對於這個定理：

設函數集 $Q(z,alpha ),alpha in Lambda$ 滿足條件
$Aleq int_{}^{}Q(z,alpha ) dF(z)leq B(Aleq R(alpha)leq B),$
那麼EMR原則一致性的充分必要條件是：經驗風險 $R_{emp}(alpha)$ 在函數集 $Q(z,alpha )in Lambda$ 上以如下意義一致收斂於期望風險 $Rleft( alpha ight)$ ：
$lim_{l ightarrowinfty}P { sup_{alphainLambda}(R(alpha)-R_{emp}(alpha))>epsilon }=0,forall epsilon>0$

所達到的效果，就是把ERM方法的一致性問題轉化為一個一致收斂的問題。
因此，如果函數集 $Qleft( z,alpha ight) , alpha in Lambda$ 中只包含一個元素，由統計學中的大數定律可以立刻得到上述定理的成立。若函數集中包含有限個 $Q(z,alpha),alphainLambda$ 中包含有限數目N個元素，統計學中的大數定律，仍然可以證明出上面的定理。
可惜是，當函數集 $Q(z,alpha),alphainLambda$ 中存在無限多個元素時，統計學的大數定律就失效了，無法得到上面的定理。
所以我們這才迫切的需要泛函空間的大數定律（在函數 $Q(z,alpha),alphainLambda$ 的空間）。
至於為什麼，我想這個答案的篇幅有點長了，簡短的篇幅不足以解釋這些，如果題主感興趣，可以參考最後給出的參考文獻[1]。

綜上所述，統計學習理論的統計基礎（里程碑）是泛函空間的大數定律（在函數 $Q(z,alpha),alphainLambda$ 的空間），而不是傳統概率統計的大數定律（在樣本空間中）。

進一步閱讀的參考文獻
[1] Vladimir N. Vapnik著. 統計學習理論的本質.

歐長坤答案寫的挺好的，只想補充一點，在泛函空間不光人們已經對大數率充分了解，而且得到關於ERM結果更強的結論，利用empirical processtheory中deviation results，而且是high probability concentration，想要了解可以去讀一下Sara Van de Geer的書，或者Shahar Mendelson的一些論文。