<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智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 5 -- Training versus Testing 上節課,我們主要介紹了機器學習的可行性。首先,由NFL定理可知,機器學習貌似是不可行的。但是,隨后引入了統計學知識,如果樣本數據足夠大,且hypothesis個數有限,那么機器學習一般就是可行的。本節課將討論機器學習的核心問題,嚴格證明為什么機器可以學習。從上節課最后的問題出發,即當hypothesis的個數是無限多的時候,機器學習的可行性是否仍然成立? ### **一、Recap and Preview** 我們先來看一下基于統計學的機器學習流程圖: ![這里寫圖片描述](https://img.kancloud.cn/fa/18/fa18a3c57289114a93781c2118cd6472_566x265.jpg) 該流程圖中,訓練樣本D和最終測試h的樣本都是來自同一個數據分布,這是機器能夠學習的前提。另外,訓練樣本D應該足夠大,且hypothesis set的個數是有限的,這樣根據霍夫丁不等式,才不會出現Bad Data,保證![](https://img.kancloud.cn/20/fb/20fb42022bbd4be133366b923dd6b2aa_75x14.jpg),即有很好的泛化能力。同時,通過訓練,得到使![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)最小的h,作為模型最終的矩g,g接近于目標函數。 這里,我們總結一下前四節課的主要內容:第一節課,我們介紹了機器學習的定義,目標是找出最好的矩g,使![](https://img.kancloud.cn/4b/16/4b16bbf54db99d8b276a674c2be8f443_41x14.jpg),保證![](https://img.kancloud.cn/ea/81/ea817d25900cc31eb34d4c5550cb8cbf_81x18.jpg);第二節課,我們介紹了如何讓![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg),可以使用PLA、pocket等演算法來實現;第三節課,我們介紹了機器學習的分類,我們的訓練樣本是批量數據(batch),處理監督式(supervised)二元分類(binary classification)問題;第四節課,我們介紹了機器學習的可行性,通過統計學知識,把![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)與![](https://img.kancloud.cn/db/aa/dbaac1c77b617c6873dc31ee9447f5c2_50x18.jpg)聯系起來,證明了在一些條件假設下,![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)成立。 ![這里寫圖片描述](https://img.kancloud.cn/38/16/3816506f5ebb9e22e207608a04183279_566x125.jpg) 這四節課總結下來,我們把機器學習的主要目標分成兩個核心的問題: * ![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg) * ![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)足夠小 上節課介紹的機器學習可行的一個條件是hypothesis set的個數M是有限的,那M跟上面這兩個核心問題有什么聯系呢? 我們先來看一下,當M很小的時候,由上節課介紹的霍夫丁不等式,得到![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg),即能保證第一個核心問題成立。但M很小時,演算法A可以選擇的hypothesis有限,不一定能找到使![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)足夠小的hypothesis,即不能保證第二個核心問題成立。當M很大的時候,同樣由霍夫丁不等式,![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)與![](https://img.kancloud.cn/db/aa/dbaac1c77b617c6873dc31ee9447f5c2_50x18.jpg)的差距可能比較大,第一個核心問題可能不成立。而M很大,使的演算法A的可以選擇的hypothesis就很多,很有可能找到一個hypothesis,使![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)足夠小,第二個核心問題可能成立。 ![這里寫圖片描述](https://img.kancloud.cn/90/98/9098a7938d40da4d46a39fdb30521c80_566x203.jpg) 從上面的分析來看,M的選擇直接影響機器學習兩個核心問題是否滿足,M不能太大也不能太小。那么如果M無限大的時候,是否機器就不可以學習了呢?例如PLA算法中直線是無數條的,但是PLA能夠很好地進行機器學習,這又是為什么呢?如果我們能將無限大的M限定在一個有限的![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)內,問題似乎就解決了。 ### **二、Effective Number of Line** 我們先看一下上節課推導的霍夫丁不等式: 其中,M表示hypothesis的個數。每個hypothesis下的BAD events ![](https://img.kancloud.cn/e2/fa/e2fa61aaaf66c810946f4534d99b47be_23x14.jpg)級聯的形式滿足下列不等式: 當![](https://img.kancloud.cn/78/69/786952cec5b3d077eef22b33630f653c_55x11.jpg)時,上面不等式右邊值將會很大,似乎說明BAD events很大,![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)與![](https://img.kancloud.cn/db/aa/dbaac1c77b617c6873dc31ee9447f5c2_50x18.jpg)也并不接近。但是BAD events ![](https://img.kancloud.cn/e2/fa/e2fa61aaaf66c810946f4534d99b47be_23x14.jpg)級聯的形式實際上是擴大了上界,union bound過大。這種做法假設各個hypothesis之間沒有交集,這是最壞的情況,可是實際上往往不是如此,很多情況下,都是有交集的,也就是說M實際上沒那么大,如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/b6/dd/b6ddeed60f25e9244a9671ac9397466a_205x199.jpg) 也就是說union bound被估計過高了(over-estimating)。所以,我們的目的是找出不同BAD events之間的重疊部分,也就是將無數個hypothesis分成有限個類別。 如何將無數個hypothesis分成有限類呢?我們先來看這樣一個例子,假如平面上用直線將點分開,也就跟PLA一樣。如果平面上只有一個點x1,那么直線的種類有兩種:一種將x1劃為+1,一種將x1劃為-1: ![這里寫圖片描述](https://img.kancloud.cn/f6/38/f638ace87b1bed8733b132c2a553e4e5_464x260.jpg) 如果平面上有兩個點x1、x2,那么直線的種類共4種:x1、x2都為+1,x1、x2都為-1,x1為+1且x2為-1,x1為-1且x2為+1: ![這里寫圖片描述](https://img.kancloud.cn/df/e0/dfe04f0697a6440e80b67746a1d5ad27_403x184.jpg) 如果平面上有三個點x1、x2、x3,那么直線的種類共8種: ![這里寫圖片描述](https://img.kancloud.cn/8a/f6/8af6bed0438df36477e229c5c5dfafdb_448x257.jpg) 但是,在三個點的情況下,也會出現不能用一條直線劃分的情況: ![這里寫圖片描述](https://img.kancloud.cn/0e/41/0e41dc1f09db4545864be0c645e434bd_453x258.jpg) 也就是說,對于平面上三個點,不能保證所有的8個類別都能被一條直線劃分。那如果是四個點x1、x2、x3、x4,我們發現,平面上找不到一條直線能將四個點組成的16個類別完全分開,最多只能分開其中的14類,即直線最多只有14種: ![這里寫圖片描述](https://img.kancloud.cn/dc/8f/dc8ff9796fb72145745fe84fc16b1a47_452x260.jpg) 經過分析,我們得到平面上線的種類是有限的,1個點最多有2種線,2個點最多有4種線,3個點最多有8種線,4個點最多有14(![](https://img.kancloud.cn/73/c6/73c6033a2450ef89ea130608eb576ac9_30x14.jpg))種線等等。我們發現,有效直線的數量總是滿足![](https://img.kancloud.cn/49/bf/49bf3a82ceb23d0fd3ded8720bdcfde5_36x17.jpg),其中,N是點的個數。所以,如果我們可以用effective(N)代替M,霍夫丁不等式可以寫成: 已知effective(N)&lt;![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg),如果能夠保證effective(N)&lt;&lt;![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg),即不等式右邊接近于零,那么即使M無限大,直線的種類也很有限,機器學習也是可能的。 ![這里寫圖片描述](https://img.kancloud.cn/cf/cb/cfcb16c446181b500819c9df2fa8a138_566x310.jpg) ### **三、Effective Number of Hypotheses** 接下來先介紹一個新名詞:二分類(dichotomy)。dichotomy就是將空間中的點(例如二維平面)用一條直線分成正類(藍色o)和負類(紅色x)。令H是將平面上的點用直線分開的所有hypothesis h的集合,dichotomy H與hypotheses H的關系是:hypotheses H是平面上所有直線的集合,個數可能是無限個,而dichotomy H是平面上能將點完全用直線分開的直線種類,它的上界是![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg)。接下來,我們要做的就是嘗試用dichotomy代替M。 ![這里寫圖片描述](https://img.kancloud.cn/d7/b9/d7b9e1d463c6722f47fbe3e5e403b2db_562x247.jpg) 再介紹一個新的名詞:成長函數(growth function),記為![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)。成長函數的定義是:對于由N個點組成的不同集合中,某集合對應的dichotomy最大,那么這個dichotomy值就是![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg),它的上界是![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg): ![這里寫圖片描述](https://img.kancloud.cn/80/0e/800e79e1a553c720362b36546d190ab9_335x47.jpg) 成長函數其實就是我們之前講的effective lines的數量最大值。根據成長函數的定義,二維平面上,![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)隨N的變化關系是: ![這里寫圖片描述](https://img.kancloud.cn/75/3e/753ec1e42fe85f40bc5445732fb5de20_183x184.jpg) 接下來,我們討論如何計算成長函數。先看一個簡單情況,一維的Positive Rays: ![這里寫圖片描述](https://img.kancloud.cn/25/03/2503a3bcf40c57d0568c90a6e855bcfc_501x97.jpg) 若有N個點,則整個區域可分為N+1段,很容易得到其成長函數![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)。注意當N很大時,![](https://img.kancloud.cn/bc/b7/bcb7e11b8a124bd1caf20285fa37ae22_108x18.jpg),這是我們希望看到的。 另一種情況是一維的Positive Intervals: ![這里寫圖片描述](https://img.kancloud.cn/82/4b/824b7ecc6bade8825a9d33595970e992_479x90.jpg) 它的成長函數可以由下面推導得出: ![這里寫圖片描述](https://img.kancloud.cn/df/33/df33d1747f2455b6a50321bdf14f1363_387x168.jpg) 這種情況下,![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg),在N很大的時候,仍然是滿足的。 再來看這個例子,假設在二維空間里,如果hypothesis是凸多邊形或類圓構成的封閉曲線,如下圖所示,左邊是convex的,右邊不是convex的。那么,它的成長函數是多少呢? ![這里寫圖片描述](https://img.kancloud.cn/90/40/90400e1eb7bfe1234fbd3c3d505289de_461x193.jpg) 當數據集D按照如下的凸分布時,我們很容易計算得到它的成長函數![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)。這種情況下,N個點所有可能的分類情況都能夠被hypotheses set覆蓋,我們把這種情形稱為shattered。也就是說,如果能夠找到一個數據分布集,hypotheses set對N個輸入所有的分類情況都做得到,那么它的成長函數就是![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/4c/13/4c13a15caa6ca6447b6342b842fe9d3c_299x266.jpg) ### **四、Break Point** 上一小節,我們介紹了四種不同的成長函數,分別是: ![這里寫圖片描述](https://img.kancloud.cn/23/ec/23ec0eb7ff32ec8505a3464bf03bc5fa_566x112.jpg) 其中,positive rays和positive intervals的成長函數都是polynomial的,如果用![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)代替M的話,這兩種情況是比較好的。而convex sets的成長函數是exponential的,即等于M,并不能保證機器學習的可行性。那么,對于2D perceptrons,它的成長函數究竟是polynomial的還是exponential的呢? 對于2D perceptrons,我們之前分析了3個點,可以做出8種所有的dichotomy,而4個點,就無法做出所有16個點的dichotomy了。所以,我們就把4稱為2D perceptrons的break point(5、6、7等都是break point)。令有k個點,如果k大于等于break point時,它的成長函數一定小于2的k次方。 根據break point的定義,我們知道滿足![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)的k的最小值就是break point。對于我們之前介紹的四種成長函數,他們的break point分別是: ![這里寫圖片描述](https://img.kancloud.cn/c2/65/c2658d95a3fb12fe10a15dfc0d5b184b_566x197.jpg) 通過觀察,我們猜測成長函數可能與break point存在某種關系:對于convex sets,沒有break point,它的成長函數是2的N次方;對于positive rays,break point k=2,它的成長函數是O(N);對于positive intervals,break point k=3,它的成長函數是![](https://img.kancloud.cn/0a/78/0a78a765bb208713fbc741a2b8320f0f_46x18.jpg)。則根據這種推論,我們猜測2D perceptrons,它的成長函數![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg) 。如果成立,那么就可以用![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)代替M,就滿足了機器能夠學習的條件。關于上述猜測的證明,我們下節課再詳細介紹。 ### **五、總結** 本節課,我們更深入地探討了機器學習的可行性。我們把機器學習拆分為兩個核心問題:![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)和![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)。對于第一個問題,我們探討了M個hypothesis到底可以劃分為多少種,也就是成長函數![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg)。并引入了break point的概念,給出了break point的計算方法。下節課,我們將詳細論證對于2D perceptrons,它的成長函數與break point是否存在多項式的關系,如果是這樣,那么機器學習就是可行的。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程。
                  <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>

                              哎呀哎呀视频在线观看