PaperlayerView exact revision on arXiv

Source-linked AI summary

Cost-Sensitive Support Vector Machines

Hamed Masnadi-Shirazi, Nuno Vasconcelos, Arya Iranmehr

arXiv:1212.0975v2cs.LGstat.ML

TL;DR

Cost-sensitive SVMs lack a fully satisfactory extension of the standard hinge-loss framework, especially when error costs or class frequencies are unequal. The paper derives a cost-sensitive hinge loss from probability elicitation and risk minimization, then builds CS-SVM and related evaluation tools. The resulting method is Bayes-consistent, applies to separable and non-separable data, and shows superior empirical performance to previous methods.

  • Problem

    Cost-sensitive SVM design is insufficiently understood because the standard symmetric hinge loss has no obvious cost-sensitive generalization and prior methods have scope limitations.

  • Method

    The paper generalizes probability-elicitation and risk-minimization connections to derive a cost-sensitive hinge loss, CS-SVM, dual analyses, example-dependent costs, and cost-sensitive performance measures.

  • Results

    The proposed classifiers implement the cost-sensitive Bayes decision rule, approximate cost-sensitive Bayes risk, enforce cost sensitivity for separable and non-separable data, and outperform previous methods empirically.

  • Takeaways & Limitations

    Minimum expected cost-sensitive risk incorporates priors and costs and connects classifier evaluation to ROC analysis, while CS-SVM can be optimized using procedures identical to classic SVM.

  • Takeaways & Limitations

    The loss-function choice requires specific desirable properties, and biased-penalty approaches have limited cost-sensitivity enforcement on separable data.

Abstract

from arXiv · show

A new procedure for learning cost-sensitive SVM(CS-SVM) classifiers is proposed. The SVM hinge loss is extended to the cost sensitive setting, and the CS-SVM is derived as the minimizer of the associated risk. The extension of the hinge loss draws on recent connections between risk minimization and probability elicitation. These connections are generalized to cost-sensitive classification, in a manner that guarantees consistency with the cost-sensitive Bayes risk, and associated Bayes decision rule. This ensures that optimal decision rules, under the new hinge loss, implement the Bayes-optimal cost-sensitive classification boundary. Minimization of the new hinge loss is shown to be a generalization of the classic SVM optimization problem, and can be solved by identical procedures. The dual problem of CS-SVM is carefully scrutinized by means of regularization theory and sensitivity analysis and the CS-SVM algorithm is substantiated. The proposed algorithm is also extended to cost-sensitive learning with example dependent costs. The minimum cost sensitive risk is proposed as the performance measure and is connected to ROC analysis through vector optimization. The resulting algorithm avoids the shortcomings of previous approaches to cost-sensitive SVM design, and is shown to have superior experimental performance on a large number of cost sensitive and imbalanced datasets.

1. Introduction

Cost-sensitive SVM design is needed because unequal error costs and class imbalance alter the Bayes-optimal decision rule, while existing SVM extensions have important limitations. The paper derives a cost-sensitive hinge-loss SVM, analyzes its dual, proposes cost-sensitive risk measures, and reports improved performance over prior methods.

  • Motivation: Unequal error costs and class imbalance make the optimal decision rule differ from the cost-insensitive rule.This motivates cost-sensitive extensions for applications such as medical diagnosis, fraud detection, and business decision making.
  • Motivation: Cost-sensitive SVM design is limited by the lack of a clear cost-sensitive generalization of the symmetric hinge loss.The paper identifies this as an incompletely understood problem despite SVMs’ learning-theoretic foundation and broad use.
  • Prior approaches: Boundary movement fails to provide reliable cost sensitivity because SVM outputs do not accurately estimate posterior probabilities, and it is flawed for non-separable data.Calibration does not improve threshold-based cost-sensitive performance because invertible output transformations preserve the ROC curve.
  • Prior approaches: Biased penalties have limited ability to enforce cost sensitivity on separable data, where large slack penalties reduce the optimization to standard SVM.The resulting boundary is midway between the classes rather than assigning a larger margin to the preferred class.
  • Proposed approach: The proposed method extends the hinge loss and derives CS-SVM by minimizing its associated risk rather than directly modifying standard SVM training.The construction generalizes probability-elicitation connections to cost-sensitive classification and supports identical optimization procedures.
  • Proposed approach: The algorithm implements the cost-sensitive Bayes decision rule, approximates cost-sensitive Bayes risk, and handles both separable and inseparable training data.The paper also studies dual regularization and sensitivity analysis, supports example-dependent costs, and connects minimum expected cost-sensitive risk to ROC analysis.

