Joint mode estimation in multi-label classification by chaining
Krzysztof Dembczyński, Willem Waegeman, Eyke Hüllermeier · Ghent University Academic Bibliography (Ghent University) · 2011
Many recently proposed algorithms in multi-label classification are believed to outperform their baseline competitors by exploiting structure and dependencies in the label space.However, most of these algorithms are presented in a purely application-driven manner, despite being intuitively appealing and showing strong performance in empirical studies.In this article we study one of these methods in detail, namely classifier chains, thereby helping to gain a better understanding of this approach.As a main result, we clarify that the original chaining method intends to predict the joint mode of the conditional distribution of label vectors in an approximate manner.Since exact inference is known to be intractable in general, this is of course a reasonable strategy.However, as a result of a theoretical regret analysis, we conclude that the existing greedy algorithm can perform quite poorly in terms of subset 0/1 loss.Therefore, we present an enhanced inference procedure for which the worst-case regret can be upper-bounded far more tightly.Finally, we discuss connections with related frameworks, such as conditional random fields and structured support vector machines, and we present experimental results confirming the validity of our theoretical findings.