Does the embedding need class labels?

The random-tree transformation is unsupervised; a later classifier still needs labels.

Does it reduce dimensionality?

Usually it produces a high-dimensional sparse representation. A separate reduction step can be applied afterward.

Why can a linear model on these features behave nonlinearly in the original inputs?

Each binary feature indicates membership in a region defined by tree splits, so combining those indicators creates a piecewise response over the original space.

AI Glossary / AI and machine learning / Intermediate

Totally Random Trees Embedding

Definition

Totally random trees embedding is an unsupervised method that represents an input by the leaves it reaches in a collection of randomly constructed trees. Each leaf becomes a binary feature. The resulting representation is usually high dimensional and sparse, providing nonlinear features that another learning algorithm can use for classification, regression or similarity analysis.

What it means

An embedding is a representation in a new feature space. Here it consists of region-membership indicators rather than dense semantic coordinates from a language model. Each tree divides the input space into regions without using a supervised target to choose useful class boundaries. A point receives a 1 for the leaf it reaches in each tree and zeros for the other leaves. Points sharing many leaves have similar codes under that particular collection of partitions. Whether that similarity is useful depends on the input features and the downstream task.

How it works

Build multiple trees with random splitting choices, subject to settings such as maximum depth and minimum leaf size. Record the leaf reached by every training point in every tree, then encode each tree's leaf identifier separately using one-hot encoding. Concatenate these blocks to form the new feature vector. For prediction, route new points through the already-fitted trees and use the same column mapping. With T trees, an ordinary code has exactly T nonzero entries, even though the number of possible columns can be much larger. Fitting a supervised predictor on these codes is a separate step, and the whole transformation should be included within the training and validation workflow.

Three practical examples

A tabular classifier uses random-tree codes before a linear classification model, allowing the final predictor to combine nonlinear regions of the original features.
An analyst compares records by how often they land in the same leaves, testing whether the resulting neighborhood structure matches a useful notion of similarity.
A visualization experiment applies a separate dimensionality-reduction method to the sparse codes. The tree embedding itself expands the representation; the later reduction produces the two-dimensional display.

Think of it this way

Imagine overlaying several different street maps, each dividing the same city into districts. A location is described by its district on every map. Nearby locations may share many districts even if one map places a boundary between them. The analogy captures repeated partitions, but mathematical splits need not correspond to meaningful geographic districts, and the resulting code does not automatically express real-world similarity.

Worked example

Suppose two fitted trees have three and two leaves respectively. Their concatenated encoding therefore has five columns. Record A reaches leaf 1 in the first tree and leaf 2 in the second, giving (1, 0, 0, 0, 1). Record B reaches leaf 1 and leaf 1, giving (1, 0, 0, 1, 0). Record C reaches leaf 2 and leaf 2, giving (0, 1, 0, 0, 1). Each vector has exactly two ones. The dot product of A and B is 1, as is that of A and C, because each pair shares one leaf. Dividing by the two trees gives a shared-leaf fraction of 0.5 for both pairs. B and C share no leaves, giving zero. This is a similarity defined by the fitted partitions, not a probability that two records belong to the same class. The leaf counts are illustrative, not a required software configuration.

Illustrative case study

In a fictional project, Pine Archive tests these features for sorting digitized records using numerical document measurements. It compares a linear model on the original measurements with a linear model on random-tree codes. The team fits each transformation only on the relevant training split and checks results across several random seeds. Some deeper configurations consume more memory without a clear validation benefit. The team records that tradeoff rather than assuming that a larger embedding must be more informative. No real performance result is implied.

Common misconceptions and mistakes

Do not confuse this method with a supervised random forest whose splits are selected using target-related criteria. Do not assume that random means the encoding changes on every prediction: a saved fitted transform maps the same input consistently. More columns do not necessarily mean more useful information. A leaf identifier is categorical, so treating leaf numbers as ordinary ordered numerical values changes the representation. Also avoid interpreting a shared leaf as proof of semantic equivalence; its meaning is determined by the chosen feature space and random boundaries.

Business use

Consider the method as a nonlinear feature baseline when a sparse downstream model is attractive. Measure total transformation time, model size and prediction quality rather than comparing only the final classifier. Keep the tree ensemble and encoder together when saving the system. Record random seeds and relevant library settings for reproducibility. If features drift or new operating regions appear, inspect how records are routed through existing leaves. Retraining the trees changes feature columns, so the downstream model must be coordinated with the new representation.

Check your understanding

A fitted embedding contains 40 trees and 1,000 possible leaf columns. How many ones does an ordinary encoded sample contain?

Answer: 40, one for the leaf reached in each tree. It does not contain 1,000 ones, and the number of active entries is different from the representation's dimensionality.

Related terms

One-hot encoding
Decision tree
Random forest
Sparse representation
feature transformation
kernel approximation

Learn next

draw two random partitions of a small two-dimensional dataset and manually build their leaf codes. Compare original distances with shared-leaf similarity, then train a simple linear predictor on the codes using a properly separated validation set.

Validation set

Sources

Sources: scikit-learn, Totally Random Trees Embedding, https://scikit-learn.org/stable/modules/ensemble.html#totally-random-trees-embedding ; RandomTreesEmbedding API, https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomTreesEmbedding.html . The guide explains the unsupervised leaf encoding and its sparsity; all records and calculations above are illustrative.

Previous: Total Variation Distance (Tvd) Next: Tournament