An implementation of fast exact max-kernel search. More...

Inheritance diagram for mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >:

[legend]

Classes
struct	CandidateCmp
	Compare two candidates based on the value. More...

Public Types
typedef TreeType< metric::IPMetric< KernelType >, FastMKSStat, MatType >	Tree
	Convenience typedef. More...

Public Member Functions
	FastMKS (const bool singleMode=false, const bool naive=false)
	Create the FastMKS object with an empty reference set and default kernel. More...

	FastMKS (const MatType &referenceSet, const bool singleMode=false, const bool naive=false)
	Create the FastMKS object with the given reference set (this is the set that is searched). More...

	FastMKS (const MatType &referenceSet, KernelType &kernel, const bool singleMode=false, const bool naive=false)
	Create the FastMKS object using the reference set (this is the set that is searched) with an initialized kernel. More...

	FastMKS (Tree *referenceTree, const bool singleMode=false)
	Create the FastMKS object with an already-initialized tree built on the reference points. More...

	FastMKS (const FastMKS &other)
	Copy the parameters of the given model. More...

	FastMKS (FastMKS &&other)
	Take ownership of the given model. More...

	~FastMKS ()
	Destructor for the FastMKS object. More...

const metric::IPMetric< KernelType > &	Metric () const
	Get the inner-product metric induced by the given kernel. More...

metric::IPMetric< KernelType > &	Metric ()
	Modify the inner-product metric induced by the given kernel. More...

bool	Naive () const
	Get whether or not brute-force (naive) search is used. More...

bool &	Naive ()
	Modify whether or not brute-force (naive) search is used. More...

FastMKS &	operator= (const FastMKS &other)
	Assign this model to be a copy of the given model. More...

void	Search (const MatType &querySet, const size_t k, arma::Mat< size_t > &indices, arma::mat &kernels)
	Search for the points in the reference set with maximum kernel evaluation to each point in the given query set. More...

void	Search (Tree *querySet, const size_t k, arma::Mat< size_t > &indices, arma::mat &kernels)
	Search for the points in the reference set with maximum kernel evaluation to each point in the query set corresponding to the given pre-built query tree. More...

void	Search (const size_t k, arma::Mat< size_t > &indices, arma::mat &products)
	Search for the maximum inner products of the query set (or if no query set was passed, the reference set is used). More...

template<typename Archive >
void	Serialize (Archive &ar, const unsigned int)
	Serialize the model. More...

bool	SingleMode () const
	Get whether or not single-tree search is used. More...

bool &	SingleMode ()
	Modify whether or not single-tree search is used. More...

void	Train (const MatType &referenceSet)
	"Train" the FastMKS model on the given reference set (this will just build a tree, if the current search mode is not naive mode). More...

void	Train (const MatType &referenceSet, KernelType &kernel)
	"Train" the FastMKS model on the given reference set and use the given kernel. More...

void	Train (Tree *referenceTree)
	Train the FastMKS model on the given reference tree. More...

Private Types
typedef std::pair< double, size_t >	Candidate
	Candidate represents a possible candidate point (value, index). More...

typedef std::priority_queue< Candidate, std::vector< Candidate >, CandidateCmp >	CandidateList
	Use a priority queue to represent the list of candidate points. More...

Private Attributes
metric::IPMetric< KernelType >	metric
	The instantiated inner-product metric induced by the given kernel. More...

bool	naive
	If true, naive (brute-force) search is used. More...

const MatType *	referenceSet
	The reference dataset. More...

Tree *	referenceTree
	The tree built on the reference dataset. More...

bool	setOwner
	If true, we own the dataset. This happens in only a few situations. More...

bool	singleMode
	If true, single-tree search is used. More...

bool	treeOwner
	If true, this object created the tree and is responsible for it. More...

Detailed Description

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>
class mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >

An implementation of fast exact max-kernel search.

Given a query dataset and a reference dataset (or optionally just a reference dataset which is also used as the query dataset), fast exact max-kernel search finds, for each point in the query dataset, the k points in the reference set with maximum kernel value K(p_q, p_r), where k is a specified parameter and K() is a Mercer kernel.

For more information, see the following paper.

@inproceedings{curtin2013fast,
  title={Fast Exact Max-Kernel Search},
  author={Curtin, Ryan R. and Ram, Parikshit and Gray, Alexander G.},
  booktitle={Proceedings of the 2013 SIAM International Conference on Data
      Mining (SDM 13)},
  year={2013}
}