2. Bayes consistent classifier design

The paper frames classifier design through risk minimization and probability elicitation, linking optimal predictors to posterior probabilities and Bayes decisions. This framework provides a generative route for constructing Bayes-consistent margin losses instead of guessing losses and checking them afterward.

  • Risk minimization: A classifier maps feature vectors to labels through h(x) = sign[p(x)], and optimality is defined by minimizing expected loss, or risk.Risk minimization can be analyzed through the corresponding conditional risk.
  • Bayes consistency: A loss is Bayes consistent when minimizing its risk yields the Bayes decision rule.The predictor can be written as p(x) = f(η(x)), where η(x) is the posterior probability and f is a link function.
  • Bayes consistency: For zero-one loss, the conditional risk is 1 − η when f ≥ 0 and η when f < 0.Its minimizers induce the familiar Bayes decision rule through the sign of the predictor.
  • Margin losses: Margin losses penalize small positive yf values, encouraging a margin and supporting better generalization than losses without margin enforcement.Exponential, logistic, and hinge losses are identified as Bayes-consistent margin losses.
  • Probability elicitation: Probability elicitation designs rewards so that expected reward is maximized at the true posterior probability η.The functions I1 and I−1 assign rewards for predictions under the two possible class outcomes.
  • Probability elicitation: Savage’s theorem states that suitable reward functions can be derived from an appropriate convex function J(η), providing a foundation for loss construction.The resulting framework supplies a generative path for Bayes-consistent margin losses using an invertible symmetric link.
  • Loss design: The elicitation framework derives a loss from a desired predictor and conditional risk, contrasting with approaches that guess a loss and then test its Bayes consistency.This reverses the usual design direction by starting from the desired optimal behavior.

3. Cost sensitive Bayes consistent classifier design

The paper extends risk minimization and probability elicitation to cost-sensitive classification, designing losses whose optimal predictors implement the cost-sensitive Bayes decision rule. It then develops approximation principles and a cost-sensitive exponential/hinge-loss construction for practical classifiers.

  • Cost-sensitive zero-one loss: The cost-sensitive zero-one loss assigns distinct penalties C1 and C−1 to false negatives and false positives, respectively.Its conditional risk is minimized at the cost-sensitive threshold γ = C−1/(C1+C−1).
  • Cost-sensitive zero-one loss: The resulting optimal classifier implements the cost-sensitive Bayes decision rule, and its minimum risk equals the minimum cost-sensitive Bayes error.The paper gives both linear and logarithmic optimal predictors satisfying the threshold condition.
  • Bayes-consistent margin losses: A generative design procedure constructs cost-sensitive margin losses from an invertible link function and a convex function governing the minimum conditional risk.The procedure derives class-specific conditional risks and losses while preserving cost-sensitive optimality.
  • Bayes-consistent margin losses: Any predictor satisfying the required symmetry and threshold conditions has conditional risk minimized by the cost-sensitive Bayes decision rule.These conditions ensure the predictor changes sign at γ = C−1/(C1+C−1).
  • Bayes-consistent margin losses: The minimum risk of a constructed cost-sensitive loss can approach the minimum cost-sensitive Bayes error arbitrarily closely in expectation.The approximation is obtained by making the loss’s minimum conditional risk arbitrarily close to that of the cost-sensitive zero-one loss.
  • Risk design: Type-II minimum conditional risks satisfy both required properties and are generally closer approximations to the cost-sensitive Bayes risk than Type-I risks.The true selection criterion remains the expected gap between the constructed and cost-sensitive zero-one minimum conditional risks.
  • Cost-sensitive exponential and hinge losses: The framework derives a cost-sensitive exponential loss, while the proposed cost-sensitive hinge loss has four degrees of freedom controlling class-specific margins and slopes.The hinge loss is reported as Type-II and as a close approximation to the zero-one minimum conditional risk.

4. Cost sensitive SVM

