好，所以現在看起來我們有個難題了，我們說 learning

是做不到的，我們或者說，至少在剛才那樣比較嚴格的環境下，learning

是做不到的，那我們就來想想啊，我們有學過什麼工具，

可以讓我們去把一個未知的東西做一些些推論，我們

learning learning 想要做的事情就是對那個未知的f，去做一些些推論，所以我們在什麼其他的地方，我們覺得好，雖然有一個東西我們不知

道，但是我們可以用一些方法去推論或去估計，到底這個東西是什麼樣子的，我們這邊就跟大家舉一個可能性，說不然我們來想

想好了，我今天如果給你一個大大的瓶子，大大的 bin，然後呢，

裏面有一堆彈珠，這一堆彈珠裏面有橘色的彈珠，也有綠色的彈珠，那我想要知道的事情是我們有很多很多的橘色彈珠，很多很多綠色彈珠，那

請問這裡面橘色弹珠的比例到底占多少，好，你說那我就拿出來一顆一顆一顆數，好，如果我們真的很多很多

很多的彈珠，然後你沒有辦法一顆一顆數，我們說實在話，我們真的不知道

彈珠裏，這一堆彈珠裏面橘色的比例是占多少的？

好，所以這是一個典型的問題說，我們想要知道這個罐子裏面到底有多少比例的橘色彈珠，但是我們不知道，

我們不知道，我們是不是沒有辦法做呢？那我們就想想我們有沒有辦法大概估計下，

或推論一下，說橘色的比例，或者說我拿一顆彈珠，它抽到橘色的機率到底是多少？

好，那這個聰明一點的同學可能就想到方法當然是有，

你這個彈珠如果在這邊的話，那麼你就隨機的從這個罐子裏面抓一把的彈珠起來，例如說抓10顆彈珠起來，

好，抓10顆彈珠，我們一般叫做 sample 取了這個 sample 之後呢，那把它放在那邊說，

我看看這個 sample 裏面有多少顆橘色的，例如說，我抓了10顆，這10顆裏面如果有三顆是橘色的，

那我們就說罐子里彈珠的這個比例，橘色彈珠的比例，大概是30%，

好，也就是說，我們原來做，原來這個假設的事情是什麼，我們假設說罐子裏好，橘色的機率，我們把它叫做

μ 然後呢，那當然綠色的機率就相對於是 1-μ 這是我們不知道我們想要知道的事

情，那我們做什麼呢，我們就從罐子大拉罐很多很多的彈珠，變成我們手上可以掌握的這些

sample 一般叫做樣本，那這些樣本呢，如果是從罐子裏面這個隨機，經過某一些例如說獨立的

隨機程序取樣的話，我們就會取到什麼，我們手上的彈珠裏面，我們可以說它有多少橘色的比例，我們把它叫做

ν OK，剛才那個是 μ 現在這個是 ν 那當然綠色的相對的比例就是1-ν

那手上這個因為我們手上已經抓起來了，我們抓一小把起來，手上的這個數字我們是知道的，

那大家學過機率，學過統計的話，就會知道說，這些

in sample 在我們手上樣本裏面的這個 ν 會告訴我們一些跟

out of sample 就是我們原來在罐子裏面不是在我們手上，

我們罐子裏面的那個μ 有關的資訊，好，什麼資訊呢，所以我們抽起來，

我們看看說，我們這樣抽起來，抽這些樣本起來以後，我們得到什麼樣的資訊？

他有沒有告訴我們說，罐子裏面一定有多少比例的橘色彈珠？

沒有，例如說就算這個罐子裏面，大部分都是橘色的

你抽一把起來，運氣很不好，你有沒有可能拿到全部都是綠色的，或很多很多綠色的，有可能，這個抽起來，幾率很小，但是有可能會發生

這件事，不過呢，我剛才說那一件事情的機率很小，所以有很大的機率，它告訴我們什麼，這個

μ，這個 sample 裏面的這個比例，跟我不知道的那個東西，不知道那個

μ 我有興趣的那個東西是很接近的，至少，大部分的時候是這樣，所以我沒有辦法有個確定的答案，我沒有辦法有說，

我抽10顆起來，這10顆的比例就一定是罐子裏面的比例，不過呢，大致上

OK 有很大的機率是這個樣子，好，所以這我們等一下呢，就要跟大家講說，好，這一件事情數學上

是長什麼樣子，好，數學上長相是這樣，好，所以我們現在有兩個數量，一個是我們剛才說的

μ ，這是罐子裏面的比例，第二個是 ν 這是我們手上的比例，那我們知道的事情是

這樣，如果今天我抽一把起來，我抽到蠻大的一把，

我抽一把起來，例如說，我剛才說10顆，或20顆，好，這抽一把起來，我們把這個抽的- 數量叫做

N 那我抽一把起來以後呢，大致上來說 μ 跟

ν 好，這兩個數字會很接近，很接近，我們繼續向右，在ε

OK 這個某一個誤差範圍之內來代表，那麼數學上有一個定理說，

這件事情發生的機率會很小，大家看有多小，它是 exponential

OK，-2 ε square N，也就是說你的N越多，這個從而就越小越小越小，所以你N很大很大很大的時候，這個從-

而內容非常小，那什麼東西的機率非常小，這個

