PaperlayerView exact revision on arXiv

Source-linked AI summary

Granular Ball Twin Support Vector Machine

A. Quadir, M. Sajid, M. Tanveer

arXiv:2410.04774v3cs.LG

TL;DR

TSVM faces matrix-inversion costs, missing SRM regularization, and sensitivity to noise and outliers. The paper proposes granular-ball classifiers, including a regularized large-scale variant, and reports improved efficiency and generalization against baselines across benchmark datasets.

  • Problem

    TSVM requires matrix inversions, omits SRM in its formulation, and is susceptible to noise and outliers.

    Source: §I · p. 2

  • Method

    GBTSVM constructs classifiers from granular balls rather than individual points, and LS-GBTSVM adds primal regularization while eliminating matrix inversions.

    Source: §I · p. 2

  • Results

    Across 36 UCI and KEEL datasets, linear and nonlinear GBTSVM and LS-GBTSVM beat baselines in efficiency and generalization; linear average ACC improved up to 20%.

    Source: §VIII · p. 11

  • Takeaways & Limitations

    LS-GBTSVM is presented as suitable for large-scale problems while addressing overfitting concerns.

    Source: §VIII · p. 11

    GBTSVM’s Wolfe-dual matrix inversion becomes costly on large datasets, and its lack of SRM raises overfitting risk.

    Source: S.III. DISCUSSION OF THE PROPOSED… · p. 15

Abstract

from arXiv · show

On Efficient and Scalable Computation of the Nonparametric Maximum Likelihood Estimator in Mixture ModelsTwin support vector machine (TSVM) is an emerging machine learning model with versatile applicability in classification and regression endeavors. Nevertheless, TSVM confronts noteworthy challenges: $(i)$ the imperative demand for matrix inversions presents formidable obstacles to its efficiency and applicability on large-scale datasets; $(ii)$ the omission of the structural risk minimization (SRM) principle in its primal formulation heightens the vulnerability to overfitting risks; and $(iii)$ the TSVM exhibits a high susceptibility to noise and outliers, and also demonstrates instability when subjected to resampling. In view of the aforementioned challenges, we propose the granular ball twin support vector machine (GBTSVM). GBTSVM takes granular balls, rather than individual data points, as inputs to construct a classifier. These granular balls, characterized by their coarser granularity, exhibit robustness to resampling and reduced susceptibility to the impact of noise and outliers. We further propose a novel large-scale granular ball twin support vector machine (LS-GBTSVM). LS-GBTSVM's optimization formulation ensures two critical facets: $(i)$ it eliminates the need for matrix inversions, streamlining the LS-GBTSVM's computational efficiency, and $(ii)$ it incorporates the SRM principle through the incorporation of regularization terms, effectively addressing the issue of overfitting. The proposed LS-GBTSVM exemplifies efficiency, scalability for large datasets, and robustness against noise and outliers. We conduct a comprehensive evaluation of the GBTSVM and LS-GBTSVM models on benchmark datasets from UCI, KEEL, and NDC datasets. Our experimental findings and statistical analyses affirm the superior generalization prowess of the proposed GBTSVM and LS-GBTSVM models.

I. INTRODUCTION

The paper addresses TSVM’s matrix-inversion, overfitting, noise, and outlier challenges by introducing classifiers built from granular balls, including a regularized version for large-scale data. It describes granular-ball generation and GBTSVM’s linear formulation, alongside related work and notation.

II. RELATED WORKS

  • Prior TSVM variants reduce SVM’s computational burden, but TSVM still requires matrix inversions and lacks SRM, while noise-robust variants may increase computational complexity.The cited background also describes granular-ball classifiers as a coarser-grained approach that balances detail against efficiency and noise resilience.Source: §I · pp. 1–2

I. INTRODUCTION

  • GBTSVM uses granular balls instead of individual points, while LS-GBTSVM adds primal regularization and avoids matrix inversions for large-scale data.The authors report that both models are insensitive to noise and stable under resampling.Source: §I · p. 2
  • Experiments on UCI, KEEL, and large-scale NDC datasets, with noise testing, are reported to show superior generalization, noise insensitivity, and resampling stability.The introduction describes 36 UCI and KEEL datasets and NDC datasets ranging from 10k to 5m.Source: §I · p. 2

A. Notations

  • Each granular ball is represented by its center, radius, and label; class-specific center and radius matrices collect these quantities.The center is the center of gravity, the radius is the average distance to enclosed samples, and the label is the majority label.Source: A. Notations · p. 2, B. Granular Ball Computing · p. 3

B. Granular Ball Computing

  • Granular-ball computing partitions data into balls characterized by centers and radii, assigns majority labels, and iteratively splits balls until each meets purity threshold T.The threshold is the percentage of samples in a ball that share its majority label.Source: B. Granular Ball Computing · p. 3

