On Boosting, Tug of War, and Lexicographic Programming.
Shounak Datta, Sayak Nag, Swagatam Das · 2017
Despite the large amount of research effort dedicated to adapting boosting for imbalanced classification, boosting methods are yet to be satisfactorily immune to class imbalance, especially for multi-class problems, due to the long-standing reliance on expensive cost set tuning. We show that the assignment of weights to the component classifiers of a boosted ensemble can be thought of as a game of Tug of War between the classes in the margin space. We then demonstrate how this insight can be used to attain a good compromise between the rare and abundant classes without having to resort to cost set tuning, which has long been the norm for imbalanced classification. The solution is based on a lexicographic linear programming framework which requires two stages. Initially, class-specific component weight combinations are found so as to minimize a hinge loss individually for each of the classes. Subsequently, the final component weights are assigned so that the maximum deviation from the class-specific minimum loss values (obtained in the previous stage) is minimized. Hence, the proposal is not only restricted to two-class situations, but is also readily applicable to multi-class problems. We also derive the dual formulation corresponding to the proposed framework. Experiments conducted on artificial and real-world imbalanced datasets as well as challenging applications such as hyperspectral image classification and ImageNet classification establish the efficacy of the proposal.