# 機器學習技法

## L1 Linear SVM
- 目標：給定空間中N個點及其對應的值($x_1$, O),..., ($x_N$, X)，找出一個超平面W，把O及X分開。
- h($x$) = sign($w^Tx$) $\in$ {1, -1}

- 1.   $\max\limits_{w} ~:~margin(w)~=~\min \limits_{n=1,...,N}distance(x_n,w)$
**subject to：** $every~y_nw^Tx_n>0$
- 2.   $\max\limits_{b,w} ~:~margin(b,w)~=~\min \limits_{n=1,...,N}\frac{1}{||w||}y_n(w^Tx_n+b)$
**subject to：** $every~y_n(w^Tx_n+b)>0$
- 3.   $\max\limits_{b,w} ~:~\frac{1}{||w||}$
**subject to：** $\min \limits_{n=1,...,N}y_n(w^Tx_n+b)~=~1$
---
- 4.   $\min\limits_{b,w} ~:~\frac{1}{2}w^Tw$
**subject to：** $y_n(w^Tx_n+b)~\geq~1~for~all~n$

- 滿足$y_n(w^Tx_n+b)=1$的點，就會在邊界上
- **Hard-Margin Linear SVM 演算法** ( d+1維 )
- 1.$Q=\begin{bmatrix}0&0^T_d\\0_d&I_d\end{bmatrix}$ ; $p=0_{d+1}$ ; $a^T_n=y_n[1~~x_n^T]$ ; $c_n=1$ ;
- 2.$u=\begin{bmatrix}b\\w\end{bmatrix}\leftarrow QP(Q,p,A,c)$;
- 3.$g_{SVM}(x)=sign(w^Tx+b)$
- 其他理論保證
- SVM 和 Regulization 很類似
- minimize：$w^Tw$
- constraint：$E_{in}=0~~~(y_n(w^Tx_n+b)\geq 1)$
- 特別的演算法$A_\rho$
- $d_{vc}(A_\rho)\leq\min(\frac{R^2}{\rho^2},d)+1\leq d+1$
- Better Generalization
- 所以我們可以考慮：**large margin + feature tranform**
---
> Quadratic programming：$u\leftarrow QP(Q,p,A,c)$
>
>   $\min\limits_{u} ~:~\frac{1}{2}u^TQu+p^Tu$
> subject to： $a^T_mu\geq c_m$ for all m
## L2 Dual SVM
- **Nonlinear transform**
- $\phi(\underset{d~維}{x_n})=\underset{\widetilde{d}維}{z_n}$，共有 N 個點。
- **Dual SVM by Lagrange Multiplier**
- 1.     $\min\limits_{b,w} ~:~\frac{1}{2}w^Tw$
   **subject to：** $y_n(w^Tz_n+b)~\geq~1~for~all~n$

- 2.  $\max\limits_{\alpha_n\geq 0} \min\limits_{b,w}~:~\frac{1}{2}w^Tw+\sum\limits_{n=1}^N\alpha_n(1-y_n(w^Tz_n+b))$
- 條件一：$0=\sum\limits_{n=1}^N\alpha_ny_n$
- 條件二：$w=\sum\limits_{n=1}^N\alpha_ny_nz_n$
- 3.  $\min\limits_{\alpha} ~:~\frac{1}{2}\sum\limits_{n=1}^N\sum\limits_{m=1}^N\alpha_n\alpha_my_ny_mz_nz_m-\sum\limits_{n=1}^N\alpha_n$
**subject to：** $\sum\limits_{n=1}^N\alpha_n~y_n=0,~\alpha_n\geq 0~for~all~n$
- **Karush-Kuhn-Tucker (KKT) conditions (充要)**
- **primal feasible : $y_n(w^Tz_n+b)≥1$**
- **dual feasible : $α_n≥0$**
- **dual-inner optimal : $\sum y_nα_n=0,~w= \sum α_ny_nz_n$**
- **primal-inner optimal : $α_n(1−y_n(w^Tz_n+b))=0$**
- **Dual SVM 演算法** ( N維 )
- 1.帶入係數
- $Q_D=\begin{bmatrix}q_{n,m}=y_ny_mz_n^Tz_m\end{bmatrix}$ ; $p=-1_{N}$
- $a^T_n=$ n-th unit direction ; $c_n=0$
- $a_\geq=y$ ; $c_\geq=0$
- $a_\leq=-y$ ; $c_\leq=0$
- 2.QP回傳一個$\alpha$後
- $\alpha\leftarrow QP(Q_D,p,A,c)$
- $w=\sum\limits_{n=1}^N\alpha_ny_nz_n$
- $b=y_n-w^Tz_n$, for some $\alpha_n>0$
- 3.$g_{SVM}(x)=sign(w^Tx+b)$

- Dual-SVM好性質
- **如果某個$\alpha_n>0$**
- 1.該點滿足 $y_n(w^Tx_n+b)=1$
- 2.該點在邊界上
- 3.該點稱為 **support vector**
- 4.$SV\subset SV_{candidate}$ (因為邊界上可能有其他點)
- 5.$w$ 和 $b$ 都可只靠 support vector 算出來
- $w=\sum\limits_{n=1}^N\alpha_n(y_nz_n)$，$w$ 是 support vector 的線性組合

