Pravděpodobně přibližně správné učení - Probably approximately correct learning

v teorie výpočetního učení, pravděpodobně přibližně správný (PAC) učení se je rámec pro matematickou analýzu strojové učení. Bylo navrženo v roce 1984 Leslie Valiant.^[1]

V tomto rámci student obdrží vzorky a musí si vybrat funkci zobecnění (nazývanou hypotéza) z určité třídy možných funkcí. Cílem je, aby s vysokou pravděpodobností („pravděpodobně“ část) měla vybraná funkce nízkou hodnotu chyba generalizace („přibližně správná“ část). Žák musí být schopen naučit se koncept s libovolným poměrem aproximace, pravděpodobností úspěchu nebo distribuce vzorků.

Model byl později rozšířen o léčbu hluku (nesprávně klasifikované vzorky).

Důležitou inovací rámce PAC je zavedení teorie výpočetní složitosti koncepty strojového učení. Od studenta se zejména očekává, že najde efektivní funkce (požadavky na čas a prostor spojené s a polynomiální velikosti příkladu) a samotný student musí implementovat efektivní postup (vyžadující počet příkladů vázaný na polynom velikosti konceptu, upravený aproximací a pravděpodobnost meze).

Definice a terminologie

Abychom mohli dát definici něčeho, co je PAC-učitelné, musíme nejprve zavést nějakou terminologii.^[2][3]

Pro následující definice budou použity dva příklady. První je problém rozpoznávání znaků vzhledem k řadě ${ displaystyle n}$ bity kódující obraz v binární hodnotě. Druhým příkladem je problém s nalezením intervalu, který bude správně klasifikovat body v intervalu jako pozitivní a body mimo rozsah jako negativní.

Nechat ${ displaystyle X}$ být soubor nazvaný instanční prostor nebo kódování všech vzorků. V problému s rozpoznáváním znaků je prostor instance ${ displaystyle X = {0,1 } ^ {n}}$. V problému intervalu prostor instance, ${ displaystyle X}$, je množina všech ohraničených intervalů v ${ displaystyle mathbb {R}}$, kde ${ displaystyle mathbb {R}}$ označuje množinu všech reálných čísel.

A pojem je podmnožina ${ displaystyle c podmnožina X}$. Jeden koncept je sada všech vzorů bitů v ${ displaystyle X = {0,1 } ^ {n}}$ které zakódují obrázek písmene "P". Ukázkovým konceptem z druhého příkladu je sada otevřených intervalů, ${ displaystyle {(a, b) střední 0 leq a leq pi / 2, pi leq b leq { sqrt {13}} }}$, z nichž každý obsahuje pouze kladné body. A koncept třídy ${ displaystyle C}$ je sbírka konceptů ${ displaystyle X}$. Může to být množina všech podmnožin řady bitů, které jsou skeletonizovaný 4-připojeno (šířka písma je 1).

Nechat ${ displaystyle EX (c, D)}$ být procedurou, která čerpá příklad, ${ displaystyle x}$pomocí rozdělení pravděpodobnosti ${ displaystyle D}$ a dává správný štítek ${ displaystyle c (x)}$, to je 1 pokud ${ displaystyle x v c}$ a 0 jinak.

Nyní, vzhledem ${ displaystyle 0 < epsilon, delta <1}$, Předpokládejme, že existuje algoritmus ${ displaystyle A}$ a polynom ${ displaystyle p}$ v ${ displaystyle 1 / epsilon, 1 / delta}$ (a další relevantní parametry třídy ${ displaystyle C}$) takové, že vzhledem k velikosti vzorku ${ displaystyle p}$ tažené podle ${ displaystyle EX (c, D)}$, tedy s pravděpodobností minimálně ${ displaystyle 1- delta}$, ${ displaystyle A}$ vydává hypotézu ${ displaystyle h v C}$ která má průměrnou chybu menší nebo rovnou ${ displaystyle epsilon}$ na ${ displaystyle X}$ se stejnou distribucí ${ displaystyle D}$. Dále pokud výše uvedené tvrzení pro algoritmus ${ displaystyle A}$platí pro každý koncept ${ displaystyle c v C}$ a pro každou distribuci ${ displaystyle D}$ přes ${ displaystyle X}$a pro všechny ${ displaystyle 0 < epsilon, delta <1}$ pak ${ displaystyle C}$ je (efektivně) PAC učitelný (nebo zjistitelný PAC bez distribuce). Můžeme to také říci ${ displaystyle A}$ je Algoritmus učení PAC pro ${ displaystyle C}$.

Rovnocennost

Za určitých pravidelných podmínek jsou tyto podmínky rovnocenné: ^[4]

1. Koncept třídy C je PAC učitelný.
2. The VC rozměr z C je konečný.
3. C je uniforma Třída Glivenko-Cantelli.^{[je zapotřebí objasnění ]}
4. C je stlačitelný ve smyslu Littlestone a Warmuth

Viz také

• Strojové učení
• Dolování dat
• Tolerance chyb (PAC učení)
• Složitost vzorku

Reference

https://users.soe.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf

Moran, Shay; Yehudayoff, Amir (2015). Msgstr "Ukázková schémata komprese pro třídy VC". arXiv:1503.06960 [cs.LG ].

Další čtení

• M. Kearns, U. Vazirani. Úvod do teorie výpočetního učení. MIT Press, 1994. Učebnice.
• M. Mohri, A. Rostamizadeh a A. Talwalkar. Základy strojového učení. MIT Press, 2018. Kapitola 2 obsahuje podrobné zpracování PAC-učitelnosti. Čitelné otevřeným přístupem od vydavatele.
• D. Haussler. Přehled pravděpodobně přibližně správného (PAC) vzdělávacího rámce. Úvod do tématu.
• L. Statečný. Pravděpodobně přibližně správné. Basic Books, 2013. Valiant tvrdí, že učení PAC popisuje, jak se organismy vyvíjejí a učí.