Report

Learning to Rank using High-Order Information Puneet K. 1Ecole 1 Dokania , A. 2 Behl , Centrale Paris and INRIA Saclay - France, Aim • • C. V. 2 Jawahar , M. Pawan 2IIIT 1 Kumar Hyderabad - India Results HOB-SVM • Incorporate High-order information • Optimizes Decomposable loss • Encoding high-order information (joint feature map): Optimizing Average Precision (Ranking) Incorporating High-Order Information Motivations and Challenges • High-Order Information For example, persons in the same image are likely to have same action Action inside the bounding box ? Context helps Problem Formulation: Given an image and a bounding box in the image, predict the action being performed in the bounding box. Dataset- PASCAL VOC 2011, 10 action classes, , 4846 images (2424 ‘trainval’ + 2422 ‘test’ images). Features: POSELET + GIST High-Order Information: “Persons in the same are likely to perform same action”. Connected bounding boxes belonging to the same image. • Results • Parameter Learning: High Order + Ranking -> No Method • Action Classification • Average Precision Optimization AP is the most commonly used evaluation metric AP loss depends on the ranking of the samples Optimizing 0-1 loss may lead to suboptimal AP • Ranking: Single Score Ranking ?? Sort difference of max-marginal scores to get ranking: Use Max-marginals AP = 1 Accuracy = 1 Max-marginals capture high-order information AP = 0.55 Accuracy = 1 • Optimization: Convex AP doesn’t decompose SVM Use dynamic graph cut for fast computation of max-marginals HOAP-SVM Notations • Samples: • Set of positive samples: • Ranking Matrix: • Labels: • Set of negative samples: • Loss function: • AP-SVM • Optimizes AP (measure of ranking) • No High-Order Information • Key Idea: Uses SSVM to encode ranking (joint score): • Parameter Learning • HOAP-SVM • Paired ttest: Sample scores similar to HOB-SVM (max-marginals) HOB-SVM better than SVM in 6 action classes HOB-SVM not better than AP-SVM HOAP-SVM better than SVM in 6 action classes HOAP-SVM better than AP-SVM in 4 actions classes Conclusions Parameter Learning • Ranking: Sort scores • Optimization Non Convex - > Difference of Convex -> CCCP Ranking: Sort scores, Optimization Convex Cutting plane -> Most violated constraint (greedy) -> O(|P||N|) HOB-SVM • Optimizes AP based loss • Incorporate high-order information • Encode ranking and high-order information (AP-SVM + HOB-SVM): Joint score similar to AP-SVM • AP-SVM Methods Loss Ranking Objective 0-1 High-Order Information No SVM Yes Convex AP-SVM AP Based No Yes Convex HOB-SVM Decomposable Yes Yes Convex HOAP-SVM AP Based Yes Yes Non-Convex (Diff of Convex) Code and Data: http://cvn.ecp.fr/projects/ranking-highorder/ Dynamic graph cut for fast upper bound