Error Bounds on the SCISSORS Approximation Method

doi:10.1021/ci200251a

Return

Error Bounds on the SCISSORS Approximation Method

2011-09-08

Imran S. Haque

Vijay S. Pande *

DOI：10.1021/ci200251a

Original

Original request for help

Save

Abstract

En 中文

The SCISSORS method for approximating chemical similarities has shown excellent empirical performance on a number of real-world chemical data sets but lacks theoretically proven bounds on its worst-case error performance. This paper first proves reductions showing SCISSORS to be equivalent to two previous kernel methods: kernel principal components analysis and the rank-k Nystrom approximation of a Gram matrix. These reductions allow the use of generalization bounds on these techniques to show that the expected error in SCISSORS approximations of molecular similarity kernels is bounded in expected pairwise inner product error, in matrix 2-norm and Frobenius norm for full kernel matrix approximations and in root-mean-square deviation for approximated matrices. Finally, we show that the actual performance of SCISSORS is significantly better than these worst-case bounds, indicating that chemical space is well-structured for chemical sampling algorithms.

Keywords:

CHEMICAL SIMILARITIES

NYSTROM METHOD

GRAM MATRIX

KERNEL

LINGO