<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 2 -- Learning to Answer Yes/No 上節課,我們主要簡述了機器學習的定義及其重要性,并用流程圖的形式介紹了機器學習的整個過程:根據模型H,使用演算法A,在訓練樣本D上進行訓練,得到最好的h,其對應的g就是我們最后需要的機器學習的模型函數,一般g接近于目標函數f。本節課將繼續深入探討機器學習問題,介紹感知機Perceptron模型,并推導課程的第一個機器學習算法:Perceptron Learning Algorithm(PLA)。 ### **一、Perceptron Hypothesis Set** 引入這樣一個例子:某銀行要根據用戶的年齡、性別、年收入等情況來判斷是否給該用戶發信用卡。現在有訓練樣本D,即之前用戶的信息和是否發了信用卡。這是一個典型的機器學習問題,我們要根據D,通過A,在H中選擇最好的h,得到g,接近目標函數f,也就是根據先驗知識建立是否給用戶發信用卡的模型。銀行用這個模型對以后用戶進行判斷:發信用卡(+1),不發信用卡(-1)。 在這個機器學習的整個流程中,有一個部分非常重要:就是模型選擇,即Hypothesis Set。選擇什么樣的模型,很大程度上會影響機器學習的效果和表現。下面介紹一個簡單常用的Hypothesis Set:感知機(Perceptron)。 還是剛才銀行是否給用戶發信用卡的例子,我們把用戶的個人信息作為特征向量x,令總共有d個特征,每個特征賦予不同的權重w,表示該特征對輸出(是否發信用卡)的影響有多大。那所有特征的加權和的值與一個設定的閾值threshold進行比較:大于這個閾值,輸出為+1,即發信用卡;小于這個閾值,輸出為-1,即不發信用卡。感知機模型,就是當特征加權和與閾值的差大于或等于0,則輸出h(x)=1;當特征加權和與閾值的差小于0,則輸出h(x)=-1,而我們的目的就是計算出所有權值w和閾值threshold。 ![這里寫圖片描述](https://img.kancloud.cn/e8/26/e82679f70043f98775f195b037d58a5e_566x249.jpg) 為了計算方便,通常我們將閾值threshold當做![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg),引入一個![](https://img.kancloud.cn/e4/57/e457b8c47fcd0d6f885a3c9beab77224_44x15.jpg)的量與![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg)相乘,這樣就把threshold也轉變成了權值![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg),簡化了計算。h(x)的表達式做如下變換: ![這里寫圖片描述](https://img.kancloud.cn/10/68/1068dccf2f081e8e805f0e616dc4c9f0_473x256.jpg) 為了更清晰地說明感知機模型,我們假設Perceptrons在二維平面上,即![](https://img.kancloud.cn/c2/db/c2db453ff702e6c14ef37ae0015f84a9_222x18.jpg)。其中,![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg)是平面上一條分類直線,直線一側是正類(+1),直線另一側是負類(-1)。權重w不同,對應于平面上不同的直線。 ![這里寫圖片描述](https://img.kancloud.cn/1b/0c/1b0ce54959a543cf8cfe78d1b1dfb42f_566x334.jpg) 那么,我們所說的Perceptron,在這個模型上就是一條直線,稱之為linear(binary) classifiers。注意一下,感知器線性分類不限定在二維空間中,在3D中,線性分類用平面表示,在更高維度中,線性分類用超平面表示,即只要是形如![](https://img.kancloud.cn/a7/fe/a7fe91d94da75c9c9149335a4892c9f3_31x14.jpg)的線性模型就都屬于linear(binary) classifiers。 同時,需要注意的是,這里所說的linear(binary) classifiers是用簡單的感知器模型建立的,線性分類問題還可以使用logistic regression來解決,后面將會介紹。 ### **二、Perceptron Learning Algorithm(PLA)** 根據上一部分的介紹,我們已經知道了hypothesis set由許多條直線構成。接下來,我們的目的就是如何設計一個演算法A,來選擇一個最好的直線,能將平面上所有的正類和負類完全分開,也就是找到最好的g,使![](https://img.kancloud.cn/4b/16/4b16bbf54db99d8b276a674c2be8f443_41x14.jpg)。 如何找到這樣一條最好的直線呢?我們可以使用逐點修正的思想,首先在平面上隨意取一條直線,看看哪些點分類錯誤。然后開始對第一個錯誤點就行修正,即變換直線的位置,使這個錯誤點變成分類正確的點。接著,再對第二個、第三個等所有的錯誤分類點就行直線糾正,直到所有的點都完全分類正確了,就得到了最好的直線。這種“逐步修正”,就是PLA思想所在。 ![這里寫圖片描述](https://img.kancloud.cn/8b/bc/8bbcc61cc267a722de85dfb605a2c907_566x241.jpg) 下面介紹一下PLA是怎么做的。首先隨機選擇一條直線進行分類。然后找到第一個分類錯誤的點,如果這個點表示正類,被誤分為負類,即![](https://img.kancloud.cn/7a/05/7a054383aad752b847f73a68958500ea_81x20.jpg),那表示w和x夾角大于90度,其中w是直線的法向量。所以,x被誤分在直線的下側(相對于法向量,法向量的方向即為正類所在的一側),修正的方法就是使w和x夾角小于90度。通常做法是![](https://img.kancloud.cn/d6/65/d665be3422ce639d1cad2cf42c849b21_138x15.jpg),如圖右上角所示,一次或多次更新后的![](https://img.kancloud.cn/f2/14/f214102f9f54b3988bb31ce3957c7bd6_49x14.jpg)與x夾角小于90度,能保證x位于直線的上側,則對誤分為負類的錯誤點完成了直線修正。 同理,如果是誤分為正類的點,即![](https://img.kancloud.cn/8d/f5/8df5b5914671bf1e34e48448bb3ee106_81x20.jpg),那表示w和x夾角小于90度,其中w是直線的法向量。所以,x被誤分在直線的上側,修正的方法就是使w和x夾角大于90度。通常做法是![](https://img.kancloud.cn/18/1b/181be13008f02ac3ff9563fa7c3f99b7_151x15.jpg),如圖右下角所示,一次或多次更新后的![](https://img.kancloud.cn/f2/14/f214102f9f54b3988bb31ce3957c7bd6_49x14.jpg)與x夾角大于90度,能保證x位于直線的下側,則對誤分為正類的錯誤點也完成了直線修正。 按照這種思想,遇到個錯誤點就進行修正,不斷迭代。要注意一點:每次修正直線,可能使之前分類正確的點變成錯誤點,這是可能發生的。但是沒關系,不斷迭代,不斷修正,最終會將所有點完全正確分類(PLA前提是線性可分的)。這種做法的思想是“知錯能改”,有句話形容它:“A fault confessed is half redressed.” 實際操作中,可以一個點一個點地遍歷,發現分類錯誤的點就進行修正,直到所有點全部分類正確。這種被稱為Cyclic PLA。 ![這里寫圖片描述](https://img.kancloud.cn/4f/27/4f27255d913cfd6f7c0314c939e397a2_566x255.jpg) 下面用圖解的形式來介紹PLA的修正過程: ![這里寫圖片描述](https://img.kancloud.cn/f8/9f/f89f2a7ce3aa218205b060358154d5d7_290x286.jpg) ![這里寫圖片描述](https://img.kancloud.cn/82/54/8254791f746ffc7774889886a98957b6_287x288.jpg) ![這里寫圖片描述](https://img.kancloud.cn/1a/25/1a259c5b92ea632a67f9b07a34352146_288x288.jpg) ![這里寫圖片描述](https://img.kancloud.cn/2e/71/2e714d02172cd91eb775f34838e2f99e_286x287.jpg) ![這里寫圖片描述](https://img.kancloud.cn/88/2b/882b1c18738dcb5aea86a55d45af1d9a_287x289.jpg) ![這里寫圖片描述](https://img.kancloud.cn/a8/d0/a8d0d5579b809d6389472f19709944d6_288x286.jpg) ![這里寫圖片描述](https://img.kancloud.cn/fd/11/fd116175679482a8e0dcc79d283680a0_288x286.jpg) ![這里寫圖片描述](https://img.kancloud.cn/c0/39/c0394c06591e98318d79d5eb225bc8c4_285x286.jpg) ![這里寫圖片描述](https://img.kancloud.cn/00/38/0038fd5fa16f2227ac7d3a8064fea4b6_286x287.jpg) ![這里寫圖片描述](https://img.kancloud.cn/b4/c0/b4c0e8da66f0d0707a5b712b798089c1_288x285.jpg) ![這里寫圖片描述](https://img.kancloud.cn/7c/35/7c358eea24102309229c9b3728905f8f_289x286.jpg) 對PLA,我們需要考慮以下兩個問題: * PLA迭代一定會停下來嗎?如果線性不可分怎么辦? * PLA停下來的時候,是否能保證![](https://img.kancloud.cn/83/2a/832a53ad229b01e563aed984b8c326dd_40x14.jpg)?如果沒有停下來,是否有![](https://img.kancloud.cn/83/2a/832a53ad229b01e563aed984b8c326dd_40x14.jpg)? ### **三、Guarantee of PLA** PLA什么時候會停下來呢?根據PLA的定義,當找到一條直線,能將所有平面上的點都分類正確,那么PLA就停止了。要達到這個終止條件,就必須保證D是線性可分(linear separable)。如果是非線性可分的,那么,PLA就不會停止。 ![這里寫圖片描述](https://img.kancloud.cn/5e/95/5e95402ab9f42f22eaaeafa26e2a3ca8_523x177.jpg) 對于線性可分的情況,如果有這樣一條直線,能夠將正類和負類完全分開,令這時候的目標權重為![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg),則對每個點,必然滿足![](https://img.kancloud.cn/61/80/61808d0eded98d89342754dfca27063d_118x20.jpg),即對任一點: ![這里寫圖片描述](https://img.kancloud.cn/03/07/03075146bf346167bc583c0d1067eb14_320x48.jpg) PLA會對每次錯誤的點進行修正,更新權重![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)的值,如果![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)越來越接近,數學運算上就是內積越大,那表示![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)是在接近目標權重![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg),證明PLA是有學習效果的。所以,我們來計算![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)的內積: ![這里寫圖片描述](https://img.kancloud.cn/1a/fc/1afc8d3be43961a827bee1576ad6b353_339x99.jpg) 從推導可以看出,![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)的內積跟![](https://img.kancloud.cn/bb/e5/bbe5423fc318ad75c0f7b29a51328e7e_16x10.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)的內積相比更大了。似乎說明了![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)更接近![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg),但是內積更大,可能是向量長度更大了,不一定是向量間角度更小。所以,下一步,我們還需要證明![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)與![](https://img.kancloud.cn/bb/e5/bbe5423fc318ad75c0f7b29a51328e7e_16x10.jpg)向量長度的關系: ![這里寫圖片描述](https://img.kancloud.cn/c3/4e/c34ef90509830b7e7bde4290a44deb65_566x234.jpg) ![](https://img.kancloud.cn/bb/e5/bbe5423fc318ad75c0f7b29a51328e7e_16x10.jpg)只會在分類錯誤的情況下更新,最終得到的![](https://img.kancloud.cn/6c/b0/6cb00731d82f38de59af78c6b3408f21_47x19.jpg)相比![](https://img.kancloud.cn/bf/f2/bff24dc94529d452f24f699792a3c924_35x18.jpg)的增量值不超過![](https://img.kancloud.cn/ca/d6/cad61f1c8e83c81ca2f5b540836d14e6_66x18.jpg)。也就是說,![](https://img.kancloud.cn/bb/e5/bbe5423fc318ad75c0f7b29a51328e7e_16x10.jpg)的增長被限制了,![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)與![](https://img.kancloud.cn/bb/e5/bbe5423fc318ad75c0f7b29a51328e7e_16x10.jpg)向量長度不會差別太大! 如果令初始權值![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg),那么經過T次錯誤修正后,有如下結論: 下面貼出來該結論的具體推導過程: ![這里寫圖片描述](https://img.kancloud.cn/a8/45/a84534fac40fa8b1a95d0e32aa82fd3f_566x690.jpg) ![這里寫圖片描述](https://img.kancloud.cn/28/0f/280f9914562157b3e5e268d42e817946_566x425.jpg) 上述不等式左邊其實是![](https://img.kancloud.cn/87/af/87af6da2563ae94f02a82a032ddbebdb_21x10.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)夾角的余弦值,隨著T增大,該余弦值越來越接近1,即![](https://img.kancloud.cn/87/af/87af6da2563ae94f02a82a032ddbebdb_21x10.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)越來越接近。同時,需要注意的是,![](https://img.kancloud.cn/f7/2e/f72eae6a9ec03167113651e64f9baac6_128x18.jpg),也就是說,迭代次數T是有上界的。根據以上證明,我們最終得到的結論是:![](https://img.kancloud.cn/01/3a/013af0cb47ecfaf09604ffe261c4c2e4_30x11.jpg)與![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)的是隨著迭代次數增加,逐漸接近的。而且,PLA最終會停下來(因為T有上界),實現對線性可分的數據集完全分類。 ### **四、Non-Separable Data** 上一部分,我們證明了線性可分的情況下,PLA是可以停下來并正確分類的,但對于非線性可分的情況,![](https://img.kancloud.cn/6f/63/6f6357ddb49b501b1c2d3fdc8ad4ae50_19x12.jpg)實際上并不存在,那么之前的推導并不成立,PLA不一定會停下來。所以,PLA雖然實現簡單,但也有缺點: ![這里寫圖片描述](https://img.kancloud.cn/10/38/1038ca0146df1f2a208b5b85d00737c8_566x201.jpg) 對于非線性可分的情況,我們可以把它當成是數據集D中摻雜了一下noise,事實上,大多數情況下我們遇到的D,都或多或少地摻雜了noise。這時,機器學習流程是這樣的: ![這里寫圖片描述](https://img.kancloud.cn/ef/af/efaf6c7b34b9bec90b0c3d0ac6fb977a_562x267.jpg) 在非線性情況下,我們可以把條件放松,即不苛求每個點都分類正確,而是容忍有錯誤點,取錯誤點的個數最少時的權重w: ![這里寫圖片描述](https://img.kancloud.cn/5b/ac/5bacf29664be7572e4664f999f526598_566x198.jpg) 事實證明,上面的解是NP-hard問題,難以求解。然而,我們可以對在線性可分類型中表現很好的PLA做個修改,把它應用到非線性可分類型中,獲得近似最好的g。 修改后的PLA稱為Packet Algorithm。它的算法流程與PLA基本類似,首先初始化權重![](https://img.kancloud.cn/63/a9/63a9ea9b3d4d11d88fb6223985211c0a_18x10.jpg),計算出在這條初始化的直線中,分類錯誤點的個數。然后對錯誤點進行修正,更新w,得到一條新的直線,在計算其對應的分類錯誤的點的個數,并與之前錯誤點個數比較,取個數較小的直線作為我們當前選擇的分類直線。之后,再經過n次迭代,不斷比較當前分類錯誤點個數與之前最少的錯誤點個數比較,選擇最小的值保存。直到迭代次數完成后,選取個數最少的直線對應的w,即為我們最終想要得到的權重值。 ![這里寫圖片描述](https://img.kancloud.cn/3f/07/3f077237bd1ab311bf0f1315e6f09c41_566x237.jpg) 如何判斷數據集D是不是線性可分?對于二維數據來說,通常還是通過肉眼觀察來判斷的。一般情況下,Pocket Algorithm要比PLA速度慢一些。 ### **五、總結** 本節課主要介紹了線性感知機模型,以及解決這類感知機分類問題的簡單算法:PLA。我們詳細證明了對于線性可分問題,PLA可以停下來并實現完全正確分類。對于不是線性可分的問題,可以使用PLA的修正算法Pocket Algorithm來解決。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看