xgboost very slow for classification with many classes

[lesshaste]

Environment info

Ubuntu

Compiler:

gcc

Package used (python/R/jvm/C++):

python

xgboost version used:

0.6

If installing from source, please provide

1. The commit hash (git rev-parse HEAD)

git rev-parse HEAD
3dcf966

2. Logs will be helpful (If logs are large, please upload as attachment).

If you are using python package, please provide

1. The python version and distribution

Python 3.5.2

2. The command to install xgboost if you are not installing from source

Installed from source

Steps to reproduce

Run the following self contained code which also creates fake data for classification with 120 classes:

#!/usr/bin/python3

from sklearn.datasets import make_classification
from xgboost import XGBClassifier
from sklearn.ensemble import RandomForestClassifier
from time import time

(trainX, trainY) = make_classification(n_informative=10, n_redundant=0, n_samples=50000, n_classes=120)

print("Shape of trainX and trainY", trainX.shape, trainY.shape)
t0 = time()
rf = RandomForestClassifier(n_estimators=50, n_jobs=-1)
rf.fit(trainX, trainY)
print("Time elapsed by RandomForestClassifier is: ", time()-t0)
t0 = time()
xgbrf = XGBClassifier(n_estimators=50, n_jobs=-1,verbose=True)
xgbrf.fit(trainX, trainY)
print("Time elapsed by XGBClassifier is: ", time()-t0)

What have you tried?

The RandomForestClassifier takes about 15 seconds but xgboost never terminates at all for me even after 10 minutes.

[marugari]

XGBoost uses regression trees, so build 120 (=num_class) trees per iteration.

That issue will be helpfull.
microsoft/LightGBM#524

[lesshaste]

@marugari

Does this mean xgboost will always be slow for multi class classification?

You accidentally linked back to this issue in your comment (2926). Did you mean to link to another one?

[marugari]

@lesshaste Sorry, I fix the link.

[khotilov]

There is an inefficiently in prediction caching that results in nclass^2 complexity #1689 (comment)
I didn't yet get to fixing it, as I didn't really have any practical need for so many classes, but I will.

[lesshaste]

That would be awesome! Thank you.

[mfeurer]

This recent paper might be another potential solution to increase multiclass speed.