Support Vector Method for Novelty Detection

Bernhard SchölkopfRobert C. WilliamsonAlexander J. SmolaJohn Shawe-TaylorJohn C. Platt

article1999NeurIPS2,697 citations

Introduces the support vector method for novelty detection, which estimates the support of an unknown distribution by separating unlabeled data from the origin in a kernel feature space with direct theoretical control over the outlier fraction.

Listen

The article addresses the challenge of identifying a compact region in input space that contains most data points drawn from an unknown distribution, while allowing for a controllable fraction of outliers. This novelty detection task matters in settings where full density estimation is unnecessary or infeasible, such as spotting anomalies or mislabeled examples in high-dimensional data.

The work develops and analyzes an algorithm that learns a decision function separating the bulk of the training points from the origin in a kernel-induced feature space. It solves a convex quadratic program whose single parameter ν directly controls the expected fraction of outliers, then recovers a sparse kernel expansion for the resulting function. Theoretical results establish that ν asymptotically equals both the fraction of support vectors and outliers, while generalization bounds quantify the probability that new points fall outside the estimated region.

Experiments on two-dimensional toy problems illustrate how ν and kernel width trade off the size of the captured region against robustness to distant points. On the USPS handwritten-digit test set the method, run with ν equal to 5 percent, surfaces the twenty most atypical patterns; many of these turn out to be segmentation errors or mislabeled digits, confirming practical utility for outlier identification.

These findings show that a support-vector-style approach can perform one-class learning without requiring a complete density model, thereby reducing computational cost and avoiding assumptions that the data admit a density. The resulting procedure runs in seconds on thousands of examples and supplies an explicit, tunable trade-off between region size and outlier tolerance.

For deployment, practitioners should choose a decision threshold strictly below the learned offset p to improve generalization on unseen data. Kernel parameters still require careful selection, and additional validation on larger or domain-specific collections would strengthen before widespread use.

Australian National University Microsoft Royal Holloway, University of London high-dimensional feature space probability distributions support vector novelty detection support vector method unsupervised learning

Schölkopf et al (1999).pdf

Paper: Support-vector networks, Corinna Cortes et al. (1995). It introduces the foundational soft-margin support vector machine framework and dual quadratic programming formulation that the source adapts for one-class novelty detection.
Paper: A training algorithm for optimal margin classifiers, B. Boser et al. (1992). It develops the core optimal margin hyperplane and dual Lagrangian optimization algorithms for kernel-based classification upon which the source's geometric separation relies.

Paper: Deep One-Class Classification, Lukas Ruff et al. (2018). It generalizes classical kernel-based one-class classification by embedding support vector novelty detection objectives into deep neural network architectures.
Paper: Isolation-Based Anomaly Detection, Fei Tony Liu et al. (2012). It develops the Isolation Forest algorithm as a scalable alternative to distance- and one-class SVM model-based anomaly detection.
Paper: Deep Autoencoding Gaussian Mixture Model for Unsupervised Anomaly Detection, Bo Zong et al. (2018). It combines deep autoencoders with density estimation to advance unsupervised anomaly detection beyond shallow kernel one-class methods.
Paper: Unsupervised Anomaly Detection with Generative Adversarial Networks to Guide Marker Discovery, Thomas Schlegl et al. (2017). It extends unsupervised novelty detection principles to generative adversarial networks for identifying anatomical anomalies in medical imagery.
Paper: LOF: identifying density-based local outliers, Markus M. Breunig et al. (2000). It introduces the local outlier factor to handle density-varying outlier detection scenarios where global boundary-separation methods may struggle.
Paper: Efficient algorithms for mining outliers from large data sets, S. Ramaswamy et al. (2000). It proposes scalable distance-based ranking algorithms for mining outliers across large high-dimensional datasets without requiring quadratic programming solvers.

Cover for Support Vector Method for Novelty Detection

Abstract

Suppose you are given some dataset drawn from an underlying probability distribution P and you want to estimate a “simple” subset S of input space such that the probability that a test point drawn from P lies outside of S equals some a priori specified ν between 0 and 1.

We propose a method to approach this problem by trying to estimate a function f which is positive on S and negative on the complement. The functional form of f is given by a kernel expansion in terms of a potentially small subset of the training data; it is regularized by controlling the length of the weight vector in an associated feature space. We provide a theoretical analysis of the statistical performance of our algorithm.

The algorithm is a natural extension of the support vector algorithm to the case of unlabelled data.

Topics

high-dimensional feature space probability distributions support vector

Keywords

novelty detection support vector method unsupervised learning pattern recognition Gaussian kernel

1 INTRODUCTION
2 ALGORITHMS
3 THEORY
4 EXPERIMENTS
5 DISCUSSION
References

Knowls

Knowl 1 — Single-Class Support Vector Machine Formulation
model/method
Given an unlabelled dataset $x_1, \dots, x_\ell \in \mathcal{X}$ , where $\mathcal{X}$ is a compact subset of $\mathbb{R}^N$ , and a feature map $\Phi: \mathcal{X} \to \mathcal{F}$ associated with a Mercer kernel $k(x, y) = \langle \Phi(x), \Phi(y) \rangle$ , the single-class support vector machine separates the dataset from the origin in feature space $\mathcal{F}$ by solving the primal quadratic program:

$\min_{w \in \mathcal{F}, \, \xi \in \mathbb{R}^\ell, \, \rho \in \mathbb{R}} \frac{1}{2} \|w\|^2 + \frac{1}{\nu \ell} \sum_{i=1}^\ell \xi_i - \rho$

subject to

$\langle w, \Phi(x_i) \rangle \ge \rho - \xi_i, \quad \xi_i \ge 0 \quad \text{for all } i = 1, \dots, \ell,$

where $\nu \in (0, 1)$ is a user-specified parameter controlling the trade-off between maximizing the distance of the hyperplane from the origin $\rho / \|w\|$ and penalizing points lying on the wrong side of the margin via slack variables $\xi_i$ .

The corresponding dual quadratic programming problem is:

$\min_{\alpha \in \mathbb{R}^\ell} \frac{1}{2} \sum_{i=1}^\ell \sum_{j=1}^\ell \alpha_i \alpha_j k(x_i, x_j) \quad \text{subject to } 0 \le \alpha_i \le \frac{1}{\nu \ell} \text{ for all } i \in \{1, \dots, \ell\}, \quad \sum_{i=1}^\ell \alpha_i = 1.$

Points $x_i$ with non-zero dual coefficients $\alpha_i > 0$ are called support vectors (SVs). For any support vector $x_i$ whose coefficient is strictly between the bounds ( $0 < \alpha_i < \frac{1}{\nu \ell}$ ), the offset $\rho$ is computed by:

$\rho = \langle w, \Phi(x_i) \rangle = \sum_{j=1}^\ell \alpha_j k(x_j, x_i).$

The resulting decision function determining whether a novel point $x$ belongs to the estimated support ( $+1$ ) or is an outlier ( $-1$ ) is:

$f(x) = \operatorname{sgn}\left( \langle w, \Phi(x) \rangle - \rho \right) = \operatorname{sgn}\left( \sum_{i=1}^\ell \alpha_i k(x_i, x) - \rho \right).$
Knowl 2 — Parameter nu as Bounds on Fractions of Support Vectors and Outliers
theoretical result
For the single-class SVM quadratic program with an optimal offset $\rho \ne 0$ on a training set of size $\ell$ :
1. $\nu$ is an upper bound on the fraction of outliers (points $x_i$ with slack $\xi_i > 0$ , or equivalently $\langle w, \Phi(x_i) \rangle < \rho$ ).
2. $\nu$ is a lower bound on the fraction of support vectors (points $x_i$ with Lagrange multipliers $\alpha_i > 0$ ).
3. If the training data are generated independently and identically distributed from a continuous probability distribution $P(x)$ without discrete components, and the kernel $k$ is analytic and non-constant, then with probability $1$ , asymptotically as $\ell \to \infty$ , the fraction of support vectors and the fraction of outliers both equal $\nu$ .
Knowl 3 — Limiting Behaviors of Single-Class SVM for Extreme Values of nu
theoretical result
The single-class SVM exhibits two distinct limiting behaviors as $\nu \in (0, 1)$ approaches its boundaries:
1. Hard Margin Limit ( $\nu \to 0$ ): The upper bound on the dual variables $\frac{1}{\nu \ell} \to \infty$ , making the penalty for margin errors infinite. If the training data in feature space are separable from the origin, the algorithm identifies the unique supporting hyperplane that separates all data from the origin while maximizing the distance $\rho / \|w\|$ to the origin.
2. Parzen Windows Limit ( $\nu \to 1$ ): The dual constraints $0 \le \alpha_i \le \frac{1}{\nu \ell}$ and $\sum_{i=1}^\ell \alpha_i = 1$ admit only one solution: $\alpha_i = \frac{1}{\ell}$ for all $i = 1, \dots, \ell$ . For normalized kernels with unit integral (such as normalized Gaussian kernels), the decision function $f(x) = \operatorname{sgn}\left( \frac{1}{\ell} \sum_{i=1}^\ell k(x_i, x) - \rho \right)$ corresponds directly to a thresholded Parzen windows density estimator.
Knowl 4 — PAC Generalization Error Bound for Support Estimation with Margin Slack
theoretical result
Let $P$ be a fixed but unknown probability distribution on the input space $\mathcal{X}$ , and let $\mathcal{F}$ be a class of real-valued functions mapping $\mathcal{X}$ to a bounded range $[a, b]$ . For a fixed threshold $\theta \in \mathbb{R}$ , margin parameter $\gamma > 0$ , and function $f \in \mathcal{F}$ , define the point slack as $d(x, f, \gamma) = \max\{0, \, \theta + \gamma - f(x)\}$ and the cumulative sample slack as $\mathcal{D}(X, f, \gamma) = \sum_{x \in X} d(x, f, \gamma)$ on a training set $X = (x_1, \dots, x_\ell)$ drawn i.i.d. from $P$ .

With probability at least $1 - \delta$ over the random draw of training sequences $X$ of size $\ell$ , for all $\gamma > 0$ and any $f \in \mathcal{F}$ :

$P\left\{ x \in \mathcal{X} : f(x) < \theta - \gamma \text{ and } x \notin X \right\} \le \frac{2}{\ell} \left( k + \log_2 \frac{1}{\delta} \right),$

where

$k = \left\lceil \log_2 \mathcal{N}\left(\frac{\gamma}{2}, \mathcal{F}, 2\ell\right) + \frac{64 (b-a) \mathcal{D}(X, f, \gamma)}{\gamma^2} \log_2\left( \frac{e \ell \gamma}{8 \mathcal{D}(X, f, \gamma)} \right) \log_2\left( \frac{32 \ell (b-a)^2}{\gamma^2} \right) \right\rceil,$

and $\mathcal{N}(\epsilon, \mathcal{F}, 2\ell) = \sup_{X' \in \mathcal{X}^{2\ell}} \mathcal{N}_{d_{X'}}(\epsilon, \mathcal{F})$ is the $\ell_\infty$ covering number of $\mathcal{F}$ at scale $\epsilon$ on samples of size $2\ell$ .

When applying this result to the single-class SVM with linear functions in feature space bounded by $\|w\| \le B = \sqrt{\alpha^T K \alpha}$ and setting $\theta + \gamma = \rho$ , the log covering number at scale $\gamma/2$ is bounded by $O\left( \frac{R^2 B^2}{\gamma^2} \log^2 \ell \right)$ , yielding an error bound on the probability of novel points falling outside the region $\{x : f(x) \ge 2\theta - \rho\}$ .
Knowl 5 — Separability from the Origin Under Gaussian RBF Kernels
theoretical result
For any training set $x_1, \dots, x_\ell \in \mathcal{X}$ , the mapped data points $\Phi(x_1), \dots, \Phi(x_\ell)$ in the feature space $\mathcal{F}$ induced by a Gaussian radial basis function (RBF) kernel,

$k(x, y) = \exp\left( -\frac{\|x - y\|^2}{c} \right), \quad c > 0,$

are strictly separable from the origin by a hyperplane.

This follows from two geometric properties:
1. All mapped points have unit length, since $\langle \Phi(x_i), \Phi(x_i) \rangle = k(x_i, x_i) = 1$ for all $i$ .
2. All pairwise inner products are strictly positive, $\langle \Phi(x_i), \Phi(x_j) \rangle = k(x_i, x_j) > 0$ for all $i, j$ , which implies that all mapped patterns reside in the same open orthant of $\mathcal{F}$ .
Knowl 6 — Invariance of Single-Class SVM Hyperplane to Outlier Movements Parallel to the Weight Vector
theoretical result
In the single-class SVM solution $(w, \rho)$ , local movements of outlier training points $x_i$ (points with slack $\xi_i > 0$ , for which the dual Lagrange multipliers are pinned at the upper bound $\alpha_i = \frac{1}{\nu \ell}$ ) parallel to the normal vector $w$ in feature space do not change the separating hyperplane.

Knowl 7 — Empirical Influence of nu and Kernel Width on Support Estimation

empirical result

Applying the single-class SVM to 2D synthetic datasets on the domain $[-1, 1]^2$ illustrates how the regularization parameter $\nu$ and the Gaussian kernel width $c$ govern the geometry of the support boundary, the margin $\rho / \|w\|$ , and the empirical fractions of support vectors (SVs) and outliers (OLs):

Parameter $\nu$	0.5	0.5	0.1	0.5
Kernel width $c$	0.5	0.5	0.5	0.1
Fraction SVs / OLs	0.54 / 0.43	0.59 / 0.47	0.24 / 0.03	0.65 / 0.38
Margin $\rho / \\|w\\|$	0.84	0.70	0.62	0.48

A large value of $\nu$ (e.g., $\nu = 0.5$ ) allows isolated peripheral data clusters to be ignored as outliers without warping the main support boundary. Decreasing $\nu$ to $0.1$ forces the boundary to expand to enclose these points. Alternatively, reducing the kernel width $c$ from $0.5$ to $0.1$ at fixed $\nu = 0.5$ analyzes the data at a finer length scale, causing the algorithm to model separate disjoint support components around the peripheral points.

Knowl 8 — Unsupervised Outlier Identification on the USPS Digit Dataset
empirical result
The single-class SVM was applied to identify atypical patterns and mislabelled examples in the USPS handwritten digit test set, which contains 2,007 images of size $16 \times 16$ pixels (256 dimensions). To enable the detection of mislabelled samples, each image vector was augmented with 10 indicator dimensions corresponding to class labels (giving 266 total dimensions).

Using a Gaussian kernel width of $c = 0.5 \times 256 = 128$ and an outlier parameter $\nu = 0.05$ (5%), training required 36 seconds on a Pentium II 450 MHz processor. Ranking the test set by the negative value of the SVM decision function $\langle w, \Phi(x) \rangle - \rho$ successfully isolated the 20 most atypical images in the dataset, which corresponded to severe segmentation artifacts, atypical writing styles, or ground-truth misclassifications.

Coverage note — All substantial theoretical propositions, generalization bounds, algorithm formulations, limiting behaviors, and empirical results from the paper have been included; no substantial contribution was omitted.

References

1.S. Ben-David and M. Lindenbaum. Learning distributions by their density levels: A paradigm for learning without a teacher. Journal of Computer and System Sciences, 55:171–182, 1997.
2.B. Schölkopf, C. Burges, and V. Vapnik. Extracting support data for a given task. In U. M. Fayyad and R. Uthurusamy, editors, Proceedings, First International Conference on Knowledge Discovery & Data Mining. AAAI Press, Menlo Park, CA, 1995.
3.B. Schölkopf, J. Platt, J. Shawe-Taylor, A.J. Smola, and R.C. Williamson. Estimating the support of a high-dimensional distribution. TR MSR 99 - 87, Microsoft Research, Redmond, WA, 1999.
4.B. Schölkopf, A. Smola, and K.-R. Müller. Kernel principal component analysis. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods — Support Vector Learning. MIT Press, Cambridge, MA, 1999. 327 – 352.
5.B. Schölkopf, R. Williamson, A. Smola, and J. Shawe-Taylor. Single-class support vector machines. In J. Buhmann, W. Maass, H. Ritter, and N. Tishby, editors, Unsupervised Learning, Dagstuhl-Seminar-Report 235, pages 19 – 20, 1999.
6.A. Smola, R. C. Williamson, S. Mika, and B. Schölkopf. Regularized principal manifolds. In Computational Learning Theory: 4th European Conference, volume 1572 of Lecture Notes in Artificial Intelligence, pages 214 – 229. Springer, 1999.
7.D.M.J. Tax and R.P.W. Duin. Data domain description by support vectors. In M. Verleysen, editor, Proceedings ESANN, pages 251 – 256, Brussels, 1999. D Facto.
8.V. Vapnik. Statistical Learning Theory. Wiley, New York, 1998.
9.V. Vapnik and A. Lerner. Pattern recognition using generalized portraits. Avtomatika i Telemekhanika, 24:774 – 780, 1963.

Citation

MLA

Schölkopf, B., et al. “Support Vector Method for Novelty Detection.”. NIPS, 1999, pp. 582–88, https://dblp.org/rec/conf/nips/ScholkopfWSSP99.

APA

Schölkopf, B., Williamson, R. C., Smola, A. J., Shawe-Taylor, J., & Platt, J. C. (1999). Support Vector Method for Novelty Detection. NIPS, 582–588. https://dblp.org/rec/conf/nips/ScholkopfWSSP99

Chicago

Schölkopf, B., R. C. Williamson, A. J. Smola, J. Shawe-Taylor, and J. C. Platt. 1999. “Support Vector Method for Novelty Detection.”. NIPS, 582–88. https://dblp.org/rec/conf/nips/ScholkopfWSSP99.

Harvard

Schölkopf, B. et al. (1999) “Support Vector Method for Novelty Detection.”, NIPS, pp. 582–588. Available at: https://dblp.org/rec/conf/nips/ScholkopfWSSP99.

Vancouver

1. Schölkopf B, Williamson RC, Smola AJ, Shawe-Taylor J, Platt JC (1999) Support Vector Method for Novelty Detection. In: NIPS. pp 582–588

BibTeX

<!doctype html><html lang="en"><head><title>Making sure you&#39;re not a bot!</title><link rel="stylesheet" href="/.within.website/x/xess/xess.min.css?cachebuster=v1.27.0"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="robots" content="noindex,nofollow"><style>
        body,
        html {
            height: 100%;
            display: flex;
            justify-content: center;
            align-items: center;
            margin-left: auto;
            margin-right: auto;
        }

        .centered-div {
            text-align: center;
        }

        #status {
            font-variant-numeric: tabular-nums;
        }

        #progress {
            display: none;
            width: 90%;
            width: min(20rem, 90%);
            height: 2rem;
            border-radius: 1rem;
            overflow: hidden;
            margin: 1rem 0 2rem;
            outline-offset: 2px;
            outline: #b16286 solid 4px;
        }

        .bar-inner {
            background-color: #b16286;
            height: 100%;
            width: 0;
            transition: width 0.25s ease-in;
        }
    	</style><script id="anubis_version" type="application/json">"v1.27.0"
</script><script id="anubis_challenge" type="application/json">{"rules":{"algorithm":"metarefresh","difficulty":1},"challenge":{"issuedAt":"2026-09-14T15:02:20.230922348+02:00","metadata":{"User-Agent":"ChapterPal/1.0 (mailto:[email protected]; https://chapterpal.com)","X-Real-Ip":"34.96.60.187"},"id":"01a0a002-e846-7e0a-a123-00662f8faeef","method":"metarefresh","randomData":"05f0e85603035a715594705bbdb3499abb4df8691ae84b88da2d55f1d657dc636dd0369c18bb40076951e75d716c9ac1bc5b7a3a1e01ca05b8713ef40ad4d1e5","policyRuleHash":"ac980f49c4d35fab","difficulty":1,"spent":false}}
</script><script id="anubis_base_prefix" type="application/json">""
</script><script id="anubis_public_url" type="application/json">""
</script></head><body id="top"><script type="ignore"><a href="/.within.website/x/cmd/anubis/api/honeypot/2c44fe67-8eff-4a02-955a-0bf6c67cc232/init">Don't click me</a></script><main><h1 id="title" class="centered-div">Making sure you&#39;re not a bot!</h1><div class="centered-div"><img id="image" style="width:100%;max-width:256px;" src="/.within.website/x/cmd/anubis/static/img/pensive.webp?cacheBuster=v1.27.0"> <img style="display:none;" style="width:100%;max-width:256px;" src="/.within.website/x/cmd/anubis/static/img/happy.webp?cacheBuster=v1.27.0"><p id="status">Loading...</p><p>Please wait a moment while we ensure the security of your connection.</p><meta http-equiv="refresh" content="2; url=/.within.website/x/cmd/anubis/api/pass-challenge?challenge=05f0e85603035a715594705bbdb3499abb4df8691ae84b88da2d55f1d657dc636dd0369c18bb40076951e75d716c9ac1bc5b7a3a1e01ca05b8713ef40ad4d1e5&amp;id=01a0a002-e846-7e0a-a123-00662f8faeef&amp;redir=%2Frec%2Fconf%2Fnips%2FScholkopfWSSP99.bib"></div><footer><div class="centered-div"><p>Protected by <a href="https://github.com/TecharoHQ/anubis">Anubis</a> From <a href="https://techaro.lol">Techaro</a>. Made with ❤️ in 🇨🇦.</p><p>Mascot design by <a href="https://bsky.app/profile/celphase.bsky.social">CELPHASE</a>.</p><p>This website is running Anubis version <code>v1.27.0</code>.</p></div></footer></main></body></html>

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

Support Vector Method for Novelty Detection

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Single-Class Support Vector Machine Formulation

Knowl 2 — Parameter nu as Bounds on Fractions of Support Vectors and Outliers

Knowl 3 — Limiting Behaviors of Single-Class SVM for Extreme Values of nu

Knowl 4 — PAC Generalization Error Bound for Support Estimation with Margin Slack

Knowl 5 — Separability from the Origin Under Gaussian RBF Kernels

Knowl 6 — Invariance of Single-Class SVM Hyperplane to Outlier Movements Parallel to the Weight Vector

Knowl 7 — Empirical Influence of nu and Kernel Width on Support Estimation

Knowl 8 — Unsupervised Outlier Identification on the USPS Digit Dataset

References

Citation

BibTeX

Access the Paper