Method for learning switching linear dynamic system models...

Details Method for learning switching linear dynamic system models... Method for learning switching linear dynamic system models...

2000-09-01

2003-07-08

Patel, Ramesh (Department: 2121)

Data processing: generic control systems or specific application

Generic control system, apparatus or process

Optimization or adaptive control

C700S023000, C700S027000, C700S030000, C700S031000, C700S046000, C700S047000, C382S103000, C382S228000, C382S236000, C375S296000, C375S297000, C375S346000, C342S095000, C342S096000, C342S102000, C342S107000

Reexamination Certificate

active

06591146

ABSTRACT:

BACKGROUND OF THE INVENTION
The problem of fitting dynamic models to sequences of data is a key technology in many applications. In econometrics and forecasting applications, data sequences may represent product inventory in a distribution channel over time, or the price of a stock or other financial instrument over time. In human motion applications, data sequences could represent the pose of the human body over time. For example, a motion such as a ballet plié can be described as a sequence of smooth changes in the angles of the arms and legs and pose of the torso.
Dynamic models can also be applied to modeling of spatial data sequences, such as genes or constrained kinematic chains.
The most basic example of learning the parameters of a dynamic model from data is the system identification problem for a single linear dynamic model. System identification is described in Ljung et al., “Theory and Practice of Recursive Estimation,” MIT Press, 1983. Unfortunately, a single linear model is incapable of representing a broad range of interesting data sequences.
A switching linear dynamic system (SLDS) model consists of a set of linear dynamic models and a switching variable that determines which model is in effect at any given point in time. A “fully connected” SLDS further assumes that there are temporal dependencies between the values of the switching variable at different times, as well as the states of different linear dynamic models. SLDS models are attractive because they can describe complex dynamics using simple linear models as building blocks. Given an SLDS model, the inference problem is to estimate the sequence of model states that best explains a measurement data sequence. Unfortunately, exact inference in SLDS models is computationally intractable, due to the large number of possible combinations of linear models over time.
Consider the case where there are r linear models in an SLDS model, and assume that the goal is to infer which model best explains each element in a measurement data sequence of length n. For the first element there are r possibilities. For two sequential elements there are r*r possibilities. There are r
n
total possibilities for the entire data set or sequence of n elements. It is infeasible to examine each of these possibilities to determine the exact, optimal solution.
One prior method for inference using fully connected SLDS models is described in Bar-Shalom et al., “Estimation and Tracking: Principles, Techniques, and Software,” Artech House, Inc. 1993 and in Kim, “Dynamic Linear Models With Markov-Switching,” Journal of Econometrics, volume 60, pages 1-22, 1994. In this method, approximate inference is achieved by truncating or collapsing the number of discrete components in the evolving model. The models are used to detect different motion regimes while tracking a maneuvering target.
Additional approximate smoothing of the switching states is described in Kim. Neither of these two references tackle smoothing of the linear dynamic system states.
In most applications, it is not practical to build an SLDS model by hand and it is therefore desirable to learn the parameters of these models from training data. A method for SLDS learning is described in Shumway et al., “Dynamic Linear Models with Switching,” Journal of the American Statistical Association, 86(415), pages 763-769, September 1991. It assumes that the SLDS is not fully connected, i.e., the switching variable has no temporal dependencies. It also assumes that a prior distribution for the switching variable is known for each time instant. These assumptions do not hold for a broad range of practical applications.
Krishnamurthy et al., “Finite-dimensional Filters for Passive Tracking of Markov Jump Linear Systems,” Automatica, 34(6), pages 765-770, 1998, assumes that the switching variable follows a Markov process model and that observations of the switching variable are available for each time instant. However, for a broad range of practical applications, these observations are not available.
In another method, the switching variable determines which linear model is coupled to the measurement at each time instant. See Ghahramani et al., “Variational Learning for Switching State-Space Models,” which will appear in the journal Neural Computation. This method can produce decoupled linear models which reach steady-state before the data series is adequately modeled. It stands in contrast to methods with fully coupled SLDS in which all models are coupled through a single state space.
Pavlovic, Frey and Huang, “Time-series Classification Using Mixed-State Dynamic Bayesian Networks,” Proc. of Computeor Vision and Pattern Recognition, pages 609-615, June, 1999, considers a single linear dynamical model whose input is modeled as a discrete Markov process. This model explains all measurement variability as a consequence of the changes in input, which may not be true in general.
Blake et al., “Learning Multi-Class Dynamics,” Advances in Neural Information Processing Systems (NIPS '98), pages 389-395, 1998, proposes particle filters as an alternative to using linear models as the building blocks in a switching framework. The use of a nonparametric, particle-based model can be inefficient in domains where linear models are a powerful building block. Nonparametric methods are particularly expensive when applied to large state spaces, since they are exponential in the state space dimension.
In Brand, “Pattern discovery via entropy minimization”, Technical Report TR98-21, Mitsubishi Electric Research Lab, 1998, a Hidden Markov Model with an entropic prior is proposed for dynamics learning from sparse input data. The method is applied to the synthesis of facial animation. The dynamic models produced by this method are time invariant. Each state space neighborhood has a unique distribution over state transitions. In addition, the use of entropic priors results in fairly deterministic models learned from a moderate corpus of training data. In many applications time-invariant models are unlikely to succeed, since different state space trajectories can originate from the same starting point depending upon the class of motion being performed.
In Ghahramani et al., “Learning Nonlinear Stochastic Dynamics Using the Generalized EM Algorithm,” Advances in Neural Information Processing Systems (NIPS '99), pages 599-605, 1999, a Kalman smoother is used in conjunction with the generalized EM algorithm to learn a class of nonlinear dynamic models from input-output data. This approach also results in time-invariant models.
Another method addresses the problem of learning temporal models of motion in images. Unlike the more common state space models, this approach concentrates directly on the image space by representing any motion as a flow field in some particular flow field space. The basis of that space is learned from a corpus of examples. Hence, different bases capture distinct motion types. See Yacoob et al., “Learned Temporal Models of Image Motion,” Proceedings of Computer Vision and Pattern Recognition, pages 446-453, 1998.
One drawback of this method is that it only captures motion of a fairly fixed (and known) duration. For example, a prototypical walk of only one particular speed can be learned. Another disadvantage is that the models that result are highly viewpoint-specific, since they depend implicitly on the camera position. Furthermore, the approach is primarily suited for analysis rather than synthesis of motion sequences.
Technologies for analyzing the motion of the human figure play a key role in a broad range of applications, including computer graphics, user-interfaces, surveillance, and video editing. A motion of the figure can be represented as a trajectory in a state space which is defined by the kinematic degrees of freedom of the figure. Each point in state space represents a single configuration or pose of the figure. A motion such as a plié in ballet is described by a trajectory along which the joint angles of the legs and arms change continuously.
A key issue in human motion ana

Affiliated with

Also associated with

Rating

Method for learning switching linear dynamic system models... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for learning switching linear dynamic system models..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for learning switching linear dynamic system models... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3019746