Implementation:Online ml River Tree MondrianTree

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

Overview

MondrianTree is an abstract base class that defines the core operations and properties shared by all Mondrian Tree implementations (classifier and regressor). It establishes the framework for trees based on the Mondrian process.

Description

This abstract base class provides the foundational structure for incremental decision trees that use a Mondrian process for split decision making. The Mondrian process is a stochastic process that hierarchically partitions space, with partition times sampled from exponential distributions based on the geometry of the data.

Key responsibilities:

Random number generation with seed control
Core hyperparameter management (step, loss, use_aggregation)
Iteration tracking
Abstract interface definition

Unlike Hoeffding Trees that use statistical bounds, Mondrian Trees use probabilistic time-based splitting, making them conceptually distinct despite both being incremental learning algorithms.

Code Reference

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

Signature:

class MondrianTree(abc.ABC):
    def __init__(
        self,
        step: float = 0.1,
        loss: str = "log",
        use_aggregation: bool = True,
        iteration: int = 0,
        seed: int | None = None,
    )

Import:

from river.tree.mondrian.mondrian_tree import MondrianTree

Usage

This is an abstract class and cannot be instantiated directly. Use concrete implementations:

from river.tree.mondrian import MondrianTreeClassifier, MondrianTreeRegressor

# Classification
clf = MondrianTreeClassifier(step=0.1, use_aggregation=True, seed=42)

# Regression
reg = MondrianTreeRegressor(step=0.1, use_aggregation=True, seed=42)

Parameters

step (float): Step parameter controlling weight updates (learning rate) - default: 0.1
loss (str): Loss type ("log" for classification, "least-squares" for regression) - default: "log"
use_aggregation (bool): Whether to use aggregation weighting - default: True
iteration (int): Initial iteration count - default: 0
seed (int | None): Random seed for reproducibility - default: None

Implementation Details

Attributes:

step (float): Learning rate for weight updates
loss (str): Loss function identifier
use_aggregation (bool): Aggregation flag
iteration (int): Number of samples processed
seed (int | None): Random seed
_rng (random.Random): Random number generator instance

Random Number Generation:

The class creates a dedicated Random instance:

self._rng = random.Random(seed)

This ensures: 1. Reproducibility when seed is set 2. Independence from global random state 3. Thread-safe random number generation

Mondrian Process Background

The Mondrian process is named after the Dutch painter Piet Mondrian, whose works consist of rectangular partitions. The process recursively partitions space:

1. Start with entire feature space at time 0 2. Sample split time T ~ Exponential(rate) 3. Choose split dimension proportional to range extensions 4. Sample split location uniformly in extended region 5. Recurse on both sub-spaces with new time T

Key Properties:

Self-consistent: Process can be extended without recomputing
Bayesian: Provides posterior distribution over tree structures
Adaptive: Split rate proportional to data spread

Loss Functions

Classification ("log"):

Logarithmic loss (negative log-likelihood)
Used with class probabilities
Weight update based on prediction error

Regression ("least-squares"):

Squared error loss
Used with continuous targets
Weight update based on prediction residual

Note: The loss parameter is currently a placeholder. Different metrics may become available in future versions.

Aggregation

Without Aggregation:

Predictions use only the reached leaf
Faster inference
Simpler implementation

With Aggregation:

Predictions combine contributions from all nodes on path
Weights computed via exponential of negative cumulative loss
More stable predictions
Better performance in many cases

Weight Update Formula:

At each node: weight_new = weight_old - step * loss

Aggregated Prediction:

P_aggregated = Σ w_i * P_i

where w_i is normalized weight at node i.

Subclass Requirements

Concrete implementations must define:

Abstract Methods:

These vary by task (classification vs regression) but typically include:

_score(node): Compute score for node
_predict(node): Get prediction from node
_loss(node): Compute loss for node
_update_weight(node): Update node weight
_update_count(node): Update node statistics
_update_downwards(...): Update node during downward pass
_compute_split_time(...): Calculate split time
_split(...): Execute split operation
_go_downwards(...): Downward tree update
_go_upwards(...): Upward weight propagation

Properties:

_is_initialized: Check if tree has seen data

Iteration Management

The iteration counter tracks samples processed:

def learn_one(self, x, y):
    # ... learning logic ...
    self.iteration += 1

Used to:

Control learning behavior (first iteration vs. subsequent)
Track total samples for diagnostics
Potentially adjust learning parameters over time

Random Sampling

The _rng instance provides reproducible randomness:

# Sample from exponential distribution
T = utils.random.exponential(1 / intensity, rng=self._rng)

# Sample feature proportionally
feature = self._rng.choices(candidates, weights, k=1)[0]

# Sample threshold uniformly
threshold = self._rng.uniform(min_val, max_val)

Step Parameter

The step parameter controls how aggressively weights are updated:

Small step (e.g., 0.01):

 * Slow adaptation
 * More stable
 * Less responsive to changes

Large step (e.g., 1.0):

 * Fast adaptation
 * More volatile
 * More responsive to changes

Default (0.1):

 * Balanced tradeoff

In practice, step acts similarly to a learning rate in gradient descent.

Design Philosophy

The MondrianTree base class embodies several principles:

1. Separation of Concerns: Base class handles common logic, subclasses handle task-specific details 2. Reproducibility: Dedicated RNG with seed control 3. Flexibility: Abstract interface allows diverse implementations 4. Simplicity: Minimal hyperparameters compared to Hoeffding Trees 5. Theory-Driven: Based on rigorous Bayesian framework

Comparison with HoeffdingTree Base

Feature	MondrianTree	HoeffdingTree
Split mechanism	Mondrian process	Hoeffding bound
Hyperparameters	step, seed	grace_period, delta, tau
Memory management	None (yet)	Sophisticated (leaf deactivation)
Theory	Bayesian	PAC (frequentist)
Visualization	Basic	Advanced (graphviz, DataFrame)
Aggregation	Built-in	None

Related Pages

References

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

The paper provides:

Mondrian process definition and properties
Tree construction algorithm
Aggregation weighting scheme
Theoretical analysis and guarantees
Extension to random forests

Page Connections

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

Principle

Implementation

Heuristic

Environment