# Random Tree Feature Layer

- ID: 1559
- Canonical URL: https://synthcore.org/idea/1559/random-tree-feature-layer
- API JSON: https://synthcore.org/api/idea/1559.json
- API Markdown: https://synthcore.org/api/idea/1559.md
- Verification status: unverified
- Source: [arXiv:2607.28844](https://arxiv.org/abs/2607.28844)
- Category: architecture
- Solves: accuracy, sample-efficiency, scalability
- ML areas: mlp, embedding, architecture, training
- Math tags: probability, functional-analysis, statistics
- Ratings: usefulness 6/10; difficulty 4/10; novelty 7/10

## Idea description

Generate many random symmetric decision trees and encode each input by the one-hot indicator of its reached leaf. Use the resulting fixed random feature vector as an additional input to an MLP, or train only a ridge/linear prediction head on it. The tree ensemble's Gaussian-process-limit interpretation predicts that increasing the number of independent trees should approximate a stable kernel while avoiding MCMC and difficult optimization over discrete split structures.

## Mathematical statement

Equation (1) represents a tree function as h(x)=sum over l in L of mu_l psi_l(x), where x in [0,1]^p is the input, L is the set of leaves, mu_l in R is the scalar parameter attached to leaf l, and psi_l(x) is the indicator that x lies in leaf l. For a symmetric depth-D tree, L={-1,1}^D; V_k in [p] is the feature selected at split k, S_k in [0,1] is its cutpoint, and l_k identifies the left or right branch. The exact leaf feature is psi_l(x;D,V,S)=product from k=1 to D of 1{l_k x_{V_k} <_{l_k} l_k S_k}, where <_1 means < and <_{-1} means <=, ensuring every x belongs to exactly one leaf. If leaf coefficients have independent mean zero variance sigma_mu^2, a single random tree has covariance proportional to the probability that two inputs reach the same leaf. For T independent trees, the empirical kernel is K_T^(T)(x,x')=(sigma_mu^2/T) sum_t sum_l psi_{t,l}(x)psi_{t,l}(x'). The neural adaptation uses z(x)=(1/sqrt(T)) concatenation over trees of all leaf indicators, so a learned linear head has predictor f(x)=w^T z(x), while an MLP can consume [x,z(x)] to combine tree interactions with smooth learned representations.

## Key formulas

- $$h(\mathbf{x})=\sum_{\mathbf{l}\in\mathcal{L}}\mu_{\mathbf{l}}\psi_{\mathbf{l}}(\mathbf{x}).$$
- $$\psi_{\mathbf{l}}(\mathbf{x};D,\mathbf{V},\mathbf{S}):=\prod_{k=1}^{D}\mathbf{1}\{l_{k}x_{V_{k}}<_{l_{k}}l_{k}S_{k}\},\qquad \mathcal{L}=\{-1,1\}^{D}.$$
- $$K_T^{(T)}(\mathbf{x},\mathbf{x}')=\frac{\sigma_\mu^2}{T}\sum_{t=1}^{T}\sum_{\mathbf{l}\in\mathcal{L}_t}\psi_{t,\mathbf{l}}(\mathbf{x})\psi_{t,\mathbf{l}}(\mathbf{x}').$$
- $$\hat{\theta}=\arg\min_{\theta}\;\frac{1}{n}\sum_{i=1}^{n}\ell\!\left(y_i,f_\theta([\mathbf{x}_i,z(\mathbf{x}_i)])\right)+\lambda\|\theta\|_2^2,\qquad z(\mathbf{x})=\frac{1}{\sqrt{T}}\bigoplus_{t=1}^{T}\big[\psi_{t,\mathbf{l}}(\mathbf{x})\big]_{\mathbf{l}\in\mathcal{L}_t}.$$

## Implementation notes

1. Integration point: add a non-learned RandomTreeFeatures module immediately before the prediction MLP. Normalize every continuous feature to [0,1]; represent categorical variables by integer IDs or one-hot vectors. The module should output all leaf indicators for a ridge baseline and optionally a compressed vector for an MLP. 2. Pseudocode: sample T trees; for each tree t sample depth D_t, feature indices V[t,k], and cutpoints S[t,k]. For each minibatch x, evaluate every split b[t,k]=(x[:,V[t,k]]>S[t,k]), convert the D branch bits into a leaf index, and emit a one-hot vector psi_t with one at that leaf. Concatenate the vectors over trees and multiply by 1/sqrt(T); feed concat(x,z) to a two- or three-layer MLP. Alternatively solve ridge regression directly on the encoded training matrix. 3. Computed from the mathematics: partition indicators, normalization, and empirical kernel K_T^(T). Estimated empirically: depth, feature and cutpoint distributions, T, and ridge coefficient lambda. Compare kernels at T=128, 512, and 2048 against a large-T reference. For memory control, retain only reached-leaf IDs, use sparse tensors, or hash leaf indices into a fixed-dimensional embedding. 4. First experiment: use California Housing or UCI Adult with fixed train, validation, and test splits. Compare a raw two-layer MLP, LightGBM/XGBoost, and the augmented MLP with T=256 random trees at depths 4, 6, and 8. Measure test RMSE or accuracy, wall-clock training time, feature-construction time, parameter count, and performance at reduced training-set sizes. A positive result is lower test error than the raw MLP at equal optimization steps, particularly in the 1k-10k example regime, with tree-feature construction costing less than one boosting pass. Also test whether accuracy and kernel estimates stabilize smoothly as T increases.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.