西瓜書擴展_學習理論

概念c=未知目標函數(shù)f

樣本集大小m=N

“不可知PLA可學習”f \notin \mathcal{H}

二分類問題，0-1損失函數(shù)（0-1 loss function）\ell_{h}(x,y)\ =\ I(y\neq h(x))

泛化誤差（generalization error）也稱期望損失（expected loss）E_{out}(h)=E(h)=\mathbb{E}_{\mathcal{P}}[\ell_{h}(x,y)]

經(jīng)驗誤差（empirical error）也稱經(jīng)驗損失（empirical?loss）E_{in}(h)=\hat{E}(h)=\frac{1}{N}\sum_{i=1}^{N}\ell_{h} (x_{i},y_{i})

由于數(shù)據(jù)集D是\mathcal{P}獨立同分布的采樣，因此h的經(jīng)驗誤差期望等于其泛化誤差，帶入霍夫丁不等式（Hoeffding Inequality）

上面說到期望就是平均數(shù)隨樣本趨于無窮的極限，那么這句話是什么意思呢？

我們還是以上面的擲骰子為例子：

如果我們擲了無數(shù)次的骰子，然后將其中的點數(shù)進行相加，然后除以他們擲骰子的次數(shù)得到均值，這個有無數(shù)次樣本得出的均值就趨向于期望。

個人理解：均值為多個隨機變量的和再除以個數(shù)，相當于還是一個隨機變量，當數(shù)量足夠多的時候，這個隨機變量會收斂，這個收斂的值為期望


\delta=2\exp(-2N\epsilon^2)，\epsilon =\sqrt{\frac{\ln\frac{2}{\delta}}{2N}}

P(|E_{in}-E_{out} |\geq \epsilon )\leq \delta

P(|E_{in}-E_{out} |\leq \epsilon )\geq 1-\delta

=P\Big( (E_{in}-\epsilon) \leq E_{out}\leq (E_{in}+\epsilon) \Big)\geq 1-\delta

=P\Big( (E_{in}-\sqrt{\frac{\ln\frac{2}{\delta}}{2N}}) \leq E_{out}\leq (E_{in}+\sqrt{\frac{\ln\frac{2}{\delta}}{2N}}) \Big)\geq 1-\delta


泛化誤差上界（generalization error bound）E_{out}\leq (E_{in}+\epsilon)


聯(lián)合約束（Union Bound）

P(\exists h\in \mathcal{H}:|E_{in}-E_{out} |\geq \epsilon )

=P\Big(\ |E_{in}(h_{1})-E_{out}(h_{1}) |\geq \epsilon \quad \mathbf{or} \ ...\ \mathbf{or} \quad |E_{in}(h_{|\mathcal{H}|})-E_{out}(h_{|\mathcal{H}|}) |\geq \epsilon \ \Big)

\leq \sum_{h\in \mathcal{H}}^{} P(|E_{in}-E_{out} |\geq \epsilon )

\leq \sum_{h\in \mathcal{H}}^{} 2\exp(-2N\epsilon^2)=2|\mathcal{H}|\exp(-2N\epsilon^2)=\delta，\epsilon=\sqrt{\frac{\ln|\mathcal{H}|+\ln\frac{2}{\delta}}{2N}}

P(|E_{in}-E_{out} |\geq \epsilon )\leq \delta

=P\Big( (E_{in}-\sqrt{\frac{\ln|\mathcal{H}|+\ln\frac{2}{\delta}}{2N}}) \leq E_{out}\leq (E_{in}+\sqrt{\frac{\ln|\mathcal{H}|+\ln\frac{2}{\delta}}{2N}}) \Big)\geq 1-\delta


對分（dichotomy）h_{|D}=\{(h(x_1),...,h(x_{N}))\ |\ h\in \mathcal{H}\}

增長函數(shù)（growth function）\Pi_ \mathcal{H}(N)=\max |h_{|D}| \leq 2^N，max表示最大

打散（shattering）\Pi_ \mathcal{H}(N)= 2^N，N個樣本點的集合 能 被H給打碎，或者說H 能 打碎N個樣本點的集合

突破點（break point）k=\min\ |\Pi_ \mathcal{H}(N)< 2^N|，N個樣本點的集合 不能 被H給打碎

vc維（VC?Dimension）d=k-1=\max\{ N\ |\ \Pi_ \mathcal{H}(N)= 2^N\}，max表示最大

一個數(shù)據(jù)點呈圓形分布的凸集，這時找不到任何突破點（break point），此時vc維趨于無窮。


Sauer 引理

Q=\{x_{1}, x_{2},x_{3},x_{4}\}

S=Q ∪\{x_5\} =\{x_{1}, x_{2},x_{3},x_{4},x_{5}\}

如果一個集合Q被\mathcal{H}_{|D^1}打碎，那么它也能被\mathcal{H}_{|D}打碎，因為\mathcal{H}_{|D^1}中包含 \mathcal{H}_{|D}所有在Q上不重復(fù)的函數(shù)。

此外，如果一個集合Q被\mathcal{H}_{|D^1|D} 打碎，集合S也將被\mathcal{H}_{|D}打碎，因為對\mathcal{H}_{|D^1|D} 中的所有函數(shù)，\mathcal{H}_{|D}都包含另外一個函數(shù)，它僅在x_5 上的輸出和前一個函數(shù)不同。

遞歸

遞歸：大雄在房里，用時光電視看著未來的情況。電視畫面中的那個時候，他正在用時光電視，看著未來的情況。電視畫面中的那個時候，他正在用時光電視，看著未來的情況……


當N \geq 2, d \geq 2的時候，\Pi_ \mathcal{H}(N) \leq \sum_{i=0}^u0z1t8os\binom{N}{i} \leq N^d \cdot (\frac{e}u0z1t8os)^d

P(|E_{in}-E_{out} |> \epsilon )\ \leq\ 4 N^d \cdot (\frac{e}u0z1t8os)^d\exp(-\frac{N\epsilon^2}{8})

基于vc維得到的泛化邊界（model complexity）\epsilon =\sqrt{\frac{8d\ln\frac{2Ne}u0z1t8os+8\ln\frac{4}{\delta}}{N}}

不是一味的追求經(jīng)驗誤差最小化
未知目標分布 P(y|x) 包含 f(x)+noise

對于不同的學習任務(wù)（分類，回歸，..）使用不同的損失函數(shù)（loss function）才能正確的解答。


X的樣本數(shù)量為N

h(X)=(Xw)=y

(Xw)=y \overset{X \ \mathrm{invertible}}{\Leftrightarrow} w=X^{-1}y

打散（shattering）就是我們給它任何一種ooxx組合y，都要能夠做到(Xw)=y也就是一條直線正確分類。

只要X可以求逆就能求出與之相對應(yīng)的w，全部的2^{N}種組合都可以使用這種做法。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容