UA MATH574M 統(tǒng)計(jì)學(xué)習(xí)I 監(jiān)督學(xué)習(xí)理論

• 統(tǒng)計(jì)決策理論
• • 損失函數(shù)與風(fēng)險(xiǎn)函數(shù)
  • • 偏差-方差的權(quán)衡
  • 最優(yōu)估計(jì)量
  • • 貝葉斯規(guī)則
• 監(jiān)督學(xué)習(xí)理論的基本概念
• • Optimal Learner
  • 經(jīng)驗(yàn)損失函數(shù)與ERM
  • 監(jiān)督學(xué)習(xí)理論的內(nèi)容
• ERM的一致性
• • Worst Case Analysis
  • Vapnik-Cervonenkis Entropy (VC-Entropy)
  • 一致性的充要條件

統(tǒng)計(jì)決策理論

損失函數(shù)與風(fēng)險(xiǎn)函數(shù)

假設(shè)樣本$X=(X_1,X_2,...,X_n){～}_{iid}f(x|\theta ),\theta \in \Theta$，是state-of-nature，假設(shè)其估計(jì)量是$\hat{\theta }(X)$（簡寫為$\hat{\theta }$），可以定義損失函數(shù)（Loss Function）
$$L(\theta ,\hat{\theta }):\Theta \times \Theta \to \mathbb{R}$$
用來衡量估計(jì)量與state-of-nature之間的差異，通常損失函數(shù)非負(fù)。常用的損失函數(shù)有這幾種：
$$\begin{gathered} SquareLoss:L(\theta ,\hat{\theta })=|\theta ?\hat{\theta }{|}_{L_2}^2 \\ AbsoluteErrorLoss:L(\theta ,\hat{\theta })=|\theta ?\hat{\theta }{|}_{L_1} \\ {L}_{p}Loss:L(\theta ,\hat{\theta })=|\theta ?\hat{\theta }{|}_{L_p}^p \end{gathered}$$
這三種損失函數(shù)一般用在回歸中，平方損失函數(shù)是最常用的。
$$0?1Loss:L(\theta ,\hat{\theta })=I(\theta =\hat{\theta })$$
這種損失函數(shù)一般用在分類問題中。
$$K?LDivergence:L(\theta ,\hat{\theta })=D(f(x|\theta )||f(x|\hat{\theta }))$$
這種損失函數(shù)一般用來做密度估計(jì)（Density Estimation）。其中K-L Divergence（Kullback-Leibler Divergence）又叫相對熵，用來描述兩個(gè)分布間的“距離”，其定義是
$$D(f(x|\theta )||f(x|\hat{\theta }))=E[ln(\frac{f(X|\theta )}{f(X|\hat{\theta })})]$$
但這個(gè)定義不滿足對稱性和三角不等式，所以不是一個(gè)真正的距離。在統(tǒng)計(jì)決策理論的框架下，參數(shù)估計(jì)可以被化歸為損失函數(shù)最小化。但遺憾的是，在Frequentist的哲學(xué)中，損失函數(shù)是關(guān)于樣本的函數(shù)，是隨機(jī)的，用來作為最優(yōu)化的目標(biāo)函數(shù)會(huì)讓問題變復(fù)雜。因此統(tǒng)計(jì)學(xué)家又定義了風(fēng)險(xiǎn)函數(shù)（Risk function）：
$$R(\theta ,\hat{\theta })=E[L(\theta ,\hat{\theta })]={\int }_{\mathbb{X}}L(\theta ,\hat{\theta })f(X|\theta )dX$$
這個(gè)就不是隨機(jī)的了，它是參數(shù)空間$\Theta$到$\mathbb{R}$上的函數(shù)。因此統(tǒng)計(jì)決策理論的目標(biāo)就是通過最優(yōu)化
$$\underset{\theta \in \Theta }{\min }R(\theta ,\hat{\theta })$$
來確定參數(shù)。

