This might not be of much help, but should you not consider ticks where no data is present? This would give you three states: 0 = false, 1 = positive, 2 = no data. If you''re data changes with time I would think that whatever solution you adopt should take this unknown in to consideration.

I suggest evolving a program, but then again, that is what I always suggest.

Cheers,
Will

quote:

---

Original post by GameCat
I''ll check out the pointers you provided but there''s one additional caveat. The method used has to be very computationally efficient since the (expected) utility I''m trying to maximize is roughly inversely proportional to computation time. So taking a really long while to make a great decision is kind of pointless...

---

Okay, having read your initial post again and your last one, then yes, you need to learn p(s_t|s_t-1,s_t-2,...,s_t-n) for some n . Finding an appropriate n is a little tricky, but you have two approaches: 1) overestimate n , which will result in arcs to earlier times (from the current time) having little weight); and/or, 2) utilise time series analysis (TSA) techniques to determine a realistic n . You could use the lag time of the sequence (first minima of the entropy function over time) or the first minima of the autocorrelation function. There is plenty of literature out there about TSA.

quote:

---

Original post by RPGeezus
This might not be of much help, but should you not consider ticks where no data is present? This would give you three states: 0 = false, 1 = positive, 2 = no data. If you''re data changes with time I would think that whatever solution you adopt should take this unknown in to consideration.

---

There is definitely no need to infer a third state in the observation set. All that is required is to utilise a typical hidden state model such as this:



In the right hand diagram missing observations are handled easily and in fact save a computational step (that of conditioning the model on the observation). The model is specified by the distributions p(s₀), p(s_t|s_t-1,s_t-2,...,s_t-n) and p(E|s). This model takes into account correlation in observations via the correlation in the hidden state s. If the domain turns out to be Markovian, then this simplifies the model by removing arcs to all states prior to the previous state; i.e., s_t-2, s_t-3, etc.

As for a computationally efficient scheme for a) learning and b) inference, in this model, it depends on whether learning must be done online or whether it can be done offline. If you believe the transition distribution p(s_t|s_t-1,...) is stationary then you can perform your learning offline; use EM in this case. Otherwise, you''ll need an online method. I''d definitely recommend dual estimation in that case. If you want some more specific help than this, drop me an email and we can talk about your problem some more.

Cheers,

Timkin