algorithm.md

The Conditional Inference Algorithm

Overview

citrees implements Conditional Inference Trees (CIT), which differ from traditional CART-style trees by separating variable selection from split point selection using nodewise permutation screening.

The Problem with Traditional Trees

Traditional decision trees (CART, ID3, C4.5) use a greedy algorithm:

For each node:
    For each feature X_j:
        For each possible split point c:
            Compute weighted impurity reduction:
            Δ = Gini(parent) - (|L|/n)·Gini(left) - (|R|/n)·Gini(right)
    Select (feature, split) that maximizes Δ

The problem: This approach is biased toward features with more split points. A feature with 1000 unique values has 999 chances to find a "good" split by chance, while a binary feature has only 1 chance. This leads to:

1. Variable selection bias: High-cardinality features appear more important
2. Spurious splits: Trees can find splits on noise features by chance
3. Overfitting: The tree structure adapts to noise, not signal

The Conditional Inference Solution

Conditional Inference Trees address this by using permutation tests:

For each node:
    Step 1: VARIABLE SELECTION (screen association with target)
        For each feature X_j:
            H0: X_j is independent of Y
            Compute p-value using permutation test
        Select feature with lowest p-value
        IF p-value >= alpha: STOP (create leaf)

    Step 2: SPLIT POINT SELECTION (given the selected feature)
        For each possible split point c:
            Score weighted child impurity under label permutations
        Select split with lowest p-value

Why This Works

1. Reduced high-cardinality bias: Stage A selects variables via permutation-test p-values rather than by searching over many thresholds for the largest impurity improvement. This avoids the pure multiple-comparisons mechanism that favors features with many candidate split points (at a fixed node; see the scope note in docs/permutation-tests.md).

2. Test-based stopping: The tree stops growing when no feature passes the configured Stage A screening rule. This replaces a separate pruning step in many workflows.

3. Bounded interpretation: Feature importances are normalized impurity decreases. Stage A screening reduces one major source of split-selection bias, but the exposed importance scores should still be interpreted as model summaries rather than formal inference.

---

Implementation Details

Feature Selection (Selector)

citrees supports multiple association measures:

Selector	For	Measures
mc	Classification	Multiple Correlation (η) - how much variance in X is explained by class membership
mi	Classification	Mutual Information - non-linear dependence
rdc	Both	Randomized Dependence Coefficient - O(n log n) non-linear dependence
pc	Regression	Pearson Correlation
dc	Regression	Distance Correlation - captures non-linear relationships

Multiple Correlation (mc) - Default for classification:

# Implemented in _selector.py
η = sqrt(SSB / SST)  # Correlation ratio (monotone in η² = SSB/SST)

# SST = Σ(x_i - x̄)²  (total sum of squares)
# SSB = Σ n_k(x̄_k - x̄)²  (between-class sum of squares)

Permutation Testing

The p-value is computed via Monte Carlo permutation test:

# Pseudocode - see _selector.py for implementation
def _ptest(func, x, y, n_resamples, alpha, early_stopping):
    θ = |func(x, y)|  # Observed statistic

    θ_perm = []
    for i in range(n_resamples):
        y_shuffled = permute(y)
        θ_perm[i] = func(x, y_shuffled)  # Statistic under null

    # +1 corrected Monte Carlo permutation p-value (Phipson & Smyth, 2010)
    p_value = (1 + sum(|θ_perm| >= θ)) / (1 + n_resamples)
    return p_value

Key parameters:

• n_resamples_selector: Number of permutations ("auto", "minimum", "maximum", int, or None)
• alpha_selector: Significance threshold (default: 0.05)
• early_stopping_selector: "adaptive", "simple", or None (fixed-$B$)
• early_stopping_confidence_selector: Posterior-confidence threshold γ for "adaptive" (default: 0.95), minimum 0.95. For a fixed statistic the rule's null size is an exact finite computation (a Pólya-urn recursion over the checkpoints, paper/theory/adaptive_stopping_size.py): 0.0488 at γ = 0.95 and 0.0522 at γ = 0.80 for α = 0.05 and 999 permutations (the tree rejects when p < α), which is why 0.95 is the minimum allowed. The rule cannot stop before ceil(1 / alpha) permutations, so with n_resamples="minimum" it runs the full budget.

Bonferroni Correction

When testing multiple features at a fixed node in the exhaustive fixed-$B$ Stage A reference procedure, the alpha is adjusted:

# Nodewise Bonferroni correction for fixed-B Stage A under the complete null
alpha_adjusted = alpha / n_features

Under the nodewise complete permutation null, this controls the probability that Stage A accepts at least one feature at that fixed node. It is not a forest-level, full-tree, selected-split, or adaptive-stopping guarantee.

Feature Muting

Feature muting removes tested features that fail the node's Stage A gate from the candidate set inherited by descendants:

# alpha_node is alpha_selector after any nodewise Bonferroni adjustment.
alpha_node = alpha_selector / n_tested_features if adjust_alpha_selector else alpha_selector

if feature_muting and pval >= alpha_node:
    mute_feature(feature)  # Remove from descendant feature pools

This is a model-construction choice, not an upper-tail p >= 1 - alpha rule and not a pure speed-only heuristic. A muted feature failed to reject the node's Stage A test under the current node threshold; that threshold is Bonferroni adjusted when adjust_alpha_selector=True. Because the decision changes which features descendants can consider, feature muting can change the fitted tree and the resulting feature ranking.

Muting is subtree-local: muted features are removed only for descendants of the current node (siblings are isolated), which avoids traversal-order dependence:

Root available: {0,1,2}
├─ Left child sees {0,1,2} → may drop feature 1 in its subtree → descendants see {0,2}
└─ Right child sees {0,1,2} (unaffected by left)

---

Honest Estimation

citrees supports honest estimation, a sample-splitting technique for reducing adaptive bias in leaf estimation (conditional unbiasedness under sample splitting assumptions). For full details, see the dedicated documentation: Honest Estimation.

---

Summary: What Each Feature Adds

Feature	Scientific Contribution	When to Use
Permutation tests	Reduced selection bias, test-based stopping	Core algorithm
Bonferroni correction	Controls nodewise fixed-$B$ Stage A rejection under the complete null	Conservative tree growth
Feature muting	Removes Stage A non-rejecting tested features from descendant pools	Large feature spaces
Honesty	Reduced adaptive bias in leaf estimation	Estimation-focused workflows

References

1. Hothorn, T., Hornik, K., & Zeileis, A. (2006). Unbiased Recursive Partitioning: A Conditional Inference Framework. JCGS, 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. Wager, S., & Athey, S. (2018). Estimation and Inference of Heterogeneous Treatment Effects using Random Forests. JASA, 113(523), 1228-1242.

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