Introduction
Detecting complex events (CEs) within massive, noisy data streams is a significant challenge in fields ranging from network security to behavioral monitoring. These events are typically composed of short activity bursts, or episodes, separated by long intervals of irrelevant data. Traditional sequence learning models often fail to maintain temporal coherence across these gaps. This paper presents a novel approach using Hierarchical Hidden Markov Models (HHMMs) and a bottom-up induction algorithm to bridge these gaps through abstraction.
Methodology: Bottom-Up Induction and Abstraction
The core of the proposed system is a bottom-up learning algorithm designed to construct HHMMs. Unlike standard HMMs, HHMMs represent patterns at multiple levels of granularity, allowing the model to capture both fine-grained actions and high-level behaviors.
The induction process involves two primary steps:
- Abstraction: Atomic events (e.g., individual keystrokes) are progressively grouped into higher-level episodes.
- Coarsening: By increasing the granularity of the sequence, the model allows correlations to emerge between subsequences that are otherwise separated by significant temporal distances.
Feature Engineering for Keystroke Dynamics
To evaluate the model, the authors focused on keystroke dynamics—identifying users based on their typing rhythms. Rather than analyzing specific characters, the keyboard was divided into 10 regions. Mapping keys to these regions shifted the focus from the content of the text to the physical movement of the user's hands, capturing a unique behavioral "signature" that remains consistent across different vocabularies.
Experimental Evaluation
The method was tested on two primary datasets:
- Key Phrase Dataset: Four volunteers typed a 22-syllable sentence 140 times. The system recorded keypress durations and inter-stroke delays.
- Text Typing Dataset: A corpus of 2,280 words was typed by four users in multiple sessions, resulting in approximately 1,350 subsequences.
Results and Discussion
The HHMM approach demonstrated high efficacy in biometric identification. In the fixed-phrase experiment, the model achieved near-perfect accuracy with only one commission error out of 160 test traces.
In the free-form text profiling, the system showed a clear statistical separation between the "legal" user and others. The scoring, measured in log-odds, indicated that the probability of the model generating the correct user's sequence was significantly higher than generating a sequence from any other user.
As shown in Figure 3, the distribution of log-odds scores for the positive class is distinctly shifted to the right compared to the negative class. The authors noted that a simple "2-out-of-3" rule—requiring two out of three consecutive sequences to exceed a threshold—would result in perfect discrimination with zero false alarms.
Conclusion
This research highlights abstraction as a powerful mechanism for handling the "long gap" problem in sequence learning. By focusing on behavioral style rather than substance, the HHMM-based system provides a robust framework for complex event detection. Future work will explore the scalability of this approach to larger user bases and its applicability to other domains such as network traffic analysis.
Summary updated