偏差-方差的權(quán)衡

假設(shè)使用平方損失函數(shù)，則對應(yīng)的風(fēng)險(xiǎn)函數(shù)又叫均方誤差（MSE，Mean Squared Error）。
$$MSE=E(\theta ?\hat{\theta }{)}^2=E[(\theta ?E\hat{\theta })+(E\hat{\theta }?\hat{\theta }){]}^2$$
考慮一下交叉項(xiàng)
$$E[(\theta ?E\hat{\theta })(E\hat{\theta }?\hat{\theta })]=(\theta ?E\hat{\theta })E(E\hat{\theta }?\hat{\theta })=0$$
而其中
$$E[(\theta ?E\hat{\theta }{)}^2]=bia{s}^2(\hat{\theta }),E[(E\hat{\theta }?\hat{\theta }{)}^2]=Var(\hat{\theta })$$
所以$MSE(\hat{\theta })=bia{s}^2(\hat{\theta })+Var(\hat{\theta })$。偏差與方差都會(huì)增加總風(fēng)險(xiǎn)，而從經(jīng)驗(yàn)上看二者又是此消彼長的關(guān)系，因此通常都需要在二者之間作出權(quán)衡（bias-variance trade-off）。

最優(yōu)估計(jì)量

風(fēng)險(xiǎn)函數(shù)還可以用來衡量估計(jì)量的優(yōu)劣，假設(shè)${\hat{\theta }}_1$和${\hat{\theta }}_2$是兩個(gè)估計(jì)量，如果
$$R(\theta ,{\hat{\theta }}_1)<R(\theta ,{\hat{\theta }}_2),?\theta \in \Theta$$
稱${\hat{\theta }}_1$絕對占優(yōu)于（uniformly dominated）${\hat{\theta }}_2$。從這個(gè)定義可以得到對最優(yōu)估計(jì)量的最樸素的認(rèn)知，如果一個(gè)估計(jì)量絕對占優(yōu)于其他所有估計(jì)量，那么它就是最優(yōu)的。這也正是上面提到的最小化風(fēng)險(xiǎn)函數(shù)的意思。然而找到風(fēng)險(xiǎn)函數(shù)的全局最優(yōu)解幾乎是不可能的，一般都是用一些更可行的方法計(jì)算得到一些近似的結(jié)果。常用的方法有三種。第一種是在最優(yōu)化限制在參數(shù)空間的某些子集中，比如限制在所有的無偏估計(jì)中，那么最優(yōu)的結(jié)果的結(jié)果就是最優(yōu)無偏估計(jì)，或稱UMVUE；如果限制在所有的線性無偏估計(jì)中，那么最優(yōu)的結(jié)果就是BLUE。第二種方法是minimax規(guī)則。對于所有可能的估計(jì)量，計(jì)算風(fēng)險(xiǎn)函數(shù)的上確界
$$\bar{R}(\hat{\theta })=\underset{\theta \in \Theta }{\sup }R(\theta ,\hat{\theta })$$
上確界代表估計(jì)量可能造成的最糟糕的結(jié)果。然后通過最小化這些上確界來選擇估計(jì)量
$$\underset{\hat{\theta }}{\min }\bar{R}(\hat{\theta })$$
用這個(gè)規(guī)則相當(dāng)于就是非常悲觀，希望估計(jì)量造成的最壞的結(jié)果也沒有那么壞就可以了。

貝葉斯規(guī)則

