Linear-time Algorithms for Pairwise Statistical Problems
Several key computational bottlenecks in machine learning involve pairwise distance computations, including all-nearest-neighbors (finding the nearest neighbor(s) for each point, e.g. in manifold learning) and kernel summations (e.g. in kernel density estimation or kernel machines). We consider the general, bichromatic case for these problems, in addition to the scientific problem of N-body potential calculation. In this paper we show for the first time O(N) worst case runtimes for practical algorithms for these problems based on the cover tree data structure (Beygelzimer, Kakade, Langford, 2006).
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningDensity EstimationSimilar Papers 제목 키워드 기반
Plug-and-play dual-tree algorithm runtime analysis
Numerous machine learning algorithms contain pairwise statistical problems at their core---that is, tasks that require computations over all pairs of input points if implemented naively. Often, tree structures are used t…
Density EstimationGeneralization Guarantee of SGD for Pairwise Learning
Recently, there is a growing interest in studying pairwise learning since it includes many important machine learning tasks as specific examples, e.g., metric learning, AUC maximization and ranking. While stochastic grad…
Generalization BoundsMetric LearningCMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines
In Software Product Lines (SPLs) it may be difficult or even impossible to test all the products of the family because of the large number of valid feature combinations that may exist. Thus, we want to find a minimal sub…
Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory
Pairwise learning is essential in machine learning, especially for problems involving loss functions defined on pairs of training examples. Online gradient descent (OGD) algorithms have been proposed to handle online pai…
Efficient Pairwise Learning Using Kernel Ridge Regression: an Exact Two-Step Method
Pairwise learning or dyadic prediction concerns the prediction of properties for pairs of objects. It can be seen as an umbrella covering various machine learning problems such as matrix completion, collaborative filteri…
Collaborative FilteringMatrix CompletionMulti-Task LearningPrediction+3