A Model for Reasoning with Uncertain Rules in Event Composition Systems

Segev Wasserkrug, Avigdor Gal, Opher EtzionUAI 2005

TL;DR

This paper introduces a formal framework for active systems to reason about uncertain events. It tackles the challenge of inferring complex business events from simpler signals, where the relationships between events are not always deterministic. The authors propose a novel approach that combines probabilistic reasoning with event composition, enabling systems to quantify the likelihood of inferred events.

What Problem Does This Paper Address?

Modern active systems, like those used in Business Activity Monitoring (BAM) and Business Process Management (BPM), are designed to react automatically to events. These events can range from IT system alerts to complex business-level occurrences. A significant challenge arises when the events a system needs to respond to are not directly observable but must be inferred from other, simpler events. Existing event composition systems typically handle these inferences deterministically, assuming perfect knowledge of event relationships. However, in many real-world scenarios, this inference is inherently uncertain. For instance, a banking system might need to detect illegal stock trading, but it can only infer this from purchase and sale events, where the certainty of illegal activity is not absolute. This paper addresses this gap by providing a formal model to represent and reason about this uncertainty in event composition.

Methods

The core of the paper is a formal framework for representing and reasoning about uncertain event composition.

  • Uncertainty Representation: The authors use probability theory to represent uncertainty. Instead of a single value, the data associated with an event instance (Event Instance Data or EID) is modeled as a Random Variable (RV). This allows for representing the probability of an event occurring with specific attributes or not occurring at all.
  • Rule Model: The system uses rules to define relationships between events. These rules consist of:
  • seln: A deterministic predicate to select a subset of events from an event history.
  • pattern: A (possibly complex temporal) predicate applied to the selected events.
  • eventTyper: The type of the inferred event.
  • mappingExpressionsr: Functions to map attributes of the triggering events to the inferred event.
  • probr: A probability associated with the rule, representing the likelihood of inferring the event if the pattern matches.
  • Probability Space: The paper defines a probability space using possible world semantics and an EID representation. This space captures the knowledge of the system about event histories at any given time.
  • Probabilistic Reasoning: The authors adopt a paradigm similar to Knowledge-Based Model Construction (KBMC). When an inference is needed, a Bayesian network is dynamically constructed based on the defined rules and the current event history. This network is then used to calculate the probabilities of inferred events.

What's new here is the formal integration of probabilistic semantics into event composition rules, moving beyond deterministic inference. The dynamic construction of Bayesian networks tailored to the current event history is also a key aspect.

Datasets

Not discussed in the paper. The paper focuses on a formal framework and uses illustrative examples (e.g., stock trading) rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Uncertainty is Inherent: Real-world event inference is often probabilistic, not deterministic. Ignoring this leads to brittle active systems.
  • Formalizing Probabilistic Event Composition: The paper provides a rigorous mathematical foundation for combining event composition with probability theory, allowing for a principled way to handle uncertainty.
  • Dynamic Bayesian Networks for Inference: The approach of dynamically constructing Bayesian networks based on incoming events and defined rules is crucial. This allows the system to adapt its reasoning model as new information becomes available.
  • Rules as Probabilistic Templates: Rules are not just triggers but also sources of probabilistic information, with probr quantifying the likelihood of an inferred event.
  • EID as Random Variables: Modeling Event Instance Data as Random Variables is a powerful abstraction that directly incorporates uncertainty into the representation of event information.

Key Results

The paper presents a formal framework and a method for calculating probabilities of inferred events. While specific quantitative results are not provided (as it's a theoretical framework paper), the key outcome is the enablement of active systems to handle uncertainty in event composition. The authors demonstrate how their framework can be used to:

  • Formally define the representation and semantics of event composition for probabilistic settings.
  • Quantify the occurrence probability of inferred events.
  • Handle both imprecise information uncertainty and uncertain relations between events.

The paper provides an example illustrating the dynamic construction of Bayesian networks for a specific rule, showing how the network evolves as new events are observed.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Computational Cost: Calculating probabilities from Bayesian networks can be computationally expensive. The paper mentions that speeding up this step is a topic for future research.
  • Dynamic Update Efficiency: While the paper proposes dynamic updates, further improvements in the efficiency of updating the inference model (e.g., using techniques for incremental junction tree updates) are suggested.
  • Prediction of Future Events: The current model focuses on inferring past or present events. Extending it to predict future events would be a valuable future direction.
  • Handling Cycles in Rules: The current algorithm assumes rules have no cycles for determinism. Handling cyclic dependencies in rules would be an extension.
  • General Algorithm for Bayesian Network Construction: The paper details the algorithm for a specific language (l₁) but notes that a general algorithm for arbitrary languages is not provided.

Summary updated

BibTeX
@inproceedings{wasserkrug2005model,
  author = {Segev Wasserkrug and Avigdor Gal and Opher Etzion},
  title = {{A Model for Reasoning with Uncertain Rules in Event Composition Systems}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
}
Figure