Learning from example
==
###### tags: `朱威達`

- learning base agent:他有**學習能力**，會在未來的觀察中提升自己的效能，
- 透過input-output的組合，可以用function預測新的unput之output
- 為何需要learning agent?
1. 無法窮舉所有情況
2. 無法隨時隨著時間演變改變機率
3. 有時候人類也找不到解答

# Supervised learning

最基礎的learning 法，給(input, output)，希望找到function $y=f(x)$，理論上可以找到完美function，實際上不可能找到。

找到一個function(hypothesis)，用training set找到一個假設function，然後再用tesing set 去檢驗這個function的正確性

**classification** -> 也叫做Boolean/binary classification，output會是true/false

**regression** -> output會是任意數值

這邊可以看到用不同次方的多項式去fit有不一樣的多項式

上面不管哪個次方的多項式都可以完美fit，如何決定要用哪個次方的多項式呢？

**Ockham's razor** -> 傾向選擇**次方較低**的多項式，希望越簡單效率越好的，越簡單的function，選到機率越高

看上面18(c)的圖7個點沒辦法用一個linear的線去fit他，所以他用6次多項式可以完美fit，但是這不會是一個好選項。選擇一個離他們都很近的linear直線其實是比較好的。(線性代數的的least square line)

總的來說，
高次多項式會fit比較好，但是高次方容易overfitting
低次多項式可以比較好的形容function的走勢，但是他沒辦法fit很好
當然希望兩這兼具但是很難，這邊的tradeoff 要自己調配平衡。

令最好的 hypothesis是$h^*$

$h^* = argmaxP(h|data)\equiv$在這些data中會選擇用h來描述的機率，然後是最高的機率。

