An Efficient Gradient-based Approach to Optimizing Average Precision Through Maximal Figure-of-Merit Learning

• Published in: Journal of signal processing systems 2014-03, Vol.74 (3), p.285-295
• Main Authors: Kim, Ilseo, Lee, Chin-Hui
• Format: Article
• Language: English
• Subjects: Circuits and Systems; Computer Imaging; Electrical Engineering; Engineering; Image Processing and Computer Vision; Pattern Recognition; Pattern Recognition and Graphics; Signal,Image and Speech Processing; Vision
• ISSN: 1939-8018; 1939-8115
• DOI: 10.1007/s11265-013-0748-0

We propose an efficient algorithm that directly optimizes a ranking performance measure, with a focus on class average precision (AP). Instead of using pair-wise ranking approximation in defining a loss function by conventional approaches, we use an efficient gradient-based approach that approximates a discrete ranking performance measure. In particular, AP is considered as a staircase function with respect to each individual sample score after rank ordering is applied to all samples. Then, a combination of sigmoid functions is applied to approximate the staircase AP function as a continuous and differntiable function of the model parameters used to compute the sample scores. Compared to the use of pair-wise rankings, the proposed approach substantially reduces the computational complexity to a manageable level when estimating model parameters with a gradient descent algorithm. In terms of explicitly optimizing a target performance metric, the proposed algorithm can be considered as an extension of maximal figure-of-merit (MFoM) learning to optimization of a ranking performance measure. Our experiments on two challenging image-retrieval datasets showcased the usefulness of the proposed framework in both improving AP and achieving learning efficiency.