貝葉斯規(guī)則是第三種非常常用的方法。Bayesian的思想是state-of-nature也是隨機(jī)的，它會(huì)服從一個(gè)先驗(yàn)$\pi (\theta )$，給定樣本后根據(jù)Bayes公式可以計(jì)算出后驗(yàn)分布
$$\pi (\theta |X)=\frac{f(X|\theta )\pi (\theta )}{m(X)}\propto f(X|\theta )\pi (\theta )$$
其中$m(X)$是樣本的邊緣分布，$f(X|\theta )\pi (\theta )$又被稱為后驗(yàn)核（posterior kernel）。因?yàn)樨惾~斯統(tǒng)計(jì)最大的問題在于大量的復(fù)雜計(jì)算，而決定后驗(yàn)分布類型的只有$f(X|\theta )\pi (\theta )$，所以通常有后驗(yàn)核就可以了。在貝葉斯統(tǒng)計(jì)中，上面定義的風(fēng)險(xiǎn)函數(shù)不再是一個(gè)確定的函數(shù)了，因?yàn)閟tate-of-nature也是隨機(jī)的。Bayesian定義了貝葉斯風(fēng)險(xiǎn)（Bayesian risk）
$$r_B(\pi ,\hat{\theta })={\int }_{\Theta }R(\theta ,\hat{\theta })\pi (\theta )d\theta =E_{\theta }{E}_{X|\theta }L(\theta ,\hat{\theta })$$
貝葉斯規(guī)則的目標(biāo)就是通過最小化貝葉斯風(fēng)險(xiǎn)來估計(jì)參數(shù)
$${\hat{\theta }}_B^{\pi }=\underset{\hat{\theta }}{\mathrm{argmin}}{r}_B(\pi ,\hat{\theta })$$
這種估計(jì)量叫貝葉斯估計(jì)。然而還是同樣的問題，光是$r_B(\pi ,\hat{\theta })$的那個(gè)積分計(jì)算上就很復(fù)雜了，更何況還要做最優(yōu)化。因此另一種更可行的方法是定義后驗(yàn)風(fēng)險(xiǎn)（posterior risk）
$$r(\hat{\theta }|X)={\int }_{\Theta }L(\theta ,\hat{\theta })\pi (\theta |X)d\theta =E_{\theta |X}L(\theta ,\hat{\theta })$$
后驗(yàn)風(fēng)險(xiǎn)是樣本的函數(shù)，它和貝葉斯風(fēng)險(xiǎn)存在如下關(guān)聯(lián)
$$r_B(\pi ,\hat{\theta })=E_{X}r(\hat{\theta }|X)$$
證明也比較容易，就是用一下全概率公式
$$r_B(\pi ,\hat{\theta })=E_{\theta }{E}_{X|\theta }L(\theta ,\hat{\theta })=E_{X,\theta }L(\theta ,\hat{\theta })=E_X{E}_{\theta |X}L(\theta ,\hat{\theta })=E_{X}r(\hat{\theta }|X)$$
這個(gè)關(guān)系可以給貝葉斯規(guī)則帶來一個(gè)新的計(jì)算思路
$${\hat{\theta }}_B^{\pi }=\underset{\mathbb{X}}{\min }\underset{\hat{\theta }}{\min }r(\hat{\theta }|X=x)$$
在實(shí)踐中，這個(gè)方法比直接找貝葉斯估計(jì)量更容易計(jì)算。

監(jiān)督學(xué)習(xí)理論的基本概念

將統(tǒng)計(jì)決策理論的框架用到監(jiān)督學(xué)習(xí)（Supervised Learning）上，可以初步建立起監(jiān)督學(xué)習(xí)理論。假設(shè)$(X,Y)=\{(X_i,Y_i){\}}_{i=1}^n$表示訓(xùn)練集，$(X_i,Y_i){～}_{iid}P(x,y)$，且滿足$Y=f(X)$，監(jiān)督學(xué)習(xí)的目標(biāo)就是構(gòu)建$f$的估計(jì)量$\hat{f}$。

Optimal Learner

監(jiān)督學(xué)習(xí)的損失函數(shù)可以寫成$L(Y,f(X))$，風(fēng)險(xiǎn)函數(shù)是
$$R(f)=E_{X,Y}L(Y,f(X))={\int }_{\mathbb{X},\mathbb{Y}}L(Y,f(X))dP(X,Y)$$
它又被稱為expected prediction error (EPE(f))。因此Optimal Learner的定義是
$$\hat{f}=\underset{f}{\mathrm{argmin}}R(f)$$
理論機(jī)器學(xué)習(xí)的文章都是試圖證明某種方法的EPE會(huì)趨近optimal learner。與貝葉斯規(guī)則類似，監(jiān)督學(xué)習(xí)也可以做簡化處理，
$$R(f)=E_{X,Y}L(Y,f(X))=E_X{E}_{Y|X}L(Y,f(X))$$
給定$X=x$時(shí)，optimal learner就是最小化$E_{Y|X}L(Y,f(X))$的解。以平方損失函數(shù)為例，考慮最優(yōu)化
$$\underset{f}{\min }{E}_{Y|X=x}L(Y,f(x))=E_{Y|X=x}(Y?f(x){)}^2$$
其解為$f^{?}(x)=E(Y|X=x)$，正是平方損失下的貝葉斯估計(jì)量，因此貝葉斯風(fēng)險(xiǎn)是平方損失下EPE的下確界。如果對EPE做分解
$$EPE(f)=E_{X,Y}(Y?f(X){)}^2=E_{X,Y}[(Y?E(Y|X))+(E(Y|X)?f(X)){]}^2$$
其中交叉項(xiàng)也會(huì)為零，$E_{X,Y}[(Y?E(Y|X)){]}^2$是平方損失下的貝葉斯風(fēng)險(xiǎn)，因此
$$EPE(f)=r_B(\pi ,\hat{\theta })+E_X(f(X)?E(Y|X){)}^2$$
后者衡量learner與貝葉斯估計(jì)之間的差距，設(shè)計(jì)learner的目標(biāo)就是控制這一項(xiàng)。

經(jīng)驗(yàn)損失函數(shù)與ERM

在實(shí)際問題中，概率測度$P(X,Y)$都是未知的，一般只能用經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)（empirical risk function）來替代EPE。經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)又叫訓(xùn)練誤差（training error），其定義是
$$R_{emp}(f)=\frac{1}{n}\sum _{i=1}^{n}L(Y_i,f(X_i))$$
最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)來尋找optimal learner的原則叫ERM（Principle of empirical risk minimization）。從理論上看，當(dāng)訓(xùn)練集足夠大時(shí)，經(jīng)驗(yàn)風(fēng)險(xiǎn)自然會(huì)趨近于EPE，但當(dāng)訓(xùn)練集不夠大的時(shí)候需要防止模型過擬合（overfitting）。過擬合指的是模型的訓(xùn)練誤差很小，但泛化能力較差。因?yàn)樽钚』?jīng)驗(yàn)風(fēng)險(xiǎn)與最小化EPE的結(jié)果并不一定總是一致的，所以會(huì)有過擬合。為了防止過擬合，可以給參數(shù)加上roughness penalty。ERM與貝葉斯估計(jì)量類似，都是試圖尋找全局的最優(yōu)解，但全局最優(yōu)通常無法找到，所以限制模型的類別，比如線性、非線性、參數(shù)模型、非參模型等，在子集上找最優(yōu)解是比較常規(guī)的做法。假設(shè)模型集合為$\mathbf{F}$，某個(gè)類別的子集為${\mathbf{F}}_1$，$f^{?}$是optimal learner，
$$f^{?}=\underset{f\in \mathbf{F}}{\mathrm{argmin}}EPE(f)$$
$\hat{f}$是在模型子集${\mathbf{F}}_1$上根據(jù)ERM找到的最優(yōu)解
$$\hat{f}=\underset{f\in {\mathbf{F}}_1}{\mathrm{argmin}}{R}_{emp}(f)$$
$\tilde{f}$是模型子集${\mathbf{F}}_1$的理論最優(yōu)解
$$\tilde{f}=\underset{f\in {\mathbf{F}}_1}{\mathrm{argmin}}EPE(f)$$
則$\hat{f}$與optimal learner之間的誤差可以做如下分解
$$EPE(\hat{f})?EPE(f^{?})=[EPE(\hat{f})?EPE(\tilde{f})]+[EPE(\tilde{f})?EPE(f^{?})]$$
第一項(xiàng)的含義是在模型子集${\mathbf{F}}_1$的估計(jì)誤差，第二項(xiàng)是將模型限制在${\mathbf{F}}_1$上的近似誤差。

