Structuring ordered nominal data for event sequence discovery

Chreston A. Miller, Francis K. H. Quek, Naren RamakrishnanACM Multimedia 2010 · DOI

TL;DR

This paper introduces a novel method for understanding temporal event sequences by applying n-gram processing, traditionally used in speech recognition, to nominal event data. By encoding events with temporal relations, the authors enable probabilistic modeling of event sequences, allowing for better comparison and ranking of events within complex data streams.

What Problem Does This Paper Address?

Many real-world data streams, such as those from media (audio, video, motion), consist of events that are nominal (descriptive labels) rather than numerical. This makes it challenging to establish clear relational structures or orderings between events, hindering the discovery of meaningful patterns. For instance, analyzing a collaborative session requires understanding how gestures, speech, and gaze interact, but these are often nominal categories. Existing methods struggle to provide a robust way to compare and rank these nominal events, especially when dealing with temporal sequences and context-dependent relationships.

Methods

The core contribution of this paper is the application of n-gram processing to temporal, nominal event data. N-grams, a technique from speech processing, model the probability of a sequence of items (like phonemes or words) based on their predecessors. The authors extend this by:

  • Temporal Relation Encoding: Representing events not just by their labels but also by their start and end times. They leverage Allen's temporal relation principles [1] to encode the relationships between these start/end times using operators (<, =, >, etc.). This creates a linear data stream representation of temporal events, similar to how phonemes are sequenced in speech.
  • N-gram Application: Applying n-gram probabilistic modeling to these encoded event sequences. This allows the system to calculate the probability of one event (or event feature like start/end time) following another, effectively providing a relational understanding and ranking based on context and history.
  • Handling Overlap and Constraints: The paper discusses how n-gram processing can be adapted to handle overlapping events and temporal constraints by breaking down events into their start/end time components and potentially using multiple levels of n-gram processing or introducing "timing events."

Datasets

The authors used a dataset derived from baseball play-by-play information from the publicly available database at http://www.hokiesports.com/baseball/stats/2009/. They encoded a set of ten plays, resulting in 83 events with 48 unique events, to demonstrate their approach. This dataset is characterized by nominal event data relevant to a temporal sequence.

Key Insights and Ideas

  • Bridging Nominal and Temporal: The paper successfully bridges the gap between nominal, descriptive data and the need for structured, temporal analysis by adapting a proven probabilistic technique (n-grams).
  • Contextual Ranking: N-gram processing provides a way to probabilistically rank and compare nominal events based on their sequential context, which is crucial for understanding complex interactions.
  • Flexibility of N-grams: The n-gram framework, when applied to temporal event encodings, shows promise for handling various temporal relationships, including overlaps and potential constraints.
  • Foundation for Modeling: The ability to structure and rank nominal temporal data is a fundamental step towards building more sophisticated models of concurrent media streams and human behavior.

Key Results

The paper presents results from two queries on the baseball dataset:

  • Query 1 (Batter hits ball): The results (Table 1) show probabilistic distributions of events that can occur after a batter hits the ball and begins to run to first base. This includes probabilities for runner behavior and opponent player positioning.
  • Query 2 (SS catches ball): The results (Table 2) illustrate the probabilistic relationships of events leading up to a shortstop catching the ball, as well as subsequent actions. It highlights how previous events tend to conclude when the shortstop gains possession.

The results demonstrate the system's ability to provide probabilistic distributions of previous/next events and associated relational operators, offering insights into event interactions.

Limitations and Future Work

  • Limitations:
    • The current implementation does not include support for time constraints.
  • The experiment used a small subset of baseball plays (ten plays, 83 events).
  • The probabilistic distributions are presented with rounding errors (±.02).
  • Future Work:
    • Further investigation into the relational operators and how multiple occurrences can be handled.
  • Incorporating time constraints into the n-gram processing.
  • Exploring how event overlap influences n-gram processing.
  • Testing the approach on larger and more complex datasets, such as those from military exercises and wargame scenarios.

Summary updated

BibTeX
@inproceedings{miller2010structuring,
  author = {Chreston A. Miller and Francis K. H. Quek and Naren Ramakrishnan},
  title = {{Structuring ordered nominal data for event sequence discovery}},
  booktitle = {ACM Multimedia},
  year = {2010},
  doi = {10.1145/1873951.1874153},
}

Loading related content...

Figure