Robust Diversity-Driven Subset Selection in Combinatorial Optimization

Abstract

Subset selection is fundamental in combinatorial optimization with applications in biology, operations research, and computer science, especially machine learning and computer vision. However, subset selection has turned out to be NP-hard and polynomial-time solutions are usually not available. Therefore, it is of great importance to develop approximate algorithms with theoretical guarantee for subset selection in constrained settings. To select a diverse subset with an asymmetric objective function, we develop an asymmetric subset selection method, which is computationally efficient and has a solid lower bound on approximation ratio. Experimental results on cascade object detection demonstrate the effectiveness of the proposed method. To select a diverse subset with bandit feedbacks, we develop a new bandit framework, which we refer to it as per-round knapsack constrained linear submodular bandits. With the proposed bandit framework, we propose two algorithms with solid regret bounds. Experimental results on personalized recommendation demonstrate the effectiveness of the proposed method. To correct bias in subset selection, we develop a new regularization criterion to minimize the distribution shift between selected subset and the set of all elements. Experimental results on image retrieval demonstrate the effectiveness of the proposed method. To explore diversity in anchor templates, we devise a pyramid of diversity-driven anchor templates to generate high quality proposals. Experimental results on cascade face detection demonstrate the effectiveness of the proposed method. In this thesis, we focus on developing robust diversity-driven subset selection methods in constrained settings as well as their applications in machine learning and computer vision.