Implementation:Online ml River Tree MondrianTreeRegressor

Knowledge Sources	Online_ml_River
Domains	Online_Learning, Decision_Trees, Regression, Mondrian_Process
Last Updated	2026-02-08 16:00 GMT

Overview

Mondrian Tree Regressor is an online decision tree for regression that uses a Mondrian process to determine split times and locations. It provides fast incremental learning with optional aggregation weighting for improved predictions.

Description

The Mondrian Tree Regressor applies the Mondrian process to regression tasks, using squared error loss to guide weight updates. Like its classification counterpart, it samples split times from exponential distributions based on feature range extensions, creating an adaptive tree structure without requiring grace periods or Hoeffding bounds.

Key features:

Mondrian process-based splitting
Squared error loss for weight updates
Aggregation weighting for combining predictions
Running mean computation at each node
Theoretically grounded in Bayesian online learning

The algorithm maintains feature ranges at every node and uses the Mondrian process to decide when splits should occur, making it particularly responsive to data that extends beyond previously observed ranges.

Usage

from river import datasets
from river import evaluate
from river import metrics
from river import tree

dataset = datasets.TrumpApproval()

model = tree.mondrian.MondrianTreeRegressor(
    step=0.1,
    use_aggregation=True,
    seed=42
)

metric = metrics.MAE()

# Note: No example result provided in source

Code Reference

Source Location: /tmp/kapso_repo_178qi9vb/river/tree/mondrian/mondrian_tree_regressor.py

Signature:

class MondrianTreeRegressor(MondrianTree, base.Regressor):
    def __init__(
        self,
        step: float = 0.1,
        use_aggregation: bool = True,
        iteration: int = 0,
        seed: int | None = None,
    )

Import:

from river.tree.mondrian import MondrianTreeRegressor

I/O Contract

Input:

x (dict): Feature dictionary with attribute names as keys
y (float): Target regression value

Output:

predict_one(x): Predicted regression value (float)

Key Parameters

step (float): Step parameter controlling weight updates (learning rate)
use_aggregation (bool): Enable aggregation weighting across tree levels
iteration (int): Current iteration count (typically start at 0)
seed (int): Random seed for reproducibility

Implementation Details

Key Methods:

learn_one(x, y): Incrementally train on one instance
predict_one(x): Predict target value
_go_downwards(): Update tree from root to leaf
_go_upwards(leaf): Update weights from leaf to root
_compute_split_time(node, extensions_sum): Calculate split time via Mondrian process
_split(node, split_time, threshold, feature, is_right_extension): Execute split
_predict(node): Get prediction from node (returns mean)
_loss(node): Compute squared error loss

Node Types:

MondrianLeafRegressor: Leaf node with running mean
MondrianBranchRegressor: Branch node with split information

Mondrian Process

The regression variant uses the same Mondrian process as classification:

Range Extension:

For each feature j and sample x: 1. Compute current range: [min_j, max_j] at node 2. Calculate extension:

  * If x_j < min_j: extension = min_j - x_j
  * If x_j > max_j: extension = x_j - max_j
  * Otherwise: extension = 0

3. Sum extensions: E = Σⱼ extension_j

Split Time Sampling:

If E > 0: 1. Sample T ~ Exponential(1/E) 2. Split time = node.time + T 3. For branches, compare with child times 4. Split if split_time < child_time

Split Feature Selection:

Sample feature j with probability proportional to its range extension: P(j) = extension_j / E

Threshold Sampling:

If right extension: threshold ~ Uniform(range_max, x_j)
If left extension: threshold ~ Uniform(x_j, range_min)

Learning Algorithm

Downward Phase:

1. Start at root node 2. For each node on path to leaf:

  * Compute range extensions for current sample
  * Sample split time from Mondrian process
  * If split time triggers:
    * Sample feature proportionally to extensions
    * Sample threshold uniformly in extension region
    * Create new branch with two children
    * Route sample to appropriate child
  * If no split:
    * Update node statistics and range
    * Move to next child

3. Reach leaf and update statistics

Upward Phase (if aggregation enabled):

1. Start at the reached leaf 2. Update weight_tree at each node from leaf to root 3. Combines node weight with children's weight_tree

Prediction with Aggregation

Without aggregation:

Use leaf node mean only

With aggregation: 1. Start at reached leaf 2. Move upward to root 3. At each node:

  * Compute weight: w = exp(weight - log_weight_tree)
  * Get node prediction: pred_node = node.mean.get()
  * Combine: pred = 0.5 * w * pred_node + (1 - 0.5 * w) * pred_prev

4. Final prediction uses contributions from all ancestors

Loss and Weight Update

Loss Function:

Squared error: L(y, ŷ) = (ŷ - y)² / 2

where ŷ = node.mean.get()

Weight Update:

At each node during downward pass: weight -= step * loss(y)

Only applied if use_aggregation=True and do_update_weight=True.

Split Decision Logic

Split Conditions:

Always consider splitting if range extension exists (E > 0).

For leaf nodes:

Always split if extension exists and split time sampled

For branch nodes:

Split if sampled split_time < child_time
This inserts a new split above existing subtree

No purity check needed for regression (unlike classification).

Properties

The tree tracks:

iteration: Number of samples processed
_root: Root node (initially a leaf)
_x: Current sample features (during processing)
_y: Current target value (during processing)

Nodes track:

time: Creation time in Mondrian process
depth: Level in tree
n_samples: Sample count
mean: Running mean of target values (stats.Mean object)
memory_range_min/max: Feature ranges
weight: Node weight (for aggregation)
log_weight_tree: Combined weight with subtree

Comparison with Hoeffding Tree Regressor

Feature	Mondrian Tree	Hoeffding Tree
Split criterion	Mondrian process	Variance reduction + Hoeffding bound
Hyperparameters	step, seed	grace_period, delta, tau
Split timing	Stochastic (exponential)	Deterministic (grace period)
Aggregation	Optional (weighted)	None (single leaf)
Theory	Bayesian	Frequentist (PAC)
Range tracking	All nodes	Not needed

Advantages

1. No Grace Period: Can split immediately if range extends 2. Flexible: Adapts split timing to data distribution 3. Aggregation: Uses entire path for prediction 4. Simple: Fewer hyperparameters than Hoeffding Trees 5. Bayesian: Principled probabilistic framework

Limitations

1. Memory: Maintains range information at all nodes 2. Performance: May not always match Hoeffding Trees on stationary data 3. Interpretability: Split times less intuitive than statistical tests 4. Complexity: Mondrian process requires understanding stochastic processes

Example Workflow

from river.tree.mondrian import MondrianTreeRegressor

# Initialize
tree = MondrianTreeRegressor(step=0.1, use_aggregation=True, seed=42)

# Learn from stream
for x, y in data_stream:
    # Get prediction before learning
    y_pred = tree.predict_one(x)

    # Update tree
    tree.learn_one(x, y)

# Tree properties
print(f"Iterations: {tree.iteration}")
print(f"Height: {tree.height}")
print(f"Nodes: {tree.n_nodes}")

Related Pages

References

Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh. "Mondrian Forests: Efficient Online Random Forests." arXiv:1406.2673, pages 2-4.

Page Connections

Double-click a node to navigate. Hold to expand connections.

Principle

Implementation

Heuristic

Environment