1樓：章浩
下面冗長無趣的分析，實在看不下去了。
與其看看零碎的碎碎念，東拼西湊的我覺得。。。
不如看林軒田大佬親自講的video來的系統 (PAC可學習性，看p26~p29即可，30分鐘搞定)
林軒田機器學習基石(國語)_嗶哩嗶哩 (゜-゜)つロ 乾杯~-bilibili
如果對video理解感到困難的同學，可以參考下面這個同學寫的部落格，我覺得已經夠清楚的啦，就不狗尾續貂了。
如何通俗地理解機器學習中的 VC 維、shatter 和 break point？
2樓：若羽
VC維定義了乙個學習器的泛化邊界。
為分類器的Hypothesis。
假設乙個布林函式
VC維就是指H最多可以打散（shatter）的點的數量對於二維拓撲空間的半平面H， 。
VC理論：一族分類的布林函式 與VC維 ，能打散的點 ，滿足在這樣的情況下，是可學習的、收斂的
3樓：魚子醬
看了前面人寫的，沒怎麼看懂，可能是他們寫得太專業了，我用通俗的語言解釋一下打散和VC維。
能否打散：給定N個樣本，分類器（或者說函式）能否分出這N個樣本所有可能的分類結果。比如二分類問題，給定兩個樣本x1和x2即N=2，你有乙個分類器f（只知道模型，引數任意），如果分類器f能分出這兩個樣本所有可能的分類情況（2^N=4種）即AA，AB，BA和BB，則分類器f能打散這兩個樣本；換言之，如果分類器f能打散這2個樣本，那麼不管你這2個樣本的類別是怎樣的分布情況，我分類器f都能把這2個樣本正確分類出來。
VC維：D維資料空間下，如果分類器最大能打散h個樣本，則該分類器的VC維=h。
4樓：裕廊西宇少爺
看了樓上各位大佬的總結，再加上自己目前在做點約束深度學習複雜性的東西，結合現在的工作和一邊自學Learning Theory的進度，也來總結幾句：
VC-Dimension 衡量模型複雜度。我們知道現在deep learning很強大，乙個原因就是模型夠複雜能逼近任意的函式（其實淺層的神經網路就可以做到這一點）。因為模型太複雜了所以需要喂大量的資料給deep model，不然就會over-fitting（對應就是 和
差太遠） . 有沒有可能把weights限定在離散集裡，比如 。若離散集太小，則表達能力不夠；若離散集太大，則又回到了原來的全精度模型裡面。
那中間乙個狀態是否對應一定的VC-Dimension降低以使得模型可以剛好複雜呢。
一些想法，持續更新。
5樓：偷泥王
我來大致解釋一下這三個概念。依照邏輯和理解的順序，我們先介紹shatter，然後break point，最後是VC Dimension。
首先，假定我們的Hypothesis Set 是乙個Binary function的集合，當我們將乙個大小為N的sample data set(記作)作為 中的乙個hypothesis 的input時，我們得到乙個長度為N的tuple，形如，我們把這樣的乙個tuple稱作乙個Dichotomy。
我們定義，對於乙個Hypothesis Set 和sample 來說，是 在sample 上所有dichotomy的集合。
這樣定義有什麼好處呢？在Hoeffding's Inequality中,
\epsilon]\]" eeimg="1"/>，
RHS中的M，也就是Hypothesis Set 的大小，是我們無法upper bound的。在Generalization Bound中，
，出現同樣的問題 - 我們無法約束hypothesis的數量，這導致我們無法判斷能否很好地估計，從而無法判斷Learning的feasibility。這裡的一系列概念，就是要找到乙個能夠替代這個M，同時也可以衡量hypothesis set的大小的乙個值，從而說明我們可以做到Learning。
Growth function.對於乙個Hypothesis Set H來說，它的Growth function是它在任意N個點上所能產生的最多的dichotomy的數量，記作。也就是說，。
那麼，我們可知對於任何 ，乙個trivial bound是。這樣一來，我們首先就把原先的Hypothesis Set 的大小的衡量從無窮縮小到了乙個有限的值，儘管仍舊是乙個不現實的upper bound。把Growth function看成是有效假設(Effective hypotheses)的數量更加容易理解 - Growth function代表的是能得出不同結果的，有意義的Hypothesis的最大數量。
如果 能在data set 上產生所有的dichotomy，那麼我們說 可以shatter。以下舉兩個例子。
Ex. input data set 為2D中的三個點，這三個點能夠組成乙個等邊三角形；定義 為所有直線，若乙個點在直線的一邊，則return +1，否則return -1，請問 能夠shatter這個嗎？
可以。Ex. input data set 為2D中的四個點，這四個點能夠組成乙個正方先；定義 為所有直線，若乙個點在直線的一邊，則return +1，否則return -1，請問 能夠shatter這個嗎？
不可以。嘗試可知，以下dichotomy無法得到：
將四個點從左上角開始順時針命名為，return +1，return -1。這個例子中，。
顯然，如果 能夠shatter 乙個大小為N的data set，那麼可知
換言之， 可以shatter某個data set
那麼，另乙個方向上，是不是能shatter任意呢？
我們來看乙個例子。
Ex. input data set 為2D中的N個點；定義 為所有convex set，若乙個點在乙個convex set內部，則return +1，否則return -1，請問 能夠shatter這個嗎？
這個例子中，。為什麼呢？假設這N個點都在某個圓的圓周上，那麼對於任意dichotomy，我們只需把+1的點連線起來，構成乙個convex set，剩下的點自然在這個convex set之外，所以任意dichotomy都可從這N個點上產生。
然而，H能shatter任意嗎？顯然是不能的，我們只需考慮N個點排成一條線的情況。
儘管現在我們把乙個無窮的範圍縮小到了有限的，這個bound還是不現實。這時我們需要break point來幫助我們進一步縮小範圍。
我們定義，如果所有大小為k的data set都不能被 shatter，我們把k稱作 的乙個break point。觀察可知如果所有大小為k的data set都不能被 shatter，那麼所有大小為k+1的也不能被 shatter，所以我們只需關心最小的這樣的k。
我們看先前的乙個例子。
Ex. 定義 為乙個平面中的所有直線，將所有點分類為+1/-1。
之前的例子中我們已經看到，對於N=3時，Growth function的值為8，；N=4時，嘗試一下便可知，Growth function的值為14，。故break point為4。
那麼break point有什麼用呢？對於乙個 ，如果break point k是finite的，那麼；經過一些證明，我們可以進一步得出，如果break point存在，的upper bound其實是乙個polynomial in N。以下補充了這個定理的證明。
這樣一來Hoeffding's Inequality和Generalizaiton Bound就可以很好地收斂。換句話說，break point的存在告訴我們Learning是可行的。
那麼，VC Dimension是什麼呢？對於乙個 ，它的Vapnik-Chervonenkis Dimension為使得的最大的N，記作。如果Growth function恆等於，那麼 為 。
觀察若 是 的VC Dimension，那麼 是 的乙個break point，因為根據定義，對於d_" eeimg="1"/>，；同時 是 最小的break point，因為 能shatter任意 個points的話，也能shatter這些points的subsets。
更重要的是，VC Dimension就是我們先前所提到的那個polynomial的order。
通過數學論證，我們還可以把進一步縮小，結論是：
並且我們可以得到VC Generalization Bound:
雖然這仍是乙個相當loose的bound，但這告訴我們Learning is feasible。
參考
Abu-Mostafa, Yaser S., Malik Magdon-Ismail, and Hsuan-Tien Lin. Learning from data:
a short course. S. l.:
AML, 2012. Print.
4/25
有朋友對於以上提到的結論「如果break point存在，就是乙個polynomial」的數學證明感興趣，在此補充。
首先，我們定義： 為在任意N個點上，使得這N個點的任意大小為k的子集都不能被shattered的最大的dichotomy的數量。
根據定義，我們可知，如果k是某乙個 的break point，那麼 。
從k=1或者N=1開始， , （k>1時）。
我們觀察 以及 的情況。
對於這N個點，記作，我們把所有的dichotomy分類。每乙個dichotomy是乙個長度為N的tuple，其中每個元素都為+1/-1。我們把所有dichotomy分成三個組， , , 。
分法如下：我們先不看N號位上的元素，如果有兩個tuple的前N-1個元素都一致，那麼我們就把這兩個tuple中，N號位上為+1的放在，N號位上為-1的放在。其餘剩下的，也就是那些1到N-1號位上元素互相都不重複的tuple，放在。
設的大小為 ，的大小為 ，顯然的大小也為。 便是所有dichotomy的數量。
那麼我們可知，因為前N-1個points的所有k-subset都不能被shatter。
然後，因為在中，中任意k-1個點都無法被中的dichotomy shatter（否則的話和就可以shatter乙個大小為k的subset），所以，
。因此，
。現在我們要用這個結論來證明乙個 lemma
Sauer's Lemma:
我們用induction證明。
首先，可知k=1或者N=1時這個lemma是對的。
然後，假定這個定理對於小於 的所有N以及所有k都是正確的。
我們需要證明這個定理對於 以及所有k也是正確的。
因為我們已知當k=1時，定理對於所有N都是正確的，我們只要關注 的情況。
Q.E.D
所以，我們可知，如果 ，那麼 ，而且RHS的最高次項的次數為k-1。
如何通俗簡單地理解 Inbound Marketing 和 Outbound Marketing
吳嘉陽 簡單一句話，以客戶需求的強烈程度分 主動營銷 inbound marketing 使用者需求相對較高，使用者主動索取產品相關資訊 和被動營銷 outbound marketing 使用者需求相對較低，被動被強推來索取產品資訊 劉延飛 Inbound marketing會慢慢成為marketi...
如何通俗地理解Hive的工作原理？
普適極客 謂詞下推 就是將SQL語句中的where謂詞邏輯都盡可能提前執行，減少下游處理的資料量。Hive中有謂詞下推優化的配置項hive.optimize.ppd，預設值true，與它對應的邏輯優化器是PredicatePushDown。該優化器就是將OperatorTree中的FilterOpe...
如何通俗地理解基因編輯中的脫靶效應？它跟基因編輯的安全風險有著怎樣的聯絡？
Ji Fei 脫靶效應該這麼理解 就是作用到靶點應該並不想開車一樣把預定的工具主動送到靶點，而應該是靠概率，也就是無序碰撞下通過結構變化驅使大部分工具與目標碰撞，脫靶效應實際上就因為這種無序碰撞並不能保證將所有工具送到目標，所以如果從無序到有序的問題沒有解決的話，是不能百分之百的說基因編輯毫無問題，...