【筆記】機器學習基石 數學基礎 Week2

本週主題 :Learning to Answer Yes/No,就是學會說 Yes/No 問句,其實是學會進行二元分類(Binary classification)

上週課程提到,在機器學習中存在一個 Learning Algorithm AA 與一個假說集合 Hypothesis Set HHAA 在觀察餵入的的資料集合 DD 後,會從假說集合挑選一個最符合的 gg ,這個 gg 會在最後應用階段時,被使用來進行分類。

延續上週核發信用卡的例子,發不發卡是一個二元分類問題,最終經由 gg 後,會得到 Yes(發卡)或 No(不發卡)結果。


感知器 Perceptron

開始上課前,我先岔開查了感知器(Perceptron),這個詞所代表的意思與定義。
感知器這個名詞緣起於類神經網路時期,這個演算法的概念跟真實的生物神經元傳遞訊號的機制類似。

enter image description here

生物的神經細胞可被視為只有兩種狀態的機器—激動時為『是』,而未激動時為『否』。而其狀態,取決於所接收到的輸入訊息,及輸入訊息的強度。當強度超過了某個門檻值時,細胞體會激動產生電脈衝,透過軸突發送訊息給下一個神經元。

如果不管生物學上的例子,感知器其實就是一種二元線性分類器(Linear Binary Classifiers),唯有當輸入的訊息符合標準或門檻值時,才會觸發下一個動作(發卡)。


Perceptron Hypothesis Set

在發卡的例子中,銀行可能掌握了用戶各種屬性資料,如年齡、性別、年收入、負債、工作經歷…等情況。而每位使用者的資料可以向量來表示:
X={x1,x,2,...,xd} X = \{x_1, x,2, ... ,x_d\}

銀行會對每個條件進行評分,也就是依照每個條件的正/負相關性給予給與權重,例如:年收入的權重給予 1,負債的權重給予 -1 …等。而權重也可以用向量來表示:
W={w1,w2,...,wd} W = \{w_1,w_2,...,w_d\}

而銀行唯有當這些條件的總分,超過門檻值(threshold , TT)時,才會核發信用卡:

