Conocimiento Bóveda 5 /36 - CVPR 2018
Optimización Eficiente para Funciones de Pérdida Basadas en Rangos
Pritish Mohapatra, Michal Rolínek, C.V. Jawahar, Vladimir Kolmogorov, M. Pawan Kumar.
< Imagen del Resumen >

Gráfico de Conceptos & Resumen usando Claude 3 Opus | Chat GPT4o | Llama 3:

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["Optimización Eficiente para
Funciones de Pérdida Basadas en Rangos"] --> B["Clasificar imágenes por
relevancia de consulta 1"] A --> C["Proceso de clasificación estándar 2"] A --> D["Evaluar con medidas AP,
NDCG 3"] A --> E["Aprender con pérdidas diferenciables
como cero-uno 4"] A --> F["Pérdida basada en rango mejor,
computacionalmente costosa 5"] F --> G["Asignar puntuaciones, determinar
clasificaciones, resolver optimización 6"] G --> H["Clasificación más violatoria
para gradiente eficiente 7"] A --> I["Pérdidas adecuadas para QS
para optimización eficiente 8"] I --> J["Pérdida depende de
intercalación de rango 9"] J --> K["Pérdidas AP, NDCG
son adecuadas para QS 10"] I --> L["Pérdida descomponible en
muestras negativas 11"] I --> M["Pérdida depende solo
del patrón de intercalación 12"] I --> N["Existen múltiples clasificaciones
más violatorias 13"] I --> O["Restricciones en rangos
basadas en puntuaciones 14"] I --> P["Inducir orden, encontrar
intercalación óptima 15"] A --> Q["Base: ordenar positivos,
negativos, encontrar intercalación 16"] A --> R["Quicksort: ordenar positivos,
asignar negativos recursivamente 17"] R --> S["Negativos de mismo rango obtienen
mismo rango gratis 18"] R --> T["Complejidad: p log p
+ n log p 19"] Q --> U["Peor complejidad que
quicksort: n log n + pn 20"] A --> V["Pérdida AP/NDCG mejora
clasificación de acciones Pascal 21"] A --> W["Quicksort escala bien
vs base 22"] A --> X["Pérdida AP mejora
detección VOC Pascal >7% 23"] A --> Y["Pérdida AP/NDCG mejora
CIFAR-10, quicksort más rápido 24"] A --> Z["Pérdida basada en rango buena
para rendimiento de clasificación 25"] Z --> AA["Pero costosa de
optimizar generalmente 26"] Z --> AB["Pérdidas adecuadas para QS
permiten optimización eficiente 27"] AB --> AC["Impulso de rendimiento sin
aumento de tiempo de cálculo 28"] A --> AD["Otras puntuaciones como
F-score inexploradas 29"] A --> AE["Asume etiquetas binarias,
prefs por pares no consideradas 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

Resumen:

1.- Problema de clasificación: Dadas imágenes y una consulta, clasificar imágenes por relevancia a la consulta

2.- Proceso estándar de clasificación: Recoger datos, aprender modelo de clasificación, asignar puntuaciones, ordenar muestras

3.- Evaluación de modelos de clasificación: Usar medidas de clasificación como Precisión Promedio (AP) o Ganancia Acumulada Descontada Normalizada (NDCG)

4.- Aprendizaje de parámetros del modelo: Popular usar funciones de pérdida diferenciables como pérdida cero-uno

5.- Optimizar funciones de pérdida basadas en rangos directamente puede dar mejor rendimiento pero es computacionalmente costoso

6.- Procedimiento costoso de cálculo de gradiente: Asignar puntuaciones, determinar clasificaciones candidatas, resolver problema de optimización

7.- Clasificación más violatoria: Solución óptima al problema de optimización, necesaria para cálculo eficiente del gradiente

8.- Funciones de pérdida adecuadas para QS: Funciones de pérdida basadas en rangos propicias para optimización eficiente

9.- Rango de intercalación: Número de muestras positivas precediendo a una muestra negativa

10.- Pérdida AP y pérdida NDCG son adecuadas para QS

11.- Propiedad de descomposición negativa: Pérdida descomponible aditivamente en muestras negativas

12.- Propiedad de dependencia de intercalación: Pérdida depende solo del patrón de intercalación de negativos y positivos

13.- Existen múltiples clasificaciones más violatorias posibles

14.- Estructura de ordenamiento parcial: Restricciones en rangos de intercalación basadas en puntuaciones

15.- Pasos de cálculo de gradiente: Inducir ordenamiento parcial, encontrar patrón de intercalación óptimo

16.- Algoritmo base: Ordenar completamente positivos (p log p) y negativos (n log n), encontrar intercalación (np)

17.- Algoritmo con sabor a Quicksort: Ordenar positivos (p log p), asignar negativos rango óptimo recursivamente (n log p)

18.- Muestras negativas entre aquellas con mismo rango obtienen mismo rango gratis

19.- Complejidad con sabor a Quicksort: p log p + n log p + p log n ~ n log p

20.- Complejidad base: n log n + pn, peor que con sabor a Quicksort

21.- Rendimiento empírico en clasificación de acciones Pascal: Pérdida AP/NDCG mejora rendimiento, tiempo de Quicksort comparable a pérdida cero-uno

22.- Buena escalabilidad del algoritmo Quicksort comparado con base a medida que aumenta el número de muestras

23.- Detección de objetos débilmente supervisada en Pascal VOC: Pérdida AP mejora rendimiento medio >7%

24.- Entrenamiento de modelo profundo en CIFAR-10: Pérdida AP/NDCG mejora rendimiento, Quicksort más rápido que base

25.- Optimizar pérdida basada en rango buena para rendimiento del modelo de clasificación

26.- Pero costosa de optimizar pérdida basada en rango en general

27.- Pérdidas basadas en rango adecuadas para QS permiten optimización eficiente

28.- Mejora en rendimiento sin tiempo computacional adicional

29.- Aplicabilidad a otras puntuaciones de clasificación como F-score o rango de reciprocidad media aún no explorada

30.- Enfoque asume etiquetado de verdad de terreno cero-uno, extensión a preferencias por pares no considerada

Bóveda del Conocimiento construida porDavid Vivancos 2024