標籤：

經驗風險最小化

04-27

過擬合

PRML介紹了一個多項式擬合曲線的例子。設函數族 $mathcal{H}={sum_{i=0}^Momega_ix^i}$ ，訓練集 $S={(x_j,y_j)}_{1leq jleq N}$ 。嘗試最小化損失函數

$frac{1}{2}sum_{j=1}^N(sum_{i=0}^Momega_i x_j^i - y_j)$

當 $M+1<N$ 時，相當於逼近
當 $M+1geq N$ 時，相當於插值

因此當 $M$ 稍大於 $N$ 的個數時，就會發生過擬合。為了解決這個問題，作者給損失函數加了一個懲罰項 $frac{lambda}{2}||omega||^2$ 來限制模型的複雜度。

經驗風險

設數據 $(x,y)$ 服從分布 $D$ ， $L$ 為損失函數，定義真實風險 $forall h inmathcal{H}$ ,

$R(h) := mathbb{E}[L(h(x), y)]$

因此一個分類問題的目標是找到 $h^*=argmin_{hinmathcal{H}}R(h)$

但是分布 $D$ 往往是不可知的，因此需要採樣 $S={(x^{(i)},y^{(i)})}sim D$ ，並把經驗風險

$R_ ext{emp}(h):=frac{1}{m}sum_iL(h(x^{(i)}), y^{(i)})$

作為目標函數優化

$hat{h}=argmin_{hinmathcal{H}}R_ ext{emp}(h)$

VC理論

Andrew Ng在CS229的Learning Theory中描述了損失函數為

$L(h(x), y)=mathbb{I}(h(x) e y)$ 的VC理論。

當 $mathcal{H}$ 為有限集時，以至少 $1-delta$ 的概率， $forall hinmathcal{H}$ ，有

$|R(h) - R_{ ext{emp}}(h)|leq O(sqrt{frac{1}{m}logfrac{k}{delta}}~)$

其中 $k=|mathcal{H}|$ 。

當 $mathcal{H}$ 為一般集時，以至少 $1-delta$ 的概率， $forall hinmathcal{H}$ ，有

$|R(h) - R_{ ext{emp}}(h)|leq O(sqrt{frac{d}{m}logfrac{m}{d}+frac{1}{m}logfrac{1}{delta}}~)$

其中 $d= ext{VC}(mathcal{H})$ 。

結構風險

通過VC理論，可以認識到真實風險和經驗風險是有差距的。誤差項被稱為置信風險，它與樣本的個數 $m$ 和模型的複雜度 $k$ 或者 $d$ 都有密切的關係。

用複雜度高的模型去擬合小樣本，往往會導致過擬合，因此有時需要給經驗風險 $R_{ ext{emp}}$ 加上一個懲罰項或者正則化項：

$R_ ext{srm}(h):=frac{1}{m}sum_iL(h(x^{(i)}), y^{(i)})+lambda J(h)$

這也被稱為結構風險。

例子

線性回歸的損失函數為MSE，防止過擬合可以加L0，L1，L2範數的正則化項
logistic回歸的損失函數為cross entropy，防止過擬合可以加L0，L1，L2範數的正則化項

線性SVM

線性分類器 $mathcal{H}={omega^tx}$ 的VC維數為 $d+1$ ，其中 $d$ 為向量 $x$ 的維數，即模型複雜度比較高。

考慮優化問題

$min_{omega,b}frac{1}{2}||omega||^2~~~~~~~ ext{s.t.}~~y^{(i)}(omega^tx^{(i)}+b)geq1,~~1leq ileq m$

的對偶問題為

$mathcal{L}(omega,b,alpha)=-sum_ialpha_i[y^{(i)}(omega^tx^{(i)}+b)-1]+frac{1}{2}||omega||^2$

因此正則化項 $frac{1}{2}||omega||^2$ 限制了線性SVM的複雜度。

參考

Pattern Recognition and Machine Learning
CS229
統計學習方法

推薦閱讀：

※樸素貝葉斯
※如何理解機器學習？
※過擬合與正則化
※如何訓練模型？（1）——最小二乘法
※關於機器學習、數據科學面試的準備

TAG:機器學習 |