A visual 32-page introduction from decision trees to online updates
Prepared for MSc Data Science study | Based primarily on Lakshminarayanan, Roy and Teh (2014)
Read in order once; return to pages 12-31 while reading the paper.
How can a random-forest-style model learn from new observations one at a time without rebuilding every tree from the beginning?
We begin with the standard model. One model divides the feature space into regions.
A single tree is unstable. Many random trees combine their predictions to form an ensemble.
The core problem. New observations arrive sequentially and the model must adapt immediately.
A mathematical tool. A random, time-labelled partition creates extendable trees.
The specific methodology in the 2014 paper. Training, extension, prediction and label smoothing.
These notes explain the 2014 classification paper entirely within the context of tree-based methods. Later Mondrian variants expand the idea to regression tasks and alternative online aggregation.
Features go in; a class label or numerical value comes out.
$x = \text{features, } y = \text{answer}$
Find useful patterns in the historical data
Stores the learned mathematical rules
Estimate $y$ for a completely new $x$
The answer is a category. Examples include predicting cat/dog, fraud/not fraud, or class 1/2/3. The 2014 Mondrian paper evaluates classification tasks.
The answer is a continuous number. Examples include predicting a house price, product demand, or a continuous risk score.
With two features, each observation is a point on a flat plane. A classifier draws boundaries that divide this plane into distinct regions. A decision tree specifically draws axis-aligned boundaries, creating vertical or horizontal cuts across the space.
A sequence of yes/no questions routes each observation to a leaf.
An internal node contains a logical test, such as $x_1 \le 4.5$. This test routes the observations into two separate groups based on their feature values.
A leaf node represents a terminal region. The tree assigns a prediction to this region based on the labels of the training observations that fall into it.
Standard trees search through many possible features and cut points. They prefer the cut that produces the purest child groups. Algorithms like CART commonly use Gini impurity to measure this purity. Other trees may use entropy for classification or variance reduction for regression.
Mondrian-tree splits are sampled from geometry. They do not use class labels to choose the split location or dimension. The tree relies on labels entirely after the structure is built to make its final predictions.
This demonstrates standard-tree behaviour. Mondrian trees select splits differently.
Six blue observations and four orange observations are mixed together. A useful split should make the resulting child nodes less mixed.
For class proportions $p_1, \dots, p_K$, the calculation is $\text{Gini} = 1 - \sum_{k=1}^K (p_k^2)$. The value is $0$ for a perfectly pure node. The value increases when classes are thoroughly mixed within the node.
| Node | Blue ($p_1$) | Orange ($p_2$) | Gini Score |
|---|---|---|---|
| Parent | 0.60 | 0.40 | 0.48 |
| A - child 1 | 1.00 | 0.00 | 0.00 |
| A - child 2 | 0.20 | 0.80 | 0.32 |
| B - each child | 0.60 | 0.40 | 0.48 |
Standard trees evaluate exact label distributions to optimise split quality. Mondrian trees trade that label-driven optimisation for random, geometric splits. These random splits possess a special online extension property.
Bagging reduces instability by averaging many varied trees.
combine tree probabilities / votes
A standard Random Forest uses bootstrap samples and random feature subsets to build independent trees. Splits within those trees are normally chosen using labels and an impurity criterion.
A Mondrian Forest uses independent Mondrian trees. Its split geometry is completely random and supports consistent online extension. It still averages the predictions from multiple trees.
Both methods are ensembles. Several imperfect and varied trees combine their individual calculations to produce a steadier, more accurate final prediction.
The difference concerns when data become available and how the model incorporates updates.
In a streaming environment, a common testing sequence is test-then-train. The model predicts the label for the incoming point, records the error for evaluation purposes, and then updates its internal structure once the true label is revealed.
A model may update online while still treating all old observations as permanently relevant. Drift-aware systems often need mechanisms like forgetting, observation weighting, fixed windows, or explicit change detection. The original Mondrian Forest paper focuses exclusively on efficient online extension. It does not present a complete drift-management system.
The input appearance changes over time, such as changing lighting or backgrounds in images.
The fundamental relationship between the features and the correct answer changes over time.
A repeated batch workflow may keep historical observations and train a new forest whenever the dataset grows. The cost of each retraining cycle becomes larger as the stream continues.
Historical data are commonly retained or reloaded, and the complete model is fitted again.
The existing trees are extended. The model stores node geometry and label statistics rather than rebuilding every tree.
The chart is a schematic resource comparison. The 2014 paper reports computational complexity and training times rather than RAM traces.
A slowly growing online model state is compared with a workflow that retains an expanding history for repeated fitting.
Every leaf corresponds to a rectangular region of feature space.
A rule such as $x_d \le x_i$ cuts one rectangular region into two. Repeating this operation creates the geometric hierarchy represented by the decision tree model.
The rectangular partitions resemble the grid-like compositions associated with the artist Piet Mondrian. The underlying mathematical object that generates these cuts is called a Mondrian process.
This perspective is useful for following a prediction sequentially from the root node to a leaf node.
This geometric perspective is useful for understanding the spatial limits and behaviour of Mondrian cuts.
A random clock decides when a rectangle splits; its side lengths influence the clock rate.
The variable $E$ is an exponential waiting time. The rate of this exponential clock is equal to the sum of the region's side lengths. In two dimensions, this rate is simply the width plus the height.
The algorithm must choose a dimension to split. It makes this choice with a probability proportional to each side length. Longer dimensions possess a higher probability of being cut.
After choosing the dimension, the exact cut point is chosen uniformly along that side. The algorithm then repeats this entire random process independently inside the two newly created child rectangles.
The paper applies this process exclusively to the bounding boxes of observed training points. If the process were applied to an infinite space, it would run forever. Bounding the process ensures the stored tree remains finite.
Each node has a recorded time. The lifetime parameter lambda stops tree growth.
A small lambda prevents the tree from running its clocks for long. This results in few splits, large leaf regions, and a smoother, simpler partition model.
A large lambda allows the internal clocks to run longer. This generates more splits, smaller leaf regions, and a highly detailed partition of the feature space.
The implementation in the 2014 experiments pauses pure leaves rather than stopping at a finite lifetime. The tree only stops expanding when all labels in a block are identical.
The lambda parameter plays a role similar to a complexity control such as maximum depth in standard random forests. However, lambda operates continuously in time rather than simply counting the discrete number of nodes.
Mondrian splits are committed only where training data have actually been observed.
Outside the grey boundary box, the old tree structure has made no fixed geometric commitment. A new observation arriving in this space can therefore trigger the creation of an earlier split that was never needed previously.
If a new observation arrives inside the boundary box, the algorithm follows the existing split structure down the tree. It then simply updates the extent of the relevant node.
A conventional decision tree diagram often suggests that each rule applies infinitely across the entire parent region. A Mondrian split is strictly tied to the observed-data extent at that node. This uncommitted exterior is the exact property that makes online extension computationally feasible.
$B_j$ denotes the full spatial block represented by a node. $B_j^x$ denotes the smallest axis-aligned rectangle that entirely encloses the training observations currently held at that node.
When a point lies outside the current observed-data box, the tree measures the extra extent. It may insert a new split above the current node if the sampled split time is earlier.
The node records the smallest rectangle that contains the observations it has already seen.
The new point lies outside the known extent, so the current rectangle must expand.
The expanded box contains all points. A sampled earlier split can become a new parent; otherwise the existing node is simply extended.
The online update either inserts a new parent node or extends an existing node and recurses.
The algorithm measures how far $x$ sits beyond the current lower or upper boundaries across every dimension.
The algorithm draws a new waiting time from an exponential distribution. The rate of this new clock equals the total extra extent.
If the newly sampled time is earlier than the existing node's split time, a new parent node is inserted above the current position.
If the new time is later, the algorithm simply expands the bounding box to enclose the new point and recurses down the existing tree path.
A point located further away produces a larger extra extent. This larger extent creates a faster exponential clock, increasing the mathematical probability that a new split will be inserted above the existing node.
A distant new point can create a split above an older split while the old subtree remains intact.
The old root and both old leaves remain as one complete subtree.
Its sampled split time occurs before the old root split time, so it becomes the parent.
The arriving point occupies the sibling leaf on the other side of the new split.
A tree restricted to a subset of points follows the identical probability law as a tree built directly on those points.
The individual random trees generated by the two routes need not be visually identical at the node level. The property simply means the online update procedure samples from the exact same mathematical probability law as a fresh batch construction on the enlarged dataset.
This strict batch-online distributional agreement is the primary theoretical feature distinguishing Mondrian Forests from earlier online random-forest schemes, which often relied on approximations or heuristic split-decisions.
Tree geometry is generated randomly; label information enters through class counts and a mathematical hierarchy.
Because the Mondrian splits are random, a leaf may ultimately contain very few observations. Relying solely on the raw frequency of a tiny sample creates extreme, unreliable probabilities. To counteract this, the paper implements a hierarchical Bayesian label model (specifically using an interpolated Kneser-Ney approximation). This structure forces a node to borrow statistical strength from its parent.
If a child node is created very soon after its parent, the algorithm forces the child's prediction to remain highly similar to the parent's established prediction.
If the child node represents a split occurring significantly later in time, the node places much greater weight on the specific observations within its own local region.
The method calculates an average over the locations where the test point could branch away.
The algorithm computes the mathematical probability that the test point branches off. This calculation requires the test point's specific distance outside the original bounding box and the continuous exponential rate associated with that node.
The algorithm adds the class-probability contribution from every theoretical branch point. It weights these contributions by the probability of reaching and separating at that specific location. If the mathematics dictate no separation occurs, the system simply uses the reached leaf prediction.
Predictions systematically become less certain as a test point moves further away from the regions actively supported by training data. The model acknowledges uncertainty rather than blindly extending the nearest leaf rule into infinity.
The original pseudocode detailed in the paper separates the logic into four distinct computational jobs.
The foundational step. The algorithm recursively draws split times, dimensions, and locations to construct the initial unlabelled geometric structure.
The online adaptation step. The algorithm inserts a parent node or expands an existing node boundary when a new labelled point arrives from the data stream.
The statistical step. The system updates the class frequencies along the affected path to prepare the hierarchical Bayesian smoothing approximations.
The evaluation step. The algorithm traverses the updated tree and calculates the weighted average of possible test-point extensions.
Assuming the tree remains reasonably balanced, a single update or prediction follows a path whose length grows proportionally to $\log N$. The original paper notes that the total processing cost scales as $\mathcal{O}(N \log N)$. In contrast, repeating a full batch retraining after every single data arrival produces a heavy computational burden scaling as $\mathcal{O}(N^2 \log N)$.
The methods may all process trees, but their statistical ideas and update rules differ.
| Method | Data mode | How splits are chosen | How predictions combine | New-data treatment | Exact Mondrian batch-online property |
|---|---|---|---|---|---|
| Batch Random Forest | Batch | Labels guide impurity reduction; feature subsets add randomness | Model combination across many trees | Usually rebuild or refit on an enlarged dataset | No |
| Mondrian Forest | Online or batch | Random geometric cuts independent of labels | Model combination across independent Mondrian trees | Extend bounding boxes and sometimes insert an earlier parent | Yes |
| ORF-Saffari | Online | Candidate split scores at leaves use labels and confidence rules | Model combination across online trees | Update leaf statistics; commit a selected split when rules are met | No |
| Dynamic trees | Online Bayesian method | Posterior tree proposals use feature and label likelihood information | Bayesian model averaging across particles | Update a particle approximation to the tree posterior | No |
Random Forests and Mondrian Forests keep a diverse collection of trees and average their outputs.
Dynamic trees weight particles as an approximation to uncertainty about the underlying tree model.
None of these labels by itself means that old concepts will be forgotten when the data-generating relationship changes.
The paper compares cumulative work under balanced-tree assumptions.
Logarithmic vertical scale; curves come from the stated complexity formulas rather than measured seconds.
Each arriving point usually follows one root-to-leaf path. Under a balanced-tree assumption, that path has length proportional to $\log N$.
The entire forest is fitted again after each arrival. Work accumulates across successively larger datasets.
The authors report at least an order-of-magnitude speed advantage against repeated batch retraining and the compared earlier online forest on several datasets.
The exact runtime depends on implementation, hardware, tree balance, feature count and the chosen comparison procedure. The chart above explains asymptotic growth only.
The authors tested predictive accuracy as more data arrive sequentially, and accuracy against total training time.
On standard datasets like USPS, Satimages, and Letter, Mondrian Forests achieved accuracy very close to the batch forest variants. The algorithm exceeded the accuracy of the compared online forest, while processing the stream much faster than repeated batch retraining.
The algorithm performs poorly on the DNA dataset. The random splitting mechanism does not use class labels, meaning the tree wastes splits on irrelevant features instead of isolating useful signals.
The plots above are illustrative sketches intended to show the general convergence trends. They are not digitised measurements. Consult Figure 3 of the original paper for the precise reported curves and experimental parameters.
The paper reports accuracy close to strong batch forests on several datasets, while training is at least an order of magnitude faster than repeatedly trained batch versions and the earlier online forest comparison.
The main weakness appears when many features are irrelevant because Mondrian split geometry does not inspect labels.
Lower is better. This is a schematic display of the order reported in the paper.
A paper-style schematic, not digitised measurements from Figure 3.
These charts reproduce the useful visual ideas from the supplied infographic. Their values are illustrative examples, not measurements reported by the 2014 paper.
A lower error curve means the model reaches useful performance after fewer incoming observations.
The comparison separates initial fitting, a small online update, full batch retraining and prediction.
This experiment makes the main weakness of label-independent splitting easy to see.
Random cuts can spend many splits on dimensions with little predictive value.
Filtering irrelevant dimensions improves both MF and the closely related ERT-1 model.
On DNA, plain MF and ERT-1 trail the label-guided batch forests. The paper links this weakness to the presence of irrelevant dimensions.
Dynamic trees outperform plain MF on DNA, but MF† reaches similar test accuracy after the feature filter. MF performs better than dynamic trees on USPS, Satimages and Letter.
A Mondrian Forest may need careful feature work when the input contains many weak or irrelevant variables. Fast online updates do not remove the need for sensible data representation.
The tree needs geometric, structural and label information for later updates and predictions.
Lower and upper values for every feature: roughly $2D$ numbers.
Split dimension, split location and split time.
Class counts and the values used by the smoothing approximation.
Parent and child references, plus node or leaf status.
This expression is an explanatory approximation. Exact memory depends on the code, data types, sparse structures and implementation choices.
Bounding-box storage and geometric calculations grow directly with the number of features.
Every additional tree carries its own structure, boxes and label statistics.
The authors note that computation is linear in the number of dimensions because rectangles are represented explicitly. They identify high-dimensional data as a limitation for future work.
Do not treat an invented memory curve as evidence. The 2014 paper reports timing and accuracy experiments, but it does not publish a general RAM-versus-stream-size law.
The shape below reproduces the requested infographic. The values describe a hypothetical implementation rather than a result from the Mondrian Forest paper.
Actual memory depends on the number of trees, feature dimension, lifetime setting, pausing rule, class count and implementation.
Memory scales approximately with the number of independent trees.
Each node stores lower and upper extents across the feature dimensions.
Additional internal nodes store geometry, times and label statistics.
A radar chart compresses several qualitative judgements into one picture. It is useful for orientation, but it is not a scientific benchmark.
The profile gives high scores to online updating and computational speed. Memory efficiency and ease of implementation depend strongly on tree count, dimension, code quality and comparison method.
Predictive performance: close to batch forests on several datasets in the paper.
Update efficiency: strong when observations arrive sequentially.
Memory: node boxes, split times and class statistics grow with the tree.
Use these specific points when judging whether the method suits a practical streaming task.
New observations modify existing trees sequentially. The algorithm traverses short paths from the root instead of discarding and replacing the entire structure.
The final online tree follows the exact same mathematical probability distribution as a tree generated via batch construction on the identical dataset.
The hierarchical label mechanism effectively smooths sparse leaf estimates. This prevents the model from generating erratic probabilities on small samples.
The random, label-independent splitting mechanism struggles heavily with noise. The algorithm wastes calculations slicing dimensions that contain no actual predictive power.
The bounding boxes must permanently store the specific lower and upper coordinate values for every feature dimension. This mechanism creates a severe computational load in high-dimensional datasets.
The foundational algorithm simply aggregates knowledge. Incremental learning alone does not automatically detect drift or decide when outdated historical patterns should be forgotten.
Mondrian trees implement a fundamentally different random partition rule. You cannot achieve a Mondrian Forest by simply feeding streaming data into standard CART algorithms.
These trees function as parallel ensembles. They do not sequentially correct the specific residual errors of previous trees in the way that XGBoost or LightGBM operate.
Use these specific questions to verify your understanding while studying the source paper and codebase.
Generate a simple, two-dimensional numerical stream in Python. Plot the geometric partition rules after selected data updates. Following this, record the prequential accuracy and the sequential update time. Compare these recorded metrics against a standard batch Random Forest that is periodically retrained on the identical data stream.
The minimum mental model to retain before proceeding.
A Mondrian tree can be extended one point at a time so that its mathematical probability distribution after the update is strictly identical to a tree sampled in batch from all points seen so far. This explicit geometric property produces an efficient online forest with competitive accuracy across the authors' standard experiments.
Prepared as explanatory study notes. Diagrams are original simplifications; technical mathematical claims should always be checked directly against the cited source papers.
This page records the position described in the supplied project notes. It does not define the final dissertation.
P2 Statistical Machine Learning.
Dr Yordan Raykov.
The Mondrian Forest direction is preferred over the BART direction.
A fresh plan is useful for discussion with the new supervisor, but it is not formally assessed.
The exact question has not yet been agreed.
The balance between methodological study, software work and application remains unclear.
The dataset, comparison models and exact experiments have not yet been selected.
It remains unclear whether background and lighting changes are the central application or only an illustration of streaming data.
The 2014 article is a starting source.
Online tree-based statistical machine learning.
Still requires agreement with the supervisor.
The method has been chosen as the preferred direction. The final dissertation question has not yet been fixed.