The End Of Knowledge - Vault 5/36 - CVPR - 2018 - Efficient Optimization for Rank-Based Loss Functions

graph LR classDef ranking fill:#f9d4d4, font-weight:bold, font-size:14px classDef pipeline fill:#d4f9d4, font-weight:bold, font-size:14px classDef evaluation fill:#d4d4f9, font-weight:bold, font-size:14px classDef learning fill:#f9f9d4, font-weight:bold, font-size:14px classDef optimization fill:#f9d4f9, font-weight:bold, font-size:14px classDef quicksort fill:#d4f9f9, font-weight:bold, font-size:14px classDef results fill:#f9d4d4, font-weight:bold, font-size:14px A[Efficient Optimization for
Rank-Based Loss Functions] --> B[Rank images by
query relevance 1] A --> C[Standard ranking process 2] A --> D[Evaluate with AP,
NDCG measures 3] A --> E[Learn with differentiable
losses like zero-one 4] A --> F[Rank-based loss better,
computationally expensive 5] F --> G[Assign scores, determine
rankings, solve optimization 6] G --> H[Most violating ranking
for efficient gradient 7] A --> I[QS suitable losses
for efficient optimization 8] I --> J[Loss depends on
interleaving rank 9] J --> K[AP, NDCG losses
are QS suitable 10] I --> L[Loss decomposable onto
negative samples 11] I --> M[Loss depends only
on interleaving pattern 12] I --> N[Multiple most violating
rankings exist 13] I --> O[Constraints on ranks
based on scores 14] I --> P[Induce ordering, find
optimal interleaving 15] A --> Q[Baseline: sort positives,
negatives, find interleaving 16] A --> R[Quicksort: sort positives,
assign negatives recursively 17] R --> S[Same-rank negatives get
same rank free 18] R --> T[Complexity: p log p
+ n log p 19] Q --> U[Worse complexity than
quicksort: n log n + pn 20] A --> V[AP/NDCG loss improves
Pascal action classification 21] A --> W[Quicksort scales well
vs baseline 22] A --> X[AP loss improves
Pascal VOC detection >7% 23] A --> Y[AP/NDCG loss improves
CIFAR-10, quicksort faster 24] A --> Z[Rank-based loss good
for ranking performance 25] Z --> AA[But expensive to
optimize generally 26] Z --> AB[QS suitable losses
enable efficient optimization 27] AB --> AC[Performance boost without
computation time increase 28] A --> AD[Other scores like
F-score unexplored 29] A --> AE[Assumes binary labels,
pairwise prefs unconsidered 30] class A,B,C ranking class D,E,F,G,H,Z,AA optimization class I,J,K,L,M,N,O,P evaluation class Q,R,S,T,U quicksort class V,W,X,Y,AC results class AD,AE learning

Resume:

1.- Ranking problem: Given images and a query, rank images by relevance to the query

2.- Standard ranking pipeline: Collect data, learn ranking model, assign scores, sort samples

3.- Evaluating ranking models: Use ranking measures like Average Precision (AP) or Normalized Discounted Cumulative Gain (NDCG)

4.- Learning model parameters: Popular to use differentiable loss functions like zero-one loss

5.- Optimizing rank-based loss functions directly can give better performance but is computationally expensive

6.- Expensive gradient computation procedure: Assign scores, determine candidate rankings, solve optimization problem

7.- Most violating ranking: Optimal solution to the optimization problem, needed for efficient gradient computation

8.- QS suitable loss functions: Rank-based loss functions amenable to efficient optimization

9.- Interleaving rank: Number of positive samples preceding a negative sample

10.- AP loss and NDCG loss are QS suitable

11.- Negative decomposability property: Loss additively decomposable onto negative samples

12.- Interleaving dependence property: Loss depends only on interleaving pattern of negatives and positives

13.- Multiple possible most violating rankings exist

14.- Partial ordering structure: Constraints on interleaving ranks based on scores

15.- Gradient computation steps: Induce partial ordering, find optimal interleaving pattern

16.- Baseline algorithm: Completely sort positives (p log p) and negatives (n log n), find interleaving (np)

17.- Quicksort-flavored algorithm: Sort positives (p log p), assign negatives optimal rank recursively (n log p)

18.- Negative samples between those with same rank get same rank for free

19.- Quicksort-flavored complexity: p log p + n log p + p log n ~ n log p

20.- Baseline complexity: n log n + pn, worse than quicksort-flavored

21.- Empirical performance on Pascal action classification: AP/NDCG loss improves performance, quicksort time comparable to zero-one loss

22.- Good scaling of quicksort algorithm compared to baseline as number of samples increases

23.- Weakly supervised object detection on Pascal VOC: AP loss improves mean performance >7%

24.- Training deep model on CIFAR-10: AP/NDCG loss improves performance, quicksort faster than baseline

25.- Optimizing rank-based loss good for ranking model performance

26.- But expensive to optimize rank-based loss in general

27.- QS suitable rank-based losses enable efficient optimization

28.- Improvement in performance without additional computational time

29.- Applicability to other ranking scores like F-score or mean reciprocity rank not yet explored

30.- Approach assumes zero-one labeling ground truth, extension to pairwise preferences not considered

Knowledge Vault built byDavid Vivancos 2024