μ 跟 ν 這兩個我們有興趣的數字，這兩個數字如果差很遠，差多遠？差的比

ε 來的遠的話，這個幾率很小，也就是說什麼，我們剛才說的，例如罐子裏

如果都是橘色，很多很多的橘色，所以你的μ 很大，你抽起來一把綠色，綠色代表你的這個

ν 很小，這兩件，所以一個很大，一個很小，所以相差很遠，這個相差很遠的機率

非常的小，這是這一個不等式告訴我們的事情，這個不等式一般叫做

Hoeffding Inequality Hoeffding 的不等式，它其實大家應該對它的概念都非常的熟悉，

我們剛才用彈珠來講，你丟銅板，OK，丟銅板為什麼丟了這個很多次以後，它會接近

你這個銅板真實的这个人頭的机率，或者是，好，你今天選舉到了，要做民意調查，為什麼打- 電話做民意調查，

然後跟這個最後，它的得票率會很接近，那這些都是由像

Hoeffding 這樣的這個不等式來規範的，它說如果你去想想這件事情的話，你抽樣起來的時候，你把這個

sample 抽起來的時候，看你抽的樣本多大，好，你抽的樣本如果夠大的話，那你就會發現說，

你抽樣得到的這個估計，跟你實際上有興趣的那個值不會差很多，好，也就是說，

我們如果用通俗一點的講法話，就是說我今天想要的事情是什麼？最好最好的事情是

μ 跟 ν 一模一樣，對不對，我抽起來，好，我抽起來有百分之30的橘色，我就說我罐子裏有百分之30的橘色，

好，我想要說這句話，我們現在可以大聲地說，這一句話呢，

大概是對的，大概是对的是什麼，probably OK

也就是說有很大的幾率是對的，然後呢，差不多是對的，我們叫 approximately

什麼意思，你說你抽起來30% 橘色，是不是罐子裏真的30%，不一定，抽起來30%，它可能是32，可能是33，可能-

28，可能29，但是會很接近，所以這邊有兩個詞，一個是

probably OK 大概，一個是 approximately 差不多

是對的，好，那個在英文裏面，probably approximately correct

我們一般叫做 PAC PAC 就是說，我今天我想要做這個推論，做這個估計說，我能不能由我手上的

這個樣本直接去說，罐子裏面有多少的橘色，然後那你說，可以，OK，那你要冒的風險是什麼？

大概差不多是對的，好，所以我們現在知道了這個 Hoeffding Inequality

實際上呢，不管你選擇的N是多少，你要抽多少的樣起來，還有你選擇的這個包容性

也就是說你到底要容忍多少的誤差，平常我們說差不多是對的，有一個誤差，應該有多少誤差，

這個式子通通都是對的，不管是什麼N或者是什麼ε，

然後呢，在這裡它跟它這個機率，大家看到說，它右邊這個機率這一項跟你的

μ 是什麼，無關，既然它跟 μ 是什麼無關的話，你就根本不需要知道μ 我們本來就說我們不知道

μ 然後我們我們抽起來，我們知道那個 μ 我們知道這個 sample 裏面的東西，然後我們要推論回來，

好，那 Hoeffding 提供我們這樣的推論，可以這樣做的原因是什麼，我們根本就在這個式子裏面沒有任何對那種-

我們不知道的東西的假設，好，那如果我今天抽越多越多的東西起來，大家

看到說，這個 exponential 就會越小越小越小，所以這個壞事發生的機率就會

越小越小，表示我的 μ 跟我的ν 這兩個量會很接近，那又或者什麼？

又或者我這個人更疏懶一點，我說反正我就設一個比較大的容忍度，這個容忍度內我都說差不多，我把

ε 設的比較大一點，那如果把 ε 設的比較大一點的話，一樣右邊這邊這些壞事發生的機率

就會變小，那當然這是一個有點自欺欺人的做法，說好，我容忍這個差別多一點的話，那麼我的機率

我這個式子不成立的這個機率，也就是說我的 μ跟ν

隔得很遠的機率也會變小，好，那所以這裡告訴我們如果，

我們的 sample 我們的樣本夠大的話，我們大概

可以推論說這個 μ的值就跟我們這個抽樣起來這個ν的值

是類似的，好，那這是給大家也順便複習一下，其實大家統計裏面應該要學到這個，那我們等一下，會把它用在

learning 的事件上面，好，那這邊就給大家一個題目說請算一算，說這個如果

我用 Hoeffding 去算的話，那我今天有一個特別的 ν 的選擇，

那我然後我有一個這個 μ 說到底 ν會跑到哪

一個範圍，那麼到底這件壞事發生的機率是多少，好，大家算一算之後，希望大家能夠算出正確的答案，

我們的參考答案是3，那你如果真的去算幾率的話，答案是4，OK 大家會看到說，

但是真正你要算那個機率，你就一定要知道那個 μ

OK，那個我們原來假設不知道那個μ的值是多少，你才會算那個機率，那所以3這個式子既- 然對任何的μ都對，那

我們可以想像說它其實是一個 over estimate 是一個過度的估計，它只是是一個

上限，它說機率的這個上限是長這個樣子。

Probability to the Rescue

機器學習基石上 (Machine Learning Foundations)---Mathematical Foundations

与讲师见面