Re: [Boost-users] non-deterministic state diagram

Subject: Re: [Boost-users] non-deterministic state diagram
From: Stjepan Rajko (stjepan.rajko_at_[hidden])
Date: 2008-11-01 13:26:23

Hi Andrej,

On Thu, Oct 23, 2008 at 6:26 PM, Andrej van der Zee <mavdzee_at_[hidden]> wrote:
> Hi,
>
> I need to calculate the non-deterministic state diagram from raw data and was wondering how boost can hep me.
>
> More specific, I have many state transition sequences (lets say up to 100-thousand) that all start at state A, such as:
> A -> B -> D -> B -> E
> A -> D -> B -> C -> B
> A -> E -> D -> F -> D
>
> Now I want to calculate the non-deterministic state diagram with a chance for each transition, and desirable in real-time. For example, for the raw data above, the transition for A -> B is 0.33.
>

What do you mean by 'in real time'?  Do you get a new transition
sequence at a certain frame rate, and need to update your
probabilities?  Or do you get a new element of each sequence?  (or
something else?)

I am working on a pattern recognition library (temporal patterns, for
now), and a part of it involves calculating transition probabilities
for a probabilistic model (hidden markov model-based).  The problem
that the library deals with is slightly more general than what you
have here, but would do the trick.  It might not be as efficient as
you might need it for the size of your problem, though.

The library has so far only offered models that are specific to
gesture recognition, but just yesterday I started implementing a general
hmm-ish class based on the Boost Graph Library, and the algorithm that
would solve your problem should be done next week.  This is all GPLed
though, I don't know if that is a problem for you.

> My question is how boost can help me:
> * Which library is best to represent the state diagram?
> * Does the library help in calculation of the state diagram from raw data?
>

With this lib, you'd have to predefine the set of states (A, B, C, D,
E, F,...) beforehand, and then it could calculate the transition
probabilities from the raw data.

Best,

Stjepan