Learning from Examples

Introduction

Learning : agent 透過 observation 來加強對未來 tasks 的 performance
- 從 input-output pairs 找出一個 function，能夠從新 input 預測 output
Why learning
- 一般程式設計無法掌握所有狀況
- 一般程式設計無法隨時間改變
- 有時候 programmer 甚至不知道該如何設計程式來解決問題

Supervised Learning

training set
- input-output pairs $(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)$
- 每個 $y$ 都是被一個不知道的 function $f(x) = y$ 所產出
- 我們目標是找到一個 function $h(x)$ 他可以非常接近 $f(x)$
hypothesis
- hypothesis 就是我們要找到那個 function
- learning 就是在一群 hypothesis 中找到最好的那一個
- 即使在之後帶入新的 data 也可以很好的 perform
test set
- 跟 training set 格式一樣
- 是用來檢驗 hypothesis 的精準度有多高
classification
- 若 y 是一個 finite set 裡面的某個 value
- 那這種 learning 稱為 classification
regression
- 若 y 是一個可以任意變動的 number
- 那該 learning 就稱為 regression

Ockham's razor

一樣的 training sets 可以找出多種不一樣維度的 hypothesis
例如圖 (c) 當 x 越大，反而 y 卻掉了下來，可能不是一個好的 hypothesis
Ockham's razor 告訴我們要優先選擇 the simplest one
所以在求取 hypothesis 時
不只單看 possible/impossible，而是要觀察是否 probable
我們可以定義一個 $h^\star$ 來表示達成 probable 的 hypothesis
$\begin{aligned} h^\star &= argmax_{h\in\mathcal{H}}P(h\mid data)\\ &= argmax_{h\in\mathcal{H}}P(data\mid h)P(h) && \text{(Bayes' rule)} \end{aligned}$
- 其中的 P(h) 機率會在 polynomial 為 1-2 時較高，變成如圖 (b) 這類 7-8 時變低
每個 hypothesis 的表現和複雜度都是一個 tradeoff
但大多的 learning 都是 focus 在 simple representation

Learning Decision Trees

Input 一個 attributes vector 要 return 一個 "Decision"
目前只針對 true/false 的 boolean classification
Decision tree 會經由一連串的 test 才走到 decision
下面舉例一棵 decision tree 來決定要不要等待餐廳的排隊

Decision tree 會藉由一系列的 attributes (下圖中間部分)
- 來產生一個個 $(x, y)$ pairs
  - x 是 input examples
  - y 是 output decisions

Create Decision Trees

要從一堆 training sets 來建立一個 Decision Tree 其實很困難

我們會使用 Decision-Tree-Learning algorithm 來建立 decision tree

Decision-Tree-Learning algorithm 是一個 Greedy 和 Divide-and-conquer 的算法

每次都尋找最重要的 attribute 做為分支點

最重要的 attribute 代表可以將 Decision 拆分的最乾淨

例如圖 A 的 Type 就是較差的 attribute，他將 decision 拆成四項，但 yes/no 在每項還是很平均

而圖 B 的 Patrons 就是一個不錯的 attribute，很好的分散了 yes/no decision

在每次的分支後，新的 outcomes 代表的又是逼個新問題，可以再次進行分支

Performance

我們會使用 learning curve 來評估 decision tree 的 accuracy

將 data 拆分為 training sets 和 test sets

假設有 100 筆資料

將 training set 設定為 1, 2, ... 99 個，每次剩下的作為 test set

每回合進行 20 次左右測試

重複操作就可以得到 learning curve

X 軸為該回合的 training set size
Y 軸為 test set 的 accuracy

Choosing Attribute tests

要怎麼從 attributes 中找到 best attribute

也就是將 data 拆分成 "good" 和 "useless" 的測量方法

也就是 Entropy 的概念

何謂 Entropy

Entropy 可以用來表達資料量的多寡
當我們對資訊掌握越高，代表不確定性越低
$100 \%\,\, \text{Certainty } \rightarrow (\text{Entropy } = 0)$
所以當 entropy = 0 時，代表無法從事情中得到任何 information
而一個 fair coin 為 1 bit of entropy
fair 4-sided die 則有 2 bit of entropy

越確定 => entropy 越低

越不確定 => entropy 越高

很少發生但發生了 => entropy 很高

可以將 entropy 記為不確定性 (0 => centainty, 1 => uncertainty)

計算 Entropy

當我們有 random variable $V$ 以及他的值 $v_k$

然後他出現的機率為 $P(v_k)$

那 entropy 就是

H(V) = \sum_kP(v_k)\log_2\frac{1}{P(v_k)} = -\sum P(v_k)\log_2P(v_k)

若 P 很小取 log 就會變很大的負數

乘上原本的 P 得到加權平均

最後加上負號，就會變成很大的正數 (機率很小，資訊量很大)

舉個例子 :

Fair coin flip is really 1-bit entropy
$H(\text{Fair}) = -(0.5\log_2 0.5 + 0.5\log_2 0.5) = 1$
coin with 99% heads
$H(\text{Loaded}) = -(0.99\log_2 0.99 + 0.01\log_2 0.01) \approx 0.08 \text{ bits}$

Entropy 還可以用來計算 boolean random variable

當 q = true 的 probability 時，Entropy 可以計算為

B(q) = -(q\log_2q + (1-q)\log_2(1-q))

Using Entropy in Decision-Tree Learning

如果有 p 個 positive examples 和 n 個 negative examples 時

我們計算 Goal 的 entropy 為

H(\text{Goal}) = B(\frac{p}{p+n})

例如餐廳的例子中 $p = n = 6$ ，所以 entropy = B(0.5) = 1 bit

但是單求這個 goal 的 entropy 是不夠的

我們將利用原本的 entropy 來減去 attribute test 後的 entropy

看誰造成 entropy 下降最多，讓 data 區分成更有確定性，那他就是最重要的 attribute

Remainder

Attribute $A$ 可以將 data 切成 $E$ subsets 分別為 $E_1, ..., E_d$
每個 subset $E_k$ 都有 $p_k$ 個 positive 和 $n_k$ 個 negative examples
每個 subset 的 entropy 我們記為 $B(\frac{p_k}{p_k+n_k})$
隨機選到第 k 個 subset 的機率為 $\frac{p_k+n_k}{p_n}$
所以我們用以下式子計算經過 attribute A 之後，剩餘的 entropy 為

\text{Remainder}(A) = \sum_{k=1}^d\frac{p_k+n_k}{p+n}B(\frac{p_k}{p_k+n_k})

Information Gain

我們用 Information gain 來表達經過 attribute A 銷掉的 entropy 有多少

銷掉越多， $Gain(A)$ 越大，代表 data 從不確定變得更加確定

\text{Gain}(A) = B(\frac{p}{p+n}) - \text{Remainder}(A)

同樣舉餐廳例子 :

\begin{aligned} \text{Gain(Type)} &= 1 - \begin{bmatrix} \frac{2}{12}B(\frac{1}{2}) + \frac{2}{12}B(\frac{1}{2}) + \frac{4}{12}B(\frac{2}{4})+ \frac{4}{12}B(\frac{2}{4}) \end{bmatrix} = 0 \text{ bits}\\ \text{Gain(Patrons)} &= 1 - \begin{bmatrix} \frac{2}{12}B(\frac{0}{2}) + \frac{4}{12}B(\frac{4}{4}) + \frac{6}{12}B(\frac{2}{6}) \end{bmatrix} \approx 0.541 \text{ bits} \end{aligned}

可以看見，Attribute Type 沒有減少任何的 entropy

而 Attribute Patrons 則幫忙減少了 0.541 的 entropy

所以 Patrons 很合理是 best attribute

Generalization and overfitting

Overfitting

Overfitting 通常會發生於 hypothesis space 跟 input attributes 增加

Training examples 的增加則不會造成 Overfitting

在之前舉例的 regression 中，下圖 b 和 c 就有明顯的 overfitting 現象

而 Decision Tree 也會有 Overfitting 的問題

Decision Tree Pruning

我們可以使用 decision tree pruning 的技巧來解決 overfitting

把 irrelevant 的 attribute test node 剪掉
通常為 branch 只剩下 leaf nodes 的 test node
刪除之後再用 leaf 來 replace 該 node
要怎麼抓出這些 irrelevant attribute ?
- 通常是 positive ratio 和整體的 positive ratio 差不多的 attribute test
- 這些 attribute 的 information gain 又會接近 0
  - 雖然跟建樹時一樣可以用 gain 來剪樹
  - 但這邊指的是 entropy 非常小的下降可以視為 irrelevant
  - 所以我們需要定義 entropy 下降多少稱作「非常小的下降」
  - 也就是需要定義一個 threshold

Pruning Threshold

我們可以利用統計學裡的 significant test

定義 Null hypothesis = "attribute test 做的結果跟沒做一樣"

接著測量 deviation :

\Delta = \sum_{k=1}^d\frac{(p_k-\hat{p_k})^2}{\hat{p_k}}+\frac{(n_k-\hat{n_k})^2}{\hat{n_k}}

我們可以使用 $\chi^2$ table 來檢驗 deviation 是否 reject null hypothesis

所以這個方法又叫作 $\chi^2 \text{Pruning}$

Early Stopping

因為 $\chi^2 \text{Pruning}$ 跟 information gain 看起來很像

我們何不把他們結合在一起，稱作 early stopping

在建樹時，就可以防止新建不必要的 attribute nodes 和分支

Broadening the applicability of decision trees

Decision tree 還有很多問題需要被解決

Missing data : 在資料缺失下，要怎麼計算 information gain ?
Multivalued attributes : 單一 attribute 有多個值時怎麼計算 information gain ?
Continuous-valued input attributes : 若 input 是 real number (e.g., height) 要怎麼分支
- 通常會定義一個中間值來進行分支
Continuous-valued output attributes : decision 是要找出 real number 要怎麼找
- 可以使用 Regression tree