mlpack  master
FastMKS< KernelType, MatType, TreeType > Class Template Reference

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

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

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...

 
FastMKSoperator= (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...

 

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
KernelTypeType of kernel to run FastMKS with.
MatTypeType of data matrix (usually arma::mat).
TreeTypeType of tree to run FastMKS with; it must satisfy the TreeType policy API.

Definition at line 63 of file fastmks.hpp.

Member Typedef Documentation

◆ Tree

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

Convenience typedef.

Definition at line 67 of file fastmks.hpp.

Constructor & Destructor Documentation

◆ FastMKS() [1/6]

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
singleModeWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.

◆ FastMKS() [2/6]

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
referenceSetSet of reference data.
singleModeWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.

◆ FastMKS() [3/6]

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
referenceSetReference set of data for FastMKS.
kernelInitialized kernel.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.

◆ FastMKS() [4/6]

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
referenceTreeTree built on reference data.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.

◆ FastMKS() [5/6]

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

Copy the parameters of the given model.

◆ FastMKS() [6/6]

FastMKS ( FastMKS< KernelType, MatType, TreeType > &&  other)

Take ownership of the given model.

◆ ~FastMKS()

~FastMKS ( )

Destructor for the FastMKS object.

Member Function Documentation

◆ Metric() [1/2]

const metric::IPMetric<KernelType>& Metric ( ) const
inline

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

Definition at line 237 of file fastmks.hpp.

◆ Metric() [2/2]

metric::IPMetric<KernelType>& Metric ( )
inline

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

Definition at line 239 of file fastmks.hpp.

◆ Naive() [1/2]

bool Naive ( ) const
inline

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

Definition at line 247 of file fastmks.hpp.

◆ Naive() [2/2]

bool& Naive ( )
inline

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

Definition at line 249 of file fastmks.hpp.

◆ operator=()

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

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

◆ Search() [1/3]

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.

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
querySetSet of query points (can be a single point).
kThe number of maximum kernels to find.
indicesMatrix to store resulting indices of max-kernel search in.
kernelsMatrix to store resulting max-kernel values in.

◆ Search() [2/3]

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.

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
queryTreeTree built on query points.
kThe number of maximum kernels to find.
indicesMatrix to store resulting indices of max-kernel search in.
kernelsMatrix to store resulting max-kernel values in.

◆ Search() [3/3]

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).

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
kThe number of maximum kernels to find.
indicesMatrix to store resulting indices of max-kernel search in.
productsMatrix to store resulting max-kernel values in.

◆ Serialize()

void Serialize ( Archive &  ar,
const unsigned  int 
)

Serialize the model.

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

◆ SingleMode() [1/2]

bool SingleMode ( ) const
inline

Get whether or not single-tree search is used.

Definition at line 242 of file fastmks.hpp.

◆ SingleMode() [2/2]

bool& SingleMode ( )
inline

Modify whether or not single-tree search is used.

Definition at line 244 of file fastmks.hpp.

◆ Train() [1/3]

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).

Parameters
referenceSetSet of reference points.

◆ Train() [2/3]

void 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
referenceSetSet of reference points.
kernelKernel to use for search.

◆ Train() [3/3]

void 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
treeTree to use as reference data.

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