Cas d'unicité de l'ensemble des valeurs des marquages obtenues grâce à l'algorithme de propagation

Nous allons montrer les points suivants, regroupés sous la forme d'une proposition

Proposition _s  

• dans le cas général, l'historique de l'ajout des transitions influe sur la valeur des marquages obtenus au cours de l'apprentissage
• dans le cas particulier où le système respecte la propriété ( $P_{\epsilon }$), il existe un lien fonctionnel entre le graphe d'états (états et transitions) et la valeur des marquages associés: cela montre l'unicité de l'ensemble des valeurs de marquage obtenues grâce à l'algorithme d'apprentissage
• dans le cas particulier où il n'existe aucune transition vers l'état $E_{S}$ (problème de viabilité), il n'est pas nécessaire que la propriété ( $P_{\epsilon }$) soit respectée pour obtenir ce lien fonctionnel

Nous allons débuter cette sous-section en montrant les limites du contexte pour lequel il existe une unicité de l'ensemble des valeurs de marquage lorsque le graphe d'états est fixé (états et transitions). La résolution du système d'équations 2.1, pour des valeurs de $M_{i}$ et $M_{i,k}$ dans 0,1,-1, et un ensemble de transitions fixé, aboutit dans le cas général à plusieurs solutions. La figure 2.3 illustre ce fait, en présentant deux graphes d'états cohérents, possédant les mêmes transitions mais pas les mêmes marquages (graphes (a) et (b)). Pourtant, on sent intuitivement que le graphe (b) ne peut pas être obtenu en utilisant l'algorithme d'apprentissage CbL. En effet, la valeur d'initialisation des marquages étant nulle, on ne voit pas comment il pourrait exister un passage à la valeur 1 sans qu'il existe une transition vers l'état $E_{S}$. Cependant, on ne peut pas déduire cela du système d'équations. En effet, le voici:

$$\left\{ \begin{array}{c} M_{1} = \max\{M_{1,1},M_{1,2}\}\\ M_{... ...\ M_{2,2} = M_{3}\\ M_{3,1} = M_{1}\\ M_{3,2} = 0\\ \end{array}\right\}$$

La résolution de ce système s'effectue de proche en proche. Il vient:

$$\left\{ \begin{array}{c} M_{1} = M_{2} = M_{3} = M_{1,1} = M_{2,... ...,1}\\ M_{1} \in \{0,1\} M_{1,2} = M_{2,1} = M_{3,2} = 0 \end{array}\right\}$$

On en déduit qu'il existe deux ensembles de solutions, représentés par le graphe (a) (solutions engendrées en fixant $M_{1}$ à 0) et le graphe (b) ($M_{1}$ = 1).
Le graphe (c) montre par quelle manière on peut passer du schéma (a) au schéma (b): ajouter une transition vers l'état $E_{S}$ (en pointillé sur la partie gauche du graphe (c)), donne le schéma de droite du graphe (c) en utilisant l'algorithme de propagation, puis la supprimer redonne le graphe (b), toujours en utilisant l'algorithme de propagation. Or, l'algorithme d'apprentissage ne fonctionne que par ajout de transition. Cet exemple montre que, dans le cas général où on autorise également des suppressions de transitions, la valeur des marquages dépend de l'historique des opérations d'ajout et de suppression.
Les graphes (d) et (e) montrent que, dans le cas général de construction du graphe d'état par apprentissage, la valeur des marquages dépend de l'historique des opérations d'ajout de transitions. Le graphe (d) montre qu'à partir d'un graphe cohérent (partie gauche) dans lequel le marquage des deux états est à 1, l'ajout de la transition de $e_{2,2}$ vers $e_{1}$ (en pointillés) ne change pas la cohérence du graphe. D'autre part, le graphe (e) est cohérent, avec le marquage des états valant 0 (figure de gauche); l'ajout de la transition de $e_{2,2}$ vers $E_{S}$ ne change pas la cohérence du graphe. Or, les graphes d'état des deux figures de droite sont identiques, alors que leurs marquages sont différents.

Figure: Exemples de cas de multiplicité des solutions au problème de marquage

Après avoir fourni ces contre-exemples utiles à une première compréhension des mécanismes de propagation, nous souhaitons montrer que, dans le cadre de l'application de l'algorithme d'apprentissage pour un système vérifiant la propriété ( $P_{\epsilon }$), la valeur des marquages ne dépend pas de l'historique des opérations d'ajout de transitions, conditionné par la stratégie d'exploration des états. Ce résultat est important, car il permet de voir la valeur des marquages obtenue après apprentissage comme une fonction de l'ensemble des transitions découvertes. Par conséquent, la connaissance de ces transitions suffit pour déterminer la valeur des marquages.
Prouvons la validité du deuxième point de la proposition 1, en utilisant les équations de la relation 2.1 liant le marquage des états $e_{i}$ à celui des états $e_{i,k}$. Pour cela, nous allons établir une formulation modifiée de ce système d'équations.
Commençons par les équations liées aux états transitoires $e_{i,k}$. Celles-ci sont très simplifiées puisque l'hypothèse ( $P_{\epsilon }$) stipule qu'une transition d'un état $e_{i,k}$ ne peut aboutir qu'à un unique état $e_{j}$ ou à un état terminal. L'expression du marquage $M_{i,k}$ prend quatre formes différentes:

1. $e_{i,k}$ n'est relié à aucun état $e_{j}$. Dans ce cas, l'équation associée à $e_{i,k}$ se résume, par hypothèse, à: $M_{i,k}$ = 0
2. $e_{i,k}$ est relié à $E_{E}$. Dans ce cas, l'équation se résume à: $M_{i,k}$ = -1
3. $e_{i,k}$ est relié à $E_{S}$. Dans ce cas, il vient: $M_{i,k}$ = 1
4. $e_{i,k}$ ne répond à aucun des trois cas précédents. $M_{i,k}$ = $M_{j}$

Occupons-nous à présent des équations associées aux états $e_{i}$. En injectant l'expression des $M_{i,k}$ dans celle de $M_{i}$, on trouve quatre cas distincts:

1. un $M_{i,k}$ vaut 1, ce qui entraîne que, quel que soit l'expression des marquages associés aux autres états $e_{i,k}$, on a l'équation: $M_{i}$ = 1
2. l'ensemble des marquages associés aux états transitoires sont fixés à 0 ou -1. Dans ce cas, $M_{i}$ = c, avec c valant 0 ou -1.
3. l'ensemble des marquages associés aux états transitoires ne comporte que des marquages étant réductibles à un $M_{j_{i,k}}$ avec éventuellement des marquages valant -1. Dans ce cas, il vient: $M_{i}$ = $M_{j_{i}}$, avec $M_{j_{i}}$ = max$M_{i,k}$
4. dans les autres cas de figure, il existe des marquages valant 0, ce qui modifie l'expression précédente: $M_{i}$ = max{0, $M_{j_{i}}$}

La valeur d'un $M_{i}$ peut donc être directement connue (cas 1 et 2) ou être en relation avec celle d'un autre marquage (cas 3 et 4). La résolution du système s'effectue soit directement, pour des états qui ne sont pas connectés à d'autres états (cas 1), soit de proche en proche à partir des états connectés aux états terminaux $E_{S}$ ou $E_{E}$. Le problème de l'unicité des valeurs des marquages $M_{i}$ revient à savoir s'il peut rester des valeurs indéterminées de $M_{i}$, répondant aux cas 3 ou 4, à la fin de la résolution de proche en proche. L'exemple que nous avons présenté en début de sous-section indique que cela peut arriver. Dans ce cas, considérons l'ensemble M des marquages ne pouvant être résolus: M = {$M_{i_{1}}$, $M_{i_{2}}$, ..., $M_{i_{n}}$}. Pour chaque $M_{i_{j}} \in M$, les cas 3 et 4 imposent que:

• soit il existe un $M_{i_{k}} \in M$ tel que $M_{i_{j}} = M_{i_{k}}$ (cas 3)
• soit il existe un $M_{i_{k}} \in M$ tel que $M_{i_{j}} = \max\{0,M_{i_{k}}\}$ (cas 4)

Le deuxième point correspond au cas évoqué par les graphes (a) et (b). Il offre a priori deux solutions pour $M_{i_{k}}$: 0 ou 1. Pour le premier point, $M_{i_{k}}$ peut valoir a priori 0, 1 ou -1. Mais, tous ces cas sont-ils possibles ?
En premier lieu, il faut remarquer que l'utilisation des équations ne permet de déduire qu'un marquage vaut 0 uniquement lorsque l'état associé ne possède pas de transition vers un autre état. En effet, la résolution de proche en proche s'effectue à partir des états terminaux $E_{E}$ et $E_{S}$, ce qui permet de fixer les valeurs des marquages à 1 ou -1. On en déduit que s'il existe des marquages valant 0 dont l'état $e_{i}$ associé possède au moins une transition vers un autre état $e_{j}$, alors ces marquages sont dans M. Mais, cela signifie-t-il que tous les marquages de M sont nuls ?
Prenons un état $e_{i}$ dont le marquage est dans M. $e_{i}$ ne peut pas avoir de transitions vers un $e_{j}$ extérieur à M, de marquage connu $M_{j}$ = 1. En effet, dans ce cas, la valeur de $M_{i}$ serait alors connue et fixée à 1 (cas 1). Or, si un marquage $M_{i}$ de M vaut 1, cela signifie que cette valeur a été propagée par une transition aboutissant à l'état associé $e_{i}$ (puisque la valeur initiale de $M_{i}$ est 0). D'après la remarque précédente, cette transition ne peut provenir que d'un élément de M. Ce qui reporte le problème à un autre $M_{i}$ de M, d'où une non-résolution du problème dans l'hypothèse d'un marquage de M valant 1. Cela montre l'impossibilité que les marquages de M puissent être égaux à 1. Émettons l'hypothèse qu'un marquage $M_{i}$ de M soit égal à -1. Dans ce cas, il est régi par le cas 3 (le cas 4 est impossible). Le passage du marquage de 0 à -1 n'est possible que si toutes les transitions issues de $E_{i}$ possèdent un marquage -1. Comme $M_{i}$ est dans M, il existe forcément une transition menant à un marquage de M. Ce marquage doit donc avoir été mis à -1 précédemment. Comme dans le cas précédent, le problème du passage de la valeur de $M_{i}$ de 0 à -1 est reporté sur un autre élément de M. Cela montre également l'impossibilité de notre hypothèse $M_{i}$ = -1. Par conséquent, l'intégralité des marquages de M ont une valeur 0.
Donc, nous venons de montrer l'unicité de la valeur des marquages obtenus par l'algorithme de propagation, dans le cas où le système vérifie la propriété ( $P_{\epsilon }$).
Considérons à présent le cas particulier où il n'existe pas de transition vers l'état $E_{S}$: il correspond à un problème de viabilité. Nous allons montrer le même résultat que précédemment, mais sans utiliser la propriété ( $P_{\epsilon }$). Les modifications au niveau des équations sont peu nombreuses: le cas 4 n'existe plus, puisque le fait qu'il n'existe pas de transition à partir d'un $e_{i,k}$ suffit pour montrer que le marquage de $e_{i}$ vaut 0. Le cas d'indétermination est donc uniquement le cas 3. D'autre part, la propriété ( $P_{\epsilon }$) n'est utilisée précédemment que pour éliminer la possibilité d'une transition à partir d'un état associé à M jusque vers un état de marquage 1 n'appartenant pas à M (c'est précisément le cas montré par les graphes (d) et (e), pour lequel l'ordre d'apparition des transitions change le marquage final). Dans notre cas, ce problème n'existe plus. En effet, l'indétermination sur $M_{i}$ existe s'il existe au moins une transition partant $e_{i,k}$ vers un état $e_{j}$ associé à M, sans qu'il existe une transition de $e_{i,k}$ vers un état non associé à M (dans le cas contraire, le minimum des deux marquages serait égal à -1, quel que soit $M_{j}$). L'hypothèse $M_{i} = -1$ implique donc que l'état $e_{i}$ soit passé d'un marquage 0 à un marquage -1. Pour cela, l'unique possibilité est que l'ensemble des transitions partant de $e_{i}$ aboutissent à des états marqués à -1. Or, nous venons de montrer qu'il existe au moins une transition allant de $e_{i}$ vers un état associé à M. Il faudrait donc que le marquage de celui-ci soit passé préalablement d'un marquage 0 à un marquage -1. Ce qui reporte le problème à un autre état associé à M. D'où la conclusion que les marquages indéterminés par résolution de proche en proche sont égaux à 0. Ce qui termine la démonstration du troisième point de la proposition 1.