Title: Minimax semi-supervised confidence sets for multi-class classification
Authors: Evgenii Chzhen - Universite Paris-Est (France) [presenting]
Abstract: Multiclass classification problems such as image annotation can involve a large number of classes. In this context, confusion between classes can occur, and a single label classification may fail. We will present a general device to build a confidence set classifier, instead of a single label classifier. In our framework the goal is to build the best confidence set classifier having a given expected size and the attractive feature of our approach is its semi-supervised nature - the construction of the confidence set classifier takes advantage of unlabeled data. The study of the minimax rates of convergence under the combination of the margin and non parametric assumptions reveals that there is NO supervised method that outperforms the proposed semi-supervised estimator. To further highlight the fundamental difference of supervised and semi-supervised methods, we establish that the best achievable rate for ANY supervised method is parametric, even if the margin assumption is extremely favourable. On the contrary, by using a sufficiently large unlabelled sample we are able to significantly improve this rate.