"Learning Kernels for variants of Normalized Cuts: Convex Relaxations and Applications"
Lopamudra Mukherjee, Vikas Singh, Jiming Peng, Chris Hinrichs,
This research was supported in part by NIH grants R21-AG034315
(Singh) and R01-AG021155 (Johnson). Hinrichs is funded via a
University of Wisconsin-Madison CIBM (Computation and Informatics
in Biology and Medicine) fellowship (National Library of Medicine
Award 5T15LM007359). Partial support for this research was also
provided by the University of Wisconsin-Madison UW ICTR through an
NIH Clinical and Translational Science Award (CTSA) 1UL1RR025011, a
Merit Review Grant from the Department of Veterans Affairs, the
Wisconsin Comprehensive Memory Program, and the Society for
Imaging Informatics in Medicine (SIIM).
We propose a new algorithm for learning kernels for
variants of the Normalized Cuts (NCuts) objective - i.e.,
given a set of training examples with known partitions, how
should a basis set of similarity functions be combined to
induce NCuts-favorable distributions. Such a procedure facilitates
design of good affinity matrices. It also helps assess the
importance of different feature types for discrimination.
Rather than formulating the learning problem in
terms of the spectral relaxation, the alternative we pursue
here is to work in the original discrete setting (i.e., the
relaxation occurs much later). We show that this strategy is
useful - while the initial specification seems rather difficult to
optimize efficiently, a set of manipulations reveal a related
model which permits a nice SDP relaxation. A salient feature
of our model is that the eventual problem size is only a
function of the number of input kernels and not the training
set size. This relaxation also allows strong optimality
guarantees, if certain conditions are satisfied. We show that the
sub-kernel weights obtained provide a complementary approach
for MKL based methods. Our experiments on Caltech101 and
ADNI (a brain imaging dataset) show that the
quality of solutions is competitive with the state-of-the-art.
The Matlab code used in our experiments can be downloaded here. Please contact me at
firstname.lastname@example.org for the password. All rights reserved.