Description
Vous trouverez ici une classe C++ autonome pouvant mesurer la complexité statistique d'un système. La théorie derrière ce code à une longue histoire, plus de 30 ans de recherches. Vous trouverez plus de détails dans cet article par Shalizi et al, et encore dans celui-ci, par le même auteur, sous la section "Grassberger-Crutchfield-Young Statistical Complexity". Cette théorie est également connue comme les états causaux (causal states), elle puise de fortes racines dans les ε-machines, et bien plus encore.
Le but de ce code est d'étendre la méthode afin de la rendre incrémentale, de sorte que de nouvelles observations puissent être prises en compte au fur et à mesure où elles arrivent: Les groupes (états causaux) sont mis à jour, et les estimations de complexité sont réévaluées efficacement. De même, il y a la possibilité de supprimer les points les plus anciens dans le cas où le système ne serait pas stationnaire, où les vieilles observations ne sont plus comparables aux nouvelles.
Ce code est autonome (pas de dépendence externe), générique (applicable à n'importe quel type utilisateur), simple à utiliser (voir ci-dessous), et consiste en un unique fichier à inclure directement dans votre projet. L'agorithme est décris dans cet article et également avec plus de détails dans la section 5.1 de ma dissertation. Je fournis ce code ici dans le but qu'il soit utile, merci de le réutiliser si vous le souhaitez!
Exemples
Ce premier exemple montre un automate cellulaire unidimensionel (CA) exécutant la règle 146, avec des conditions initiales aléatoires, dans un monde cyclique. La partie gauche de l'image est le champ brut de l'automate, la partie droite montre le filtre en action. Les motifs détectés sont difficile à suivre dans le champ brut, mais clairement visibles dans le champ de complexité. Le résultat est comparable aux images obtenues avec Cimula, décrites dans cet article. La phase transiente initiale a été omise et toutes les observations sont collectées avant de calculer les complexité locales, avec la commande: ./CA_Complexity -k200 -n -p6 -f6 -r146 -w400 -t300 -s11
Voici la règle 54 en action. L'image est prise dès le début, incluant les conditions initiales aléatoires. Les observations sont ici prisent en compte incrémentalement ligne par ligne. L'algorithme "apprend" rapidement le motif de fond, qui s'efface comme étant "peu complexe". ./CA_Complexity -r54 -w400 -t300
Il s'agit de la fameuse règle 110. Les états transients ont été supprimés et la taille des cônes espace-temps choisis afin de rendre les interactions plus visibles. ./CA_Complexity -k500 -n -p6 -f5 -r110 -w400 -t300 -s6
Le code
Vous pouvez télécharger ici la dernière version (1.0) contenant les fichiers ci-dessous et un Makefile. Vous trouverez dans l'archive:
- CausalStateAnalyzer.h: La classe principale. Spécialisez-la avec vos types pour les cones espace-temps passés et futurs. Puis fournissez-lui les observations sous la forme de paires cone passé/cone futur. Vous aurez les estimations de complexité incrémentalement, à la demande. Voire aussi le guide rapide ci-dessous.
- CA_Complexity.cpp: Un exemple d'utilisation, avec des automates cellulaires. Il s'agit du code qui a produit les images ci-dessus. Dispose d'un mode graphique, ./CA_Complexity -h produit un message d'aide.
Pour information l'analyseur contient désormais une version de la fonction gamma incomplète, optimisée pour ses propres besoins. Cette nouvelle version a été implémentée indépendemment de tout code existant. Elle permet d'éviter de devoir lier le programme à un fichier externe, comme les classes de tests statistiques provenant du projet CSSR qui étaient utilisées dans les premières versions. La nouvelle version du test Khi-carré est à la fois autonome et beaucoup plus rapide.
Vous trouverez également ici le code source de l'expérience détaillée dans la section 5.1 de ma dissertation.
Guide d'utilisation
- Définissez les types pour vos cônes espace-temps passés et futurs. Par exemple des entiers utilisés comme ID.
Créez ensuite l'objet analyseur:
CausalStateAnalyzer<int,int> analyzer; - Surveillez les correspondances passé/futur de votre système et fournissez-les par paire:
analyzer.addObservation(past, future); - Validez les observations quand vous pensez en avoir suffisament. Ceci peut être fait après chaque observation, ou tout à la fin, ou par lots de 12, ou en fait quand vous voulez.
analyzer.commitObservations(); - A ce stade les valeurs de complexité sont disponibles:
Les complexités locales sont retournées sous forme de vecteur, pour chaque paire d'observation fournie, dans cet ordre.
vector<float>& complexities = analyzer.getComplexities();
La complexité globale est le nombre de bits qui serait nécessaire pour encoder tous les états causaux:
float globalComplexity = analyzer.getGlobalComplexity();
Vous pouvez maintenant retourner à l'étape 2 et continuer à fournir de nouvelles observations, etc.
N'oubliez pas de valider les observations avant de lire les nouvelles valeurs de complexité.
Optionel:
- Vous pouvez supprimer des observations, ce qui est particulièrement utile pour des systèmes (lentement) non-stationaires où la complexité évolue au cours du temps.
analyzer.removeObservation(too_old_past, too_old_future); - Vous pouvez aussi appeler la fonction "getScaledComplexities" pour obtenir des valeurs dans [0..1], mises à l'échelle en utilisant les min/max de complexité observés. Pratique par exemple pour créer des images en échelle de gris.
vector<float>& complexities = analyzer.getScaledComplexities();
Historique
v1.0: Pas de changement. La version 0.8 a été renommée en 1.0 car le code est stable, et aussi symboliquement pour correspondre à ma dissertation de Doctorat et à un article publié.
v0.8: Example CA fixé. Légère amélioration des performances.
v0.7: Bug corrigé dans les fréquences des distributions. Ajout de nouvelles fonctionalités pour l'exemple sur les automates cellulaires.
v0.6: Optionel: La classe peut maintenant être sérialisée, ce qui est particulièrement utile pour sauvegarder/reprendre des calculs.
v0.5: Ajout de tests pour gérer correctement la suppression de données.
v0.4: Ecrabouillage d'un horrible bug, changement de l'API pour incréments en 2 phases, introduction d'optimisations en assembleur, et d'autres améliorations de performance.
v0.3: Améliorations des performances, suppression de la dépendence vers les classes de test du projet CSSR.
v0.2: Correction de bugs et amélioration des performances.
v0.1: Première version publique.
