Definition des PAC-Lernmodells

Das wahrscheinlich ungefähr korrekte (PAC) Lernmodell ist definiert als:

Eine Konzeptklasse gilt als PAC-lernbar, wenn ein Algorithmus und eine Polynomfunktion so dass für alle ε> 0 und δ> 0 für alle Verteilungen D auf X und gilt Für jedes Zielkonzept c∈C gilt für jede Stichprobengröße m≥poly (1 / ε, 1 / δ, n, Größe (c)) Folgendes :$C$$A$$poly(·,·,·,·)$$ε>0$$δ>0$$D$$X$$c∈C$$m≥poly(1/ε,1/δ,n,size(c))$

$Pr[R(hs)≤ε]≥1-δ$

wobei $R(hs)$ der Generalisierungsfehler über eine Stichprobe $S$ der Größe $m$ die Instanzen der Variablen $X$ nach der Verteilung $D$ und $size(c)$ die maximalen Kosten der rechnerischen Darstellung von $c∈C$ .

Ich weiß, dass $poly(1/ε,1/δ,n,size(c))$ ein Polynom ist. Aber was ist die explizite Form von $poly(1/ε,1/δ,n,size(c))$ ? Was sind die Variablen? Was ist ihr Abschluss?

Es gibt keine Einschränkungen für außer dass es sich um ein Polynom oder allgemeiner um eine polynomiell begrenzte Funktion handelt (dh um eine durch ein Polynom begrenzte Funktion). Der Unterschied spielt in diesem Fall keine Rolle. Ohne Beschränkung der Allgemeinheit kann man annehmen , dass für einige , .$poly(\cdot,\cdot,\cdot,\cdot)$$A,B > 0$$poly(x,y,z,w) = A(xyzw)^B$

Die Definition versucht, die Situation zu modellieren, dass nur eine kleine Anzahl von Stichproben benötigt wird, um das Konzept zu lernen. Um "klein" zu quantifizieren, müssen wir erstens entscheiden, welche Mengen klein sein werden (in diesem Fall ), und zweitens, wie klein "ist". klein". In diesem Fall definieren wir "klein" als eine Funktion, die höchstens polynomiell in wächst . In anderen Fällen haben wir strengere Anforderungen, beispielsweise "klein" soll in polynomisch sein .$\epsilon,\delta,n,size(c)$$1/\epsilon,1/\delta,n,size(c)$$\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$

Eine Standarddefinition in der Komplexitätstheorie ist die der Polynomzeit. Wir sagen, dass ein Algorithmus zum Lösen eines Problems effizient ist, wenn er bei einer Eingabe der Größe im Zeitpolynom in läuft, dh seine Laufzeit ist durch ein Polynom in . In Ihrer Terminologie könnten wir dies als für ein Polynom angeben . Wie zuvor, wenn für ein Polynompoly , dann tatsächlich für ein , und so ohne Verlust der Allgemeinheit wir kann annehmen, dass$n$$n$$T(n)$$n$$T(n) \leq poly(n)$$n$$T(n) \leq poly(n)$$poly(\cdot)$$T(n) \leq An^B$$A,B>0$$poly(n) = An^B$. Wir wollen uns aber nicht im Voraus für die Werte von . Wir freuen uns, solange einige Werte von funktionieren.$A,B$$A,B$

Ihr Fall ist ähnlich, nur das Polynom darf von mehreren Größen abhängen und nicht nur von einer Größe.