d Multi-Label Boosting FCSM Nov 2013 1 

cting Multiple Responses with Boosting and Trees 

Ping Li1,2 and John Abowd2

Department of Statistics & Biostatistics 

Department of Computer Science 

Rutgers University (1) 

and 

Department of Statistical Science 

Cornell University (2) 

November 4, 2013 
d Multi-Label Boosting FCSM Nov 2013 2 

Motivation: Multi-Label Learning 

nal classification methods only deal with a single response (label) for 

ample. For example, handwritten digit recognition (0, 1, 2, ..., 9). 

y practical problems, however, one example may involve multiple 

ses (labels). In scene classification, an image might be both 

ain” and “Beach”. In Census survey forms, one can choose to declare 

 races, for example, both “American Indian” and “White”. 

bel learning is more challenging. Our working progress demonstrates 

 very promising to use boosting and trees for this type of problems. 
d Multi-Label Boosting FCSM Nov 2013 3 

History and Progress 

oost (Fridman et. al.,2000) is a well-known work on boosting in 

s. It is also known that the original version had numerical problem. 

Fridman, 2001) avoided the numerical problem by using only the 

er information to build the trees (the base learner for boosting). The 

m is extremely popular in industry. 

ART, ABC-LogitBoost (Ping Li, 2009, 2010) substantially improved 

and logitboost by writing the traditional derivatives of logistic regression 

erent way, for the task of multi-class (not multi-label) classification. 

 LogitBoost (Ping Li, 2010) derived the new tree-split criterion for 

st and fully solved the numerical issue. (Robust) Logitboost is often 

ccurate than MART due to the use of second-order information. 

a is to extend multi-class boosting algorithms to multi-label settings, 

ssentially the same (logistic regression) framework. 
d Multi-Label Boosting FCSM Nov 2013 4 

e-Based Boosting Algorithms Are Popular in Industry? 

p easily to large datasets. 

d to clean / transform / normalized / kernelize the data. 

rameters and parameter tuning is simple. 
d Multi-Label Boosting FCSM Nov 2013

5

What is Classification?

e: USPS Handwritten Zipcode Recognition

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

2 4 6 8 10 12 14 16

2468

10121416

Teach the machine to automatically recognize the 10 digits.
d Multi-Label Boosting FCSM Nov 2013 6 

Multi-Class Classification 

ning data set 

N 

yi, Xi} Xi ∈ Rp, yi ∈ {0, 1, 2, ..., K − 1} i=1 , 

o learn a function to predict the class label yi from Xi. 

: binary classification : multi-class classification 

tant practical problems can be cast as (multi-class) classification. 

e, Li, Burges, and Wu, NIPS 2007 

Ranking Using Multiple Classification and Gradient Boosting. 
d Multi-Label Boosting FCSM Nov 2013 7 

Logistic Regression for Classification 

he class probabilities 

p

ˆ

k = Pr {y = k|X} , k = 0, 1, ..., K − 1, 

K

 

−1

p

ˆ

k = 1, (only K − 1 degrees of freedom). 

k=0

n the class label according to 

y

ˆ|X = argmax pˆk

k
d Multi-Label Boosting FCSM Nov 2013 8 

Multinomial Logit Probability Model 

Fk e

pk = K−1 eFs s=0

= Fk(x) is the function to be learned from the data. 

ogistic regression: 

βT F(x) = x

to learn the coefficients β. 
 

d Multi-Label Boosting FCSM Nov 2013 9 

ditive modeling: 

M

F(x) = F(M)(x) = ρmh(x; am), 

m=1

a pre-specified function (e.g., trees). 

to learn the parameters ρm and am. 

Boost (Friedman et. al, 2000) and MART (Multiple Additive 

 Trees, Friedman 2001) adopted this model. 
d Multi-Label Boosting FCSM Nov 2013 10 

ning Logistic Regression by Maximum Likelihood 

o maximize the mutlinomial likelihood: Suppose 

yi = 

k, 

0

1

0 Lik ∝ p ... × 

pi,k × ... × p = i,

0 × i,K

−

1

pi,k

ntly, maximizing the log likelihood: 

log Lik ∝ log

pi,k

ntly, minimizing the negative log likelihood loss 

Li = 

− log

pi,k, (

yi = 

k) 
 

d Multi-Label Boosting FCSM Nov 2013 11 

The Negative Log-Likelihood Loss 

 N N K−1 L = Li = − ri,k log pi,k i=1 i=1 k=0

⎧⎨

