Présentation

On dispose d'une fonction de coût/utilité pour comparer les prédictions faites sur un système avec ce qui ce passe réellement. On aimerait obtenir:

Les décisions optimales a prendre afin de maximiser la fonction d'utilité.
L'utilité moyenne espérée.
Des évènements quand un des deux paramètres ci-dessus change.

Cet article (version preprint) présente l'aspect théorique de ce problème ainsi qu'en algorithme pour calculer les objets ci-dessus à partir des données et de la fonction de coût/utilité.

Le code source de l'implémentation de référence est disponible comme logiciel Libre, aux termes de la GNU LGPL v2.1 ou plus.

Des exemples applicatifs sont fournis ci-dessous et détaillés dans l'article.

Détails

Prédictions dans un contexte physique

Dans un contexte physique le transfert d'information est limité par la vitesse de la lumière. Le « présent » d'un système est défini comme un seul point dans l'espace-temps. Ceci est à mettre en contraste avec les systèmes dynamiques, où le « présent » est constitué de l'intégralité du vecteur d'état (la ligne sur la figure ci-dessous). Dans le cas qui nous intéresse ici, il n'y a pas de propagation instantannée de l'information, et seule une petite partie du vecteur d'état est disponible.

Le cône espace-temps passé est ici défini comme l'ensemble des points qui ait pu avoir une influence causale sur le présent. Le cône futur est de même défini comme l'ensemble des points ayant pu être influencés par le présent. Pour prédire correctement un point F dans le cône futur, il faut potentiellement disposer des points dans le cône passé de F. Alors qu'il est possible de disposer de certains d'entre eux comme P, dans le cône passé du système, le problème est que certains points comme O sont en dehors et non accessibles. Mais tant P que O font partie du cône passé de F, dans notre propre futur. La conséquence est que même pour un système déterministe on obtient une distribution statistique de futurs pour un passé observé donné. En d'autres termes, les conditions aux limites ou dans des régions inaccessibles peuvent déterminer une partie du futur.

Considérons maintenant le regroupement de deux cônes passés x₁^- et x₂^- s'ils ont la même distribution de futurs x⁺: p(x⁺|x₁^-)=p(x⁺|x₂^-). Supposons que le point P dans le passé ait une valeur différente pour les deux passés x₁^- et x₂^-. Il n'y a alors aucun moyen de retrouver quelle était la valeur de P par de nouvelles observations. On ne peut utiliser la connaissance obtenue dans le futur par ces observations pour décider entre x₁^- et x₂^- puisque p(x⁺|x₁^-)=p(x⁺|x₂^-). En pratique ces deux passés sont donc équivalents. Mathématiquement la relation d'équivalence associée x₁^- ≡ x₂^- partitionne le passé du système en ensembles σ(x^-)={ y^-: p(x⁺|y^-)=p(x⁺|x^-)}.

Les ensembles σ sont appelés les états causaux du système (cf Cosma Shalizi's Thesis). Dans un cadre discret une nouvelle observation donne lieu à une transition entre un état σ₁ et un état σ₂. Les états causaux et leurs transitions forment un automate déterministe, l'ε-machine (cf cet article par James Crutchfield and Karl Young). Un résultat intéressant est l'abstraction des dépendances du passé dans les états causaux. Les transitions entre les états incluent toutes les dépendances du passé pouvant avoir une influence sur le futur, et l'ε-machine forme en fait un graph Markovien.

La construction des états causaux n'est pas limitée aux cônes espace-temps. On peut également regrouper ensemble des données (paramètres) x∊X en fonction des distributions de probabilités conditionnelles p(z|x) pour des points z∊Z d'un espace de prédictions. La même relation d'équivalence peut alors être définie comme ci-dessus. Et on peut appeler états causaux les classes d'équivalence induites par cette relation par analogie (ou abus), même si aucune notion de causalité n'est alors explicitement introduite.

Introduction d'une fonction d'utilité

La description précédente ne distingue pas les futurs qui ont des conséquences importantes où anodines pour l'observateur. Par exemple, administrer un médicament à un patient peut causer des effets secondaires graves. L'approche des états causaux est de regarder p(effet|médicament), mais ne spécifie pas si l'effet est désiré ou non. En pratique on devrait tenir compte de nombreux paramètres comme l'état du patient quand on lui donne le médicament, etc. Il s'agit juste ici d'un exemple d'illustration où on veut prédire un effet (espace Z) à partir d'un médicament (espace X).

L'idée est alors d'introduire une fonction d'utilité U(y,z) pour quantifier la conséquence de prédire y∊Z (l'effet que l'on pense va se produire) alors qu'en fait c'est l'effet z qui apparaît. Par exemple, si on donne un médicament pour soigner le mal de tête mais que le patient se retrouve avec un mal au ventre en plus du mal de tête qui n'a pas disparu, alors l'utilité de la prédiction initiale n'est pas très bonne.

Que se passe-t'il si on regroupe maintenant les médicaments en tenant compte de leur utilité espérée E[U(effet|médicament)]=E[U(y|x)]=∫_z∊ZU(y,z)p(z|x) au lieu de simplement les probabilités conditionnelles p(effet|médicament) ? On peut alors:

Regrouper x₁ et x₂ si l'effet d'utilité espérée maximale est le même. Ceci permet de classer les médicaments par catégorie, comme ceux pour le mal de tête et ceux pour le mal de ventre. Mais ça ne dit rien sur les effets secondaires.
Regrouper x₁ et x₂ quand l'utilité maximale attendue est la même. Ceci permet de classer les médicaments en fonction de leur puissance, et éventuellement placer les plus puissants seulement sur ordonnance. Mais cela n'indique pas quel est l'effet attendu pour chaque médicament.
Faire les deux à la fois.

En termes techniques:

Le premier cas correspond à x₁ ≡ x₂ quand argmax_y∊ZE[U(y|x₁)]=argmax_y∊ZE[U(y|x₁)]. Les classes d'équivalence sont les états d'iso-prédiction.
Le second cas correspond à x₁ ≡ x₂ quand max_y∊ZE[U(y|x₁)]=max_y∊ZE[U(y|x₁)]. Les classes d'équivalence sont les états d'iso-utilité.
Le troisième cas correspond à l'intersection des deux premiers. Les classes d'équivalences sont les états décisionnels.

L'article donne plus de détails. Le nom "état décisionnel" vient de l'hypothèse que la fonction d'utilité encode tout ce que l'utilisateur à besoin de savoir pour prendre une décision.

Si comme supposé dans la thèse susmentionnée « les structures émergentes sont des sous-machines de l'ε-machine », alors une conséquence intéressante est que les états décisionnels sont les structures émergentes correspondantes à la fonction d'utilité. Une autre conséquence est que les transitions entre états décisionnels correspondent à des évènements du système qui provoquent un changement de décision. D'où la réponse au problème posé en introduction.

Exemples applicatifs

Filtrage d'image

On peut filtrer une image en fonction de la difficulté de prédire un point en regardant ses voisins. On peut alors s'attendre à ce que les régions avec un fond uniforme (comme un ciel bleu) seront assez simples à prédire. Alors que les bords et autres transitions abruptes sont plus difficiles. Démonstration :

D'autres exemples et conditions d'applicabilité sont données dans l'article.

Reconstruction de modèle Markoviens sous-jacent

Les ε-machines sont connues comme étant l'automate cellulaire minimal et optimal pouvant reproduire statistiquement les données d'origine. L'introduction d'une fonction d'utilité donne des sous-machines de l'ε-machine, où les états sont distincts quand leur utilité attendue ou les prédictions optimales sont différentes.

Cf l'article pour un exemple d'automate reconstruit.

Télécharger le code source

L'implémentation de référence est disponible en logiciel libre aux termes de la GNU LGPL v2.1 ou plus récente.

Le code est disponible dans mon dépôt de sources. La dernière version du moment peut être téléchargée soit en tant qu'archive tar.gz, soit en utilisant GIT: git clone git://source.numerimoire.net/decisional_states.git.