Talip7/scikit-learn-issues-multilabel huggingface dataset:
Array API support for k-nearest neighbors models with the brute force method

This issue is a sibling of a similar issue for k-means: #26585 with similar purpose but likely different constraints.

In particular an efficient implementation of k-NN on the GPU would require:

- `torch.cdist`
- `torch.topk` being discussed at:
   - https://github.com/data-apis/array-api/issues/629

COMMENT:
Here is a relevant gist of what could be a pytorch drop-in replacement for the `kneighbors` method:

https://gist.github.com/fcharras/82772cf7651e087b3b91b99105a860dd

Self quoting myself in the [k-means thread:](https://gist.github.com/fcharras/ce1f1df7d15675268827e1fb9b65265b):

> to my knowledge the best brute force implementations require materializing the pairwise distance matrix in memory and can't go farther than the IO bottleneck, so the speedup one can get is more limited, and the pytorch implementation should be decently close from the best you can get.

Labels: New Feature, Array API
Array API support for k-nearest neighbors models with the brute force method

This issue is a sibling of a similar issue for k-means: #26585 with similar purpose but likely different constraints.

In particular an efficient implementation of k-NN on the GPU would require:

- `torch.cdist`
- `torch.topk` being discussed at:
   - https://github.com/data-apis/array-api/issues/629

COMMENT:
It would be interesting to compare with cuML and if cuML is much faster than this PyTorch GPU implementation of brute force kNN, then it might be interesting to see if we can get similar performance with Triton based implementation.

Labels: New Feature, Array API
Array API support for k-nearest neighbors models with the brute force method

This issue is a sibling of a similar issue for k-means: #26585 with similar purpose but likely different constraints.

In particular an efficient implementation of k-NN on the GPU would require:

- `torch.cdist`
- `torch.topk` being discussed at:
   - https://github.com/data-apis/array-api/issues/629

COMMENT:
Forked your original gist and added some basic cuml comparison: https://gist.github.com/betatim/68219c95f539df51afad96cd9cd14a1c

On a machine with 8 Tesla V100 (32GB RAM), 80 Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz (from looking at `/proc/cpuinfo`) and 1TB RAM I get about 8s for the torch implementation and about 1s for the cuml option. With 5M samples in the data, so more than the original gist used.

On a second run I got 6s and 0.33s respectively. Seems to fluctuate a bit.

Labels: New Feature, Array API
Array API support for k-nearest neighbors models with the brute force method

This issue is a sibling of a similar issue for k-means: #26585 with similar purpose but likely different constraints.

In particular an efficient implementation of k-NN on the GPU would require:

- `torch.cdist`
- `torch.topk` being discussed at:
   - https://github.com/data-apis/array-api/issues/629

COMMENT:
Have you tried to set `CUDA_VISIBLE_DEVICES=0` to make sure that none of the two implementation leverages the fact that you have multiple GPU devices on the benchmark machine?

Labels: New Feature, Array API
Array API support for k-means

This is an early issue to publicly discuss the possibility (or not) to use the Array API (see #22352) for k-means and make it run on GPUs using PyTorch in particular.

@fcharras has already started to run some promising experiments using the raw PyTorch API. Maybe you could link to a gist with your code?

Unfortunately, the current state of the Array API is likely too limiting because AFAIK it does not yet expose the equivalent of `torch.cdist`, `torch.expand` and `torch.scatter_add_`.

The purpose of this issue is to precisely identify what is blocking us with the current state of Array API and discuss potential solutions:

- use this use case to report to the Array API standardization committee what are our needs to make the spec evolve and benefit everybody;
- alternatively, explore the use of multi-dispatch system such as [uarray](https://github.com/Quansight-Labs/uarray) that is being adopted in scipy to make it possible to maintain a pytorch-specific optimized code path as an alternative to a slower yet generic Array API code path and numpy-optimized code path that would rely on our current Cython code,
- decide that the estimator-level engine API proposed in #25535 is the only sane way to make this estimator GPU (which I now doubt personally).

COMMENT:
Here is a gist with I think a rather comprehensive implementation of the lloyd algorithm with pytorch:

https://gist.github.com/fcharras/ce1f1df7d15675268827e1fb9b65265b

Scroll down to the bottom of the file for a quick tester.

This function is almost a drop-in replacement for the lloyd private function in the scikit-learn implementation.

For k-means, running this on gpu does offer a speedup with respect to current scikit-learn performance (in the x2 - x5 range I think ?), but in the realm of gpu implementations of kmeans it is a bit underwhelming. Both the "pairwise distance + min lookup" and "weight multiplication + centroid update" steps should be fused rather than being called separately with materializing intermediate results in memory (because the read/write in memory is the bottleneck), that would offer another x2 - x5 speedup.

I'll post a similar gist for the KNN. For the KNN it's a different story, to my knowledge the best brute force implementations require materializing the pairwise distance matrix in memory and can't go farther than the IO bottleneck, so the speedup one can get is more limited, and the pytorch implementation should be decently close from the best you can get.

Labels: New Feature, Array API
Array API support for k-means

This is an early issue to publicly discuss the possibility (or not) to use the Array API (see #22352) for k-means and make it run on GPUs using PyTorch in particular.

@fcharras has already started to run some promising experiments using the raw PyTorch API. Maybe you could link to a gist with your code?

Unfortunately, the current state of the Array API is likely too limiting because AFAIK it does not yet expose the equivalent of `torch.cdist`, `torch.expand` and `torch.scatter_add_`.

The purpose of this issue is to precisely identify what is blocking us with the current state of Array API and discuss potential solutions:

- use this use case to report to the Array API standardization committee what are our needs to make the spec evolve and benefit everybody;
- alternatively, explore the use of multi-dispatch system such as [uarray](https://github.com/Quansight-Labs/uarray) that is being adopted in scipy to make it possible to maintain a pytorch-specific optimized code path as an alternative to a slower yet generic Array API code path and numpy-optimized code path that would rely on our current Cython code,
- decide that the estimator-level engine API proposed in #25535 is the only sane way to make this estimator GPU (which I now doubt personally).

COMMENT:
It would be interesting to see if `torch.compile` could help for `_min_over_pairwise_distance`.

Labels: New Feature, Array API
Array API support for k-means

This is an early issue to publicly discuss the possibility (or not) to use the Array API (see #22352) for k-means and make it run on GPUs using PyTorch in particular.

@fcharras has already started to run some promising experiments using the raw PyTorch API. Maybe you could link to a gist with your code?

Unfortunately, the current state of the Array API is likely too limiting because AFAIK it does not yet expose the equivalent of `torch.cdist`, `torch.expand` and `torch.scatter_add_`.

The purpose of this issue is to precisely identify what is blocking us with the current state of Array API and discuss potential solutions:

- use this use case to report to the Array API standardization committee what are our needs to make the spec evolve and benefit everybody;
- alternatively, explore the use of multi-dispatch system such as [uarray](https://github.com/Quansight-Labs/uarray) that is being adopted in scipy to make it possible to maintain a pytorch-specific optimized code path as an alternative to a slower yet generic Array API code path and numpy-optimized code path that would rely on our current Cython code,
- decide that the estimator-level engine API proposed in #25535 is the only sane way to make this estimator GPU (which I now doubt personally).

COMMENT:
I think it would be interesting to write a special-cased version of the PyTorch implementation for k-means without sample weights because in practice very few people have non-None sample weights.

Then it would be nice to have a summary table of run results for various implementations and hardware on the same data.

Maybe let's try a dataset just small enough so that cuML does not crash: https://github.com/rapidsai/cuml/issues/5470.

Labels: New Feature, Array API
Array API support for k-means

This is an early issue to publicly discuss the possibility (or not) to use the Array API (see #22352) for k-means and make it run on GPUs using PyTorch in particular.

@fcharras has already started to run some promising experiments using the raw PyTorch API. Maybe you could link to a gist with your code?

Unfortunately, the current state of the Array API is likely too limiting because AFAIK it does not yet expose the equivalent of `torch.cdist`, `torch.expand` and `torch.scatter_add_`.

The purpose of this issue is to precisely identify what is blocking us with the current state of Array API and discuss potential solutions:

- use this use case to report to the Array API standardization committee what are our needs to make the spec evolve and benefit everybody;
- alternatively, explore the use of multi-dispatch system such as [uarray](https://github.com/Quansight-Labs/uarray) that is being adopted in scipy to make it possible to maintain a pytorch-specific optimized code path as an alternative to a slower yet generic Array API code path and numpy-optimized code path that would rely on our current Cython code,
- decide that the estimator-level engine API proposed in #25535 is the only sane way to make this estimator GPU (which I now doubt personally).

COMMENT:
A triton implementation of https://github.com/soda-inria/sklearn-numba-dpex/tree/main/sklearn_numba_dpex/kmeans would also be interesting to compare against.

Labels: New Feature, Array API
⚠️ CI failed on Wheel builder ⚠️

**CI failed on [Wheel builder](https://github.com/scikit-learn/scikit-learn/actions/runs/5274563578)** (Jun 15, 2023)

COMMENT:
Looking through `build_tools/update_environments_and_lock_files.py`, it looks like all our CI jobs that run on PRs have matplotlib installed, so we did not catch this during development.

Labels: Bug
Improving the descriptions in decision tree structure example

### Describe the issue linked to the documentation

I am suggesting two improvements to the documentation of decision trees. This is motivated by constantly having to come back to the source code to try to understand what `DecisionTreeClassifier.tree_.value` is.

I am unsure what do the element values inside the `value` 3D array store? I get that at the leaf IDs, they store the average predicted probabilities. What about on the non-leaf IDs?

### Sphinx example
In https://scikit-learn.org/stable/auto_examples/tree/plot_unveil_tree_structure.html#sphx-glr-auto-examples-tree-plot-unveil-tree-structure-py, there is a walk-through meant to educate users/devs on the structure of a decision tree that stems from the Cython `Tree` class.

Currently, it describes:

- children_left[i]: id of the left child of node i or -1 if leaf node
- children_right[i]: id of the right child of node i or -1 if leaf node
- feature[i]: feature used for splitting node i
- threshold[i]: threshold value at node i
- n_node_samples[i]: the number of training samples reaching node i
- impurity[i]: the impurity at node I

However, there is value, missing_go_to_left and weighted_n_node_samples as well accessible as properties of `Tree`.

### Cython docstring
Moreover, the docstring in the Cython Tree class is missing a description of the missing_go_to_left  property. https://github.com/scikit-learn/scikit-learn/blob/1e8a5b833d1b58f3ab84099c4582239af854b23a/sklearn/tree/_tree.pyx#L639

In addition, `max_depth` seems to still be included even though it is not a property anymore? Should this still be in the Cython docstring?

### Suggest a potential alternative/fix

1. Add descriptions to the sphinx example `plot_unveil_tree_structure.py` for `value`, `max_depth`, `missing_go_to_left` and `weighted_n_node_samples`.

- value: a 3D array of shape (node_count, n_outputs, max_n_classes), where n_outputs are the number of columns in `y` and `max_n_classes` is either the number of classes (if classification), or the # of columns in `y` (if regression). The values within `value` correspond to the...?
- `max_depth`: a integer corresponding to the maximum depth of the tree
- `missing_go_to_left`: a 1D boolean array of shape (node_count), on whether or not this node contained missing values or not?
- `weighted_n_node_samples`: Similar to `n_node_samples`, except each sample is weighted by some `sample_weight` during fit

2. Patch the Cython docstring to include a description of `missing_go_to_left`.

COMMENT:
I'm +1 on the proposed solutions.

Labels: Documentation, module:tree
Improving the descriptions in decision tree structure example

### Describe the issue linked to the documentation

I am suggesting two improvements to the documentation of decision trees. This is motivated by constantly having to come back to the source code to try to understand what `DecisionTreeClassifier.tree_.value` is.

I am unsure what do the element values inside the `value` 3D array store? I get that at the leaf IDs, they store the average predicted probabilities. What about on the non-leaf IDs?

### Sphinx example
In https://scikit-learn.org/stable/auto_examples/tree/plot_unveil_tree_structure.html#sphx-glr-auto-examples-tree-plot-unveil-tree-structure-py, there is a walk-through meant to educate users/devs on the structure of a decision tree that stems from the Cython `Tree` class.

Currently, it describes:

- children_left[i]: id of the left child of node i or -1 if leaf node
- children_right[i]: id of the right child of node i or -1 if leaf node
- feature[i]: feature used for splitting node i
- threshold[i]: threshold value at node i
- n_node_samples[i]: the number of training samples reaching node i
- impurity[i]: the impurity at node I

However, there is value, missing_go_to_left and weighted_n_node_samples as well accessible as properties of `Tree`.

### Cython docstring
Moreover, the docstring in the Cython Tree class is missing a description of the missing_go_to_left  property. https://github.com/scikit-learn/scikit-learn/blob/1e8a5b833d1b58f3ab84099c4582239af854b23a/sklearn/tree/_tree.pyx#L639

In addition, `max_depth` seems to still be included even though it is not a property anymore? Should this still be in the Cython docstring?

### Suggest a potential alternative/fix

1. Add descriptions to the sphinx example `plot_unveil_tree_structure.py` for `value`, `max_depth`, `missing_go_to_left` and `weighted_n_node_samples`.

- value: a 3D array of shape (node_count, n_outputs, max_n_classes), where n_outputs are the number of columns in `y` and `max_n_classes` is either the number of classes (if classification), or the # of columns in `y` (if regression). The values within `value` correspond to the...?
- `max_depth`: a integer corresponding to the maximum depth of the tree
- `missing_go_to_left`: a 1D boolean array of shape (node_count), on whether or not this node contained missing values or not?
- `weighted_n_node_samples`: Similar to `n_node_samples`, except each sample is weighted by some `sample_weight` during fit

2. Patch the Cython docstring to include a description of `missing_go_to_left`.

COMMENT:
I will submit a PR

Labels: Documentation, module:tree
Failed testcase with numpy binary compiled with clang compiler on AWS Graviton

### Describe the bug

Below testcase is failing when we are building scikit-learn using numpy binary compiled with clang compiler on AWS Graviton:

```py
    @wraps(func)
    def inner(*args, **kwds):
        with self._recreate_cm():
>           return func(*args, **kwds)
E           AssertionError: 
E           Not equal to tolerance rtol=1e-06, atol=0
E           
E           Mismatched elements: 5 / 5 (100%)
E           Max absolute difference: 0.00270843
E           Max relative difference: 6.70094909e-06
E            x: array([-295.771699,  286.233237, -474.636702,  192.601933,  459.884624])
E            y: array([-295.770108,  286.231319, -474.634337,  192.600684,  459.881916])

/usr/lib/python3.10/contextlib.py:79: AssertionError
= 1 failed, 26002 passed, 3301 skipped, 93 xfailed, 44 xpassed, 2444 warnings in 750.63s (0:12:30) =
```



### Steps/Code to Reproduce

``` bash
git clone https://github.com/numpy/numpy.git 
cd numpy
git checkout v1.24.3
git submodule update --init
CC=clang-15 CXX=clang++-15 python3 setup.py build_ext --inplace -j $(nproc)
pip install .
python3 runtests.py -v -m full
```

### Expected Results

No failures. Testcases should be either passed or skipped.

### Actual Results

```py
    @wraps(func)
    def inner(*args, **kwds):
        with self._recreate_cm():
>           return func(*args, **kwds)
E           AssertionError: 
E           Not equal to tolerance rtol=1e-06, atol=0
E           
E           Mismatched elements: 5 / 5 (100%)
E           Max absolute difference: 0.00270843
E           Max relative difference: 6.70094909e-06
E            x: array([-295.771699,  286.233237, -474.636702,  192.601933,  459.884624])
E            y: array([-295.770108,  286.231319, -474.634337,  192.600684,  459.881916])

/usr/lib/python3.10/contextlib.py:79: AssertionError
= 1 failed, 26002 passed, 3301 skipped, 93 xfailed, 44 xpassed, 2444 warnings in 750.63s (0:12:30) =
```

### Versions

```shell
latest version. Scikit-learn built from source code from main branch.
```

COMMENT:
Looking through your "steps to reproduce" it is building and running the tests from NumPy and scikit-learn is not involved. I recommend going to https://github.com/numpy/numpy to see if they can help.

Labels: Bug, Needs Triage
False positive warning in `FunctionTransformer`

While looking at #26543, I find out that we raise a `FutureWarning` that looked like a false positive to me:

```python
from sklearn.preprocessing import FunctionTransformer, OneHotEncoder
from sklearn.pipeline import make_pipeline
import pandas as pd
import numpy as np


test_df = pd.DataFrame(
    np.random.randint(low=0, high=9, size=(10, 2)), columns=["None", "valid"]
)


def _drop_None_cols(df):
    col_names = [col for col in df.columns if "None" in col]
    if len(col_names):
        return df.drop(columns=col_names)
    return df


encoder_dropping_None = make_pipeline(
    OneHotEncoder(sparse_output=False),
    FunctionTransformer(_drop_None_cols),
).set_output(transform="pandas")


# encoder_dropping_None.fit_transform(test_df)
```

```
/Users/glemaitre/Documents/packages/scikit-learn/sklearn/preprocessing/_function_transformer.py:345: UserWarning: With transform="pandas", `func` should return a DataFrame to follow the set_output API.
  warnings.warn(
```

Indeed, my function `func` is returning a dataframe and the output of the transform is indeed a dataframe. So the warning is a bit surprising. Using the global config (i.e. `set_config` will not raise this warning).

COMMENT:
Maybe @thomasjpfan has already in mind what is wrong here before that I investigate the problem.

Labels: Enhancement
False positive warning in `FunctionTransformer`

While looking at #26543, I find out that we raise a `FutureWarning` that looked like a false positive to me:

```python
from sklearn.preprocessing import FunctionTransformer, OneHotEncoder
from sklearn.pipeline import make_pipeline
import pandas as pd
import numpy as np


test_df = pd.DataFrame(
    np.random.randint(low=0, high=9, size=(10, 2)), columns=["None", "valid"]
)


def _drop_None_cols(df):
    col_names = [col for col in df.columns if "None" in col]
    if len(col_names):
        return df.drop(columns=col_names)
    return df


encoder_dropping_None = make_pipeline(
    OneHotEncoder(sparse_output=False),
    FunctionTransformer(_drop_None_cols),
).set_output(transform="pandas")


# encoder_dropping_None.fit_transform(test_df)
```

```
/Users/glemaitre/Documents/packages/scikit-learn/sklearn/preprocessing/_function_transformer.py:345: UserWarning: With transform="pandas", `func` should return a DataFrame to follow the set_output API.
  warnings.warn(
```

Indeed, my function `func` is returning a dataframe and the output of the transform is indeed a dataframe. So the warning is a bit surprising. Using the global config (i.e. `set_config` will not raise this warning).

COMMENT:
OK, seeing the code in `set_output`, I can silence it only setting the encoder.

```python
encoder_dropping_None = make_pipeline(
    OneHotEncoder(sparse_output=False).set_output(transform="pandas"),
    FunctionTransformer(_drop_None_cols),
)
encoder_dropping_None.fit_transform(test_df)
```

Somehow, it is expected that I provide `feature_names_out` this is not really possible with what I want to do.

Looking at what is required, it makes somehow sense. However, I would not be surprised if a user set the output on the pipeline instead of going through each estimator and thinking if you really want to rewrap or not the output.

I don't really know what is best here.

Labels: Enhancement
False positive warning in `FunctionTransformer`

While looking at #26543, I find out that we raise a `FutureWarning` that looked like a false positive to me:

```python
from sklearn.preprocessing import FunctionTransformer, OneHotEncoder
from sklearn.pipeline import make_pipeline
import pandas as pd
import numpy as np


test_df = pd.DataFrame(
    np.random.randint(low=0, high=9, size=(10, 2)), columns=["None", "valid"]
)


def _drop_None_cols(df):
    col_names = [col for col in df.columns if "None" in col]
    if len(col_names):
        return df.drop(columns=col_names)
    return df


encoder_dropping_None = make_pipeline(
    OneHotEncoder(sparse_output=False),
    FunctionTransformer(_drop_None_cols),
).set_output(transform="pandas")


# encoder_dropping_None.fit_transform(test_df)
```

```
/Users/glemaitre/Documents/packages/scikit-learn/sklearn/preprocessing/_function_transformer.py:345: UserWarning: With transform="pandas", `func` should return a DataFrame to follow the set_output API.
  warnings.warn(
```

Indeed, my function `func` is returning a dataframe and the output of the transform is indeed a dataframe. So the warning is a bit surprising. Using the global config (i.e. `set_config` will not raise this warning).

COMMENT:
In the original code, the warning is raised when we call `.set_output` on the pipeline, not when we call `.fit_transform` on it.

Labels: Enhancement