給定任意D，它是某些H的Bad Sample（即E_in和E_out不接近）的概率為：

即H中備選函數(shù)的數(shù)量M=|H|越少，樣本數(shù)據(jù)量N越大，則樣本成為壞樣本的概率越小。在一個(gè)可接受的概率水平上，學(xué)習(xí)算法A只需要挑選那個(gè)表現(xiàn)最好的h作為g就行了。

挑選出最好的g需要滿足兩個(gè)條件：找到一個(gè)假設(shè)g使得E_out(g)和E_in(g)是非常接近的，使得E_in(g)足夠小，

下面是BAD和M的關(guān)系：

因此選擇一個(gè)合適的M是非常重要的，需要用一個(gè)有限的值m來替代一個(gè)非常無限的值M

思路：overlapping for similar hypotheses h1 ≈ h2 ，它們的E_in(h₁)≈E_in(h₂),E_out(h₁)≈E_out(h₂)(比如說PLA中的兩條直線，相鄰的很近的直線)=>union bound over-estimating

?

to account for overlap,we can group similar hypotheses by kind

h對(duì)D的一個(gè)Dichotomy(二分):備選函數(shù)集中的每一個(gè)函數(shù)h都是輸入X到輸出Y的一個(gè)映射：H={hypothesis h:X->{×,Ο}}將h(x1,x2,...,xN)=(h(x₁),h(x₂),...,h(x_N))∈{×,Ο}^N?其中H(x₁,x₂,...,x_N)包含了所有對(duì)D的dichotomies。

hypotheses H 和dichotomies?H(x₁,x₂,...,x_N)的區(qū)別：

?

growth function:?remove dependence by taking max of all?possible (x₁, x₂, . . . , x_N)

4個(gè)成長(zhǎng)函數(shù)

break point：有k個(gè)輸入，如果它不能被當(dāng)前的備選函數(shù)集H shatter，那么k就是H的一個(gè)Break Point

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/nolonely/p/6163720.html

總結(jié)

以上是生活随笔為你收集整理的无限的hypotheses 变成有限的dichotomies的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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