PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiclass Linear Perceptrons with Multiplicative Margins

Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov, Daswin De Silva, Denis Kleyko

arXiv:2608.30028v1cs.LGcs.NE

TL;DR

The paper addresses gaps in descriptions and analysis of multiclass Perceptron variants, including omitted loss functions, convergence and mistake bounds, and non-separable data. It develops multiplicative-margin classifiers and reports that they typically outperform standard and classic linear baselines on synthetic and real datasets.

  • Problem

    Prior descriptions omit key elements such as associated loss functions, convergence analysis, mistake bounds, and behavior on linearly non-separable data.

  • Method

    The paper defines associated loss functions for multiclass Perceptron formulations, including the multiclass β-hinge loss.

  • Results

    MMPerc almost always outperformed across synthetic DataGen datasets and, with appropriately chosen α and bias, often outperformed SVM and Ridge.

  • Takeaways & Limitations

    Experiments on synthetic and real datasets present multiclass Perceptrons with a multiplicated margin as an alternative to the standard Perceptron, SVM, and Ridge.

  • Takeaways & Limitations

    Direct comparison with prior studies is not straightforward because the data differ, and transfer of the design conclusions remains uncertain.

Abstract

from arXiv · show

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.

1 Introduction

The paper motivates simple linear classifiers for efficient learning across vector representations and introduces MMPerc to address gaps in prior multiplicative-margin Perceptron work.

  • Linear classifiers support efficient training and inference across diverse vector-represented data with modest computational requirements.
  • Linear evaluation trains a classifier on frozen DNN features, which often make classes approximately linearly separable.
  • HDC/VSA applications require efficient classifiers that support varying hypervector formats and dimensionalities, including online learning.
  • Prior multiplicative-margin Perceptron work lacks comprehensive loss, convergence, mistake-bound, non-separability, and design analyses, and was restricted to binary input vectors.
  • MMPerc introduces multiclass linear Perceptrons with multiplicative margins for arbitrary-format vector representations, including loss functions, learning rules, design considerations, and mistake-bound analysis.
  • Across most evaluated settings, MMPerc outperforms the standard Perceptron, with experiments using synthetic and real data, original vectors, and hypervector transformations.

2 Background and Basic Notions

This section defines multiclass linear Perceptron prediction and online or offline training, then frames learning through mistake-based updates and convex surrogate losses.

  • Online training presents one labeled instance per round, updates after observing its true label, and accesses each instance only once.
  • Offline training reuses a complete dataset across epochs until a mistake-based, epoch-based, or validation-based stopping criterion is met.
  • In the realizable online setting, a finite mistake bound implies convergence after at most that many mistakes, whereas the non-learnable case does not converge.
  • A multiclass linear Perceptron computes class scores as s = Wx and predicts the class with the highest score.
  • On a mistake, the standard multiclass Perceptron updates the predicted and true class weights using the error-correction rule.
  • The Perceptron loss is a continuous, convex surrogate based on the score gap, enabling subgradient updates despite the difficulty of directly minimizing 0-1 loss.

3 Method

The method section presents multiclass large-margin Perceptrons, including loss functions, learning rules, and mistake-bound analyses.

  • The method covers loss functions and learning rules for multiclass large-margin Perceptrons.
  • It also analyzes mistake bounds for linearly separable and non-separable data.

3.1 Loss Functions and Learning Rules for Multiclass Large-Margin Perceptrons

The paper develops additive and multiplicative margin Perceptrons through hinge losses, mistake criteria, and update rules, including asymmetric and absolute-score variants.

  • Additive Margin Formulation: The additive β-hinge loss is zero when the score gap δ is at least β and upper bounds the scaled 0-1 loss for β > 0.
  • Additive Margin Formulation: AMPerc updates only on mistakes and changes the true and competing class weights as in the standard Perceptron.
  • Multiplicative Margin Formulation: The multiplicative α_s-hinge loss requires the true-class score to exceed the strongest competing score by a fraction determined by α.
  • Multiplicative Margin Formulation: At α = 0, the multiplicative loss recovers the multiclass Perceptron loss.
  • Multiplicative Margin Formulation: MMPerc-Asm uses an asymmetric learning rule derived from subgradients of the multiplicative hinge loss.
  • The asymmetric case with absolute true-class score: When s_y < 0, the unmodified multiplicative formulation cannot produce a misclassification for δ ≥ 0, motivating the adjusted score s_y − α|s_y|.
  • The asymmetric case with absolute true-class score: The absolute multiplicative variant uses |s_y| in its loss, while MMPerc-AbsAsm combines this margin with an asymmetric update rule.

