citrees

Conditional Inference Trees and Forests for Python

Paper: This repository contains the citrees package, benchmark code, and results for Milletich, Downes, Goley, and Hirst (2026), Conditional Inference Trees and Forests for Feature Selection (PDF).

citrees implements conditional-inference-style decision trees and forests using permutation-based screening before threshold selection. Unlike traditional CART-style trees that greedily optimize split criteria, citrees separates variable selection from split point selection to reduce the classic high-cardinality split-selection bias mechanism. Fixed-B p-value calibration is nodewise; adaptive tree and forest rankings remain empirical model outputs.

Note: citrees is inspired by the conditional inference framework (Hothorn et al., 2006) but is not a direct port of R's partykit::ctree. We implement the core principles—permutation-based variable selection and statistical stopping rules—while adding our own extensions like RDC selectors and feature muting. In particular, Stage A screening is designed to mitigate the classic high-cardinality selection bias mechanism of greedy impurity optimization (with the usual fixed-node/root scope caveats for adaptive trees).

Why citrees?

Traditional decision trees (CART, ID3, C4.5) suffer from variable selection bias:

Problem	CART Behavior	citrees Solution
Selection bias	Favors high-cardinality features	Fixed-node Stage A permutation screening mitigates this multiplicity mechanism
Spurious splits	Finds "good" splits by chance	Stage A must accept a feature before threshold search; Stage B is an algorithmic split score
Overfitting	Requires pruning/cross-validation	Principled stopping via hypothesis tests
Feature importance	Biased toward frequently-split features	Still uses impurity-decrease importance; Stage A mitigates a key root-level bias mechanism

Installation

# From source
git clone https://github.com/rmill040/citrees.git
cd citrees
pip install -e .

# With uv (recommended)
uv sync

The installable citrees package has a small runtime dependency set. The benchmark and manuscript pipeline under paper/ uses additional optional dependencies and is installed separately with the paper extra or dependency group.

Experiment CLI (citrees-exp)

This repository includes a Typer-based CLI for running the paper experiments, managing the API-server/worker experiment pipeline, managing AWS infrastructure, and monitoring progress.

# Install experiment CLI deps
uv sync --group paper
# or
pip install -e '.[paper]'

citrees-exp --help

Quick Start

from citrees import (
    ConditionalInferenceTreeClassifier,
    ConditionalInferenceTreeRegressor,
    ConditionalInferenceForestClassifier,
    ConditionalInferenceForestRegressor,
    MaxValuesMethod,
)

# Classification
clf = ConditionalInferenceTreeClassifier(
    selector="mc",           # Multiple correlation for feature selection
    splitter="gini",         # Gini impurity for split quality
    alpha_selector=0.05,     # Screening threshold for feature selection
    alpha_splitter=0.05,     # Screening threshold for split selection
)
clf.fit(X_train, y_train)
predictions = clf.predict(X_test)
probabilities = clf.predict_proba(X_test)

# Regression
reg = ConditionalInferenceTreeRegressor(
    selector="pc",           # Pearson correlation
    splitter="mse",          # Mean squared error
)
reg.fit(X_train, y_train)

# Forest ensemble (parallel training)
forest = ConditionalInferenceForestClassifier(
    n_estimators=100,
    max_features=MaxValuesMethod.SQRT,  # Random feature subset per split
    n_jobs=-1,                          # Use all cores
)
forest.fit(X_train, y_train)
forest_predictions = forest.predict(X_test)
forest_probabilities = forest.predict_proba(X_test)

# Feature importance (impurity decrease; subject to known caveats)
importances = forest.feature_importances_

Key Features

Statistical Feature Selection

At each node, features are tested for association with the target using permutation tests. A feature must pass the configured Stage A screening rule before citrees searches over thresholds for that feature. With fixed-$B$ permutation tests, the root-node p-values have the usual exchangeability-based interpretation; with the default adaptive stopping, the values are best read as algorithmic screening and stopping scores.

Multiple Selector Methods

