[ML] Missing values break fixed candidate splits for low-cardinality features, silently degrading models #3241

Summary

For a feature with few distinct values and a few missing values, CBoostedTreeImpl::initializeFixedCandidateSplits puts the missing values (NaN) into the feature's candidate splits. The list ends up unsorted and contains NaN. Trees trained on it have splits where one side gets no training rows. The model can end up no better than chance, and the job still reports success.

In the reproduction below (six integer features, 10 distinct values each), 2% missing values drop test accuracy from about 0.85 to about 0.49. Up to 93% of splits have a child with number_samples: 0. With 0% or 20% missing values, the data is unaffected. Default hyperparameters are affected too.

Reproduction

repro.py uses only the Python standard library. It needs a node with ML enabled. For each missing-value rate it trains a classification job, then prints the share of splits with a zero-sample child and the test accuracy.

import json
import random
import sys
import time
import urllib.error
import urllib.request

ES = "http://localhost:9200"
# Pinned hyperparameters (deep trees) so runs are comparable; pass --default-hyperparameters to let DFA tune them.
HYPERPARAMETERS = {
    "alpha": 0.016, "downsample_factor": 0.27, "eta": 0.06, "eta_growth_rate_per_tree": 1.03,
    "feature_bag_fraction": 0.8, "gamma": 0.019, "lambda": 0.11, "max_trees": 63,
    "soft_tree_depth_limit": 11.0, "soft_tree_depth_tolerance": 0.15,
}


def call(method, path, body=None):
    data = None if body is None else (body if isinstance(body, str) else json.dumps(body)).encode()
    ctype = "application/x-ndjson" if isinstance(body, str) else "application/json"
    req = urllib.request.Request(ES + path, method=method, data=data, headers={"Content-Type": ctype})
    try:
        return json.load(urllib.request.urlopen(req))
    except urllib.error.HTTPError as e:
        return json.load(e)


def rows(n, missing, rnd):
    out = []
    for _ in range(n):
        x = [rnd.randint(0, 9) for _ in range(6)]
        label = "a" if x[0] + x[1] - x[2] + rnd.gauss(0, 2) > 4.5 else "b"
        doc = {f"x{i}": v for i, v in enumerate(x) if rnd.random() >= missing}
        doc["label"] = label
        out.append(doc)
    return out


def run(missing, seed, tuned):
    name = f"repro-missing{int(missing * 100)}-s{seed}{'-default' if tuned else ''}"
    source, dest = name, f"{name}-results"
    call("POST", f"/_ml/data_frame/analytics/{name}/_stop?force=true")
    call("DELETE", f"/_ml/data_frame/analytics/{name}")
    call("DELETE", f"/{source},{dest}?ignore_unavailable=true")
    for old in call("GET", f"/_ml/trained_models?tags={name}").get("trained_model_configs", []):
        call("DELETE", f"/_ml/trained_models/{old['model_id']}?force=true")
    mapping = {**{f"x{i}": {"type": "integer"} for i in range(6)}, "label": {"type": "keyword"}}
    call("PUT", f"/{source}", {"mappings": {"properties": mapping}})
    bulk = "".join('{"index":{}}\n' + json.dumps(d) + "\n" for d in rows(1000, missing, random.Random(seed)))
    call("POST", f"/{source}/_bulk?refresh=true", bulk)
    classification = {"dependent_variable": "label", "training_percent": 80, "randomize_seed": seed}
    if not tuned:
        classification.update(HYPERPARAMETERS)
    call("PUT", f"/_ml/data_frame/analytics/{name}", {
        "source": {"index": source}, "dest": {"index": dest}, "analysis": {"classification": classification}})
    call("POST", f"/_ml/data_frame/analytics/{name}/_start")
    while (state := call("GET", f"/_ml/data_frame/analytics/{name}/_stats")["data_frame_analytics"][0]["state"]) \
            not in ("stopped", "failed"):
        time.sleep(2)

    models = call("GET", f"/_ml/trained_models?tags={name}&include=definition")["trained_model_configs"]
    assert len(models) == 1, f"expected exactly one model tagged {name}, found {len(models)}"
    trees = models[0]["definition"]["trained_model"]["ensemble"]["trained_models"]
    splits = zero = 0
    for t in trees:
        nodes = t["tree"]["tree_structure"]
        for n in nodes:
            if "split_feature" in n:
                splits += 1
                zero += 0 in (nodes[n["left_child"]]["number_samples"], nodes[n["right_child"]]["number_samples"])
    accuracy = call("POST", "/_ml/data_frame/_evaluate", {
        "index": dest, "query": {"term": {"ml.is_training": False}},
        "evaluation": {"classification": {"actual_field": "label", "predicted_field": "ml.label_prediction",
                                          "metrics": {"accuracy": {}}}}})["classification"]["accuracy"]["overall_accuracy"]
    print(f"missing={missing:4.0%} seed={seed} state={state:8} trees={len(trees):3} "
          f"zero-sample splits={zero:4}/{splits:<4} ({100.0 * zero / max(splits, 1):5.1f}%) test accuracy={accuracy:.3f}",
          flush=True)


