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

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 6 -- Theory of Generalization 上一節課,我們主要探討了當M的數值大小對機器學習的影響。如果M很大,那么就不能保證機器學習有很好的泛化能力,所以問題轉換為驗證M有限,即最好是按照多項式成長。然后通過引入了成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)和dichotomy以及break point的概念,提出2D perceptrons的成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)是多項式級別的猜想。這就是本節課將要深入探討和證明的內容。 ### **一、Restriction of Break Point** 我們先回顧一下上節課的內容,四種成長函數與break point的關系: ![這里寫圖片描述](https://img.kancloud.cn/ef/70/ef7059b80a060dee27473d8dae99a10d_566x255.jpg) 下面引入一個例子,如果k=2,那么當N取不同值的時候,計算其成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)是多少。很明顯,當N=1時,![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)=2,;當N=2時,由break point為2可知,任意兩點都不能被shattered(shatter的意思是對N個點,能夠分解為![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg)種dichotomies);![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)最大值只能是3;當N=3時,簡單繪圖分析可得其![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg),即最多只有4種dichotomies。 ![這里寫圖片描述](https://img.kancloud.cn/0c/88/0c88b2335d3f1173a19fe5195b886102_566x183.jpg) 所以,我們發現當N&gt;k時,break point限制了![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)值的大小,也就是說影響成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的因素主要有兩個: * 抽樣數據集N * break point k(這個變量確定了假設的類型) 那么,如果給定N和k,能夠證明其![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的最大值的上界是多項式的,則根據霍夫丁不等式,就能用![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)代替M,得到機器學習是可行的。所以,證明![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界是poly(N),是我們的目標。 ![這里寫圖片描述](https://img.kancloud.cn/0d/c9/0dc97b6fdcf7a4a14c9d5c6e614826c2_384x93.jpg) ### **二、Bounding Function: Basic Cases** 現在,我們引入一個新的函數:bounding function,B(N,k)。Bound Function指的是當break point為k的時候,成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)可能的最大值。也就是說B(N,k)是![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界,對應![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)最多有多少種dichotomy。那么,我們新的目標就是證明: 這里值得一提的是,B(N,k)的引入不考慮是1D postive intrervals問題還是2D perceptrons問題,而只關心成長函數的上界是多少,從而簡化了問題的復雜度。 ![這里寫圖片描述](https://img.kancloud.cn/cc/5b/cc5b71d65f85ae77c3d76a6306983714_566x216.jpg) 求解B(N,k)的過程十分巧妙: * 當k=1時,B(N,1)恒為1。 * 當N &lt; k時,根據break point的定義,很容易得到![](https://img.kancloud.cn/64/5c/645c90e6a643c7c2f5602d3a2790c993_97x18.jpg)。 * 當N = k時,此時N是第一次出現不能被shatter的值,所以最多只能有![](https://img.kancloud.cn/5a/f8/5af8688894f120bdcab8768507fdff02_19x14.jpg)個dichotomies,則![](https://img.kancloud.cn/64/5c/645c90e6a643c7c2f5602d3a2790c993_97x18.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/d1/39/d139afd0e51b1af4c1ff16990f3f491f_566x221.jpg) 到此,bounding function的表格已經填了一半了,對于最常見的N&gt;k的情況比較復雜,推導過程下一小節再詳細介紹。 ### **三、Bounding Function: Inductive Cases** N &gt; k的情況較為復雜,下面給出推導過程: 以B(4,3)為例,首先想著能否構建B(4,3)與B(3,x)之間的關系。 首先,把B(4,3)所有情況寫下來,共有11組。也就是說再加一種dichotomy,任意三點都能被shattered,11是極限。 ![這里寫圖片描述](https://img.kancloud.cn/3c/6d/3c6de6609f96cebdb500d845bd29f6af_224x285.jpg) 對這11種dichotomy分組,目前分成兩組,分別是orange和purple,orange的特點是,x1,x2和x3是一致的,x4不同并成對,例如1和5,2和8等,purple則是單一的,x1,x2,x3都不同,如6,7,9三組。 ![這里寫圖片描述](https://img.kancloud.cn/43/89/438900e0edfed76f91ffd9302b740d0b_561x326.jpg) 將Orange去掉x4后去重得到4個不同的vector并成為![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg),相應的purple為![](https://img.kancloud.cn/67/8a/678a8c223bcbb1f3c6aabf3c286630ce_10x14.jpg)。那么![](https://img.kancloud.cn/78/c2/78c213ecc1237c735d53844a1c951536_119x18.jpg),這個是直接轉化。緊接著,由定義,B(4,3)是不能允許任意三點shatter的,所以由![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)和![](https://img.kancloud.cn/67/8a/678a8c223bcbb1f3c6aabf3c286630ce_10x14.jpg)構成的所有三點組合也不能shatter(alpha經過去重),即![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/95/ea/95eae24953a2e7e6fdc7f205f0d9e0dd_559x328.jpg) 另一方面,由于![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)中x4是成對存在的,且![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)是不能被任意三點shatter的,則能推導出![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)是不能被任意兩點shatter的。這是因為,如果![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)是不能被任意兩點shatter,而x4又是成對存在的,那么x1、x2、x3、x4組成的![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg)必然能被三個點shatter。這就違背了條件的設定。這個地方的推導非常巧妙,也解釋了為什么會這樣分組。此處得到的結論是![](https://img.kancloud.cn/a9/ee/a9ee3ebafb44808c3cbda09f39a2917a_10x7.jpg) ![這里寫圖片描述](https://img.kancloud.cn/e0/81/e0813bd8ce5db72297020eb8be387355_560x324.jpg) 由此得出B(4,3)與B(3,x)的關系為: ![這里寫圖片描述](https://img.kancloud.cn/fb/89/fb8902c4ca01ba7a4061fc73b2972c7b_564x122.jpg) 最后,推導出一般公式為: ![這里寫圖片描述](https://img.kancloud.cn/13/2f/132fd0e215d88415a6c50f72f9978208_560x118.jpg) 根據推導公式,下表給出B(N,K)值 ![這里寫圖片描述](https://img.kancloud.cn/81/67/81672a60e9e6a7926c7aa35a0f952846_562x191.jpg) 根據遞推公式,推導出B(N,K)滿足下列不等式: ![這里寫圖片描述](https://img.kancloud.cn/ea/80/ea80adc93a1cdee6d7c9d2e273f8fa89_554x98.jpg) 上述不等式的右邊是最高階為k-1的N多項式,也就是說成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界B(N,K)的上界滿足多項式分布poly(N),這就是我們想要得到的結果。 得到了![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界B(N,K)的上界滿足多項式分布poly(N)后,我們回過頭來看看之前介紹的幾種類型它們的![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)與break point的關系: ![這里寫圖片描述](https://img.kancloud.cn/f8/da/f8da66d501158c0667c9958f90b5d976_566x183.jpg) 我們得到的結論是,對于2D perceptrons,break point為k=4,![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界是![](https://img.kancloud.cn/04/17/0417697c19243c90db65bf43fcf83ba3_35x14.jpg)。推廣一下,也就是說,如果能找到一個模型的break point,且是有限大的,那么就能推斷出其成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)有界。 ### **四、A Pictorial Proof** 我們已經知道了成長函數的上界是poly(N)的,下一步,如果能將![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)代替M,代入到Hoffding不等式中,就能得到![](https://img.kancloud.cn/6f/c7/6fc7702fbf9cb862010777554e97d82d_74x14.jpg)的結論: ![這里寫圖片描述](https://img.kancloud.cn/fd/9c/fd9c5c36280b0548aad46603a9d3a557_566x108.jpg) 實際上并不是簡單的替換就可以了,正確的表達式為: ![這里寫圖片描述](https://img.kancloud.cn/c0/22/c0220c9194c332a9789e8f76214d0493_566x91.jpg) 該推導的證明比較復雜,我們可以簡單概括為三個步驟來證明: ![這里寫圖片描述](https://img.kancloud.cn/a5/4b/a54b85f77d0c26f13ba558bb5c071cb0_566x385.jpg) ![這里寫圖片描述](https://img.kancloud.cn/72/d6/72d6f01b10eca305c01245be19545365_566x355.jpg) ![這里寫圖片描述](https://img.kancloud.cn/50/e4/50e413b4d4bb0bb65a2d0a3912eb7be2_566x392.jpg) 這部分內容,我也只能聽個大概內容,對具體的證明過程有興趣的童鞋可以自行研究一下,研究的結果記得告訴一下我哦。 最終,我們通過引入成長函數![](https://img.kancloud.cn/b8/3d/b83dac2572351ca2b87995181ffd66bb_25x10.jpg),得到了一個新的不等式,稱為Vapnik-Chervonenkis(VC) bound: ![這里寫圖片描述](https://img.kancloud.cn/05/7e/057ecd77b72464a53c5a8a7b087e4bbf_566x127.jpg) 對于2D perceptrons,它的break point是4,那么成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)。所以,我們可以說2D perceptrons是可以進行機器學習的,只要找到hypothesis能讓![](https://img.kancloud.cn/c9/38/c938ce5f2a3f7dfb47848be0e1a75bfc_54x15.jpg),就能保證![](https://img.kancloud.cn/20/fb/20fb42022bbd4be133366b923dd6b2aa_75x14.jpg)。 ### **五、總結** 本節課我們主要介紹了只要存在break point,那么其成長函數![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)就滿足poly(N)。推導過程是先引入![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界B(N,k),B(N,k)的上界是N的k-1階多項式,從而得到![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)的上界就是N的k-1階多項式。然后,我們通過簡單的三步證明,將![](https://img.kancloud.cn/51/56/515626ad9a6c314226ca818d6a40392f_52x18.jpg)代入了Hoffding不等式中,推導出了Vapnik-Chervonenkis(VC) bound,最終證明了只要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>

                              哎呀哎呀视频在线观看