III. THE PROPOSED GRANULAR BALL TWIN SUPPORT VECTOR MACHINE (GBTSVM)

  • GBTSVM uses granular-ball inputs to reduce sample count and buffer noisy points, placing each class’s hyperplane near its own ball centers and at least one unit from the opposing balls’ tangents.The authors describe the formulation for the linear case and refer to supplementary material for the nonlinear formulation.Source: §III · pp. 3, 5
  • The linear formulation uses a regularization term δI to address the difficulty of computing an inverse involving H^T H.I denotes an identity matrix of appropriate dimensions.Source: §III · p. 4

IV. LARGE SCALE GRANULAR BALL TWIN SUPPORT VECTOR MACHINE (LS-GBTSVM)

LS-GBTSVM reformulates GBTSVM to address costly matrix inversion on large datasets and its omission of structural risk minimization. Its formulation adds regularization and an equality constraint, with linear and nonlinear versions described.

IV. LARGE SCALE GRANULAR BALL TWIN SUPPORT VECTOR MACHINE (LS-GBTSVM)

  • The reformulation targets costly matrix inversions in GBTSVM’s Wolfe dual and its lack of SRM, which raises overfitting risk.The proposed optimization adds an equality constraint and is intended to remove extensive matrix inverses.Source: §IV · p. 5
  • Regularization terms in the primal formulation incorporate SRM, while the modified Lagrangian bypasses calculation of the large matrix inverse.The formulation uses positive tunable parameters d1, d2, d3, and d4, slack variables, and vectors of ones.Source: §IV · p. 5
  • The proposed models cover linear and nonlinear kernel spaces, and the resulting optimal values determine two non-parallel hyperplanes for classification.Test samples are labeled according to the optimal planes.Source: §IV · p. 5

V. TIME COMPLEXITY AND ALGORITHM

GBTSVM recursively splits impure granular balls using 2-means, then classifies using the generated balls. Its stated complexity is lower than standard TSVM when the number of balls is much smaller than the number of samples.

V. TIME COMPLEXITY AND ALGORITHM

  • The passage states that, across t iterations, the overall computational complexity of generating granular balls is O(2nt), or less, with splitting phases costing at most O(2n) each.Source: §V · p. 5
  • The proposed GBTSVM time complexity is much lower than TSVM, with O(p^3) ≪ O(n^3) when p ≪ n.The granular-ball generation cost is stated as O(2nt) or less, for t iterations.Source: §V · p. 5
  • The algorithm starts with the dataset as one granular ball and splits a ball with purity below threshold T into two using 2-means.Balls meeting the threshold are retained and assigned a center, radius, and majority-class label.Source: §V · p. 6

VI. VIOLATION TOLERANCE UPPER BOUND

The violation tolerance upper bound relates differences in estimated slack variables to the distance between granular-ball centers. The theorems establish this relation for pairs of positive and negative granular balls, and the authors interpret closer balls as having more similar tolerances.

VI. VIOLATION TOLERANCE UPPER BOUND

  • For positive granular balls, Theorem 1 bounds the difference between their estimated slack variables in terms of the distance between their centers.The bound is stated in the theorem’s inequality.Source: §VI · p. 6
  • Theorem 2 gives the corresponding slack-variable bound for any pair of negative granular balls.Its inequality likewise depends on the distance between the granular-ball centers.Source: §VI · p. 7
  • The authors interpret the derived bound as meaning that closer granular balls have more similar violation tolerances, and identical samples have identical tolerances.The slack variables are interpreted as tolerances for violations from the boundary hyperplane.Source: §VI · pp. 6–8

VII. EXPERIMENTAL RESULTS

The evaluation compares GBTSVM and LS-GBTSVM with baseline models on UCI, KEEL, and generated NDC datasets, including experiments at different noise levels.

VII. EXPERIMENTAL RESULTS

  • The experiments compare both proposed models with baselines on UCI and KEEL datasets under different noise levels and on NDC-generated datasets.Supplementary analyses vary granular-ball parameters, label noise, and several hyperparameters.Source: §VII · p. 8

A. Experimental Setup

Experiments use standard train/test splits and cross-validation for model tuning, with fixed penalty parameters for large-scale NDC comparisons.

A. Experimental Setup

  • Data are split 70:30 into training and testing sets, and five-fold cross-validation with grid search tunes hyperparameters.For the NDC comparisons, all models use penalty parameters equal to 1.Source: A. Experimental Setup · p. 8
  • Nonlinear experiments use a Gaussian kernel, with its parameter selected from 2^-5 to 2^5.The search ranges for d1, d2, d3, and d4 each span 10^-5 to 10^5.Source: A. Experimental Setup · p. 8
  • Experiments run on Windows 11 with Python 3.11 and 128 GB RAM; dual QPPs use CVXOPT, while LS-GBTSVM also uses SOR.The CPU is an Intel Xeon Gold 6226R at 2.90 GHz.Source: A. Experimental Setup · p. 8

