Nonlinear Kernel Support Vector Machine with 0-1 Soft Margin Loss

• URL: http://arxiv.org/abs/2203.00399v1
• Date: Tue, 1 Mar 2022 12:53:52 GMT
• Title: Nonlinear Kernel Support Vector Machine with 0-1 Soft Margin Loss
• Authors: Ju Liu, Ling-Wei Huang, Yuan-Hai Shao, Wei-Jie Chen, Chun-Na Li
• Abstract summary: We propose a nonlinear model for support vector machine with 0-1 soft margin loss, called $L_0/1$-KSVM, which cunningly involves the kernel technique into it. $L_0/1$-KSVM has much fewer SVs, simultaneously with a decent predicting accuracy, when compared to its linear peer.
• Score: 13.803988813225025
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advance on linear support vector machine with the 0-1 soft margin loss ($L_{0/1}$-SVM) shows that the 0-1 loss problem can be solved directly. However, its theoretical and algorithmic requirements restrict us extending the linear solving framework to its nonlinear kernel form directly, the absence of explicit expression of Lagrangian dual function of $L_{0/1}$-SVM is one big deficiency among of them. In this paper, by applying the nonparametric representation theorem, we propose a nonlinear model for support vector machine with 0-1 soft margin loss, called $L_{0/1}$-KSVM, which cunningly involves the kernel technique into it and more importantly, follows the success on systematically solving its linear task. Its optimal condition is explored theoretically and a working set selection alternating direction method of multipliers (ADMM) algorithm is introduced to acquire its numerical solution. Moreover, we firstly present a closed-form definition to the support vector (SV) of $L_{0/1}$-KSVM. Theoretically, we prove that all SVs of $L_{0/1}$-KSVM are only located on the parallel decision surfaces. The experiment part also shows that $L_{0/1}$-KSVM has much fewer SVs, simultaneously with a decent predicting accuracy, when comparing to its linear peer $L_{0/1}$-SVM and the other six nonlinear benchmark SVM classifiers.

Related papers

• $p$SVM: Soft-margin SVMs with $p$-norm Hinge Loss [0.0]
  Support Vector Machines (SVMs) based on hinge loss have been extensively discussed and applied to various binary classification tasks. In this paper, we explore the properties, performance, and training algorithms of $p$SVMs.
  arXiv  Detail & Related papers  (2024-08-19T11:30:00Z)
• Settling Constant Regrets in Linear Markov Decision Processes [57.34287648914407]
  We study the constant regret guarantees in reinforcement learning (RL) We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) For an MDP characterized by a minimal suboptimality gap $Delta$, Cert-LSVI-UCB has a cumulative regret of $tildemathcalO(d3H5/Delta)$ with high probability, provided that the misspecification level $zeta$ is below $tildemathcalO(Delta / (sqrtd
  arXiv  Detail & Related papers  (2024-04-16T17:23:19Z)
• A Safe Screening Rule with Bi-level Optimization of $\nu$ Support Vector Machine [15.096652880354199]
  We propose a safe screening rule with bi-level optimization for $nu$-SVM. Our SRBO-$nu$-SVM is strictly deduced by integrating the Karush-Kuhn-Tucker conditions. We also develop an efficient dual coordinate descent method (DCDM) to further improve computational speed.
  arXiv  Detail & Related papers  (2024-03-04T06:55:57Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Kernel Support Vector Machine Classifiers with the $\ell_0$-Norm Hinge Loss [3.007949058551534]
  Support Vector Machine (SVM) has been one of the most successful machine learning techniques for binary classification problems. This paper is concentrated on vectors with hinge loss (referred as $ell$-KSVM), which is a composite function of hinge loss and $ell_$norm. Experiments on the synthetic and real datasets are illuminated to show that $ell_$-KSVM can achieve comparable accuracy compared with the standard KSVM.
  arXiv  Detail & Related papers  (2023-06-24T14:52:44Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Estimating Average Treatment Effects with Support Vector Machines [77.34726150561087]
  Support vector machine (SVM) is one of the most popular classification algorithms in the machine learning literature. We adapt SVM as a kernel-based weighting procedure that minimizes the maximum mean discrepancy between the treatment and control groups. We characterize the bias of causal effect estimation arising from this trade-off, connecting the proposed SVM procedure to the existing kernel balancing methods.
  arXiv  Detail & Related papers  (2021-02-23T20:22:56Z)
• A Semismooth-Newton's-Method-Based Linearization and Approximation Approach for Kernel Support Vector Machines [1.177306187948666]
  Support Vector Machines (SVMs) are among the most popular and the best performing classification algorithms. In this paper, we propose a semismooth Newton's method based linearization approximation approach for kernel SVMs. The advantage of the proposed approach is that it maintains low computational cost and keeps a fast convergence rate.
  arXiv  Detail & Related papers  (2020-07-21T07:44:21Z)
• Unified SVM Algorithm Based on LS-DC Loss [0.0]
  We propose an algorithm that can train different SVM models. UniSVM has a dominant advantage over all existing algorithms because it has a closed-form solution. Experiments show that UniSVM can achieve comparable performance in less training time.
  arXiv  Detail & Related papers  (2020-06-16T12:40:06Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  We introduce algorithms for learning nonlinear dynamical systems of the form $x_t+1=sigma(Thetastarx_t)+varepsilon_t$. We give an algorithm that recovers the weight matrix $Thetastar$ from a single trajectory with optimal sample complexity and linear running time.
  arXiv  Detail & Related papers  (2020-04-30T10:42:48Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.