3.2 Mistake Bounds for the Linearly Separable Case

For linearly separable data, the paper derives mistake upper bounds for additive- and multiplicative-margin multiclass Perceptrons, with validity conditions tied to the margin threshold.

  • Assumptions: The separable-data analysis assumes bounded inputs and weight vectors achieving an additive margin γ against every incorrect class.The condition is equivalent to zero multiclass γ-hinge loss on every training instance.
  • Mistake bounds: M0 = 2(R2+β)/γ2 for AMPerc, recovering the additive-margin mistake bound.
  • Mistake bounds: M0 = R2 (2 – α) / (γ2 – α R2) for both MMPerc and MMPerc-Abs, provided γ2 – α R2 > 0.
  • Mistake bounds: M0 = (1 +(1 – α)2) R2 / (γ – α R)2 for MMPerc-Asm when γ – α R > 0.
  • Mistake bounds: M0 = (1 +(1 + α)2) R2 / (γ – α R)2 for MMPerc-AbsAsm when γ – α R > 0.
  • Implications: Introducing a positive margin increases these upper bounds relative to the standard Perceptron, while a finite bound implies offline-training convergence.

3.3 Mistake Bounds for the Linearly Non-Separable Case

For linearly non-separable data, the paper bounds mistakes relative to a fixed competitor through cumulative multiclass b-hinge loss, yielding bounds that grow with training length.

  • Analysis framework: The non-separable analysis compares Perceptron mistakes with the cumulative b-hinge loss of any fixed linear competitor.
  • Loss: The multiclass b-hinge loss is [b – (⟨uy, x⟩ – max_i ≠ y ⟨ui, x⟩)]+, measuring the competitor’s margin shortfall.
  • Bounds: The non-separable bounds grow with the number of training instances T rather than remaining fixed constants.
  • Consistency: Setting α or β to zero recovers the known standard multiclass Perceptron bound.
  • Bounds: M0 = {b Lb + 2 R2 ||U||2 + (2 b Lb R2 ||U||2)1/2} / b2 for the standard multiclass Perceptron.
  • Separable special case: When L1 = 0, the bound simplifies to M0 = 2 ||U||2 R2, which becomes 2R2/γ2 after weight normalization.

3.4 Discussion

The discussion links Perceptron dynamics and margin design to self-regulation, convergence, and generalization, while highlighting that additive margins lose scale invariance during training.

  • Generalization: Generalization bounds can incorporate the derived mistake bounds through penalized empirical-risk selection of a classifier obtained during training.
  • Learning rate: As mistakes accumulate, the effective learning rate η/M decreases, reducing each update’s relative effect and supporting stabilization.
  • Margin thresholds: For AMPerc, the effective threshold βeff = β / ||(M+1)W|| decreases with the number of mistakes because weight norms grow.
  • Margin thresholds: βeff/γ ≥ β / 2(R2+β), and AMPerc may require many more mistakes to reach βeff = γ/2 than the standard Perceptron bound.
  • Multiplicative margins: MMPerc bases classification and updating on relative class scores, so scaling W does not change the enforced multiplicative margin.
  • Multiplicative margins: The MMPerc weights continue adjusting until the specified multiplicative-margin condition is satisfied.
  • Limitation: MMPerc-Abs has a limitation when the true score is nonnegative and a competing score is negative: no mistake is triggered for any α.

4 Experimental Investigation

The experiments address practical design choices for evaluating multiclass Perceptrons across synthetic and real datasets, including bias scaling, margin selection, training mode, and weight selection.

  • Bias: Setting the bias component proportional to √D improved classification accuracy compared with the usual choice of 1.
  • Bias: For unnormalized vectors with norms up to R = Θ(√D), substantial boundary shifts require bias updates of order R2.
  • Bias: A bias term can be critical for improving multiclass Perceptron accuracy on certain datasets.
  • Margin selection: The margin threshold α is selected by cross-validation, and its value can substantially affect classification accuracy.
  • Training mode: The study uses offline training because it typically yields higher accuracy and matches baseline reporting practice.
  • Training mode: Preliminary tests found no consistent benefit from larger batches or the asymmetric learning rule, so reported experiments use batch size 1 and symmetric MMPerc-Abs.
  • Weight selection: Weights are selected from the epoch with highest training accuracy, although this may not always give the best testing accuracy.
  • Datasets: Synthetic DataGen classes are generated around class centers without feature or label noise, producing piece-wise linear separable regions.

4.3 Experiments with Synthetic Datasets

Synthetic experiments compare MMPerc with Perceptron and classic linear baselines across varied dimensions, class counts, sample sizes, and representations. MMPerc generally performs strongly, but its accuracy depends on margin threshold and bias choices, with transfer to real data left open.

  • Experimental setup: Synthetic datasets varied dimensionality, class count, training-set size, and representation, including real-valued vectors and 1000-dimensional hypervectors.Experiments used d ∈ {2,10}, C ∈ {3,10}, S ∈ {5,50,500,5000}, and D = 1000 after expansion.
  • Synthetic results: Perceptron perfectly separates the training set, but its decision boundaries are arbitrarily placed and provide only minimal separation.This behavior is especially relevant when evaluating small training sets.
  • Synthetic results: MMPerc smoothly adjusts decision boundaries as α varies, and suitable α-values can produce higher accuracy than Perceptron.The experiments report that appropriate thresholds improve alignment with true class regions.
  • Synthetic results: Across synthetic DataGen datasets, MMPerc almost always outperformed Perceptron and generally exceeded SVM and Ridge under the evaluated one-vs-all setup.SVM and Ridge occasionally failed to perfectly separate training data, with testing accuracies also affected.
  • Design considerations: Including a bias term can be critical, while selecting α remains important because both design choices substantially affect classification accuracy.The paper emphasizes careful bias selection for unnormalized data and appropriate margin thresholds for realizing MMPerc’s benefits.
  • Scope: The synthetic-data conclusions may not transfer directly to real datasets, motivating a separate evaluation focused on margin thresholds and bias.The authors explicitly identify transfer to real data as an open question.

4.4 Experiments with Real Datasets

Real-dataset experiments compare MMPerc with standard linear classifiers across original, binarized, RP, and RP+bin representations and multiple dimensionalities. MMPerc generally performs strongly, with bias and margin selection materially affecting accuracy and relative rank.

  • Experimental setup: Experiments evaluate original and transformed real datasets, including binarized, RP, and RP+bin representations, across hypervector dimensionalities D.Hypervector dimensionalities were selected from D ∈ {64, 128, 200, 500, 1000, 2000, 4000, 10000}; MMPerc α was cross-validated.
  • Experimental setup: Training used at most 100 epochs, with early stopping when training accuracy reached 0.9999 per epoch.This schedule contrasts with a 2500-epoch schedule used in prior work.
  • CTG results: On CTG, cross-validated α matched the best-performing α, while binarization reduced accuracy relative to the original representation.The CTG results include classification accuracies for original and binarized data and compare multiple classifier setups.
  • CTG results: For RP, MMPerc with bias and its cross-validated variant outperformed the baselines, while bias-free Perceptron and MMPerc variants showed a noticeable accuracy drop.RP accuracy remained stable across D, which the authors attribute to the linearity of the RP transformation.
  • CTG results: In RP+bin, binary-hypervector classifiers outperformed classifiers trained on original or binarized CTG data at larger D, while SVM accuracy declined at higher D.The authors associate RP+bin variation with local nonlinear features introduced by binarization and suggest SVM hyperparameter suboptimality as a possible explanation for its decline.
  • Comparison and discussion: Across real datasets and transformations, appropriately selected α and bias often made MMPerc outperform both SVM and Ridge under the same one-prototype-per-class memory budget.MMPerc was also reported to achieve accuracies close to SVM and higher than most other classifiers; on HAND, it performed similarly to the standard Perceptron.

5 Discussion

The discussion presents MMPerc as a simple multiclass linear Perceptron family whose multiplicative margin is scale-invariant, with theoretical analysis, broad experiments, and practical deployment considerations. Results are generally favorable, while threshold selection and incomplete comparisons define important boundaries.

  • Framework and theory: The framework includes architectural and algorithmic variants, associated loss functions, and mistake bounds for separable and non-separable data.The analysis also covers weight updates and practical design choices.
  • Margin mechanism: MMPerc defines the margin as a fixed proportion of the winning class score, making it invariant to absolute score magnitude.This avoids explicitly accounting for class-prototype and data-vector norms when selecting the threshold.
  • Experimental evaluation: Experiments compare MMPerc with the standard Perceptron, Ridge, and SVM classifiers on synthetic and real data under the same memory budget.The evaluation spans real-valued and binary vectors across a wide range of dimensionalities.
  • Experimental evaluation: MMPerc achieves competitive accuracy and frequently outperforms baselines when the bias and margin threshold are properly chosen.The CTG and HAND results include representative accuracies such as 96.04% for one MMPerc setup and 97.85% for HAND1 MMPerc without transformation.
  • Limitations and future work: Selecting the margin threshold is a key limitation because MMPerc requires hyperparameter tuning, addressed here through cross-validation.The threshold may need to be tailored per dataset, and class-specific thresholds could increase selection complexity.
  • Practical deployment: The variants retain a minimalistic design with fixed unit learning rate and limited operational requirements, supporting real-valued, integer, binary, and sparse vectors.Binary operations can reduce to counting or addition, while training avoids weight normalization, projection, decay, and variable learning rates.

6 Conclusion

The conclusion presents MMPerc as a family of multiclass linear Perceptrons with multiplicative margins, supported by theory, design analysis, and extensive evaluations. The models typically improve accuracy over standard and classic linear baselines, but require margin-threshold selection.

  • Contributions: MMPerc introduces multiclass linear Perceptron classifiers with multiplicative margins and a theoretical framework covering losses, updates, and mistake bounds.The bounds address both linearly separable and non-separable data.
  • Design and implementation: The models require no or minor modifications to the standard Perceptron update rule and use a fixed unit learning rate.This supports computationally lightweight implementations across varied vector formats.
  • Evaluation: Experiments cover synthetic and real datasets with real-valued and binary inputs across a wide range of dimensionalities.The study also examines bias, threshold selection, training regimes, epoch control, and inference weights.
  • Results: MMPerc typically achieves higher classification accuracy than the standard Perceptron, SVM, and Ridge classifiers.The conclusion reports this pattern across the evaluated settings rather than as a single dataset-specific result.
  • Limitations: MMPerc requires selecting an appropriate margin threshold, which can be addressed through cross-validation at additional computational cost.This is identified as a cost relative to the standard Perceptron.
  • Implications: The accuracy gains and implementation simplicity make MMPerc promising for resource-constrained and edge scenarios, HDC contexts, and linear DNN evaluation.These applications are presented as promising candidates rather than established deployment outcomes.

1 Supplementary Note 1: Related work

The related-work discussion situates MMPerc within the development of Perceptron models, multiclass constructions, additive-margin methods, and broader large-margin classifiers. It emphasizes that multiplicative-margin algorithms had not previously been explored in the cited work.

  • Perceptron foundations: Perceptrons developed from threshold-based neural elements into single-layer linear models and multilayer architectures with fixed input transformations and trainable output weights.The single-layer Perceptron is linear in its parameters, while transformed feature spaces can support linear classification.
  • Multiclass Perceptrons: Incremental Perceptron procedures were proven to converge to weights that classify all instances from linearly separable classes.The multiclass linear Perceptron later received convergence guarantees and mistake-bound analyses for separable settings.
  • Multiclass constructions: The Kesler construction represents multiclass classification as a two-class problem, enabling error-correcting learning rules and two-class Perceptron analysis.It concatenates class weight vectors to obtain the equivalent representation.
  • Large-margin methods: Prior large-margin Perceptrons and online classifiers use additive thresholds, constrained optimization, norm constraints, adaptive learning rates, or weight decay.Examples include ROMMA, Passive-Aggressive, MIRA, ALMA, MICRA, and Pegasos.
  • Classic baselines: SVMs combine a squared weight norm with hinge loss, whereas replacing hinge loss with squared error yields Ridge regression.These methods provide classic large-margin and regularized linear baselines.
  • Research gap: The related-work review states that multiplicative-margin algorithms had not been explored in prior work of the cited scope.This positions the paper's MMPerc framework as a distinct direction within Perceptron margin methods.

