Complexité de l'échantillon - Sample complexity

La complexité de l' échantillon d'un algorithme d' apprentissage automatique représente le nombre d'échantillons d'apprentissage dont il a besoin pour apprendre avec succès une fonction cible.

Plus précisément, la complexité de l'échantillon est le nombre d'échantillons d'apprentissage que nous devons fournir à l'algorithme, de sorte que la fonction renvoyée par l'algorithme se situe dans une erreur arbitrairement petite de la meilleure fonction possible, avec une probabilité arbitrairement proche de 1.

Il existe deux variantes de la complexité des échantillons :

La variante faible fixe une distribution entrée-sortie particulière ;
La variante forte prend la complexité de l'échantillon dans le pire des cas sur toutes les distributions d'entrée-sortie.

Le théorème No Free Lunch, discuté ci-dessous, prouve qu'en général, la complexité de l'échantillon fort est infinie, c'est-à-dire qu'il n'y a pas d'algorithme qui peut apprendre la fonction cible globalement optimale en utilisant un nombre fini d'échantillons d'apprentissage.

Cependant, si nous ne nous intéressons qu'à une classe particulière de fonctions cibles (par exemple, uniquement des fonctions linéaires), alors la complexité de l'échantillon est finie et dépend linéairement de la dimension VC de la classe de fonctions cibles.

Définition

Soit un espace que nous appelons l'espace d'entrée, et un espace que nous appelons l'espace de sortie, et notons le produit . Par exemple, dans le cadre de la classification binaire, est généralement un espace vectoriel de dimension finie et est l'ensemble . ${\style d'affichage X}$ ${\style d'affichage Y}$ ${\style d'affichage Z}$ ${\style d'affichage X\fois Y}$ ${\style d'affichage X}$ ${\style d'affichage Y}$ ${\style d'affichage \{-1,1\}}$

Fixer un espace d'hypothèses de fonctions . Un algorithme d'apprentissage sur est une carte calculable de à . En d'autres termes, il s'agit d'un algorithme qui prend en entrée une séquence finie d'échantillons d'apprentissage et génère une fonction de à . Les algorithmes d'apprentissage typiques incluent la minimisation empirique des risques , sans ou avec régularisation de Tikhonov . ${\mathcal {H}}$ $h\colon X\à Y$ ${\mathcal {H}}$ $Z^{*}$ ${\mathcal {H}}$ ${\style d'affichage X}$ ${\style d'affichage Y}$

Fixez une fonction de perte , par exemple, la perte carrée , où . Pour une distribution donnée sur , le risque attendu d'une hypothèse (une fonction) est ${\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}$ ${\mathcal {L}}(y,y')=(y-y')^{2}$ ${\style d'affichage h(x)=y'}$ ${\style d'affichage \rho }$ ${\style d'affichage X\fois Y}$ $h\in {\mathcal {H}}$

{\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)

Dans notre contexte, nous avons , où est un algorithme d'apprentissage et est une séquence de vecteurs qui sont tous tirés indépendamment de . Définir le risque optimal $h={\mathcal {A}}(S_{n})$ ${\mathcal {A}}$ $S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}$ ${\style d'affichage \rho }$

{\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}} (h).

Définir , pour chacun . Notez qu'il s'agit d'une variable aléatoire et dépend de la variable aléatoire , qui est tirée de la distribution . L'algorithme est dit cohérent s'il converge probabiliste vers . En d'autres termes, pour tout , il existe un entier positif , tel que, pour tout , on a

h_{n}={\mathcal {A}}(S_{n})