監(jiān)督學(xué)習(xí)理論的內(nèi)容

從上面的描述中，我們已經(jīng)可以窺見監(jiān)督學(xué)習(xí)理論需要回答的幾個(gè)問題了。ERM收斂的條件是什么？收斂速度怎么樣？怎么才能控制它的收斂？這三個(gè)問題都有實(shí)際意義。第一個(gè)問題可以回答基于ERM的監(jiān)督學(xué)習(xí)算法在哪些情境下適用；第二個(gè)問題可以回答為了保證結(jié)果盡可能接近Optimal Learner，至少需要多大的訓(xùn)練集；第三個(gè)問題可以回答過擬合能不能避免。以下給出一致性理論的簡單介紹。

ERM的一致性

ERM的一致性理論建立在概統(tǒng)漸進(jìn)理論的基礎(chǔ)上，提供了ERM收斂的充要條件，滿足這些充要條件的算法才有機(jī)會(huì)收斂到Optimal Learner。

Worst Case Analysis

假設(shè)風(fēng)險(xiǎn)函數(shù)$R(f)$有界，則ERM具有一致性的充要條件是$R_{emp}(f)$依概率單邊一致收斂（uniformly one-sided convergence in probability）到$R(f)$，$?f\in \mathbf{F}$，即
$$\underset{n\to \infty }{\lim }P\{\underset{f\in \mathbf{F}}{\sup }(R(f)?R_{emp}(f))>?\}=0,??>0$$
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$R_{emp}(f)$是$(X,Y)$的函數(shù)，所以這里的概率測度就是上面那個(gè)概率測度$P(X,Y)$。這個(gè)結(jié)論其實(shí)是很直觀的，ERM的一致性指大樣本的時(shí)候，希望ERM的最優(yōu)結(jié)果趨近于Optimal Learner，這個(gè)結(jié)論說的是要實(shí)現(xiàn)這個(gè)效果，那么首先在大樣本的時(shí)候訓(xùn)練誤差就要一致收斂到EPE。這個(gè)定理是監(jiān)督學(xué)習(xí)理論一個(gè)非常關(guān)鍵的定理，因?yàn)橐ＷC訓(xùn)練誤差一致收斂，就要求我們必須分析最壞的情況，即考慮${\sup }_{f\in \mathbf{F}}(R_{emp}(f)?R(f))$。這其實(shí)就是在強(qiáng)調(diào)對ERM一致性的分析，其實(shí)是一種Worst Case Analysis。

Vapnik-Cervonenkis Entropy (VC-Entropy)

