Unconfused Ultraconservative Multiclass Algorithms
Proceedings of the 5th Asian Conference on Machine Learning, PMLR 29:309-324, 2013.
We tackle the problem of learning linear classifiers from noisy datasets in a multiclass setting. The two-class version of this problem was studied a few years ago by, e.g. Bylander (1994) and Blum et al. (1996): in these contributions, the proposed approaches to fight the noise revolve around a Perceptron learning scheme fed with peculiar examples computed through a weighted average of points from the noisy training set. We propose to build upon these approaches and we introduce a new algorithm called \uma (for Unconfused Multiclass additive Algorithm) which may be seen as a generalization to the multiclass setting of the previous approaches. In order to characterize the noise we use the \em confusion matrix as a multiclass extension of the classification noise studied in the aforementioned literature. Theoretically well-founded, \uma furthermore displays very good empirical noise robustness, as evidenced by numerical simulations conducted on both synthetic and real data.