0:00
好,那所以我們這邊是講到說這個一個 hypothesis
的時候,我們可以做 verification 那现在如果今天我們有很多个
hypothesis 的時候,我們要怎么辦呢? 好,你说很多 hypothesis
那有什麼大不了,一个 hypothesis 既然是一個罐子,那我如果有10個 hypothesis 我们拿10個个罐子出來,
10个罐子不是重點,我现在問題是這樣, 如果你今天真的有10個
hypothesis 然后这10個我們就说你有10個罐子好了,
那10个罐子,然后你就抽了這個 彈珠出來,抽了彈珠出來以後發現其中有
一個瓶子抽出來的彈珠全部都是綠色的, 你的問題就是你是不是要選這個瓶子,
這是對應到什麼?這是對應到我們在 learning 裏面,你如果有10個
hypothesis 其中有一個 hypothesis 在你所看到的資料上,
全對,你要不要選它,所以這問題是這樣,你的演算法說哎呀, 我找到了一個全對的
hypothesis 相當於全部是綠色的彈珠,現在問題是這一個彈珠罐 好還是不好,也就是說你要不要選這個
hypothesis 當你最後的g,好,簡單化一點,我們說不要講罐子了,
我們乾脆用銅板來講好了,大家身上有沒有帶銅板,有帶銅板的話呢,可以這個拿出來玩一下,
那在臺大課程我們差不多一個班有一百五六十個人,所以我們有一百五六十
顆銅板在那邊,我現在請每一位同學把你手上的銅板
丟五次,丟五次以後,你要記錄有幾次正面,幾次的這個反面
好,丟完以後呢,150個人, 我們很有可能會發現有一個人他丟的五次銅板
五次都是正面,好,五次都是正面,那我現在就問了
這一個銅板真的比其它銅板要好嗎?也就說它正面機率是真的比其它銅板要高呢
還是它跟其它銅板沒有什麼不一樣,只是這個人運氣好,剛好丟了五次,然後五次都是正面。
大家仔細想一想這個問題的話,可能會發現就 算我說的銅板都是非常公平的銅板,公平就是正面、 反面機率都是二分之一。
我今天既然有150個人在那邊,或者還各位同學如果你現在坐在電腦前面,你就只有一個人- 呢,你可以丟150
次,通常你不用丟到150次,你丟個20次,30次,40次,搞不好你就會出現這個- 全部正面
的這個情形,我們有那麼多人在的時候,你去算一算機率會發現 其中至少有一個人出現這個
五個正面的機率是大於99%的, 也就是說當我今天有選擇,我在選什麼?我在選那個
在在丟的記錄裏面,我看起來最好的那個 銅板,當我今天有選擇的時候,我就有了偏見,其實這些銅板都是一樣,都是非常公平的。
但是我去選了那個這個丟了五次正面的,然後說它比較幸運,其實並沒有
好,所以現在說事情是這樣, 大家想一想 Hoeffding
告訴我們是什麼事情?Hoeffding 告訴我們事情是 我取樣出來的跟我罐子裏的大部分的時候是一樣的,
只有小部分的時候是不好的,不好這個就是我 取樣出來跟我罐子裏的那兩個
μ 跟 ν 差的非常遠, 不好的我們把它叫做 BAD 就是不好的。
好,然後它說 Hoeffding 說不好的這一件事情很小, 那現在怎麼樣呢,我們現在發現有選擇的時候,
這些選擇會惡化這些不好的情形, 對不對,你原來你原來只有一顆銅板的時候,好,你這個
這個銅板的機率是1/2,那麼那個最不好的就是你拿到五個正面的那個機率就是1/32
而已,現在你有150個選擇的時候,你的這個 不好發生不好的事情,也就是說你選到那個全部是
全部是正面,那它其實沒有比較好的那一個銅板,這一件事情發生的幾率
超過99%,也就是不好的機率就惡化了。
好,所以這是 不好的,那我們現在從銅板,不好的銅板回頭來看說,那什麼叫做不好的資料,我們現在已經-
有一個概念, 銅板就是彈珠,就是我們手上的資料,好,不好的銅板是怎麼樣,
它實際上的機率是1/2,但是我們丟丟丟丟到五次正面,也就是說 它的
Ein 我們手上的 Sample看起來好像是0,所以兩個差得很遠,
那不好的資料是怎麼樣?不好的資料就是 Eout跟Ein 差的很遠,如果
我只有一個 hypothesis 我就可以直接看說Eout跟Ein,如果兩個差得很遠,
比什麼遠,比 ε 來的遠的話,那麼就說它是不好的,最典型的例子就是什麼,我們手上看起來很好啊,Ein-
很小啊, 但是它在Eout 也就是那些我們看不到的地方,實際上是
很不好的,Eout很大,好,也就是 長這個樣子,Hoeffding
guarantee的事情是我們要再三 強調 Hoeffding guarantee
的事情是說你抽一把出來的時候, 有很大的這個機會,是會是好的情形,就很小的機會,是不好的
情形,它的機率是在你抽一把這一件事情上面, 好,所以呢,你可以說我抽一把
這一把是好的,抽一把這一把是不好,你可以一把一把一把各種不同的抽,各種不同的抽就
對應到各種不同的資料,所以我們這邊把它說 資料可能有D1、 D2然後一直到如果能夠把資料
非常概略性的編號下各種,剛才我們說有無線多種可能的資料, 但如果編下來的話,然後你說D1是不好的,D2是好的,
D3是不好的等等,每個每個資料會有好或不好, 再說一次什麼叫好或不好,Ein跟Eout有沒有差的很遠,
Hoeffding 保證的事情是什麼,保證的事情是這裡沒有太多格
BAD的,也就是說總體來說, BAD的機率是小於等於我們那個 Exponential 那個非常小的東西。
Hoeffding 說的事情是這樣,我把資料列成,所有可能的資料列成一排,那個當然是N筆的資料列成一排,
好,D1有N筆,D2有N筆,D3有N筆,所有可能資料知道列成一排的話,不好的那些格
很少格,OK,或者說,嚴格來說當然是它們的機率加起來,非常的小,
好,所以這是Hoeffding 我如果把所有的資料窮舉出來,那它們的機率
然後乘上說,它到底是好的還是不好,這些總共加起來,就是不好的機率,那Hoeff- ding
說不好的機率非常的小, 那如果今天有很多個 hypothesis
那不好的機率會變成什麼樣子呢? 我們現在就要說,如果你現在有很多 hypothesis,記得我們很多
hypothesis 為了做什麼? 為了讓我的演算法可以做選擇,
所以演算法做選擇的話,所以怎麼樣?所以怎麼樣是不好的資料,不好的資料就是演算法- 沒有辦法
自由自在的做選擇,演算法可能會選到那個不好的那一格 對不對,如果你有很多個 hypothesis
然後演算法可能會選不好的那一格,還是沒有辦法 自由自在做選擇,所以好的資料是演算法不管選什麼都對,它只要照照它的
這個自由意識去選就好了,不好的資料是演算法可能會我們這個通俗一點說,
踩到雷了,OK,這個不好的就是地雷,如果演算法剛好選到那個 hypothesis
那個 hypothesis 在這筆資料上 Ein跟 Eout 差的很遠,例如說什麼,例如說Ein
非常的低,Eout 其實很大,演算法,好死不死,它說我選這個,這個看起來Ein很低啊,結果碰到雷
說,Eout很大,拿去投資股市,輸得很摻,被老闆罵或者是這個 這個有其他更不好的情形,那就那就不好了,
好,所以不好的資料就是讓演算法可能會踩到雷的, 那也就是什麼呢?就是有,如果今天有一個
hypothesis, OK,在這個 hypothesis 上,它的
Ein 跟Eout差很遠,那就是不好的資料, 所以故事是怎麼樣,所以我們現在有很多筆啊,大家記得說,說我們每個
hypothesis 然後每個資料 有好或不好,這就是一排,Hoeffding
告訴我們說什麼,Hoeffding 告訴我們說總共這個不好的機率加起來很小, 另外一個
hypothesis 一樣它有它自己的一排,它的BAD跟另外一個人 BAD可能不一樣,
然後但是加起來都會很小,所以Hoeffding 告訴我們的是一行一行,OK,
這個加起來,BAD加起來機率會很小, 那我們現在要的是什麼,我們現在要的是說,我的演算法要能夠安安心心的做選擇,
如果我現在資料是D1的話,我演算法能不能安安心心的做選擇,不行啊,它要 這個它有可能會踩到雷,是h1、
h3跟hM, 好,如果是D2的話,它可能會踩到雷是h2跟h3,
只有像h這個1126這種這是完全沒有雷的, 好,這種才是好的資料,所以呢,只要
這個 column 上面有一個不好的,我們就說它是
overall對演算法來說不好的,所以我們就把它標成不好,不好,不好,只有這個可能- 勉勉強強是好的,
那所以我們現在想要知道的事情是什麼,我們現在想知道的事情是 好吧,那麼如果我現在有興趣的事情是
在我的演算法可以自由自在做選擇狀況下,怎麼樣是 不好的資料,這個不好的資料發生的機率
到底是多少?好,也就是說我想要在這邊有一個 跟原來
Hoeffding 相對應東西,那我用的事情是這樣,就是說只要這裡有一個不好,我就說不好。
有一個不好我就說不好,好,所以呢,這總共的不好的加起來到底有多少
好,在我們這樣的定義之下,我們就說,所以我們想像的
那個不好,就是有一個h不好,定義上是有一個我们就用or
對h1不好,或者對h2不好,或者對h3不好,只要對某一個人不好,那我們就說它是不好的
那,大家學過機率知道啊,我們今天如果有很多個 機率的事件,然後那是or起來,聯集起來的話
我可以把它們拆開來再加起來,拆開來加起來,也就是說,有點像集合
集合的聯集的時候,我要算聯集的面積,我可以把每個集合的面積加起來
然後,那這樣的話會是一個上限,會是一個upper bound
所以我今天把這個或拆成這個加法,那我這裡要加一個小於等於上去 這樣的方法通常叫做一個union
bound,就是聯集的上限 那麼這個聯集的上限怎麼樣,現在我既然拆成每一項每一項,大家記得每一項是什么
是對一個hypothesis不好,對一個hypothesis不好我們會不會做,會
誰告訴我們的,hoeffding,所以這裡的每一項都是 兩倍的exp,然後後面那一長串的東西
既然每一項都是,我總共有幾項,我的hypothesis set裡面如果有M個的話
那就有M項,所以總共就乘上一個M倍 比原來的hoeffding乘了M倍,如果今天有一個hypothesis
set,裡面有100項 那我這個比原來的hoeffding有不好事情發生的機會,就乘上100倍
好,那這個可以想成是hoeffding,在這邊我們叫作是finite-bin,就是說
有限數量,如果你有有限個罐子的話的一個延伸,那對所有的 N、
ε 還有我們现在新加上的M,就是你有幾個罐子或者你有幾個hypotheses都是成立的
那一樣,我們不需要知道每個Eout是多少 所以我們不需要知道f,我們也不需要知道p
那如果,ok,我們今天的資料量夠多的時候,那我們就可以說
好吧,所以這裡的每一個h都是安全的,每一個h都是安全的表示什麼,不管你的演算法怎麼選
你一定可以選到一個g,這個g會有好的性質是它的Ein跟Eout是接近的
好,既然在這麼安全的狀況下,那就怎麼樣呢
最合理的演算法,至少目前看起來最合理的演算法,就像我們之前在PLA和pocket- 做的一樣
算一個g,這個g的Ein最小 因為如果這個g的Ein最小,某種角度幾乎也就是說這個g的
Eout也是比較小的,因為Ein和Eout都很接近 好,於是,我們現在
終於可以做到一點點的learning了,什麼意思呢? 如果我今天的hypothesis
set只有有限多種選擇 我的資料量夠多,那麼不管我的演算法怎麼選,Ein跟Eout都會接近,這是我們剛才-
導的這個 finite-bin 的 hoeffding告訴我們的事情,然後呢,如果我的演算法設計來說什麼,找一個Ei-
n最小的 那麼,這個我們就可以有這樣的推論去得到說,所以我的Ein很小
我的Eout也很小,好,所以這是我們更新的流程,實際上是我們多加了兩條
線,這兩條線就是我有一個機率函數,這個機率函數控制我怎麼測試我最後的
g跟f一不一樣,也就是這個Eout裏面的式子,然後呢我怎麼產生我的資料 也就是我的D的這個i.i.d.的這個方式,目前我們
有證明到的是H要是這個 finite
size要有限大,我的N要夠大 好,那如果這樣的話,我們終於可以開心一點了
機器學習是有可能做得到的,不過當然大家都說
講了這麼多,但是我們之前說的perceptron,那些線不是無限多條嗎
那你現在說,你的H要有限大,所以你還是在打嘴炮,你還沒有完全解決問題
好,對,我沒有完全解決問題,那,但是這個有限條的這個 是一個很好的出發點,讓我們知道說,機器學習其實可以做到一些事情
但那個無限條的呢,說老實話,有一點點困難,所以我們差不多要花未來兩到三次上課時間才會
完全跟大家解決說,無線條的時候到底發生什麼事,但是我們會解決,不要緊張,但是要等到- 下一次上課
好,那這邊呢,再給大家一個小小的問題說 我這邊有四個hypothesis,ok,那這四個hypothesis之間
它個別的,就是對個別hypothesis不好的資料,跟對所有hypothesis不- 好的資料的一些關係是什麼
好,這個問題稍微有一點困難一點,主要是希望大家能夠想一想
那想一想的事情呢,實際上是希望大家去想到說,其實
如果我今天對,例如說我今天是一個hypothesis,對我不好的資料
對我如果乘上那個負的,想像是我的另外一面,我的另外一面也會是不好的資料,為什麼,因- 為它所有的Ein跟Eout
都只是我反過來而已,所以我的Ein跟Eout隔很遠 它的Ein跟Eout也會隔很遠,我們兩個不好的資料會是
一樣的,一模一樣的,那這是選項二的意思,因為選項二是對的,所以
你如果回去看我們的推導的話,你會發現選項四也是對的,因為那些bad會重疊在一起
那三當然是對的,三是四個hypothesis,本來就是我們的式子,所以我們的參考- 答案是一
那下一次,我們會用到這些重疊的一些性質,來去探討說無限多條線的時候會發生什麼事情
好,總結來說呢,那我們今天呢,跟大家講的說,一開始跟大家
這個說了一個很驚悚的事情,機器學習做不到,大家本來這個
包袱收一收,準備要回家了,不過呢,我們跟大家說,其實如果加上一些假設,例如說
統計上的假設,然後說我的資料是怎麼樣產生出來,然後我要怎麼樣衡量我的表現
那我就可以把這個訓練的時候發生的事情
也就是我在我的資料上發生的這些Ein跟我在資料外看到這些Eout連結起來
那我們這個是follow了說,我們從彈珠的例子出發 我們真的可以從手上的彈珠去推論罐子裡有多少彈珠
再來,我們就可以從手上的資料去推論或者去驗證 說這個函數,如果只有一個H的話,大概會表現的好
然後我們說如果有很多H,事情變得比較複雜,但是 只要是有限個H的話,我們目前是可以做的
然後我們有限個H,然後妳的演算法如果能夠找到一個小的Ein的話,那麼learnin- g還是可行的
那我們下一次,已經跟大家再三講了,就是我們要看看如果今天M是無限大,我的hypot- hesis set裡面
有無限多個hypothesis的時候,到底是發生什麼事情,有興趣的話,歡迎大家下一- 次再跟我們一起回來
好,謝謝! [音樂]
[音樂]
[音樂]