if __name__ == "__main__":
    tuned = "--default-hyperparameters" in sys.argv
    for missing in (0.0, 0.02, 0.2):
        for seed in (1, 2, 3):
            run(missing, seed, tuned)

Each cell lists seeds 1, 2 and 3. Every job ended in state stopped.

The classes are roughly balanced, so 0.5 is chance. With 2% missing values, the pinned runs also stop adding trees early (13, 43 and 7 trees, against 64 in the other runs).

Cause

Links point to ml-cpp 7fa9cff, the native build in the snapshot above. CBoostedTreeImpl.cc hasn't changed since 2022-09.

1. Missing values are NaN. The missing string "\0" is stored as quiet_NaN (CDataFrame.cc#L750), and isMissing means not finite (CDataFrame.h#L554-L561). Categorical encodings pass NaN through unchanged (CDataFrameCategoryEncoder.cc#L671-L677).

2. Unique values are collected without skipping NaN (CBoostedTreeImpl.cc#L1519-L1524):

   for (std::size_t i = 0; i < features.size(); ++i) {
       if (state[i].size() <= m_NumberSplitsPerFeature + 1) {
           state[i].insert(m_Encoder->encode(*row)[features[i]]);
       }
   }

   state[i] is a boost::unordered_set<double> (L1488). Because NaN != NaN, every missing row adds a new entry.

3. Features with at most m_NumberSplitsPerFeature (75) entries take the fixed-candidate path (L1539-L1551). This path sorts the values and uses the midpoints between neighbors as splits. NaN breaks std::sort, and a midpoint next to a NaN is NaN, so the list ends up unsorted and contains NaN.

4. Every reader of the list assumes it is sorted.

   • Rows cache their split index with CSearchTree::upperBound (L1675-L1690).
   • Nodes recover their split index with std::lower_bound (CBoostedTree.cc#L104-L113) and route rows by comparing the two (CBoostedTree.cc#L87-L93).

   With an unsorted list, the recovered index can differ from the bucket where the split was evaluated (CBoostedTreeLeafNodeStatisticsScratch.cc#L343-L407). The split statistics then show rows on both sides and pass the empty-side check (L364-L376), but every row actually goes to one side.

Evidence:

• Step 3 is confirmed on a local build. On the unfixed code, a feature with 10 distinct values and 10 missing rows gets 19 candidate splits instead of 9. A regression model trained on such features has 3534 zero-sample nodes.
• Step 4 comes from reading the code, and the leaf values agree with it. In two affected models, zero-sample leaves have a value of exactly 0 in 32 of 32 and 570 of 601 cases, against 3 of 736 and 41 of 1215 for other leaves. Leaf values are computed with the same training-time routing (CBoostedTreeImpl.cc#L2147-L2175), so no training row reached these leaves even during training.
• The threshold of 75 explains why 2% breaks but 20% doesn't. At 2%, 10 values plus about 16 NaN entries stay under 75. At 20%, about 160 NaN entries push the feature onto the quantile path, which handles missing values ([ML] Avoid log spam when we only have missing values for a feature computing candidate splits for regression and classification #1500).

Also hit via n_gram_encoding

In my project, I first saw this as NaN feature importance in a DFA classification job on domain names, using n_gram_encoding with n_grams: [1, 2] and length: 12. Positional n-grams are missing for strings shorter than the window. That gives the same pattern: about 25 distinct values and 1–38 missing rows per feature.

• Over three random seeds, 1.2%, 13.3% and 34.3% of splits had a zero-sample child. With the window shrunk to the shortest string, so that no n-gram feature is ever missing, all three seeds gave 0%.
• downsample_factor: 1 and feature_bag_fraction: 1 both made it worse, so it isn't a sampling effect. Shallower trees reduced it but didn't remove it.
• 97–100% of the first zero-sample splits on each path were on features with missing values. All the others were below such a split.

Fix

#3240 makes two changes in initializeFixedCandidateSplits:

• Skip missing values when collecting unique values. The check sits inside the existing cap test, so encoding still stops once a feature exceeds the cap. Missing rows still get their own split index (missingSplit) when the splits cache is refreshed, so how they are assigned doesn't change.
• Take the fixed-candidate path only when a feature has at least two distinct values. Skipping missing values without this guard adds a crash. If every training value of a selected feature is missing, reserve(values.size() - 1) throws std::length_error. That can happen when the encoding was computed on a different data set.

Results on a local build:

• 2% missing: 0 zero-sample splits. Test accuracy is 0.825–0.866 with pinned hyperparameters and 0.845–0.876 with default hyperparameters, against 0.49–0.60 before.
• 0% missing: bit-identical to before.
• 20% missing: these features now take the fixed-candidate path, as low-cardinality features are meant to. Over 10 seeds, mean accuracy is 0.790, against 0.792 on the old quantile path (standard error about 0.006 each), so there's no regression.
• n_gram_encoding: 0 zero-sample splits for all three seeds.

Related: native TreeSHAP on zero-sample nodes

At zero-sample nodes, native SHAP divides 0 by 0 in two places:

• the child fractions in shapRecursive (CTreeShapFeatureImportance.cc#L252-L257);
• computeInternalNodeValues (L163-L175).

On the n_gram_encoding model above, every training row got a single feature with importance 0. The exported feature_importance_baseline was 0.0 for both classes, while the sample-weighted mean of leaf values summed over the trees is 0.2895.

The Java port in Elasticsearch returns NaN instead, which fails the job's inference phase. elastic/elasticsearch#161539 fixes that. It uses machine epsilon in ShapPath to match the native code, and splits evenly at zero-sample nodes below the root.

The training fix stops new models from getting these nodes, but older models still have them. Incremental training can also create them, because it recounts the samples of existing trees on new data. The TreeInferenceModel Javadoc asks for such changes to land natively first, so #3240 also adds the native guard:

• shapRecursive splits child fractions evenly at zero-sample nodes below the root.
• computeInternalNodeValues gives such nodes the unweighted mean of their children.

With the guard, the exported baseline is 0.2895. Baseline plus the sum of importances equals the logit of the native prediction within 4.7e-7.

On these pre-fix models, native and Java predictions also differ on some rows, so their SHAP values differ there too. For the seed-1 n_gram_encoding model, that is 272 of 800 training rows, by up to 0.054 in probability. Models trained with the fix agree within 1e-8 in prediction and 3e-15 in importance.

Environment

• Elasticsearch main (9.6.0-SNAPSHOT), run with ./gradlew run -Drun.license_type=trial.
• Native code 9.6.0-SNAPSHOT, build hash 7fa9cff98eb951.
• macOS, arm64.