Datawhale
作者：邱錫鵬，復旦大學教授
沒有免費午餐定理（NFL）是由Wolpert 和Macerday在最優化理論中提出的。沒有免費午餐定理證明：對于基于迭代的最優化算法，不存在某種算法對所有問題（有限的搜索空間內）都有效。
如果一個算法對某些問題有效，那么它一定在另外一些問題上比純隨機搜索算法更差。也就是說，不能脫離具體問題來談論算法的優劣，任何算法都有局限性. 必須要“具體問題具體分析”。
沒有免費午餐定理對于機器學習算法也同樣適用。不存在一種機器學習算法適合于任何領域或任務。 如果有人宣稱自己的模型在所有問題上都好于其他模型，那么他肯定是在吹牛。
丑小鴨定理（Ugly Duckling Theorem）是1969 年由渡邊慧提出的[Watanable,1969]。“丑小鴨與白天鵝之間的區別和兩只白天鵝之間的區別一樣大”。這個定理初看好像不符合常識，但是仔細思考后是非常有道理的。
因為世界上不存在相似性的客觀標準，一切相似性的標準都是主觀的。
如果從體型大小或外貌的角度來看，丑小鴨和白天鵝的區別大于兩只白天鵝的區別；但是如果從基因的角度來看，丑小鴨與它父母的差別要小于它父母和其他白天鵝之間的差別。
奧卡姆剃刀原理是由14 世紀邏輯學家William of Occam提出的一個解決問題的法則：“如無必要，勿增實體“。
奧卡姆剃刀的思想和機器學習上正則化思想十分類似：簡單的模型泛化能力更好。如果有兩個性能相近的模型，我們應該選擇更簡單的模型。
因此，在機器學習的學習準則上，我們經常會引入參數正則化來限制模型能力，避免過擬合。
最小描述長度也可以通過貝葉斯學習的觀點來解釋[MacKay, 2003]。模型?? 在數據集?? 上的對數后驗概率為
其中? log ??(??) 和? log ??(??|??) 可以分別看作是模型?? 的編碼長度和在該模型下數據集?? 的編碼長度。也就是說，我們不但要使得模型?? 可以編碼數據集??，也要使得模型?? 盡可能簡單。
當使用機器學習方法來解決某個特定問題時，通常靠經驗或者多次試驗來選擇合適的模型、訓練樣本數量以及學習算法收斂的速度等。
但是經驗判斷或多次試驗往往成本比較高，也不太可靠，因此希望有一套理論能夠分析問題難度、計算模型能力，為學習算法提供理論保證，并指導機器學習模型和學習算法的設計。
這就是計算學習理論， 計算學習理論（Computational Learning Theory）是關于機器學習的理論基礎，其中最基礎的理論就是可能近似正確（Probably Approximately Correct，PAC）學習理論。
機器學習中一個很關鍵的問題是期望錯誤和經驗錯誤之間的差異，稱為泛化錯誤（Generalization Error）。泛化錯誤可以衡量一個機器學習模型?? 是否可以很好地泛化到未知數據。
因此，需要降低對學習算法能力的期望，只要求學習算法可以以一定的概率學習到一個近似正確的假設，即PAC 學習（PAC Learning）。
一個PAC 可學習（PACLearnable）的算法是指該學習算法能夠在多項式時間內從合理數量的訓練數據中學習到一個近似正確的??(??)。
PAC 學習可以分為兩部分：
“可能”（Probably）：一個學習算法?? 有“可能”以1 ? ?? 的概率學習到這樣一個“近似正確”的假設。?? 一般為0 到1/2之間的數，0 < ?? < 1/2。
PAC 學習可以下面公式描述：
其中??,?? 是和樣本數量?? 以及假設空間? 相關的變量。如果固定??、??，可以反過來計算出需要的樣本數量：
其中|?| 為假設空間的大小. 從上面公式可以看出，模型越復雜，即假設空間? 越大，模型的泛化能力越差。
要達到相同的泛化能力，越復雜的模型需要的樣本數量越多。為了提高模型的泛化能力，通常需要正則化（Regularization）來限制模型復雜度。
PAC 學習理論也可以幫助分析一個機器學習方法在什么條件下可以學習到一個近似正確的分類器。從上述公式可以看出，如果希望模型的假設空間越大，泛化錯誤越小，其需要的樣本數量越多。