## L3 Kernel SVM
> Quadratic programming：$u\leftarrow QP(Q,p,A,c)$
>
>   $\min\limits_{u} ~:~\frac{1}{2}u^TQu+p^Tu$
> subject to： $a^T_mu\geq c_m$ for all m
- Based on **Dual SVM**：
- $\Phi(x_1)\Phi(x_2)=K(x_1,x_2)$
- 先做轉換再做內積，$\tilde{d}+1$ $~~\rightarrow~~$ 先做內積，$O(d)$ 運算
- 將$z_n^Tz_m$運算，偷吃步算出
- 算$q_{n,m}=y_ny_mz_n^Tz_m$會用到
- 算$b=y_s−w^Tz_s$會用到
- 算$g_{SVM}(x)=sign(w^T\cdot\Phi(x)+b)$會用到
- **Kernel SVM演算法**
- 1.帶入QP
- $Q_D=\begin{bmatrix}q_{n,m}=y_ny_mK(x_n,x_m)\end{bmatrix}$ ; $p=-1_{N}$
- $(A,c) 滿足等式、下界條件$
- 2.$\alpha\leftarrow QP(Q_D,p,A,c)$
- 3.$b\leftarrow y_s-\sum\limits_{SV}\alpha_ny_nK(x_n,x_s),~~~~(x_s,y_s)是SV$
- 4.$g_{SVM}(x)=sign(\sum\limits_{SV}\alpha_ny_nK(x_n,x)+b)$
- **Kernel = Transform + Inner Product**
- Linear Kernel：$K(x,x')=x^Tx$
- linear first
- 可用special QP solver加速
- w和SV有直觀幾何意義
- 但不行處理非線性邊界
- Polynomial Kernel：$K_Q(x,x')=(\zeta+\gamma ~x^Tx')^Q$
- 不同參數代表不同內積定義，不同距離定義
- Q太大會有numerical difficulty，造成QPsolver不準
- 三個參數不容易選擇
- Exponential Kernel：$K(x,x')=e^{(-\gamma||x-x'||^2)}$
- $g_{SVM}(x)=sign(\sum\limits_{SV}\alpha_ny_ne^{(-\gamma||x-x_n||^2)}+b)$
- Gaussian 在 SV 的線性組合
- 又稱為：Radial Basis Function (RBF)
- $\gamma越大，越容易overfitting$
- 1.sharp gaussion
- 2.對應到衰退比較慢的無限多維transform
- 容易因太強大而overfitting
- 非常神秘
- 計算速度會比較慢
- **Valid Kernel**
- $K(x,x')=\phi(x)^T\phi(x')$，表示z空間兩向量的相似性
- **Mercer's condition**
- 1.要滿足對稱性
- 2.K 要是半正定的
- **Possible but Hard，建議用linear或是Gaussian就足夠**
## L4 Soft-Margin SVM
- **堅持一定要完美分開，容易造成overfitting**
-   $\min\limits_{b,w,\xi} ~:~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}\xi_n$
**subject to：** $y_n(w^Tx_n+b)~\geq~1-\xi_n~~and~~\xi_n\ge 0~for~all~n$

- 可用QP解，$\tilde{d}+N+1$變數，$2N$限制條件
- **Soft-Margin Dual SVM by Lagrange Multiplier**
- 1.  $\min\limits_{b,w,\xi} ~:~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}\xi_n$
**subject to：** $y_n(w^Tx_n+b)~\geq~1-\xi_n~~and~~\xi_n\ge 0~for~all~n$

- 2.  $\max\limits_{\alpha_n\geq 0,\beta_n\geq 0} \min\limits_{b,w,\xi}~:~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^N\xi_n$
          $+\sum\limits_{n=1}^N\alpha_n(1-\xi_n-y_n(w^Tz_n+b))+\sum\limits_{n=1}^{N}\beta_n(-\xi_n)$