This class allows specification of the type of kernel and also of the type of tree. FastMKS can be run on kernels that work on arbitrary objects – however, this only works with cover trees and other trees that are built only on points in the dataset (and not centroids of regions or anything like that).

Template Parameters

KernelType	Type of kernel to run FastMKS with.
MatType	Type of data matrix (usually arma::mat).
TreeType	Type of tree to run FastMKS with; it must satisfy the TreeType policy API.

Definition at line 62 of file fastmks.hpp.

Member Typedef Documentation

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

typedef std::pair<double, size_t> mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Candidate

private

Candidate represents a possible candidate point (value, index).

Definition at line 274 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

typedef std::priority_queue<Candidate, std::vector<Candidate>, CandidateCmp> mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::CandidateList

private

Use a priority queue to represent the list of candidate points.

Definition at line 286 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

typedef TreeType<metric::IPMetric<KernelType>, FastMKSStat, MatType> mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Tree

Convenience typedef.

Definition at line 66 of file fastmks.hpp.

Constructor & Destructor Documentation

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::FastMKS	(	const bool	singleMode = `false`,
		const bool	naive = `false`
	)

Create the FastMKS object with an empty reference set and default kernel.

Make sure to call Train() before Search() is called!

Parameters

singleMode	Whether or not to run single-tree search.
naive	Whether or not to run brute-force (naive) search.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::FastMKS	(	const MatType &	referenceSet,
		const bool	singleMode = `false`,
		const bool	naive = `false`
	)

Create the FastMKS object with the given reference set (this is the set that is searched).

Optionally, specify whether or not single-tree search or naive (brute-force) search should be used.

Parameters

referenceSet	Set of reference data.
singleMode	Whether or not to run single-tree search.
naive	Whether or not to run brute-force (naive) search.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::FastMKS	(	const MatType &	referenceSet,
		KernelType &	kernel,
		const bool	singleMode = `false`,
		const bool	naive = `false`
	)

Create the FastMKS object using the reference set (this is the set that is searched) with an initialized kernel.

This is useful for when the kernel stores state. Optionally, specify whether or not single-tree search or naive (brute-force) search should be used.

Parameters

referenceSet	Reference set of data for FastMKS.
kernel	Initialized kernel.
single	Whether or not to run single-tree search.
naive	Whether or not to run brute-force (naive) search.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::FastMKS	(	Tree *	referenceTree,
		const bool	singleMode = `false`
	)

Create the FastMKS object with an already-initialized tree built on the reference points.

Be sure that the tree is built with the metric type IPMetric<KernelType>. Optionally, whether or not to run single-tree search can be specified. Brute-force search is not available with this constructor since a tree is given (use one of the other constructors).

Parameters

referenceTree	Tree built on reference data.
single	Whether or not to run single-tree search.
naive	Whether or not to run brute-force (naive) search.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::FastMKS ( const FastMKS< KernelType, MatType, TreeType > & other )

Copy the parameters of the given model.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::FastMKS ( FastMKS< KernelType, MatType, TreeType > && other )

Take ownership of the given model.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::~FastMKS ( )

Destructor for the FastMKS object.

Member Function Documentation

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

const metric::IPMetric<KernelType>& mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Metric ( ) const

inline

Get the inner-product metric induced by the given kernel.

Definition at line 236 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

metric::IPMetric<KernelType>& mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Metric ( )

inline

Modify the inner-product metric induced by the given kernel.

Definition at line 238 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Naive ( ) const

inline

Get whether or not brute-force (naive) search is used.

Definition at line 246 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool& mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Naive ( )

inline

Modify whether or not brute-force (naive) search is used.

Definition at line 248 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

FastMKS& mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::operator= ( const FastMKS< KernelType, MatType, TreeType > & other )

Assign this model to be a copy of the given model.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Search	(	const MatType &	querySet,
		const size_t	k,
		arma::Mat< size_t > &	indices,
		arma::mat &	kernels
	)

Search for the points in the reference set with maximum kernel evaluation to each point in the given query set.

The resulting kernel evaluations are stored in the kernels matrix, and the corresponding point indices are stored in the indices matrix. The results for each point in the query set are stored in the corresponding column of the kernels and products matrices; for instance, the index of the point with maximum kernel evaluation to point 4 in the query set will be stored in row 0 and column 4 of the indices matrix.

If querySet only contains a few points, the extra overhead of building a tree to perform dual-tree search may not be warranted, and it may be faster to use single-tree search, either by setting singleMode to false in the constructor or with SingleMode().

Parameters

