- Pondération de contextes
-
Les algorithmes de pondération de contextes (ou CM pour Context Mixing) constituent une famille d'algorithmes de compression de données sans perte, statistiques et adaptatifs.
La pondération de contextes est encore aujourd'hui un domaine de recherche active en compression de données, en intelligence artificielle et en apprentissage automatique.
Sommaire
Algorithme
Principe
L'objectif de la pondération de contextes est d'apporter une solution au principal problème des algorithmes de prédiction par reconnaissance partielle, à savoir la difficulté de concevoir un modèle statistique capable de représenter n'importe quel type de données que l'on voudrait pouvoir compresser.
Un CM utilise plusieurs modélisations statistiques indépendantes (donc plus simples) pour évaluer la probabilité des différents symboles.
En regroupant ces différentes modélisations ayant chacune des avantages propres, la pondération de contexte est censée offrir une fiabilité supérieure dans la prédiction que chaque modélisation prise séparément.
Les différentes entrées d'un CM sont en général adaptées à des types de données différents. Par exemple un CM peut mixer les sorties d'un prédicteur spécialisé pour le texte et d'un autre spécialisé pour les images, chacun étant à priori plus performant sur le type de données pour lequel il est spécialisé ; il devrait ainsi approcher les performances du prédicteur spécialisé pour le texte sur le texte et celles du prédicteur spécialisé pour les images sur les images.
Prédicteur
Le rôle d'un prédicteur est d'estimer, dans un contexte donné, la probabilité d'apparition des différents symboles. La façon dont le prédicteur évalue cette probabilité est indépendante de l'algorithme de pondération de contextes ; en fait, chaque prédicteur pourrait être utilisé indépendamment en entrée d'un codage arithmétique, dans le cadre d'un algorithme de prédiction par reconnaissance partielle, par exemple.
L'apport de la pondération de contextes est de multiplier des prédicteurs dont les modèles statistiques se complètent : pour que la démarche ait un intérêt, il faut que chaque prédicteur soit meilleur que les autres dans au moins un domaine.
Mixeur
Le rôle d'un mixeur est de pondérer les estimations de probabilité des différents prédicteurs afin de donner le plus d'importance possible à la meilleure prédiction et de limiter au maximum les erreurs dues à des prédictions erronées. Le mixeur est donc le cœur de la pondération de contextes.
Le mixeur le plus simple possible effectue une moyenne des estimations des différents prédicteurs. En pratique, ce type de mixeur n'a qu'un intérêt très limité : cela revient à lisser les fluctuations dans la qualité des différentes prédictions.
Les mixeurs plus avancés ajustent leur pondération au cours de la compression. Cela peut être fait suivant le type de flux en entrée (le mixeur favorise alors certains prédicteurs de façon prédéfinie), ou suivant un algorithme d'optimisation par apprentissage automatique comme l'algorithme du gradient ou un réseau de neurones (le mixeur favorise alors certains prédicteurs de façon intelligente). En pratique, les deux approches sont souvent combinées.
Estimation secondaire
Afin de rendre la prédiction finale la plus sûre possible, certaines implémentations intègrent une estimation secondaire (SSE pour Secondary Symbol Estimation).
Il s'agit d'utiliser un prédicteur supplémentaire (différent des prédicteurs déjà utilisés), associant un contexte et la prédiction pondérée telle qu'obtenue par le mixeur pour estimer une nouvelle fois la probabilité des différents symboles.
Il est bien évidemment possible de procéder à plusieurs SSE et d'utiliser plusieurs mixeurs ; la seule contrainte étant d'utiliser la même architecture à la compression et à la décompression. Il faut néanmoins compter avec les problèmes de performance inhérents à la multiplication des calculs.
À titre d'exemple, PAQAR utilise 7 types de prédicteurs, 99 contextes distincts (et autant d'instances de prédicteur), 12 mixeurs de premier niveau, chacun d'entre eux donne lieu à une estimation secondaire, ces 12 estimations secondaires sont suivies de 5 estimations tertiaires et un mixeur de second niveau délivre la prédiction finale.
Propriétés
Un algorithme de pondération de contextes est en général un algorithme symétrique. Cela signifie qu'il fait la même chose à la compression et à la décompression. Cela signifie aussi que sa vitesse est la même dans les deux cas (si l'on ne tient pas compte des subtilités des entrées-sorties), et que la quantité de mémoire nécessaire (pour stocker les mixeurs, les prédicteurs et leurs contextes) est identique.
Dans certaines implémentations, néanmoins, certain prédicteurs très spécifiques (ne travaillant que sur un type de données bien précis, par exemple) sont activés ou désactivés à la compression, suivant qu'il ait été jugé opportun de les utiliser ou non. Dans ce cas, le temps nécessaire à l'estimation de l'utilité de ces différents prédicteurs s'ajoute à la compression, mais pas à la décompression. Un exemple de ce cas de figure est le prédicteur spécifique à la recompression des fichiers JPEG du logiciel PAQ, qui n'est activé que lorsqu'une image JPEG a été détecté dans le flux de symboles à compresser.
Performances
Les taux de compression obtenus par les CM sont parmi les meilleurs obtenus aujourd'hui et ce, quel que soit le type de données à compresser (à l'exception, bien entendu des données aléatoires).
La quantité de mémoire nécessaire est en général importante. Chaque prédicteur a ses propres besoins et le ou les mixeurs peuvent également nécessiter quelques ressources (par exemple dans le cas d'un réseau de neurones).
La vitesse est le point faible des CM. Ils sont d'autant plus lents que le nombre de prédicteurs (ou de contextes) est important. Certains mixeurs intelligents désactivent dynamiquement les prédicteurs et les contextes non pertinents pour accélérer les calculs.
Un CM est parallélisable, du moins en théorie, car les prédicteurs sont presque toujours indépendants. La complexité liée à la synchronisation des différentes prédictions au niveau des mixeurs, et à la nécessité de maintenir les modèles statistiques à jour à chaque nouveau symbole fait qu'en pratique, les principales implémentations de CM sont purement séquentielles.
Implémentations
L'implémentation la plus représentative d'un algorithme de pondération de contextes et sans doute le projet communautaire PAQ initié par Matt Mahoney, dont dérivent d'autres implémentations plus ou moins connues comme PAQAR, PAsQDa, PWCM, LPAQ ou ZPAQ.
ASH, CCM et NanoZip sont d'autres implémentations assez connues.
À ce jour, la seule implémentation intégrée dans un archiveur destiné au grand public reste PWCM, qui est utilisé dans WinRK.
Voir aussi
Articles connexes
Liens externes
Catégories :- Algorithme de compression sans perte
- Théorie de l'information
Wikimedia Foundation. 2010.
