Timezone: »
In this paper we consider the problem of learning an n x n Kernel matrix from m similarity matrices under general convex loss. Past research have extensively studied the m =1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well known Mirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m^2 log n) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n x n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL, which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVM solver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.
Author Information
Achintya Kundu (Indian Institute of Science)
Vikram Mukunda Rao Tankasali (Google Deepmind)
Chiranjib Bhattacharyya (Indian Institute of Science)
Aharon Ben-Tal
More from the Same Authors
-
2015 Poster: Weighted Theta Functions and Embeddings with Applications to Max-Cut, Clustering and Summarization »
Fredrik D Johansson · Ankani Chattoraj · Chiranjib Bhattacharyya · Devdatt Dubhashi -
2015 Poster: Spectral Norm Regularization of Orthonormal Representations for Graph Transduction »
Rakesh Shivanna · Bibaswan K Chatterjee · Raman Sankaran · Chiranjib Bhattacharyya · Francis Bach -
2014 Poster: Learning on graphs using Orthonormal Representation is Statistically Consistent »
Rakesh Shivanna · Chiranjib Bhattacharyya -
2014 Poster: A provable SVD-based algorithm for learning topics in dominant admixture corpus »
Trapit Bansal · Chiranjib Bhattacharyya · Ravindran Kannan -
2012 Poster: The Lovasz $\theta$ function, SVMs and finding large dense subgraphs »
Vinay Jethava · Anders Martinsson · Chiranjib Bhattacharyya · Devdatt Dubhashi -
2009 Poster: On the Algorithmics and Applications of a Mixed-norm based Kernel Learning Formulation »
Saketha Nath Jagarlapudi · dinesh govindaraj · Raman S · Chiranjib Bhattacharyya · Aharon Ben-Tal · K. R. Ramakrishnan -
2007 Poster: Kernels on Attributed Pointsets with Applications »
Mehul Parsana · Sourangshu Bhattacharya · Chiranjib Bhattacharyya · K. R. Ramakrishnan -
2007 Poster: A Randomized Algorithm for Large Scale Support Vector Learning »
Krishnan S Kumar · Chiranjib Bhattacharyya · Ramesh Hariharan