Multi-label learning is an important problem which is ubiquitous in real world computer vision and machine learning applications, where one instance can be assigned to multiple classes simultaneously. In this thesis, we introduce the problem of multi-label learning with a variety of challenges such as class correlations and class imbalance, and provide an improvement of a recent algorithm. Among many algorithms, Baoyuan Wu et al. [AAAI, pp:2229–2236, 2016] recently formulate multi-label learning as a constrained submodular minimization, whose objective function encourages label consistency and smoothness via graph Laplacians and whose class cardinality bounds handles the class imbalance issue. Its convex relaxation is a convex quadratic programming problem, and can thus be solved effect...[ Read more ]

Multi-label learning is an important problem which is ubiquitous in real world computer vision and machine learning applications, where one instance can be assigned to multiple classes simultaneously. In this thesis, we introduce the problem of multi-label learning with a variety of challenges such as class correlations and class imbalance, and provide an improvement of a recent algorithm. Among many algorithms, Baoyuan Wu et al. [AAAI, pp:2229–2236, 2016] recently formulate multi-label learning as a constrained submodular minimization, whose objective function encourages label consistency and smoothness via graph Laplacians and whose class cardinality bounds handles the class imbalance issue. Its convex relaxation is a convex quadratic programming problem, and can thus be solved effectively by the alternative direction method of multipliers (ADMM). However, in practice such a convex approach leads to degenerated prediction where all entries of predicted values are pushed to positive or negative simultaneously. To overcome this issue, we propose new linear constraints such that predictions will be orthogonal to constant vectors to eliminate degenerated predictions. Moreover, we replace uniform graph Laplacian by class-specific one to make label smoothness more accurate, and further improve class cardinality bounds by making class imbalance bounds adaptive to each instance and introducing new structured bounds via independent component analysis. Although the new optimization problem becomes nonconvex, we find a heuristic iterative algorithm inspired by ADMM effective in practice. The experiments over three multi-label classification datasets (yeast, emotions and scene) show that the proposed method with new structured bounds effectively reduces the degenerated cases and improves robustness with respect to parameters of model. On the other hand, class-specific graph Laplacian does not improve the performance, and the non-convexity in the optimization problem may cause failure of algorithmic convergence that needs future investigation.