Selector	Task	Description	Complexity
mc	Classification	Multiple correlation (ANOVA-based)	O(n)
mi	Classification	Mutual information	O(n log n)
rdc	Both	Randomized Dependence Coefficient	O(n log n)
pc	Regression	Pearson correlation	O(n)
dc	Regression	Distance correlation	O(n²)

Advanced Capabilities

• Bonferroni Correction: Controls nodewise fixed-$B$ Stage A rejection probability under the complete permutation null when testing multiple features
• Feature Muting: Removes Stage A non-rejecting tested features from descendant feature pools
• Honest Estimation: Optional sample splitting to reduce adaptive bias in leaf estimation (Wager & Athey, 2018)

Algorithm Overview

The conditional inference algorithm (Hothorn et al., 2006) proceeds as follows:

Algorithm: Conditional Inference Tree
Input: Data (X, y), screening thresholds α_select, α_split

function BuildTree(X, y, depth):
    # Step 1: Test global null hypothesis
    for each feature j in {1, ..., p}:
        H₀: X_j ⊥ Y (feature j independent of target)
        p_j ← PermutationTest(X_j, y)

    # Apply Bonferroni correction
    α_adjusted ← α_select / p

    # Select feature with strongest association
    j* ← argmin(p_j)

    if p_j* ≥ α_adjusted:
        return LeafNode(y)  # No feature passes Stage A screening

    # Step 2: Find an algorithmic split point for the selected feature
    for each threshold c in X_j*:
        H₀: Fixed-feature threshold score under label exchangeability
        p_c ← PermutationTest(X_j*, y, c)

    c* ← argmin(p_c)

    if p_c* ≥ α_split:
        return LeafNode(y)  # No threshold passes the split rule

    # Step 3: Recurse
    left ← {i : X_ij* ≤ c*}
    right ← {i : X_ij* > c*}

    return InternalNode(
        feature=j*, threshold=c*,
        left=BuildTree(X[left], y[left], depth+1),
        right=BuildTree(X[right], y[right], depth+1)
    )

Documentation

Document	Description
Algorithm Details	Deep dive into conditional inference
Selectors	Feature selection methods (mc, mi, rdc, pc, dc)
Splitters	Split criteria (gini, entropy, mse, mae)
Permutation Tests	Nodewise permutation tests and scope caveats
Honest Estimation	Sample splitting for leaf estimation
Basic Usage Example	Runnable classifier, regressor, and forest demo

Parameters Reference

Core Parameters

Parameter	Type	Default	Description
selector	str or list	'mc'/'pc'	Feature selection method
splitter	str	'gini'/'mse'	Split criterion
alpha_selector	float	0.05	P-value threshold for feature selection
alpha_splitter	float	0.05	P-value threshold for split selection
n_resamples_selector	NResamples/int/None	NResamples.AUTO	Permutation resamples for selector (None disables permutation tests)
n_resamples_splitter	NResamples/int/None	NResamples.AUTO	Permutation resamples for splitter (None disables permutation tests)

Optimization Parameters

Parameter	Type	Default	Description
adjust_alpha_selector	bool	True	Bonferroni correction for features
adjust_alpha_splitter	bool	True	Bonferroni correction for thresholds
early_stopping_selector	EarlyStopping/None	EarlyStopping.ADAPTIVE	Sequential stopping rule for selector permutation tests
early_stopping_splitter	EarlyStopping/None	EarlyStopping.ADAPTIVE	Sequential stopping rule for splitter permutation tests
early_stopping_confidence_selector	float	0.95	Posterior-confidence threshold γ for adaptive stopping (selectors)
early_stopping_confidence_splitter	float	0.95	Posterior-confidence threshold γ for adaptive stopping (splitters)
feature_muting	bool	True	Remove Stage A non-rejecting tested features from descendant pools
feature_scanning	bool	True	Test promising features first

Tree Structure Parameters

