Constrained Submodular Minimization for Missing Labels and Class Imbalance in Multi-label Learning

Authors

  • Baoyuan Wu King Abdullah University of Science and Technology (KAUST)
  • Siwei Lyu State University of New York at Albany
  • Bernard Ghanem King Abdullah University of Science and Technology (KAUST)

DOI:

https://doi.org/10.1609/aaai.v30i1.10186

Keywords:

multi-label, missing labels, class-imbalance, constrained submodular minimization

Abstract

In multi-label learning, there are two main challenges: missing labels and class imbalance (CIB). The former assumes that only a partial set of labels are provided for each training instance while other labels are missing. CIB is observed from two perspectives: first, the number of negative labels of each instance is much larger than its positive labels; second, the rate of positive instances (i.e. the number of positive instances divided by the total number of instances) of different classes are significantly different. Both missing labels and CIB lead to significant performance degradation. In this work, we propose a new method to handle these two challenges simultaneously. We formulate the problem as a constrained submodular minimization that is composed of a submodular objective function that encourages label consistency and smoothness, as well as, class cardinality bound constraints to handle class imbalance. We further present a convex approximation based on the Lovasz extension of submodular functions, leading to a linear program, which can be efficiently solved by the alternative direction method of multipliers (ADMM). Experimental results on several benchmark datasets demonstrate the improved performance of our method over several state-of-the-art methods.

Downloads

Published

2016-03-02

How to Cite

Wu, B., Lyu, S., & Ghanem, B. (2016). Constrained Submodular Minimization for Missing Labels and Class Imbalance in Multi-label Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10186

Issue

Section

Technical Papers: Machine Learning Methods