用貝氏：
$h^*argmaxP(data|h)P(h)\equiv$(選到這個h而他可以描述這個data的機率)*(天生選到h的機率)
$P(h)$(天生選到h的機率)在低次項被選中的機率很高，像較於高次方
$P(h)$傾向選擇簡單的hypothesis(Ockham's)
<!-- $P(data|h)$傾向選擇複雜的hypothesis(會fit 比較好) -->

**tradeoff:(描述能力)-(一般化能力)**

# Learning Decicion Tree

if else.....就是Decicion Tree
今天要決定是否要等這家餐廳？有10個要決定的東西(attributes)
可以建一個決策樹

或是換一個方法，自動產生這個tree
搜集過去12組客人的方式，學習出這個決策樹。

該怎麼learn呢？
所以希望：
1. 描述上面那個表格(越詳細)
2. tree越小越好（越簡單/越一般化）

會發現要達成上面兩項(矛盾)這是一個**intractable problem** -> problems for which there exist no efficient algorithms to solve them，找不到適合的最佳解

有一個代替的方法是用**greedy divide-n-conquer**：**永遠考慮重要屬性先**
這樣可以盡量把tree 壓得小

像是用**餐廳type**無法很快決定是否要等(模糊)，就不會是優先考慮的attribute

**裡面有沒有人**就是可以優先選的attribute

<!-- 
-->
所以尊崇用影響比較大的attribute優先，再重新畫一次決策樹
深度下降很多

## Entropy

要怎麼去量化attribute的重要性？
一個可以把data分類yes/no的就是一個好的attribute

用**entropy**量化
Entropy:用來衡量一個random variable的不確定性/資訊量

所以**我們要選的attribute是能使entropy降最多的**$\equiv$一開始資訊雜亂，在做某一個決定之後，可以降低最多資訊雜亂度的

所以可以得出
$log\frac{1}{P(v_k)}=-logP(v_k)$提出來

Entropy:$H(V) = -\sum P(v_k)logP(v_k)$

**在這邊可以換算，如果他是硬幣的話有兩種可能$\equiv2^1可能\equiv1bit$，若是4面骰$\equiv2^2可能\equiv2bits$**

就可以用上面的舉例理解：
一個公平硬幣，兩面個是0.5, 0.5，他不確定性很高
其entropy$H(Fair)$將會是1 bit

若是硬幣機率是0.99, 0.1，他不確定性很低(應該會是0.99那面)
其entropy$H(不公平)$將會是0.08 bit

**結論：**
不確定性很大 -> entropy高
不確定性很小 -> entropy低
會優先想選擇entropy高的attribute

### Boolean variable
令q為true的機率, (1-q)為fakse的機率
$B(q)=-qlogq - (1-q)log(1-q)\equiv$-(true的機率)*(true的資訊量)-(false的機率)*(false的資訊量)

## Remainder
所以繞回去，要找哪個attribute，就是要找哪個attribute使entropy越小

1. 所以今天我們有attribute A(餐廳type), 有d種(餐廳type)，然後依照他的type分成不同的$E_d$
2. $每個集合E -> p_k為true的樣本數(要等的), n_k為false樣本數(不等的)$
3. entropy = $B(p_k/(p_k+n_k))\equiv B(p_k出現的機率)$
4. 一隨機選取的sample 他是來自集合k個value的的機率是$\frac{集合 k的所有樣本數}{所有樣本數}$

整體整理：
$Remainder(A) = \sum\frac{p_k+n_k}{p+n}B(\frac{p_k}{p_k+n_k})$

可以得經過餐廳類型的判別得到下一場的資訊總和。

我自己的理解：
對每一類型餐廳，依照他的樣本多寡比例，所總和的資訊量

## Infromation gain


$Entropy的減少\equiv Gain(A)的增加\equiv attribute的重要性$

$Gain() = 原本的資訊量 - 剩下的資訊量 = Entropy的減少$

帶入就可以發現
$Gain(餐廳人數)=0.541的影響(好的參考選擇)(會被選為決策樹的root)$
$Gain(餐廳總類)=0沒有影響$

## Decision tree prunning

為了解決決策樹overfitting的問題

**把樹的leaf減少一點**

1. 找leaf的末端
2. 如果leaf的前面node判別為irrevalent
3. 因為他不重要就把該node剪掉，把兩個leaf node合併為一個代替他
4. repeat

該怎麼判斷該node為irrevalent?

所以當我在考慮一個attribute的時候，把他分成不同集合，但是他的positive跟negative跟原先差不多$\equiv$他的gain幾乎=0 -> 他是irrevlent

所以問題：Gain要多大才是有用，多大才是要split

### Significance Test

**背景值**
這邊沒有看他數學@@

令$p_k為true 的樣本數$，$n_k為false的樣本數$
背景值為$\hat{p}_k, \hat{n}_k$

所以他的偏移值(deviation)=$\Delta$

然後可以用自己的需求$\Delta$去查表，去看他有沒有顯著性

所以知道當這個**node很重要**，他的偏移量$\Delta$會很大，若是這個**nod不重要**他的偏移量$\Delta$就很小

所以透過這個$\chi^2 pruning$可以生成pruned tree，他可以濾掉很多noise，可以簡化整個tree。

## Early stopping
Information gain是用來建這個tree，選擇哪些node是重要的
$\chi^2 pruning$是這個tree建完之後，把不重要的部分合併

$\chi^2 pruning$跟information gain的概念很像，我們直接融合兩個概念變成**early stopping**，所以他只長重要node，之後就不用花力氣去融合他的leaves

if(information gain足夠大 && x2 punning足夠大){
    才會建出那個node
}

所以就不會像原本長完整棵樹，而是只長出重要的node -> early stopping

## Advanced議題
### Missing data
若是收集的資料有些dimension沒有數據，該怎麼辦？
### Multivalued
要是某attribute可能有超多分枝(餐廳有100個分支)，這樣在做information gain的時候下出線問題
### Continuous and interger-valued input attribute
某些可能是連續的值(身高、體重，是數值而不是0/1)，他就有無限多可能的value，要透過一些方法把整個連續值切斷(split)來得到最好的information gain
### Continuous-valued output attributes
如果要用decision tree 來output 一個value(decision tree只能output true/false)，這時候我們會需要regression tree

人類容易去理解決策樹，知道她過程判斷什麼。而Neural Network像是黑盒子，不知道他決策的過程，直接output答案

# Evaluating and choosing the Best Hypothesis

選一個hypothesis最可以解釋(預測)未來的資料，(未來資料不要跟過去的樣本有差)

隨便取一個random variable $E_j$
如果$E_j滿足\\
P(E_j|E_{j-1}, E_{j-2}...)=P(E_j)$不同的資料彼此沒有關係
每個資料符合$P(e_j)=P(E_{j-1})=...$模型看的參考的資料會是一樣的

則稱**independent and indentical distributed(iid)**
independent:不同data為獨立
indentical distributed：取自同一個distribution

error rate -> $h(x)\neq y$的出現比例
就算在training set 的error rate很低，也不代表他在tesing set 上error會很低

所以我們會隨機把data split開來成為training set跟testing set

## k-fold cross validation
原本只是隨機split一次，其實很吃運氣，因為不知道split出來的到底是很是壞，很看人品。
所以會有k-fold cross validation，他把資料分成k等分，這邊在李鴻毅的筆記那邊有介紹[李鴻毅筆記validation在最下面](https://hackmd.io/vjlb4Ay3S2u7WY5CO_6OVA?view)

這邊把推展到極致是**leave-one-out cross-validation(LOOCV)**
令現在100筆資料，分成100等份，我們train 99筆，test 1筆...一直下去
常用於**資料很少的時候**(醫學的圖...)

## Peeking
主要因素是"人"，因為人可以看到testing set的結果，進而修改模型的參數，來提升他的效能。
所以就算某種較差的模型，若是透過很狠的調整參數，他的結果反而回超過較好的模型。
這也代表一件事，就是透過"人"將testing set 的資料流入training set之中。

所以現在改變為
1. training set
2. validation set
3. testing set，

我們不能看tesing，只能對validation調參數

## Model selection
對於選擇多少order的多項式可以參考[李鴻毅筆記Bias與variance那邊](https://hackmd.io/vjlb4Ay3S2u7WY5CO_6OVA?view)

一般分為兩部分：
1. model selection(多少order)
2. optimization(調整參數)

一般的步驟：
從簡單的model去fit，逐漸往複雜的model去做修正

### Error Rate
一般會用loss function來判斷$L(y, \hat{y})$

又可以分為$L_1 loss, L_2 loss$

$L_1 loss為y, \hat{y}的絕對差值=|y-\hat{y}|$

$L_2 loss為y, \hat{y}的差值的平方=(y-\hat{y})^2$


希望能將loss越來越小

在**實際問題中不是每個出現機率是相等的，所以還要考慮他出現的機率**，所以還要乘上他的probability$P(x,y)$
所以最後得到的expected generalization loss會是：
$GenLoss(h) = \sum L(y, h(x))P(x,y)$

所以可以得到最好的hypothesis就會是$h^* = argminGenLoss(h)$
又$P(x,y)$常常是不知道的，比如辨識照片是一隻貓的機率是多少，但是不知道出現貓照片的機率有多高。

所以直接假設機率是$\frac{1}{N}$重新整理會得到Empirical
$EmpLOss(h) = \frac{1}{N}\sum L(y, h(x))$


### Regularation
當model很複雜的時候

## Univriate linear regression
這個過程就是求$w_0,w_1$最fit $y = w_1x+w_0$的過程

希望求出$h_w(x) = w_1x+w_0$之最佳解，稱為linear regression
$\equiv$least square solution（線代）

用有別於線性代數的推倒方法來解釋：
為了minimize loss function
可以把loss function視為一個以$w$為變數的函數
只要分別對loss function做偏微分，可得closed-form solution，可以得到唯一解。
便可以得到最好的$w_0, w_1$

loss function ($L_2$是mean square error 一定滿足)是一個convex$\equiv$他不會有local min，只會有一個最低的凹洞$\equiv$有closed-form solution

絕大多數的情況之下是**不會**有closed-form solution的。

### Gradient-decent

在這邊設定learinig rate為$\alpha$，可以設定是常數，也可以設定隨時間改變
就可以得到$w_0, w_1$的update函式

這邊可以參考[李鴻毅筆記](https://hackmd.io/vjlb4Ay3S2u7WY5CO_6OVA#Regression)有很多圖可以看

<!-- #### Batch gradient descent
有N個training sample，同時都要考慮N個sample

這個方法叫做Batch gradient descent，一次看一對data -->

#### Stochastic Gradient Descent
現在大家用這方法，每次隨機挑一些data做訓練

#### Multivariate linear Regression
高維度多項式，模型比較複雜，但是fit比較好

用多變數形成一個曲線，可以整理成
多變量的linear regression，要找出$w^*$使loss最小


如果是linear regression有**一般式**可以解，Multivariate linear Regression也可以

所以可以用**least square solution**最小平方法的方法可以解$w^*$

多變量linear regression複雜，但是training效果好

也因為他很複雜，所以會用regularization把他用smooth一點

令q=1對L做regularizationt稱為$L_1$

要用哪種regularization看自己的目的

$L_1 regularization$有個特別作用，要求模型在學習的時候，盡可能不要有weighting，最好有很多$w_i$=0(很稀疏)，稱為**sparse model**，模型比較簡單

## Classification

linear function也可以用來分類
現在目標是找到一個線，將資料分成兩個線

$input(x_1, x_2)$ -> hypothesis -> output(0,1)

這邊舉了範例，白色 -> 正常地震，黑色 -> 爆炸地震

可以看到(a)圖可以完美的用一條線分類，但是現實中不可能那麼好，要找一條線可以適應(b)的狀況最好

分兩類的linear線稱為，linear separator
如果可以用一linear function分出兩類，則稱**linear separable**。


h(x){
    threshold(w內積x)>=0    return 1
    threshold(w內積x)<0    return 0
}

現在我們可以用很多種方式求多項式的係數w，我們將求得的w, x放進threshold()之中，判斷他是0還是1

這邊整理看一下數學的意義
根據
$w_i = w_i +\alpha(y-h_w(x))*x_i$
其中注意看$y-h_w(x)$

1. y=h(x)，這是當h(x的預測值是對的時候)
2. 當y=1而h(x)預測為0的時候，我們會希望w內積x大一點讓h(x)接近y
3. 當y=0而h(x)預測為1的時候，我們會希望w內積x小一點讓h(x)接近y

可以觀察這個圖（a)），隨著訓練增加，正確率有一直上升，但是好像都還不是很穩定的感覺。
（b）在雜訊比較多的狀況下，而且learning rate 是一常數的狀況下
（c）隨著update越多的情況下，learning rate會越來越小，整個performence會穩定很多。

### 原因一

因為他的boundary是一條linear的線，都是非黑即白的狀態，在很多情況下，如果有一個比較soft的boundary會是比較好的選擇，不要這麼武斷

所以可以透過軟化threshold function，用sigmoid function
有下面特質：
1. 連續、和緩的形質
2. 保有threshold的性質

(a)threshold function
(b)logistic function

所以可以得到
$h_w(x)=Logistic(w,x)=\frac{1}{1+e^{-w\cdot x}}$

Logistic Regession需要gradient descent去解決這問題。

最後w的update式子可以化成上面的這個式子

可以看這兩個圖對同一筆data的比較：
上面是用**hard threshold**執行
下面是用**logistic regression**然後他soften boundary可以看出他效能因此提升很多。