q-OCSVM: A q-Quantile Estimator for High-Dimensional Distributions
In this paper we introduce a novel method that can efficiently estimate a family of hierarchical dense sets in high-dimensional distributions. Our method can be regarded as a natural extension of the one-class SVM (OCSVM) algorithm that finds multiple parallel separating hyperplanes in a reproducing kernel Hilbert space. We call our method q-OCSVM, as it can be used to estimate q quantiles of a highdimensional distribution. For this purpose, we introduce a new global convex optimization program that finds all estimated sets at once and show that it can be solved efficiently. We prove the correctness of our method and present empirical results that demonstrate its superiority over existing methods.
The one-class SVM (OCSVM) algorithm, due to by 
      Scholkopf et al, finds a hyperplane in feature space that maximizes the 
      separation between the training set and the origin. The original OCSVM 
      paper showed that, for suitable choices of kernel and slack variable 
      penalty, the function returned by OCSVM is an indictor of the q-support* 
      of the data distribution, i.e., a set of minimum volume that contains a q 
      fraction of the distribution. A good way to characterize a distribution is 
      to estimate its q-support for many values of q, and one could simply run 
      OCSVM many times to generate these estimates -- this paper calls that 
      algorithm I-OCSVM. However, these estimates won't necessarily be nested, 
      while the actual q-supports must be. This paper describes an extension of 
      the OCSVM algorithm, called q-OCSVM, for computing nested estimates of the 
      q-supports of a distribution. Other papers have also proposed extensions 
      of OCSVM with this property, but this paper's approach for enforcing the 
      nesting constraint is very simple: the learned hyperplanes are required to 
      be parallel, i.e., they only differ in their bias term. The paper modifies 
      the OCSVM optimization problem to include this parallel constraint, and 
      shows that the dual is still solvable in polynomial time for very 
      high-dimensional feature spaces, via the kernel trick. The theoretical 
      results in Section 4, which prove that the q-OCSVM algorithm 
      asymptotically estimates the q-supports, are straightforward extensions of 
      the results found in the original OCSVM paper. The experimental results 
      show that the q-OCSVM algorithm outperforms existing algorithms, including 
      I-OCSVM, for several datasets, though sometimes the improvement is small. 
      Some might regard the simplicity of the q-OCSVM extension as a 
      reason not to accept the paper, but I view it as a point in the paper's 
      favor. However, I do wonder whether an even simpler approach might work 
      too. For example, I accept that forcing all the hyperplanes to be parallel 
      acts as a kind of regularizer, and thus helps with overfitting. But 
      couldn't this effect be achieved with the I-OCSVM algorithm by just 
      increasing the penalty on the norm of the weight vector? Admittedly, this 
      still would not guarantee that the estimated q-supports are nested. Which 
      leads to a question: Does I-OCSVM intersect the q-supports that it learns, 
      as suggested in the Introduction? Also, is q-OCSVM faster to train than 
      I-OCSVM? It seems like it might be, since it's one QP and not several QPs. 
      If so, that would be worth mentioning. Finally, instead of setting \nu = 1 
      - \alpha, what if we used a held-out validation set to choose a value for 
      \nu that optimizes coverage ratio? It seems that might improve the results 
      for all algorithms. The results in Figures 2 and 3 are averaged 
      over 61 and 21 datasets, respectively, but the plots do not contain error 
      bars, so it's hard to judge the significance of the results. On the other 
      hand, the fact that the q-OCSVM algorithm dominates the others for all 
      values of q is encouraging. Also, I think the left- and right-hand side of 
      each figure contain the same information, and thus seem redundant. 
      The paper is clear and well-written, and the relationship to 
      previous work is well-explained. Figure 1 is a very helpful illustration. 
      For completeness, it might be good to cite some work on estimating the 
      quantiles of a _conditional_ distribution. Search for "nonparametric 
      quantile regression" or "kernel quantile regression". * The term 
      "q-support" is mine, not the paper's.