Descripteurs aléatoires

En statistiques et en apprentissage automatique, le calcul de descripteurs aléatoires est une technique d'approximation permettant d'évaluer de manière approchée certains noyaux définis positifs. Cette technique consiste à construire un plongement du domaine de définition du noyau vers un espace euclidéen de faible dimension qui approche la géométrie induite par le noyau.

Le calcul des descripteurs pour un ensemble de points permet de construire une approximation de faible rang de la matrice à noyau associée, et par conséquent de développer des approximations de méthodes à noyaux et de processus gaussiens ayant des coûts de calculs réduits.

Les descripteurs sont typiquement construits en utilisant une approximation de Monte-Carlo d'une représentation intégrale du noyau, d'où leur nature « aléatoire ».

La méthode a été initialement proposée par Ali Rahimi et Benjamin Recht en 2008^[1].

La construction repose sur une approximation d'une représentation intégrale du noyau. Soit ${\displaystyle \kappa :\mathbb {R} ^{d}\times \mathbb {R} ^{d}\rightarrow \mathbb {R} }$ un noyau continu et invariant par translation, c.-à-d. de la forme ${\displaystyle \kappa (x,y)=K(x-y)}$. Par le théorème de Bochner, un tel noyau admet une représentation intégrale de la forme

${\displaystyle \kappa (x,y)=\int _{\mathbb {R} ^{d}}\exp(i\omega ^{\mathsf {T}}(x-y))\mathrm {d} p(\omega )}$

où ${\displaystyle p}$ est la transformée de Fourier de ${\displaystyle K}$.

Un descripteur aléatoire est une fonction ${\displaystyle \phi :\mathbb {R} ^{d}\rightarrow \mathbb {R} ^{m}}$ construite telle que la quantité ${\displaystyle \langle \phi (x),\phi (y)\rangle }$ est une approximation numérique de la représentation intégrale du noyau (uniformément pour tous ${\displaystyle x,y}$).

La définition n'est donc pas unique, mais les descripteurs les plus courants sont obtenus par une approximation de Monte-Carlo de l'intégrale, c.-à-d. reposent sur le tirage de ${\displaystyle f}$ vecteurs de fréquence ${\displaystyle \omega _{1},\dots ,\omega _{f}\in \mathbb {R} ^{d}}$ tirés de manière i.i.d. selon ${\displaystyle p}$ :

• ${\displaystyle \phi (x)=f^{-1/2}[\cos(\omega _{1}^{\mathsf {T}}x),\sin(\omega _{1}^{\mathsf {T}}x),\dots ,\cos(\omega _{f}^{\mathsf {T}}x),\sin(\omega _{f}^{\mathsf {T}}x)]^{\mathsf {T}}}$
• ${\displaystyle \phi (x)=f^{-1/2}{\sqrt {2}}[\cos(\omega _{1}^{\mathsf {T}}x+b_{1}),\dots ,\cos(\omega _{f}^{\mathsf {T}}x+b_{f})]^{\mathsf {T}}}$ où les ${\displaystyle (b_{i})_{1\leq i\leq f}}$ sont tirés i.i.d. et uniformément sur ${\displaystyle [0,2\pi ]}$

• Portail des probabilités et de la statistique