[{"conference":{"name":"CVPR: Conference on Computer Vision and Pattern Recognition","location":"Salt Lake City, UT, USA","end_date":"2018-06-22","start_date":"2018-06-18"},"type":"conference","status":"public","_id":"273","department":[{"_id":"VlKo"}],"date_updated":"2023-09-11T13:24:43Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.08269"}],"scopus_import":"1","month":"06","abstract":[{"lang":"eng","text":"The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time."}],"oa_version":"Preprint","ec_funded":1,"publication_status":"published","publication_identifier":{"isbn":["9781538664209"]},"language":[{"iso":"eng"}],"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"external_id":{"arxiv":["1604.08269"],"isi":["000457843603087"]},"article_processing_charge":"No","author":[{"last_name":"Mohapatra","full_name":"Mohapatra, Pritish","first_name":"Pritish"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"},{"first_name":"C V","full_name":"Jawahar, C V","last_name":"Jawahar"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"M Pawan","last_name":"Kumar","full_name":"Kumar, M Pawan"}],"title":"Efficient optimization for rank-based loss functions","citation":{"ista":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 3693–3701.","chicago":"Mohapatra, Pritish, Michal Rolinek, C V Jawahar, Vladimir Kolmogorov, and M Pawan Kumar. “Efficient Optimization for Rank-Based Loss Functions.” In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 3693–3701. IEEE, 2018. https://doi.org/10.1109/cvpr.2018.00389.","ama":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. Efficient optimization for rank-based loss functions. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE; 2018:3693-3701. doi:10.1109/cvpr.2018.00389","apa":"Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., & Kumar, M. P. (2018). Efficient optimization for rank-based loss functions. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 3693–3701). Salt Lake City, UT, USA: IEEE. https://doi.org/10.1109/cvpr.2018.00389","short":"P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701.","ieee":"P. Mohapatra, M. Rolinek, C. V. Jawahar, V. Kolmogorov, and M. P. Kumar, “Efficient optimization for rank-based loss functions,” in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, USA, 2018, pp. 3693–3701.","mla":"Mohapatra, Pritish, et al. “Efficient Optimization for Rank-Based Loss Functions.” 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–701, doi:10.1109/cvpr.2018.00389."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa":1,"publisher":"IEEE","quality_controlled":"1","page":"3693-3701","date_created":"2018-12-11T11:45:33Z","doi":"10.1109/cvpr.2018.00389","date_published":"2018-06-28T00:00:00Z","year":"2018","isi":1,"publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","day":"28"},{"day":"17","publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","isi":1,"year":"2018","date_published":"2018-12-17T00:00:00Z","doi":"10.1109/cvpr.2018.00956","date_created":"2022-03-18T12:45:09Z","page":"9175-9184","quality_controlled":"1","publisher":"IEEE","oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Uijlings J, Konyushkova K, Lampert C, Ferrari V. 2018. Learning intelligent dialogs for bounding box annotation. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVF: Conference on Computer Vision and Pattern Recognition, 9175–9184.","chicago":"Uijlings, Jasper, Ksenia Konyushkova, Christoph Lampert, and Vittorio Ferrari. “Learning Intelligent Dialogs for Bounding Box Annotation.” In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 9175–84. IEEE, 2018. https://doi.org/10.1109/cvpr.2018.00956.","ieee":"J. Uijlings, K. Konyushkova, C. Lampert, and V. Ferrari, “Learning intelligent dialogs for bounding box annotation,” in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, United States, 2018, pp. 9175–9184.","short":"J. Uijlings, K. Konyushkova, C. Lampert, V. Ferrari, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 9175–9184.","apa":"Uijlings, J., Konyushkova, K., Lampert, C., & Ferrari, V. (2018). Learning intelligent dialogs for bounding box annotation. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 9175–9184). Salt Lake City, UT, United States: IEEE. https://doi.org/10.1109/cvpr.2018.00956","ama":"Uijlings J, Konyushkova K, Lampert C, Ferrari V. Learning intelligent dialogs for bounding box annotation. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE; 2018:9175-9184. doi:10.1109/cvpr.2018.00956","mla":"Uijlings, Jasper, et al. “Learning Intelligent Dialogs for Bounding Box Annotation.” 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 9175–84, doi:10.1109/cvpr.2018.00956."},"title":"Learning intelligent dialogs for bounding box annotation","author":[{"last_name":"Uijlings","full_name":"Uijlings, Jasper","first_name":"Jasper"},{"full_name":"Konyushkova, Ksenia","last_name":"Konyushkova","first_name":"Ksenia"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert"},{"first_name":"Vittorio","full_name":"Ferrari, Vittorio","last_name":"Ferrari"}],"external_id":{"arxiv":["1712.08087"],"isi":["000457843609036"]},"article_processing_charge":"No","language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781538664209"],"eissn":["2575-7075"]},"publication_status":"published","oa_version":"Preprint","abstract":[{"text":"We introduce Intelligent Annotation Dialogs for bounding box annotation. We train an agent to automatically choose a sequence of actions for a human annotator to produce a bounding box in a minimal amount of time. Specifically, we consider two actions: box verification [34], where the annotator verifies a box generated by an object detector, and manual box drawing. We explore two kinds of agents, one based on predicting the probability that a box will be positively verified, and the other based on reinforcement learning. We demonstrate that (1) our agents are able to learn efficient annotation strategies in several scenarios, automatically adapting to the image difficulty, the desired quality of the boxes, and the detector strength; (2) in all scenarios the resulting annotation dialogs speed up annotation compared to manual box drawing alone and box verification alone, while also outperforming any fixed combination of verification and drawing in most scenarios; (3) in a realistic scenario where the detector is iteratively re-trained, our agents evolve a series of strategies that reflect the shifting trade-off between verification and drawing as the detector grows stronger.","lang":"eng"}],"month":"12","scopus_import":"1","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1712.08087"}],"date_updated":"2023-09-19T15:11:49Z","department":[{"_id":"ChLa"}],"_id":"10882","status":"public","type":"conference","conference":{"start_date":"2018-06-18","end_date":"2018-06-23","location":"Salt Lake City, UT, United States","name":"CVF: Conference on Computer Vision and Pattern Recognition"}}]