2018年1月26日 星期五

Machine Learning Foundations 作業二 Question 4


台大線上課程的Machine Learning Foundations,作業二的Question 4


如何解這道題目?我們可以寫一支python解這道題目。
如,求Original VC Bound的epsilon (error) 的上限為多少,我們就會定義一個function:

def errorForOriginalVcBound (N, sigma):

然後將數學式子寫成代碼,放進去就好了。但這時候,遇到一個問題,如何用程式表達mH?還記得VC Dimension嗎?:


我們可以將mH(N)換成N^dvc,如此一來,式子就寫成:


於是,我們的function,多了一個參數,叫dvc:

def errorForOriginalVcBound (dvc, N, sigma):

也可以用Python定義一個function叫mH,覆用之。

def mH (N, dvc):
    return math.pow (N, dvc)

Error for Original VC Bound的實作

def errorForOriginalVcBound (dvc, N, sigma):
    value = 4 * mH (2*N, dvc) / sigma
    value = 8 * np.log (value) / N
    value = math.sqrt (value)
    return value

接下來是 Error for Rademacher Penalty Bound的實作,

def errorForRademacherPenaltyBound (dvc, N, sigma):
    value1 = 2 * N * mH (N, dvc)
    value1 = 2 * np.log (value1) / N
    value1 = math.sqrt (value1)

    value2 = (2/N) * np.log (1/sigma)
    value2 = math.sqrt (value2)

    value3 = 1/N

    return value1 + value2 + value3

再來是Error for Parrondo and Van den Broek的實作。但我們發現一個問題,就是公式的左右邊,都有一個epsilon。有兩種解法,

第1種解法,是用一元二次求x解的公式,x就是epsilon:

ax^2 + bx + c = 0

這樣,就可以推導出,只有左邊有epsilon的式子出來。於是,我們就把式子的右邊,寫成代碼即可。這是數學家的作法。

第2種解法,將epsilon當成一個參數。至於要給什麼樣的值,我們可以先觀察其它的式子算出來的結果,再做決定。我選擇第2種解法,於是,Error for Parrondo and Van den Broek的實作如下:

def errorForParrondoAndVanDenBroek (dvc, N, sigma, epsilon):
    value = 6 * mH (2*N, dvc) / sigma
    value = 2 * epsilon + np.log (value)
    value = math.sqrt ((1/N) * value)
    return value

對於Devroye而言,也是公式的左右兩邊,都有一個epsilon。實作的方法與剛才的Parrondo相同:

def errorForDevroye (dvc, N, sigma, epsilon):
    value = np.log (4) + dvc * np.log (N * N) - np.log (epsilon)
    value = 4 * epsilon * (1 + epsilon) + value
    value = (1/(2*N)) * value
    value = math.sqrt (value)
    return value

這裡有一個問題是,為何function的第一行要這麼寫?那是因為當N=10000時,直接計算,數字太大,電腦無法處理。我們可用以用對數運算,將式子拆解成電腦可以處理的單元,如下:



最後是Variant VC Bound的實作:

def errorVariantVcBound (dvc, N, sigma):
    value = 2 * mH (N, dvc)
    value = value / math.sqrt (sigma)
    value = np.log (value)
    value = (16.0 / N) * value
    value = math.sqrt (value)
    return value

所以,我們現在有5個functions,依據題目的順序排列:
errorForOriginalVcBound
errorForRademacherPenaltyBound
errorForParrondoAndVanDenBroek
errorForDevroye
errorVariantVcBound

其中,errorForParrondoAndVanDenBroek和errorForDevroye因為都需要epsilon參數,而我們不知道該給那一個值,所以暫不管它。先求其它3個:

    dvc = 50
    sigma = 0.05
    N = 10000

    value1 = errorForOriginalVcBound (dvc, N, sigma)
    print ("Error for Original VC Bound          = ", value1)
    
    value2 = errorForRademacherPenaltyBound (dvc, N, sigma)
    print ("Error for Rademacher Penalty Bound   = ", value2)
    
    value3 = errorVariantVcBound (dvc, N, sigma)
    print ("Error for Variant VC Bound           = ", value3)



