This paper proposes a method for multi-class classification problems, where the number of classes $K$ is large. The method, referred to as {\em Candidates v.s. Noises Estimation} (CANE), selects a small subset of candidate classes and samples the remaining classes. We show that CANE is always consistent and computationally efficient. Moreover, the resulting estimator has low statistical variance approaching that of the maximum likelihood estimator, when the observed label belongs to the selected candidates with high probability. In practice, we use a tree structure with leaves as classes to promote fast beam search for candidate selection. We also apply the CANE method to estimate word probabilities in neural language models. Experiments show that CANE achieves better prediction accuracy over the Noise-Contrastive Estimation (NCE), its variants and a number of the state-of-the-art tree classifiers, while it gains significant speedup compared to the standard $\mathcal{O}(K)$ methods.

本文提出了一种多类别分类问题的方法，称为候选项 vs. 噪声估计(CANE)，它选择少量的候选类别并对其余的类别进行抽样，并将CANE方法应用于在大型神经语言模型中估计单词概率，大量实验证明CANE方法在准确性和速度方面都取得了明显的优势。

大规模多类别分类问题中的候选项和噪音估计