score=i=1dwixi,and{score>T, approvescore<T, rejectscore=0, ignored score = \sum_{i=1}^{d}{w_ix_i} , and \left\{ \begin{array}{l} score > T ,\ approve \\ score < T , \ reject \\ score = 0 ,\ ignored \end{array} \right .

我們將其輸出 yy 的結果集合使用符號來表示,可稱為Label,可表示為 y={+1(approve),1(reject)}y = \{ +1 (approve) , -1 (reject)\} , 0 ignored,因此式子可簡化成
h(x)=sign(i=1dwixiT), where h(x)H h(x) = sign(\sum_{i=1}^{d}{w_ix_i} - T) ,\ where\ h(x) ∈ H
其中
sign(x)={+1, x>01, x<0 sign(x) = \left\{ \begin{array}{l} +1,\ x >0 \\ -1,\ x < 0 \end{array} \right .



為簡化數學式的表示,可針對數學符號再做進一步的化簡
h(x)=sign(i=1dwixiT)=sign(i=1dwixi+(T)w0×(+1)x0)=sign(i=0dwixi)=sign(WTX) \begin{aligned} h(x) &= sign(\sum_{i=1}^{d}{w_ix_i} - T) \\ &= sign(\sum_{i=1}^{d}{w_ix_i} + \underbrace{(-T)}_{w_0} \times \underbrace{(+1)}_{x_0}) \\ &= sign(\sum_{i=0}^{d}{w_ix_i}) \\ &= sign(W^TX) \end{aligned}
個人經驗雖然兩者意義上相同,但在實務上偏向使用矩陣運算,因為矩陣運算的可以藉由GPU使用CUDA來加速。


Perceptrons in R^2

為可視化,我們將感知器使用在二維平面上,即表示只使用兩種條件,例如年收入與負債兩種,若使用越多條件會映射到更高維度的空間。因此 h(x)h(x) 可表示成 sign(w0+w1x1+w2x2)sign(w_0 + w_1x_1+w_2x_2),因為 signsign 是以 0 為分界線的函數,因此可設 w0+w1x1+w2x2=0w_0 + w_1x_1+w_2x_2=0 ,該式恰是一條直線方程式,而不同權重 WW 會對應到不同的直線。

若將平面上個點依照線段來劃分,所有的點會分落在線段兩側,一側為正另一側為負。而我們期望的目標是能找到一條直線 ,剛好能將不同的 Label 劃分開來。

enter image description here

因為感知器的實做其實是藉由一條直線方程,來劃分平面上所有點,因此只能作為一個二元線性分類器(Linear Binary Classifiers)。


Perceptron Learning Algorithm (PLA)

在上一節中,我們可得知感知器中 Hypothesis Set 的所有可能集合 HH,也就是平面上所有的直線。一旦有了 DDHH 後,我們就可以藉由機器學習演算法來挑選最適合的線段。


何謂最適合的線段?

之前提過,機器再觀察餵入的資料會從 Hypothesis Set HH 中學到一函數 Hypothesis gg ,在期望上我們希望 gg 越接近 Target function ff 越好。但之前也提過,我們並不知曉 ff 到底長怎樣。因此實做時根本不可能與 ff 相互比較。

但我們可使用餵入的資料來協助找到最好的 gg ,先忽略錯誤標記及存在雜訊的情況下,我們可以假設所輸入的資料 xx 在經由 f(x)f(x) 後,可以得到一輸出結果 yy。 如果我們可以從 HH 中 找到一條 gg ,對每個點其輸出結果與 ff 完全一致,我們則認為 gg 是個不錯的結果。

因此在這邊對於合適線段的定義應該是,找到一條只直線 gg ,使資料集中所有點的分類結果與本身的 Label 一致


如何找到最適合的線段?

若在 Hypothesis Set HH 不大的情況下,可以每條線段逐一檢查。但在平面上的線段是無窮多的,根本不可能一一檢查。
因此這邊採用逐漸修正的方式,在取得一條初始線段 g0g_0 的情況下,經過不斷的錯誤修正,對線段進行平移旋轉等操作,最終能找到一條 gfg_f ,這就是Perceptron Learning Algorithm (PLA) 演算法的核心。


特別提醒: WW 其實是直線方程的法向量


PLA 演算法

具體演算法流程如下:

1. 初始化權重 W 為 W0,設定 W0 = 0
2. 按序或隨機邊遍歷訓練中的點,找尋分類與 Label 不符的:
	1. 若存在,則更新權重 W 後,重新執行步驟二。
	2. 若不存在,停止執行。



將所找到的錯誤點標記為 (Xn(t),Yn(t))(X_{n(t)}, Y_{n(t)}) ,權重更新公式如下:
Wt+1Wt+Yn(t)Xn(t) W_{t+1} \leftarrow W_t + Y_{n(t)}X_{n(t)}

如果 sign()=1sign()=-1,但是 y=+1y=+1,也就是说 WWXX 的夾角過大,需要使 WWXX 靠攏,即左圖。
如果 sign()=+1sign()=+1,但是 y=1y=-1,也就是说 WWXX 的夾角過小,需要使 WWXX 遠離,即右圖。
向量修正



雖然PLA的核心相當的簡單,但有幾個最基本的問題需要解決的是:

  1. 這演算法何時會停下來?
  2. 如果停下來,找到的g_f 真的接近 f 嗎?



Guarantee of PLA

PLA 演算法停止必須滿足訓練集所有樣本都是線性可分的(linear separable),也就是說平面上必須至少存在一條線的,並且使的線的一側全為藍點,另一側全為紅點。



[證明] PLA會停止運行

TODO: 證明改成英文的 LaTeX的中文好醜

(1) 評估 Wt+1W_{t+1}WtW_{t}WfW_f 的相近程度
\because D 為線性可分
\therefore 必存在一條直線其法向量為 WfW_f ,使 DD 中所有點皆符合 Yn=sign(WfTXn)Y_n = sign(W_f^TX_n)
 
\because 已知 Yn=sign(WfTXn)Y_n = sign(W_f^TX_n)
\therefore 可推知 YnWfTXn>0Y_nW_f^TX_n > 0min(YnWfTXn)>0min( Y_nW_f^TX_n) > 0
 
\because 在運行 tt 次時,存在一個分類錯誤的點 (Xn(t),Yn(t))(X_{n(t)}, Y_{n(t)})
 (Xn(t),Yn(t))D\because\ (X_{n(t)}, Y_{n(t)}) \in D
\therefore 可推知 Yn(t)WfTXn(t) min(YnWfTXn)>0Y_{n(t)}W_f^TX_{n(t)} \geq\ min( Y_nW_f^TX_n) > 0
 
為評估 WfW_fWt+1W_{t+1} 的相近程度,故使向量內積 
WfTWt+1=WfT(Wt+Yn(t)Xn(t)) Wt+1Wt+Yn(t)Xn(t)=WfTWt+WfTYn(t)Xn(t))WfTWt+min(YnWfTXn) Yn(t)WfTXn(t) min(YnWfTXn)>WfTWt+0 min(YnWfTXn)>0 \begin{aligned} W_f^TW_{t+1} &= W_f^T( W_t + Y_{n(t)}X_{n(t)} ) \qquad \because\ W_{t+1} \leftarrow W_t + Y_{n(t)}X_{n(t)} \\ &= W_f^TW_t + W_f^TY_{n(t)}X_{n(t)} ) \\ &\geq W_f^TW_t + min( Y_nW_f^TX_n) \qquad \because\ Y_{n(t)}W_f^TX_{n(t)} \geq\ min( Y_nW_f^TX_n) \\ &> W_f^TW_t + 0 \qquad \because\ min( Y_nW_f^TX_n) > 0 \end{aligned}
可得 WfTWt+1>WfTWtW_f^TW_{t+1} > W_f^TW_t ,向量內積隨執行次數增加而增加



(2) 排除向量長度增長對向量內積增加的影響
\because 在運行 tt 次時,存在一個分類錯誤的點 (Xn(t),Yn(t))(X_{n(t)}, Y_{n(t)}) ,使的 sign(WtT,Xn(t))Yn(t)sign(W_t^T, X_{n(t)}) \neq Y_{n(t)}
\therefore 可推知 Yn(t)(WtT,Xn(t))0Y_{n(t)}(W_t^T, X_{n(t)}) \leq 0
 
\because 已知 Wt+1Wt+Yn(t)Xn(t)W_{t+1} \leftarrow W_t + Y_{n(t)}X_{n(t)} ,故可得
Wt+12=Wt+Yn(t)Xn(t)2=Wt2+2WtYn(t)Xn(t)+Yn(t)Xn(t)2Wt2+0+Yn(t)Xn(t)2Yn(t)(WtT,Xn(t))0Wt2+maxYn(t)Xn(t)2Wt2+maxXn(t)2Yn(t)±1 \begin{aligned} { \parallel W_{t+1} \parallel}^2 &= {\parallel W_t + Y_{n(t)}X_{n(t)} \parallel} ^2 \\ &= {\parallel W_t \parallel} ^2 + 2 W_tY_{n(t)}X_{n(t)} + {\parallel Y_{n(t)}X_{n(t)} \parallel} ^2 \\ &\leq {\parallel W_t \parallel} ^2 + 0 + {\parallel Y_{n(t)}X_{n(t)} \parallel} ^2 \qquad \because Y_{n(t)}(W_t^T, X_{n(t)}) \leq 0 \\ &\leq {\parallel W_t \parallel} ^2 + {max\parallel Y_{n(t)}X_{n(t)} \parallel} ^2 \\ &\leq {\parallel W_t \parallel} ^2 + {max\parallel X_{n(t)} \parallel} ^2 \qquad \because Y_{n(t)} 為 \pm1,取平方後無影響 \\ \end{aligned} \\
可得 Wt+12Wt2+maxXn(t)2{ \parallel W_{t+1} \parallel}^2 \leq {\parallel W_t \parallel} ^2 + {max\parallel X_{n(t)} \parallel } ^2 ,證明在運行中向量長度增加緩慢



(3) 證明隨執行次數增加而 Wt+1W_{t+1}WfW_f 逐漸靠近
\because 已知向量內積公式為 ab=abcosθ\vec a \cdot \vec b = |\vec a||\vec b| cos{\theta}
\because 又從(1)中得知,向量內積隨執行次數增加而增加
\because 又從(2)中得知,在運行中向量長度增加緩慢
\therefore 向量內積的增加,為 cosθcos{\theta} 增加所導致
\therefore 證明隨執行次數增加而 Wt+1W_{t+1}WfW_f 逐漸靠近



(4) 證明PLA會停止
設定初始向量為 W0=0W_0 = 0,從 0 開始進行 TT 次迭代
 
由(2)推知:
WT2WT12+maxXn2WT22+maxXn2+maxXn2W02+TmaxXn2TmaxXn2 W0=0 \begin{aligned} { \parallel W_T \parallel}^2 &\leq {\parallel W_{T-1} \parallel} ^2 + {max\parallel X_{n} \parallel} ^2 \\ &\leq {\parallel W_{T-2} \parallel} ^2 + {max\parallel X_{n} \parallel} ^2 +{ max \parallel X_{n} \parallel} ^2 \\ &\leq {\parallel W_{0} \parallel} ^2 + T \cdot {max\parallel X_{n} \parallel} ^2 \\ &\leq T \cdot {max\parallel X_{n} \parallel} ^2 \qquad \because\ W_{0} = 0 \\ \end{aligned}
 
由(1)推知:
WfTWTWfTWT1+min(YnWfTXn)WfTWT2+min(YnWfTXn)+min(YnWfTXn)WfTW0+Tmin(YnWfTXn)Tmin(YnWfTXn) \begin{aligned} W_f^TW_{T} &\geq W_f^TW_{T-1}+ min( Y_nW_f^TX_n) \\ &\geq W_f^TW_{T-2}+ min( Y_nW_f^TX_n) + min( Y_nW_f^TX_n) \\ &\geq W_f^TW_{0}+ T \cdot min( Y_nW_f^TX_n) \\ &\geq T \cdot min( Y_nW_f^TX_n) \\ \end{aligned}
 
結合上述兩結論,可得
WfTWfWTWTTmin(YnWfTXn)WfWTTmin(YnWfTXn)WfTmaxXn(t)2Tmin(YnWfTXn)WfmaxXn(t)Tmin(YnWfTXn)WfmaxXn(t)TC,C=min(YnWfTXn)WfmaxXn(t) \begin{aligned} \frac{W_f^T}{ \parallel W_f\parallel} \frac{W_T}{ \parallel W_T \parallel} &\geq \frac {T \cdot min( Y_nW_f^TX_n)}{\parallel W_f\parallel \parallel W_T \parallel} \\ &\geq \frac {T \cdot min( Y_nW_f^TX_n)}{\parallel W_f\parallel \sqrt{T \cdot {max\parallel X_{n(t)} \parallel } ^2 }} \\ &\geq \frac {\sqrt{T} \cdot min( Y_nW_f^TX_n)}{\parallel W_f\parallel max\parallel X_{n(t)} \parallel } \\ &\geq \sqrt{T} \frac { min( Y_nW_f^TX_n)}{\parallel W_f\parallel max\parallel X_{n(t)} \parallel } \\ &\geq \sqrt{T} \cdot C , \qquad C = \frac { min( Y_nW_f^TX_n)}{\parallel W_f\parallel max\parallel X_{n(t)} \parallel } \\ \end{aligned} \\
 
已知內積中正規化後,乘積最多為 1
故可得
1WfTWfWTWTTmin(YnWfTXn)WfmaxXn(t) \begin{aligned} 1 &\geq \frac{W_f^T}{ \parallel W_f\parallel} \frac{W_T}{ \parallel W_T \parallel} \\ & \geq \sqrt{T} \frac { min( Y_nW_f^TX_n)}{\parallel W_f\parallel max\parallel X_{n(t)} \parallel } \\ \end{aligned}
 
化簡後:
R2ρ2=Wf2maxXn(t)2min(YnWfTXn)2 \frac{R^2}{\rho^2} = \frac {\parallel W_f\parallel^2 max\parallel X_{n(t)} \parallel^2 } { min( Y_nW_f^TX_n)^2} \geq
其中
R2=maxXn(t)2ρ2=min(YnWfTWfXn) R^2 = max\parallel X_{n(t)} \parallel^2 \qquad \qquad \rho^2 = min(Y_n \frac {W_f^T}{\parallel W_f\parallel }X_n)
從最後一條式子看來T是有上限的,因此在線性可分的情況下,PLA 最終會停止


Non-Separable Data

PLA 演算法的優缺點相當清楚,優點是簡易實做,可以適用於任何維度,缺點是資料必須是線性可分的,可是是否為線性可分通常無法事前得知。即使資料是線性可分的,但因為時間複雜度高,執行時間也會耗費相當久。

另一種情況是 ff 產生的資料本身是線性可分,但因雜訊(noise)、輸入錯誤…等因素,最終產生出線性不可分的資料,也會使得 PLA 無法停止。
 
 
為避免無窮迴圈的情況發生,因此我們退而求其次,不找不犯錯的線,改找犯錯最少的線:
Wg=argminn=1N(Ynsign(WTXn) W_g = argmin \sum_{n=1}^N (Y_n \neq sign(W^TX_n)
但此類問題已經被證實是一個NP-hard問題,不可能找到最佳解,只能找到近似解。
 
 
這邊提出了一個近似的演算法Pocket,他本質是一個貪婪演算法,屬於PLA演算法的變形,演算法如下:

1. 初始化權重 W 為 W0,設定 W0 = 0
2. 隨機邊遍歷訓練中的點,找尋分類與 Label 不符的:
   1. 若存在,則更新 W 後,並統計新線段存在的錯誤點數。若總數小於所紀錄,則更新紀錄與對應權重。
   2. 若不存在,停止執行。
3. 執行前,請先設定中止條件,EX:執行次數、錯誤點少於多少時停止…等。



課堂測驗

Q1 . Assume that each email is represented by the frequency of keyword occurrence, and output +1 indicates a spam. Which keywords below shall have large positive weights in a good perceptron for the task?

  • [ ] coffee, tea, hamburger, steak
  • [V] free, drug, fantastic, deal
  • [ ] machine, learning, statistics, textbook
  • [ ] national, Taiwan, university, coursera




Q2 . Let n=n(t)n = n(t), according to the rule of PLA below, which formula is true?
sign(wtTxn)yn, and , ,wt+1wt+ynxn sign(w^T_tx_n)≠y_n ,\ and\ ,\ , w_{t+1} \leftarrow w_t + y_nx_n

  • [ ] wt+1Txn=ynw^T_{t+1}x_n = y_n
  • [ ] sign(wt+1Txn)=ynsign(w^T_{t+1}x_n)=y_n
  • [V] ynwt+1TxnynwtTxny_nw^T_{t+1}x_n \geq y_nw^T_tx_n
  • [ ] ynwt+1Txn<ynwtTxny_nw^T_{t+1}x_n < y_nw^T_tx_n




Q3 . Define R2=maxnxn2R^2 = max_n \parallel x_n\parallel^2 , ρ=minnynwfTxfxn\rho = min_ny_n \frac {w^T_f}{\parallel x_f \parallel} x_n. We want to show that TT \leq □. Express the upper bound by the two terms above.

  • [ ] R/ρR/\rho
  • [V] R2/ρ2R^2/\rho^2
  • [ ] R/ρ2R/\rho^2
  • [ ] ρ2/R2\rho^2/R^2




Q4 .Since we do not know whether DD is linear separable in advance, we may decide to just go with pocket instead of PLA. If DD is actually linear separable, what’s the difference between the two?

  • [V] pocket on DD is slower than PLA
  • [ ] pocket on DD is faster than PLA
  • [ ] pocket on DD returns a better gg in approximating ff than PLA
  • [ ] pocket on DD returns a worse gg in approximating ff than PLA



課程資料

  1. 課程影片: Perceptron Hypothesis Set
  2. 課程影片:Perceptron Learning Algorithm (PLA)
  3. 課程影片:Guarantee of PLA
  4. 課程影片: Non-Separable Data



參考資料

  1. 感知器 - 維基百科
  2. FUNcLogs: 感知學習演算法(Perceptron Learning Algorithm)白話說明
  3. [資料分析&機器學習] 第3.2講:線性分類-感知器(Perceptron) 介紹 – Yeh James – Medium
  4. Linear separability - Wikipedia
  5. 投影屏15页的constant如何推导出?


參考筆記

  1. 机器学习基石笔记2——在何时可以使用机器学习(2) - 杜少 - 博客园
  2. 机器学习基石笔记2——在何时可以使用机器学习(2) - Deribs4 - 博客园
  3. 听课笔记(第二讲): Perceptron-感知机 (台湾国立大学机器学习基石)
  4. Coursera台大机器学习基础课程学习笔记1 – 机器学习定义及PLA算法 - HappyAngel - 博客园



機器學習基石筆記目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET