Large Scale Online Learning of Image Similarity Through Ranking
Gal Chechik, Varun Sharma, Uri Shalit, Samy Bengio.
Year: 2010, Volume: 11, Issue: 36, Pages: 1109−1135
Abstract
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
functions.
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.