Asi přibližně správný trénink

Pravděpodobně Approximately Correct Learning ( PAC learning ) je schéma strojového učení , které využívá koncepty asymptotické spolehlivosti a výpočetní složitosti . Navrhl v roce 1984 Leslie Valiant [1] .

V tomto schématu učitel obdrží vzorky a musí si vybrat zobecňující funkci (nazývanou hypotéza ) z určité třídy možných funkcí. Cílem je funkce, která s vysokou pravděpodobností (proto to "pravděpodobně" v názvu) bude mít nízkou chybu zobecnění (proto to "přibližně správné" v názvu). Učitel by měl být schopen naučit koncept [2] udávající libovolný aproximační faktor, pravděpodobnost úspěchu nebo rozdělení vzorku .

Model byl později rozšířen o zpracování šumu (nesprávně klasifikované vzorky).

Důležitou novinkou schématu MIC je využití konceptu výpočetní složitosti strojového učení. Zejména se od učitele očekává, že najde efektivní funkce (které jsou omezeny na běh a prostor vyžadovaný polynomem velikosti vzorku) a učitel musí implementovat efektivní postup (poptáním o velikosti příkladu omezeného polynomem velikosti vzorku). velikost konceptu, upravená aproximací a hranicemi pravděpodobnosti ).

Definice a terminologie

Pro formální definici se používá nějaká daná množina , nazývaná prostor funkcí nebo kódování všech vzorků. Například v problému optického rozpoznávání znaků je prostor příznaků , a v problému nalezení intervalu (správná klasifikace bodů uvnitř intervalu jako kladných a mimo interval jako záporných) je prostor příznaků množinou všech ohraničených intervaly v . $X$ $X=\{0,1\}^{n}$ $\mathbb {R}$

Dalším konceptem použitým ve schématu je koncept - podmnožina . Například sada všech bitových sekvencí v kódování vzoru písmene "P" je jedním z konceptů v problému OCR. Příkladem konceptu pro problém hledání intervalu je množina otevřených intervalů , z nichž každý obsahuje pouze kladné body. Třída pojmů je soubor pojmů nad . To může být množina všech podmnožin rámce 4-connected pole bitů (šířka písma je 1). $c\subset X$ $X=\{0,1\}^{n}$ $\{(a,b)\mid 0\leqslant a\leqslant \pi /2,\pi \leqslant b\leqslant {\sqrt {13}}\}$ $C$ $X$

Dovolit být procedura, která generuje příklad pomocí rozdělení pravděpodobnosti a dává správné označení , což je 1, pokud a 0 jinak. Nyní, za předpokladu, předpokládejme, že existuje algoritmus a polynom z (a další relevantní parametry třídy ) takový, že daný vzorek velikosti , nakreslený podle , pak s pravděpodobností alespoň výstupem algoritmu je hypotéza , která má střední hodnotu chyba, menší nebo rovna pro stejné rozdělení . Dále, pokud výše uvedené tvrzení pro algoritmus platí pro jakýkoli koncept a pro jakoukoli distribuci přes a pro všechny , pak je (efektivně) možno se naučit VPK (nebo se naučit VPK bez distribuce ). V tomto případě se má za to, že jde o algoritmus učení VPK pro . $EX(c,D)$ $X$ $D$ $c(x)$ $x\in c$ $0<\epsilon ,\delta <1$ $A$ $p$ $1/\epsilon ,1/\delta$ $C$ $p$ $EX(c,D)$ $1-\delta$ $A$ $h\in C$ $\epsilon$ $X$ $D$ $A$ $c\in C$ $D$ $X$ $0<\epsilon ,\delta <1$ $C$ $A$ $C$

Ekvivalence

Za určitých podmínek pravidelnosti jsou tyto tři podmínky ekvivalentní:

Třída konceptu se dá naučit VPK. $C$
Vapnik-Chervonenkisova dimenze třídy je konečná. $C$
$C$ je homogenní třída Glivenko-Cantelli .

Viz také

Odolnost proti chybám (školení VPK)
Složitost vzorku

Poznámky

↑ Valiant1984 .
↑ Koncepty jsou vlastní podmnožiny množiny přípustných vlastností.

Literatura

Valiant L. Teorie naučitelného // Komunikace ACM. - 1984. - Vydání. 27 .
Kearns M., Vazirani U. Úvod do teorie výpočetního učení. - MIT Press, 1994. - ISBN 9780262111935 .
Balas Kausik Natarajan. strojové učení. Teoretický přístup. - Morgan Kaufmann Publishers, 1991. - ISBN 1-55860-148-1 .
D. Haussler. Přehled pravděpodobně přibližně správného výukového rámce (PAC) Archivováno 28. září 2011 na Wayback Machine . Úvod do tématu.
L. Valiant. Pravděpodobně přibližně správně. Basic Books, 2013. Valiant v knize pojednává o tom, jak učení VPK popisuje, jak se organismy vyvíjejí a učí.

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-Net Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG