# CS156_Machine Learning Course Lecture 02 - Is Learning Feasible?
###### tags: `CS156` `Machine Learning`
[撥放清單](https://www.youtube.com/watch?v=mbyG85GZ0PI&list=PLD63A284B7615313A)
[課程連結](https://www.youtube.com/watch?v=MEG35RDD7RA)
## Review of Lecture 1
- [ ] 0.41

上一節課提到，一個問題是否可以學習的三個要點：
1. 是否存在一個模式
2. 無法用數學來求解
3. 擁有相關資料

然後給出了一個信用貸款的案例，信用貸款有著一定的模式(pattern)，就是看申請人是不是有收入還有他的信用記錄等等，這些信息某種程度上跟信用表現是相關的。我們知道有這個模式的存在，但我們並不知道這個模式的具體形式為何，也沒有辦法用數學的方式來求解，只有手上過去的歷史資料。因此我們可以用機器學習來求解。

即使我們知不知道是否存在一個模式，但在手上擁有資料的情況下還是可以應用機器學習來判斷是否存在某式模式。有指標可以用來度量機器學習的效果，然後判斷是否學到東西。

至於無法用數學來求解的這個問題，如果你能夠用數學求解就直接去使用數學求解，這種方式求到的解是比較精確的。不過即使如此你還是可以用機器學習來硬train一發。

最重要的就是，你必需擁有資料，機器學習就是從資料中學習，沒有資料就沒有辦法學習，即使資料並不存在一個模式，最多就是學習失敗而以。

現階段課程只會關注supervised learning，這種情況下存在著一個target function，$f$，$f(x)$輸出即表示是否有好的信用風險，其中$x$是申請信息。值得注意的是，這個target function是未知的，它是一個非常大的假設，但你手上的資料是一個data pair，意思就是給定的資料中對信用風險的結果是已知的，我們就是用這個資料來求解這個target function。

最終求解得到的就是$g$，我們希望這個$g$ function是接近$f$這個target function。而這個$g$是從hypothesis set $\mathcal{H}$中所學習出來的。

但是最後還是有一個問題，我們真的能學到東西嗎?學到這個未知的函數。我們手上就只有一個資料集，即使資料集已經有著相關的目標值，但是資料集外的資料經過這個未知的目標函數得到的會是什麼?這後續的討論就是這節課要說的。
## Feasibility of learning - Outline
- [ ] 8.22

課程大綱，從機率談起，再跟學習演算法結合，並證明學習是可行的。

## A related experiment
- [ ] 12.30

這邊給出一個簡單的範例，有個箱子(bin)，裡面有著紅、綠兩種顏色的球，我們會從這箱子裡面隨機抽出幾個球來做為樣本，其中，抽到紅色的機率稱之為$\mu$，寫為$\mathbb{P}[\text{picking a red marble}]=\mu$。

我們可以把這個範例想成是一個二元類別的範例，因為就只有紅、綠，而且每一個樣本都是iid。我們還可以將這個箱子內視為擁有著無數個球，而紅色的球的佔比剛好為$\mu$，綠色球的佔比則為$1-\mu$，$\mathbb{P}[\text{picking a green marble}]=1-\mu$。其中$\mu$是一個未知的值，而且從圖片來看，紅色的球比綠色的小，因此$\mu<1-\mu$。不過現實中我們在sample樣本的時候是不可能可以看的到樣本全貌的，也因此我們才會說$\mu$是未知的。

現在，我們隨機的從這箱子內取出$N$筆資料，這邊的$N$所代表的就是學習演算法中資料集的數量(課程中刻意使用相同的符號)。抽出來的樣本就像是上圖中所呈現，值得注意的是，$\mu$依然是未知的，而每一個人抽出來的樣本可能都是不一樣的，這是一個機率問題，因此，我們將抽出來的樣本是紅色的機率以符號$\nu$($nu$，不是$v$)來表示。可以發現到，上圖簡報在SAMPLE的部份並沒有寫成$\nu=$fraction of red maribles，因為我們在意並不是樣本內的資料，而是實際的資料，因此$\nu$對它而言是不重要的，因為$\nu$並不能代表實際的資料，而我們真正關心的是實際的資料，因此保留$\mu$，而刪除$\nu$(這堂課的觀點如此)。
## Does $\nu$ say anything about $\mu$?
- [ ] 14.43

現在，我們要先關心一個問題，那就是$\nu$是否可以代表$\mu$?簡單的回答是不行，以上圖為例，實際資料中多數為紅色球，但樣本卻是多數為綠色球，比較極端一點的案例就是你的樣本通通是綠色球，這確實是可能的，只是機率不高，但這並不能代表實際資料皆為綠色球，對吧?

但完整的回答是可以，只是在說明這個問題之前要討論很多事情。從機率論來看，只要你的樣本夠大，那$\nu$就會非常近似$\mu$。

這兩個答案的主要分別在於"可能"與"很有可能"。

## What does $\nu$ say about $\mu$?
- [ ] 20.04

從機率的角度來看，$\nu$是可以反映出$\mu$的。更直白的說，在一個足夠大的樣本數中($N$)，$\nu$是可能近似$\mu$的(記得，$\nu$是樣本平均，$\mu$是總體平均)，而且它們之間相差小於$\epsilon$。

如果我們要描述一件事發生的機率很小，通常這件事不會是什麼好事，所以我們才會希望它發生的機率很小，也就是$\mathbb{P}[\text{bad thing}]$，而這件不好的事就是$\nu-\mu>epsilon$的機率，即$\mathbb{P}[\vert \nu - \mu \vert > \epsilon]$，上面我們已經提過，它們之間相差小於$\epsilon$，因此只要超過$\epsilon$就是我們所不樂見，我們希望發生這件事的機率愈小愈好，我們保證這個機率小於$e^{-N}$，即$\mathbb{P}[\vert \nu - \mu \vert > \epsilon] \leq e^{-N}$。

這是一個好消息，因為負指數下降的非常的快，所以只要樣本數$N$夠大，那發生這件事的機率就會非常的小。但壞消息是，沒那麼簡單，我們還要考慮我們所能容忍的差值，也就是$\epsilon$，因此，考慮進去之後整體來看是$e^{-\epsilon^2N}$，也因此你能容忍的愈小，在經過$\epsilon^2$之後所付出的代價就愈高。如果你能容忍的是0.1，那經過平方之後就是0.01，如果你的樣本數$N=100$，那就是$e^{-1}$。這意謂著，你的容忍值愈小，你所要付出的代價就會愈高。

最後再小調整一下，會得到最終的公式，$\mathbb{P}[\vert \nu - \mu \vert > \epsilon] \leq 2e^{-2\epsilon^2N}$，雖然老師課堂上開玩笑的說，加入2是因為2的發音像true，但實際上這個公式就是著名的Hoeffding不等式(Hoeffding's Inequality)，這個公式會伴隨著我們的課程，一直到證明VC dimension都是用到這個公式。

最終我們希望得證的是$\mu=\nu$，但這不大可能，因此我們只會說，它們之間是PAC，也就是可能近似正確(Probably Approximately Correct)，其中probably來自指數項，$-2\epsilon^2N$，approximately來自$\epsilon$，所以我們希望它們之間的差異非常的小。
## Hoeffding Inequality
- [ ] 26.00

$\mathbb{P}[\vert \nu - \mu \vert > \epsilon] \leq 2e^{-2\epsilon^2N}$

這邊寫下整個Hoeffding Inequality，要記得，$\mu$是實際的紅球機率，也就是箱子內的實際紅球，而$\nu$是抽出來的樣本紅球機率，樣本中沒有寫下$\nu$ = fraction of red marbbles是因為每次抽的樣本得到的值都不一樣，因此沒有寫。

Hoeffding Inequality：
* 適用於任意的$N$與$\epsilon>0$，這意謂著你可以選擇任意的樣本數以及任意的容忍值在hoeffding inequality上都是成立的，這是大數法則的一種形式
* 邊界不取決於$\mu$
* 首先看不等式左邊的部份，這個機率明顯是決取於$\mu$，$\mu$影響著$\nu$的機率分佈($\nu$是從箱子內sample出$N$樣本所得的機率)，這是一個二項分佈的概念，根據$\mu$就可以算出$\nu$等於任意值的機率。因此，是否超過容忍值$\epsilon$的機率也是取決於$\mu$，不過我們對$\mu$沒什麼興趣，我們單純的想知道它的邊界，也就是$2e^{-2\epsilon^2N}$，可以發現，這個邊界值並沒有$\mu$，因為我們知道$\mu$是一個未知的值。現在，不管$\mu$是什麼，我們都可以根據樣本數$N$以及容忍值$\epsilon$來計算出它的邊界為何。
* $N, \epsilon$與邊界的權衡
* 相同的bound情況下，$\epsilon$愈小，那就意謂著你的$N$就要愈大，反之，你的$\epsilon$愈大，代表很好達成，自然需要的$N$就不是那麼大，這是一種取捨。因此，很明顯的，樣本愈大，我們就更相信$\mu$會接近$\nu$。
* $\nu \approx \mu \Rightarrow \mu \approx \nu$
* 這有點饒舌，當我們在進行實驗的時候並不知道$\mu$長什麼樣子，它是個未知值，唯一知道的隨機變數就只有$\nu$，我們利用hoeffding inequality從$\nu$來推論出$\mu$，這並不是一個實際發生的因果關係，如果從因果關係來看是$\mu$影響$\nu$，而不是$\nu$影響$\mu$。很幸運的是，不等式的左邊項目的機率形式是對稱的。因此，雖然實際上應該說$\nu$會接近$\mu$($\mu$不變)，但因為對稱性質，因此我們也可以說，我們已知$\nu$，而$\mu$有接近$\nu$的趨勢。
## Connection to learning
- [ ] 27.21

有了稍早的數學補充知識，現在要將之與學習連結在一起。在箱子角度，我們想知道的是裡面的機率分佈，也就是求那一個未知數，$\mu$。但是在學習的角度，求的是一個target function，$f:\mathcal{X} \to \mathcal{Y}$，這個function存在著一個domain，$\mathcal{X}$，也許是一個高維度的歐幾里得空間(Euclidean space)，而$\mathcal{Y}$可以是任意的。function包含大量的信息，但箱子只存在一個數值，這就是兩者之間的差異，而我們要將這兩者連結起來。

- [ ] 28.07

將兩者連結的作法如下說明，我們首先假設箱子是學習問題的輸入空間，每一個小球就對應一個$x$，如果是上一節課所提的信貸申請的話，每一個$x$可能就記錄著客戶的資訊，這些小球集合成一個空間，也就是$\mathcal{X}$，寫成$x \in \mathcal{X}$。

- [ ] 29.12

* 綠色點代表著你的hypothesis，$h(x)$，所預測的結果與target function，$f(x)$，吻合。雖然我們並不知道那些點是綠色而那些不是(因為我們並不知道target function的全貌)，但我們至少可以利用這個方式將target function與$\mu$連結起來。
* 紅色點代表的是hypothesis的預測結果與target function不相同。

現在，整個問題已經簡化成hypothesis與target function的結果是否相同，根據上面的定義賦予每一個點一個顏色。也可以注意到，即使這個箱子本身存在著一個機率，但是在談學習問題的時候是沒有談到機率的，我們唯一有的就是一個資料集來做研究而以，所以我們還要再做一些調整，讓學習可以跟機率有關聯。
## Back to the learning diagram
- [ ] 32.44

回到第一節課提過的learning diagram。最上面的target function是未知的，我們也不打算去碰它，演算法唯一有的信息就是訓練樣本，再根據訓練樣本從hypothesis set裡面挑一個function來做為最終的hypothesis $g$。

在箱子的範例中，那個箱子就是一個輸入空間，這個輸入空間中存在著一個機率，我們要將這個機率應用在這個輸入空間所生成的資料點上。

假設，輸入空間的資料點是$d$維的歐幾里得空間，每一個資料點都有一個被sample到的機率，以$P$表示，然後有幾個假設：
1. 這個$P$本身並沒有任何的假設，它可以是任意值，就是一個機率值
2. 我們甚至不需要知道$P$是什麼，即使$P$會影響選到紅或綠球的機率，也就是會影響$\mu$，但是因為我們用Hoeffding Inequality直接來bound，是不受$\mu$影響的，這對學習的可行性提供了很大的幫助
3. 我們利用$P$生成$x_1, \cdots, x_n$的資料點並假設它們是i.i.d(獨立同分佈)，這是唯一的假設

我們沒有對target function做任何的假設，跟它完全無關，我們只有假設資料是根據$P$的機率分佈採樣而來。
## Are we done?
- [ ] 36.30

目前為止我們還沒有完全的解決問題，稍早前提過，紅色、綠色兩個色球對應於hypothesis $h$與target function是否一致。意思就是，當你確定你的$h$的時候，也相對的確定每一個球的顏色。所以上圖可以看的到，當$h(x)=f(x)$就會是綠色，反之當不相等的時候就是紅色。

對於這個hypothesis $h$而言，$\nu$可以泛化到$\mu$，而$h$可以是任意的，但問題在於我們一直討論的都是驗證，而不是學習。如果我們希望它能做到的是學習而不是驗證，那我們並沒有辦法保證$\nu$會很小，並且我們會從多個hypothesis中選擇一個$h$。這邊的每一個hypothesis都會看過所有的樣本，然後再從中找出一個對樣本而言最有利的hypothesis $h$(誤差最小的假設)。

課程中雖然提了一個範例，但不是很清楚老師所說的意思...
## Multiple bins
- [ ] 38.56

既然我們說，我們會有很多個hypothesis，然後再從中挑出一個最好的，那我們就用很多個箱子來觀察不同hypothesis。

上圖可以看的到，$h_1, h_2$所呈現的箱子顏色不同，以最右上的球來看，$h_1$是紅，而$h_2$是綠，這是因為$h_1$的預測與目標函數是不同的所造成，而$h_2$的預測與目標函數相同，因此為綠色。課程暫時假設hypothesis是有限的，因此我們擁有$M$個hypothesis。

每個hypothesis都有不同的隨機抽樣的樣本，現在就可以開始進行學習，抽象來說，學習的過程就是要描述這些樣本，然後找出一個好的樣本，當我們找到好的樣本的時候，就可以依據Hoeffding不等式說，我們成功了。
## Notation for learning
- [ ] 42.18

下面說明會用到的一些符號，以利後續的討論：
* $\nu$，in sample(樣本內)的frequency，所給定的資料中發生情況的標準定義，如果樣本內的表現很好，那就說明給定的樣本內的誤差很小，以$E_{in}$來表示樣本內的誤差，為了讓它跟hypothesis有關聯，因此寫為$E_{in}(h)$，以此估算hypothesis與target function之間的誤差，不同的$h$就會得到不同的$E_{in}(h)$
* $\mu$，out of sample(樣本外)，意味著我們看不到的資料，也就是我們希望學習好之後在這邊也可以很好的地方，以$E_{out}$來表示，為了讓它跟hypothesis有關聯，因此寫為$E_{out}(h)$

可以發現，不管是$\mu$還是$\nu$都是取決於hypothesis $h$。回頭看一開始的Hoeffding inequality：
$\mathbb{P}[\vert \nu - \mu \vert > \epsilon] \leq 2e^{-2\epsilon^2N}$

根據上面的定義，我們調整如下：
$\mathbb{P}[\vert E_{in}(h) - E_{out}(h) \vert > \epsilon] \leq 2e^{-2\epsilon^2N}$

意義上來看是一樣的，樣本內的誤差與樣本外的誤差之間的差異還是一樣要大於一個容忍值$\epsilon$，我們希望這個機率是小於右邊項目。注意到，這邊是連箱子的符號也有跟著變動。
## Notation with multiple bins
- [ ] 43.10

現在，我們將剛剛所定義的符號套在多個箱子上：
* $E_{out}(h)$，樣本外，也就是下面那一個row的樣本外的資料
* $E_{in}(h)$，樣本內 ，也就是下面那一個row的資料

很明顯的，樣本外的誤差取決於你的hypothesis，而樣本內的誤差會隨著樣本不同而不同，
## Are we done already?
- [ ] 44.10

不過就算我們做了調整，還是沒有解決學習的問題，因為Hoeffding inequality並不適合用在多個箱子的情況。

## Coin analogy
- [ ] 46.59

這邊先用範例說明為什麼不適用，再說明我們可以怎麼調整。課程中老師要求大家拿出硬幣投個五次，看看有沒有人是連續五次的正面。課程中確實有同學是連續五次正面，老師稱這個是一個biased coin。因為剛剛課程中說in sample相對應於output of sample存在著一個Hoeffding inequality，因此當你得到連續五次的正面就代表這個硬幣是很容易得到正面的。如果這不是一個biased coin，那是什麼原因造成的?

回頭看問題，簡報上主要以投擲10次做測試，假設手上擁有的是一個公平的硬幣(正反機率一致)，然後你投擲10次，得到連續10個正面的機率是$0.5^{10} \approx 0.1%$，機率非常的小。如果我們有1000個硬幣，那我們得到連續10個正面的機率就變成$\approx 63%$。

這代表什麼?這代表著這種情況下得到10個正面並不能反映出真實的機率。會發生這樣的問題是因為你嚐試太多次，最終發生的是，因為Hoeffding作用在每一次的投擲，但還是存在一定的機率，假設是0.5，0.5是正，0.5是反，如果你嚐試的次數夠多，而且很幸運的讓這些0.5%是不相交的(disjoint)，那最終會發現，壞事還是會以較高的機率發生，這就是問題的關鍵。
## From coins to learning
- [ ] 49.18

我們把剛剛的硬幣問題跟學習問題放在一起看，硬幣是一個正反面的問題，箱子內的球是紅、綠色的問題，都是二分類的問題，因此關聯起來是沒問題的：
1. 將獲得正面的機率定義為$\mu$，相對應得到紅色球的機率
2. 硬幣是一個公平硬幣，因此這個範例下的所有箱子內的紅、綠色的其都是一半一半

現在我們開始採樣，第1、2個箱子取出來的都不是我們想要的，因為我們希望我們的hypothesis可以完全正確，因此我們希望全部都是綠色(代表$h(x)=f(x)$)，終於，在一起的採樣中發生這樣的奇蹟，全部都是綠色的。但是很明顯的，這並不是一個正確答案。我們需要一個好的工具來處理這樣的多個箱子的問題。

在一次實驗的情況下Hoeffding inequality確實是有效果的，但它的約束會隨著你實驗次數的增加而減少，我們需要瞭解是什麼造成減少。
## A simple solution
- [ ] 52.55

$\mathbb{P}[\vert E_{in}(g) - E_{out}(g) \vert > \epsilon] \leq$

上面的不等式是課程中提過的壞事發生的機率，注意到，是$g$，不是$h$，因為$g$是我們最終的那一個hypothesis，而我們希望$g$得到的樣本內的誤差跟樣本外的誤差愈接近愈好，因此我們想要這個誤差超過容忍值$\epsilon$的機率能夠愈小愈好。

我們需要一個更強的Hoeffding，因為我們將$g$考慮進來，這不僅是一個固定的hypothesis與一個固定的箱子，它涉及大量的箱子，而且我們觀察隨機樣本就是為了從中選擇一個。

假設我們有$M$個hypothesis，$h_1,h_2,\cdots,h_M$，是有限的，調整公式之後，我們得到：
$\mathbb{P}[\vert E_{in}(g) - E_{out}(g) \vert > \epsilon] \leq \mathbb{P}[\vert E_{in}(h_1) - E_{out}(h_1) \vert > \epsilon \text{ or } \vert E_{in}(h_2) - E_{out}(h_2) \vert > \epsilon \cdots \text{ or } \vert E_{in}(h_M) - E_{out}(h_M) \vert > \epsilon]$

我們所選擇的最終的那個hypothesis $g$是不好的機率會被上面的不等式bound住。這很明顯，因為$g$也是裡面的其中一個hypothesis，這在機率裡面稱為union bound，在union bound裡面並不考慮重疊的問題，因此這個不等式可以寫成：
$\mathbb{P}[\vert E_{in}(g) - E_{out}(g) \vert > \epsilon] \leq \sum^M_{m=1}\mathbb{P}[\vert E_{in}(h_m) - E_{out}(h_m) \vert > \epsilon]$

這是一個非常寬鬆的邊界(upper bound)，你也可以把它想成是一個worst case，就是把所有不好的機率加總起來就對了，最壞也就是這樣而以。

這麼做的好處在於，每一個相加項目都是一個固定的hypothesis，我們只是把每一個事先聲明好的hypothesis的機率相加，那就不會有剛才無法使用Hoeffding的問題出現，每一個都是我們已經解決過的單一個實驗，最多就是$M$個，然後再將每一個項目都替換成Hoeffding所給出的邊界。
## The final verdict
- [ ] 55.49

替換成Hoeffding所給出的邊界得到一個不等式：
$\mathbb{P}[\vert E_{in}(g) - E_{out}(g) \vert > \epsilon] \leq \sum^M_{m=1}2e^{-2\epsilon^2N}$

這意謂著樣本內外誤差大於容忍值的這個壞事跟你的hypothesis有關，我們說我們有$M$個hypothesis，也就是，$\mathbb{P}[\vert E_{in}(g) - E_{out}(g) \vert > \epsilon] \leq 2Me^{-2\epsilon^2N}$，這代表你的$M$愈大，出現壞事的機率就會跟著變大。上一堂課的QA提到過，如果你的模型過於複雜，那也許對樣本內的資料有很大的記憶效用，但是它並不能很好的泛化到樣本外的資料。將模型的複雜想成$M$，也就是你的模型有著大量參數的情況下，你的樣本內外資料將會失去連結。

我們希望利用樣本內的資料來觀察樣本外的狀況，因此當模型愈複雜，那兩者之間偏離的機率就會愈大。因為它們的upper bound已經愈來愈大，這意謂著兩者之間也允許愈來愈寬鬆。

## QA
Q1：當Hoeffding inequality所給出的bound是沒意義的時候會有什麼情況?比如小於2。
A1：要嘛資料的品質，要嘛資料的數量不足以保證其泛化的能力，或許你所設置的容忍值$\epsilon$過於嚴謹，不然這沒什麼。舉例來說，總統大選你在路上隨機拉了5個人問他們傾向，這5個人的結果並不能代表什麼，我們需要更多的反饋。

Q2：在perceptron的範例中，每一組w會被視為新的m嗎?
A2：事實上，我們所談的每一種學習模型，其hypothesis的大小都是無限大，不過後續的課程會提到另一種有限的抽象概念，將它應用在這個新的Hoeffding inequality上。

Q3：關於課程中提到的$\nu=\mu$，反之$\mu=\nu$的概念。
A3：這在統計學與機器學習中很常見，對於一個機率與樣本而言，何為因，何為果?機率生成一個樣本，如果知道機率那就可以知道你有多大的可能得到這樣一個樣本或其它樣本。那反過來，如果你有一個樣本，要反推什麼樣的機率可以生成這樣的樣本，這就是用結果(抽到一個樣本)來決定原因(反推機率)，而不是原因推導結果。在箱子的問題也是一樣，箱子是原因，而樣本中的frequency則是結果，只要知道箱子的情況就可以知道樣本中的分佈狀況。在學習的效用中，我們通過觀察樣本來推理箱子的情況，這就是一種用結果來推理原因的情況。從$\mathbb{P}[\vert \nu - \mu \vert > \epsilon] \leq 2e^{-2\epsilon^2N}$來看，$\nu$是隨著抽樣的不同而變動，而$\mu$是固定的。當$\nu$與$\mu$一致的時候我們就說，就是這個$\nu$，然後以此推理什麼樣的$\mu$會產出這樣的樣本。這邊比較多是邏輯問題，而不是數學問題。

Q4：一個複雜的模型會有大量的$h$，是否一個$h$就對應一個模型?
A4：每一個$h$都是一個hypothesis，我們會從裡面挑出一個特定的函數來做為最終的函數$g$，也就是最接近目標函數$f$的那一個函數。模型是為了找出最好的hypothesis而可以進行搜尋的那些hypothesis，也就是hypothesis set，$\mathcal{H}$。直覺上可能會用hypothesis的大小來度量複雜度，但不清楚這個數字是否跟複雜度有相對應關係，後續會有更深入的討論，像是單一hypothesis的複雜度與包含所有hypothesis的複雜度。

Q5：怎麼選擇$g$?
A5：我們已經有一種方法可以選擇，那就是perceptron learning algorithm。有著一個hypothesis set $\mathcal{H}$，其包含一系列的$h$，為空間上不同的線，利用perceptron learning algorithm來從中選出一個適合的$g$，在假設資料是線性可分的情況下，最終結束迭代就代表完成分類，這個時候所得到的hypothesis $g$就是我們所要的$g$。這取決於你的資料，也取決於你的學習模型。

Q6：如何擴展這個公式來支撐輸出是一個取值範圍內的反饋，而不是一個二分類的反饋?
A6：課程中說過，不等式$\mathbb{P}[\vert \nu - \mu \vert > \epsilon] \leq 2e^{-2\epsilon^2N}$的右邊項目是一個均勻分佈，如果現在做的不是一個二分類的實驗(箱子實驗是紅、綠的二分類實驗)，我們考慮的不再是錯誤的機率而是某個變數的期望值以及樣本中該變數的平均值，那$\nu, \mu$會非常接近(這需要做一些技術性的修改)。基本上，在大數定理的集合中，這只是其中一個成員，很多的成員實際上與期望值、樣本平均值有關。如果將函數定義為1、0，然後關注它的期望值，這種情況下會將給定的樣本視為樣本平均值，而機率則為期望值。所以二分類並不是一個完全不同的情況，只是一個更好處理的特殊情況。其它情況下，有個值得關注的點，那就是變數的方差，它會影響bound。選擇$\epsilon$做為容忍值是因為變數的方差是非常有限的，如果說機率是$\mu$，那方差就是$\mu(1-\mu)$，那只是從一個常數經過計算再得到另一個新的常數而以。如果你有一些方差特別大或小的樣本，那它會影響對$\epsilon$的選擇，從而保證這個不等式是有效的。因此，針對問題的簡單回覆是可以做的到但需要技術性的改造，唯一要考慮到的就是剛才所提的變數的方差。(這邊不是很清楚老師的回覆)

Q7：為什麼會有多個箱子?
A7：箱子只是工具，幫助我們從機率的角度來說明學習是可行的。如果只用一個箱子，你會發現到，你在處理的就是你的hypothesis set只有一個hypothesis。也因為你只有一個hypothesis，你做的就是驗證其樣本內的效果與跟樣本外的效果相關，因為這個是由Hoeffding inequality所保證的效果。如果需要真正的學習，那就需要更多的hypothesis，不能只有一個。箱子隨著hypothesis而變化，你隨機挑出來的石頭是紅的還是綠的是取決於你的hypothesis是否與target function的結果相同。所以我們需要多一點的箱子，也就是多一點的hypothesis來利用樣本內的資料找到樣本內效果最好的，然後希望應用在樣本外一樣好的那一個hypothesis。

Q8：是否可以說明機率與$mathcal{H}$的關係。
A8：$\mathcal{H}$是一個固定的hypothesis set，不存在機率問題，唯一會有機率問題的就是在$\mathcal{X}$集合上的一個機率分佈。(見簡報8)

Q9：以perceptron為例，如果資料是線性可分的，那可以分割空間的線很多，該怎麼選擇最好的那一個?
A9：課程後面會提到，理論上會得到一個最好泛化效果的那一個解。

Q10：不管你怎麼挑那個最終的$g$，Hoeffding inequality都會成立嗎?
A10：寫下$g$的同時，就已經在討論任意的hypothesis。定義上，$g$就是最終的hypothesis，而你的演算法可以從hypothesis set裡面選擇任意一個hypothesis來當做$g$。所以$g$並不是一個固定的hypothesis，它是一個從整個hypothesis set裡面根據資料與學習規則找出來的那一個被稱為正確的hypothesis。因此，很明顯的$g$可以不一定，而且都會成立。

Q11：對於perceptron或linear algorithm來說，有一點疑惑的是，每一個步驟都存在一個hypothesis，但(還沒有結束，老師就回答)
A11：這個過程我們是不可見的，就像課程說的，我們有資料，然後演算法弄一弄就得到一個最終的hypothesis，過程中很明顯的要訪問到大量的hypothesis，從資料中抽象來觀察它們。在實務上，這些事會發生在一個空間內，然後通過修改某些參數從一個hypothesis跳到另一個hypothesis，直到最後找到那個最終的hypothesis，稱之為$g$。另一方面課程中用union bound將worst case的狀況加總起來，這個泛化的邊界會作用到每一個hypothesis上面，不論你是否在過程中有訪問到這個hypothesis。因為我們得到樣本內外偏差邊界的方式是考慮所有的hypothesis所得，從樣本內到樣本外，與$\epsilon$緊密相關。這樣的保證讓我們不管選擇那一個hypothesis都是可以的。這樣的作法可能有點overkill，但往好處想，即使是中間值也會有好的泛化能力，這些值不只可以用來探索，還可以直接做為答案。

Q12：還是不明白Hoeffding inequality如何保證學習可行。
A12：Hoeffding表明了驗證是可行的。如果你有一個樣本，而且你有一個問題要問，然後你可以看到樣本內的這個問題是如何被回答的，我們有理由相信，多數人的答案會跟你樣本的結果是相近的，這是驗證的過程。為了將驗證轉到學習，課程中調整不等式(簡報第24頁)，讓不等式同時應用在大量的hypothesis上，也就是簡報上紅色字體的$M$。調整之後它已經不是一般的Hoeffding，但我們依然稱之為Hoeffding，不同的是新的這個Hoeffding可以$M$個hypothesis的情況，同時保證能夠滿足要求。雖然這個機率比之前還要來的寬鬆，因為你有多個壞事發生的機率會比你只有一個壞事要發生的機率來的大，我們是用union bound來加總這個i.i.d的機率分佈。

Q13：我們是否可以說，箱子對應整個群體?
A13：箱子對應賦予球顏色之前的整個群體。簡報中有一個灰色箱(簡報第9頁)，這個灰色的箱子就是老師所說的generic input，稱為$\mathcal{X}$，也是輸入空間。然後再根據hypothesis來上色。確實，這個箱子可以對應整個群體。

Q14：Hoeffding inequality與統計學裡面的p值是否有關聯?
A14：有的。如果我有一個樣本，當我對這個樣本進行推理，而且這個結果是可靠的，與樣本外的表現差不多，這個這個偏離的機率會需要很多的工作。統計學中的p值就是其中一個方法，當然還有其它相應的大數定理。課程中只是從很多的理論中挑一個來說明，一路用這個公式推理到VC-dimension。

(- \[\s\]\s\d{1,2}[.\d{1,2}]+)