  Annotating multi-class instances is a crucial task in the field of machine
learning. Unfortunately, identifying the correct class label from a long
sequence of candidate labels is time-consuming and laborious. To alleviate this
problem, we design a novel labeling mechanism called stochastic label. In this
setting, stochastic label includes two cases: 1) identify a correct class label
from a small number of randomly given labels; 2) annotate the instance with
None label when given labels do not contain correct class label. In this paper,
we propose a novel suitable approach to learn from these stochastic labels. We
obtain an unbiased estimator that utilizes less supervised information in
stochastic labels to train a multi-class classifier. Additionally, it is
theoretically justifiable by deriving the estimation error bound of the
proposed method. Finally, we conduct extensive experiments on widely-used
benchmark datasets to validate the superiority of our method by comparing it
with existing state-of-the-art methods.
