Efficient max-margin multi-label classification with applications to zero-shot learning

Hariharan, Bharath; Vishwanathan, S.; Varma, Manik
July 2012
Machine Learning;Jul2012, Vol. 88 Issue 1/2, p127
Academic Journal
The goal in multi-label classification is to tag a data point with the subset of relevant labels from a pre-specified set. Given a set of L labels, a data point can be tagged with any of the 2 possible subsets. The main challenge therefore lies in optimising over this exponentially large label space subject to label correlations. Our objective, in this paper, is to design efficient algorithms for multi-label classification when the labels are densely correlated. In particular, we are interested in the zero-shot learning scenario where the label correlations on the training set might be significantly different from those on the test set. We propose a max-margin formulation where we model prior label correlations but do not incorporate pairwise label interaction terms in the prediction function. We show that the problem complexity can be reduced from exponential to linear while modelling dense pairwise prior label correlations. By incorporating relevant correlation priors we can handle mismatches between the training and test set statistics. Our proposed formulation generalises the effective 1-vs-All method and we provide a principled interpretation of the 1-vs-All technique. We develop efficient optimisation algorithms for our proposed formulation. We adapt the Sequential Minimal Optimisation (SMO) algorithm to multi-label classification and show that, with some book-keeping, we can reduce the training time from being super-quadratic to almost linear in the number of labels. Furthermore, by effectively re-utilizing the kernel cache and jointly optimising over all variables, we can be orders of magnitude faster than the competing state-of-the-art algorithms. We also design a specialised algorithm for linear kernels based on dual co-ordinate ascent with shrinkage that lets us effortlessly train on a million points with a hundred labels.


Related Articles

  • Borel resummation of the É›-expansion of the dynamical exponent z in model a of the Ï•4( O( n)) theory. Nalimov, M. Yu.; Sergeev, V. A.; Sladkoff, L. // Theoretical & Mathematical Physics;Apr2009, Vol. 159 Issue 1, p499 

    We perform the Borel resummation of the currently known terms of the É›-expansion up to order É› 4 of the dynamical exponent z in the critical-behavior model A. We obtain the large-order asymptotic approximation of the É›-expansion of the dynamical exponent and find a significant...

  • Foreword and Editorial. Haeng-kon Kim; Fiaidhi, Jinan // International Journal of Software Engineering & Its Applications;2014, Vol. 8 Issue 3, pvii 

    An introduction is presented in which the editors discuss various reports within the issue on topics including tag identification and tag collisions, the performance of algorithms used for image processing, and new approach for object evolution.

  • Collaboration and Gaming. Angelides, Marios; Agius, Harry // Multimedia Tools & Applications;Jan2013, Vol. 62 Issue 1, p139 

    An introduction is presented in which the guest editors discuss various reports within the issue on topics including the use of collaboration for multimedia resources tagging, web page partitioning, and the augmentation of games and gesture-based recognition into mobile phone interfaces.

  • Design, implementation and validation of AI-inspired information systems. Cuzzocrea, Alfredo // Journal of Intelligent Information Systems;Aug2015, Vol. 45 Issue 1, p1 

    An introduction to the journal is presented in which the editor discusses various reports within the issue on topics including consistent structuring of inconsistent knowledge, the design of distributed database systems, and a kernel information propagation tag clustering algorithm.

  • A Generalization of a Theorem of Liao. Xiong Dai; Zuo Zhou // Acta Mathematica Sinica;Feb2006, Vol. 22 Issue 1, p207 

    Let X be a metrizable space and let ϕ:ℝ × X → X be a continuous flow on X. For any given {φt}–invariant Borel probability measure, this paper presents a { ϕ t }–invariant Borel subset of X satisfying the requirements of the classical ergodic theorem...

  • The Uniform Convergence of a Sequence of Weighted Bounded Exponentially Convex Functions on Foundation Semigroups. Ali, Hoda A. // Kyungpook Mathematical Journal;2006, Vol. 46 Issue 3, p337 

    In the present paper we shall prove that on a foundation *-semigroup S with an identity and with a locally bounded Borel measurable weight function ω, the pointwise convergence and the uniform convergence of a sequence of ω-bounded exponentially convex functions on S which are also...

  • On the generalized nonlinear ultra-hyperbolic heat equation related to the spectrum. Kananthai, Amnuay; Nonlaopon, Kamsing // Computational & Applied Mathematics;2009, Vol. 28 Issue 2, p157 

    In this paper, we study the nonlinear equation of the form ∂;/∂t u(x, t) -c²◻k u(x, t) = f(x, t, u(x, t)) where ◻k is the ultra-hyperbolic operator iterated k-times, defined by ◻k = (∂²/∂x1² + ∂² ∂x2² + … +...

  • A Comparison of Alternative Approaches for Numerical Solutions of GI/PH/1 Queues. Kao, Edward P.C. // INFORMS Journal on Computing;Winter96, Vol. 8 Issue 1, p74 

    This paper compares alternative approaches for computing the R matrix of Neuts in numerical solutions of queues of GI/PH/1 type. We consider the relative merits of using two algorithms proposed recently by Latouche, the state reduction procedure proposed in this journal by Kao, and an approach...

  • The Design and Evaluation of Task Assignment Algorithms for GWAP-based Geospatial Tagging Systems. Chen, Ling-Jyh; Syu, Yu-Song; Chen, Hung-Chia; Lee, Wang-Chien // Mobile Networks & Applications;Jun2012, Vol. 17 Issue 3, p395 

    Geospatial tagging (geotagging) is an emerging and very promising application that can help users find a wide variety of location-specific information, and thereby facilitate the development of advanced location-based services. Conventional geotagging systems share some limitations, such as the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics