2015 RobustTreecodeApproximationforK

• (March et al., 2015) ⇒ William B. March, Bo Xiao, Sameer Tharakan, Chenhan D. Yu, and George Biros. (2015). “Robust Treecode Approximation for Kernel Machines.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783272

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Robust+Treecode+Approximation+for+Kernel+Machines
• http://dl.acm.org/citation.cfm?id=2783258.2783272&preflayout=flat#citedby

Quotes

Author Keywords

• Bandwidth selection; general; kernel regression; kernel summations; nystrom methods; statistical; treecodes

Abstract

Since exact evaluation of a kernel matrix requires O (N2) work, scalable learning algorithms using kernels must approximate the kernel matrix. This approximation must be robust to the kernel parameters, for example the bandwidth for the Gaussian kernel. We consider two approximation methods: Nystrom and an algebraic treecode developed in our group. Nystrom methods construct a global low-rank approximation of the kernel matrix. Treecodes approximate just the off-diagonal blocks, typically using a hierarchical decomposition.

We present a theoretical error analysis of our treecode and relate it to the error of Nystrom methods. Our analysis reveals how the block-rank structure of the kernel matrix controls the performance of the treecode. We evaluate our treecode by comparing it to the classical Nystrom method and a state-of-the-art fast approximate Nystrom method. We test the kernel matrix approximation accuracy for several different bandwidths and datasets. On the MNIST2M dataset (2M points in 784 dimensions) for a Gaussian kernel with bandwidth h=1, the Nystrom methods' error is over 90% whereas our treecode delivers error1%.

We also test the performance of the three methods on binary classification using two models: a Bayes classifier and kernel ridge regression. Our evaluation reveals the existence of bandwidth values that should be examined in cross-validation but whose corresponding kernel matrices cannot be approximated well by Nystrom methods. In contrast, the treecode scheme performs much better for these values.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 RobustTreecodeApproximationforK	William B. March Bo Xiao Sameer Tharakan Chenhan D. Yu George Biros			Robust Treecode Approximation for Kernel Machines				10.1145/2783258.2783272		2015