Codage parcimonieux 📖 Wikipedia

Plus rigoureusement, considérons une entrée vectorielle ${\displaystyle x}$ . Alors, considérant qu'on a à notre disposition un dictionnaire de motifs élémentaires ${\displaystyle D}$ , matrice contenant dans chaque colonne un motif de la même taille que ${\displaystyle x}$  (${\displaystyle x\in \mathbb {R} ^{m}}$  et ${\displaystyle D\in \mathbb {R} ^{m\times k}}$ ), il existe ${\displaystyle (\alpha _{i})_{i\in [1..k]}}$  tel que ${\displaystyle x\simeq D.\alpha }$ .

Plus généralement, pour un jeu de données de taille ${\displaystyle d}$ , le problème revient à décomposer la matrice ${\displaystyle X\in \mathbb {R} ^{m\times d}}$  en produit de deux autres matrices plus simples : la propriété de parcimonie impose qu'il y ait le plus de ${\displaystyle 0}$  possible dans le vecteur de poids alpha ainsi que dans le dictionnaire. Cette condition se traduit par le fait que l'on veut reproduire l'entrée avec le moins de motif possible^[1].

On peut de plus rajouter une condition sur le dictionnaire afin que les valeurs des motifs n'explosent pas lorsque l'on diminue les poids. Pour cela, il est classique après chaque apprentissage de projeter les colonnes du dictionnaire sur la boule unité, à savoir:

${\displaystyle B=\{D_{j}\in \mathbb {R} ^{m}}$  tq ${\displaystyle \|D_{j}\|_{2}\leqslant 1\}}$ 

La pratique courante est de découper l'entrée en petites fenêtres de taille fixe afin d'avoir à traiter des entrées de taille constante, quitte à faire du zéro-padding pour compléter une fenêtre qui dépasse de l'entrée.

Pour le codage parcimonieux, on considère souvent la fonction de coût suivante pour une entrée ${\displaystyle x}$ :

${\displaystyle l(x,D)={\frac {1}{2}}\|x-D\alpha \|_{2}^{2}+\lambda |\alpha |_{1}}$ 

Le premier terme correspond à la distance de l'entrée reconstruite par rapport à l'entrée originale tandis que le second terme correspond à la condition de parcimonie.

Toute la difficulté de l'apprentissage pour le codage parcimonieux est d'apprendre à la fois un dictionnaire ainsi que les poids. Pour ce faire, on fixe alternativement un des paramètres pour entrainer l'autre à l'aide d'une descente de gradient stochastique^[2].

Les algorithmes les plus utilisés pour faire cela sont LARS et Frank-Wolfe ^[2]

Des améliorations peuvent être apportées à la construction précédente en rajoutant des conditions sur le dictionnaire ou sur les poids. On peut notamment montrer que l'ajout de l'invariance par translation via une convolution apporte des résultats meilleurs et permettent d'obtenir un dictionnaire plus complexe car il y a moins d'éléments redondants dans celui-ci^[3].

•   Portail des neurosciences
•   Portail des probabilités et de la statistique
•   Portail de l'informatique théorique