Discussion items from 1/28/04


Here are some interesting discussion items that came up on 1/28

1. Just as with Markovian nature, statitionarity of a process too is a
function of the specific model used. You can make a non-stationary
process stationary by adding additional variables whose influence was
ignored earlier

The order of a markov process is the oldest time-slice state
   variable that affects the current state. If our state is made up
for 10 random variables X1..X10, then we can have a second order
markov process where x1..x5 at time t are dependent on x1..x5 at time
t-1, while the x6..x10 at time t are dependent on x6..x10 at time
t-2. 

2. Dynamic bayes nets are to bayes nets as Situation Calculus is to
   FOPC. Specifically:

   --> A k-horizon unfolding of a dynamic bayes net just corresponds
       to a  normal (static) bayes net.

   --> The CPTs of a normal bayes net are partitioned into two
       separate classes in the case of DBN--The "transition model"
       and the "sensor model". 

   --> If you have evidence on e1...en, and you want to find the
   distribution of Xk (k<n), then you must consider both "causal" and
   "diagnostic" evidence on Xk. The causal evidence comes from
   e1...ek-1 (through their diagnostic influence on X1..Xk-1) while
   the diagnostic one comes from ek...en.
   
       In the context of DBN, the causal evidence propagation is
"prediction" component and the diagnostic evidence component is
"smoothing".

   Although DBN separates these two types of evidence propagation,
from a BN point of view both of them _must_ be taken into account to
arrive at the true distribution of Xk (you do not have the option of
not smoothing...)
    
 The connection to BN also helps explain why the forward/backward
algorithm is polynomial. The unwound DBN winds up being a singly
connected BN (for which exact inference is polynomial). In fact the
forward-backward algorithm can be seen as the causal-diagnostic
message passing algorithm on exact inference for singly-connected BNs.

3. Notice that "Filtering" involves prediction as well as smoothing
   components (the smoothing is done only with respect to current
   evidence and the current state)


4. To get the maximally likely state sequence given the evidence
sequence, you need to get the joint distribution of the state sequence
given evidence sequence, and take its mean. This will not in general
be the same as taking the most likely value of each state in the
sequence (which can be computed through smoothing). 

An example is the following:

 Suppose you heard me say a three word sentence that sounded like

"Tom if dumb". Now based just on the signal, the most likely state for
the second word is "if".  However, if you take the evidence sequence
into consideration, the most likely interpretation is 
"Tom is dumb"



5. One way of understanding the viterbi algorithm for finding maximal
   likely sequence of states given evidence is to notice that the path
   likelyhood in the state sequence is multiplicative in the
   transition propabilities. If you take logs, and multiply by -1, we
   get a normal summative shortest path problem (where the shortest
   path will be the path with maximum  likelyhood). 


   [[It is interesting to note that in actual implementations, Viterbi
    is actually done in the log space, since otherwise we get too many
    underflow errors because of multiplying probabilities]]
 
6. The standard HMM model assumes that the state is made up of a
   single random variable. If the state has multiple variables, then 
   we can make a "mega" variable whose domain is the cartesian product
of the domains of the original variables. You however lose the
advantages of factorization if you do it this way.