- 條件一：$0 = C−α_n−β_n$
- 條件二：$0=\sum\limits_{n=1}^N\alpha_ny_n$
- 條件三：$w=\sum\limits_{n=1}^N\alpha_ny_nz_n$
- 3.  $\min\limits_{\alpha} ~:~\frac{1}{2}\sum\limits_{n=1}^N\sum\limits_{m=1}^N\alpha_n\alpha_my_ny_mz_nz_m-\sum\limits_{n=1}^N\alpha_n$
**subject to：** $\sum\limits_{n=1}^N\alpha_n~y_n=0,~and~~~0\le\alpha_n\le C~for~all~n$
- **Kernel Soft-Margin SVM演算法**
- 1.帶入QP ( N變數，2N+1條件)
- $Q_D=\begin{bmatrix}q_{n,m}=y_ny_mK(x_n,x_m)\end{bmatrix}$ ; $p=-1_{N}$
- $(A,c)$ 滿足等式、下界、**上界條件**
- 2.$\alpha\leftarrow QP(Q_D,p,A,c)$
- 3.$b\leftarrow y_s-\sum\limits_{SV}\alpha_ny_nK(x_n,x_s)~~~~(x_s,y_s)是~free~SV$
- 4.$g_{SVM}(x)=sign(\sum\limits_{SV}\alpha_ny_nK(x_n,x)+b)$
- **Physical Meaning of $α_n$**
- 要滿足的條件 complementary slackness：
- $α_n(1−y_n(w^Tz_n+b))=0$
- $(C-\alpha_n)~\xi_n=0$
- 種類
- Non SV ： $0=\alpha_n~~~~~~~~~~~~~\xi_n=0$
- 一般被正常分類，離邊界很遠的點 (極少數會邊界上)
- Free SV ： $0\le\alpha_n\le C~~~~~\xi_n=0$
- 在邊界上，標出b值的SV
- Bounded SV ： $\alpha_n=C~~~~\xi_n=violation$
- 在邊界中，犯錯誤的SV (分類不一定錯誤) (極少數會邊界上)
- **Gaussian soft-margin SVM 的實務選擇，$(C,\gamma)$為參數**
- Selection by Cross Validation
- 嘗試代入不同的$(C,\gamma)$參數，無法直接optimize
- $E_{cv}$蠻有代表性，但算一組要花很多時間，
- Selection by # SV
- **Leave-One-Out CV Error for SVM**： $E_{loocv} ≤ \frac{\#SV}{N}$
- $e_{non-SV}=0$
- $e_{SV}\le1$
- 只是upper bound而已，用來刪除一些可能性，而不代表該參數很好
## L5 Kernel Logistic Regression
- **把SVM視為Reguliazed Model**
- Soft-Margin-SVM可以看成是一種regulization
- $\min\limits_{b,w} ~:~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}max(1-y_n(w^Tz_n+b),0)$
- 不能用QP(kernel trick)解
- 不一定可以微分
- 
- **SVM和Logistic Regression的關係**
- **Soft-Margin-SVM**
- $\min\limits_{b,w} ~:~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}max(1-y_n(w^Tz_n+b),0)$
- **Logistic Regression**
- $\min\limits_w ~:~\frac{\lambda}{N}w^tw+\frac{1}{N}\sum\limits_{n=1}^{N}log(1+exp(-y_nw^tz_n))$
- $s=W^Tz_n+b$
- $err_{0/1}(s,y)=[[ys\le0]]$
- $err_{SVM}(s,y)=max(1-ys,0)$
- $err_{SCE}(s,y)=log_2(1+exp(−ys))$
- 觀察結果
- $err_{0/1}\le err_{SVM}$
- $err_{SCE}\approx err_{SVM}\rightarrow SVM~很像~log~reg$
- **Probabilistic SVM：用SVM來做二元分類問題**
- 1.run $SVM$ and get $(b_{SVM}, w_{SVM})$
- 2.$\min\limits_{A,B}\frac{1}{N}\sum\limits_{n=1}^Nlog(1+exp(-y_n~(A(w^T_{SVM}x + b_{SVM})+B)~)~)$
$=\min\limits_{A,B}\frac{1}{N}\sum\limits_{n=1}^Nlog(1+exp(-y_n~(A\phi(x)+B)~)~)$
- 避免在Z空間做logistic regression，而是先再X空間做SVM，再做雙變數logistic regression，而達到一樣效果。
- **Representer Theorem**：最佳 $w$ 可以表示成 $z$ 的線性組合
- 對任意L2-regularized linear model：$\min\limits_w\frac{\lambda}{N}w^tw+\frac{1}{N}\sum\limits_{n=1}^{N}err(y_n,w^Tz_n)$，其解可寫成$w_*=\sum\beta_nz_n$
- $w_*=w_{||}+w_\perp$
- $w_\perp$比$w_*$更好
- 相同的error
- 更小的$w^Tw$
- **Kernel Logistic Regression(KLR)：用representer theorem帶入Logistic Regression**
- $\min\limits_w\frac{\lambda}{N}w^tw+\frac{1}{N}\sum\limits_{n=1}^{N}log(1+exp(-y_nw^tz_n))$ with $w_*=\sum\beta_nz_n$
- $$\min\limits_\beta\frac{\lambda}{N}\sum\limits_{n=1}^{N}\sum\limits_{m=1}^{N}\beta_n\beta_mK(x_n,x_m)+\frac{1}{N}\sum\limits_{n=1}^{N}log(1+exp(-y_n\sum\limits_{m=1}^{N}\beta_mK(x_m,x_n)))$$
- 大部分的$\beta_n$項都非零
## L6 Support Vector Regression
- **Kernel Ridge Regression：用representer theorem帶入Ridge Regression**
- $\min\limits_{w}~\frac{\lambda}{N}w^Tw+\frac{1}{N}\sum\limits_{n=1}^{N}(w^Tz_n-y_n)^2~~~with~~~w^*=\sum\limits_{n=1}^N\beta_nz_n$
- 最佳解：$\beta=(\lambda I+K)^{-1}y$
- $\lambda>0~\rightarrow~K$ positive semi-definite $\rightarrow~\beta~exists$
- $O(N^3)$ time and **dense matrix**
- **SVR：誤差有一容忍範圍的一種長度一次方 regression**
- **Tube Regression = Standard SVR**
- $\min\limits_{b,w}~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}\max(0,|w^Tz_n+b-y_n|-\epsilon)~~~$
- **Support Vector Regression Primal and Dual**
- 1. $\min\limits_{b,w}~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}\max(0,|w^Tz_n+b-y_n|-\epsilon)~~~$
- 2. $\min\limits_{b,w}~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}(\xi_n^\land+\xi_n^\lor)~~~$
$subject~~to~~~~~(y_n-w^Tz_n-b)\le\epsilon+\xi_n^\land$
$~~~~~~~~~~~~~~~~~~~~~~~(w^Tz_n+b-y_n)\le\epsilon+\xi_n^\lor$
$~~~~~~~~~~~~~~~~~~~~~~~\xi_n^\land\ge0,~~~\xi_n^\lor\ge0$
- 條件一：$0=\sum\limits_{n=1}^N(\alpha_n^\land-\alpha_n^\lor)$
- 條件二：$w=\sum\limits_{n=1}^N(\alpha_n^\land-\alpha_n^\lor)z_n=\sum\limits_{n=1}^N\beta_nz_n$
- 3. $\min\limits_{b,w}~\frac{1}{2}\sum\limits_{n=1}^N\sum\limits_{m=1}^N(\alpha_n^\land-\alpha_n^\lor)(\alpha_m^\land-\alpha_m^\lor)K_{n,m}+\sum\limits_{n=1}^N((\epsilon-y_n)\alpha_n^\land+(\epsilon+y_n)\alpha_n^\lor)~~~$
$subject~~to~~~~~\sum\limits_{n=1}^N(\alpha_n^\land-\alpha_n^\lor)=0$
$~~~~~~~~~~~~~~~~~~~~~~~0\le\alpha_n^\land\le C,~~0\le\alpha_n^\lor\le C$
- Sparsity of SVR
- $\alpha_n^\land(\epsilon+\xi_n^\land-y_n+w^Tz_n+b)=0$
- $\alpha_n^\lor(\epsilon+\xi_n^\lor-y_n+w^Tz_n+b)=0$
- 在tube中$\rightarrow~\xi=0~\rightarrow~\alpha=0~\rightarrow~\beta=0$
- 各種模型
- **Soft-Margin-SVM**
- $\min\limits_{b,w} ~:~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}max(1-y_n(w^Tz_n+b),0)$
- **Tube Regression = Standard SVR**
- $\min\limits_{b,w}~\frac{1}{2}w^Tw+C\sum\limits_{n=1}^{N}\max(0,|w^Tz_n+b-y_n|-\epsilon)~~~$
---
- **Logistic Regression**
- $\min\limits_w ~:~\frac{\lambda}{N}w^tw+\frac{1}{N}\sum\limits_{n=1}^{N}log(1+exp(-y_nw^tz_n))$
- **Kernel Logistic Regression**
- $\min\limits_w ~:~\frac{\lambda}{N}w^tw+\frac{1}{N}\sum\limits_{n=1}^{N}log(1+exp(-y_nw^tz_n))$ with $w_*=\sum\beta_nz_n$
- $$\min\limits_\beta ~:~\frac{\lambda}{N}\sum\limits_{n=1}^{N}\sum\limits_{m=1}^{N}\beta_n\beta_mK(x_n,x_m)+\frac{1}{N}\sum\limits_{n=1}^{N}log(1+exp(-y_n\sum\limits_{m=1}^{N}\beta_mK(x_m,x_n)))$$
- **Ridge Regression**
- $\min\limits_{w} ~:~\frac{\lambda}{N}w^Tw+\frac{1}{N}\sum\limits_{n=1}^{N}(w^Tz_n-y_n)^2~~~$
- 最佳解：$w=(\lambda I+Z^TZ)^{-1}Z^Ty$
- **Kernel Ridge Regression (又稱為LSSVM)**
- $\min\limits_{w} ~:~\frac{\lambda}{N}w^Tw+\frac{1}{N}\sum\limits_{n=1}^{N}(w^Tz_n-y_n)^2~~~with~~~w^*=\sum\limits_{n=1}^N\beta_nz_n$
- 最佳解：$\beta=(\lambda I+K)^{-1}y$
- 
- 分類：
- **SVM $\rightarrow$ dual SVM**
- **SVR $\rightarrow$ dual SVR**
- **ridge regression $\rightarrow$ kernel ridge regression**
- **logistic regression $\rightarrow$ kernel logistic regression**
## L7 Blending and Bagging
- **Aggregation**：把不同的 Hypothesis $g_i$，Mix and Combine成最後的$G(x)$
- 好處
• Aggregation ⇒ Feature Transform
• Aggregation ⇒ Regularization
- 種類
- Select：Validation
- $G(x)=g^*(x)，g^*(x)使E_{val}(g_i^-)最小$
- Uniformly：Vote
- $G(x)=sign(\sum\limits_{t=1}^Tg_t(x))$
- Non-uniformly：
- $G(x)=sign(\sum\limits_{t=1}^T\alpha_tg_t(x))$
- Conditionally：
- $G(x)=sign(\sum\limits_{t=1}^Tq_t(x)g_t(x))$
- **Uniform Blending**
- Classification：$~G(x)=sign(\sum\limits_{t=1}^Tg_t(x))$
- Multiclass：$~~~~~~G(x)=argmax\sum[[g_t(x)=k]]$
- Regression：$~~~~G(x)=\frac{1}{T}\sum\limits_{t=1}^Tg_t(x)$
- $avg(g_t-f)^2=avg(g_t-G)^2+(G-f)^2$
- Performance = Deviation(Variance) + Consensus(Bias)
- $avg(E_{out}(g_t))~\ge~E_{out}(G)$
- Uniform Blending reduce variance
- **Linear Blending**
- Two-Level Learning： $G(x)=sign(\sum\limits_{t=1}^T\alpha_tg_t(x))$
- 1.先得到各個$g_t(x)$
- 2.再得到$\alpha$，藉由 $~min\frac{1}{N}\sum\limits_{n=1}^N(y_n-\sum\limits_{t=1}^T\alpha_tg_t(x_n))^2$
- Blending演算法：
- 1.$從~D_{train}~算出~g_1^-,...,g_T^-，以及從~D~算出~g_1,...,g_T$
- 2.$把~D_{val}~的資料~(x_n,y_n)~轉換到~((g_1^-(x_n),...,g_T^-(x_n)),y_n)$
- 3.$用~((g_1^-(x_n),...,g_T^-(x_n)),y_n)~計算出~\alpha$
- 若由linear regression解出，則為linear blending
- 若由其他model解出，則稱為stacking
- 4.$回傳~G_{LB}(x)=\alpha~\cdot~(g_1(x_n),...,g_T(x_n))$
- 得到 $\alpha$ 來組合 $g_t$ 的方式是透過 $g^-$，避免複雜度太高。
- **Bagging(Bootstrap Aggregation)**
- Blending = 拿到 $g_t$ 後才做 aggregation
- Learning = 邊做 aggregation 邊得到 $g_t$
- Bootstrapping ： 一種統計的工具，重複的從 $D$ 抽樣，來模擬 iid 的抽樣
- **取後放回**，sample size可以是任意大小$N'$
- 理想上的 Aggregation
- $for~t=1,...,T$
- $每次~iid~從~P^N~抽樣出~size-N的~D_t$
- $g_t=A(D_t)$
- $G=Uniform(g_t)$
- Bootstrap Aggregation
- $for~t=1,...,T$
- $Bootstrapping：從D抽樣出~size-N'的\tilde{D_t}$
- $g_t=A(\tilde{D_t})$
- $G=Uniform(g_t)$
## L8 Adaptive and Boosting
- 我們可以將 Bootstrapping 視為 Reweighting
- $D={(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)}$
- $\tilde{D_t}={(x_1,y_1),(x_1,y_1),(x_2,y_2),(x_4,y_4)}$
- $E_{in}(h)=\frac{1}{4}(2[[y_1\ne h(x_1)]]+1[[y_2\ne h(x_2)]]+0[[y_3\ne h(x_3)]]+1[[y_4\ne h(x_4)]])$
- 透過 Weighting ，來產生更 Diverse 的 Hypothesis
- 
- 希望構造$u_n^{t+1}$，讓上一輪得到的$g_t$看起來像用猜的一樣
- $\frac{錯誤的u_n}{正確的u_n~~+~~錯誤的u_n}~=~\frac{1}{2}$
- 方法一：
- 透過已知的$g_t$，看正確的點有a個，錯誤的點有b個(a+b=const)
- 正確的點$u_n$設為b，錯誤的點$u_n$設為a
- 方法二：
- 透過已知的$g_t$，看正確的$u_n$為a，錯誤的$u_n$為b
- $正確的點u_n乘以\frac{b}{a+b}，錯誤的點u_n乘以\frac{a}{a+b}$
- $\epsilon_t=\frac{b}{a+b}=加權錯誤率$
- 正確點乘以 $\epsilon_t$，錯誤點乘以 $1-\epsilon_t$
- $\blacklozenge_t=\sqrt\frac{1-\epsilon_t}{\epsilon_t}=scaling~factor$
- 正確點除以 $\blacklozenge_t$，錯誤點乘以 $\blacklozenge_t$
- $\alpha_t=ln(\blacklozenge_t)$
- **問題：如果有一個$g_t$的$\epsilon_t=0$，則他會得無限多票**
- **Adaboost演算法**
- $u^{(1)}=[\frac{1}{N},...,\frac{1}{N}]$
- $for~t=1,2,...,T$
- 1.$g_t=A(D,u^{(t)})$
- 2.更新 $u^{(t)}~by~\blacklozenge_t=\sqrt\frac{1-\epsilon_t}{\epsilon_t}$
- incorrect：$u_n^{(t+1)}=u_n^{(t)}\cdot\blacklozenge_t$
- correct：$~~~~u_n^{(t+1)}=u_n^{(t)}~/~\blacklozenge_t$
- 3.計算 $\alpha_t=ln(\blacklozenge_t)$
- return $G(x)=sign(\sum\alpha_tg_t(x))$
- **AdaBoost Decision Stump**
- **Decision Stump**
- $h_{s,i,\theta}(x)=s\cdot sign(x_i-\theta)$
- 本身不夠strong，但配合Adaboost就很又效率
- 被應用在人臉辨識
## L9 Decision Tree
- 
- $G(x)=\sum\limits_{t=1}^Tq_t(x)g_t(x)$
- $q_t(x)=$[[is x on the path?]]
- $g_t(x)=$const at leaf
- $G(x)=\sum\limits_{c=1}^C[[b(x)=c]]~G_c(x)$
- $G(x):$ Full Tree Hypothesis
- $b(x):$ Branching Criteria
- $G_c(x):$ Sub Tree Hypothesis
- **C&RT 演算法**
- function $DecisionTree(data~D)$
- if cannot branch
- return $g_t(x)=E_{in}-$optimal const
- else
- 1.learn branching criteria
- $b(x)=argmin(size_1\cdot impurity_1+size_2\cdot impurity_2)$
- 2.split D to 2 parts
- $D=D_1\cup D_2$
- 3.build subtree
- $G_c(x)=DecisionTree(D_c)$
- 4.return $G(x)=\sum\limits_{c=1}^2[[b(x)=c]]G_c(x)$
- 不純度的計算
- Regression：$impurity(D)=\frac{1}{N}\sum(y_n-\bar{y})^2$
- Classificaion：$impurity(D)=\frac{1}{N}\sum[[y_n\ne y^*]]$
- Gini Index：$Gini=1-\sum\limits_{k=1}^K(\frac{\sum_{n=1}^N~~[[y_n=k]]}{N})^2$
- 停止的條件
- all $y_n$ the same：非常純
- all $x_n$ the same：找不到decision stump切點
- **一些常見的變化**
- 加入Regulization
- $\min\limits_{possible~G}E_{in}(G)+\lambda\Omega(G)$
- $\Omega(G)$=Number of Leaves(G)
- 實務上不可能算出所有的G
- $G^{(i)}=G^{(i-1)}去掉一片葉子後，使得E_{in}最小的G$
- 依序算出$G^{(0)},~G^{(1)},...,~G^{(N)}$
- 再從其中，挑出使 Regulization 式子最小的那個G
- Branching
- $y_n$不一定是數值，有可能是類別
- Decision Stump $\rightarrow$ Decision Subset
- Surrogate Branch
- 有些 data 的某些 feature 遺失了，無法被b(x)分類
- 每次在設定 branch 條件時，多 maintain 替代的 Surrogate Branch
- 找尋其他feature的decision stump，使 $b_1(x),b_2(x),...\approx~b(x)$
- C&RT 特性
- human-explainable
- multiclass easily
- categorical features easily
- missing features easily
- efficient non-linear training (and testing)

