Förmodligen ungefär korrekt träning

Probably Approximately Correct Learning ( PAC - inlärning ) är ett maskininlärningsschema som använder begreppen asymptotisk tillförlitlighet och beräkningskomplexitet . Föreslog 1984 av Leslie Valiant [1] .

I detta schema får läraren prover och måste välja en generaliserande funktion (kallad hypotes ) från en viss klass av möjliga funktioner. Målet är en funktion som med stor sannolikhet (därav "förmodligen" i namnet) har ett lågt generaliseringsfel (därav "ungefärligt korrekt" i namnet). Läraren bör kunna lära ut ett koncept [2] som ger en godtycklig approximationsfaktor, sannolikhet för framgång eller provfördelning .

Modellen utökades senare för att hantera buller (felklassade prover).

En viktig innovation i MIC-systemet är användningen av konceptet med beräkningskomplexiteten för maskininlärning. I synnerhet förväntas läraren hitta effektiva funktioner (som är begränsade i körtid och utrymme som krävs av ett polynom av urvalsstorleken), och läraren måste implementera en effektiv procedur (genom att be om en exempelstorlek begränsad av ett polynom av konceptstorlek, modifierad genom approximation och sannolikhetsgränser ).

Definitioner och terminologi

För en formell definition används någon given uppsättning , som kallas funktionsutrymmet eller kodningen av alla sampel. Till exempel, i problemet med optisk teckenigenkänning, är särdragsutrymmet , och i problemet med att hitta ett intervall (korrekt klassificering av punkter inuti intervallet som positiva och utanför intervallet som negativa), är särdragsutrymmet mängden av alla avgränsade intervaller i . $X$ $X=\{0,1\}^{n}$ $\mathbb {R}$

Ett annat koncept som används i schemat är konceptet - en delmängd . Till exempel är uppsättningen av alla bitsekvenser i som kodar mönstret för bokstaven "P" ett av begreppen i OCR-problemet. Ett exempel på ett koncept för problemet med att hitta ett intervall är uppsättningen av öppna intervall , som var och en endast innehåller positiva punkter. Klassen av begrepp är en uppsättning begrepp över . Detta kan vara uppsättningen av alla delmängder av ramverket 4-anslutna -matrisen av bitar (teckensnittets bredd är 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$

Låt vara en procedur som genererar ett exempel med hjälp av en sannolikhetsfördelning och ger rätt etikett , som är 1 om och 0 annars. Nu, givet , anta att det finns en algoritm och ett polynom från (och andra relevanta klassparametrar ) så att, givet ett urval av storlek , ritat enligt , då med sannolikhet åtminstone utgången av algoritmen är hypotesen , som har medelvärde fel, mindre än eller lika med för samma fördelning . Vidare, om påståendet ovan för algoritmen är sant för vilket koncept som helst och för någon distribution över och för alla , är det (i praktiken) VPK-lärbart (eller distributionsfritt VPK-lärbart ). I det här fallet anses det vara VPK -inlärningsalgoritmen för . $EX(c,D)$ $x$ $D$ $c(x)$ $x\in c$ $0<\epsilon ,\delta <1$ $A$ $sid$ $1/\epsilon ,1/\delta$ $C$ $sid$ $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$

Ekvivalens

Under vissa villkor för regelbundenhet är dessa tre villkor likvärdiga:

Konceptklassen är VPK-lärbar. $C$
Klassens Vapnik-Chervonenkis dimension är ändlig. $C$
$C$ är en homogen Glivenko-Cantelli-klass .

Se även

Feltolerans (VPK-träning)
Exempelkomplexitet

Anteckningar

↑ Valiant1984 .
↑ Begrepp är korrekta delmängder av uppsättningen av tillåtna funktioner.

Litteratur

Valiant L. En teori om det lärbara // ACM:s kommunikation. - 1984. - Utgåva. 27 .
Kearns M., Vazirani U. An Introduction to Computational Learning Theory. - MIT Press, 1994. - ISBN 9780262111935 .
Balas Kausik Natarajan. maskininlärning. Ett teoretiskt tillvägagångssätt. - Morgan Kaufmann Publishers, 1991. - ISBN 1-55860-148-1 .
D. Haussler. Översikt över Probably Approximately Correct (PAC) Learning Framework Arkiverad 28 september 2011 på Wayback Machine . En introduktion till ämnet.
L. Valiant. Förmodligen Ungefär korrekt. Basic Books, 2013. I boken diskuterar Valiant hur VPK-lärande beskriver hur organismer utvecklas och lär sig.

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-nät Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG