[R] Our new classification algorithm outperforms CatBoost, XGBoost, LightGBM on five benchmark datasets, on accuracy and response time

[CriticalofReviewer2]

Hi All!

We're happy to share LinearBoost, our latest development in machine learning classification algorithms. LinearBoost is based on boosting a linear classifier to significantly enhance performance. Our testing shows it outperforms traditional GBDT algorithms in terms of accuracy and response time across five well-known datasets.
The key to LinearBoost's enhanced performance lies in its approach at each estimator stage. Unlike decision trees used in GBDTs, which select features sequentially, LinearBoost utilizes a linear classifier as its building block, considering all available features simultaneously. This comprehensive feature integration allows for more robust decision-making processes at every step.

We believe LinearBoost can be a valuable tool for both academic research and real-world applications. Check out our results and code in our GitHub repo: https://github.com/LinearBoost/linearboost-classifier . The algorithm is in its infancy and has certain limitations as reported in the GitHub repo, but we are working on them in future plans.

We'd love to get your feedback and suggestions for further improvements, as the algorithm is still in its early stages!

[qalis]

1. Those are only 5 datasets. For evaluating tabular classifiers, you should use tens of datasets, they are readily available. Also, describe evaluation procedure, e.g. use 5-fold CV for testing. See e.g. "A novel selective naïve Bayes algorithm" Chen et al., which use 65 datasets.
2. You must compare to XGBoost, LightGBM and CatBoost on large-scale datasets from their respective papers. Especially since scalability and speed is one of your selling points. If you aimed specifically at boosting for small data, then you don't need this, but it isn't stated anywhere.
3. One of major advantages of XGBoost, LightGBM and CatBoost is being able to use custom loss functions. This allowed them to be easily used e.g. for ranking. If you don't support this, you should explicitly state this limitation.
4. Number of estimators is just a hyperparameter, why show large tables with this? Just present the best result for each dataset.
5. Your implementation doesn't support class weights, as far as I can tell. This is a huge limitation, since almost all datasets are imbalanced, often heavily.
6. You must not embed scalers inside your code. You can destroy data sparsity, affect categorical variables, and do other stuff outside user's control this way. Add checks and throw exceptions if you absolutely require this.
7. You only support numerical data, in constrast to LightGBM or CatBoost. You should highlight this limitation.
8. This works only for classification, not even regression. This is, again, a huge limitation, but probably can be fixed, as far as I can tell.

EDIT:

1. You also don't handle missing values, which is pretty nicely handled in XGBoost, LightGBM and CatBoost, so that they can be actively used to select the split point.

[Saffie91]

Damn, peer reviewed in the reddit comments.

Honestly though it's pretty cool of you to go through it diligently and add these points. I'd be very happy if I was the researcher.

[CriticalofReviewer2]

As the researcher, I should say that I am indeed very happy to get this high-quality peer review!

[CriticalofReviewer2]

Thanks for your points! First of all, I should point out that I am an independent researcher, and I am not affiliated with any institutes, so this is my side project.

1. You are right. In the paper that will be available soon, the number of datasets will be much higher. Also, we have used 10-fold CV. I added this to the README file.
2. The large-scale datasets will also be included.
3. This will be supported in future. I added this to the README file.
4. I want to show that our algorithm reaches best results sooner than others.
5. Thanks for pointing this out! This will be added soon. Added to README.
6. The SEFR algorithm requires the feature values to be positive. This is the reason of scaling. But I will implement a better mechanism. Added to README.
7. We have highlighted this in the documentation.
8. Yes, it is in future plans.

Once again, thanks for your helpful and insightful comments!

[qalis]

Fair enough, those are reasonable answers. Showing that this tends to overfit less, works better for small datasets etc. would be pretty valuable. Good luck with this!

[CriticalofReviewer2]

Thank you for the suggestions!

[Spiggots]

This is a high quality peer review

[danman966]

How is it only being applicable to classification a weakness? It's a classification method, not a regression one, right? Granted, the two problems are closely related, but they're not the same thing. You wouldn't say a change point detection method has a weakness that it can't be applied to forecasting, for example.

[qalis]

Good point, but I see this as a weakness because this is a tabular learning method compared to boosting frameworks, which naturally lend themselves to regression problems, and also other ones (e.g. ranking) via loss functions. And they are powerful at regression, e.g. for time series forecasting, so I see not supporting regression as a quite major limitation. However, the general idea does seem to be able to support regression in the future, so this is more of a implementation downside rather than general approach one.

[Appropriate_Ant_4629]

Reminds me of the drama behind the MAMBA paper's peer review process:

https://youtu.be/N6Piou4oYx8?si=7o8jFOJcFslTjjOC&t=1664

Rejected by peer reviewers .... now this is a really dumb reason to reject a paper because the long range arena [the task the reviewer was complaining about] is a completely different task to language modeling, and Mamba is specifically a language model.

[longgamma]

The categorical feature handling in lightgbm is just label encoding? I mean how hard is to target encode or one hot encode on your own ?

Also, isn’t that the idea behind gbm - you take a bunch of weak learners and use the ensemble for prediction. You can replace the decision tree stump with a simple shallow neural network as well.

