PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Margin Distribution Machine

Teng Zhang, Zhi-Hua Zhou

arXiv:1311.0989v2cs.LG

TL;DR

SVM maximizes the minimum margin, while theoretical results indicate that the margin distribution is more relevant to generalization. LDM optimizes that distribution through its mean and variance, and experiments report advantages over SVM and other methods across regular- and large-scale data sets.

  • Problem

    SVM focuses on minimum margin, whereas theoretical results indicate that the margin distribution is more crucial to generalization and is not captured by the single-point margin considered by SVM.

    Source: §2 · p. 4

  • Method

    LDM optimizes the margin distribution by simultaneously maximizing margin mean and minimizing margin variance.

    Source: §3.1 · p. 4

  • Results

    Experiments on twenty regular-scale and twelve large-scale data sets report LDM superior or highly competitive to SVM and other compared methods.

    Source: §1 · p. 2, §4.2 · p. 16, §4.3 · p. 17

  • Takeaways & Limitations

    The authors conclude that LDM can be used wherever SVM can be applied, and that the experiments validate its superiority to SVMs and many state-of-the-art methods.

    Source: §6 · p. 20

    The analysis considers the linear case for simplicity, while stating that its results also apply to other feature mappings.

    Source: §3.3 · p. 11

Abstract

from arXiv · show

Support vector machine (SVM) has been one of the most popular learning algorithms, with the central idea of maximizing the minimum margin, i.e., the smallest distance from the instances to the classification boundary. Recent theoretical results, however, disclosed that maximizing the minimum margin does not necessarily lead to better generalization performances, and instead, the margin distribution has been proven to be more crucial. In this paper, we propose the Large margin Distribution Machine (LDM), which tries to achieve a better generalization performance by optimizing the margin distribution. We characterize the margin distribution by the first- and second-order statistics, i.e., the margin mean and variance. The LDM is a general learning approach which can be used in any place where SVM can be applied, and its superiority is verified both theoretically and empirically in this paper.

1. Introduction

SVM’s minimum-margin objective does not capture the full margin distribution, which theory links more closely to generalization. LDM targets that distribution by maximizing margin mean and minimizing variance, with experiments showing advantages over SVM and other methods.

1. Introduction

  • Arc-gv achieved larger minimum margins yet generalized poorly, motivating the conjecture that margin distribution matters more than minimum margin.Later theory studied and proved this conjecture, and identified both margin mean and variance as important.Source: §1 · p. 2
  • LDM jointly maximizes margin mean and minimizes margin variance to optimize the margin distribution, following theoretical results on distributional margins.The paper proposes dual coordinate descent for kernel LDM and averaged stochastic gradient descent for large-scale linear LDM.Source: §1 · p. 2
  • Experiments on twenty regular-scale and twelve large-scale data sets report LDM superiority over SVM and many state-of-the-art methods.The authors state that these results support the importance of margin distribution for SVM-style learning.Source: §1 · p. 2

2. Preliminaries

The preliminaries define the instance and label spaces and frame learning as predicting labels for unseen examples drawn from an underlying distribution. They contrast hard-margin SVM’s minimum-margin objective with soft-margin SVM’s relaxed margin formulation.

2. Preliminaries

  • The instance space is X ∈ R^d, labels are Y = {+1, −1}, and the i.i.d. training set is drawn from D over X × Y to predict future unseen labels.The text introduces S as a training set of size m.Source: §2 · p. 3
  • Hard-margin SVM maximizes the minimum training margin when examples are separable with zero error.The paper characterizes this as a single-point margin objective.Source: §2 · pp. 3–4
  • For non-separable data, soft-margin SVM uses instance losses ξ and a trade-off parameter C, equivalently expressed using relaxed minimum margin γ0 and parameter C̄.The paper identifies γ0 as characterizing the top-p minimum margin, so both SVM variants consider only a single-point margin rather than the whole distribution.Source: §2 · pp. 3–4

3. LDM

Section 3 formulates LDM around the margin mean and variance, then presents optimization methods and a theoretical error analysis. It develops kernel and large-scale linear procedures for optimizing this objective.

3.1. Formulation

  • LDM seeks to maximize the margin mean while minimizing its variance; its hard- and soft-margin formulations subsume the corresponding SVM formulations under stated parameter settings.For soft-margin LDM, setting λ1 and λ2 to 0 recovers soft-margin SVM; the paper focuses on the soft-margin version thereafter.Source: §3.1 · pp. 4–5

3.2. Optimization

  • The optimization section presents a dual coordinate descent method for kernel LDM and an averaged stochastic gradient descent method for large-scale linear LDM.Source: §3.2 · p. 5, §3.2.2 · p. 9

3.2.1. Kernel LDM

  • Kernel LDM is optimized through a dual quadratic program that can be efficiently solved by dual coordinate descent using closed-form coordinate updates.The dual objective has a decoupled box constraint and a convex quadratic objective; the optimal solution admits a representation in the span of the training examples’ feature mappings.Source: §3.2.1 · pp. 5–8

3.2.2. Large Scale Kernel LDM

  • Kernel LDM’s kernel-matrix computation costs O(m^2), which may be prohibitive at large scale; the paper presents a fast linear-kernel LDM using ASGD.For the linear objective, a gradient estimate from a randomly sampled pair of training examples is unbiased, and the method uses averaged stochastic gradient descent.Source: §3.2.2 · pp. 8–10

3.3. Analysis

  • The analysis derives a bound on LDM’s expected probability of error using leave-one-out cross-validation, described as an unbiased estimate of test error.The analysis considers the linear case for simplicity and states that the results also apply to other feature mappings.Source: §3.3 · p. 11

4. Empirical Study

The empirical study compares LDM with SVM and other methods across regular- and large-scale datasets, then examines margin distributions, computational cost, and parameter sensitivity.

4.1. Experimental Setup

  • The evaluation covered 20 regular-scale and 12 large-scale datasets, using linear and RBF kernels on regular-scale data and linear kernels on large-scale data.Regular-scale experiments used 30 random train/test partitions; large-scale experiments recorded average accuracy and standard deviations over 10 random partitions.Source: §4.1 · pp. 13–15

4.2. Results on Regular Scale Data Sets

  • 13 linear-kernel and 15 RBF-kernel datasets gave LDM the best accuracy; LDM was never worse than SVM across regular-scale datasets.For linear kernels, LDM significantly outperformed SVM, MDO, MAMC, and KM-OMD on 12, 9, 17, and 10 of 20 datasets; for RBF kernels, it significantly outperformed SVM, MAMC, and KM-OMD on 10, 18, and 15 of 20.Source: Table 2 · p. 14, Table 3 · p. 15, §4.2 · pp. 16–17

4.3. Results on Large Scale Data Sets

  • 8 large-scale datasets gave LDM the best accuracy, and LDM was always better than or comparable to SVM.LDM significantly outperformed SVM, MDO, and MAMC on 6, 7, and 12 of 12 datasets, respectively; KM-OMD returned no results on any dataset, and MDO missed KDD2010 after 48 hours.Source: Table 4 · p. 16, §4.3 · p. 17

4.4. Margin Distributions

  • LDM usually had a slightly smaller minimum margin than SVM, but its cumulative-margin curve generally lay farther right, indicating larger margins for most examples.The figure plots cumulative frequency against margin; a curve farther right represents a larger accumulated margin.Source: Figure 1 · p. 17, §4.2 · p. 17, §4.4 · p. 18

4.5. Time Cost

  • On 12 large-scale datasets, LDM was slightly slower than ASGD-based SVM on three datasets and highly competitive on the other nine.Both LDM and ASGD-based SVM were much faster than LIBLINEAR-based SVM, which the authors attribute to ASGD.Source: Figure 2 · p. 18, §4.5 · p. 18

4.6. Parameter Influence

  • LDM performance was not very sensitive to parameter settings on the representative regular-scale datasets examined.The study varied λ1, λ2, and C one at a time while fixing the other parameters at cross-validated settings.Source: Figure 3 · p. 19, §4.6 · p. 19

5. Related Work

Prior margin-distribution methods differ from LDM in their objectives and scope; the paper reports LDM superior to MDO and MAMC, while identifying computational limits for KM-OMD.

5. Related Work

  • MDO minimizes costs that penalize smaller margins, but its non-convex objective may get stuck in local minima, it supports only linear kernels, and experiments found it inferior to LDM.MDO can be viewed as optimizing a weighted margin combination whose weights depend on the margins.Source: §5 · p. 19
  • MAMC is a special case of LDM with zero margin variance; despite its closed-form solution, it degenerates when class sizes differ and experiments found LDM clearly superior.Source: §5 · pp. 19–20
  • KM-OMD directly optimizes a weighted margin combination while ignoring variance, uses a hard-margin setting, and its computational cost prohibits large-scale application.The paper suggests the hard-margin setting may contribute to its worse performance than LDM.Source: §5 · p. 20

6. Conclusions

The conclusion presents LDM as an approach that optimizes margin distribution by maximizing its mean and minimizing its variance. Experiments across regular- and large-scale datasets validate its superiority to SVMs and other state-of-the-art methods.

6. Conclusions

  • LDM optimizes margin distribution by maximizing the margin mean and minimizing the margin variance simultaneously.Source: §6 · p. 20
  • LDM is presented as a general learning approach usable wherever SVM can be applied.Source: §6 · p. 20
  • Experiments on 20 regular-scale and 12 large-scale datasets validate LDM’s superiority to SVMs and many state-of-the-art methods.Source: §6 · p. 20
  • The authors identify generalizing LDM to regression and other learning settings as future work.Source: §6 · p. 20
Loading 1311.0989v2…