| Abstract | Many machine learning algorithms require the summation of Gaussian kernelfunctions, an expensive operation if implemented straightforwardly. Several meth-
ods have been proposed to reduce the computational complexity of evaluating such
sums, including tree and analysis based methods. These achieve varying speedups
depending on the bandwidth, dimension, and prescribed error, making the choice
between methods difficult for machine learning tasks. We provide an algorithm
that combines tree methods with the Improved Fast Gauss Transform (IFGT). As
originally proposed the IFGT suffers from two problems: (1) the Taylor series
expansion does not perform well for very low bandwidths, and (2) parameter se-
lection is not trivial and can drastically affect performance and ease of use. We
address the first problem by employing a tree data structure, resulting in four eval-
uation methods whose performance varies based on the distribution of sources and
targets and input parameters such as desired accuracy and bandwidth. To solve the
second problem, we present an online tuning approach that results in a black box
method that automatically chooses the evaluation method and its parameters to
yield the best performance for the input data, desired accuracy, and bandwidth.
In addition, the new IFGT parameter selection approach allows for tighter error
bounds. Our approach chooses the fastest method at negligible additional cost,
and has superior performance in comparisons with previous approaches.
|
