可能近似正確的學習

在計算學習理論中，可能近似正確的學習（PAC）是一個機器學習的數學分析框架。在這個框架中，學習者收到樣本，必須從某類可能的函數中選擇一個概括性的函數（稱為假設）。目標是，在高概率的情況下（可能的部分），所選的函數將具有低泛化誤差（近似正確的部分）。學習者必須能夠在任何任意的近似率、成功概率或樣本分布的情況下學習這個概念。該模型后來被擴展到處理噪聲（錯誤分類的樣本）。PAC框架的一個重要創新是將計算復雜性理論的概念引入機器學習。特別是，學習者被期望找到有效的函數（時間和空間的要求被約束為例子大小的多項式），而學習者本身必須實現一個有效的程序。

為了給出PAC可學習的東西的定義，我們首先要介紹一些術語。對于下面的定義，我們將使用兩個例子。xxx個例子是字符識別的問題，給定一個數組為n的數組位編碼的二值圖像。

另一個例子是尋找一個區間的問題，該區間內的點將被正確地分類為正值，而區間外的點則是負值。{displaystyleX}是一個被稱為實例空間的集合。是一個稱為實例空間或所有樣本編碼的集合。在字符識別問題中，實例空間為{displaystyleX}是區間問題中所有有界區間的集合。是R中所有有界區間的集合。

在某些規則性條件下，這些條件是等價的。概念類C是可PAC學習的。C的VC維度是有限的。