The paper extends the SVM hinge loss to encode asymmetric costs and derives CS-SVM by minimizing the resulting risk. The construction provides Bayes-decision guarantees while preserving the standard SVM optimization structure.

  • Loss construction: The cost-sensitive hinge loss assigns separate margins and slopes to positive and negative examples.Positive examples use margin e/d and slope d, while negative examples use margin b/a.
  • Optimization: Replacing the standard hinge loss with the cost-sensitive loss yields a quadratic program similar to the standard soft-margin SVM.The cost-sensitive formulation reduces to the standard setting when the class-cost parameters take their cost-insensitive values.
  • Parameter effects: Under the parameterization C−1 ≥ 1 and C1 ≥ 2C−1 − 1, κ controls the separable-case cost sensitivity, while C1 and C−1 weight margin violations.Increasing C−1, equivalently decreasing κ, enlarges the positive margin; larger C1 increases the cost of positive errors.
  • Bayes consistency: The derived classifier implements the cost-sensitive Bayes decision rule and approximates the cost-sensitive Bayes risk.These guarantees follow from the risk-based derivation rather than heuristic parameter choices.
  • Parameter effects: For separable data, CS-SVM enforces a larger positive margin while remaining a maximum-margin solution.The negative margin is reduced relative to the positive margin according to the chosen cost parameters.
  • Comparison with prior methods: Unlike BP-SVM, CS-SVM maintains a maximum-margin solution independently of the slack penalty C and does not simply overtrain on the positive class.The formulation adjusts class margins through κ rather than relying only on the penalty weight.

5. Cost-sensitive SVM in the dual

The dual CS-SVM formulation introduces regularization and modified class-specific constraints to address cost sensitivity and class imbalance. Its effects include asymmetric margins and more balanced support-vector representations.

  • Dual formulation: The CS-SVM dual reduces to the standard SVM dual when C1 = C−1 = 1.This makes the formulation compatible with standard dual solvers.
  • Dual formulation: In the dual, cost sensitivity appears through an ℓ1-norm regularization term and relaxed upper-bound constraints on α+.The regularization term is associated with α− and has coefficient 1 − κ.
  • Imbalanced dataset learning: On the covertype UCI dataset with imbalance ratio 1:211, decreasing κ reduces negative support vectors and approaches a support-vector imbalance ratio of 1 at κ = 2^-256.The number of nonzero α− components becomes closer to the number of nonzero α+ components as regularization increases.
  • Imbalanced dataset learning: For the checkerboard dataset with imbalance ratio 1:1000, κ = 0.01 produces a decision boundary close to the optimal one.Choosing κ < 0.01 violates the stated condition and has diminishing returns, preferring the majority class.
  • Imbalanced dataset learning: For imbalanced data, CS-SVM applies sparsity-inducing ℓ1 regularization to α−, reducing unwanted movement of the decision boundary toward the minority class.The resulting asymmetric margin favors the minority class.
  • Cost-sensitive learning: In cost-sensitive learning, the asymmetric regularization reduces the margin for the lower-cost class and increases it for the higher-cost class.The same mechanism favors the minority class in imbalanced-data learning.

6. Example-dependent cost-sensitive learning

The paper extends CS-SVM to example-dependent costs through the ED-CS-Hinge loss. Experiments on KDD98 report improvement over ED-BP-Hinge and other SVM-based algorithms.

  • Motivation: Example-dependent cost-sensitive learning addresses settings where misclassification costs differ across individual examples, including within the same class.The paper identifies computational advertising, medical diagnosis, information retrieval, fraud detection, and business decision-making as applications.
  • Method: The ED-CS-Hinge loss extends the CS-SVM loss to incorporate example-specific costs.This provides an example-dependent cost-sensitive SVM formulation.
  • Method: The ED-CS-Hinge retains asymmetric-margin flexibility compared with the ED-BP-Hinge.The paper presents this flexibility as an inherited benefit of the CS-SVM loss.
  • Results: On the KDD98 dataset, the example-dependent CS-SVM improves over the ED-BP-Hinge-based SVM and other SVM-based algorithms.The result is reported for the experimental study of example-dependent cost-sensitive learning.

7. Performance measure

The paper adopts minimum cost-sensitive risk as a performance measure that incorporates class costs and priors. Through vector optimization, this measure selects operating points on classifier ROC curves and supports partial-ROC evaluation when costs are unknown.

  • Risk definition: Cost-sensitive zero-one risk combines class priors, false-negative rates, false-positive rates, and their respective costs.When costs are equal, it simplifies to the cost-insensitive probability of error.
  • ROC connection: Each classifier maps to false-positive and false-negative rate vectors whose Pareto-optimal frontier forms the ROC curve.Vector optimization compares these vectors in the nonnegative orthant.
  • ROC connection: Choosing (P1C1, P−1C−1) selects the ROC operating point minimizing the corresponding cost-sensitive risk.The paper calls this quantity minimum risk thereafter.
  • Unknown costs and priors: When costs or priors are unknown, TP-t-AUC and TN-t-AUC evaluate restricted regions of the ROC curve rather than a single operating point.The two measures target performance in high-sensitivity and high-specificity regions.
  • Empirical evaluation: Figure 5 compares ROC curves and risk operating points for CI-SVM, BP-SVM, and CS-SVM on the german test set.It distinguishes best-risk points from threshold-tuned and unthresholded model risks.