## L10 Random Forest
- **Random Forest演算法**
- $for~t=1,...,T$
- $Bootstrapping：從D抽樣出~size-N'的\tilde{D_t}$
- $g_t=DecisionTree(\tilde{D_t})$
- $return~G=Uniform(g_t)$
- 如何讓樹之間更 diverse
- 在每一次要做branch的時候
- 1.原來的d維資料中，只取d'<<d維
- 2.將原來的d維資料中，用投影矩陣P投影到d'<<d維
- 
- Out Of Bag 資料
- 每一次抽樣中，一筆資料成為OOB的機率為$(1-\frac{1}{N})^N\approx\frac{1}{e}$
- 每一次抽樣中，OOB資料的個數大約為$\frac{1}{e}\cdot N$
- 
- 用 OOB 來做 Self-Validation：
- 每一次抽樣中，OOB資料可以用來validate $g_t$，但不需要
- $E_{oob}(G)=\frac{1}{N}\sum\limits_{n=1}^Nerr(y_n,G_n^-(x_n))$
- 其中$G_i^-(x_n)=average(沒有用到data~i~的g)$
- Feature Selection
- 原因：
- Redundant：年齡和生日
- Irrelevant：生日和得癌症機率
- 好處：
- efficiency
- generalization
- interpretability
- 壞處：
- computation
- overfit
- mis-interpretability
- By Importance
- 線性模型中，|w|越大的feature，代表越importance
- 先跑一次線性模型，得到每一維度的重要性
- 把原始資料只取d'個維度，再做第二階段學習
- 非線性模型中，難以使用此種方法
- By Permutation Test
- 可能想說把某一維度，塞成其他分布，或是重新排列。
- importance( $i$ ) = performance( $D$ ) − performance( $D^{(p)}$ )
- 其中 $D^{(p)}$ 為原始資料中，把第i個維度，做任意permutation
- In Random Forest
- importance( $i$ ) $=E_{oob}(G) − E_{oob}(G^{(p)})$
- $~~~~~~~~~~~~~~~~~~~~~~~~= E_{oob}(G) − E_{oob}^{(p)}(G)$
- 其中 $E_{oob}^{(p)}(G)$ 是每次要算 $(x_n,y_n)$ 和 $g_t$ 錯誤率時，把 $(x_n,y_n)$ 的第 $i$ 個維度，換成對於 $g_t$ 是OOB的任意permutation的值。
- 
## L11 Gradient Boosted Decision Tree
- 符號釐清
- $E_{in}(h)=\sum err(y_n,h(x_n))=錯誤的點數$
- $E_{in}^u(h)=\sum u_nerr(y_n,h(x_n))=錯誤的u$
- $\epsilon=\frac{錯誤u}{正確u+錯誤u}$
- 把權重$u_n$放入 Data 的方式
- 1.在計算$E_{in}$的時候，由$\sum err(y_n,h(x_n))$ 變成 $\sum u_nerr(y_n,h(x_n))$
- 原本base algorithm $A$ 會找到一個h，使得$E_{in}(h)=\sum err(y_n,h(x_n))$最小
- 不可以再用原本的演算法了，因為有了權重
- 2.用權重代表data比例，經過sample之後餵給base algorithm $A$
- **AdaBoost-Decision-Tree**
- 演算法：
- $for~t=1,...,T$
- 1.$g_t=DecisionTree(D,u^{(t)})$
- 在這之中會用到sample
- 2.更新 $u^{(t)}~by~\blacklozenge_t=\sqrt\frac{1-\epsilon_t}{\epsilon_t}$
- incorrect：$u_n^{(t+1)}=u_n^{(t)}\cdot\blacklozenge_t$
- correct：$~~~~u_n^{(t+1)}=u_n^{(t)}~/~\blacklozenge_t$
- 3.計算 $\alpha_t=ln(\blacklozenge_t)$
- $return~G(x)=\sum\alpha_tg_t(x)$
- 演算法細節：
- 1.**pruned**：希望$E_{in}$不為0，避免$\alpha_t\rightarrow \infty$。
- 2.**sampleing**：把權重放入 Data中。
- (如果每棵樹都只有一層高 $\rightarrow$ Adaboost Decision Stump)
- **Gradient-Boosted-Decision-Tree**
- $s_1=s_2=...=s_N=0$
- $for~t=1,...,T$
- 1.$g_t=A(\{(x_n,y_n-s_n)\})$
- 使得 $\frac{1}{N}\sum\limits_{n=1}^N~(g_t(x_n)-(y_n-s_n))^2$ 最小
- 2.計算 $\alpha_t=$ 單變數linear regression$(\{(g_t(x_n),y_n-s_n)\})$
- 使得 $\frac{1}{N}\sum\limits_{n=1}^N~((y_n-s_n)-\eta g_t(x_n))^2$ 最小
- 3.$s_n=s_n+\alpha_tg_t(x_n)$
- $return~G(x)=\sum\alpha_tg_t(x)$
- **核心形式**
- AdaBoost = 選定 $e^{-ys}$ 為 error function 的 gradient boost
- $\min\limits_\eta\min\limits_h\frac{1}{N}\sum\limits_{n=1}^N~exp(~-y_n(\sum\limits_{t=1}^{T-1}\alpha_tg_t(x_n)+\eta h(x_n))~)$
- GradientBoost
- $\min\limits_\eta\min\limits_h\frac{1}{N}\sum\limits_{n=1}^N~err(~y_n~,~\sum\limits_{t=1}^{T-1}\alpha_tg_t(x_n)+\eta h(x_n)~)$
- Error Function
- $err_{0/1}(s,y)=[[ys\le 0]]$
- $err_{ADA}(s,y)=e^{-ys}$
- $err_{regression}(s,y)=(s-y)^2$
- **AdaBoost的數學解釋**
- $u_n^{T+1}$
$=u_n^1~~\blacklozenge_1^{-y_ng_1(x_n)}~~...~~\blacklozenge_T^{-y_ng_T(x_n)}$
$=u_n^{1}~~e^{-y_n\alpha_1g_1(x_n)}~~...~~e^{-y_n\alpha_Tg_T(x_n)}$
$=\frac{1}{N}~e^{-y_n\sum\limits_{t=1}^T\alpha_tg_t(x_n)}$
$=\frac{1}{N}~e^{-y_ns_n}~~~~~$ **定義 voting score ：$s=\sum\limits_{t=1}^T\alpha_tg_t(x)$**
- **定義** $E_{ADA}=\sum\limits_{n=1}^Nu_n^{T+1}=\frac{1}{N}\sum\limits_{n=1}^N~e^{-y_ns_n}$
- **透過voting score和margin比對，可知 $y_n\times$ voting score 要越大越好**
- **演算法可以在每個回合，讓$E_{ADA}$越來越小**
- **Gradient Descent ： 變數為 $\eta$ 和 $h$**
- $E_{ADA}=\frac{1}{N}\sum\limits_{n=1}^N~e^{-y_n(\sum\limits_{t=1}^{t-1}\alpha_tg_t(x_n)+\eta h(x_n))}=\sum\limits_{n=1}^Nu_n^te^{-\eta y_nh(x_n)}$
- 1.決定方向：透過 $A$ 找到 $h$
- $E_{ADA}=\sum\limits_{n=1}^Nu_n^t(1-\eta y_nh(x_n))=\sum\limits_{n=1}^Nu_n^t+\eta\sum\limits_{n=1}^Nu_n^t(-y_nh(x_n))$ (泰勒展開)
- $\sum\limits_{n=1}^Nu_n^t(-y_nh(x_n))=-\sum\limits_{n=1}^Nu_n^t+2E_{in}^{u(t)}$
- $h$ 最小化 $E_{in}^{u(t)}$ ，因此 $h$ 最小化 $\sum\limits_{n=1}^Nu_n^t(-y_nh(x_n))$
- 2.決定步伐大小：透過 $\alpha_t=ln\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}$
- $E_{ADA}=\sum\limits_{n=1}^Nu_n^te^{-\eta y_nh(x_n)}=\sum\limits_{正確n}u_n^te^{-\eta}+\sum\limits_{錯誤n}u_n^te^{\eta}$
$=(\sum\limits_{n=1}^Nu_n^t)\cdot((1-\epsilon_t)e^{-\eta}+\epsilon_te^{\eta})$
- 解極值可得$\alpha_t=\eta_t=ln\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}$
- **GradientBoost for regression**
- **Gradient Descent ： 變數為 $\eta$ 和 $h$**
- $E_{GB}=\frac{1}{N}\sum\limits_{n=1}^N~(\sum\limits_{t=1}^{t-1}\alpha_tg_t(x_n)+\eta h(x_n)-y_n)^2$
$=\frac{1}{N}\sum\limits_{n=1}^N~(s_n+\eta h(x_n)-y_n)^2$
- 1.決定方向：找一個 $h$ 最小化 $\{(x_n,y_n-s_n)\}$ 的 squared error
-
- $E_{ADA}=\frac{1}{N}\sum\limits_{n=1}^N(~(s_n-y_n)^2+2\eta h(x_n)(s_n-y_n)~)$ (泰勒展開)
- $=const+\frac{\eta}{N}\sum\limits_{n=1}^N2h(x_n)(s_n-y_n)$
- $\rightarrow~const+\frac{\eta}{N}\sum\limits_{n=1}^N(2h(x_n)(s_n-y_n)+h(x_n)^2)$
- $=const+\frac{\eta}{N}\sum\limits_{n=1}^N(~const+(h(x_n)-(y_n-s_n))^2~)$
- 找一個 $h$ 最小化 $\sum\limits_{n=1}^N(h(x_n)-(y_n-s_n))^2$
- 2.決定步伐大小：解 $\{(x_n,y_n-s_n)\}$ 的單變數 linear regression
- $E_{ADA}=\frac{1}{N}\sum\limits_{n=1}^N~(s_n+\eta g_t(x_n)-y_n)^2$
$=\frac{1}{N}\sum\limits_{n=1}^N~(y_n-s_n-\eta g_t(x_n))^2$
- 解單變數 linear regression ，可得$\alpha_t=\eta$
## L12 Neural Network
- Neural Network
- 
- 假設已經有$g_1(x)，g_2(x)$的結果
- 可以組出 AND ：$G(x)=sign(-1+g_1(x)+g_2(x))$
- 可以組出 OR ：$G(x)=sign(1+g_1(x)+g_2(x))$
- 可以組出 NOT ：$G(x)=sign(-g_1(x))$
- 更多的perceptron，可以組出更smooth 的邊界
- 
- 更多層的neural network，可以組出更nonlinear的邊界
- $XOR(g_1,g_2)=OR(AND(-g_1,g_2),AND(g_1,-g_2))$
- Transformation function
- 1.sign function  $h(x)=sign(s)$
- 離散造成難以optimize
- 2.linear function  $h(x)=s$
- 整個network變成linear，因此沒有必要做多層
- 3.sigmoid function  $h(x)=\frac{1}{1+e^{-s}}=\theta(s)$
- logistic regression用的，比較soft
- 4.hyperbolic tangent function  $h(x)=\frac{e^s-e^{-s}}{e^s+e^{-s}}=2\theta(2s)-1$
- 函數界於sign和linear之間，且容易optimize
- 符號說明
- 
- 可以看成是 $d^0-d^1-d^2-d^3~~=~~d-2-3-1$ 的 neural network
- $d^l$ 表示第 $l$ 層有多少節點
- $w_{ij}^l$ 表示第 $l-1$ 層第 $i$ 節點，到第 $l$ 層第 $j$ 節點的weight
- $s_j^l$ 表示第 $l$ 層第 $j$ 節點的input
- $s_j^l=\sum\limits_iw_{ij}^lx_i^{l-1}$
- $x_j^l$ 表示第 $l$ 層第 $j$ 節點的output
- $x_j^l=\begin{equation}\left\{\begin{array}{lr}
tanh(s_j^l) &if~l<L\\s_j^l &if~l=L
\end{array}\right.\end{equation}$
- 如何用back propagation的技術，train出neural network 的參數
- 每次餵入一組Data $\{x_n=(x_1,...,x_d),y_n\}$ ，使用gradient descent調整參數 $w_{ij}^l$ ，使得 $e_n=(y_n-NN(x_n))$ 越來越小
- Backprop演算法
- 初始化 $w_{ij}^l$
- for t = 0, 1, ..., T
- 1.Stochastic：隨機挑一組$\{x_n=(x_1,...,x_d),y_n\}$
- 2.Forward：算出所有的 $x_i^l$
- 3.Backward：算出所有的 $\delta_j^l$
- 4.Gradient Descent： $w_{ij}^l\leftarrow w_{ij}^l-\eta~\delta_j^l~x_i^{l-1}$
- Return Neural Network
- 介紹gradien descent
- 每一個 $w_{ij}^l$ 要朝向 $\frac{\partial e_n}{\partial w_{ij}^l}$ 走一小步
- $\frac{\partial e_n}{\partial w_{ij}^l}=\frac{\partial e_n}{\partial s_{j}^l}\frac{\partial s_{j}^l}{\partial w_{ij}^l}=\delta_j^l~x_i^{l-1}$
- $\delta_j^l=\sum\limits_k~\delta_k^{l+1}~w_{jk}^{l+1}~tanh^{'}(s_j^l)$，可以從後往前算
- mini-batch：平行化一次找多個點跑 step 1~3，算出 $\delta_j^l~、~x_i^{l-1}$ 的平均，再更新 step 4
- 一些常見最佳化問題
- 1.neural network並非convex
- 不一定可以找到global minimum
- sensitive to初始值
- 所以盡量要多試幾組隨機，小的初始值
- 2.$d_{VC}=O(VD)$ V是neurons個數，D是weights個數
- 可以近似任何函數，但容易overfitting
- 3.Weight-Elimination Regulizarizer $\sum\frac{{w_{ij}^l}^2}{1+{w_{ij}^l}^2}$
- 可以讓small weight在regulization的過程也有足夠的更新
- 當更新到 $w_{ij}^l=0$ 則可以不用儲存，降低$d_{VC}$
- 4.常常我們會使用early stopping
- 因為neural network太強大了
- 越多的iteration使得$d_{VC}$變得很大
## L13 Deep Learning
- Deep learning
- 
- 每一層neural network可能對應到某一個特徵的辨識
- Deep Learning會遇到的問題
- 難以決定neural network的structure
- 很高的模型複雜度
- dropout
- denoising
- 難以做很好的optimization
- 很高的計算複雜度
- **AutoEncoder**
- $d-\tilde{d}-d$ 的 neural network 使得 input = output
- 
- 我們可以看成，把 $d$ 維的資料 $x$ 轉換成 $\tilde{d}$ 維的 $\phi(x)$ ，過程中資料的特性不會遺失
- 對supervised learning ： learning informative representation
- 我們可以用 $\tilde{d}$ 維資料，代表合理的轉換 $\phi(x)$
- 對unsupervised learning ： learning typical representation
- density estimation：當 $g(x)\sim x$
- outlier detection：當 $g(x)\nsim x$
- basic autoencoder 設定
- 1.$\tilde{d}<d$，有壓縮資料的好處
- 2.Data餵給neural network：$\{(x_1,x_1),(x_2,x_2),...,(x_n,x_n)\}$
- 3.有時候會設定 $w_{ij}^1=w_{ij}^2$ 來regulization
- **Pretraining**
- 實務上，我們會做2-step的deep learning
- 
- **Regulization**
- 1.structural constraints
- 2.weighted regularizers
- 3.early stopping
- 4.denoising
- 
- 希望neural network本身就可以把有noise的資料變成沒有noise的資料
- 實務上在 data/image processing很有用
- Linear Autoencoder 的解
- General 的 Autoencoder
- $h_k(x)=\sum\limits_{j=0}^{\tilde{d}}~~w_{jk}^2~tanh(\sum\limits_{i=0}^{d}w_{ij}^1x_i)$
- Linear 的 Autoencoder
- $h_k(x)=\sum\limits_{j=1}^{\tilde{d}}~~w_{kj}^2~(\sum\limits_{i=1}^{d}w_{ij}^1x_i)$
- 1.拿掉 $x_0$
- 2.假設 $w_{ij}^1=w_{ij}^2$ 來regulization
- $W$ 是 $d\times\tilde{d}$ 的矩陣
- $WW^T=V~\Gamma V^T$
- 3.假設 $\tilde{d}<d$ 來壓縮資料
- $E_{in}(W)=\frac{1}{N}\sum\limits_{n=1}^N||x_n-WW^Tx_n||^2$
- $\min\limits_V\min\limits_\Gamma\frac{1}{N}\sum\limits_{n=1}^N||VIV^Tx_n-V~\Gamma V^Tx_n||^2$
- 最好的 $\Gamma$
- $\min\limits_\Gamma\sum\limits_{n=1}^N||(I-\Gamma)V^Tx_n||^2$
- $\Gamma=\begin{bmatrix}I_{\tilde{d}} &0\\0 &0\end{bmatrix}$
- 最好的 $V$
- $\min\limits_V\sum\limits_{n=1}^N||\begin{bmatrix}0 &0\\0 &I_{d-\tilde{d}}\end{bmatrix}V^Tx_n||^2=\max\limits_V\sum\limits_{n=1}^N||\begin{bmatrix}I_{\tilde{d}} &0\\0 &0\end{bmatrix}V^Tx_n||^2$
- $\begin{bmatrix}0 &0\\0 &0\end{bmatrix}\begin{bmatrix}1 &2\\3 &4\end{bmatrix}=\begin{bmatrix}1 &2\\0 &0\end{bmatrix}$
- $\tilde{d}=1$
- 則 $\max\limits_v\sum\limits_{n=1}^Nv^Tx_nx_n^Tv$ subject to $v^Tv=1$
- $\sum\limits_{n=1}^Nx_nx_n^Tv=\lambda v$ ，可知 $v$ 為 $X^TX$ 的 topmost eigenvectors
- 最好的 $W$
- $\{w_j\}=\{v_j~with~[[\Gamma_j=1]]\}=$ top eigenvectors
- Linear Autoencoder 演算法
- 算 $X^TX$ 的 top eigenvectors
- return $\Phi(x)=W(x)$
- Principal Component Analysis 演算法(PCA)
- 取 $\bar x=\frac{1}{N}\sum\limits_{n=1}^Nx_n$，讓 $x_n~\leftarrow~x_n-\bar x$
- 算 $X^TX$ 的 top eigenvectors
- return $\Phi(x)=W(x-\bar x)$
- [主成分分析](https://zh.wikipedia.org/wiki/%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90)