Patterns Emerge From Chaos

June 2009
By Rita Boland and Maryann Lawlor
E-mail About the Author


The USS Benfold fires a missile during training exercise Stellar Daggers. The overall goal of the exercise was to detect, track, engage and destroy multiple incoming air and ballistic missile threats simultaneously during the final phase of flight. Research underway at the Massachusetts Institute of Technology (MIT) could help in this work by finding patterns in seemingly unrelated data.

Basic research lays foundation for increasing targeting accuracy and situational awareness.

A Massachusetts Institute of Technology researcher is developing a way to take simple descriptions of behavior patterns and assemble them to uncover complex dynamics. Once achieved, this capability would enable data to drive the learning mechanism with as little external intervention as possible. Although only in the basic research phase, this methodology could one day enable warfighters and analysts to take seemingly unrelated information and reveal underlying behavior—a valuable commodity in fighting the Global War on Terrorism.

With support from the U.S. Air Force Office of Scientific Research (AFOSR) and other organizations, Emily Fox, a doctoral student at the Massachusetts Institute of Technology (MIT), is conducting the work under the direction of her adviser, professor Alan Willsky, from MIT’s Laboratory for Intelligent Decision Systems. Fox has been interested for some time in the topic of extracting information from limited observations or from phenomena that exhibit complex dynamics. Specifically, she has been enthralled by activities that appear to evolve over time and are too challenging to describe using classical techniques. While interning at MIT’s Lincoln Laboratory, Fox worked on target tracking, one application area for the research she now is conducting.

“The challenge is in learning models that are simple yet sufficiently descriptive enough of the observations and are flexible in allowing new information to be incorporated,” Fox explains. Nonparametric Bayesian methods, a class of statistical approaches, address this goal. “As a class, these methods allow flexible mechanisms to incorporate uncertainty while encouraging simple descriptors. In this case, the uncertainty is the number of behaviors. Our research has focused on adapting and augmenting standard nonparametric Bayesian building blocks, such as the hierarchical Dirichlet process, to the setting of dynamic phenomena to discover underlying behavior.” Fox has been conducting her work in conjunction with Erik Sudderth and Michael Jordan, both studying at the University of California–Berkeley.

To date, the work has involved a number of varying applications. Fox and her colleagues analyzed how to learn the dance of honeybees, how to detect changes in the volatility of a stock index and how to segment an audio recording comprising an unknown number of speakers into labels of who is speaking when. “The model we have developed is able to perform these tasks without relying on knowledge of the specific application,” she explains.

For example, in examining the bee dance, the behaviors the researchers uncovered fall into three types of actions: turn right, waggle and turn left. Although biologists are familiar with these movements, the doctoral students’ application shows that the developing method can uncover coherent behavior without incorporating prior knowledge or expectations. This capability would enable observers to learn behaviors that have not been studied previously, or to uncover behaviors that have not been characterized before.

“Our model similarly provides a flexible mechanism for finding various regimes of volatility instead of the standard assumed two-regime model. Finally, the same model provides speaker diarization results that are competitive with the current state of the art in technologies.

“Each of the above tasks handled by our model [normally] poses either a significant challenge or burden to a human. Having automated procedures such as ours that can analyze data with little initial human input can be of great value in reducing that burden and assisting domain experts in characterizing processes and phenomena they are studying,” Fox explains.

Dr. Jon Sjogren, program manager, AFOSR, explains that having the right model for a physical or behavioral situation makes it possible to reach conclusions that are relatively resilient even when the input is imprecise. In addition, these conclusions can be attained with a relatively moderate amount of computing. “Thus a little data should lead to a robust conclusion without too much effort,” Sjogren says.

Many real-world situations that interest the Air Force are amenable to various types of modeling. The results from nonparametric Bayesian models that Fox has created are based on a massive foundation of statistical systems analysis that MIT has built up over the years. They are promising because they cover several classes of situations of importance to the military, Sjogren adds.

“In addition to seeking flexible response, U.S. Defense Department engineers have come to appreciate the flexible use of modeling techniques that apply to a number of disparate scenarios. Beyond the need to track one or several airborne platforms lies the need to model coordinated action of several communications or sensing platforms. Fox’s work has shed light on this class of problem—along with seemingly distinct challenge problems,” Sjogren relates. Another example is the effect of conspiratorial activity taking place across different cultural backgrounds, or adversarial modeling, he adds.

Many of the issues that arise in standard multiple- or maneuvering-target tracking algorithms require information about either the number of targets or types of maneuvers, he adds. Fox began to wonder whether nonparametric Bayesian methods could be adapted to these problems after hearing about Dirichlet processes from Sudderth. “The work on maneuvering target tracking led to my considering a more general model that has broader applicability to other domains,” she relates.

Willsky explains that one of the main thrusts of basic research at MIT is the exploration of new modeling frameworks that offer novel approaches to extracting information from complex data about complex environments. Currently, one of the significant focus areas is the development of methods that can understand complex data, environments and phenomena. The goal is to be able to extract structure that leads to coherent explanations of what is observed, he says.


