A Branch-and-Bound Framework for Unsupervised Common Event Discovery.

Area of Science:

• Computer Science
• Artificial Intelligence
• Machine Learning

Background:

• Supervised learning methods for event discovery face challenges with unknown or difficult-to-detect event labels.
• Existing approaches struggle when not all possible event combinations can be anticipated.

Purpose of the Study:

• Introduce Common Event Discovery (CED) as an unsupervised approach to identify variable-length common events in time series.
• Propose an efficient framework to overcome the computational challenges of exhaustive search in CED.

Main Methods:

• Developed an efficient branch-and-bound (B&B) framework to avoid prohibitive quartic costs associated with exhaustive search.
• Derived novel bounding functions for commonality measures and extended the framework for accelerated search.
• The B&B framework accepts multidimensional signals quantifiable into histograms, with generalizations for synchrony and event commonality.

Main Results:

• The proposed B&B framework efficiently finds globally optimal solutions for Common Event Discovery.
• Demonstrated effectiveness in analyzing motion capture data of deliberate behavior.
• Validated on spontaneous facial behavior in diverse video contexts, including interviews and parent-infant interactions.

Conclusions:

• The branch-and-bound framework provides an effective and efficient solution for unsupervised Common Event Discovery.
• The framework is generalizable to various signal types and event discovery tasks, including video search and supervised detection.
• Successfully applied to real-world data, showcasing its utility in understanding human behavior and interactions.