Parameter	Type	Default	Description
max_depth	int	None	Maximum tree depth
min_samples_split	int	2	Minimum samples to split
min_samples_leaf	int	1	Minimum samples in leaf
min_impurity_decrease	float	0.0	Minimum impurity decrease to split
max_features	MaxValuesMethod/int/float/None	None	Features per split
threshold_method	ThresholdMethod	ThresholdMethod.EXACT	How to generate split candidates
max_thresholds	MaxValuesMethod/int/float/None	None	Maximum thresholds per feature
threshold_scanning	bool	True	Test promising thresholds first

Honest Estimation

Parameter	Type	Default	Description
honesty	bool	False	Enable sample splitting
honesty_fraction	float	0.5	Fraction for estimation sample (rest for splitting)

Forest Parameters

Parameter	Type	Default	Description
n_estimators	int	100	Number of trees
max_samples	int/float/None	None	Bootstrap sample cap (count or fraction)
bootstrap	bool	True	Whether to use bootstrap sampling
sampling_method	SamplingMethod/None	SamplingMethod.STRATIFIED	How to sample classes during bootstrap
n_jobs	int/None	None	Parallel jobs (-1 for all cores)
oob_score	bool	False	Compute out-of-bag score (requires bootstrap)

Notes:

• sampling_method applies to classification forests only and requires bootstrap=True.
• sampling_method options: stratified, undersample, oversample.
• max_samples is only used when bootstrap=True.
• bootstrap=False disables bootstrapping (and thus OOB).
• Invalid combinations (e.g., bootstrap=False with sampling_method set) raise a validation error.
• Forest classes default max_features=MaxValuesMethod.SQRT (trees default None).
• OOB scores are computed only for samples that receive at least one OOB prediction.

Miscellaneous Parameters

Parameter	Type	Default	Description
random_state	int/None	None	Random seed for permutation tests, sampling, and bootstrap
verbose	int	1	Verbosity level (0=quiet; higher prints more progress)
check_for_unused_parameters	bool	False	Warn when parameters are ineffective due to other settings

Use Cases

citrees is intended for scenarios requiring:

• Feature screening with reduced split-selection bias for interpretability
• High-dimensional data where many features are noise
• Permutation-based nodewise screening for scientific applications
• Sample-split leaf estimation with honest estimation, without standalone confidence-interval or coverage guarantees

Development

# Install with dev dependencies
uv sync

# Run tests
uv run pytest tests/unit tests/integration -v

# Run linters
uv run pre-commit run --all-files

See CONTRIBUTING.md for contribution guidelines and SUPPORT.md for issue-reporting and support expectations.

Releases

Release notes are maintained in CHANGELOG.md.

Citation

@software{citrees,
  title = {citrees: Conditional Inference Trees and Forests for Python},
  author = {Milletich, Robert and Downes, Justin and Goley, Steve and Hirst, Newel},
  year = {2026},
  url = {https://github.com/rmill040/citrees}
}

References

Core Papers

1. Hothorn, T., Hornik, K., & Zeileis, A. (2006). Unbiased Recursive Partitioning: A Conditional Inference Framework. Journal of Computational and Graphical Statistics, 15(3), 651-674.

2. Strobl, C., Boulesteix, A. L., Zeileis, A., & Hothorn, T. (2007). Bias in Random Forest Variable Importance Measures. BMC Bioinformatics, 8(1), 25.

3. Strobl, C., Boulesteix, A. L., Kneib, T., Augustin, T., & Zeileis, A. (2008). Conditional Variable Importance for Random Forests. BMC Bioinformatics, 9(1), 307.

Additional Methods

4. Wager, S., & Athey, S. (2018). Estimation and Inference of Heterogeneous Treatment Effects using Random Forests. JASA, 113(523), 1228-1242.

5. Lopez-Paz, D., Hennig, P., & Schölkopf, B. (2013). The Randomized Dependence Coefficient. NeurIPS.

6. Székely, G. J., Rizzo, M. L., & Bakirov, N. K. (2007). Measuring and Testing Dependence by Correlation of Distances. Annals of Statistics, 35(6), 2769-2794.

License

MIT License - see LICENSE for details.