534
簡單自學機器學習理論—— 泛化界限 (Part II )
首發地址：https://yq.aliyun.com/articles/67168
本文由北郵@愛可可-愛生活 老師推薦，阿裏雲雲棲社區組織翻譯。
以下為譯文
part II- 泛化界限（第I部分內容點此；第III部分內容點此）
上節總結到最小化經驗風險不是學習問題的解決方案，並且判斷學習問題可解的條件是求：
在本節中將深度調查研究該概率，看其是否可以真的很小。
獨立同分布
為了使理論分析向前發展，作出一些假設以簡化遇到的情況，並能使用從假設得到的理論推理出實際情況。
我們對學習問題作出的合理假設是訓練樣本的采樣是獨立同分布的，這意味著所有的樣本是相同的分布，並且每個樣本之間相互獨立。
大數法則
m
hoeffding
將其應用到泛化概率上，假設錯誤限定在0和1之間，則對於假設h有
這意味著訓練與泛化誤差之間的差大於
的概率是隨著數據集的大小成指數衰減。
泛化界限：第一次嚐試
為了針對整個假設空間都有泛化差距大於，表示如下：
使用布爾不等式，可以得到
使用
置信度1-δ有
使用基本代數知識，用δ表示得到：
上式就是第一次泛化界限，該式表明泛化錯誤是受到訓練誤差加上以假設空間大小和數據集大小的函數的限定。
檢驗獨立性假設
首先需要問自己是否每一個可能的假設都需要考慮？答案是簡單的，由於學習算法需要搜索整個假設空間以得到最優的解決方案，盡管這個答案是正確的，我們需要更正式化的答案：
泛化不等式的公式化揭示了主要的原因，需要處理現存的上確界，上確界保證了存在最大泛化差距大於“的假設上。
從上圖可以看出是二分類問題，很明顯彩色線產生的是相同的分類，它們有著相同的經驗風險。如果隻對經驗風險感興趣，但是需要考慮樣本外的風險，表示如下：
為了確保上確界要求，需要考慮所有可能的假設。現在可以問自己，每一個有大泛化差距的假設事件可能是互相獨立的嗎？如果上圖紅線假設有大的泛化差距大於，那麼可以肯定的是在該區域的每個假設也都會有。
這對我們的數學分析是沒有幫助的，由於區域之間看起來取決於樣本點的分布，因此沒有方法在數學上精確獲取這些依賴性，於是這些統一的界限和獨立假設看起來像是我們能夠做的最佳近似，但它高估了概率並使得這些界限非常接近，性能不好。
對稱引理
’
（1）
該式意味著最大泛化差距大於’之間的經驗風險差概率大於
的兩倍，這被稱作對稱引理。
生長函數
如果我們有許多假設有著相同的經驗風險，可以放心地選擇其中一個作為整個群的代表，將其稱作有效假設並拋棄其它的假設。
假設在
H
（2）
但由於是指數形式，隨著m
VC
2D
從圖中的判定邊界，可清晰知道沒有線性分類器能產生這樣的標簽，因為沒有線性分類器能夠以這樣的方式劃分空間，這一事實能夠用來獲得更好的限定，這使用
K是空間。
維數作為其替身，
將會是複雜度或者假設空間豐富度的測量。
VC
或者使用表示生長函數上的界限得到：
該式清晰並間接表示了學習問題是否可解，並針對無限假設空間，對其泛化誤差有著有限的界限。
基於分布的界限
事實上，ρ，可以證明得到針對假設分類器有：
這就是支持向量機（SVM）背後的理論依據。
一個不等式去管理所有的它們
上麵的所有分析是針對二元分類問題，然而
δ的函數，這個不等式基本說明泛化誤差能夠分解為兩部分：經驗訓練誤差和學習模型的複雜度。該不等式的形式對於任何學習問題、不管多麼準確界限而言都是適用的。
參考文獻：
l Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012.
l Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
l Abu-Mostafa, Y. S., Magdon-Ismail, M., & Lin, H. (2012). Learning from data: a short course.
文章原標題《Machine Learning Theory - Part II》，作者：Mostafa Samir，譯者：海棠
文章為簡譯，更為詳細的內容，請查看原文
最後更新：2017-07-12 22:08:44