---
# System prepended metadata

title: 課程｜機器學習技法
tags: [課程]

---

# 機器學習技法

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

    - 1. &emsp;&emsp;$\max\limits_{w} ~:~margin(w)~=~\min \limits_{n=1,...,N}distance(x_n,w)$
      **subject to：** $every~y_nw^Tx_n>0$
    - 2. &emsp;&emsp;$\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. &emsp;&emsp;$\max\limits_{b,w} ~:~\frac{1}{||w||}$
      **subject to：** $\min \limits_{n=1,...,N}y_n(w^Tx_n+b)~=~1$
    ---
    - 4. &emsp;&emsp;$\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)$
> 
> &emsp;&emsp;$\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.&emsp;&emsp;&emsp;&emsp;&emsp;$\min\limits_{b,w} ~:~\frac{1}{2}w^Tw$
      &emsp;&emsp;&emsp;**subject to：** $y_n(w^Tz_n+b)~\geq~1~for~all~n$
    
    - 2.&emsp;&emsp;$\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.&emsp;&emsp;$\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)$
> 
> &emsp;&emsp;$\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**
    - &emsp;&emsp;$\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.&emsp;&emsp;$\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.&emsp;&emsp;$\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$
      &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;$+\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.&emsp;&emsp;$\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)解
            - 不一定可以微分
    - ![](https://i.imgur.com/o3K4wan.png)
- **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$
    - ![](https://i.imgur.com/0TxXbww.png)
    - 分類：
        - **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
    - ![](https://i.imgur.com/EYaAFDO.png)
    - 希望構造$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
- ![](https://i.imgur.com/Y7kX8Zf.png)
- $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維
    - ![](https://i.imgur.com/aBs01AX.png)
- Out Of Bag 資料
    - 每一次抽樣中，一筆資料成為OOB的機率為$(1-\frac{1}{N})^N\approx\frac{1}{e}$
    - 每一次抽樣中，OOB資料的個數大約為$\frac{1}{e}\cdot N$
    - ![](https://i.imgur.com/ugQApMs.png)
    - 用 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的值。
        - ![](https://i.imgur.com/ugQApMs.png)
## 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
    - ![](https://i.imgur.com/jOPcdto.png)
    - 假設已經有$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 的邊界
        - ![](https://i.imgur.com/dQQmNP3.png)
    - 更多層的neural network，可以組出更nonlinear的邊界
        - $XOR(g_1,g_2)=OR(AND(-g_1,g_2),AND(g_1,-g_2))$
- Transformation function
    - 1.sign function ![](https://i.imgur.com/vaG1oSU.png) $h(x)=sign(s)$
        - 離散造成難以optimize
    - 2.linear function ![](https://i.imgur.com/5m5vRAW.png) $h(x)=s$
        - 整個network變成linear，因此沒有必要做多層
    - 3.sigmoid function ![](https://i.imgur.com/d89yyfp.png) $h(x)=\frac{1}{1+e^{-s}}=\theta(s)$
        - logistic regression用的，比較soft
    - 4.hyperbolic tangent function ![](https://i.imgur.com/iIJGBBO.png) $h(x)=\frac{e^s-e^{-s}}{e^s+e^{-s}}=2\theta(2s)-1$
        - 函數界於sign和linear之間，且容易optimize
- 符號說明
    - ![](https://i.imgur.com/dAWKaTb.png)
    - 可以看成是 $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
    - ![](https://i.imgur.com/q3HzsI4.png)
    - 每一層neural network可能對應到某一個特徵的辨識
    - Deep Learning會遇到的問題
        - 難以決定neural network的structure
        - 很高的模型複雜度
            - dropout
            - denoising
        - 難以做很好的optimization
        - 很高的計算複雜度
- **AutoEncoder**
    - $d-\tilde{d}-d$ 的 neural network 使得 input = output
    - ![](https://i.imgur.com/2V7gRhA.png)
    - 我們可以看成，把 $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
    - ![](https://i.imgur.com/Dbvf8lE.png)
- **Regulization**
    - 1.structural constraints
    - 2.weighted regularizers
    - 3.early stopping
    - 4.denoising
        - ![](https://i.imgur.com/kZh7Iza.png)
        - 希望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)

