Definição do modelo de aprendizado do PAC

O modelo de aprendizado provavelmente aproximadamente correto (PAC) é definido como:

Uma classe de conceito $C$ é dito ser aprendido por PAC se existe um algoritmo $A$ e uma função polinomial $poly(·,·,·,·)$de modo que, para qualquer e , para todas as distribuições em e para qualquer conceito-alvo , o seguinte vale para qualquer tamanho de amostra :$ε>0$$δ>0$$D$$X$$c∈C$$m≥poly(1/ε,1/δ,n,size(c))$

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

onde é o erro de generalização sobre uma amostra de tamanho contendo instâncias da variável após a distribuição e o é o custo máximo da representação computacional de .$R(hs)$$S$$m$$X$$D$$size(c)$$c∈C$

Eu sei que é um polinômio. Mas qual é a forma explícita de ? Quais são as variáveis? Qual é o seu grau?$poly(1/ε,1/δ,n,size(c))$$poly(1/ε,1/δ,n,size(c))$

Não há restrições no além de ser um polinômio ou, mais geralmente, uma função limitada polinomialmente (ou seja, uma função limitada por um polinômio); a diferença não importa neste caso. Sem perda de generalidade, pode-se assumir que, para alguns , .$poly(\cdot,\cdot,\cdot,\cdot)$$A,B > 0$$poly(x,y,z,w) = A(xyzw)^B$

A definição está tentando modelar a situação em que apenas um pequeno número de amostras é necessário para aprender o conceito. Para quantificar "pequeno", precisamos primeiro decidir com relação a quais quantidades serão pequenas (neste caso, ) e, segundo, quão pequena é " pequeno". Nesse caso, definimos "pequeno" como qualquer função que cresça no máximo polinomialmente em . Em outros casos, temos requisitos mais rigorosos, digamos que queremos que "pequeno" seja polinomial em .$\epsilon,\delta,n,size(c)$$1/\epsilon,1/\delta,n,size(c)$$\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$

Uma definição padrão na teoria da complexidade é a do tempo polinomial. Dizemos que um algoritmo para resolver algum problema é eficiente se, em uma entrada de tamanho é executado no tempo polinomial em , ou seja, seu tempo de execução é limitado por algum polinômio em . Em sua terminologia, podemos afirmar isso como para algum polinômio . Como antes, se para algum polinômio , então, de fato, para alguns e, portanto, sem perda de generalidade, podemos assumir 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$. Mas nós não queremos decidir com antecedência sobre os valores de . Estamos felizes desde que alguns valores de funcionem.$A,B$$A,B$

Seu caso é semelhante, apenas o polinômio pode depender de várias quantidades, em vez de apenas uma quantidade.