Try   HackMD

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

上週回顧

上週課程提到,在機器學習中存在一個 Learning Algorithm

A 與一個假說集合 Hypothesis Set
H
A
在觀察餵入的資料集合
D
後,會從假說集合挑選一個最符合的
g
,這個
g
會在最後應用階段時,被使用來進行分類。

本週延續上週核發信用卡的例子,發不發卡是一個二元分類問題,使用者資料

x 最終經由
g
後,會得到
y
,也就是 Yes(發卡)或 No(不發卡)結果。

感知器 Perceptron

開始上課前,我先岔開查了感知器(Perceptron) 這個詞所代表的意思與定義。

感知器這個名詞緣起於類神經網路時期,這個演算法的概念跟真實的生物神經元傳遞訊號的機制類似。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
神經元結構(圖片來源: CarlXie-CSDN博客

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

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

Perceptron Hypothesis Set

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

X={x1,x,2,...,xd}

銀行會對每個條件進行評分,也就是依照每個條件的正/負相關性給予給與權重,例如:年收入的權重給予 1,負債的權重給予 -1等。而權重也可以用向量來表示:

W={w1,w2,...,wd}

而銀行唯有當這些條件的總分,超過門檻值(threshold ,

T)時,才會核發信用卡:

score=i=1dwixi,and{score>T, approvescore<T, rejectscore=0, ignored

我們將其輸出

y 的結果集合使用符號來表示,可稱為Label,可表示為
y={+1(approve),1(reject)}
, 0 ignored,因此式子可簡化成:

h(x)=sign(i=1dwixiT), where h(x)H

其中

sign(x)={+1, x>01, x<0


為簡化數學式的表示,可針對數學符號再做進一步的化簡:

h(x)=sign(i=1dwixiT)=sign(i=1dwixi+(T)w0×(+1)x0)=sign(i=0dwixi)=sign(WTX)

個人經驗雖然兩者意義上相同,但在實務上偏向使用矩陣運算,因為矩陣運算的可以藉由 GPU 使用 CUDA 來加速。

Perceptrons in
R2

為可視化,我們將感知器使用在二維平面上,即表示只使用兩種條件,例如:年收入與負債兩種,若使用越多條件會映射到更高維度的空間。

因此

h(x) 可表示成
sign(w0+w1x1+w2x2)
,因為
sign
是以 0 為分界線的函數,因此可設
w0+w1x1+w2x2=0
,該式恰是一條直線方程式,而不同權重
W
會對應到不同的直線。

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Perceptrons in R^2(圖片來源: 課程截圖

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

Perceptron Learning Algorithm (PLA)

在上一節中,我們可得知感知器中 Hypothesis Set 的所有可能集合

H,也就是平面上所有的直線。一旦有了
D
H
後,我們就可以藉由機器學習演算法來挑選最適合的線段。

何謂最適合的線段?

之前提過,機器在觀察餵入的資料會從 Hypothesis Set

H 中學到一函數 Hypothesis
g
,期望上我們希望
g
越接近 Target function
f
越好。但之前也提過,我們並不知曉
f
到底長怎樣。因此實做時根本不可能與
f
相互比較。

但我們可使用餵入的資料來協助找到最好的

g ,先忽略錯誤標記及存在雜訊的情況下,我們可以假設所輸入的資料
x
在經由
f(x)
後,可以得到一輸出結果
y
。 如果我們可以從
H
中找到一條
g
,對每個點其輸出結果與
f
完全一致,我們則認為
g
是個不錯的結果。

因此在這邊對於合適線段的定義應該是,找到一條只直線

g ,使資料集中所有點的分類結果與本身的 Label 一致

如何找到最適合的線段?

若在 Hypothesis Set

H 不大的情況下,可以每條線段逐一檢查。但在平面上的線段是無窮多的,根本不可能一一檢查。

因此這邊採用逐漸修正的方式,在取得一條初始線段

g0 的情況下,經過不斷的錯誤修正,對線段進行平移旋轉等操作,最終能找到一條
gf
,這就是 Perceptron Learning Algorithm (PLA) 演算法的核心。

提醒

W 其實是直線方程的法向量

PLA 演算法

具體演算法流程如下:

  1. 初始化權重
    W
    W0
    ,設定
    W0
    = 0
  2. 按序或隨機遍歷所有資料,也就是二維平面上所有的點,找出分類結果與真實標籤不符的資料:
    1. 若存在,則更新權重
      W
      後,重新執行步驟二。
    2. 若不存在,停止執行。

其中,我們將所找到分類結果的資料標記為

(Xn(t),Yn(t)) ,而權重更新公式如下:

Wt+1Wt+Yn(t)Xn(t)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
向量修正(圖片來源: 課程截圖

如果

sign()=1,但是
y=+1
,也就是说
W
X
的夾角過大,需要使
W
X
靠攏,即左圖。

如果

sign()=+1,但是
y=1
,也就是说
W
X
的夾角過小,需要使
W
X
遠離,即右圖。

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

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

Guarantee of PLA

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
線性可分(圖片來源: 課程截圖

[證明] PLA 會停止運行

TODO: 證明改成英文的, LaTeX 搭中文好醜
  1. 評估

    Wt+1
    Wt
    Wf
    的相近程度

    D
    為線性可分
    必存在一條直線其法向量為
    Wf
    ,使
    D
    中所有點皆符合
    Yn=sign(WfTXn)


    已知存在一條法向量為
    Wf
    的直線且
    Yn=sign(WfTXn)

    可知平面上任一點皆與法向量為
    Wf
    的直線存在一定距離
    故推知
    YnWfTXn>0
    min(YnWfTXn)>0


    在運行
    t
    次時,存在一個分類錯誤的點
    (Xn(t),Yn(t))

    (Xn(t),Yn(t))D

    可推知
    Yn(t)WfTXn(t) min(YnWfTXn)>0


    為評估

    Wf
    Wt+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

    可得

    WfTWt+1>WfTWt ,向量內積隨執行次數增加而增加。

  2. 向量內積的增長可能原因有二:向量長度增加或向量夾縮小。為排除向量長度增長對向量內積增加的影響,進行下列證明:

    在運行
    t
    次時,存在一個分類錯誤的點
    (Xn(t),Yn(t))
    ,使的
    sign(WtT,Xn(t))Yn(t)

    可推知
    Yn(t)(WtT,Xn(t))0


    已知
    Wt+1Wt+Yn(t)Xn(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

    可得

    Wt+12Wt2+maxXn(t)2 ,證明在運行中向量長度增加緩慢

  3. 證明隨執行次數增加而

    Wt+1
    Wf
    逐漸靠近
    已知向量內積公式為
    ab=|a||b|cosθ

    又從(1)中得知,向量內積隨執行次數增加而增加
    又從(2)中得知,在運行中向量長度增加緩慢
    向量內積的增加,為
    cosθ
    增加所導致
    證明隨執行次數增加而
    Wt+1
    Wf
    逐漸靠近

  4. 證明PLA會停止
    設定初始向量為

    W0=0,從 0 開始進行
    T
    次迭代

    由(2)推知:

    WT2WT12+maxXn2WT22+maxXn2+maxXn2W02+TmaxXn2TmaxXn2 W0=0

    由(1)推知:

    WfTWTWfTWT1+min(YnWfTXn)WfTWT2+min(YnWfTXn)+min(YnWfTXn)WfTW0+Tmin(YnWfTXn)Tmin(YnWfTXn)

    結合上述兩結論,可得

    WfTWfWTWTTmin(YnWfTXn)Wf∥∥WTTmin(YnWfTXn)WfTmaxXn(t)2Tmin(YnWfTXn)WfmaxXn(t)Tmin(YnWfTXn)WfmaxXn(t)TC,C=min(YnWfTXn)WfmaxXn(t)

    已知內積中正規化後,乘積最多為 1
    故可得

    1WfTWfWTWTTmin(YnWfTXn)WfmaxXn(t)

    化簡後

    R2ρ2=Wf2maxXn(t)2min(YnWfTXn)2T

    其中

    R2=maxXn(t)2ρ2=min(YnWfTWfXn)

    從最後一條式子看來T是有上限的,因此在線性可分的情況下,PLA 最終會停止

Non-Separable Data

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

另一種情況是

f 產生的資料本身是線性可分,但因雜訊(noise)、輸入錯誤等因素,最終產生出線性不可分的資料,也會使得 PLA 無法停止。

為避免無窮迴圈的情況發生,因此我們退而求其次,不找不犯錯的線,改找犯錯最少的線:

Wg=argminn=1N(Ynsign(WTXn)

但此類問題已經被證實是一個 NP-hard 問題,不可能找到最佳解,只能找到近似解。

這邊提出了一個近似的演算法 Pocket,它本質是一個貪婪演算法,屬於 PLA 演算法的變形,演算法如下:

  1. 初始化權重

    W
    W0
    ,設定
    W0
    = 0

  2. 隨機遍歷所有資料,找出分類結果與真實標籤不符的資料:

    1. 若存在,則更新
      W
      後,並統計新線段存在的錯誤點數。若總數小於所記錄,則更新記錄與對應權重。
    2. 若不存在,停止執行。
  3. 執行前,請先設定中止條件,如:執行次數、錯誤點少於多少時停止等。

課堂測驗

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

[ ] 1. coffee, tea, hamburger, steak
[V] 2. free, drug, fantastic, deal
[ ] 3. machine, learning, statistics, textbook
[ ] 4. national, Taiwan, university, coursera


Q2 . Let

n=n(t), according to the rule of PLA below, which formula is true?
sign(wtTxn)yn, and , ,wt+1wt+ynxn

[ ] 1.

wt+1Txn=yn
[ ] 2.
sign(wt+1Txn)=yn

[V] 3.
ynwt+1TxnynwtTxn

[ ] 4.
ynwt+1Txn<ynwtTxn


Q3 . Define

R2=maxnxn2 ,
ρ=minnynwfTxfxn
. We want to show that
T
. Express the upper bound
by the two terms above.

[ ] 1.

R/ρ
[V] 2.
R2/ρ2

[ ] 3.
R/ρ2

[ ] 4.
ρ2/R2


Q4 .Since we do not know whether

D is linear separable in advance, we may decide to just go with pocket instead of PLA. If
D
is actually linear separable, what's the difference between the two?

[V] 1. pocket on

D is slower than PLA
[ ] 2. pocket on
D
is faster than PLA
[ ] 3. pocket on
D
returns a better
g
in approximating ff than PLA
[ ] 4. pocket on
D
returns a worse
g
in approximating ff than PLA

其他連結

  1. 機器學習基石筆記目錄

參考資料

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

參考筆記

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



本文作者:辛西亞.Cynthia
網站連結辛西亞的技能樹 / hackmd 版本
版權聲明:部落格中所有文章,均採用 CC BY-NC-SA 4.0 許可協議。轉載請標明作者、連結與出處!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →