Principle:Online ml River Online Rule Learning
| Knowledge Sources | |
|---|---|
| Domains | Online_Learning, Rule_Based_Systems |
| Last Updated | 2026-02-08 18:00 GMT |
Overview
Online rule learning systems build and maintain a set of human-interpretable IF-THEN rules that are updated incrementally as data arrives. Each rule consists of a conjunction of conditions on feature values (the antecedent) and a prediction model (the consequent). Rules can be added, expanded, or removed in response to new data, providing an interpretable and adaptive model for streaming environments.
Rule-based models offer a compelling alternative to decision trees in online learning because they can represent overlapping regions and non-hierarchical decision boundaries.
Theoretical Basis
Rule Structure
A rule set R = {r_1, r_2, ..., r_m} where each rule has the form:
IF condition_1 AND condition_2 AND ... AND condition_k
THEN predict using model_r
Conditions are typically axis-aligned thresholds (e.g., x_j > v) or categorical equalities. The consequent model can be a constant (majority class or mean), a linear model, or any incremental learner.
Adaptive Model Rules (AMRules)
AMRules is an online rule learning algorithm designed for regression on high-speed data streams. Key mechanisms include:
- Rule creation: When no existing rule covers an instance, a default rule handles it. When the default rule accumulates sufficient statistics, a new specialized rule is created.
- Rule expansion: Existing rules are expanded (adding conditions) using the Hoeffding bound to ensure statistically significant splits, analogous to Hoeffding trees.
- Anomaly detection: Rules track the distribution of covered instances and can detect when a rule's coverage region has shifted.
- Rule removal: Underperforming rules are pruned based on error metrics.
Hoeffding Bound for Rule Expansion
The Hoeffding bound guarantees that the observed mean of a bounded random variable is close to the true mean with high probability:
epsilon = sqrt(R^2 * ln(1/delta) / (2n))
A rule is expanded by adding a new condition when the best split's quality exceeds the second-best by more than epsilon.
Advantages
- Interpretability: Rules are directly readable by domain experts.
- Modularity: Rules are independent; adding or removing one does not require retraining others.
- Parallelism: Rules can be updated and evaluated in parallel.