✔️ Linting Passed

All linting checks passed. Your pull request is in excellent shape! ☀️

_{Generated for commit: a23e8aa. Link to the linter CI: here}

Could you use the following test for that is currently failing:

@pytest.mark.parametrize(
    "make_data, Tree, tolerance",
    [
        (datasets.make_regression, DecisionTreeRegressor, 0.08),
        (datasets.make_classification, DecisionTreeClassifier, 0.03),
    ],
)
@pytest.mark.parametrize("sample_weight_train", [None, "ones"])
def test_missing_values_is_resilience(
    make_data, Tree, sample_weight_train, global_random_seed, tolerance
):
    """Check that trees can deal with missing values and have decent performance."""
    n_samples, n_features = 5_000, 10
    X, y = make_data(
        n_samples=n_samples, n_features=n_features, random_state=global_random_seed
    )

    X_missing = X.copy()
    rng = np.random.RandomState(global_random_seed)
    X_missing[rng.choice([False, True], size=X.shape, p=[0.9, 0.1])] = np.nan
    X_missing_train, X_missing_test, y_train, y_test = train_test_split(
        X_missing, y, random_state=global_random_seed
    )
    if sample_weight_train == "ones":
        sample_weight = np.ones(X_missing_train.shape[0])
    else:
        sample_weight = None

    native_tree = Tree(max_depth=10, random_state=global_random_seed)
    native_tree.fit(X_missing_train, y_train, sample_weight=sample_weight)
    score_native_tree = native_tree.score(X_missing_test, y_test)

    tree_with_imputer = make_pipeline(
        SimpleImputer(), Tree(max_depth=10, random_state=global_random_seed)
    )
    tree_with_imputer.fit(X_missing_train, y_train)
    score_tree_with_imputer = tree_with_imputer.score(X_missing_test, y_test)

    assert abs(score_tree_with_imputer - score_native_tree) < tolerance

Instead to check between missing/no-missing performance, I compare between imputation vs. native support. I check with the global random seed that the test is working in the tolerance given.

Instead to check between missing/no-missing performance, I compare between imputation vs. native support. I check with the global random seed that the test is working in the tolerance given.

Thanks! This is a much better test. I think it will also help alleviate the issue when adding ExtraTree* to this unit-test.

Thanks! This is a much better test. I think it will also help alleviate the issue when adding ExtraTree* to this unit-test.

So running the tests with all the random seeds locally fails in quite a number of random seeds (roughly 50% of the seeds?):

SKLEARN_TESTS_GLOBAL_RANDOM_SEED='all' pytest sklearn/tree/tests/test_tree.py -k is_resilience 

@glemaitre is on it to try to create a better dataset for this test

I think if that is the case, we need to prolly lower the NaN missing completely at random rate.

I think if that is the case, we need to prolly lower the NaN missing completely at random rate.

Actually, I think that the dataset created for regression is not really good (we cannot nicely predict on it). Maybe we should craft an easier dataset and split the tests into two test (or create a private function to generate the dataset). I'll have a look to check the discriminating performance of the tree to have less variance.

I push a new version of the test where I use make_friedman1 that is pretty interesting because intuitively imputer with the mean will be worth than the native support because of the sine relationship between X and y.

I push a new version of the test where I use make_friedman1 that is pretty interesting because intuitively imputer with the mean will be worth than the native support because of the sine relationship between X and y.

Ah nice! Yeah that is pretty sensible. I also see a more stable test in #27966. Testing now with all global random seeds

I can't get the test_missing_values_is_resilience test to fail on main, what am I missing?

SKLEARN_TESTS_GLOBAL_RANDOM_SEED='all' pytest sklearn/tree/tests/test_tree.py -k is_resilience -v

Since this is supposed to be a non-regression test, I would expect the test to fail on main ...

Are you referring to the existing test on main or the new one?

Are you referring to the existing test on main or the new one?

test_missing_values_is_resilience. With @glemaitre modifications I thought that this was a non-regression test that was supposed to fail in main but maybe I misunderstood.

test_missing_values_is_resilience. With @glemaitre modifications I thought that this was a non-regression test that was supposed to fail in main but maybe I misunderstood.

Ah I see. test_regression_tree_missing_values_toy changes are the ones that will fail on main because the impurity is still not computed correctly on main.

However, when we change the cython code to make it correct, the test_missing_values_is_resilience was failing. @glemaitre suggested that this test was not actually a good test in testing "missing value support natively vs situation_X", where "situation_X" is some non-missing value situation:

1. "situation_X" was originally no missing values
2. "situation_X" is now imputing the missing values naively

In addition, the dataset used originally was not very good (see: #28327 (comment)).

Hope that clarifies!

Thanks for the explanation that clarifies things a lot!

I pushed a small simplification to do a classification dataset based on friedman1 (there may be an easier way). That allows to remove the tolerance thing which I did not like too much and found a bit hard to follow.

I made sure locally that the test pass for all the seeds, but if you can double-check that would be great:

SKLEARN_TESTS_GLOBAL_RANDOM_SEED='all' pytest sklearn/tree/tests/test_tree.py -k is_resilience -s

Feel free to improve it if you want!

Another thing I am wondering about: rather than only checking that the mse is positive, would it make sense to make a simple test like the one in #28316 where we theoretically know what the impurity should be and we make sure that this is the case.

I pushed a small simplification to do a classification dataset based on friedman1 (there may be an easier way). That allows to remove the tolerance thing which I did not like too much and found a bit hard to follow.

I made sure locally that the test pass for all the seeds, but if you can double-check that would be great:

Thanks! Will take a look this weekend.

Another thing I am wondering about: rather than only checking that the mse is positive, would it make sense to make a simple test like the one in #28316 where we theoretically know what the impurity should be and we make sure that this is the case.

I think it's possibly a good unit-test to add in addition to what we have. The existing test test_regression_tree_missing_values_toy is a test that implicitly ensures we do not compute negative MSE values due to improperly handling the missing values in both right/left children. This is imo a separate issue from testing that MSE is computed correctly. As an example: Before this PR, the MSE is numerically computed correctly but only when missing values go to the left. So the test would be insufficient.

Also, I'm planning on extending this test in #27966, so for extra trees, I think it would be difficult to compute theoretically the true MSE since it's random. WDYT is the best approach here?

In my last commit, I have pushed a tweak to check that the impurity match after the first split with a tree fitted without NaN, so at least that's a cheap way to sanity check impurity calculation. Not sure if there is an way to generalise the idea for deeper tree levels.

I have to admit I did find the time to understand the tree code well enough to be 100% confident that the code change is correct.

I am fine with merging this as is since the additional test where the NaNs goes to the right node makes complete sense.

I would also be completely fine to revert the additional sanity-check I have added in 55e96af.

@lesteve I'm fine with the changes that you have done.

OK let's merge this then, thanks @adam2392 for the fix!