Lt. Brett Whorley, USN, a member of the Liberty Bells from the Airborne Early Warning Squadron, assesses possible targets with his radar while conducting airborne early warning and strike group coordination. The ability to predict with some certainty future events based on observed behavior yet without human intervention is part of the exploration an MIT researcher has undertaken.

“There are many reasons to seek methods that make fewer and fewer prior assumptions about the phenomena or data being examined. One of these reasons is purely intellectual: How far can we go with the least prior assumptions about what we’re studying? But there are others such as avoiding traps of self-fulfilling prophecies. When one puts in prior assumptions, one is in essence constraining or biasing the interpretation of data. If those assumptions aren’t correct, one runs the risk of producing answers that are not correct,” Willsky notes.

During the past few years, a new approach to modeling has been introduced. Jordan and another research scientist at PrincetonUniversity, David Blei, have demonstrated how this new approach could be applied to problems such as automatically classifying large bodies of documents. Sudderth, who will soon become a faculty member at BrownUniversity in Providence, Rhode Island, brought these models to the attention of the group at MIT and explored a very different use of this new approach specifically for problems in object recognition and computer vision.

“As often happens, it is the graduate students in a group who teach the professor, and it happened in this case, leading me to pose some questions about whether this modeling approach offered any promise for the learning of dynamic behavior,” Willsky notes.

Tracking moving objects is a problem that Willsky has been involved in for many years. He has been particularly intrigued by tracking maneuvering objects, a problem not only of great interest for military surveillance systems but also of considerable importance for many civilian computer vision applications. With this in mind, Willsky suggested that Fox probe problems in this arena. “That is the problem on which Emily started, but her work has evolved to much broader and fundamental classes of models for the learning of complex dynamic phenomena in which we wish to learn their modes of behavior, how they switch among them, and ultimately the patterns of such switches,” he explains.

Willsky admits that the researchers are still learning what applications might benefit from these models. The emphasis is on methodologies that they believe are fundamental and new, offering possibilities for machine learning and data analysis that move well beyond what currently is available. In addition, the methodologies are meant to be broadly applicable and address issues that come up in a variety of domains.

“It’s important to emphasize that for the most part, our group uses these applications as vehicles to try out our new methods and to explore and expose their capabilities. While tracking objects is one area in which this framework is likely to bear fruit, there are many others,” he says. For example, extracting patterns of different modes of motion, while having significant potential for situational awareness applications of military significance, also has many other potential applications, Willsky adds.

Fox’s approach applied to speaker diarization is one example that could be particularly beneficial when conversations have been taped for future review. It would enable law enforcement and other national security personnel to determine automatically how many people are engaged in a conversation, what each person sounds like and when each is speaking, he explains.

The capability could have broader applications as well. Willsky notes that urban planners could use the capability to learn travel patterns in cities for intelligent traffic control such as after a major sporting event. “Even more ambitious applications could include using the motion of 22 football players to determine what play is being run and which defensive scheme is being used. A good quarterback and middle linebacker can do that. What about a computer? We are nowhere close to being able to solve problems such as this, but that’s what a lot of the excitement is about and what keeps us going: new ideas, such as those developed by Fox, always suggest even more questions than they answer,” he relates.

Although the AFOSR is funding the work, as are several other Defense Department organizations, the investigations do not focus solely on military applications. Willsky explains that many of these Defense Department agencies are interested in “moving the dial,” that is to say, they fund and foster new methodologies that could help solve the challenges the military faces. In this case, that challenge is situational awareness. However, financial supporters understand that universities are involved in basic research that is likely to have very broad applicability with many benefits, he adds.

Sjogren agrees that the AFOSR’s support of the research is not intended to result solely in military solutions. However, although the work may not focus on particular military-interest applications at the outset, it can lead to a flexible framework that can be adapted to many military situations. “The idea is to utilize the connections and similarities fully between problems and the models that solve them,” he maintains.

Willsky points out that his group performs basic research in areas related to the extraction of coherent information and knowledge from complex data concerning complex phenomena, a topic that is applicable in many different fields. Although some funding is from the Defense Department, the Shell Oil Corporation is providing additional resources, because some applicability may exist to improve the ability to discover oil fields.

Although basic research will never be complete because it leads to more questions and additional research, Fox allows that various markers of completion will indicate research progress. These include the publication of the findings in peer-reviewed periodicals. In addition, invitations to present material in various professional forums also indicate interest in the validity of the research. To date, the nonparametric Bayesian methods material has been presented at the International Conference on Machine Learning and at the Neural Information Processing Conference. Next month, Fox will present the material at the System Identification Symposium.

Fox measures her accomplishment in another way. “Success to me would be seeing fellow researchers and practitioners continue to build upon the methods I have developed and utilize them in application domains I had not thought of. One example of this is a student, Matthew Hoffman at PrincetonUniversity, who has used this model to synthesize music clips of unlimited length, driven and inspired by the structure of other music recordings at hand,” she says.

Massachusetts Institute of Technology:
U.S. Air Force Office of Scientific Research: