發表於 | 分類於

decision tree

在訓練過程中決策樹會問出一系列的問題。首先會從最後上方的樹根開始將資料的特徵將資料分割到不同邊(比方說依據溫度將資料切成三份)，分割的原則是：這樣的分割要能得到最大的資訊增益(Information gain, 簡稱IG)。

Information gain計算方式 :
$$
IG(D_p,f) = I(D_p)-\sum^{m}_{j=1}\frac{N_j}{N_p}I(D_j)
$$
常見的計算資訊量的方式有下列兩種 :

  • Entropy
    $$
    I_H(t) = -\sum^{c}_{i=1}p(i|t)log_2p(i|t)
    $$
  • Gini
    $$
    I_G(t) = \sum^{c}{i=1}p(i|t)(1-p(i|t)) = 1-\sum^{c}{i=1}p(i|t)^2
    $$

訓練過程中，藉由找到最大IG的方式來確定分割問題的方式。

pruning(剪枝)

因為 decision tree 容易 overfitting 。我們稱只顧眼前利益而採限制條件的方法為「greedy」，ID3, C4.5以及CART等大部份的決策樹模型都是屬於此類，此種方式比較不會考慮後果而肓目的分枝生長，所以才有Tree pruning的方法產生，以避免樹過度生長而造成過度擬合問題。

random forest

  1. 隨機從資料集中選擇部分資料出來訓練 (boostrap)(bagging)
  2. 將部分資料做成 decision tree

  3. 最後 ensemble 各個分類器，來提升結果

    random forest 條件 :

  • 各個分類器之間須具有差異性。
  • 每個分類器的準確度必須大於0.5。

發表於 | 分類於

boosting

Boosting算法是將很多個弱的分類器(weak classifier)進行合成變成一個強分類器(Strong classifier)，和Bagging不同的地方是分類器之間是有關聯性的，是透過將舊分類器的錯誤資料權重提高，然後再訓練新的分類器，這樣新的分類器就會學習到錯誤分類資料(misclassified data)的特性，進而提升分類結果。

如果再用全部的data下去訓練，錯的資料永遠都會判錯，因此我們會輸入錯的資料，需要針對錯誤的資料去學習(將錯誤的資料權重加大)，那這樣新訓練出來的分類器才能針對這些錯誤判讀的資料得到好的結果。

adaboost

AdaBoost : 讓判斷錯誤的train data提高權重，讓產生新的權重的training set讓舊的分類器 fail掉，但在新的分類器上就去加強學這些權重較大的training set。

最後我們會得到 f1(x),…,fL(x)個分類器。我們需要把 L個分類器的結果做加權總合
$$
H(x) = sign(\sum^{L}_{k=}a_kf_k)和training data的權重不太一樣，錯誤率越低的分類器在最後結果的合成上要佔\較大的權重，下面假設錯誤率分別為0.1, 0.2, 0.4下的權重變化：\
εk=0.1, αk=0.5ln⁡(((1–0.1))/0.1)=1.0986\
εk=0.2, αk=0.5ln⁡(((1–0.2))/0.2)=0.6931\
εk=0.4, αk=0.5*ln⁡(((1–0.4))/0.4)=0.2027\
$$
和training data的權重不太一樣，錯誤率越低的分類器在最後結果的合成上要佔較大的權重，下面假設錯誤率分別為0.1, 0.2, 0.4下的權重變化：

εk=0.1, αk=0.5 ln⁡(((1–0.1))/0.1)=1.0986
εk=0.2, αk=0.5 ln⁡(((1–0.2))/0.2)=0.6931
εk=0.4, αk=0.5 * ln⁡(((1–0.4))/0.4)=0.2021

