Estimating the support of a high-dimensional distribution. (English) Zbl 1009.62029

Schölkopf, Bernhard; Platt, John C.; Shawe-Taylor, John; Smola, Alex J.; Williamson, Robert C.

Neural Comput. 13, No. 7, 1443-1471 (2001).

Summary: Suppose you are given some data set 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 value between 0 and 1.
We propose a method to approach this problem by trying to estimate a function \(f\) that 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. The expansion coefficients are found by solving a quadratic programming problem, which we do by carrying out sequential optimization over pairs of input patterns. We also 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 unlabeled data.

MSC:

62G07	Density estimation
90C90	Applications of mathematical programming

Keywords:

quadratic programming

Software:

SVMlight

References:

[1]	DOI: 10.1006/jcss.1997.1507 · Zbl 0880.68106 · doi:10.1006/jcss.1997.1507
[2]	DOI: 10.1214/aos/1030741073 · Zbl 0897.62034 · doi:10.1214/aos/1030741073
[3]	DOI: 10.1137/0138038 · Zbl 0479.62028 · doi:10.1137/0138038
[4]	DOI: 10.1214/aos/1176348670 · Zbl 0757.60012 · doi:10.1214/aos/1176348670
[5]	Gayraud G., Mathematical Methods of Statistics 6 (1) pp 26– (1997) · Zbl 0873.62038
[6]	DOI: 10.1162/089976698300017269 · doi:10.1162/089976698300017269
[7]	DOI: 10.2307/2289162 · Zbl 0607.62045 · doi:10.2307/2289162
[8]	DOI: 10.1016/0047-259X(91)90106-C · Zbl 0739.62042 · doi:10.1016/0047-259X(91)90106-C
[9]	DOI: 10.1006/jmva.1995.1067 · Zbl 0847.62027 · doi:10.1006/jmva.1995.1067
[10]	DOI: 10.1214/aos/1176324626 · Zbl 0841.62045 · doi:10.1214/aos/1176324626
[11]	DOI: 10.2307/2286331 · Zbl 0428.62040 · doi:10.2307/2286331
[12]	DOI: 10.1162/089976600300015565 · doi:10.1162/089976600300015565
[13]	Shawe-Taylor J., IEEE Transactions on Information Theory. Submitted. (2000)
[14]	DOI: 10.1016/S0893-6080(98)00032-X · doi:10.1016/S0893-6080(98)00032-X
[15]	DOI: 10.1109/6.769272 · doi:10.1109/6.769272
[16]	DOI: 10.1214/aos/1069362732 · Zbl 0881.62039 · doi:10.1214/aos/1069362732
[17]	Williamson R. C., IEEE Transactions on Information Theory (in press). (1998)