- 訓(xùn)練與測(cè)試
- 例證
- 重要概念：斷點(diǎn)
訓(xùn)練與測(cè)試
以一次期末考試為例：
在測(cè)試中：
Ein 是考前復(fù)習(xí)時(shí)，與復(fù)習(xí)資料之間的誤差。
Eout 是考試中，與考試資料之間的誤差。
在訓(xùn)練中：
Ein 是對(duì)于練習(xí)題的學(xué)習(xí)誤差。
Eout 是對(duì)于聯(lián)系材料整體的學(xué)習(xí)誤差。
但是在學(xué)習(xí)過(guò)程中，因?yàn)閷?duì)材料整體越來(lái)越熟悉，反應(yīng)你學(xué)習(xí)的復(fù)雜程度（次數(shù)）。
M來(lái)自哪里
對(duì)于不良事件記為：Bm
此時(shí)
其反應(yīng)為B1到BM中至少有一個(gè)發(fā)生。
很明顯，我們對(duì)Bad event的約束有很多重復(fù)，所以可以從這方面入手進(jìn)行優(yōu)化。
M的優(yōu)化
以感知器模型為例進(jìn)行說(shuō)明：
Ein 與 Eout 其物理意義如圖：
當(dāng)模型有所改變時(shí)：
改變十分微小的時(shí)候，h1 和 h2 兩者的Ein 和Eout的差值幾乎不變，這就是重疊部分的來(lái)源。
二分
因?yàn)檩斎肟臻g是無(wú)限的，所以我們選擇去考量有限個(gè)輸入點(diǎn)序列。并統(tǒng)計(jì)點(diǎn)的二分?jǐn)?shù)量（對(duì)或者錯(cuò)）
就像我們?cè)谏吓艌D中改變感知器模型任意次，單下排圖中的樣本點(diǎn)時(shí)，我們只會(huì)認(rèn)為這是同一種情況。
所以說(shuō)，我們將整個(gè)輸入空間變?yōu)榱艘粋€(gè)輸入序列。進(jìn)而可以為假設(shè)限定上限。
增長(zhǎng)函數(shù)
對(duì)于上述的情況，我們?yōu)镸設(shè)定了增長(zhǎng)函數(shù)來(lái)對(duì)其進(jìn)行限定。
將M的增長(zhǎng)函數(shù)應(yīng)用于感知器模型
我們發(fā)現(xiàn)，N=4的例子中，我們無(wú)法取得所有的組合方式，所以2N這一上限無(wú)法達(dá)到。
例證
positive rays
positive intervals
凸集
三種情況下的增長(zhǎng)函數(shù)
總結(jié)
因?yàn)橹笖?shù)的數(shù)字非常小，所以當(dāng)m是一個(gè)多項(xiàng)式的時(shí)候，小的指數(shù)會(huì)使得多項(xiàng)式中絕大多數(shù)的失效，進(jìn)而簡(jiǎn)化多項(xiàng)式。同時(shí)使得不等式右側(cè)足夠的小，這樣一來(lái)就說(shuō)明了模型的推廣性與可用性。
重要概念：斷點(diǎn)（break point）
定義
定義：自斷點(diǎn)起，你無(wú)法獲得所有的二分組合。
其對(duì)應(yīng)了模型的復(fù)雜程度。
下圖中，四個(gè)點(diǎn)的分布無(wú)法使用感知器模型進(jìn)行徹底的二分，所以在該假設(shè)空間中，K=4。所以，我們?cè)诘弥獢帱c(diǎn)的情況下，無(wú)需關(guān)系N的大小。如此一來(lái)，可以將增長(zhǎng)函數(shù)進(jìn)行限定。
上述三個(gè)例證的斷點(diǎn)
應(yīng)用方式
K = 2時(shí)，任意三個(gè)點(diǎn)的組合：
不能夠獲得K=2個(gè)點(diǎn)的所有組合。
僅四個(gè)可實(shí)現(xiàn)的組合，證明了K是一個(gè)極佳限定方式。
