Context mixing

Context mixing

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 une descente de 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érents 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 CMs 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érale 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 CMs. 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

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Pond%C3%A9ration de contextes ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Context mixing de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Context mixing — is a type of data compression algorithm in which the next symbol predictions of two or more statistical models are combined to yield a prediction that is often more accurate than any of the individual predictions. For example, one simple method… …   Wikipedia

  • Context tree weighting — The context tree weighting method (CTW) is a lossless compression and prediction algorithm by Willems, Shtarkov, and Tjalkens (1995) . The CTW algorithm is among the very few such algorithms that offer both theoretical guarantees and good… …   Wikipedia

  • Code-mixing — Sociolinguistics Areas of study Accent · Dialect Discourse analysis Language varieties …   Wikipedia

  • PAQ — A sample session of PAQ8O PAQ is a series of lossless data compression archivers that have evolved through collaborative development to top rankings on several benchmarks measuring compression ratio (although at the expense of speed and memory… …   Wikipedia

  • Lossless data compression — is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be… …   Wikipedia

  • Dynamic Markov compression — (DMC) is a lossless data compression algorithm developed by Gordon Cormack and Nigel Horspool [1]. It uses predictive arithmetic coding similar to prediction by partial matching (PPM), except that the input is predicted one bit at a time (rather… …   Wikipedia

  • ROLZ — (от англ. Reduced Offset LZ алгоритм Лемпела Зива с сокращёнными смещениями)  словарный алгоритм сжатия данных, близкий к LZ77, но использующий некоторые контекстные приёмы для уменьшения числа активных смещений. Само понятие ROLZ… …   Википедия

  • Data compression — Source coding redirects here. For the term in computer programming, see Source code. In computer science and information theory, data compression, source coding or bit rate reduction is the process of encoding information using fewer bits than… …   Wikipedia

  • Feminist political ecology — is a synthesis of the perspectives taken by several different feminisms, specifically those of ecofeminism, feminist environmentalism, socialist feminism, feminist poststructuralism and environmentalism. It adds to this mix the political… …   Wikipedia

  • PAQ — ist ein Kompressionsprogramm zur komprimierten Archivierung von Dateien, das im Vergleich zu anderen Formaten meist die höchste Datenkompressionsrate aufweist, auf Kosten sehr langer Laufzeiten und hohem Speicherverbrauch. PAQ ist ein… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”