計算學習理論PAC學習框架

Question

考慮機器學習算法從訓練集訓練，用PAC學習模型幫助您在訓練樣本大小界限需要我們這樣的概率誤差是有限的（由小量）是有界的（按三角形）。

什麼PAC學習模型說一下計算（時間）的複雜性。 假設一個學習算法有更多的時間（如更多的迭代）錯誤和概率是如何限制變化

作爲一個學習算法，需要一個小時訓練是沒有實際用途的財務預測問題。我所需要的性能變化，隨着時間如何給算法的變化都在誤差範圍而言，什麼是錯誤的有界

Answer 1

的PAC模型簡單地告訴你，你需要多少數據塊來獲得一定水平的概率有一定概率的錯誤。這可以通過查看您使用的實際機器學習算法來轉化爲對運行時間的影響。例如，如果您的算法運行時間爲O（2^n），並且PAC模型表示您需要1000個示例，可能有95％的機會出現.05錯誤，10,000出現0.0055錯誤的示例，那麼您知道你應該期望增加精度的巨大放緩。而O（log n）算法的相同PAC信息可能會導致您繼續前進並獲得較低的錯誤。

在一個側面說明，這聽起來像你可能會感到困惑如何大多數監督學習算法的工作：

假設一個學習算法，賦予了更多的時間（如更多的迭代），如何在錯誤和概率誤差是有限的變化

在大多數情況下，你不能真正給同樣的算法更多的時間和期望更好的結果，除非你偶然的參數（例如學習率）或增加例子的數量。也許通過'迭代'來表示例子，在這種情況下，例子數量對可能性和錯誤率的影響可以通過操縱用於PAC學習模型的方程組來找到;請參閱wiki article。