distribution that can be represented compactly (Boyen & Koller, 1998), or in the form of a set of weighted samples as in the Sequential Monte-Carlo Sampling methods (Doucet, Godsill, & Andrieu, 2000b; Kanazawa, Koller, & Russell, 1995; Liu & Chen, 1998).

The most simple case of the DBN where, in each time-slice, there is only a single state variable and an observation node, is the well-known Hidden Markov Model (HMM) (Rabiner, 1989). Filtering in this simple structure can be solved using dynamic programming in the discrete HMM (Rabiner, 1989), or Kalman filtering in the linear Gaussian model (Kalman, 1960).  More recently, extensions of the HMM with multiple hidden interacting chains such as the Coupled Hidden Markov Models (CHMM) and the Factorial Hidden Markov Models (FHMM) have been proposed (Brand, 1997; Ghahramani & Jordan, 1997; Jordan, Ghahramani, & Saul, 1997). In these models, the size of the belief state is exponential in the number of hidden chains. Therefore, the inference and parameter estimation problems become intractable if the number of hidden chains is large. For this reason, approximate techniques are required. CHMM (Brand, 1997) employs a deterministic approximation that approximates full dynamic programming by keeping only a fixed number of "heads" with highest probabilities. The "heads" are thus chosen deterministically rather than randomly as in sampling-based methods. FHMM (Ghahramani & Jordan, 1997; Jordan et al., 1997) uses variational approximation (Jordan, Ghahramani, Jaakkola, & Saul, 199) which approximates the full FHMM structure by a sparsified tractable structure.  This idea is similar to the structured approximation method in (Boyen & Koller, 1998).

Our AHMM can be viewed as a type of Coupled/Factorial HMM since the AHMM
also consists of a number of interacting chains. However the type of interaction in our AHMM is different from the other types of interaction that have been considered (Brand, 1997; Jordan et al., 1997; Ghahramani & Jordan, 1997). This is because the main focus of the AHMM is the dynamics of temporal abstraction among the chains, rather than the correlation between them at the same time interval. In addition, each node in the AHMM
has a specific meaning (policy, state, or policy termination status), and the links have a clear causal interpretation based on the policy selection and persistence model. This is in contrast to the Coupled/Factorial HMM where the nodes and links usually do not have any clear semantic/causal interpretation. The advantage is that prior knowledge about the temporal decomposition of an abstract process can be incorporated in the AHMM more nturally.

## 2.3  Sequential Importance Sampling (Sis)

Sequential Importance Sampling (SIS) (Doucet et al., 2000b; Liu & Chen, 1998), also known as Particle Filter (PF), is a general Monte-Carlo approximation scheme for dynamic stochastic models. In principle, the SIS method is the same as the so-called Bayesian Importance Sampling (BIS) estimator in the static case (Geweke, 1989). Suppose that we want to estimate the quantity f = f f ( x ) p ( x ) dx, i.e., the mean of f ( x ) where x is a random variable with density p. Note that if f is taken as the identity function of an event A then f is simply Pr(A). Let q(x) be an arbitrary 2 density function, termed the importance distribution. Usually, the importance distribution q is chosen so that is it easy to obtain