Last updated: 22.06.06
This software provides implementations of various algorithms for max-product and sum-product n-body computations for 2-particle interactions. Good background material and links related to these computational problems are available here.
For sum-product, the available algorithms are:
For max-product, the available algorithms are:
To run an nbody sum or max algorithm from Matlab, simply call:
nbody_methods(X, Y, w, P, kernel_name,
influence_descriptor, weights_descriptor,
algorithm, computation_type,
relative_error,absolute_error);
where
X = D x NX matrix of source particles
Y = D x NY matrix of target particles
w = NX x 1 vector of source particle weights
P = 1 x NP array of kernel parameters
kernel_name = one of {'gaussian','lpq','laplacian','sigmoid','polynomial','dog'}
influence_descriptor = one of {'positive','negative','mixed'}
weights_descriptor = one of {'positive','negative','mixed'}
algorithm = one of {'kdtree','anchors','naive','fgt','dt'}
computation_type = one of {'sum','max'}
relative_error = the desired relative error
absolute_error = the desired absolute error
For example, to run the kd-tree dualtree sum-product algorithm with a gaussian kernel with bandwidth = 2, and using positive weights, you could enter:
nbody_methods(X, Y, w, 2, 'gaussian', 'positive', 'positive', 'kdtree', 'sum', 1e-3, 1e-3);
For more detailed information on how to use these methods, look here. There are also some demonstration applications available here.
Note regarding error:
The speed of the approximation algorithms relies on only satisfying the computational request to a given error tolerance. In particular, the result for each target particle satisfies the given relative error OR the given absolute error - not necessarily both.
The dual-tree algorithm for n-body computations on data organized into a tree was introduced by Gray and Moore in [1].
The kd-tree structure splits boxes along the median of the dimension with the greatest range.
The anchors hierarchy is described in [2].
The fast Gauss transform is described in [3,4].
The distance transform is described in [5,6].
In-depth discussion of sum-product and max-product methods directly related to these algorithms is available in [7,8,9,10,11].
In addition, the kd-tree creation implementation uses Wirth's kth-smallest algorithm, described in [12] and implemented by N. Devillard.
Dustin Lang, Mike Klaas, Firas Hamze, Anthony Lee
[1] A. G. Gray and A. W. Moore. `N-Body' problems in statistical learning. In Advances in Neural Information Processing Systems 4, pages 521-527, 2000.
[2] Andrew Moore. The Anchors Hierarchy: Using the triangle inequality to survive high dimensional data. Technical Report CMU-RI-TR-00-05, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, February 2000.
[3] L. Greengard and J. Strain. The fast Gauss transform. SIAM Journal of Scientific Statistical Computing, 12(1):79-94, 1991.
[4] L. Greengard and X. Sun. A new version of the Fast Gauss Transform. Documenta Mathematica, ICM(3):575-584, 1998.
[5] P. Felzenszwalb and D. Huttenlocher. Efficient belief propagation for early vision. In CVPR, 2004.
[6] Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Distance transforms of sampled functions. Technical Report TR2004-1963, Cornell Computing and Information Science, 2004.
[7] Dustin Lang. Fast methods for inference in graphical models (and beat tracking the graphical model way). Master's thesis, University of British Columbia, 2004.
[8] Mike Klaas. Exorcising N-squared stigmata in sequential Monte Carlo. Master's thesis, University of British Columbia, 2005.
[9] Dustin Lang, Mike Klaas and Nando de Freitas. Empirical Testing of Fast Kernel Density Estimation Algorithms. Technical Report UBC TR-2005-03, University of British Columbia, 2005.
[10] Mike Klaas, Dustin Lang and Nando de Freitas. Fast Maximum a Posteriori Inference in Monte Carlo State Spaces. Aritifical Intelligence and Statistics, 2005.
[11] Nando de Freitas, Yang Wang, Maryam Mahdaviani and Dustin Lang. Fast Krylov Methods for N-Body Learning. NIPS 2005.
[12] Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice-Hall, Inc., Englewood Cliffs (Nov. 1975).
Questions, bugs or comments? Email Anthony