{\style d'affichage n}

{\style d'affichage h_{n}}

{\style d'affichage S_{n}}

\rho ^{n}

{\mathcal {A}}

{\mathcal {E}}(h_{n})

{\mathcal {E}}_{\mathcal {H}}^{*}

\epsilon ,\delta >0

{\style d'affichage N}

{\style d'affichage n\geq N}

\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .

La complexité de l' échantillon de est alors le minimum pour lequel cela est vérifié, en fonction de , et . Nous écrivons la complexité de l'échantillon pour souligner que cette valeur de dépend de , et . Si n'est pas cohérent , alors nous définissons . S'il existe un algorithme pour lequel est fini, alors on dit que l'espace des hypothèses est apprenable .

{\mathcal {A}}

{\style d'affichage N}

\rho ,\epsilon

{\style d'affichage \delta }

N(\rho ,\epsilon ,\delta )

{\style d'affichage N}

\rho ,\epsilon

{\style d'affichage \delta }

{\mathcal {A}}

N(\rho ,\epsilon ,\delta )=\infty

N(\rho ,\epsilon ,\delta )

{\mathcal {H}}

En d'autres termes, la complexité de l'échantillon définit le taux de cohérence de l'algorithme : étant donné une précision et une confiance souhaitées , il faut échantillonner des points de données pour garantir que le risque de la fonction de sortie est dans les meilleurs possibles, avec une probabilité d'au moins . $N(\rho ,\epsilon ,\delta )$ ${\style d'affichage \epsilon }$ ${\style d'affichage \delta }$ $N(\rho ,\epsilon ,\delta )$ ${\style d'affichage \epsilon }$ ${\style d'affichage 1-\delta }$

Dans l' apprentissage probablement approximativement correct (PAC) , on se demande si la complexité de l'échantillon est polynomiale , c'est-à-dire si elle est limitée par un polynôme dans et . Si est polynomial pour un algorithme d'apprentissage, alors on dit que l'espace d'hypothèse est

PAC-learnable . Notez qu'il s'agit d'une notion plus forte que d'être apprenable.

N(\rho ,\epsilon ,\delta )

{\style d'affichage 1/\epsilon }

{\style d'affichage 1/\delta }

N(\rho ,\epsilon ,\delta )

{\mathcal {H}}

Espace d'hypothèse sans restriction : complexité d'échantillon infinie

On peut se demander s'il existe un algorithme d'apprentissage pour que la complexité de l'échantillon soit finie au sens fort, c'est-à-dire qu'il existe une borne sur le nombre d'échantillons nécessaires pour que l'algorithme puisse apprendre n'importe quelle distribution sur l'espace d'entrée-sortie avec un erreur cible spécifiée. Plus formellement, on se demande s'il existe un algorithme d'apprentissage , tel que, pour tout , il existe un entier positif tel que pour tout , on a ${\mathcal {A}}$ $\epsilon ,\delta >0$ ${\style d'affichage N}$ ${\style d'affichage n\geq N}$

\sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,

où , avec comme ci-dessus. Le théorème No Free Lunch dit que sans restrictions sur l'espace d'hypothèse , ce n'est pas le cas, c'est-à-dire qu'il existe toujours de "mauvaises" distributions pour lesquelles la complexité de l'échantillon est arbitrairement grande.

h_{n}={\mathcal {A}}(S_{n})

S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}

{\mathcal {H}}

Ainsi, afin de faire des déclarations sur le taux de convergence de la quantité

\sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),

il faut soit

contraindre l'espace des distributions de probabilité , par exemple via une approche paramétrique, ou ${\style d'affichage \rho }$
contraindre l'espace des hypothèses , comme dans les approches sans distribution. ${\mathcal {H}}$

Espace d'hypothèse restreint : complexité d'échantillon finie

Cette dernière approche conduit à des concepts tels que la dimension VC et la complexité de Rademacher qui contrôlent la complexité de l'espace . Un espace d'hypothèse plus petit introduit plus de biais dans le processus d'inférence, ce qui signifie qu'il peut être supérieur au meilleur risque possible dans un espace plus grand. Cependant, en limitant la complexité de l'espace d'hypothèse, il devient possible pour un algorithme de produire des fonctions plus uniformément cohérentes. Ce compromis conduit au concept de

régularisation .

{\mathcal {H}}

{\mathcal {E}}_{\mathcal {H}}^{*}

C'est un théorème de la théorie VC que les trois énoncés suivants sont équivalents pour un espace d'hypothèse : ${\mathcal {H}}$

${\mathcal {H}}$ est PAC-apprenable.
La dimension VC de est finie. ${\mathcal {H}}$
${\mathcal {H}}$ est une classe Glivenko-Cantelli uniforme .

Cela donne un moyen de prouver que certains espaces d'hypothèses sont apprenables par PAC, et par extension, apprenables.

Un exemple d'espace d'hypothèse pouvant être appris par PAC

$X=\mathbb {R} ^{d},Y=\{-1,1\}$ , et soit l'espace des fonctions affines sur , c'est-à-dire des fonctions de la forme pour certains . Il s'agit de la classification linéaire avec problème d'apprentissage décalé. Maintenant, notez que quatre points coplanaires dans un carré ne peuvent être brisés par aucune fonction affine, car aucune fonction affine ne peut être positive sur deux sommets diagonalement opposés et négative sur les deux autres. Ainsi, la dimension VC de est , elle est donc finie. Il s'ensuit la caractérisation ci-dessus des classes pouvant être apprises par PAC qui peuvent être apprises par PAC et, par extension, pouvant être apprises. ${\mathcal {H}}$ ${\style d'affichage X}$ $x\mapsto \langle w,x\rangle +b$ $w\in \mathbb {R} ^{d},b\in \mathbb {R}$ ${\mathcal {H}}$ ${\style d'affichage d+1}$ ${\mathcal {H}}$

Limites de complexité de l'échantillon

Supposons qu'il s'agisse d' une classe de fonctions binaires (fonctions à ). Alors, est -PAC-apprenable avec un échantillon de taille : ${\mathcal {H}}$ ${\style d'affichage \{0,1\}}$ ${\mathcal {H}}$ ${\style d'affichage (\epsilon ,\delta )}$

N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}

où est la dimension VC de . De plus, tout algorithme d'apprentissage -PAC pour doit avoir une complexité d'échantillon :

VC({\mathcal {H}})

{\mathcal {H}}

{\style d'affichage (\epsilon ,\delta )}

{\mathcal {H}}

N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}

Ainsi, la complexité de l'échantillon est une fonction linéaire de la dimension VC de l'espace d'hypothèse.

Supposons qu'il s'agisse d' une classe de fonctions à valeur réelle avec une plage dans . Alors, est -PAC-apprenable avec un échantillon de taille : ${\mathcal {H}}$ ${\style d'affichage [0,T]}$ ${\mathcal {H}}$ ${\style d'affichage (\epsilon ,\delta )}$

N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }} {\epsilon ^{2}}}{\bigg )}

où est la pseudo-dimension de Pollard de .

PD({\mathcal {H}})

{\mathcal {H}}

Autres réglages

En plus du cadre d'apprentissage supervisé, la complexité de l'échantillon est pertinente pour les problèmes d'

apprentissage semi-supervisé , y compris l' apprentissage actif , où l'algorithme peut demander des étiquettes à des entrées spécifiquement choisies afin de réduire le coût d'obtention de nombreuses étiquettes. Le concept de complexité de l'échantillon apparaît également dans l' apprentissage par renforcement, l'apprentissage en ligne et les algorithmes non supervisés, par exemple pour l' apprentissage par dictionnaire .

Efficacité en robotique

Une complexité élevée de l'échantillon signifie que de nombreux calculs sont nécessaires pour exécuter une recherche dans l'arbre Monte Carlo . C'est l'équivalent d'une recherche de force brute sans modèle dans l'espace d'état. En revanche, un algorithme à haute efficacité a une faible complexité d'échantillon. Les techniques possibles pour réduire la complexité de l'échantillon sont l'apprentissage métrique et l'apprentissage par renforcement basé sur un modèle.

Languages

In other projects