Deconstructing Kernel Machines

Abstract

This paper studies the following problem: Given an SVM (kernel)-based binary classifier C as a black-box oracle, how much can we learn of its internal working by querying it? Specifically, we assume the feature space ℝ^ d is known and the kernel machine has m support vectors such that d  >  m (or d  > >  m ), and in addition, the classifier C is laconic in the sense that for a feature vector, it only provides a predicted label (±1) without divulging other information such as margin or confidence level. We formulate the problem of understanding the inner working of C as characterizing the decision boundary of the classifier, and we introduce the simple notion of bracketing to sample points on the decision boundary within a prescribed accuracy. For the five most common types of kernel function, linear, quadratic and cubic polynomial kernels, hyperbolic tangent kernel and Gaussian kernel, we show that with O ( dm ) number of queries, the type of kernel function and the (kernel) subspace spanned by the support vectors can be determined. In particular, for polynomial kernels, additional O ( m ^3) queries are sufficient to reconstruct the entire decision boundary, providing a set of quasi-support vectors that can be used to efficiently evaluate the deconstructed classifier. We speculate briefly on the future application potential of deconstructing kernel machines and we present experimental results validating the proposed method.