Nonparametric model
==
###### tags: `朱威達`

parametric model:據參數性的模型，也就是用training data來預測有限的w(係數)的集合，訓練完成後我們就可以用這一組w去描述這個模型。

nonparametric model:假設我們不能用一組有限的w集合去描述此分佈，我們用目前training data來預測接下來進來的data

所以需要保留多少訓練資料？不知道，要用多少參數描述model？不知道
這稱為instance based learning, memory based learning

# 查表
最簡單的方式是查表，將所有的樣本放進table中，我們要求h(x)時我們再去table中看x對應的y。
這方法很不一般化，若是x不在table之中就不知道答案

# Nearst neighbor model

給一組資料$x$，在他周圍找最近的k個樣本，稱為k-nearst neighbors，我們用$NN(k, x)$來到表這些鄰居

classification問題：看看$NN(k,x)$這些鄰居是哪個類別多(因為要投票，所以一般會選擇基數個鄰居)

regression問題：我們取$NN(k,x)$對應的output的平均，或是中位數作為output

這邊舉個例子：
(a)只考慮一個鄰居，會容易overfitting像是紅色圈圈那邊
(b)考慮5個鄰居，解決overfitting的問題(有一點點underfitting)

Nearst neighbor model依舊還是會有overfitting, underfitting的問題

要幾個鄰居**沒有一個標準答案**，可以做cross-validation試試看最適合的鄰居k

## 定義最近鄰居
不同計算距離的方式會得出不一樣的鄰居

### Minkowski distance
p是一個參數，p=1時，是Manhattan Distance。p=2時，是Euclidean Distance。

Manhattan Distance：
為水平距離加垂直距離。
$d(x,y)=|x_1-x_2|+|y_1-y_2|$

Euclidean Distance：

### Hamming distance
對boolean的attributes
兩個長度相等的字串，將其中一個變換成另外一個字串所需要替換的字元個數。
例如字串"1111"與"1000"之間的Hamming Distance為3

## 正規化(Normalization)
橘子蘋果不能加在一起。
有好幾種loss func 不能隨便加再一起，要注意數量(單位)。若loss1(0~1000), loss2(0~1)現在兩個相加，loss2就沒用了。（可以乘上weight解決）

所以**正規化**很重要

有很多種不一樣的正規化方法。
最普通是是$\frac{x-平均}{標準差}$

## curse of dimentionality
(這邊老師寫板書忘了補...)
在低維度之下，nearest neighbor他運作的不錯，但是高維度就不太行。

令$l$為鄰居邊長的平均，所以包含k個鄰居的體積會是$l^n$然後整樣本的總體積是$1$，得到$l^n=k/n$，化簡得$l=(k/n)^{1/n}$

隨著輸入的維度上升，input space的大小也隨之指數成長，那麼我們的訓練資料集佔整個數據空間的比例就會變得很小
**維度很高，越不可信**
所以
1. 降低維度很重要
2. 用locality降低為度

## k-d tree
今天若是採用今天進入幾個點，全部scan過一遍再找最近的鄰居，會爆。
所以會用k-d tree，用tree來代表資料的親疏遠近。

用來找最近k個鄰居
適用在很多examples時
是一個balanced tree，來建構樣本的遠近

1. 一開始所有樣本都在root
2. 挑一個數i(所有dim的中位數)
3. 若dim<=i，去左子樹，若dim>i去右子樹
4. 一直建下去

這樣就可以很簡單的找到k個鄰居

適用於樣本數>dim數
令維度為n，最好是$2^n個example$
所以若維度=10，則最好有1024個以上examples

若是資料不夠多，成本太高還不如用linear scan暴力scan過

## Locality-sensitive hashing
用hash table可以更快的找到鄰居。
目標不是放在100%正確的鄰居，而是專注在速度（近似解）

- 所以透過projection，有很大的機率相近的example會落到相同的bin，但是這不是絕對的，小機率下很遠的example也會到同一個bin
所以有一hash function g(x)給任何$x_j, x_j'$如過他們距離超過cr，他們在同一個bin的機率會很小。如果距離小於r，他們在同一個機率很高。c,r要自己調。

- LSH 會創多個random projection，再合併他們。
我們選$l$個random projection再創$l$個hash table

有有這些random projection, $x_q$進來，分別丟給這$l$個function，得到$l$個結果。
$x_q丟進g_1(x)，取g_1(x)的鄰居$
$x_q丟進g_2(x)，取g_2(x)的鄰居$
$x_q丟進g_3(x)，取g_3(x)的鄰居$
...
對這些些所有的鄰居取$\cup$（所有可能是x鄰居的人），存在$C$之中

再來再從$C$之中取最近的k個鄰居，有很高機率可以全找到
證明略...