發現最小的值是0.3313。我們可以用這個最小的值,當作是epsilon的參數,用在errorForParrondoAndVanDenBroek和errorForDevroye

    epsilon = min ([value1, value2, value3])
    print ("epsilon = ", epsilon)

    value4 = errorForParrondoAndVanDenBroek (dvc, N, sigma, epsilon)
    print ("Error for Parrondo and Van den Broek = ", value4)

    value5 = errorForDevroye (dvc, N, sigma, epsilon)
    print ("Error for Devroye                    = ", value5)


所以,Devroye公式算出來的值,是最小的。

-Count

Machine Learning Foundations 作業二 Question 10 解法

台大線上課程的Machine Learning Foundations,作業二 Question 10:


這個題目的解答,可以參考網路上這位仁兄所寫的:

我也是先參考這篇文章後,思考了一段時間,才真正了解這道題目的意思。想將自己理解的過程分享大家,故有此文。

在解這道題之前,先了解題目在講什麼?什麼是Simplified Decision Trees?H所代表的是那一種型式的Hypothesis Set?我們很容易被題目裡出現的一大堆不熟悉的數學符號唬住。所以,先了解這些數學符號,才是首要之務。

我們先將d設為2,這樣可以簡化問題,去理解H到底是什麼樣的Hypothesis Set?先看看,這時候,S長什麼樣子?

S a collection of vectors in {0, 1}^2

{0, 1}^2是什麼意思?

請參考WIKI的Cartesian Product (笛卡爾積)


也可以參考 數學指南 實用數學手冊 笛卡爾積 p644, p887, p895

所以:

於是

S a collection of vectors in {0, 1}^2

這句話就是

S a collection of vectors in {(0, 0), (0, 1), (1, 0), (1, 1)}

這又是什麼意思呢?意思是,S的集合裡的元素,是由這4個vector組合而成的:

s1 = (0, 0)
s2 = (0, 1)
s3 = (1, 0)
s4 = (1, 1)

共有幾種這樣的S?這是Power Set的概念,請參考WIKI


所以S共有16種可能。列舉其中幾種可能:

S = empty
S = {s4}
S = {s1, s2}
S = {s1, s3, s4}
S = {s1, s2, s3, s4}

接下來,解釋這個式子:

還是一頭霧水,到底這個式子是在講什麼?有數學式子是這樣寫的嗎?我們把i拆解開來:

因為 d = 2,所以 i = 1, 2。

v1 = [[ x1 > t1 ]]
v2 = [[ x2 > t2 ]]

還好我寫過程式,可以用程式的角度去想,>做的是邏輯運算,若成立,就是1,否則為0。那麼,為何要被 [[ 和 ]] 包圍起來?這是要強調被 [[ 和 ]] 包圍起來,表示裡面是在做邏輯運算,其結果不是1就是0。舉一例:

x = (3, 4)
t = (5, 2)

v1 = [[x1 > t1]] = [[3 > 5]] = 0
v2 = [[x2 > t2]] = [[4 > 2]] = 1

v = (v1, v2) = (0, 1)

所以我們發現,原來

是在做座標轉換。什麼意思?畫圖表示:

接下來,解釋這道式子:

先看看這個意思。

被 [[ 與 ]] 包圍的,就是在做邏輯運算。意思就是,當v屬於S,則為1,否則為0。舉兩個例子:

Case 1:


Case 2:

這樣大家是不是了解H所代表的Hypothesis Set長什麼樣子的吧?其實很簡單,就是當d=2的情況下,以t為中心,將平面切成4個區域:s1, s2, s3, s4

該了解的都了解之後,我們可以開始回答問題本身:

What is the VC-dimension of the "simplified decision trees" hypothesis set?

還是一樣,先看d=2的情況,假設有4個點,p1, p2, p3, p4,是否都可以從H找到h來區分這4個點?


共有16個情況,只列前面8種,是因為將前面的8種,反過來,就是後面的8種。這16種情況,都能從H找到h,區分4個點。如上圖,要滿足第2個情況:(p1, p2, p3, p4) = (+, +, +, -),t要擺在那裡?擺在4個點的中間。S要長什麼樣子?如下:


考慮平面上有5個點:p1, p2, p3, p4, p5

p1 = p2 = p3 = p4 = +1
p5 = -1

因為t只能將平面切成4個部份。所以,第5個點,p5,不管怎麼放,都會和另外1個點處在同一區域。如下圖p2和p5處在同一位置。這樣一下,經過座標轉換,p2和p5就貼在一起,變成(1,0)。可是同一個點,不能同時為+1,與-1,所以這種情況不可能發生。


所以:
d = 2, dvc = 4 = 2^2

t能將三維空間,分為8塊,所以:
d = 3, dvc = 8 = 2^3

然後,d維空間,用數學歸納法,可以得到:  
dvc = 2^d

-Count

2018年1月21日 星期日

人臉識別在無人商店的應用 (Apply Face Recognition in Unmanned Store)

去年2017年,發生了兩件事情:
  1. 2017年蘋果公司推出了iPhoneX,捨棄指紋,改用人臉識別Face ID,造成人臉識別相關應用,突然火紅起來。許多做人臉識別的新創公司,市值也倍速增長。
  2. 2016年,Amazone推出無人商店,Amazone GO。大陸有樣學樣,很快,在2017年中,開始冒出了許多無人商店,其盛況,可比當年2016年共享單車的興起。

這兩件事情,結合在一起,就是「人臉識別在無人商店的應用」。

本篇,從Machine Learning的角度,探討Face Recognition,可以用在無人商店的那些場景。對於客戶而言,無人商店有這4個場景:
  1. 商店知道進店的客戶是誰
  2. 商店能為客戶推銷商品
  3. 客戶能在無店員的情況下,為購買的商品付款
  4. 商店可以根據客戶過往的銷售記錄,給客戶相關折扣
那麼,Face Recognition是否能應用在這4個場景?其實學過台大線上課程的Machine Learning Foundations,或對統計學有基本概念的,應該可以回答這個問題。

Face Recognition和Fingerprint Verification一樣,都是二元分類的問題:


上圖是Fingerprint Verification。f表示我們有一個很明確的方法,可以知道目前這個指紋是不是你的。若是,則輸出為+1,否則為-1。結果只有兩個,不是+1,就是-1,稱為二元分類問題。

可是通常,我們找不到這種很明確的方法。我們會用機器學習的方式,找到一個與f很接近的方法,稱為g,做為驗證指紋或人臉的方法。

用g識別這張臉是不是你的,若是,則輸出為+1,否則為-1。因為g是來自於機器學習的結果,不能完全代表未知的f。大部份情況下,g的預測的結果和f的一致,少部份情況下會不一致。我們將x視為某個fingerprint或是某個face,做進一步分析:
  • g(x) = +1
    • g(x) == f(x) True Positive (TP)
    • g(x) != f(x) False Positive (FP) —> Error
  • g(x) = -1
    • g(x) == f(x) True Negative (TN)
    • g(x) != f(x) False Negative (FN) —> Error

會有以上4個情況,會有兩個型態不同的Error。

True和False,這兩值是從何而來?當預測的g和實際的f一致 g(x) == f(x),則為True,不一致 g(x) != f(x),則為False。

Positive和Negative,這兩值是從何而來?取決於g的結果,+1代表Positive中文稱為陽性,-1代表Negative中文稱為陰性。

為何Positive和Negative無法從f的結果得出?那是因為我們永遠無法找到f。若能找到,就不用機器學習了。

以上4個情況,我們可以整理出一個Confusion Matrix:


這兩種型態不同的Error,稱為False Accept和False Reject:
  • False Accept (False Positive):誤識別
    • 別人的指紋,識別成我的指紋。或我的指紋,識別成別人的指紋
    • 別人的臉,識別成我的臉。或我的臉,識別成別人。如,小孩的臉可以解鎖父母的iPhone X,這種情況時有耳聞。
  • False Reject (False Negative):不識別
    • 系統不認我的指紋。如iPhone的指紋,常常不靈光。
    • 系統不認我的臉。如iPhone X在昏暗的環境下,人臉解鎖的失敗率較高。

然後,根據場景的需要,會有兩種Cost Matrix:

Cost Matrix 1

Cost Matrix 2

