0:00
好，所以現在看起來我們有個難題了，我們說 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 是一個過度的估計，它只是是一個
上限，它說機率的這個上限是長這個樣子。
Hsuan-Tien Lin, 林軒田教授 (Professor)
