Douglas L. Vail

Conditional Random Fields for Activity Recognition Degree Type: Ph.D. in Computer Science
Advisor(s): John D. Lafferty, Manuela M. Veloso
Graduated: May 2008

Abstract:

To act intelligently in the presence of others, robots must use information from their sensors to recognize the behaviors and activities of the other agents in their environment. Robots must map from low-level, difficult to interpret data, such as position information extracted from video, to abstract states, in particular, the activities of the other agents. In this thesis, we explore how to bridge the gap from noisy, continuous observations about the world to high-level, discrete activity labels for robots in the environment.

We contribute the use of conditional random fields (CRFs) for activity recognition in multi-robot domains. We explore the appropriateness of CRFs with an empirical comparison to hidden Markov models. We elucidate the properties of CRFs that make them well suited to the activity recognition, namely discriminative training, the ability to robustly incorporate rich features of the observations, and their nature as conditional models, with a variety of synthetic and real robot data.

Accurate activity recognition requires complex and rich features of the observations. We choose the most informative features from a large set of candidates using feature selection. We adapt two feature selection algorithms, grafting and ℓ₁ regularization, to conditional random fields. We also investigate a third feature selection algorithm, which was originally proposed for CRFs in a natural language processing domain, in an activity recognition context. In particular, we focus on scaling feature selection to very large sets of candidate features that we define succinctly using a rich relational feature specification language.

The reduced feature sets that we discover via feature selection enable efficient, real-time inference. However, feature selection and training for conditional random fields is computationally expensive. We adapt an M-estimator, introduced by Jeon and Lin for log-density estimation in ANOVA models, for fast, approximate parameter estimation in CRFs. We provided an in depth, empirical evaluation of the properties of the M-estimator and then we introduce a new, efficient feature selection algorithm for CRFs based around M-estimation to identify the most important features.

Thesis Committee:
Manuela Veloso (Co-Chair)
John Lafferty (Co-Chair)
Carlos Guestrin
Dieter Fox (University of Washington)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Conditional Random Fields, Activity Recognition, Robotics, Undirected Graphical Models, Feature Selection, M-estimators