Sandsynligvis nogenlunde korrekt træning

Sandsynligvis Approximately Correct Learning ( PAC - læring ) er et maskinlæringsskema , der bruger begreberne asymptotisk pålidelighed og beregningsmæssig kompleksitet . Foreslået i 1984 af Leslie Valiant [1] .

I dette skema modtager læreren prøver og skal vælge en generaliserende funktion (kaldet en hypotese ) fra en bestemt klasse af mulige funktioner. Målet er en funktion, der med stor sandsynlighed (derfor "sandsynligvis" i navnet) har en lav generaliseringsfejl (derfor "omtrent korrekt" i navnet). Læreren bør være i stand til at undervise i et koncept [2] der giver en vilkårlig tilnærmelsesfaktor, sandsynlighed for succes eller stikprøvefordeling .

Modellen blev senere udvidet til at håndtere støj (forkert klassificerede prøver).

En vigtig nyskabelse af MIC-ordningen er brugen af konceptet om den beregningsmæssige kompleksitet af maskinlæring. Især forventes læreren at finde effektive funktioner (som er begrænset i køretid og plads, der kræves af et polynomium af stikprøvestørrelsen), og læreren skal implementere en effektiv procedure (ved at bede om en eksempelstørrelse begrænset af et polynomium af konceptstørrelse, modificeret ved tilnærmelse og sandsynlighedsgrænser ).

Definitioner og terminologi

Til en formel definition bruges et givet sæt , kaldet feature space eller kodningen af alle samples. For eksempel, i problemet med optisk tegngenkendelse er trækrummet , og i problemet med at finde et interval (korrekt klassificering af punkter inde i intervallet som positive og uden for intervallet som negative), er trækrummet mængden af alle afgrænsede intervaller i . $x$ $X=\{0,1\}^{n}$ $\mathbb {R}$

Et andet begreb, der bruges i ordningen, er begrebet - en delmængde . For eksempel er sættet af alle bitsekvenser, der koder for mønsteret af bogstavet "P" et af begreberne i OCR-problemet. Et eksempel på et koncept for problemet med at finde et interval er sættet af åbne intervaller , som hver kun indeholder positive punkter. Klassen af begreber er et sæt af begreber over . Dette kan være sættet af alle undersæt af frameworket 4-forbundne array af bits (skrifttypebredden er 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$

Lad være en procedure, der genererer et eksempel ved hjælp af en sandsynlighedsfordeling og giver den korrekte etiket , som er 1 hvis og 0 ellers. Nu, givet , antag, at der er en algoritme og et polynomium fra (og andre relevante klasseparametre ) sådan, at givet en stikprøve af størrelse , tegnet i henhold til , så med sandsynlighed er mindst outputtet af algoritmen hypotesen , som har middelværdi fejl, mindre end eller lig med for samme fordeling . Ydermere, hvis sætningen ovenfor for algoritmen er sand for ethvert koncept og for enhver distribution over og for alle , så er den (effektivt) VPK-lærbar (eller distributionsfri VPK-lærbar ). I dette tilfælde anses det for at være VPK-indlæringsalgoritmen for . $EX(c,D)$ $x$ $D$ $c(x)$ $x\in c$ $0<\epsilon ,\delta <1$ $EN$ $s$ $1/\epsilon ,1/\delta$ $C$ $s$ $EX(c,D)$ $1-\delta$ $EN$ $h\in C$ $\epsilon$ $x$ $D$ $EN$ $c\in C$ $D$ $x$ $0<\epsilon ,\delta <1$ $C$ $EN$ $C$

Ækvivalens

Under visse regelmæssighedsbetingelser er disse tre betingelser ækvivalente:

Konceptklassen er VPK-lærelig. $C$
Klassens Vapnik-Chervonenkis dimension er begrænset. $C$
$C$ er en homogen Glivenko-Cantelli klasse .

Se også

Fejltolerance (VPK-træning)
Eksempel på kompleksitet

Noter

↑ Valiant1984 .
↑ Begreber er korrekte undergrupper af sættet af tilladte funktioner.

Litteratur

Valiant L. En teori om det lærbare // Kommunikation af ACM. - 1984. - Udgave. 27 .
Kearns M., Vazirani U. An Introduction to Computational Learning Theory. - MIT Press, 1994. - ISBN 9780262111935 .
Balas Kausik Natarajan. maskinelæring. En teoretisk tilgang. - Morgan Kaufmann Publishers, 1991. - ISBN 1-55860-148-1 .
D. Haussler. Oversigt over Probably Approximately Correct (PAC) Learning Framework Arkiveret 28. september 2011 på Wayback Machine . En introduktion til emnet.
L. Valiant. Sandsynligvis nogenlunde korrekt. Basic Books, 2013. I bogen diskuterer Valiant, hvordan VPK-læring beskriver, hvordan organismer udvikler sig og lærer.

Machine learning og data mining
Opgaver	Klassifikationsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-Net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG