Learning with Multiple Complementary Labels
  A complementary label (CL) simply indicates an incorrect class of an example,
but learning with CLs results in multi-class classifiers that can predict the
correct class. Unfortunately, the problem setting only allows a single CL for
each example, which notably limits its potential since our labelers may easily
identify multiple CLs (MCLs) to one example. In this paper, we propose a novel
problem setting to allow MCLs for each example and two ways for learning with
MCLs. In the first way, we design two wrappers that decompose MCLs into many
single CLs, so that we could use any method for learning with CLs. However, the
supervision information that MCLs hold is conceptually diluted after
decomposition. Thus, in the second way, we derive an unbiased risk estimator;
minimizing it processes each set of MCLs as a whole and possesses an estimation
error bound. We further improve the second way into minimizing properly chosen
upper bounds. Experiments show that the former way works well for learning with
MCLs but the latter is even better.