B. Experiments on Real World UCI and KEEL Datasets

The experiments compare GBTSVM variants with baseline classifiers on UCI and KEEL benchmarks, under label noise, and on large NDC datasets. The conclusions report performance, noise resilience, and scalability findings, while identifying multiclass classification as future work.

B. Experiments on Real World UCI and KEEL Datasets

  • 85.30%, 85.32%, and 81.34% average ACC for GBTSVM, LS-GBTSVM, and LS-GBTSVM (SOR), respectively, exceed the reported baseline averages on linear UCI/KEEL datasets.The corresponding baseline averages are 82.21% for SVM, 72.46% for GBSVM (PSO), and 65.47% for TSVM.Source: B. Experiments on Real World UCI and… · p. 8, Table I · p. 9
  • On 36 UCI/KEEL datasets, linear-kernel pairwise tests report significant superiority for GBTSVM and LS-GBTSVM over baseline models; LS-GBTSVM (SOR) succeeds on 19 datasets.For nonlinear comparisons, the reported Nemenyi test finds significant differences for the proposed models against baselines, with the stated exception of LS-GBTSVM (SOR) versus SVM.Source: B. Experiments on Real World UCI and… · pp. 8–9, Table II · p. 9
  • 88.74%, 85.85%, and 84.93% average ACC for GBTSVM, LS-GBTSVM, and LS-GBTSVM (SOR), respectively, compare with 76.27%, 79.43%, and 84.83% for SVM, GBSVM, and TSVM.The passage reports that the proposed models outperform baselines on most datasets and that GBTSVM has the lowest average rank.Source: B. Experiments on Real World UCI and… · p. 9, Table IV · p. 10

C. Experiments on UCI and KEEL Datasets with Label Noise

  • Across 5%, 10%, 15%, and 20% label noise, GBTSVM and LS-GBTSVM outperform compared models; granular balls’ predominant labels mitigate minority-label noise.LS-GBTSVM has the lowest average rank at 0% and 5% noise (1.94 and 2.68), while GBTSVM has the lowest rank at 10%, 15%, and 20%.Source: C. Experiments on UCI and KEEL… · p. 10

D. Experiment on Artificial NDC Datasets.

VIII. CONCLUSIONS

  • The conclusions report up to 20% average ACC improvement for linear cases and up to 12% increase in noisy nonlinear cases; baseline models face memory issues beyond NDC-50k.The paper identifies extending the binary-classification models to multiclass scenarios as future work.Source: §VIII · p. 11

SUPPLEMENTARY MATERIAL

  • The supplementary material includes mathematical formulations of GBSVM and TSVM.The section introduces those formulations without further details in the supplied passage.Source: SUPPLEMENTARY MATERIAL · p. 13

A. Granular Ball Support Vector Machine (GBSVM)

The section reviews granular-ball and twin support vector machines, then presents the proposed models’ linear and nonlinear formulations. The linear LS-GBTSVM hyperplane parameters are obtained without matrix inversion.

A. Granular Ball Support Vector Machine (GBSVM)

B. Twin Support Vector Machine (TSVM)

  • TSVM constructs two non-parallel hyperplanes, each passing through its class samples while maximizing distance from samples of the other class.The class assignment uses the obtained hyperplane parameters.Source: B. Twin Support Vector Machine (TSVM) · p. 13

NON-LINEAR CASES

  • The proposed GBTSVM and LS-GBTSVM formulations cover linear and nonlinear cases.The section introduces their formulations for both cases.Source: NON-LINEAR CASES · p. 13

A. Linear LS-GBTSVM

  • For linear LS-GBTSVM, the hyperplane parameters are obtained without matrix inversion.The formulation derives the parameters through K.K.T. conditions and expresses them in matrix form.Source: A. Linear LS-GBTSVM · pp. 13–14

B. Non-linear GBTSVM

Nonlinear GBTSVM maps input samples into a Hilbert space and constructs granular balls there. The model’s primal problems use the resulting class-ball centers and radii.

B. Non-linear GBTSVM

  • Nonlinear GBTSVM maps each input sample into a Hilbert space and defines granular balls over the mapped data.The mapped dataset is denoted Dϕ, and a granular ball is represented in that space.Source: B. Non-linear GBTSVM · p. 14
  • The nonlinear primal problems use the centers and radii of the positive- and negative-class granular balls.These class-specific quantities enter the GBTSVM formulation.Source: B. Non-linear GBTSVM · p. 14
  • A positive small value δ is used to handle situations involving singular matrices.Source: B. Non-linear GBTSVM · p. 14

C. Non-linear LS-GBTSVM

Nonlinear LS-GBTSVM is formulated as a pair of constrained minimization problems. Its dual formulation and solutions are calculated similarly to the linear case.

C. Non-linear LS-GBTSVM

S.III. DISCUSSION OF THE PROPOSED GBTSVM AND LS-GBTSVM MODELS

The discussion attributes GBTSVM’s robustness and efficiency to granular-ball inputs, while identifying matrix inversion and the absence of SRM as GBTSVM limitations. The sensitivity analyses report label-noise resilience and examine granular-ball and kernel parameters.

S.III. DISCUSSION OF THE PROPOSED GBTSVM AND LS-GBTSVM MODELS

  • GBTSVM uses granular balls to reduce noise effects, uses ball centers rather than all samples for efficiency, and applies nonlinear kernel transformations to capture complex patterns.Source: S.III. DISCUSSION OF THE PROPOSED… · p. 15
  • GBTSVM’s Wolf-dual matrix inversion is costly on large datasets, and its lack of SRM raises overfitting risk.Source: S.III. DISCUSSION OF THE PROPOSED… · p. 15
  • LS-GBTSVM eliminates matrix inversions and adds regularization terms for SRM, while retaining granular-ball inputs and their reported robustness, scalability, and resampling resilience.The discussion also reports computational efficiency compared with standard SVM and GBSVM.Source: S.III. DISCUSSION OF THE PROPOSED… · p. 15

A. Sensitivity Analysis of GB Parameters num and pur

  • With increased num and pur, ACC rises; the text attributes this to further ball division capturing underlying data patterns.The analysis varies num over {2, 3, 4, 5} and pur over {1, 0.97, 0.94, 0.91, 0.88, 0.85, 0.82, 0.79}.Source: A. Sensitivity Analysis of GB… · p. 15

B. Sensitivity Analysis of Label Noise

  • Across varying label-noise levels, GBTSVM and LS-GBTSVM show consistent, superior performance, attributed to ball labels being governed mainly by the prevailing label.The analysis contaminates labels at 5%, 10%, 15%, and 20%.Source: B. Sensitivity Analysis of Label Noise · p. 15

C. Sensitivity Analysis of Hyperparameter σ and pur

  • GBTSVM accuracy fluctuates with σ and pur, with reported optima at σ ranges 21 to 25 and 2−5 to 2−3; performance is described as more influenced by σ.The study also examines d1 and d2 and the relation between granular-ball count and accuracy across purities, but these passages provide no outcomes for those analyses.Source: S.VI. SENSITIVITY ANALYSIS · p. 15, C. Sensitivity Analysis of… · p. 17

D. Sensitivity Analysis of Hyperparameters d1 and d2

The section examines how GBTSVM accuracy varies with hyperparameters and granular-ball purity, then presents UCI and KEEL evaluations, including LS-GBTSVM results.

D. Sensitivity Analysis of Hyperparameters d1 and d2

  • Beyond 10^-2, further increases in d1 and d2 yield diminishing improvements in testing ACC.ACC rises with both parameters until a threshold, so careful hyperparameter selection is important for generalization.Source: D. Sensitivity Analysis of… · p. 17

ing ACC of the Proposed GBTSVM and LS-GBTSVM Models with Different Purities

  • Across purities from 0.82 to 1.0, granular-ball counts decrease as purity falls, while ACC remains within a stable range.The reported pattern covers GBTSVM and LS-GBTSVM on five UCI and KEEL datasets.Source: ing ACC of the Proposed GBTSVM and… · p. 17

S.VI. EVALUATION ON UCI AND KEEL DATASETS

  • The evaluation presents baseline and proposed-model performance for UCI and KEEL datasets in linear and nonlinear cases, with and without label noise.The passage identifies Table I and Table S.IV as presenting these cases.Source: S.VI. EVALUATION ON UCI AND KEEL… · p. 17

LS-GBTSVM† (SOR)

  • The LS-GBTSVM (SOR) results include ACC entries for shuttle-6 vs 2-3 at noise levels from 5% to 20%.The supplied table text does not identify the model columns, so it does not support a specific performance comparison.Source: LS-GBTSVM† (SOR) · pp. 20–21

LS-GBTSVM (SOR)†

The supplied results report accuracy comparisons for UCI and KEEL datasets under nonlinear-kernel settings and include ACC and average-rank summaries. A separate LS-GBSVM (SMO) result block also reports ACC and average-rank values.

ACC (%)

  • The UCI and KEEL comparison is for nonlinear kernels, with ACC entries reported across noise levels.The table text includes results for multiple cases, but its column labels are not available here.Source: ACC (%) · pp. 23–25
Loading 2410.04774v3…