2 Supplementary Note 2: Proofs of Mistake Bounds

The proofs bound Perceptron mistake counts by combining lower bounds on progress toward a comparator with upper bounds on weight-matrix growth. The resulting guarantees differ across additive-margin and multiplicative-margin variants and require margin-related conditions in several cases.

  • Separable-data bounds: After M mistakes, AMPerc, MMPerc, and MMPerc-Abs satisfy (γM)^2 ≤ ||(M+1)W||^2, while the other variants use ((γ − αR)M)^2.The latter bound is stated with γ − αR ≥ 0.
  • Upper bounds: MMPerc and MMPerc-Abs have upper weight-growth bound ||(M+1)W||^2 < R^2(2M + αM^2 − αM).This follows from the multiplicative mistake condition and a norm bound on the true-class weight vector.
  • Mistake bounds: AMPerc has mistake bound M < 2(R/γ)^2(1 + β/R^2), whereas MMPerc and MMPerc-Abs use a denominator condition involving γ^2 − αR^2.The AMPerc result follows from its additive margin parameter β; the multiplicative variants share the same displayed quadratic-growth expression.
  • Mistake bounds: MMPerc-Asm has mistake bound M < (1 +(1 − α)^2)R^2/(γ − αR)^2, provided γ − αR > 0.Its upper weight-growth term is (1 +(1 − α)^2)R^2M.
  • Proof strategy: The analysis initializes all variants with zero weights and studies lower and upper bounds on the Frobenius dot product after mistakes.The lower-bound argument sums updates only on rounds where the classifier makes mistakes.
  • Non-separable data: For non-separable data, the lower bound becomes bM − L_b(U), or (b − α||U||R)M − L_b(U) for MMPerc-Asm and MMPerc-AbsAsm.Here L_b(U) is the cumulative comparator loss over mistaken rounds.

3 Supplementary Note 3: Extended Experimental Results

The extended experiments examine random projection, binarization, bias choices, and classifier rankings across synthetic and HAND datasets. MMPerc generally remains competitive or superior, but performance depends on representation, dimensionality, bias, and dataset configuration.

  • Random projection experiments: Random projection expands DataGen vectors to D = 1000, with additional tests varying binarization and the bias term.The experiments compare original configurations with RP and RP+bin transformations.
  • Random projection experiments: 0.9900 vs 0.9927: for C = 3, d = 2, S = 500, Perceptron nearly matches the best MMPerc after random projection.In the same setting, SVM accuracy improves to 0.9500 from 0.8620 without random projection.
  • Random projection experiments: 0.8253 vs 0.8113: SVM outperforms the best MMPerc for C = 3, d = 10, S = 5 after random projection.The passage attributes this result possibly to SVM’s one-vs-all strategy.
  • Binarized representations: RP+bin retains vector directions while discarding norms and distances, altering class regions and producing radiating linear decision boundaries.Vectors separated by norm differences can become similar after binarization.
  • Bias selection: bias = normmax consistently outperformed bias = 0 and bias = 1 across the tested setups and is recommended as the default.Zero bias performed poorly, while bias = 1 improved accuracy but remained inferior to bias = normmax.
  • HAND datasets: MMPerc generally matched or slightly exceeded Perceptron across HAND datasets, while SVM often declined on binarized data and Ridge was generally weaker.For HAND1 and HAND5, MMPerc without bias achieved the lowest average rank across D.
Loading 2608.30028v1…