Definición del modelo de aprendizaje PAC

El modelo de aprendizaje probablemente aproximadamente correcto (PAC) se define como:

Se dice que una clase de concepto puede aprenderse con PAC si existe un algoritmo y una función polinómica tal que para cualquier ε> 0 y δ> 0 , para todas las distribuciones D en X y para cualquier concepto objetivo c∈C , se cumple lo siguiente para cualquier tamaño de muestra m≥poly (1 / ε, 1 / δ, n, tamaño (c)) :$C$$A$$poly(·,·,·,·)$$ε>0$$δ>0$$D$$X$$c∈C$$m≥poly(1/ε,1/δ,n,size(c))$

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

donde $R(hs)$ es el error de generalización sobre una muestra $S$ de tamaño $m$ contiene instancias de la variable $X$ después de la distribución $D$ y el $size(c)$ es el costo máximo de la representación computacional de $c∈C$ .

Sé que $poly(1/ε,1/δ,n,size(c))$ es un polinomio. Pero, ¿cuál es la forma explícita de $poly(1/ε,1/δ,n,size(c))$ ? ¿Cuáles son las variables? ¿Cuál es su grado?

No hay restricciones en aparte de ser un polinomio, o más generalmente, una función polinomialmente limitada (es decir, una función limitada por un polinomio); La diferencia no importa en este caso. Sin pérdida de generalidad, se puede suponer que por alguna , .$poly(\cdot,\cdot,\cdot,\cdot)$$A,B > 0$$poly(x,y,z,w) = A(xyzw)^B$

La definición está tratando de modelar la situación de que solo se necesita un pequeño número de muestras para aprender el concepto. Para cuantificar "pequeño", primero debemos decidir con respecto a qué cantidades será pequeño (en este caso, ), y segundo, qué tan pequeño es " pequeña". En este caso, definimos "pequeño" como cualquier función que crece como máximo polinomialmente en . En otros casos, tenemos requisitos más estrictos, digamos que queremos que "pequeño" sea polinomial en .$\epsilon,\delta,n,size(c)$$1/\epsilon,1/\delta,n,size(c)$$\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$

Una definición estándar en la teoría de la complejidad es la del tiempo polinomial. Decimos que un algoritmo para resolver algún problema es eficiente si en una entrada de tamaño se ejecuta en tiempo polinomial en , es decir, su tiempo de ejecución está limitado por algún polinomio en . En su terminología, podríamos decir esto como para algún polinomio . Como antes, si para algún polinomio , entonces, de hecho, para algún , y así sin pérdida de generalidad, puede suponer que$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$. Pero no queremos que decidir de antemano en los valores de . Estamos contentos mientras algunos valores de funcionen.$A,B$$A,B$

Su caso es similar, solo el polinomio puede depender de varias cantidades en lugar de solo una cantidad.