Xgboost multiple class predictive performance beats one versus rest

Question

I have an NLP task I'm tackling with xgboost (R implementation).

Before describing my doubt I'll give you some background:

I have a corpus of documents for which I did topic discovery, using a term x term matrix clustering approach. For each document, I get a topic score computed using the terms in the document (with a TfIdf score). Then for each document, I pick up the topic with the highest score.

The following step is to create a model that given the term x document score matrix and the best topic per document, predicts the best topic.

I tried two different approaches:

• a multiple class model, where a topic is associated with each document;
• a one versus rest series of models, one per topic, where each document is labeled as belonging or not to a topic.

Here are the results of the two approaches, using AUC:

    i                 topic    single     multi
1   1             Topic.nv1 0.9564445 0.9880821
2   2  Topic.nv10_Topic.wv9 0.9848492 0.9969546
3   3            Topic.nv11 0.9174293 0.9741100
4   4 Topic.nv12_Topic.wv11 0.9874073 0.9967725
5   5 Topic.nv13_Topic.wv10 0.9509909 0.9916768
6   6 Topic.nv14_Topic.wv12 0.9864622 0.9959161
7   7            Topic.nv15 0.7333333 0.9333333
8   8   Topic.nv2_Topic.wv3 0.9590279 0.9877953
9   9   Topic.nv3_Topic.wv5 0.9448966 0.9879057
10 10   Topic.nv4_Topic.wv2 0.9521490 0.9908656
11 11   Topic.nv5_Topic.wv6 0.9761665 0.9946294
12 12             Topic.nv6 0.9439377 0.9889028
13 13   Topic.nv7_Topic.wv4 0.9656248 0.9926163
14 14             Topic.nv8 0.9673726 0.9944970
15 15   Topic.nv9_Topic.wv8 0.9716538 0.9929586
16 16             Topic.wv1 0.9610704 0.9925414
17 17             Topic.wv7 0.9765398 0.9904255

It is visible that the multiclass approach systematically outperforms the one vs rest one. NB: These are training set performances.

Is there a clear theoretical reason for this?

Answer 1

Multiclass models in XGBoost consist of n_classes separate forests, one for each one-vs-rest binary problem. At each iteration, an extra tree is added to each forest. But it isn't actually a one-vs-rest approach (as I thought in the first version of this answer), because these trees are built to minimize a single loss function, the cross-entropy of the softmax probabilities. https://discuss.xgboost.ai/t/multiclassification-training-process/29
https://github.com/dmlc/xgboost/issues/806
https://github.com/dmlc/xgboost/issues/3655

In general, the one-vs-rest models are very good at identifying the single class, whereas the multiclass model has to balance performance on all of them. More specifically, I think that the softmax may be responsible for the phenomenon you're displaying. (I'm still thinking about it, but I thought I should post the above for now.)

Suppose one of your documents is reasonably likely to be in either of two topics: the probability scores given by the forests are 0.9, 0.85, then <0.1 in all the rest. In your topic-1 model, you make a fairly confident judgement that this document is of topic 1 (score of 0.9). But in the multiclass ensemble, you see things as much more uncertain; maybe the model applies softmax, so that the probability of topic 1 is only ~0.5.

More extreme, suppose the individual topic model scores are all 0.9. Now the multiclass ensemble applies softmax and produces equal 1/17 probabilities for each topic!

In the other direction, suppose one of your documents is judged unlikely to fit any of the topics: all the individual topic model probability scores are 0.01. In the multiclass ensemble, that gets scaled up to 1/17 (OK, 17 topics makes this a harder sell).

---

Hrm, except how likely is it to get the 0.9 and 0.85, since a training sample in one of these two topics will be pushed toward 0 by the other model... ? Especially when your scores are fairly high, so it's not like the models have huge blind spots.
(This part still causes a problem with the correct understanding of how XGBoost works; the log-loss of the softmax probabilities still penalizes being confident about belonging to two different classes...)