Learning Kernels for variants of Normalized Cuts: Convex Relaxations and Applications

Area of Science:

• Machine Learning
• Computer Vision
• Data Science

Background:

• Normalized Cuts (NCuts) is a graph-based image segmentation technique.
• Learning optimal kernels is crucial for enhancing NCuts performance.
• Existing methods often rely on spectral relaxations, which can be computationally intensive.

Purpose of the Study:

• To propose a new algorithm for learning kernels tailored to NCuts objectives.
• To facilitate the design of effective affinity matrices for segmentation.
• To assess the importance of different feature types in discrimination tasks.

Main Methods:

• The algorithm learns kernel weights in the discrete setting, deferring relaxation.
• It reformulates the problem to allow for Semidefinite Programming (SDP) relaxation.
• The problem size is independent of training set size, depending only on the number of input kernels.

Main Results:

• The proposed method yields a model with strong optimality guarantees under certain conditions.
• The learned sub-kernel weights offer a complementary approach for Multiple Kernel Learning (MKL) methods.
• Experiments on Caltech101 and ADNI datasets demonstrate state-of-the-art competitive performance.

Conclusions:

• The discrete optimization approach with later relaxation is effective for learning NCuts kernels.
• The method provides an efficient and scalable solution for kernel learning in segmentation.
• The results highlight the potential of this approach for various computer vision and data analysis tasks.