Open Collections

Meta level tracking with stochastic grammar

University of British Columbia

The ability to learn about a stochastic process from noisy observations is fundamental to many applications. In order to track a dynamic process, the typical knowledge representation required is the state space model such as a linear Gauss Markov model, where efficient algorithms exists to perform state estimation under many different model assumptions. However, for meta level tracking, we are not only interested in the state estimation of the process, but classification of the process to a finite set of categories. In other words, in order to extract semantics of the sequential data, the approach taken is to define a model for each category, and determine the most likely one during the tracking. However, current models that are widely applied in classifying sequential data are mainly Markov models, but they are not only restrictive in the patterns that they can express, they often require state space that grows exponentially in the length of the observation. The solution presented in the thesis is to apply a more expressive and general model than Markov models to characterize the sequential process; the prior knowledge of the sequential process is to be encoded as a declarative language (linguistic framework) using stochastic context free grammar (SCFG) methods. The objective of the thesis is to formulate a meta level tracking framework, introduce and analyze the use of SCFG as the knowledge representation model, and discuss properties, applications, and algorithms involved. The research of the meta level tracking presented in the thesis is the result of the two main projects: electronic support measure against a multifunction radar, and ground surveillance with GMTI (ground moving target indicator) radar. In the electronic support measure problem, the algorithm developed plays the role of a target that is being tracked by a radar, and its aim is to estimate the operation mode of the radar and maximize its ownship safety. The ground surveillance is a reverse problem, where the algorithm runs in a radar and aims to learn the geometric patterns of ground moving targets’ trajectories, and implicitly infer their intents. In both cases, because the sequential process involved has hierarchical structure and long range dependency; for example an arc spatial pattern in a ground moving target’s trajectory, Markov models are not sufficient for the characterization and representation of the process. SCFG, on the other hand, can compactly encode the prior knowledge as production rules, and has demonstrated strength in modeling the branching and self-embedding dependencies that are often seen in processes with hierarchical structure and multiple time scales. In the electronic support measure problem, a novel model called Markov modulated SCFG is developed, and efficient algorithms are derived to perform both the state and parameter estimation of the model. In GMTI problem, a stochastic parser is modified to deal with GMTI data, and a detailed formal language analysis of several common two-dimensional spatial patterns is performed with their corresponding stochastic grammar constructed. All the developed algorithms are implemented in C++ and their performance evaluated.

Thesis/Dissertation

application/pdf

2009-08-17

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/12263

Electrical and Computer Engineering

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/