✔️ Linting Passed

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

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

@jjerphan I pushed a commit to run test_pairwise_distances_argkmin with "all random seeds" so that we can see if the improved error message help us understand what's going on with #27126.

Feel free to adapt this PR at will.

I ran one of the failing tests of #27126 locally using:

SKLEARN_TESTS_GLOBAL_RANDOM_SEED="45" pytest sklearn/metrics/tests/test_pairwise_distances_reduction.py -v -k "test_pairwise_distances_argkmin and cityblock" -x  --pdb

the error message was:

E               AssertionError: Neighbors indices are not matching when rounding distances at
E                 3 significant digits derived from rtol=1.0e-04.
E                 
E                 Query vector index         : 61
E                 Reference ordered distances: [159450.703125 160197.78125  160429.53125  161349.21875  161953.109375
E                  162041.515625 162137.984375 162665.90625  162700.25     163778.59375 ]
E                 Computed ordered distances : [159450.65128034 160197.77867103 160429.4601412  161349.25246161
E                  161953.08416814 162041.40858293 162138.01407665 162665.88381121
E                  162700.24564451 163778.55885714]
E                 Norm. abs. ord. dist. diff.: 0.03828817754983902
E                 Rounded distance           : 164000.0
E                 Neighbors group rank       : 5
E                 Reference neighbors indices: [16]
E                 Computed neighbors indices : [88]
E               assert {16} == {88}
E                 Extra items in the left set:
E                 16
E                 Extra items in the right set:
E                 88
E                 Full diff:
E                 - {88}
E                 + {16}

but I also wanted to see the distances and the matching indices arrays, so I used the debugger:

(Pdb) p ref_indices_row
array([39, 48, 21, 56, 46, 93, 59, 54, 45, 16])
(Pdb) p indices_row
array([39, 48, 21, 56, 46, 93, 59, 54, 45, 88])
(Pdb) p ref_dist_row
array([159450.703125, 160197.78125 , 160429.53125 , 161349.21875 ,
       161953.109375, 162041.515625, 162137.984375, 162665.90625 ,
       162700.25    , 163778.59375 ])
(Pdb) p dist_row
array([159450.65128034, 160197.77867103, 160429.4601412 , 161349.25246161,
       161953.08416814, 162041.40858293, 162138.01407665, 162665.88381121,
       162700.24564451, 163778.55885714])

The distances for the last neighbor are indeed very close and the difference happens at the 8th digits which might be expected for float32 rounding errors.

Using pdb I went up in the stack to compare the distances in the reference distance matrix computed by cdist:

(Pdb) p dist_matrix[61, 16]
163778.57524980605
(Pdb) p dist_matrix[61, 88]
163778.55885714293

so those are indeed close. Let's have a look at the next neighbors in the reference cdist matrix:

(Pdb) p dist_matrix.argsort(axis=1)[61, :15]
array([39, 48, 21, 56, 46, 93, 59, 54, 45, 88, 16, 15, 17, 73,  7])

so 88 and 16 are indeed the closest candidate for rank k=10 according to cdist.

So we should probably find a way to tolerate those cases where the Cython code returns neighbors swaps within the range of rounding errors of the chosen dtype.

The CI has failed because of the way I formatted the commit message. Let me push another empty commit with the right message structure.

@jjerphan the last commit message makes it possible to reproduce all the failures with the extra info of this PR.

I suppose we should simplify the code of assert_argkmin_results_quasi_equality. Instead of the complex bucketing strategy, we could provide the full reference distance row (without sorting and truncation) and check that the top k computed neighbors are:

• in the right order based on the Cython computed distances,
• have Cython distance values that match the reference cdist distance within tolerance (irrespective of the reference ordering),
• such that there exist no other element in the reference distance row of the query that is significantly smaller most distant top-k neighbor found by Cython.

This should be probably more robust while being both strict enough and easier to debug in case of failure. WDYT?

We could do that yes.

I think the current yet complex assertion checks that the ordering between both algorithms is identical (up to a bucketing for acceptable numerical imprecision of float32). Is there a way we could check that with what you propose? If I understand your first item correctly, it does not propose to assert that but only the correct ordering of the index w.r.t their distances, is this right?

Is there a way we could check that with what you propose? If I understand your first item correctly, it does not propose to assert that but only the correct ordering of the index w.r.t their distances, is this right?

Yes but since the computed distances for each neighbor should match the reference computed distance within round-off errors and furthermore that there should not exist any significantly closer neighbor based on the reference distances, the approximate ordering should also be satisfied as a result.

Let me try to give it a shot.

@jjerphan I pushed two commits to implement what I had in mind with even stronger tests for the assertion function. This also fixes some xfail edge cases (at least on my machine).

I decided to focus this PR to the argkmin tests for now but we could do a follow-up PR to do a similar treatment for the radius neighbors tests and further simplify this test file.

Once the last commit CI is green, I will push a new empty commit with message [azure parallel] [all random seeds] test_pairwise_distances_argkmin to re-run will all seeds on the CI.

The code coverage report reveals that the tests for the checker could be improved. I will do that tomorrow. In the mean time let me push the all random seed commit.

@jjerphan finally this PR is ready for reviewing.

It should reduce the average CI time quite significantly (see the CI reports of the second to last commit).

Thanks!

I do not really have time to review it now, but I trust you.

(I find that having me approve this PR is a bit weird since I opened it but I, in fact, have not contributed to it much but you.)

With the recent merges to accelerate conda install and reduce time of the slowest test, combined with this PR, the macOS CI is almost fast again!

I have not reviewed it entirely, but I am trusting you for coming up with better assertions than mine.

Let's wait for you to get a but of time to have a quick look, at least on the updated tests and their messages. If the test cases and the messages make sense to you, then this should be good.

I can't approve this PR.

You can just say so in a comment :)

Thanks for the review @glemaitre.