# 2.1 Learning a Class from Examples

- 本節常用的符號一覽：

| 符號 | 意義 |
| ---- | ---------------------------------------------- |
| $C$ | 一個代表 family car 的 class |
| $X$ | training set |
| $x$ | 某台車的「價格」和「引擎動力」之值所構成的向量 |
| $S$ | most specific hypothesis（滿足條件下最 tight 的長方形） |
| $G$ | most general hypothesis（滿足條件下最大的長方形）|

假設我們想要 learn 一個 class $C$，代表 "family car"

我們有一個 set 蒐集不同的車，還有一群人可以去 survey，讓那些人去檢視這個 set 裡所有的車，然後一一 label，那些他們認為是 family car 的車就是 positive examples，不是的就是 negative examples。

$\rightarrow$ <font color = "snake">class learning</font> 就是去找到某個 "family car" 的描述（在這個例子裡），這樣的描述是所有 positive examples 都共享的，而 negative examples 則都沒有。

如果我們這麼做，假設給我們一台車，我們就能藉由去檢查它是否符合這樣的一個描述，來預測它是不是一台 family car。

假設我們得到的結論是人們區別是不是 family car 的標準是「價格」和「引擎動力」，那這兩個 attributes 就是 class recognizer 的 inputs。
> Note: 當我們把這兩個特點當作代表的 input，其他的 attributes 就被視為不相關的。

> 圖為 "family car" 這個 class 的 trainging set
> 這張圖中的每個圓圈代表一台車，裡面是 $-$ 代表它被認為不是 family car，裡面是 $+$ 則是。

這些 data 的數學表示方式：


假設我們最後得到的結果是這樣：

> 每個標示 $+$ 的圓圈是一台 family car，這些車都落在價格（橫軸，$x_1$）介於 $p_1$ 到 $p_2$ 之間、引擎動力（縱軸，$x_2$）介於 $e_1$ 到 $e_2$ 之間的灰色區域中。
>
> 也就是：
> 

由上方的 $(2.4)$ 我們可以確定一個 Hypothesis Class $H$，裡面包含所有可能的灰色長方形。
> 「價格」和「引擎動力」的範圍應該要落在哪裡才會被認為是 family car，這個標準可能有很多種，因此可以畫出許多種不同的灰色長方形。我們把這些可能蒐集到 $H$ 裡面。

一個 learning algorithm 就會從 $H$ 裡面找出某個特定的 $h\in H$，這個 $h$ 就是某個 $(p_1^h,p_2^h,e_1^h,e_2^h)$，去最大地逼近代表著 family car 的 class $C$。
> 在定義 $H$ 時，我們不知道到底哪一個 $h$，也就是「價格」和「引擎動力」要落在什麼樣的值裡面才能最接近「真正的 family car」，不過一但我們把關注的地方限縮到 Hypothesis Class $H$ 裡面，就能 reduce 到一個更簡單的 problem。

$\Rightarrow$ 因此，我們的目標就是：
:::warning
找到某個最接近 $C$ 的 $h\in H$
:::
> 也就是說，given 一個特定的 training set，我們要找到上文中那四個 parameters （$p_1^h,p_2^h,e_1^h,e_2^h$）的值。


> 這個 hypothesis $h$ 會去對某個 instance $x$ （某台車）做預測，使得它如果是 positive example （是 family car）就 output $1$，否則 output $0$。

- 因為在現實生活中<font color = "red">我們沒辦法知道 $C(x)$，所以我們沒辦法去評斷 $h(x)$ 和 $C(x)$ 到底有多相符</font>。我們有的只是 training set $X$，而 $X$ 只是「所有可能的 $x$ 所成的 set」 的 subset。

因為我們要找那四個 parameters 的值，所以我們要考慮所有的 $h$ （所有可能的灰色長方形），但是如果 $x_1$、$x_2$ 是實數，我們可以畫出無限多種長方形，這時候，因為要選出最好的那個 $h$，所以我們定義一個 <font color = "snake">empirical error</font>，也就是 ++training instances 裡面有多少 $h$ 做出的 prediction 和 $X$ 所給定的 required values 不相符++：

> 意思就是一一檢視 training set 裡的每台車，如果某個 hypothesis 預測某台車是 family car，但實際上它被認為不是，那這個 hypothesis 的 error 值就 $+1$，反之如果預測正確，error 值就不變。

