Gal Chechik, Varun Sharma, Uri Shalit, Samy Bengio.
Year: 2010, Volume: 11, Issue: 36, Pages: 1109−1135
Learning a measure of similarity between pairs of objects is an
important generic problem in machine learning. It is particularly
useful in large scale applications like searching for an image that
is similar to a given image or finding videos that are relevant to a
given video. In these tasks, users look for objects that are not
only visually similar but also semantically related to a given
object. Unfortunately, the approaches that exist today for learning
such semantic similarity do not scale to large data sets. This is
both because typically their CPU and storage requirements grow
quadratically with the sample size, and because many methods impose
complex positivity constraints on the space of learned similarity
The current paper presents OASIS, an Online Algorithm for Scalable Image Similarity learning that learns a bilinear similarity measure over sparse representations. OASIS is an online dual approach using the passive-aggressive family of learning algorithms with a large margin criterion and an efficient hinge loss cost. Our experiments show that OASIS is both fast and accurate at a wide range of scales: for a data set with thousands of images, it achieves better results than existing state-of-the-art methods, while being an order of magnitude faster. For large, web scale, data sets, OASIS can be trained on more than two million images from 150K text queries within 3 days on a single CPU. On this large scale data set, human evaluations showed that 35% of the ten nearest neighbors of a given test image, as found by OASIS, were semantically relevant to that image. This suggests that query independent similarity could be accurately learned even for large scale data sets that could not be handled before.