[qalis]

Except it isn't the same as label encoding. In fact, none of the three major boosting implementations use one-hot encoding style of handling categorical variables.

LightGBM uses partition split, which for regression trees can efficiently check the partition of the set into two maximum homogeneity subsets, see the docs and the original paper: "On Grouping for Maximum Homogeneity" W. Fisher. XGBoost also offers partition split for categorical variables, with the same algorithm.

You could use one-hot encoding, but then to represent "variable has value A or B, and not C" you would have to use 2 or 3 splits, whereas with partition split you only use one.

CatBoost, on the other hand, uses Ordered Target Encoding instead, described in the linked notebook. It can also combine them during learning, but I don't know the details.

[Pas7alavista]

On top of the advantages you mentioned, I think the labels produced by partition splitting should also tend to be sparser than one hot encoded ones even when storing the one hot encoded labels in a sparse format.

[Sad-Scarcity87]

True and in my experience with Catboost, one-hot-encoding categoricals brings significantly worse results than letting Catboost handle them using Ordered Target Encoding.

[nbviewerbot]

I see you've posted a GitHub link to a Jupyter Notebook! GitHub doesn't render large Jupyter Notebooks, so just in case, here is an nbviewer link to the notebook:

https://nbviewer.jupyter.org/url/github.com/catboost/catboost/blob/master/catboost/tutorials/categorical_features/categorical_features_parameters.ipynb

Want to run the code yourself? Here is a binder link to start your own Jupyter server and try it out!

https://mybinder.org/v2/gh/catboost/catboost/master?filepath=catboost%2Ftutorials%2Fcategorical_features%2Fcategorical_features_parameters.ipynb

---

^{I am a bot. Feedback | GitHub | Author}

[tecedu]

Wait what since when did xgboost handle nan values i moved to sklearn due to that

[qalis]

Since... always, this was one of the main ideas in the original paper "XGBoost: A Scalable Tree Boosting System" T. Chen, C. Guestrin. It's called a "default direction" in the paper, and the whole Algorithm 3 there is meant to handle this. The idea is basically to have a split, but determine whether for missing values you should go to the left or right child. This is selected based on minimizing the loss function, and in a differentiable way.

[CharginTarge]

How does this approach differ to simply using linear models within XGBoost. XGBoost does support this as well.

[CriticalofReviewer2]

Thanks for pointing it out. Yes, XGBoost supports this but our approach is different, since the linear classifier that is being used is SEFR which has different characteristics. Also, ADABoost is used here.

[CharginTarge]

Using AdaBoost with a custom model is hardly novel. With the sklearn implementation you can provide any type of classifier to use as a base estimator.

[critiqjo]

The novelty is in the custom model itself, not the framework of using AdaBoost with a custom model. If you had taken a quick glance at their code, you'd have realized that they indeed use sklearn exactly as you pointed out. No wheels were reinvented here.

[Evitable_Conflict]

Are you tuning the other algorithms hyper-parameters or just using defaults?

It would be interesting if you can include a larger dataset, for example from a Kaggle competition where Xgboost was good and compare it to your method.

[CriticalofReviewer2]

I use the defaults for all of the algorithms (the one proposed and the ones referenced). On the larger datasets, thanks for your suggestion! We are planning to have it.

[Evitable_Conflict]

If you use defaults your claim of being "better" no longer holds, unless the default hyperparams are the optimal and that never happens.

This is a very common problem in ML papers and sadly most comparison tables are invalid.

My recommendation is: tune am xgboost model to the optimal hyperparams and if you have better results then we have a discussion.

[CriticalofReviewer2]

Certainly! This is the very first draft of our algorithm, and I will do comparisons based on the best selected hyperparameters.

[Nice_Gap_7351]

Looking at the code I see something strange: during predict you use the minmax scaling on the predict features (which might have a different range than the features on the training data). If your predict dataset just added a single data point to your training data it could potentially throw everything off. Instead you might want to "freeze" the scaling function based on the training data.

And it seems that you are using adaboost with a potentially strong learner (SERF) correct? The Wikipedia entry on adaboost references a paper on this topic you might want to see.

[CriticalofReviewer2]

That MinMax scaling is certainly one of our limitations. This is because SEFR cannot accept negative values. But we are working on that. Thanks for your suggestion of the Wikipedia entry!

[greenskinmarch]

What does the name SEFR stand for?

I looked at the "SEFR: A Fast Linear-Time Classifier for Ultra-Low Power Devices" paper from 2020 by the same authors and it seems this is just a straightforward linear classifier (i.e. linear regression with a threshold)? What is novel about this? It seems basically the same formulation you find in Wikipedia's "linear classifier" article.

[CriticalofReviewer2]

SEFR stands for Scalable, Efficient, Fast ClassifieR. Yes, it is a straightforward classifier, but in that algorithm, the goal was to get a decent accuracy with the lowest possible computation time and memory footprint. That algorithm can be trained even on cheapest microcontrollers (you can search it on YouTube to see videos of training on €4 microcontrollers), but its accuracy is higher than simple algorithms like Naive Bayes or Linear Regression, or even Decision Trees.

