<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 7 -- The VC Dimension 前幾節課著重介紹了機器能夠學習的條件并做了詳細的推導和解釋。機器能夠學習必須滿足兩個條件: * **假設空間H的Size M是有限的,即當N足夠大的時候,那么對于假設空間中任意一個假設g,![](https://img.kancloud.cn/6f/c7/6fc7702fbf9cb862010777554e97d82d_74x14.jpg)**。 * **利用算法A從假設空間H中,挑選一個g,使![](https://img.kancloud.cn/2a/52/2a52bca567910bf4798b98fe89451c0b_75x18.jpg),則![](https://img.kancloud.cn/b5/5d/b55d5ca372ae52bf9eb7f9b2ea722cc5_59x15.jpg)**。 這兩個條件,正好對應著test和trian兩個過程。train的目的是使損失期望![](https://img.kancloud.cn/2a/52/2a52bca567910bf4798b98fe89451c0b_75x18.jpg);test的目的是使將算法用到新的樣本時的損失期望也盡可能小,即![](https://img.kancloud.cn/b5/5d/b55d5ca372ae52bf9eb7f9b2ea722cc5_59x15.jpg)。 正因為如此,上次課引入了break point,并推導出只要break point存在,則M有上界,一定存在![](https://img.kancloud.cn/6f/c7/6fc7702fbf9cb862010777554e97d82d_74x14.jpg)。 本次筆記主要介紹VC Dimension的概念。同時也是總結VC Dimension與![](https://img.kancloud.cn/2a/52/2a52bca567910bf4798b98fe89451c0b_75x18.jpg),![](https://img.kancloud.cn/b5/5d/b55d5ca372ae52bf9eb7f9b2ea722cc5_59x15.jpg),Model Complexity Penalty(下面會講到)的關系。 ### **一、Definition of VC Dimension** 首先,我們知道如果一個假設空間H有break point k,那么它的成長函數是有界的,它的上界稱為Bound function。根據數學歸納法,Bound function也是有界的,且上界為![](https://img.kancloud.cn/04/17/0417697c19243c90db65bf43fcf83ba3_35x14.jpg)。從下面的表格可以看出,![](https://img.kancloud.cn/b6/ad/b6ad57c08daa830a956af3f1f88ba6a6_64x18.jpg)比B(N,k)松弛很多。 ![這里寫圖片描述](https://img.kancloud.cn/af/53/af5361f15c0c0acede9e5b3db15a98f8_566x367.jpg) 則根據上一節課的推導,VC bound就可以轉換為: ![這里寫圖片描述](https://img.kancloud.cn/b9/8d/b98df90d1b006cbc1646ef61a0858515_566x201.jpg) 這樣,不等式只與k和N相關了,一般情況下樣本N足夠大,所以我們只考慮k值。有如下結論: * **若假設空間H有break point k,且N足夠大,則根據VC bound理論,算法有良好的泛化能力** * **在假設空間中選擇一個矩g,使![](https://img.kancloud.cn/c9/38/c938ce5f2a3f7dfb47848be0e1a75bfc_54x15.jpg),則其在全集數據中的錯誤率會較低** ![這里寫圖片描述](https://img.kancloud.cn/cc/e7/cce71828ea8d92819c1f378792decf08_463x160.jpg) 下面介紹一個新的名詞:VC Dimension。VC Dimension就是某假設集H能夠shatter的最多inputs的個數,即最大完全正確的分類能力。(注意,只要存在一種分布的inputs能夠正確分類也滿足)。 shatter的英文意思是“粉碎”,也就是說對于inputs的所有情況都能列舉出來。例如對N個輸入,如果能夠將![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg)種情況都列出來,則稱該N個輸入能夠被假設集H shatter。 根據之前break point的定義:假設集不能被shatter任何分布類型的inputs的最少個數。則VC Dimension等于break point的個數減一。 ![這里寫圖片描述](https://img.kancloud.cn/a4/44/a444a6249aadee137d37d252918b612e_566x158.jpg) 現在,我們回顧一下之前介紹的四種例子,它們對應的VC Dimension是多少: ![這里寫圖片描述](https://img.kancloud.cn/fa/3e/fa3e8b3229dfe2c5c399185a83037f2a_566x283.jpg) 用![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)代替k,那么VC bound的問題也就轉換為與![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)和N相關了。同時,如果一個假設集H的![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)確定了,則就能滿足機器能夠學習的第一個條件![](https://img.kancloud.cn/6f/c7/6fc7702fbf9cb862010777554e97d82d_74x14.jpg),與算法、樣本數據分布和目標函數都沒有關系。 ![這里寫圖片描述](https://img.kancloud.cn/28/09/280941f25127675742e8ebddfb9e97de_566x371.jpg) ### **二、VC Dimension of Perceptrons** 回顧一下我們之前介紹的2D下的PLA算法,已知Perceptrons的k=4,即![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)。根據VC Bound理論,當N足夠大的時候,![](https://img.kancloud.cn/50/e2/50e2bb0d06a95c58783b164099430e42_116x18.jpg)。如果找到一個g,使![](https://img.kancloud.cn/2a/52/2a52bca567910bf4798b98fe89451c0b_75x18.jpg),那么就能證明PLA是可以學習的。 ![這里寫圖片描述](https://img.kancloud.cn/df/98/df98132c30b0e472fd26e80205911cb6_566x266.jpg) 這是在2D情況下,那如果是多維的Perceptron,它對應的![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)又等于多少呢? 已知在1D Perceptron,![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg),在2D Perceptrons,![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg),那么我們有如下假設:![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg),其中d為維數。 要證明的話,只需分兩步證明: * ![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg) * ![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg) ![這里寫圖片描述](https://img.kancloud.cn/19/7f/197f69c54dcc451c1532a364feaf4f8c_566x167.jpg) 首先證明第一個不等式:![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)。 在d維里,我們只要找到某一類的d+1個inputs可以被shatter的話,那么必然得到![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)。所以,我們有意構造一個d維的矩陣![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)能夠被shatter就行。![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)是d維的,有d+1個inputs,每個inputs加上第零個維度的常數項1,得到![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)的矩陣: ![這里寫圖片描述](https://img.kancloud.cn/ee/34/ee3465d8665b213e106fee86e4cb3d26_468x145.jpg) 矩陣中,每一行代表一個inputs,每個inputs是d+1維的,共有d+1個inputs。這里構造的![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)很明顯是可逆的。shatter的本質是假設空間H對![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)的所有情況的判斷都是對的,即總能找到權重W,滿足![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg),![](https://img.kancloud.cn/5d/ab/5dabc86a86bc0afd53543923f0e843bc_93x17.jpg)。由于這里我們構造的矩陣![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)的逆矩陣存在,那么d維的所有inputs都能被shatter,也就證明了第一個不等式。 ![這里寫圖片描述](https://img.kancloud.cn/72/a5/72a5ac54ac09d8b0143372f6a699f719_566x302.jpg) 然后證明第二個不等式:![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)。 在d維里,如果對于任何的d+2個inputs,一定不能被shatter,則不等式成立。我們構造一個任意的矩陣![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg),其包含d+2個inputs,該矩陣有d+1列,d+2行。這d+2個向量的某一列一定可以被另外d+1個向量線性表示,例如對于向量![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg),可表示為: 其中,假設![](https://img.kancloud.cn/93/ee/93ee6e7f66efc2a4d3276654ccd881b6_45x16.jpg),![](https://img.kancloud.cn/e3/f5/e3f570aed227454a626c531f1e0f3ae5_99x15.jpg). 那么如果![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)是正類,![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)均為負類,則存在![](https://img.kancloud.cn/6c/33/6c3386bfed4a0e9bb0cbf3c66b17e360_18x11.jpg),得到如下表達式: ![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)&lt;font color="#0000ff"&gt;![](https://img.kancloud.cn/2a/23/2a2347e92679cbbf5b897a826b3bda0c_84x15.jpg)&lt;/font&gt;+&lt;font color="#ff0000"&gt;![](https://img.kancloud.cn/9b/5a/9b5a7106d19546d5171ad65a6fbb1af3_84x14.jpg)&lt;/font&gt;+![](https://img.kancloud.cn/6b/f4/6bf4ff6e9d6d768b53448e2dbb3052d7_18x2.jpg)+&lt;font color="#ff0000"&gt;![](https://img.kancloud.cn/5d/e3/5de355165e7b77de68a628cf852d2a7a_85x14.jpg)&lt;/font&gt;![](https://img.kancloud.cn/e7/02/e702e9265a102524811ca04f38a974e3_24x12.jpg) 因為其中藍色項大于0,代表正類;紅色項小于0,代表負類。所有對于這種情況,![](https://img.kancloud.cn/05/c5/05c53b7e8ec04c22aa581501549a824c_14x11.jpg)一定是正類,無法得到負類的情況。也就是說,d+2個inputs無法被shatter。證明完畢! ![這里寫圖片描述](https://img.kancloud.cn/6f/34/6f343dca66652421b308bcd44198c861_566x322.jpg) 綜上證明可得![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)。 ### **三、Physical Intuition VC Dimension** ![這里寫圖片描述](https://img.kancloud.cn/3c/6e/3c6e9c31e47c616be3ecba2551d25990_566x414.jpg) 上節公式中![](https://img.kancloud.cn/6c/33/6c3386bfed4a0e9bb0cbf3c66b17e360_18x11.jpg)又名features,即自由度。自由度是可以任意調節的,如同上圖中的旋鈕一樣,可以調節。VC Dimension代表了假設空間的分類能力,即反映了H的自由度,產生dichotomy的數量,也就等于features的個數,但也不是絕對的。 ![這里寫圖片描述](https://img.kancloud.cn/73/15/7315f5e1bb5b6d59e0195afcd5a41d37_566x95.jpg) 例如,對2D Perceptrons,線性分類,![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg),則![](https://img.kancloud.cn/6c/33/6c3386bfed4a0e9bb0cbf3c66b17e360_18x11.jpg),也就是說只要3個features就可以進行學習,自由度為3。 介紹到這,我們發現M與![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)是成正比的,從而得到如下結論: ![這里寫圖片描述](https://img.kancloud.cn/b6/91/b6911806b7d87580b52253215ad36bec_566x363.jpg) ### **四、Interpreting VC Dimension** 下面,我們將更深入地探討VC Dimension的意義。首先,把VC Bound重新寫到這里: ![這里寫圖片描述](https://img.kancloud.cn/7e/c8/7ec8379d5bf346388dd07a7276b59ff1_566x113.jpg) 根據之前的泛化不等式,如果![](https://img.kancloud.cn/56/25/5625b9fcd4d5ea19e62211aa15147269_111x17.jpg),即出現bad壞的情況的概率最大不超過![](https://img.kancloud.cn/91/2b/912be982bb55f94f143f9c67b9652fcb_8x11.jpg)。那么反過來,對于good好的情況發生的概率最小為![](https://img.kancloud.cn/04/3b/043ba9ce4e371d94aa40db0784f36fdf_35x13.jpg),則對上述不等式進行重新推導: ![這里寫圖片描述](https://img.kancloud.cn/7e/85/7e85ef6072ceccda33db8160b024e200_566x234.jpg) ![](https://img.kancloud.cn/7b/0c/7b0cf84156a1f54329998fc4b798125b_7x7.jpg)表現了假設空間H的泛化能力,![](https://img.kancloud.cn/7b/0c/7b0cf84156a1f54329998fc4b798125b_7x7.jpg)越小,泛化能力越大。 ![這里寫圖片描述](https://img.kancloud.cn/9f/e6/9fe69a15e82fbee47015a6ee1d76692a_566x370.jpg) 至此,已經推導出泛化誤差![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)的邊界,因為我們更關心其上界(![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)可能的最大值),即: ![這里寫圖片描述](https://img.kancloud.cn/18/cc/18ccf7147d6d57edaaf207d2d1a43bf4_566x116.jpg) 上述不等式的右邊第二項稱為模型復雜度,其模型復雜度與樣本數量N、假設空間H(![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg))、![](https://img.kancloud.cn/7b/0c/7b0cf84156a1f54329998fc4b798125b_7x7.jpg)有關。![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)由![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)共同決定。下面繪出![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)、model complexity、![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)隨![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)變化的關系: ![這里寫圖片描述](https://img.kancloud.cn/20/3b/203b59ebcfb561df194e14b619a0569f_566x240.jpg) 通過該圖可以得出如下結論: * **![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)越大,![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)越小,![](https://img.kancloud.cn/b1/34/b134b0391e5f0b33dbc4456fe5c2dacb_11x11.jpg)越大(復雜)**。 * **![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)越小,![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)越大,![](https://img.kancloud.cn/b1/34/b134b0391e5f0b33dbc4456fe5c2dacb_11x11.jpg)越小(簡單)**。 * **隨著![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)增大,![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)會先減小再增大**。 所以,為了得到最小的![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg),不能一味地增大![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)以減小![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg),因為![](https://img.kancloud.cn/5b/cf/5bcf9eebe555c8380ea4c84aea710839_23x14.jpg)太小的時候,模型復雜度會增加,造成![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)變大。也就是說,選擇合適的![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg),選擇的features個數要合適。 下面介紹一個概念:樣本復雜度(Sample Complexity)。如果選定![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg),樣本數據D選擇多少合適呢?通過下面一個例子可以幫助我們理解: ![這里寫圖片描述](https://img.kancloud.cn/20/46/204663f79d68fe16d2fa214da893345d_566x148.jpg) 通過計算得到N=29300,剛好滿足![](https://img.kancloud.cn/91/2b/912be982bb55f94f143f9c67b9652fcb_8x11.jpg)的條件。N大約是![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)的10000倍。這個數值太大了,實際中往往不需要這么多的樣本數量,大概只需要![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)的10倍就夠了。N的理論值之所以這么大是因為VC Bound 過于寬松了,我們得到的是一個比實際大得多的上界。 ![這里寫圖片描述](https://img.kancloud.cn/47/a3/47a3cc0704e5c1e4e0faf1ea8d4201ec_566x316.jpg) 值得一提的是,VC Bound是比較寬松的,而如何收緊它卻不是那么容易,這也是機器學習的一大難題。但是,令人欣慰的一點是,VC Bound基本上對所有模型的寬松程度是基本一致的,所以,不同模型之間還是可以橫向比較。從而,VC Bound寬松對機器學習的可行性還是沒有太大影響。 ### **五、總結** 本節課主要介紹了VC Dimension的概念就是最大的non-break point。然后,我們得到了Perceptrons在d維度下的VC Dimension是d+1。接著,我們在物理意義上,將![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)與自由度聯系起來。最終得出結論![](https://img.kancloud.cn/41/9b/419b70437d3439ec7d5302bf12e03e34_21x14.jpg)不能過大也不能過小。選取合適的值,才能讓![](https://img.kancloud.cn/dd/0f/dd0f9962b91f91dfa644b8d9c6d853d2_29x14.jpg)足夠小,使假設空間H具有良好的泛化能力。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
                  <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>

                              哎呀哎呀视频在线观看