iKernel: Exact Indexing for Support Vector Machines

Abstract

SVM (Support Vector Machine) is a well-established machine learning methodology popularly used for learning classification, regression, and ranking functions. Especially, SVM for rank learning has been applied to various applications including search engines or relevance feedback systems. A ranking function F learned by SVM becomes the query in some search engines: A relevance function F is learned from the user's feedback which expresses the user's search intention, and top-k results are found by evaluating the entire database by F. This paper proposes an exact indexing solution for the SVM function queries, which is to find top-k results without evaluating the entire database. Indexing for SVM faces new challenges, that is, an index must be built on the kernel space (SVM feature space) where (1) data points are invisible and (2) the distance function changes with queries. Because of that, existing top-k query processing algorithms, or existing metric-based or reference-based indexing methods are not applicable. We first propose key geometric properties of the kernel space - ranking instability and ordering stability - which is crucial for building indices in the kernel space. Based on them, we develop an index structure iKernel and processing algorithms. We then present clustering techniques in the kernel space to enhance the pruning effectiveness of the index. According to our experiments, iKernel is highly effective overall producing 1-5% of evaluation ratio on large data sets. (C) 2013 Elsevier Inc. All rights reserved.