Multiclass Linear Perceptrons with Multiplicative Margins
Authors: Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov, Daswin De Silva, Denis Kleyko
Organizations: Department of Computer Science, Electrical and Space Engineering, Luleå University of Technology, 971 87 Luleå, Sweden · Institute of Information Technologies and Systems, 03187 Kyiv, Ukraine · Centre for Data Analytics and Cognition, La Trobe University, Melbourne, Australia · AI, Robotics and Cybersecurity Center and Department of Computer Science, Örebro University, Örebro, 70182, Sweden · Intelligent Systems Lab, Research Institutes of Sweden, Kista, 16440, Sweden
Abstract
This paper introduces a family of multiclass linear Perceptron classifiers with a multiplicative margin mechanism (MMPerc), as an alternative to standard margin-free and additive margin Perceptrons. The multiplicative formulation enforces classification confidence by requiring the true class score to exceed that of competing classes by a specified fraction of itself, rather than by a fixed additive threshold. This avoids dependence on score magnitudes arising from varied norms of data and class weight vectors. We propose several architectural and algorithmic variants of MMPerc, derive associated loss functions and mistake bounds for both linearly separable and non-separable data, and analyze key design considerations, including bias, margin threshold selection, and training modes. Extensive experiments on synthetic and real datasets show that MMPerc classifiers typically outperform the standard Perceptron, as well as classic baselines such as Support Vector Machines and Ridge classifiers. Owing to their simplicity, minimalistic design, and computational efficiency, MMPerc classifiers are promising candidates for conventional machine learning tasks, linear evaluation of Deep Neural Networks, integration with Hyperdimensional Computing / Vector Symbolic Architecture representations, and deployment in resource-constrained applications.
Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes k is at least 3, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers {hw:x↦argmaxy∈[k]wy⋅x,x∈Rd,w∈Rkd} using at most O(k2⋅(dlogd+logk)) samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e. k=2, our result is strictly stronger than all prior works.
We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples (x,y) from a distribution over Rd×[k], with Gaussian x-marginal, the goal is to output a hypothesis whose error is comparable to that of the best k-class linear classifier. While the binary case k=2 has a well-developed algorithmic theory, much less is known for k≥3. Even for k=3, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error O(k3/2opt)+ε for general k. Additionally, we develop a sharper localization-based framework which leads to error O(opt)+ε for k=3, and error poly(k)opt+ε for geometrically regular k-class linear classifiers.
Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma
We consider the problem of constructing a K-class classifier from the combination of O(logK) simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the K class centers are independent Gaussian points in Rd and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.
Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh +2