dualtree_kde.h File Reference

This file contains an implementation of kernel density estimation for a linkable library component. More...

Include dependency graph for dualtree_kde.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	DualtreeKde< TKernelAux >
	A computation class for dual-tree based kernel density estimation. More...
Variables
const fx_module_doc	kde_doc
const fx_entry_doc	kde_entries []
const fx_module_doc	kde_main_doc
const fx_entry_doc	kde_main_entries []
const fx_submodule_doc	kde_main_submodules []

---

Detailed Description

This file contains an implementation of kernel density estimation for a linkable library component.

It implements a rudimentary depth-first dual-tree algorithm with finite difference and series-expansion approximations, using the formalized GNP framework by Ryan and Garry. Currently, it supports a fixed-bandwidth kernel density estimation with no multi-bandwidth optimizations. We assume that users will be able to cross-validate for the optimal bandwidth using a black-box optimizer which is not implemented in this code.

For more details on mathematical derivations, please take a look at the published conference papers (in chronological order):

inproceedings{DBLP:conf/sdm/GrayM03, author = {Alexander G. Gray and Andrew W. Moore}, title = {Nonparametric Density Estimation: Toward Computational Tractability}, booktitle = {SDM}, year = {2003}, ee = {http://www.siam.org/meetings/sdm03/proceedings/sdm03_19.pdf}, crossref = {DBLP:conf/sdm/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }

misc{ gray03rapid, author = "A. Gray and A. Moore", title = "Rapid evaluation of multiple density models", booktitle = "In C. M. Bishop and B. J. Frey, editors, Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics", year = "2003", url = "citeseer.ist.psu.edu/gray03rapid.html" }

incollection{NIPS2005_570, title = {Dual-Tree Fast Gauss Transforms}, author = {Dongryeol Lee and Alexander Gray and Andrew Moore}, booktitle = {Advances in Neural Information Processing Systems 18}, editor = {Y. Weiss and B. Sch"{o}lkopf and J. Platt}, publisher = {MIT Press}, address = {Cambridge, MA}, pages = {747--754}, year = {2006} }

inproceedings{DBLP:conf/uai/LeeG06, author = {Dongryeol Lee and Alexander G. Gray}, title = {Faster Gaussian Summation: Theory and Experiment}, booktitle = {UAI}, year = {2006}, crossref = {DBLP:conf/uai/2006}, bibsource = {DBLP, http://dblp.uni-trier.de} }

Author:

Dongryeol Lee (dongryel)

See also:

kde_main.cc

Bug:

No known bugs.

Definition in file dualtree_kde.h.

---

Variable Documentation

const fx_module_doc kde_doc

Initial value:

 {
  kde_entries, NULL,
  "Performs dual-tree kernel density estimate computation.\n"
}

Definition at line 148 of file dualtree_kde.h.

const fx_entry_doc kde_entries[]

Initial value:

 {
  {"bandwidth", FX_PARAM, FX_DOUBLE, NULL,
   "  The bandwidth parameter.\n"},
  {"do_naive", FX_PARAM, FX_BOOL, NULL,
   "  Whether to perform naive computation as well.\n"},
  {"dwgts", FX_PARAM, FX_STR, NULL,
   "  A file that contains the weight of each point. If missing, will\
 assume uniform weight\n"},
  {"fast_kde_output", FX_PARAM, FX_STR, NULL,
   "  A file to receive the results of computation.\n"},
  {"kernel", FX_PARAM, FX_STR, NULL,
   "  The type of kernel to use.\n"},
  {"knn", FX_PARAM, FX_INT, NULL,
   "  The number of k-nearest neighbor to use for variable bandwidth.\n"},
  {"loo", FX_PARAM, FX_BOOL, NULL,
   "  Whether to output the density estimates using leave-one-out.\n"},
  {"mode", FX_PARAM, FX_STR, NULL,
   "  Fixed bandwidth or variable bandwidth mode.\n"},
  {"multiplicative_expansion", FX_PARAM, FX_BOOL, NULL,
   "  Whether to do O(p^D) kernel expansion instead of O(D^p).\n"},
  {"probability", FX_PARAM, FX_DOUBLE, NULL,
   "  The probability guarantee that the relative error accuracy holds.\n"},
  {"relative_error", FX_PARAM, FX_DOUBLE, NULL,
   "  The required relative error accuracy.\n"},
  {"threshold", FX_PARAM, FX_DOUBLE, NULL,
   "  If less than this value, then absolute error bound.\n"},
  {"scaling", FX_PARAM, FX_STR, NULL,
   "  The scaling option.\n"},
  FX_ENTRY_DOC_DONE
}

Definition at line 117 of file dualtree_kde.h.

const fx_module_doc kde_main_doc

Initial value:

 {
  kde_main_entries, kde_main_submodules,
  "This is the driver for the kernel density estimator.\n"
}

Definition at line 159 of file dualtree_kde.h.

const fx_entry_doc kde_main_entries[]

Initial value:

 {
  {"data", FX_REQUIRED, FX_STR, NULL,
   "  A file containing reference data.\n"},
  {"query", FX_PARAM, FX_STR, NULL,
   "  A file containing query data (defaults to data).\n"},
  FX_ENTRY_DOC_DONE
}

Definition at line 109 of file dualtree_kde.h.

const fx_submodule_doc kde_main_submodules[]

Initial value:

 {
  {"kde", &kde_doc,
   "  Responsible for dual-tree kernel density estimate computation.\n"},
  FX_SUBMODULE_DOC_DONE
}

Definition at line 153 of file dualtree_kde.h.