non-deterministic state diagram
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. 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? Thank you, Andrej
Date: Fri, 24 Oct 2008 01:26:51 +0000 From: mavdzee@yahoo.co.uk To: boost-users@lists.boost.org Subject: [Boost-users] non-deterministic state diagram
Hi,
I need to calculate the non-deterministic state diagram from raw data and was wondering how boost can hep me.
It may help to outline the naive approach. As a frequent advocate of re-inventing the wheel and "dirt level" programming, let me see if I can motivate the case for something simple like a 2D array of count_types ( unsigned ints) that gets updated as you record each transition ( indicies are "current" and "next" ) perhaps with running totals for both, leading to 3 int increments and some simple offset calculations per recorded transition. I guess if you need to calculate the float p on each iteration, divisions IIRC are still slow, you might consider some tricks here given a past result and incrementing numerator or denominator by 1 ( no idea what these may be). Now, if your state table is big compared to cache sizes, you could anticipate some thrashing and think about any ways to minimize this ( brute force LUT's are not always the fasted way to go ). For example, it may make sense to keep small count types and make carries exceptional events, allowing larger pieces of primary table to stay in lower level caches, especially if you expect pretty uniform P's. This should all code, and be easy to optimize with "tricks", pretty quickly but what dead ends does it stick you with?
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.
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?
Thank you, Andrej
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_________________________________________________________________ Store, manage and share up to 5GB with Windows Live SkyDrive. http://skydrive.live.com/welcome.aspx?provision=1?ocid=TXT_TAGLM_WL_skydrive...
From: marchywka@hotmail.com To: boost-users@lists.boost.org Subject: RE: [Boost-users] non-deterministic state diagram Date: Fri, 24 Oct 2008 06:28:01 -0400
Date: Fri, 24 Oct 2008 01:26:51 +0000 From: mavdzee@yahoo.co.uk To: boost-users@lists.boost.org Subject: [Boost-users] non-deterministic state diagram
Hi,
I need to calculate the non-deterministic state diagram from raw data and was wondering how boost can hep me.
It may help to outline the naive approach. As a frequent advocate of re-inventing the wheel and "dirt level" programming, let me see if I can motivate the case for something simple like a 2D array of count_types ( unsigned ints) that gets updated as you record each transition ( indicies are "current" and "next" ) perhaps with running totals for both, leading to 3 int increments and some simple offset calculations per recorded transition. I guess if you need to calculate the float p on each iteration, divisions IIRC are still slow, you might consider some tricks here given a past result and incrementing numerator or denominator by 1 ( no idea what these may be). Now, if your state table is big compared to cache sizes, you could anticipate some thrashing and think about any ways to minimize this ( brute force LUT's are not always the fasted way to go ). For example, it may make sense to keep small count types and make carries exceptional events, allowing larger pieces of primary table to stay in lower level caches, especially if you expect pretty uniform P's.
This should all code, and be easy to optimize with "tricks", pretty quickly but what dead ends does it stick you with?
Ok, no interest yet. Let's assume you have 1<>
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.
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?
Thank you, Andrej
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_________________________________________________________________ Store, manage and share up to 5GB with Windows Live SkyDrive. http://skydrive.live.com/welcome.aspx?provision=1?ocid=TXT_TAGLM_WL_skydrive...
_________________________________________________________________ Want to read Hotmail messages in Outlook? The Wordsmiths show you how. http://windowslive.com/connect/post/wedowindowslive.spaces.live.com-Blog-cns...
From: marchywka@hotmail.com To: boost-users@lists.boost.org Subject: RE: [Boost-users] non-deterministic state diagram Date: Sun, 26 Oct 2008 22:08:19 -0400
Ok, no interest yet. Let's assume you have 1<>
eh, there was supposed to be a few paragapths of TEXT in between the less and greater than. Sorry about that, the last message I sent probably made little sense. I had a nice alternative set of questions based on spare matrix implementation but apparently hotmail, thinking I was trying to type html, reduced it to a less than and greater than- I was trying to write 1 left shift 20. Anyway, if any one thought more about this based on the transitions only occuring over a very small subset of the possible ones please comment.
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
_________________________________________________________________ You live life beyond your PC. So now Windows goes beyond your PC. http://clk.atdmt.com/MRT/go/115298556/direct/01/
Hi Andrej, On Thu, Oct 23, 2008 at 6:26 PM, Andrej van der Zee <mavdzee@yahoo.co.uk> 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
participants (3)
-
Andrej van der Zee -
Mike Marchywka -
Stjepan Rajko