接下來要做的事情，就是分析$R_{emp}(f)$依概率單邊一致收斂到$R(f)$的充要條件。為了做這個(gè)分析，需要定義一個(gè)新的結(jié)構(gòu)，VC-Entropy。先舉一個(gè)例子介紹一下VC-Entropy的思想。假設(shè)學(xué)習(xí)任務(wù)是做一個(gè)二分類問題，$Y$被標(biāo)注為0和1，如果只有5個(gè)觀察對象，觀察足夠多次后得到的$f(X)$只有這四種結(jié)果(0,1,1,0,0), (0,1,0,1,0), (1,0,1,1,1), (0,0,1,0,1) （根據(jù)觀察到的特征用分類器$f$分類的結(jié)果）。這四個(gè)向量在五維空間中構(gòu)成的圖形（這個(gè)圖形相當(dāng)于所有分類結(jié)果的邊界）有4個(gè)頂點(diǎn)，由此可以定義這個(gè)分類器的隨機(jī)熵（random entropy）為$\ln 4$。這個(gè)值用來衡量分類器分類結(jié)果的離散程度。現(xiàn)在將這個(gè)定義推廣到一般情況。對于訓(xùn)練集$(X,Y)=\{(X_i,Y_i){\}}_{i=1}^n$與算法$f$，定義隨機(jī)向量
$$q(f)=[f(X_1),f(X_2),...,f(X_n){]}^T\in {\mathbb{R}}^n$$
則這個(gè)向量表示算法$f$所有可能輸出在${\mathbb{R}}^n$空間中的位置。然后利用$?$-net去定義所有這些$q(f)$的邊界的“頂點(diǎn)”，用$N(?,X)$表示“頂點(diǎn)”的個(gè)數(shù)，用$H(?,X)=\ln N(?,X)$用來衡量輸出的離散程度，則VC-entropy的定義是
$$H(?,n)=E_{X}H(?,X)$$
這個(gè)定義已經(jīng)將特征的不確定性考慮在內(nèi)了，其含義是輸入的特征（隨機(jī)變量）經(jīng)過算法$f$處理后輸出結(jié)果的平均離散程度，只與$?$的選取與訓(xùn)練集大小$n$有關(guān)。

一致性的充要條件

$R_{emp}(f)$依概率雙邊一致收斂（uniformly two-sided convergence in probability）到$R(f)$，$?f\in \mathbf{F}$，即
$$\underset{n\to \infty }{\lim }P\{\underset{f\in \mathbf{F}}{\sup }(|R(f)?R_{emp}(f)|)>?\}=0,??>0$$
的充要條件是
$$\underset{n\to \infty }{\lim }\frac{H(?,n)}{n}=0,??>0$$
因?yàn)殡p邊收斂比單邊收斂強(qiáng)，所以這個(gè)結(jié)果也是單邊一致收斂的充要條件。這個(gè)結(jié)果也是比較直觀的，相當(dāng)于是在限制所有可能輸出的邊界的大小，假設(shè)上面的極限等于一個(gè)正實(shí)數(shù)，那么“頂點(diǎn)”的個(gè)數(shù)會(huì)指數(shù)增加，隨著訓(xùn)練集越來越大，算出輸出的值域反而會(huì)擴(kuò)張，從而出現(xiàn)類似過擬合的現(xiàn)象，顯然是不會(huì)收斂的；假設(shè)上面的極限是一個(gè)負(fù)實(shí)數(shù)，那么“頂點(diǎn)”的個(gè)數(shù)會(huì)指數(shù)減少，隨著訓(xùn)練集越來越大，算法輸出的值域會(huì)逐漸坍塌，出現(xiàn)類似欠擬合的現(xiàn)象，這樣也不會(huì)收斂。監(jiān)督學(xué)習(xí)理論討論了一致性的充要條件后，還討論了快速收斂（快速收斂指的是指數(shù)收斂）的充要條件，快速收斂且獨(dú)立于概率測度（也就是可以在不同的context下都具有一致性）的充要條件。基于$N(?,X)$構(gòu)建另外兩個(gè)結(jié)構(gòu)。退化VC-entropy
$$H_{ann}(?,n)=\ln EN(?,X)$$
以及增長函數(shù)
$$G(?,X)=\ln \underset{X}{\sup }N(?,X)$$
根據(jù)定義可以直接得到VC-entropy的邊界
$$H(?,n)\le H_{ann}(?,n)\le G(?,X)$$
其中
$$\underset{n\to \infty }{\lim }\frac{H_{ann}(?,n)}{n}=0,??>0$$
是快速收斂的充要條件。
$$\underset{n\to \infty }{\lim }\frac{G(?,n)}{n}=0,??>0$$
快速收斂且獨(dú)立于概率測度的充要條件。

總結(jié)

以上是生活随笔為你收集整理的UA MATH574M 统计学习I 监督学习理论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。