1 if yi = k ri,k = ⎩ 0 otherwise 
d Multi-Label Boosting FCSM Nov 2013	 12 

asic Optimization Methods for Maximum Likelihood 

n’s Method 

e first and second derivatives of the loss function. 

thod in LogitBoost. 

nt Descent 

es the first order derivative of the loss function. 

————-

used a creative combination of gradient descent and Newton’s method. 
 

d Multi-Label Boosting FCSM Nov 2013 13 

Derivatives Used in LogitBoost and MART 

nction: 

N N K−1

L = Li = − ri,k log pi,k

i=1 i=1 k=0

erivative: 

∂Li

= − (ri,k − pi,k) ∂Fi,k

d derivative: 

∂2Li

∂F2 = pi,k (1 − pi,k).

i,k
 

 

�

� 

d Multi-Label Boosting FCSM Nov 2013	 14 

The Original LogitBoost Algorithm 

1 

 pi,k = K , k = 0 to K − 1, i = 1 to N

1 to M Do 

= 0 to K − 1, Do 

ri,k−pi,k 

i,k = pi,k (1 − pi,k), zi,k = . pi,k(1−pi,k)

t the function fi,k by a weighted least-square of zi,k to xi with weights wi,k. 

K−1 K−1 

i,k = Fi,k+ν fi,k − 1 K K k=0 fi,k

= exp(Fi,k)/ K−1 exp(Fi,s), k = 0 to K − 1, i = 1 to N s=0
 

 

 

 

d Multi-Label Boosting FCSM Nov 2013 15 

The Original MART Algorithm 

1 

 pi,k = K , k = 0 to K − 1, i = 1 to N

1 to M Do 

= 0 to K − 1 Do 

k,m}J = J-terminal node regression tree from {ri,k − pi,k, xi}N j=1 i=1

K− ri,k−pi,k 1 xi∈Rj,k,m 

m = K

x (1−pi,k)pi,k i∈Rj,k,m

J 

= Fi,k + ν β j=1 j,k,m1xi∈Rj,k,m

= exp(Fi,k)/ K−1 exp(Fi,s), k = 0 to K − 1, i = 1 to N s=0
� �

d Multi-Label Boosting FCSM Nov 2013	 16 

The Numerical Issue in LoigtBoost 

ri,k−pi,k 

i,k = pi,k (1 − pi,k), zi,k = . pi,k(1−pi,k)

t the function fi,k by a weighted least-square of zi,k to xi with weights wi,k. 

K−1 K−1 

i,k = Fi,k + ν fi,k − 1 K K k=0 fi,k

bility issue”: 

ri,k−pi,k 

s close to 0 or 1, zi,k = zi,k =

may approach infinity. pi,k(1−pi,k)

gitBoost avoids this pointwise thresholding and is essentially free of 

roblems. 
 

 

 

 

 

 

 

 � 

d Multi-Label Boosting FCSM Nov 2013 17 

e-Splitting Using the Second-Order Information 

ues: xi, i = 1 to N. Assume x1 ≤ x2 ≤ ... ≤ xN . 

ues: wi, i = 1 to N. Response values: zi, i = 1 to N. 

e index s, 1 ≤ s < N, to maximize the gain of weighted SE: 

) =SET − (SEL + SER) 

N s N

= (zi − z ̄)2wi − (zi − z ̄L)2wi + (zi − z ̄R)2wi

i=1 i=1 i=s+1

N

i=1 i=1N ziwi s ziwi i=s+1 ziwi 

N , z ̄L = s , z ̄R = N . 

i=1 wi i=1 wi i=s+1 wi
 

 

 

 

 

 

 

 

 

 

d Multi-Label Boosting FCSM Nov 2013 18 

fication, we obtain 

 2 2 N N s 2 [ i=s+1 ziwi i=1 ziwi i=1 ziwi] 

= s + N − N

i=1 wi i=s+1 wi i=1 wi

 2 2 N N 

2 i=s+1 ri,k − pi,k i=1 

ri,k − pi,k 

ri,k − pi,k]

+ − .

N N

pi,k(1 − pi,k) i=s+1 pi,k(1 − pi,k) i=1 pi,k(1 − pi,k) 

ri,k−pi,k 

= pi,k(1 − pi,k), zi = . pi,k(1−pi,k)

ure is numerically stable. 
 

 

d Multi-Label Boosting FCSM Nov 2013 19 

used the first order information to construct the trees: 

1 s �2 1 N �2 

Gain(s) = s ri,k − pi,k + N − s ri,k − pi,k i=1 i=s+1

1 N �2 − N ri,k − pi,k . i=1

also be derived by letting weights wi,k = 1 and response 

− pi,k. 

used more information and could be more accurate in many datasets. 
 

 

 

 

d Multi-Label Boosting FCSM Nov 2013 20 

Robust LogitBoost 

1 

 pi,k = K , k = 0 to K − 1, i = 1 to N

1 to M Do 

= 0 to K − 1 Do 

k,m}J = J-terminal node regression tree from {ri,k − pi,k, xi}Ni=1, j=1

with weights pi,k(1 − pi,k). 

K− ri,k−pi,k 1 xi∈Rj,k,m 

m = K

x (1−pi,k)pi,k i∈Rj,k,m

J 

= Fi,k + ν j=1 βj,k,m1xi∈Rj,k,m

K−1 

exp(Fi,k)/ s=0 exp(Fi,s), k = 0 to K − 1, i = 1 to N 
d Multi-Label Boosting FCSM Nov 2013 21 

Experiments on Binary Classification 

 classification is even more interesting!) 

9990 training samples, 91701 test samples 

t was used in a competition. LibSVM was the winner. 

——– 

: 100000 training samples, 50000 test samples : 521012 training samples, 50000 test samples 

gest datasets from Bordes et al. JMLR 2005, 

 Classifiers with Online and Active Learning 
d Multi-Label Boosting FCSM Nov 2013 22 

IJCNN1 Test Errors 

2000 

800 600 400 200 000 Test: J = 20 

ν = 0.1 

MART 

LibSVM 

Robust LogitBoost 

0 5000 10000 

Iterations 
d Multi-Label Boosting FCSM Nov 2013 23 

Forest100k Test Errors 

5000 4500 4000 3500 3000 Test: J = 20 

ν = 0.1 

SVM 

MART 

Robust LogitBoost 

0 5000 10000 

Iterations 
d Multi-Label Boosting FCSM Nov 2013 24 

Forest521k Test Errors 

4000 3500 3000 2500 2000 

500 Test: J = 20 

ν = 0.1 

SVM 

Robust Logi

MART 

tBoost 

0 5000 10000 

Iterations 
d Multi-Label Boosting FCSM Nov 2013 25 

ABC-Boost for Multi-Class Classification 

ptive Base Class 

T = ABC-Boost + MART 

Boost = ABC-Boost + (Robust) LogitBoost 

he success of ABC-Boost is the use of “better” derivatives. 
 

 

d Multi-Label Boosting FCSM Nov 2013 26 

Review Components of Logistic Regression 

omial logit probability model: 

F K−1 k e

pk = , pk = 1 K−1

eFs s=0 k=0

= Fk(x) is the function to be learned from the data. 

o-zero constraint: 

K−1

Fk(x) = 0 

k=0

y used to obtain a unique solution (only K − 1 degrees of freedom). 
 

 

d Multi-Label Boosting FCSM Nov 2013 27 

m-to-zero constraint? 

Fi,k+C C Fi,k Fi,k e e e e

= = = pi,k. K−1 F K−1 K−1 e e i,s+C C eFi,s eFi,s s=0 s=0 s=0

bility, one should impose a constraint. 

K−1 

r choice is to assume Fi,k = const, equivalent to k=0

K−1

Fi,k = 0. 

k=0

assumption used in many papers including LogitBoost and MART. 
 

 

d Multi-Label Boosting FCSM Nov 2013 28 

ve log-Likelihood loss 

N N K−1

L = Li = − ri,k log pi,k

i=1 i=1 k=0

⎧ ⎨ K−1 1 if yi = k ri,k = ri,k = 1 ⎩ 0 otherwise k=0
d Multi-Label Boosting FCSM Nov 2013 29 

 used in LogitBoost and MART: 

∂Li

= 

−

(

ri,k

−

pi,k

) ∂Fi,k

∂

2

Li

= 

pi,k (1

−

pi,k

), ∂F

2

i,k

 be derived without imposing any constraints on 

Fk. 
 

 

 

d Multi-Label Boosting FCSM Nov 2013 30 

Derivatives Under Sum-to-zero Constraint 

nction: 

K−1

Li = − ri,k log pi,k

k=0

lity model and sum-to-zero constraint: 

F K−1 i,k e

pi,k = , Fi,k = 0 K−1

eFi,s s=0 k=0

s of generality, we assume k = 0 is the base class 

K−1 Fi,0 = − i=1 Fi,k
d Multi-Label Boosting FCSM Nov 2013 31 

tives: 

∂Li = (

ri,

0

−

pi,

0

)

−

(

ri,k

−

pi,k

), ∂Fi,k

∂

2

Li

= 

pi,

0(1

−

pi,

0) +

pi,k(1

−

pi,k) + 2

pi,

0

pi,k. ∂F

2

i,k

LogitBoost used: 

∂Li ∂

2

Li

= 

−

(

ri,k

−

pi,k

), = 

pi,k (1

−

pi,k

). ∂F

2 

Fi,k i,k
d Multi-Label Boosting FCSM Nov 2013 32 

Datasets 

vertype Total 581012 samples. 

asets were generated: Covertype290k, Covertype145k 

ker Original 25010 training samples and 1 million test samples. 

5kT1, Poker25kT2, Poker525k, Poker275k, Poker150k, Poker100k. 

Originally 60000 training samples and 10000 test samples. 

0k swapped the training with test samples. 

ariations of MNIST Original MNIST is a well-known easy 

m. (www.iro.umontreal.ca/

 ̃lisa/twiki/bin/view.cgi/Public/ 

hallowComparisonICML2007) created a variety of much more difficult 

s by adding various background (correlated) noise, background 

 rotations, etc. 

tter Total 20000 samples. 
d Multi-Label Boosting FCSM Nov 2013 33 

dataset 

K # training # test # features 

Covertype290k 7 290506 290506 54 

Covertype145k 7 145253 290506 54 

Poker525k 10 525010 500000 25 Poker275k 10 275010 500000 25 Poker150k 10 150010 500000 25 Poker100k 10 100010 500000 25 Poker25kT1 10 25010 500000 25 

Poker25kT2 10 25010 500000 25 

Mnist10k 10 10000 60000 784 M-Basic 10 12000 50000 784 

M-Rotate 10 12000 50000 784 

M-Image 10 12000 50000 784 

M-Rand 10 12000 50000 784 

M-RotImg 10 12000 50000 784 M-Noise1 10 10000 2000 784 M-Noise2 10 10000 2000 784 M-Noise3 10 10000 2000 784 M-Noise4 10 10000 2000 784 M-Noise5 10 10000 2000 784 M-Noise6 10 10000 2000 784 Letter15k 26 15000 5000 16 

Letter4k 26 4000 16000 16 

Letter2k 26 2000 18000 16 
d Multi-Label Boosting FCSM Nov 2013 34 

Summary of test mis-classification errors 

aset mart abc-mart logitboost abc-logitboost logistic regression # test 

vertype290k 11350 10454 10765 9727 80233 290506 vertype145k 15767 14665 14928 13986 80314 290506 

er525k 7061 2424 2704 1736 248892 500000 er275k 15404 3679 6533 2727 248892 500000 er150k 22289 12340 16163 5104 248892 500000 er100k 27871 21293 25715 13707 248892 500000 er25kT1 43575 34879 46789 37345 250110 500000 

er25kT2 42935 34326 46600 36731 249056 500000 

st10k 2815 2440 2381 2102 13950 60000 

Basic 2058 1843 1723 1602 10993 50000 Rotate 7674 6634 6813 5959 26584 50000 

mage 5821 4727 4703 4268 19353 50000 

Rand 6577 5300 5020 4725 18189 50000 RotImg 24912 23072 22962 22343 33216 50000 Noise1 305 245 267 234 935 2000 

Noise2 325 262 270 237 940 2000 

Noise3 310 264 277 238 954 2000 

Noise4 308 243 256 238 933 2000 

Noise5 294 244 242 227 867 2000 

Noise6 279 224 226 201 788 2000 

er15k 155 125 139 109 1130 5000 

er4k 1370 1149 1252 1055 3712 16000 er2k 2482 2220 2309 2034 4381 18000 
d Multi-Label Boosting FCSM Nov 2013 35 

Comparisons with SVM and Deep Learning 

M-Noise1 to M-Noise6 

SVM, Neural Nets, and Deep Learning are from 

ontreal.ca/

 ̃lisa/twiki/bin/view.cgi/Public/ 

lowComparisonICML2007 

2 3 4 5 6 

Degree of correlation 

1 2 3 4 5 

6 0 

10 40 

Degree of correlation 

Error rate (%) mart 

abc−mart abc−logit

logit 

−3 

BN−3 

SV

Mrbf 30 

20 
d Multi-Label Boosting FCSM Nov 2013 36 

Comparisons with SVM and Deep Learning 

M-Noise1 to M-Noise6 

18 

−3 

BN−3 

SV

Mrbf 

mart 

logit 

abc−mart 

abc−logit 

16 

Error rate (%) 14 

12 10 

2 3 4 5 6 1 2 3 4 5 6 

Degree of correlation Degree of correlation 
d Multi-Label Boosting FCSM Nov 2013 37 

ore Comparisons with SVM and Deep Learning 

M-Basic M-Rotate M-Image M-Rand M-RotImg 

BF 

3.05% 11.11% 22.61% 14.58% 55.18% 

OLY 

3.69% 15.42% 24.01% 16.62% 56.41% 

4.69% 18.11% 27.41% 20.04% 62.16% 

3.11% 10.30% 16.31% 

6.73% 47.39% 

3.46% 10.30% 23.00% 11.28% 51.93% 3.94% 14.69% 16.15% 9.80% 52.21% 

4.12% 15.35% 11.64% 13.15% 49.82% 

art 

3.69% 13.27% 9.45% 10.60% 46.14% 

ost 

3.45% 13.63% 9.41% 10.04% 45.92% 

gitboost 

3.20% 11.92% 8.54% 

9.45% 44.69% 
x 10 2.4 

Test mis−classification errors 2.2 2 1.8 1.6 1.4 1.2 

000 2000 3000 4000 5000 1000 2000 3000 4000 5000 

Boosting iterations Boosting iterations 

4 x 10 

Test mis−classification errors 4 3 

2 1 0 

000 2000 3000 4000 5000 1000 2000 3000 4000 5000 

Boosting iterations Boosting iterations 
d Multi-Label Boosting FCSM Nov 2013 39 

Extending Multi-Class to Multi-Label Learning 

 Learning: Suppose yi = k, 

0 1 0 Lik ∝ p ... i,0 × × pi,k × ... × p i,K−1 = pi,k

 Learning: Suppose yi ∈ Si = {0, k}, 

1 1 0 Lik ∝ p ... i,0 × × pi,k × ... × p i,K−1 = pi,0pi,k

ctually more than one ways to determine the weights. For example, 

ose the following loss function: 

⎧ 

N K−1 ⎨ 1/|Si| if yi ∈ Si 

i = − wi,k log pi,k , wi,k = ⎩ 0 otherwise 

i=1 k=0
d Multi-Label Boosting FCSM Nov 2013 40 

bining Multi-Label Model with Boosting and Trees 

d to modify the existing boosting algorithms (MART, LogitBoost, 

ART, ABC-LogitBoost) to incorporate the new models. 

h example, the algorithm will again output a vector of class 

ities. We need to a criterion to truncate the list to assign class labels. 

d a good evaluation criterion to assess the quality of multi-label 

g. 
d Multi-Label Boosting FCSM Nov 2013 41 

Evaluation Criteria 

model and boosting, we learn the set of class probabilities for each 

d sort them in descending order: 

pˆi,(0) ≥ 

pˆi,(1) ≥ ... ≥ 

pˆi,(K

−1)

r three criteria: 

ror: How many times the top-ranked label is not in the true labels. 

ge: How far one needs, on average, to go down the list of labels in 

 cover all the ground truth labels. 

on: A more comprehensive ranking measure borrowed from 

tion retrieval (IR) literature. 
d Multi-Label Boosting FCSM Nov 2013 42 

Experiments and Comparisons 

ented our method with MART (other implementations are forthcoming). 

ed our result with an existing publication on the same dataset. 

0.75 

0.7 0.5 

0.45 

Coverage

200 400 600 800 1000 1 200 400 600 800 1000 

Boosting iterations Boosting iterations 

 with boosting and trees (red curves) is substantially better than 

esults (dashed horizontal line). 

on is about 87% but the other paper did not report. 

0.65 

0.6 

0.55 
d Multi-Label Boosting FCSM Nov 2013 43 

Ongoing Work 

r (and others’) multi-label algorithms on Census data. 

ment with various multi-label probability models. 

ent (Robust) LogitBoost for multi-label learning ent ABC-MART and ABC-LogitBoost for multi-label learning 
d Multi-Label Boosting FCSM Nov 2013 44 

References 

 et. al., Mcrank: Learning to rank using multiple classification and 

t boosting, NIPS 2007 

, Adaptive base class boost for multi-class classification, 

811.1250, 2008 

, ABC-boost: adaptive base class boost for multi-class classification, 

009 

 Robust logitboost and adaptive base class (abc) logitboost, UAI 2010 

, Fast abc-boost for multi-class classification, arXiv:1006.5051, 2010 , Learning to Rank Using Robust LogitBoost, Yahoo! Learning to 

rand Challenge, 2010