8. Experimental study

The experimental study evaluates CS-SVM against BM-SVM and BP-SVM across cost-sensitive, unknown-cost, imbalanced, and example-dependent-cost settings using benchmark datasets and task-specific measures.

  • Experimental design: Experiments compare BM-SVM, BP-SVM, and CS-SVM across four settings: available costs, unavailable costs, example-dependent costs, and imbalanced datasets.The study uses 21 real-world datasets created from 20 distinct datasets.
  • Experimental design: The experiments use Gaussian RBF kernels and dataset-specific grid searches for C, γ, cost parameters, and κ, with cross-validation or separate validation data.The same search range and granularity are used across algorithms within each dataset.
  • Known class-dependent costs: CS-SVM outperforms BP-SVM on all three known-cost datasets, surpasses BM-SVM on two, and ties it on one using minimum expected risk.The evaluated datasets are German credit, Statlog Heart Disease, and KDD99.
  • Unknown class-dependent costs: CS-SVM improves both TP-0.9-AUC and TN-0.9-AUC over BP-SVM and BM-SVM in 15 of 16 unknown-cost experiments, tying in one.These experiments use eight datasets without known costs and without severe imbalance.
  • Imbalanced data: CS-SVM improves TP-0.9-AUC and TN-0.9-AUC in 17 of 18 imbalanced-data experiments, tying in one.The experiments target large datasets with severe imbalance ratios.
  • Example-dependent costs: The example-dependent CS-SVM achieves the best performance among the evaluated example-dependent SVM methods on the KDD98 donation-profit task.It ranks fifth among all listed methods, including more complicated compounded schemes.

9. Conclusion

The conclusion presents CS-SVM as a cost-sensitive extension of SVM hinge-loss design grounded in Bayes-risk consistency. It also connects dual analysis and performance measurement to broader cost-sensitive and imbalanced-learning settings.

  • Conclusion: The paper extends probability-elicitation-based loss design to cost-sensitive classification and derives CS-SVM by minimizing the resulting cost-sensitive hinge-loss risk.The method enforces cost sensitivity for both separable and non-separable training data.
  • Conclusion: The proposed predictor implements the cost-sensitive Bayes decision rule and approximates the cost-sensitive Bayes risk.
  • Conclusion: The dual analysis establishes connections between cost-sensitive learning, regularization theory, and sensitivity analysis.
  • Conclusion: Minimum expected cost-sensitive risk is proposed for evaluating binary classifiers under cost-sensitive and imbalanced data settings, with connections to ROC analysis.
  • Conclusion: CS-SVM is extended to example-dependent costs, and empirical evidence reports superior performance relative to previous methods.

Appendix A. Fenchel Dual Problem

The appendix states a Fenchel-duality theorem for regularized risk minimization with convex regularizer and loss functions.

  • Fenchel dual theorem: For convex functions Ω and φ defined on R^n and R, respectively, the regularized risk minimization problem has a Fenchel dual formulation.
  • Fenchel dual theorem: The primal and dual variables are β and z, while Ω* and φ* denote the Fenchel conjugates of Ω and Φ.

Proof

The proof section develops the dual formulation using Fenchel conjugacy and duality, while accounting for bias, regularization, and the specific hinge losses.

  • Dual derivation: Fenchel conjugates and duality rules are used to transform the primal and dual decision-function formulation.
  • Bias term: For decision functions with an unregularized bias term, the dual formulation includes an equality constraint.
  • Hinge-loss conjugates: The conjugate of the hinge loss is derived for φ(u) = max(b − au, 0), then specialized to CI-Hinge, BP-Hinge, and CS-Hinge losses.
  • Notation and cases: The proof distinguishes cases and uses the diagonal label matrix Y, whose entries are restricted to −1 and 1 and satisfy Y = Y^-1.

CI-Hinge

The passage expresses the scaled hinge loss as φ(u) = C max(1 −u, 0) = max(C −Cu, 0), and gives its conjugate φ∗(v) = I[0,C](v) −v.

  • CI-Hinge: The CI-Hinge loss scales the standard hinge loss by C: φ(u) = C max(1 −u, 0).It is equivalently written as max(C −Cu, 0).
  • CI-Hinge: The scaled hinge loss has the equivalent piecewise-max representation max(C −Cu, 0).
  • CI-Hinge: Its conjugate is given by φ∗(v) = I[0,C](v) −v.
Loading 1212.0975v2…