因為我們在挑這個 $h$ 時要求它這個灰色長方形必須包含所有的 positive examples 而不能包含任何的 negative example，所以我們要求 empirical error 必須是 $0$。

但是未來如果我們給另個例子（一台新的車），它可能在一個 positive examples 和 negative examples 邊界的位置，這樣一來我們的 candidate hypotheses 就可能給出不同的答案，這也就引入一個新的問題—— <font color = "snake">generalization</font>，也就是說我們的 ++hypothesis 在分類不屬於原來 training set 的 future examples 時，到底正確度有多高。++

這個問題的有兩種極端的可能性：

1. most specific: $S$
2. most general: $G$

第一種就是去找那個（包含所有 positive 但不包含任何 negative example 的） tightest 的長方形，這樣求出來的 $h$ 我們令他 $= S$。
- 實際上的 $C$（代表 family car 的 class）可能比 $S$ 要大，但 $C$ 絕對不可能比 $S$ 小。
> 可能誤判有的車不是 fmaily car 但實際上它是，但不可能有車是 family car 但這個 hypothesis 預測它不是。

第二種就是去找一樣包含所有 positive 但不包含任何 negative example 的長方形，但這次找可以畫出來最大的那個。


所有介於 $S$ 和 $G$ 之間的 $h \in H$ 都是 valid hypothesis with no error，我們說這樣 training set 是 consistent（有解）的，而且如果蒐集所有這些 $h$，我們稱它為 <font color = "snake">version space</font>

- 實際上，根據 training set $X$ 和 hypothesis class $H$ 的不同，有可能會有很多的 $S_i$ 和 $G_j$，這些 $S$ 和 這些 $G$ 分別構成 $S$-set 和 $G$-set

$\rightarrow$ 所有 ==$S$-set== 裡的 $S_i$ 都是 consistent 的，而且不存在別的 hypothesis 更 specific 而且也是 consistent。
> 畫不出滿足條件，而且比 $S$-set 中的灰色長方形更小的長方形

Similarly,

$\rightarrow$ 所有 ==$G$-set== 裡的 $G_j$ 都是 consistent 的，而且不存在別的 hypothesis 更 general 而且也是 consistent。
> 畫不出滿足條件，而且比 $G$-set 中的灰色長方形更大的長方形

$\Rightarrow$ $S$-set 和 $G$-set 構成 boundary sets，而且任何在它們之間的 hypothesis 都是 consistent 的，同時也是 version space 的一部分。

- 有一個 algorithm 叫做 candidate elimination，會在一個個檢查 training instances 時逐漸去更新 $S$-set 和 $G$-set。
- 我們 assume training set $X$ 大到使得我們能找到 unique 的 $S$ 和 $G$。

回到挑那個最接近 $C$ 的 hypothesis $h$，一個直觀的想法就是我們直接挑介於 $S$ 和 $G$ 中間的那個，如下圖：


這樣一來，我們增加了 <font color = "snake">margin</font>，也就是和 boundary 的距離，最終我們要挑的是 ++boundary 最大且 error 最小++的 $h$。

因為我們要檢查的不只是每個 instance 有沒有在相對於 boundary 正確的那一側，我們還想知道++這個 instance 離 boundary 有多遠++，所以我們用另一個 error (loss) function
> 不像原本的 $h(x)$ 只會傳回 $0/1$，我們要的是一個會回傳 distance to the boundary 的 function。

- 在某些應用裡面，一個 wrong decision 可能是非常 costly 的，所以如果有 instance 落在 $S$ 和 $G$ 之間，我們稱為 <font color = "snake">doubt</font>，我們沒辦法很確定的去 label 它，因為我們沒有足夠的 data。在這種情況下，system 會 reject 這個 instance 然後交給專家處理。

在此我們假設 $C$ 被包含在 $H$ 中，也就是說 hypothesis class $H$ 裡有某個 $h$ 使得 error $E(h|X)=0$
> 實際上有可能根本沒辦法 learn $C$，也就是我們找不到某個 $h\in H$ 使得這個 $h$ 的 error 是 $0$。
>
> $\rightarrow$ 我們應該要確定 $H$ 是足夠 flexible 來讓我們 learn $C$ 的