Kernelized Sorting

Object matching is a fundamental operation in data analysis. It typically requires the definition of a similarity measure between the classes of objects to be matched. Instead, we develop an approach which is able to perform matching by requiring a similarity measure only within each of the classes. This is achieved by maximizing the dependency between matched pairs of observations by means of the Hilbert Schmidt Independence Criterion. This problem can be cast as one of maximizing a quadratic assignment problem with special structure and we present a simple algorithm for finding a locally optimal solution.

Codes

Written in Python [Download].

(Some) Applications

Layout of 284 images into a "NIPS 2008" letter grid using Kernelized Sorting.
Images are laid out in the letter grid according to their color grading.

Layout of 320 images into a 2D grid of size 16 by 20 using Kernelized Sorting.
Images are laid out in the 2D grid according to their color grading.

Image matching as obtained by Kernelized Sorting.
The images are cut vertically into two equal halves and Kernelized Sorting is used to
pair up image halves that originate form the same images. 140 pairs out of 320 are correctly matched.
This is quite respectable given that chance level would be 1 correct pair.


Publications

Novi Quadrianto, Le Song, Alex J. Smola.
Kernelized Sorting. Advances in Neural Information Processing Systems 21, pp. 1289-1296, 2009.

Novi Quadrianto, Alex J. Smola, Le Song, Tinne Tuytelaars.
Kernelized Sorting. IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 32(10), pp. 1809-1821, 2010.