Towards a more effective storage of transitions

A Markov model of $N$ states needs to store a matrix of transition probabilities of size $N^2$.

Furthermore, in a standard Markov model, with our kind of data, many transition probabilities will be either zero or insignificant. Indeed, in a video sequence of an object, the trajectory of the object is often continuous and does not jump randomly from one position to another. When the object is in a position corresponding to one pathlet model, only a few pathlet models can can be used for the next position in the sequence. In the transition matrix, all of the impossible configurations are modelled by a probability of zero.

In some other situations, the transition probability is very low. Such situations can include atypical behaviours that happened only once during the training stage. In this case, we may want to discard these transitions since they do not reflect representative situations. A low probability transition can also come from the hardware used to capture the video sequence. A slow computer may drop some frames when the user is running a resource consuming process. This will result on sudden jump of the object within the sequence, and so an atypical behaviour. The same effect can be achieved if a recorded video sequence has not been correctly encoded in digital format.

It would be better not to store these values as they are generally unnecessary. The variable length Markov model gives a solution to this problem because it discards small probabilities and also transitions that do not add any useful information to the model. The transition probabilities storage needs to be rearranged for efficiency.

In the VLMM model, the transition probabilities are encoded in a tree. Figure 6.2 shows such a tree. Figure 6.2(a) represents the standard storage in VLMM as described in [81]. Figure 6.2(b) represents the way we have stored the probabilities. We can easily map between the two. Our storage is more efficient in retrieving probabilities for our application, but the gain is negligible compared to the other sources of computation.

Figure 6.2: Example of storage of transitions in a VLMM model. The two way of storing the probabilities are equivalents. 6.2(a) stores conditional probabilities while 6.2(b) stores joint probabilities. From 6.2(a) we can deduce for instance the probabilities $P \left({\cal{G}}_{3}=B\vert{\cal{G}}_{2}=B,{\cal{G}}_{1}=A \right)=0.2$ , or $P \left({\cal{G}}_{2}=C\vert{\cal{G}}_{1}=A \right)=0.3$. From 6.2(b) we can deduce the probabilities $P \left({\cal{G}}_{3}=B,{\cal{G}}_{2}=B,{\cal{G}}_{1}=A \right)=0.072$ , or $P \left({\cal{G}}_{2}=C,{\cal{G}}_{1}=A \right)=0.18$.

Each branch of the tree represents a transition probability. In this case, the set of pathlet models is $\{A,B,C\}$. A pathlet model, a position in the history and a vector of probabilities is associated with each node. The size of the vector is the same as the size of the set of pathlet models. Each element in the vector corresponds to a immediate child. If the value in the vector is null, the corresponding child is not drawn on the tree. On figure 6.2(b), it stores the joint probability of having this child and all the pathlet models seen so far on their respective positions in the history.

For instance, the node $B_2$ corresponds to the pathlet model $B$ at the position $2$ in the history. The second element in the vector associated with the node $B_2$ correspond to the probability of $B$ (the second pathlet model) being at the position 3 (one step further in the history) given that the total sequence ends with the subsequence $B,A$. Using mathematical notation, the second element in the vector associated with the node $B_2$ is the probability $P \left({\cal{G}}_{3}=B,{\cal{G}}_{2}=B,{\cal{G}}_{1}=A \right)$ that is the probability of having the sequence $B,B,A$. The end of this sequence corresponds to the nodes $B_2$ and $A_1$ that need to be retrieved from the tree to reach $B_3$.

On figure 6.2(a), the vector stores the probability of having a child at its corresponding position in the history given that all the nodes seen so far are placed on their respective positions in the history.

For instance, the second element in the vector associated with the node $B_2$ corresponds to the probability of $B$ being the third in the history given that $B$ is the second and $A$ is the first, that is: $P \left({\cal{G}}_{3}=B\vert{\cal{G}}_{2}=B,{\cal{G}}_{1}=A \right)$ .

This tree representation of the storage is also called a prediction suffix tree. It is proved in [82] that a prediction suffix tree is equivalent to a finite state automata. It is also equivalent to a transition matrix as used by Markov models.