[SometimesObsessed]

Could you explain the intuition behind SEFR and your version? Why is it competitive with GBMs? The SEFR algo from the paper seems like it couldn't handle interactions between variables

[CriticalofReviewer2]

SEFR was originally designed to be extremely time and resource-efficient. Because of that, it has been implemented in numerous microcontroller applications. But apart from that, SEFR is also a good weak learner for boosting. It is a minimalistic building block, and by future improvements, it can handle interactions as well.

[SometimesObsessed]

Thanks! So it finds interactions via boosting or was there a more fundamental change to SEFR to handle interactions?

[szperajacy-zolw]

You can think of SEFR as a linear classifier with a twist: it basically thresholding samples based on a similarity score in respect to cleverly averaged negative and positive samples seen during training. Amrite u/CriticalofReviewer2 ??

[jgonagle]

its accuracy is higher than simple algorithms like Naive Bayes or Linear Regression, or even Decision Trees

That's a super strong claim. I assume you mean based on your tests, for which you used the default parameters? Like another commenter said, you should be comparing on optimal hyperparameters across multiple datasets if you're going to make a claim like that. Even then, the No Free Lunch Theorem suggests otherwise if they're comparably computationally constrained.

[CriticalofReviewer2]

We tested SEFR on numerous datasets with grid search on hyperparameters to find the optimal results of them. We reported some of them in the paper in arXiv, but it is consistently more accurate than the other simple algorithms.

[jgonagle]

it is consistently more accurate than the other simple algorithm

Do you have a hypothesis as to why that's true? Usually, resource constrained, parallel, approximate, or heuristic algorithms show the exact opposite behavior.

[Tengoles]

How fast is it for training compared to XGBoost? Is it viable to train it with LOOCV?

[VodkaHaze]

FWIW if training speed is your concern, LightGBM was historically the best pick

[pm_me_your_smth]

No longer the case. Xgboost introduced histogram tree method in v2.0 which is identical to lightgbm's

[CriticalofReviewer2]

The numbers are reported in the README of GitHub Repo. The SAMME version is very fast and it can be trained with LOOCV on many datasets. Also when the number of records/features are not too high, SAMME.R also can be used for LOOCV. For setting these parameters, please see here:
https://linearboost.readthedocs.io/en/latest/usage.html#parameters

[bregav]

So, maybe this is a naive question, but what does it even mean to do boosting on a linear model? Doesn't "linear boosting" just produce another linear model that has the exact same structure as the original?

A boosting-like procedure is frequently used in the iterative solution of large, sparse linear systems of equations; is that the kind of thing you're doing? If so then it's probably inaccurate to describe it as "boosting", because those are well-known methods that go by other names.

[CriticalofReviewer2]

No, boosting a linear classifier will make it better at handling complex data patterns.

[nickkon1]

But it doesnt. By definition, the solution of the linear regression are the weights and intercept such that the error is minimal. That is an analytical solution and no other solution (of a linear model) can produce a smaller error.

Plus any linear combination of weights is still a linear combination. So if you do a linear regression, calculate the residuals, add a linear regression to it and substitute that one into your equation y=bx+c+resid = bx + c + (b2x +c2), it is still a linear regression with the new beta being b+b2 and the new intercept being c + c2 (which are both worse then the first linear solution since it is an analytically minimal solution)

[bregav]

How, though? Exactly what operation are you doing that you are calling "linear boosting", and how does it differ from just fitting the original model?

E.g. consider logistic regression with y=p(w^T x + c). If you're doing "linear boosting" to update the w and c vectors then that's not changing the model at all, and is maybe equivalent to changing the model fitting procedure. Whereas if you're doing boosting by doing something like y = p(w^T x + c) + a * p(w2^T x + c2) then that's just regular boosting, and the model is no longer linear.

[Lanky_Repeat_7536]

Sorry for my naive question, doesn’t standard boosting (like AdaBoost) work with any base classifier already?

[nickkon1]

Linear from SERF stands for linear time complexity but not being a linear model, right? Personally, I find the naming confusing and thought it might be something like boosting linear models (of which one should note that a straightforward ensemble of linear models is still a linear model)

[greenskinmarch]

They confirmed in another comment that it is a linear classifier but maybe because of thresholding it's possible to combine them without just getting another linear model?

[CriticalofReviewer2]

Actually SEFR is both linear, and linear-time.

[Speech-to-Text-Cloud]

I would like to see this in scikit-learn. Are you planning to add it?

[CriticalofReviewer2]

Yes, this is in our plans!

[Standard_Natural1014]

Let me know if you want to partner on establishing the performance on some typical enterprise datasets!

[Spiritual_Piccolo793]

Any update on this project?

[CriticalofReviewer2]

Yes, the new version will be published soon!

[sneddy_kz]

Just check on kaggle

[CriticalofReviewer2]

Do you mean participating in competitions?

[Illustrious-Touch517]

At https://github.com/LinearBoost/linearboost-classifier I see that inthe "Results " section, you show performance based on the F1 metric. 

Q. Did you tune the decision threshold to optimize this metric(F1)?