querySet	Set of query points (can be a single point).
k	The number of maximum kernels to find.
indices	Matrix to store resulting indices of max-kernel search in.
kernels	Matrix to store resulting max-kernel values in.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Search	(	Tree *	querySet,
		const size_t	k,
		arma::Mat< size_t > &	indices,
		arma::mat &	kernels
	)

Search for the points in the reference set with maximum kernel evaluation to each point in the query set corresponding to the given pre-built query tree.

The resulting kernel evaluations are stored in the kernels matrix, and the corresponding point indices are stored in the indices matrix. The results for each point in the query set are stored in the corresponding column of the kernels and products matrices; for instance, the index of the point with maximum kernel evaluation to point 4 in the query set will be stored in row 0 and column 4 of the indices matrix.

This will throw an exception if called while the FastMKS object has 'single' set to true.

Be aware that if your tree modifies the original input matrix, the results here are with respect to the modified input matrix (that is, queryTree->Dataset()).

Parameters

queryTree	Tree built on query points.
k	The number of maximum kernels to find.
indices	Matrix to store resulting indices of max-kernel search in.
kernels	Matrix to store resulting max-kernel values in.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Search	(	const size_t	k,
		arma::Mat< size_t > &	indices,
		arma::mat &	products
	)

Search for the maximum inner products of the query set (or if no query set was passed, the reference set is used).

The resulting maximum inner products are stored in the products matrix and the corresponding point indices are stores in the indices matrix. The results for each point in the query set are stored in the corresponding column of the indices and products matrices; for instance, the index of the point with maximum inner product to point 4 in the query set will be stored in row 0 and column 4 of the indices matrix.

Parameters

k	The number of maximum kernels to find.
indices	Matrix to store resulting indices of max-kernel search in.
products	Matrix to store resulting max-kernel values in.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

template<typename Archive >

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Serialize	(	Archive &	ar,
		const unsigned	int
	)

Serialize the model.

Referenced by mlpack::fastmks::FastMKS< kernel::EpanechnikovKernel >::Naive().

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::SingleMode ( ) const

inline

Get whether or not single-tree search is used.

Definition at line 241 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool& mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::SingleMode ( )

inline

Modify whether or not single-tree search is used.

Definition at line 243 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Train ( const MatType & referenceSet )

"Train" the FastMKS model on the given reference set (this will just build a tree, if the current search mode is not naive mode).

Parameters

referenceSet Set of reference points.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Train	(	const MatType &	referenceSet,
		KernelType &	kernel
	)

"Train" the FastMKS model on the given reference set and use the given kernel.

This will just build a tree and replace the metric, if the current search mode is not naive mode.

Parameters

referenceSet	Set of reference points.
kernel	Kernel to use for search.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

void mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::Train ( Tree * referenceTree )

Train the FastMKS model on the given reference tree.

This takes ownership of the tree, so you do not need to delete it! This will throw an exception if the model is searching in naive mode (i.e. if Naive() == true).

Parameters

tree	Tree to use as reference data.

Member Data Documentation

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

metric::IPMetric<KernelType> mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::metric

private

The instantiated inner-product metric induced by the given kernel.

Definition at line 271 of file fastmks.hpp.

Referenced by mlpack::fastmks::FastMKS< kernel::EpanechnikovKernel >::Metric().

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::naive

private

If true, naive (brute-force) search is used.

Definition at line 268 of file fastmks.hpp.

Referenced by mlpack::fastmks::FastMKS< kernel::EpanechnikovKernel >::Naive().

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

const MatType* mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::referenceSet

private

The reference dataset.

We never own this; only the tree or a higher level does.

Definition at line 257 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

Tree* mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::referenceTree

private

The tree built on the reference dataset.

Definition at line 259 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::setOwner

private

If true, we own the dataset. This happens in only a few situations.

Definition at line 263 of file fastmks.hpp.

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::singleMode

private

If true, single-tree search is used.

Definition at line 266 of file fastmks.hpp.

Referenced by mlpack::fastmks::FastMKS< kernel::EpanechnikovKernel >::SingleMode().

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>

bool mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >::treeOwner

private

If true, this object created the tree and is responsible for it.

Definition at line 261 of file fastmks.hpp.

The documentation for this class was generated from the following file:

src/mlpack/methods/fastmks/fastmks.hpp

Classes

Public Types

Public Member Functions

Private Types

Private Attributes

Detailed Description

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree> class mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename KernelType, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::StandardCoverTree>
class mlpack::fastmks::FastMKS< KernelType, MatType, TreeType >