Unsupervised Frequent Pattern Mining for CEP

Guy Shapira, Assaf SchusterarXiv 2022 · DOI · arXiv

Abstract

Complex Event Processing (CEP) is a critical component of real-time monitoring systems in domains ranging from high-frequency finance to cybersecurity. However, the efficacy of CEP is traditionally limited by the "expert bottleneck"—the requirement for human specialists to manually define patterns. This paper introduces REDEEMER (REinforcement baseD cEp pattErn MinER), a novel framework designed to automate the discovery of meaningful patterns in massive, high-dimensional data streams. By integrating Action-Branching Reinforcement Learning with Active Learning and Bayesian Search, REDEEMER identifies complex event relationships with minimal human intervention, effectively uncovering "unknown unknowns" in streaming data.

Introduction

In the modern data landscape, systems must react to events as they happen. Complex Event Processing (CEP) facilitates this by matching incoming data streams against predefined logical patterns—for instance, triggering a security alert if a specific sequence of unauthorized access attempts occurs within a narrow time window.

Despite its utility, CEP faces a significant scalability challenge. Most patterns are authored manually by domain experts. This process is not only expensive and time-consuming but also inherently limited by human perception; experts can only write patterns for behaviors they already anticipate. Existing automated tools often focus on optimizing known patterns rather than discovering entirely new ones. REDEEMER addresses this gap by providing a semi-supervised approach to pattern discovery, navigating astronomical search spaces to find frequent, meaningful event sequences without overwhelming human supervisors.

Methodology

REDEEMER’s architecture is built upon three technical pillars designed to balance computational efficiency with human-centric relevance.

1. Action-Branching Actor-Critic (A2C)

The primary challenge in automated pattern mining is the combinatorial explosion of the search space. A pattern consists of multiple events, each with various attributes and conditions. To make this tractable, REDEEMER employs an "Action Branching" strategy. Instead of a single neural network attempting to select a complete pattern in one step, the model utilizes a multi-branch architecture. One branch selects the event type (e.g., "Sensor Trigger"), while parallel branches select associated conditions (e.g., "Threshold > X"). This "divide and conquer" approach allows the Reinforcement Learning (RL) agent to navigate billions of possible combinations effectively.

2. Active Learning Loop

To ensure the discovered patterns are meaningful rather than just statistical noise, REDEEMER incorporates a human-in-the-loop component. To minimize the burden on the expert, the system uses an uncertainty-based Active Learning strategy. The model only queries the expert to rank or validate a pattern when its internal confidence is lowest. This ensures that every human interaction provides maximum information gain, allowing the model to align its internal reward function with human intuition using very few labels.

3. Bayesian Search for Parameter Optimization

While the RL agent handles the logical structure of the pattern (the "formula"), the specific constants—such as exact time windows or sensor thresholds—are optimized using Bayesian search. This dual-optimization approach ensures that the logical skeletons discovered by the RL agent are precisely tuned to maximize their frequency and relevance within the actual dataset.

Experimental Evaluation

The researchers evaluated REDEEMER across three high-dimensional environments to test its versatility:

  • StarPilot: A synthetic dataset from OpenAI’s Procgen benchmarks, involving complex interactions between spaceship movement, health metrics, and combat events.
  • Professional Football: Real-world sensor data from a 2013 match, featuring high-frequency (2000Hz) tracking of players and the ball.
  • GPU Cluster Logs: A month-long operational log from a research server cluster, tracking power, temperature, and memory utilization.

Key Results and Insights

REDEEMER demonstrated significant improvements over standard RL baselines such as Vanilla Actor-Critic (VAC) and Deep Deterministic Policy Gradient (DDPG).

Superior Generalization and Accuracy

In the football dataset, REDEEMER achieved over 90% accuracy in predicting how a human expert would rank unseen patterns. This suggests that the model successfully learned the underlying concept of "meaningfulness" rather than simply memorizing frequent sequences.

Discovery of Complex Tactics

A standout result was the system’s ability to mine complex tactical patterns without prior domain knowledge. In the football environment, REDEEMER successfully identified a "double-pass" sequence (Player A passes to B, who immediately returns the ball to A). The system recognized this as a frequent and meaningful pattern purely through data observation and minimal feedback.

Robustness to Expert Noise

Real-world experts are rarely perfect. The researchers simulated noisy labeling and found that REDEEMER maintained a steady learning curve even when human feedback was inconsistent. This robustness is vital for deployment in messy, real-world environments where expert time is fragmented and prone to error.

Limitations and Future Work

While REDEEMER represents a leap forward in automated CEP, several challenges remain. The current action space is limited to sequential patterns; future iterations could expand the pattern language to include complex logical operators like "NOT" or "OR" across asynchronous time windows. Additionally, the framework currently relies on a single source of expertise. Incorporating "crowdsourced" feedback from multiple experts with varying reliability levels is a promising avenue for future research.

Conclusion

REDEEMER shifts the paradigm of Complex Event Processing from manual definition to automated discovery. By combining the exploratory power of Reinforcement Learning with the precision of Active Learning, it allows organizations to uncover critical insights hidden within their data streams, effectively bridging the gap between massive raw data and actionable human knowledge.

Summary updated

Abstract

Complex Event Processing (CEP) is a set of methods that allow efficient knowledge extraction from massive data streams using complex and highly descriptive patterns. Numerous applications, such as online finance, healthcare monitoring and fraud detection use CEP technologies to capture critical alerts, potential threats, or vital notifications in real time. As of today, in many fields, patterns are manually defined by human experts. However, desired patterns often contain convoluted relations that are difficult for humans to detect, and human expertise is scarce in many domains. We present REDEEMER (REinforcement baseD cEp pattErn MinER), a novel reinforcement and active learning approach aimed at mining CEP patterns that allow expansion of the knowledge extracted while reducing the human effort required. This approach includes a novel policy gradient method for vast multivariate spaces and a new way to combine reinforcement and active learning for CEP rule learning while minimizing the number of labels needed for training. REDEEMER aims to enable CEP integration in domains that could not utilize it before. To the best of our knowledge, REDEEMER is the first system that suggests new CEP rules that were not observed beforehand, and is the first method aimed for increasing pattern knowledge in fields where experts do not possess sufficient information required for CEP tools. Our experiments on diverse data-sets demonstrate that REDEEMER is able to extend pattern knowledge while outperforming several state-of-the-art reinforcement learning methods for pattern mining.
BibTeX
@misc{shapira2022unsupervised,
  author = {Guy Shapira and Assaf Schuster},
  title = {{Unsupervised Frequent Pattern Mining for CEP}},
  year = {2022},
  eprint = {2207.14017},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.14017},
}
Figure