Définition du modèle d'apprentissage PAC

Le modèle d'apprentissage probablement correct (PAC) est défini comme suit:

Une classe conceptuelle $C$ est dit être PAC-apprenant s'il existe un algorithme $A$ et une fonction polynomiale $poly(·,·,·,·)$de telle sorte que pour tout $ε>0$ et $δ>0$ , pour toutes les distributions $D$ sur $X$ et pour tout concept cible $c∈C$ , ce qui suit vaut pour toute taille d'échantillon $m≥poly(1/ε,1/δ,n,size(c))$ :

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

où $R(hs)$ est l'erreur de généralisation sur un échantillon $S$ de taille $m$ contenant des instances de variable $X$ suivant la distribution $D$ et la $size(c)$ est le coût maximal de la représentation informatique de $c∈C$ .

Je sais que $poly(1/ε,1/δ,n,size(c))$ est un polynôme. Mais quelle est la forme explicite de $poly(1/ε,1/δ,n,size(c))$ ? Quelles sont les variables? Quel est son degré?

Il n'y a aucune contrainte sur autre que le fait qu'il s'agit d'un polynôme ou, plus généralement, d'une fonction bornée polynomiale (c'est-à-dire une fonction bornée par un polynôme); la différence n'a pas d'importance dans ce cas. Sans perte de généralité, on peut supposer que pour certains , .$poly(\cdot,\cdot,\cdot,\cdot)$$A,B > 0$$poly(x,y,z,w) = A(xyzw)^B$

La définition tente de modéliser la situation selon laquelle seul un petit nombre d'échantillons est nécessaire pour apprendre le concept. Afin de quantifier "petit", nous devons d'abord décider par rapport à quelles quantités il va être petit (dans ce cas, ), et deuxièmement, comment petit est " petit". Dans ce cas, nous définissons "petit" comme toute fonction grandissant au plus polynomialement en . Dans d'autres cas, nous avons des exigences plus strictes, disons que nous voulons que "petit" soit polynomial dans .$\epsilon,\delta,n,size(c)$$1/\epsilon,1/\delta,n,size(c)$$\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$

Une définition standard dans la théorie de la complexité est celle du temps polynomial. Nous disons qu'un algorithme pour résoudre un problème est efficace si sur une entrée de taille il s'exécute en polynôme temporel en , c'est-à-dire que son temps d'exécution est délimité par un polynôme en . Dans votre terminologie, nous pourrions dire ceci comme pour un polynôme . Comme précédemment, si pour certains polynômes , alors en fait pour certains , et donc sans perte de généralité nous peut supposer 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$. Mais nous ne voulons pas décider à l' avance sur les valeurs de . Nous sommes heureux tant que certaines valeurs de fonctionnent.$A,B$$A,B$

Votre cas est similaire, seul le polynôme est autorisé à dépendre de plusieurs quantités plutôt que d'une seule quantité.