**速度提升很多！速度提升很多！速度提升很多！速度提升很多！速度提升很多！**

## Nonparametric Regression


### （a）連連看
是最簡單的Nonparametric Regression
當雜訊小時，效果還不錯
當雜訊大的時候，很容易爆掉

### （b）k-nearest-neighbors regression

sliding window 的感覺，這邊取k個鄰居，然後取他的平均值就是他hypothesis的預測
(這邊圖上用3)

### （c）k-nearest-neighbors linear regression

這邊取k個鄰居，每次找一條最好的線通過他，不斷重複，這個結果依然不是連續的，如圖上所示
(這邊取三個)

### （d）Locally weighted regression

用sliding window的想法
希望要**有continuous**
所以取一點$x_q$，很近的neighbor weight比較重，比較遠的neighbor weight 較輕(或是趨近於零)

他概念像是這樣：
取10個鄰居，他的weight就用$k(d)$那個function來算出來

**他就會取10個鄰居，取中間的點帶quadratic kernel可以得到權重後的結果，每次sliding window看一格，然後預測出很多條線，最後在取這些線的平均。**

用gradient descent更新w，然後完成這個regression

# Support Vector Machine(SVM)

2000-2010很強的時光

不需要很多先備知識就可以直接尻svm，效果都還不錯

現在要區分黑白兩色的線有無限多條，哪一個是最好的呢？

對svm來說最好的線是margin area的平均（margin area是虛線，由support vectors 決定）

supprot vector -> 就是boundary的衛兵

有些example的重要性比較大(像是Locally weighted regression)，很遠的樣本沒什麼影響力。

SVM 目標不是為了降低empirical loss，而是generalization loss
要怎麼達到？**用maximum margin seperator（margin area 越大越好）**

要怎麼找到seperator(w,b)呢？
省略數學的部分....

**seperator定義為${w\cdot x +b=0}$**
所以概念上我們可以用gradient descent來求得w,b，此w,b會使他的margin是最大的。
但是我們可以改寫為另外一個問題(dual problem)，可以順便解出w,b
$x_j, x_k$為訓練資料
這邊也沒有要推＠＠

我們要先找到$\alpha$就可以推出w，$w = \sum\alpha_jx_j$

他有三個重要性質：
1. 他是convex$\equiv$他可以找到global最佳解
2. input的點運算只需要跟少量support vector內積、加法、乘法，就可以判斷是哪類，大於0還是小於0呢？
3. 只有**support vectors**的$\alpha_j\neq0$其他點的$\alpha=0$(support vector看很重，其他都不看的意思)


可以用$h(x)=sign(\sum\alpha_jy_j(x\cdot x_j)-b)$判斷是黑是白，因為不是support vector的樣本之$\alpha=0$所以很快就可以判別。

SVM是非參數模型，但是有support vector，可以之參考幾個參考他們幾個，便偷偷取得參數模型的優點。

**可以被線性區分 -> linearly seperatable -> SVM**

## 用多維SVM

常常資料不是容易線性區分的
如果像是上面左圖，不能用linear 區分，可以把他圖map到高維度的空間，這樣就可以用線性分類(上右圖)

因為老是好像寫黑板，所以我的理解是

$F(\begin{bmatrix} x_1 \\ x_2 \end{bmatrix})=\begin{bmatrix}f_1 \\ f_2 \\ f_3\end{bmatrix}=\begin{bmatrix} x_1^2 \\ x_2^2 \\ \sqrt{2}x_1x_2 \end{bmatrix}$

理論上是一定可以被線性區分的，可以**一直往更高維度mapping**一直試。

所以理論上我們要計算mapping到高維度的$x_j\cdot x_k$就可以用$F(x_j)\cdot F(x_k)$
之後再可以得到，$F(x_j)\cdot F(x_k)=(x_j\cdot x_k)^2$

**Kernel trick**
大概的總結是：要計算高緯度的內積，並不需要把它轉換成高緯度再計算，可以在低維度直接求出來高維度的內積結果 -> 運算有效率

## kernel function

要計算高緯度的內積，並不需要把它轉換成高緯度再計算，可以在低維度直接求出來高維度的內積結果 -> 運算有效率

kernel function = $(x_j\cdot x_k)^2$

有很**多種不同**的設計

1. 讓你不真的mapping到高維度，但是可以得到高維度function內積的結果。
2. 因為這低緯度function更高維度的操作，使svm 不會限制在線性的分類，使他超強。

## Soft margin classifier

在實際狀況也沒有一定要堅持100%分類（還可能overfitting），所以可能分辨到
一定程度錯了也沒有關係。
寧可有一些是錯的，這樣他的一般化會比較好

# Ensemble Learning

