Talip7/scikit-learn-issues-multilabel huggingface dataset:
Use SYRK instead of GEMM in pairwise distance

### Discussed in https://github.com/scikit-learn/scikit-learn/discussions/27877

<div type='discussions-op-text'>

<sup>Originally posted by **darshanp4** November 30, 2023</sup>
Hello 

I was checking the DBSCAN algo , where mostly computing pairwise distance it use -2X*X**T, so for this operation currently sklearn uses the blas _gemm. where it consuming much time. If we can use the syrk which also level3 blas (https://pyclblas.readthedocs.io/en/latest/SYRK.html). Which is more optimized for this type of operations.

Is there any similar approach any one seen or tried.

Thank you.  </div>

COMMENT:
The point is that the pairwise distances performe reductions (aggregation functions) over a chunk of distance values. This chunk size was empirically tested, and 256 chosen as a good *middle ground*.
This is much different from BLAS functions, e.g. matrix-matrix operations is just multiplications and additions, nothing else. Therefore, the cache is even more important and, I guess, the most engineering-hours of work put into optimizing it - out of all algos!

Back to this issue: As SYRK would only apply to the diagonal, it is a 2. order effect. I'm -1 on it considering the trade-offs with code complexity.

Labels: Performance, Needs Benchmarks
sklearn.linear_model.lars_path_gram ONLY accepts Xy to be of shape (n_features,) and NOT (n_features, n_targets)

### Describe the bug

The [documentation](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.lars_path_gram.html) says lars_path_gram accepts Xy to be _"array-like of shape (n_features,) or (n_features, n_targets)"_. 
![WechatIMG671](https://github.com/scikit-learn/scikit-learn/assets/52297971/7c3c8a07-a4d9-443e-8d75-4345fa2df56b)

However, it does not support the latter since the cython function it calls [sklearn.utils.arrayfuncs.min_pos](https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/utils/arrayfuncs.pyx#L13) only accepts 1D array instead of 2D matrix.

### Steps/Code to Reproduce

```
from sklearn.linear_model import lars_path_gram
import numpy as np
y=np.array([[0],[-1],[1]])
x=np.identity(3)
lars_path_gram(Xy=x.T@y,Gram=x.T@x,n_samples=3)
```

### Expected Results

```
# The expected result should be same as following.
# The following code runs correctly.
from sklearn.linear_model import lars_path_gram
import numpy as np
y=np.array([[0],[-1],[1]])
x=np.identity(3)
lars_path_gram(Xy=x.T@y[:,0],Gram=x.T@x,n_samples=3) #replaced x.T@y with x.T@y[:,0] which converts matrix into array
```

### Actual Results

```
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "lib/python3.9/site-packages/sklearn/linear_model/_least_angle.py", line 307, in lars_path_gram
    return _lars_path_solver(
  File "lib/python3.9/site-packages/sklearn/linear_model/_least_angle.py", line 722, in _lars_path_solver
    g1 = arrayfuncs.min_pos((C - Cov) / (AA - corr_eq_dir + tiny32))
  File "sklearn/utils/arrayfuncs.pyx", line 13, in sklearn.utils.arrayfuncs.__pyx_fused_cpdef
TypeError: No matching signature found
```

### Versions

```shell
System:
    python: 3.9.2 (default, Feb 28 2021, 17:03:44)  [GCC 10.2.1 20210110]
executable: /bin/python
   machine: Linux-5.10.0-26-cloud-amd64-x86_64-with-glibc2.31

Python dependencies:
      sklearn: 1.3.2
          pip: 20.3.4
   setuptools: 44.1.1
        numpy: 1.25.2
        scipy: 1.11.3
       Cython: 3.0.6
       pandas: 2.1.0
   matplotlib: 3.8.0
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: openmp
   internal_api: openmp
    num_threads: 4
         prefix: libgomp
       filepath: /lib/python3.9/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 4
         prefix: libopenblas
       filepath: /lib/python3.9/site-packages/numpy.libs/libopenblas64_p-r0-5007b62f.3.23.dev.so
        version: 0.3.23.dev
threading_layer: pthreads
   architecture: Haswell

       user_api: blas
   internal_api: openblas
    num_threads: 4
         prefix: libopenblas
       filepath: /lib/python3.9/site-packages/scipy.libs/libopenblasp-r0-23e5df77.3.21.dev.so
        version: 0.3.21.dev
threading_layer: pthreads
   architecture: Haswell
```

COMMENT:
Indeed the documentation was incorrect.

Labels: Bug, Needs Triage
sklearn.linear_model.lars_path_gram ONLY accepts Xy to be of shape (n_features,) and NOT (n_features, n_targets)

### Describe the bug

The [documentation](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.lars_path_gram.html) says lars_path_gram accepts Xy to be _"array-like of shape (n_features,) or (n_features, n_targets)"_. 
![WechatIMG671](https://github.com/scikit-learn/scikit-learn/assets/52297971/7c3c8a07-a4d9-443e-8d75-4345fa2df56b)

However, it does not support the latter since the cython function it calls [sklearn.utils.arrayfuncs.min_pos](https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/utils/arrayfuncs.pyx#L13) only accepts 1D array instead of 2D matrix.

### Steps/Code to Reproduce

```
from sklearn.linear_model import lars_path_gram
import numpy as np
y=np.array([[0],[-1],[1]])
x=np.identity(3)
lars_path_gram(Xy=x.T@y,Gram=x.T@x,n_samples=3)
```

### Expected Results

```
# The expected result should be same as following.
# The following code runs correctly.
from sklearn.linear_model import lars_path_gram
import numpy as np
y=np.array([[0],[-1],[1]])
x=np.identity(3)
lars_path_gram(Xy=x.T@y[:,0],Gram=x.T@x,n_samples=3) #replaced x.T@y with x.T@y[:,0] which converts matrix into array
```

### Actual Results

```
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "lib/python3.9/site-packages/sklearn/linear_model/_least_angle.py", line 307, in lars_path_gram
    return _lars_path_solver(
  File "lib/python3.9/site-packages/sklearn/linear_model/_least_angle.py", line 722, in _lars_path_solver
    g1 = arrayfuncs.min_pos((C - Cov) / (AA - corr_eq_dir + tiny32))
  File "sklearn/utils/arrayfuncs.pyx", line 13, in sklearn.utils.arrayfuncs.__pyx_fused_cpdef
TypeError: No matching signature found
```

### Versions

```shell
System:
    python: 3.9.2 (default, Feb 28 2021, 17:03:44)  [GCC 10.2.1 20210110]
executable: /bin/python
   machine: Linux-5.10.0-26-cloud-amd64-x86_64-with-glibc2.31

Python dependencies:
      sklearn: 1.3.2
          pip: 20.3.4
   setuptools: 44.1.1
        numpy: 1.25.2
        scipy: 1.11.3
       Cython: 3.0.6
       pandas: 2.1.0
   matplotlib: 3.8.0
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: openmp
   internal_api: openmp
    num_threads: 4
         prefix: libgomp
       filepath: /lib/python3.9/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 4
         prefix: libopenblas
       filepath: /lib/python3.9/site-packages/numpy.libs/libopenblas64_p-r0-5007b62f.3.23.dev.so
        version: 0.3.23.dev
threading_layer: pthreads
   architecture: Haswell

       user_api: blas
   internal_api: openblas
    num_threads: 4
         prefix: libopenblas
       filepath: /lib/python3.9/site-packages/scipy.libs/libopenblasp-r0-23e5df77.3.21.dev.so
        version: 0.3.21.dev
threading_layer: pthreads
   architecture: Haswell
```

COMMENT:
It has been addressed in #28419

Labels: Bug, Needs Triage
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
Could you please post a minimal reproducible showing this issue?

Labels: New Feature, help wanted
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
That's an interesting suggestion. @glouppe are you aware of any reference in the literature that study this potential source of bias?

Labels: New Feature, help wanted
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
@CompRhys 

Ok, I guess this would be your reproducible code, I will play around with it a little as well.

For max outputs how would you go about choosing which outputs were considered when selecting the optimal split?

Labels: New Feature, help wanted
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/tree/_tree.pyx
https://github.com/scikit-learn/scikit-learn/blob/678e3999eeaadcaaef523d1d0d2f52a25986d460/sklearn/tree/_splitter.pxd
https://github.com/scikit-learn/scikit-learn/blob/678e3999eeaadcaaef523d1d0d2f52a25986d460/sklearn/tree/_criterion.pxd

So you need to familiarise yourself with these files. I haven't gone through it in depth myself (no time) but somewhere in there there should be logic that is selecting which features to consider when determining the split. You'll want to add some logic that will sample which outputs to consider when calculating the impurity. There's a method `node_impurity()` that is the thing you'll probably want to edit.

The proposal here is to add a layer of randomization that randomly draws a subset of the output features for calculating the impurity, currently the impurity is just the sum over all the output dimensions. This would be controlled by the `max_outputs` argument to tree based models described in the top post.

Labels: New Feature, help wanted
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
@CompRhys ok I'll look into it. Thank you

Labels: New Feature, help wanted
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
Hey update, I started to look deeper into implementation, I believe the logic you are looking for is located here:
scikit-learn/sklearn/tree/_splitter.pyx#L1562
sklearn/tree/_splitter.pyx#L1598


I will be looking into this further. If anyone gets it before I do feel free to write your own pull request. Once I have a reasonable draft I will draft a pull request. Might take a minute it is tricky logic.

Labels: New Feature, help wanted
[RFC] Varying the number of outputs considered for splitting in Multi Output Decision Trees

### Describe the workflow you want to enable

One strength of RFRs is that they are incredibly robust and therefore provide a strong baseline for many tasks without needing to consider normalization or scaling of either the inputs or outputs. In the case of multi-output RFRs this robustness towards the output space goes away due to the summing of impurities across different output dimensions which entails the need to standardize the output labels to ensure that undue attention isn't given to particular outputs. Currently the documentation doesn't readily inform the user of this artifact. In the spirit of the Random Forest one solution to avoiding this problem would be to randomly sample which output(s) to consider for the determination of the split. If the number of outputs was set to 1 then we would end up with a case where the normalization of the output space once again doesn't matter.

### Describe your proposed solution

The introduction of a new kwarg `max_outputs` (by analogy to `max_features`) could allow users to control how many outputs were considered when selecting the optimal split. If set to `1.0` all outputs would be used as currently, if set to `1` then a single output would be used as described above. This seems like a relevant and natural hyper-parameter for the multi-output RFR.  

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

I have not been able to find literature that explores the above slight adjustment to the current algorithm. This is a RFC to see if the team would accept such a PR in principle without the quoted 200+ citation requirement if sufficient empirical evidence was provided.

COMMENT:
@ogrisel should I proceed with this issue, would you like to see it implemented? Or do we need a better example? I want to wait until the reproducible code sign is off so I know you'll want this

Labels: New Feature, help wanted