V teorii výpočetního učení je pravděpodobně přibližně správné učení (PAC learning) rámec pro matematickou analýzu strojového učení. Navrhl ho v roce 1984 Leslie Valiant.
V tomto rámci studující obdrží vzorky a musí si vybrat zobecňovací funkci (tzv. hypotézu) z určité třídy možných funkcí. Cílem je, aby s vysokou pravděpodobností (tzv. „pravděpodobně“) měla zvolená funkce nízkou chybu zobecnění (tzv. „přibližně správnou“ část). Studující musí být schopen naučit se pojmu vzhledem k libovolnému přibližovacímu poměru, pravděpodobnosti úspěchu nebo rozložení vzorků.
Model byl později rozšířen o zpracování šumu (špatně klasifikované vzorky).
Důležitou inovací rámce PAC je zavedení konceptů teorie výpočetní složitosti do strojového učení. Očekává se zejména, že studující nalezne efektivní funkce (časové a prostorové požadavky ohraničené na polynom velikosti příkladu) a sám studující musí zavést efektivní postup (vyžadující příkladový počet ohraničený na polynom velikosti konceptu, modifikovaný aproximací a pravděpodobnostními hranicemi).
Definice a terminologie
Abychom mohli dát definici něčeho, co je PAC-naučitelné, musíme nejprve zavést nějakou terminologii.
Pro následující definice budou použity dva příklady. Prvním je problém rozpoznávání znaků vzhledem k poli bitů. Druhým příkladem je problém nalezení intervalu, který správně klasifikuje body v intervalu jako kladné a body mimo rozsah jako záporné.
Dovolit je množina, která se nazývá prostor instance nebo kódování všech vzorků. V problému rozpoznávání znaků je prostor instance . V problému intervalu je prostor instance , Kde označuje množinu všech reálných čísel.
Koncept je podmnožina . Jeden koncept je množina všech bitů, které kódují písmeno „P“ v . Příklad konceptu z druhého příkladu je množina všech čísel mezi a . Třída konceptu je množina konceptů nad . To může být množina všech množin bitů, které jsou skeletonizované 4-connected (šířka písma je 1).
Dovolit je postup, který kreslí příklad, , pomocí rozdělení pravděpodobnosti a dává správné označení .
Řekněme, že existuje algoritmus, který daný přístup k a vstupy a že s pravděpodobností alespoň , Výstupy hypotéza, která má chybu menší nebo rovna s příklady čerpané z s distribucí . Pokud existuje takový algoritmus pro
každý koncept , Pro každou distribuci nad , A pro všechny a pak je PAC učitelný. Můžeme také říci, že je PAC učení algoritmus pro .