選定一集合、一堆hypothesis，然後結合他們的預測
生成多個決策樹，然後最後在投票看看哪一個是最好的

三個臭皮匠，勝過諸葛亮的概念，一個樹爛掉的機率，一定比三棵樹爛掉的機率高
另一個裡解是，看一下這個圖，如果是單一條分類的話+,- 分為兩邊會有很多錯誤，但若是三條邊一起結合起來，就可以很清楚圍出一個boundary出來。

## Bagging

有一大資料庫，隨機取一些出來當training set ，重複做k次，可以得到k個個training set，就可以做出k個不同的hypothesis。

最後平均他們的output（看分類哪個比較多）:$h(x)=\frac{1}{K}\sum h_i(x)$

classification, regression都是可以用的

可以壓低他的variance，減緩某些(over/underfitting)，在**訓練資料很少的時候**很有用。

在實際的作法上很強

## Random forest

一堆k個決策樹，然後做bagging
重要的是要**隨機選attribute**，而不是像以前只選擇Gain()最強的attribute。
也就是隨機選一個attribute然後再找他資訊量高低作為split point（多了隨機性）

再來推廣，原本用的資訊量高低分，現在用隨機的split point來分左右子樹
稱為extremely randomized tree(Extratree)

用cross-validation可以找出：
1. K個樹
2. 每個數N個example
3. split point的attribute數
4. 用random split的數目

Random forest 比較不會overfitting

隨著數越多，他會越收斂

## Stacking

同樣training set 用3種model, SVM, logistic regression, decision tree.

input(10維)，output(13維)
可以看到他在最後會append粗體字分別是，SVM, logistic regression, decision tree的預測。像是結合不同model的意見。
圖上面結合yes, no, no 會output=no

也可以設定每一個model 的權重

項是在基礎模型之上再搭一個模型的感覺

stacking比單一模型降低bias，效能也比單一模型好

## Boosting

最常見的一種
最重要的想法是weighted training set，某樣本的weight越大，他對hypothesis的重要性也越大。

最一開始大家的$w_j$都=1，生成第一個hypothesis $h_1$（這$h_1$有對有錯），希望可以**針對分類錯誤地改進**，分類錯的loss比較高，所以就是提高分類錯誤的weight，降低分類正確的weight。
我們會不斷更新$h_n$，做個k次，集合他們的結果。

方塊的大小代表在權重，所以錯誤的權重一直增加，正確的權重減少。
然後最後再總和大家的答案(根據圖，按照大家的決策數大小，越大權重越高)

### adaboost

ada=動態
動態調整boosting

意思是，集結很多L - weak learning algo（就是比亂猜好一點點），只要集結夠多L就可以得到正確率高的hypothesis

回到boosting
可以看圖說，boosting的效能真的提升
根據圖也可以看出他的K數量數量選擇上有上限，因為選一定的K時，他的error就變得很低很低，就沒有再增加K的意義了。

## Online learninig

目前為止我們都**假設**資料是i.i.d(independent and identically distributed)，因為數學比較好推導，但是過去對未來的資料說independent，我們怎麼預測未來？又怎麼說我們為來對過去independent？狀態隨時在改變

所以不是i.i.d怎麼辦？我們會考慮online learninig

onlinelearninig(){
    if(新的資料模型判斷錯){
        修正舊的模型
    }
}

### Randomized weighted majority algo

就是來聽聽大家(punkits)的判斷，他對多相信一點，他錯少相信一點。
長久下去，說得很準的punkits權重越來越高（越相信他）
M的數學也沒有推導...

如果$\beta$接近1 -> 降低weight的速度慢
要容忍錯誤很久
如果$\beta$接近0 -> 降低weight的速度快
錯誤容忍率低
各有好壞

一般的model目標降低loss，這裡目標降低regret

**資料隨時間變動**，或是**不斷要考慮新資料**的會需要online learning
ex:google search關鍵字

# Summary
需要定義一個loss function，針對你想要的預測

當你幫問題拆成很多小條件，有些物件可以直接拆成許多小物件，不一定每一個都需要機器學習

要開發時要知道自己的目標、資料來說要用監督式、非監督是、還是強化學習。

有沒有資料？
資料哪來？正確性？

1. preprocess
2. normalization(單位)

沒有說哪個模型是最好的，只有比較適合的場合
Randomforest -> 很多種feature，但是有許多不相關
Nonparameteric -> 有很多資料且你沒有先備知識
Logistic regression -> 適合線性分類
SVM -> 適合資料不多的時候
deep neural network -> a data analysis method that uses machine learning algorithms to automatically recognize patterns and regularities in data

經驗～～

- 不要全然相信你的model
- Interpretability:你可以知道為什麼他會吐出這個output（近年的不知道為什麼）
- Explainability:知道他怎麼吐出這個output