Cost Matrix 1 在乎的是 False Accept。如發生False Accept時,Cost設為1000。適用的場景如下:
  • 支付:
    • False Accept發生的機率要很低:若無人商店採用刷臉支付,萬一有一個人刷臉,系統誤識別為我的臉,那麼我就莫明奇妙被扣款。發生這種事情,會對無人商店的品牌信任度造成極大的損失。
    • False Reject發生的機率不用太低:頂多刷臉支付失敗,再刷一次就好了。
    • 手機解鎖:
      • Fase Accept發生的機率要很低:駭客想用指紋登入我的手機,萬一真的被試成功了,我會造成很多損失。
      • False Reject發生的機率不用太低:頂多指紋登入失敗,再按指紋一次就好了。
      Cost Matrix 2 在乎的是 False Reject。如發生False Reject時,Cost設為10。適用的場景如下:
      • 商品推薦
        • False Reject發生的機率要很低:若無人商店根據人臉,為客戶推薦商品。若False Reject機率太高,識別不出客戶,就無法為客戶推薦商品。商店可能會有營收上的損失
        • False Accept發生的機率不用太低:無人商店誤識別人臉為另外一個客戶,為客戶推薦錯誤的商品,這件事情的嚴重性,比識別不出客戶而不推薦任何商品,要來的低。
      • 折扣
        • False Reject發生的機率要很低:若無人商店根據人臉,給客戶折扣。若False Reject機率太高,識別不出客戶,客戶拿不到折扣會不高興。
        • False Accept發生的機率不用太低:無人商店將陌生人臉誤認為另外一個客戶,而給陌生人折扣,這件事情的嚴重性,比識別不出客戶而給任何折扣,要來的低。

      是不是有一個方法讓False Accept和False Reject發生的機率都變小?Face Accept Rate (FAR)和False Reject Rate (FRR)之間的關係,是一個ROC 曲線(Receiver Operating Characteristic Curve):


      FAR = (False Accept) / (True Positive + False Accept)
      FRR = (False Reject) / (True Negative + False Reject)

      若透過Machine Learning找到一個g,它的FAR愈小,FRR就愈大,反之亦然。

      回到客戶在無人商店的4個場景,看看Face Recognition可以應用在那些方面。
      1. 商店知道進店的客戶是誰
      2. 商店能為客戶推銷商品
      3. 客戶能在無店員的情況下,為購買的商品,付款
      4. 商店可以根據客戶過往的銷售記錄,給客戶相關折扣

      1 商店知道進店的客戶是誰

        此場景可以用Face Recognition實現,並且重點在FRR要盡可能小。

        2 商店知道進店的客戶是誰

        此場景可以用Face Recognition實現,並且重點在FRR要盡可能小。

        3 客戶能在無店員的情況下,為購買的商品,付款

        用Face Recognition實現刷臉付款,非常危險,即使FAR可以設非常小,也會有問題。根據2015年FDDB為各家的Face Recognition做ROC分析,發現在FRR<=70%的情況下,FAR可以達1/2845。意思就是2845次刷臉,會有一次出現FAR。若無人商店的註冊人數突破2845,那麼FAR出現的次數就會更頻繁,會造成災難性的結果。

        所以,完全靠刷臉支付,不可行。那我們會想,結果其它的Biometric Authentication,如指紋、虹膜、或聲紋,是否會好一點?這是所謂的Biometric Multi-Factor Authentication,還是會有FAR的問題。另外一個方法是,Biometric Authentication後,要求客戶輸入簡單的PIN碼,但還是有可能,誤識別的客戶,PIN碼剛好和另一個客戶一樣。

        我個人認為,無人商店,在免密支付的過程中,不應該用任何生物識別技術(包含人臉)驗證客戶的身份,做為支付與否的依據。

        4 商店可以根據客戶過往的銷售記錄,給客戶相關折扣

        此場景可以用Face Recognition實現,並且重點在FRR要盡可能小。

        -Count

        2018年1月10日 星期三

        Decision Stump

        台大的線上課程,Machine Learning Foundations,在Effective Number of Hypotheses這一節,有一道問題:



        答案是 (3)。Why?

        坦白講,這道題目剛開始我不是很清楚。 後來了解,"Consider positive and negative rays as H.",這句話的意思,並非指同時有positive ray和negative ray。而是指同一時間,要不就是positive ray,再不然就是negative ray。

        題目了解清楚後,我們就用列舉的方式,N = 2, 3, 4,去找mH(2), mH(3), mH(4)。



        mH (2) = 4



        mH (3) = 6, break point at 3



        mH (4) = 4 x 2 = 8
        上圖只列出x1 = O,這是一半的情況,數量為4。我們可以確定,當x1 = X,數量也是4。所以所有數量加起來就是4+4 = 8

        我們大概可以歸納出 mH (N) = 2N

        -Count

        2017年12月30日 星期六

        Why PLA May Work - Step 4

        上一篇文章提到


        我用Python寫了一支PLA程式,執行結果如下:


        這支程式從w0跑到w7,跑了7次,就找到了wf = w7。我們觀察到:

        wfw0 < wfw1 < … < wfw7 

        數學上,也證明了這個現象:


        我們希望能從這現象,兩個向量的內積愈大,去推論兩個向量就愈靠近。

        wf與wt的向量內積愈大,代表兩件事:
        1. wf與wt之間的夾角愈小
        2. wt的長度愈大 (wf長度固定)

        所以,接下來,我們要證明,PLA,在每次修正錯誤後,Wt的長度變長的幅度,不會太大。

        這裡借用台大的Machine Learning Foundations線上課程裡的一張圖,證明這件事情:


        有了這道式子之後,我們想知道,隨者更正的次數的增加,wt的長度是如何變長的幅度:


        我們發現,隨者t的增加,變長的幅度的上限,是以開根號的型式成長。

        至於wf與wt兩個向量內積成長的幅度為何?


        得知,內積成長的幅度,沒有上限,但不會小於t。

        將這兩個式子擺在一起:


        可以推論,wf與wt之間的夾角,會愈來愈小。也就是wt與wf愈來愈靠近。

        -Count

        2017年12月29日 星期五

        Why PLA May Work - Step 5

        現在要證明PLA是可以停止的。台大的線上課程,Machine Learning Foundations,有證明的過程,但有一部份,是要是讓我們自己去想。還好,網路上,有人寫了完整的證明過程:


        參考他的文章,我整理一下思路。WT是第T次修正的weight。將Wf與WT的單位向量做內積,得到以下結果。


        我們知道,向量的內積,從幾何意義上來看,就是將一個向量,投影在另一個向量,若兩個向量的長度都是1,則投影的長度就是<=1。

        我們想更進一步知道,若PLA若遇到線性可分的資料情況下,T的值,應該是有上限的:


        也就是說,我們希望從兩個單位向量的內積,若能推導到

        T <= 1/C

        就表示T有一個上限。有上限,就表示PLA若遇到線性可分的資料情況,的確是會停止。

        接下來,我們從之前推導的兩個式子:

        Why PLA May Work - Step 4


        求這兩個單位向量的內積的上限:



        下面是推導的過程:



        於是,我們得知,T有上限。就表示PLA若遇到線性可分的資料情況,的確是會停止。

        -Count

        2017年12月26日 星期二

        Why PLA May Work - Step 3

        現在解釋這道式子的由來:


        教材裡,有該式子的推導過程。



        結合上兩篇的文章,應該足以清楚了解


        本篇,再深入了解一下此式子的幾何意義。此式子的左右兩邊是做向量的內積,向量的內積,就是在Wf上的投影,如下圖所示:


        我們觀察到,w2在wf上的投影長度,大於w1在wf上的投影長度。真的是這樣嗎?Why?我們從wt+1是怎麼來的開始推導:


        式子兩邊都對wf做內積:


        我們認為,畫紅線的那一塊,一定是大於零。為何如此肯定?


        那是因為一定會存在離切割線最近的點,投影在wf上的長度,也一定是最小,而且是大於零。


        所以


        我用Python寫了一支程式,跑的結果,也是如此。


        這支程式從w0跑到w4,跑了5次,就找到了wf = w4。我們觀察到:

        w4w0 < w4w1 < w4w2 < w4w3 

        -Count