發表於

  • blending 意思是混和我們的模型
    $$
    \begin{align}
    G(x)=&\frac{1}{T}\sum^{T}_{t=1}g_t(x)\avg((g_t(x)-f(x))^2)=&avg(g_t^2-2g_tf+f^2)\=&avg(g_t^2)-2Gf+f^2\=&avg(g_t^2)-2G^2+G^2+(G-f)^2\=&avg((g_t-G)^2)+(G-f)^2
    \avg(E_{out}(g_t)) =& avg(\epsilon(g_t-G)^2)+(G-f)^2
    \end{align}
    $$
    所以將模型平均後的 error 可能比隨意選取的模型error還要來得小
    $$
    avg(\epsilon(g_t-G)^2) 表示各個模型之間的差異
    $$
    我們也可以用很多不同的方式做blending ，不一定是線性。

  • bagging (boostrap aggregation)

    給定一個大小為n的訓練集D，bagging 算法從中任意選出m個大小為n’的子集合，作為新的訓練集，之後再將其平均或者投票，得到bagging的結果，這種抽樣的方式在統計上叫做boostrap。

  • adaptive boosting

    1. obtain $g_t by A(D,u^{(t)}) ，u^{(t)}一開始為\frac{1}{N}(uniform)$

    2. update $u^{(t)} to u^{(t+1)} by A_t = (\frac{1-E}{E})^{0.5}$

      E 為錯誤率，表示錯得越少我們給越大的權重

    3. compute $\alpha_t = ln(A_t)$

    4. return $G(x)=sign(\sum^{T}{t=1)\alpha_tg_t(x)$

發表於 | 分類於

1.它是一種二類分類模型，目的是找出margine(support vector 到 hyper plane的距離)最大的模型。

2.support vector : 在 margin 邊界上的點

  • $$
    magin = |\frac{w^T}{||w||}(x-x’)| = \frac{1}{||w||}|w^Tx+b|
    $$

    $$
    因為 y_n(w^Tx_n+b)>0 (分類正確)
    $$

    $$
    margin(b,w) = min_{n=1,..,N}\frac{1}{||w||}y_n(w^Tx_n+b)
    $$

    $$
    我們可以令 min y_n(w^Tx_n+b) = 1 ，不會影響分類結果，margin=\frac{1}{||w||}
    $$

    $$
    我們目標為最大化margin = \frac{1}{||w||}，等同於min_{b,w}\frac{1}{2}w^Tw
    $$

    $$
    e.q. y_n(w^Tx_n+b) >1.5 ，我們可以scale (\frac{b}{1.5},\frac{w}{1.5})，
    $$

    $$
    所以 y_n(w^Tx_n+b) >1也是可以的 ，修正條件為 y_n(w^Tx_n+b)\geq1
    $$

  • 我們可以使用QP(quaratic programming)求解，再使用（Lagrange Duality）將約束條件合併到目標中。
    $$
    y_n(w^Tx_n+b)\geq1
    $$

    $$
    L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum^{n}_{i=1}\alpha_i(y_i(w^Tx_i+b)-1)
    $$

    $$
    SVM = min_{b,w}(max_{all \alpha_n\geq0}L(b,w,\alpha))
    $$

    $$
    如果沒有符合條件，L 會趨近無限大，如果符合條件，L會等於\frac{1}{2}||w||^2
    $$

    $$
    Lagrange 是把問題變得看似沒有約束條件，把條件併入問題中
    $$

  • $$
    min_{b,w}(max_{all \alpha_n\geq0}L(b,w,\alpha)) \geq max_{all \alpha_n\geq0}(min_{b,w}L(b,w,\alpha))
    $$

    這稱為 （Lagrange Duality）。
    $$
    \frac{\partial L(b,w,\alpha)}{\partial b}=-\sum^{N}_{n=1}\alpha_ny_n=0 ，代回原式可把b消除
    $$

    $$
    \frac{\partial L(b,w,\alpha)}{\partial w_i}=w_i-\sum^{N}_{n=1}\alpha_ny_nz_{n,i}=0，代回原式
    $$

    $$
    max_{all \alpha_n\geq0,\sum yn\alpha_n=0,w=\sum \alpha_ny_nz_n}-\frac{1}{2}||\sum^{N}_{n=1}\alpha_ny_nz_n||^2+\sum^{N}_{n=1}\alpha_n
    $$

    $$
    min_{all \alpha_n\geq0,\sum yn\alpha_n=0,w=\sum \alpha_ny_nz_n}\frac{1}{2}||\sum^{N}_{n=1}\alpha_ny_nz_n||^2-\sum^{N}_{n=1}\alpha_n
    $$

    $$
    min \frac{1}{2}A^TQA+P^TA ， subject \quad \alpha_j^TA\geq c_i\quad for\quad i=1,2,…
    $$

    ​ 代入 QP 利用SMO算法即可以求出。

  • kernel function

    透過核函數將低維映射到高維空間，進一步將平面上不好分開的區間分開，且避開了在高維空間中進行計算。
    $$
    f(x)=\sum^{n}_{i=1}\alpha_iy_i<x_i,x>+b
    $$
    映射成
    $$
    \sum^{n}_{i=1}\alpha_iy_i<\phi(x_i),\phi(x)>+b
    $$

​ 可以使用很多不同的 kernel function，例如 : linear 、polynomial、gaussian。

  • soft margin SVM : 因為雜訊關係，可能有些數據偏離原本位子很多，造成margin嚴重縮小，我們稱該點為outlier，所以提出 soft margin SVM，我們可以忽略一些 outlier ，來讓我們的結果好一點。
    $$
    y_i(w^Tx_i+b)\geq 1-\zeta_i 改成 y_i(w^Tx_i+b)\geq 1-\zeta_i
    $$

    $$
    \zeta_i\geq0 稱為(slack\quad variable)，為允許數據點偏離 margin的量
    $$

    $$
    所以目標函數改為 min \frac{1}{2}||w||^2+C\sum^{n}_{i=1}\zeta_i
    $$

發表於 | 分類於

  • 為何 logistic regression 要求 maximum likelihood ?

    在機器學習中，我們通常是最小化損失函數，但在logistic regression 中，我們求 maximum likelihood，兩者是等效的。
    $$
    P(Y=1|x)=\pi(x) , P(Y=0|x)=1-\pi(x)
    $$

    $$
    likelihood->L(w) = \prod[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}
    $$

    $$
    log likelihood->lnL(w) = \sum[y_iln\pi(x_i)+(1-y_iln(1-\pi(x_i)))]
    $$

    $$
    \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad=\sum[y_iln\frac{\pi(x_i)}{1-\pi(x_i)}+ln(1-\pi(x_i))]
    $$

    $$
    max\quad lnL(w) = min \quad-lnL(w)
    $$

    $$
    取整個數據的平均對數似然損失 J(w) = -\frac{1}{N}lnL(w)
    $$

    ​ 所以最大化似然函數與最小化對數似然損失是等價的 !!

  • logistic regression 跟 maximum entropy model 關係?

    其實兩者 logistic regression就是 maximum entropy model 類別為兩類的情況，當處理多類別時，就是 maximum entropy model。

  • sigmoid 跟 softmax 關係?

    softmax 可以處理多類別，當類別為二元分類時即是 sigmoid

  • 牛頓法

    https://ccjou.wordpress.com/2013/07/08/%E7%89%9B%E9%A0%93%E6%B3%95%E2%94%80%E2%94%80%E9%9D%9E%E7%B7%9A%E6%80%A7%E6%96%B9%E7%A8%8B%E7%9A%84%E6%B1%82%E6%A0%B9%E6%96%B9%E6%B3%95/

  • 可以使用梯度下降法或牛頓法，這次我採用牛頓法進行實作，程式碼在這 !!! https://github.com/citya1472581234/machine_learning/tree/master/logistic_regression

  • 以下是實作 logistic regression 的 loss 與 accuracy 的變化。

發表於 | 分類於

​ 主要的概念有 :增長函數（growth function）、對分（dichotomy）、打散（shattering）和中斷點（break point）

  1. 增長函數 : 增長函數表示空間H對m個數據所能賦予標記的最大可能結果數

    假設現在有A、B兩點，考慮二分類的情況，可能的值有：AA、AB、BA和BB，所以這裡增長函數為4。

  2. 對分 : 假定我們的Hypothesis Set H是一個Binary function的集合當我們將一個大小為N的sample data set記做 $ x1,x2,…,x_{N} $ ，做為H中的一個hypothesis h的輸入的時候，我們就會得到一個長度為N的tuple，形如 $(h(x1),h(x2),…,h(x_N))$。
    ​ 而這個tuple中的每個元素都是+1或者-1，我們把這樣的一個tuple就稱作為一個Dichotomy，然後我們定義，對於一個Hypothesis Set H來說 $H(x1,x2,…,x_N)$是H在sample$(x1,x2,…,x_N)$上所有Dichotomy 的集合

  3. 打散 : 指的是假設空間H能實現數據集D上全部示例的對分，以二元分類來看即增長函數為$2^m$

  4. Vapink-Chervonenkis Dimension : 在於我們以前是無法約束hypothesis的數量的。在Hoeffding’s Inequality中， $P[|E_{in}-E_{out}|>\epsilon]\leq2Me^{-2\epsilon^2N}$ 其中的M，也就是Hypothesis Set H的勢為無窮大，在Generalization Bound中， $E_{out}\leq E_{in}(g)+(\frac{1}{2N}ln\frac{2M}{\delta})^{0.5}$ ，M也是無窮大，導致無法判斷學習的可行性，所以我們必須找到有限的M

  1. Growth function : Growth function是指針對任意N個點的最多的dichotomy數，而前面的集合M是指對於特定的一個data set所能產生的dichotomy的集合，也就是說$m_H(N) = max|H(x1,x2,…,x_N)|$

    定義H為一個平面中的所有直線，若一個點在直線的一邊，則return +1，否則return -1。

    N=3時，Growth function的值為8

    N=4時，Growth function的值為14，所以

    $ m_H(N)<2^N$
    如果break point存在，$m_{H}(N)$就是一个polynomial

    對於這個例子，break point 為 4

​ 這樣一來我們的Hoeffding’s Inequality和Generalizaiton Bound就明顯可以很好地收斂，換句話說，如果break point存在，我們就可以說，Learning是可行的。

發表於 | 分類於

  • cycle gan

    • 整個cycle可以看成是一個autoencoder,兩個generator看成是encoder和decoder,而兩個discriminator則是準則,整體架構如下:

      cyclegan

    • loss 方面,有兩個判別網路的loss,還有兩個生成網路的loss,最後是L1 loss(希望生成圖像，與輸入圖像很接近)

      cycleganloss

  • pix2pix

    • 判別網路將兩張圖片組成一個 pair ,輸入從三通道變六通道的疊加圖,整體結構如下:

    ​ pix2pix

    • patch gan

      將圖像分成NxN的patch,來減少運行時間,還能更好的處理大圖片的細節patch

    • loss 方面,有一個gan的loss,和L1 loss

      pix2pixloss

    • Unet

      類似 auto encoder + residual , 來減輕訓練的負擔 ,整體結構如下:unet

  • convolution auto encoder

    • 將圖片經由conv壓縮成向量,在deconv重構成原來圖片cae