MLPACK
1.0.7
|
Public Member Functions | |
RASearchRules (const arma::mat &referenceSet, const arma::mat &querySet, arma::Mat< size_t > &neighbors, arma::mat &distances, MetricType &metric, const double tau=5, const double alpha=0.95, const bool naive=false, const bool sampleAtLeaves=false, const bool firstLeafExact=false, const size_t singleSampleLimit=20) | |
double | BaseCase (const size_t queryIndex, const size_t referenceIndex) |
size_t | NumDistComputations () |
size_t | NumEffectiveSamples () |
double | Prescore (TreeType &queryNode, TreeType &referenceNode, TreeType &referenceChildNode, const double baseCaseResult) const |
TOFIX: This function is specified for the cover tree (usually) so I need to think about it more algorithmically and keep its implementation mostly empty. More... | |
double | PrescoreQ (TreeType &queryNode, TreeType &queryChildNode, TreeType &referenceNode, const double baseCaseResult) const |
double | Rescore (const size_t queryIndex, TreeType &referenceNode, const double oldScore) |
Re-evaluate the score for recursion order. More... | |
double | Rescore (TreeType &queryNode, TreeType &referenceNode, const double oldScore) |
Re-evaluate the score for recursion order. More... | |
double | Score (const size_t queryIndex, TreeType &referenceNode) |
Get the score for recursion order. More... | |
double | Score (const size_t queryIndex, TreeType &referenceNode, const double baseCaseResult) |
Get the score for recursion order. More... | |
double | Score (TreeType &queryNode, TreeType &referenceNode) |
Get the score for recursion order. More... | |
double | Score (TreeType &queryNode, TreeType &referenceNode, const double baseCaseResult) |
Get the score for recursion order, passing the base case result (in the situation where it may be needed to calculate the recursion order). More... | |
Private Member Functions | |
void | InsertNeighbor (const size_t queryIndex, const size_t pos, const size_t neighbor, const double distance) |
Insert a point into the neighbors and distances matrices; this is a helper function. More... | |
size_t | MinimumSamplesReqd (const size_t n, const size_t k, const double tau, const double alpha) const |
Compute the minimum number of samples required to guarantee the given rank-approximation and success probability. More... | |
void | ObtainDistinctSamples (const size_t numSamples, const size_t rangeUpperBound, arma::uvec &distinctSamples) const |
Pick up desired number of samples (with replacement) from a given range of integers so that only the distinct samples are returned from the range [0 - specified upper bound) More... | |
double | Score (const size_t queryIndex, TreeType &referenceNode, const double distance, const double bestDistance) |
Perform actual scoring for single-tree case. More... | |
double | Score (TreeType &queryNode, TreeType &referenceNode, const double distance, const double bestDistance) |
Perform actual scoring for dual-tree case. More... | |
double | SuccessProbability (const size_t n, const size_t k, const size_t m, const size_t t) const |
Compute the success probability of obtaining 'k'-neighbors from a set of size 'n' within the top 't' neighbors if 'm' samples are made. More... | |
Private Attributes | |
arma::mat & | distances |
The matrix the resultant neighbor distances should be stored in. More... | |
bool | firstLeafExact |
Whether to do exact computation on the first leaf before any sampling. More... | |
MetricType & | metric |
The instantiated metric. More... | |
arma::Mat< size_t > & | neighbors |
The matrix the resultant neighbor indices should be stored in. More... | |
size_t | numDistComputations |
arma::Col< size_t > | numSamplesMade |
The number of samples made for every query. More... | |
size_t | numSamplesReqd |
The minimum number of samples required per query. More... | |
const arma::mat & | querySet |
The query set. More... | |
const arma::mat & | referenceSet |
The reference set. More... | |
bool | sampleAtLeaves |
Whether to sample at leaves or just use all of it. More... | |
double | samplingRatio |
The sampling ratio. More... | |
size_t | singleSampleLimit |
The limit on the largest node that can be approximated by sampling. More... | |
Definition at line 31 of file ra_search_rules.hpp.
mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::RASearchRules | ( | const arma::mat & | referenceSet, |
const arma::mat & | querySet, | ||
arma::Mat< size_t > & | neighbors, | ||
arma::mat & | distances, | ||
MetricType & | metric, | ||
const double | tau = 5 , |
||
const double | alpha = 0.95 , |
||
const bool | naive = false , |
||
const bool | sampleAtLeaves = false , |
||
const bool | firstLeafExact = false , |
||
const size_t | singleSampleLimit = 20 |
||
) |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::BaseCase | ( | const size_t | queryIndex, |
const size_t | referenceIndex | ||
) |
|
private |
Insert a point into the neighbors and distances matrices; this is a helper function.
queryIndex | Index of point whose neighbors we are inserting into. |
pos | Position in list to insert into. |
neighbor | Index of reference point which is being inserted. |
distance | Distance from query point to reference point. |
|
private |
Compute the minimum number of samples required to guarantee the given rank-approximation and success probability.
n | Size of the set to be sampled from. |
k | The number of neighbors required within the rank-approximation. |
tau | The rank-approximation in percentile of the data. |
alpha | The success probability desired. |
|
inline |
Definition at line 215 of file ra_search_rules.hpp.
References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numDistComputations.
|
inline |
Definition at line 216 of file ra_search_rules.hpp.
References mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::numSamplesMade.
|
private |
Pick up desired number of samples (with replacement) from a given range of integers so that only the distinct samples are returned from the range [0 - specified upper bound)
numSamples | Number of random samples. |
rangeUpperBound | The upper bound on the range of integers. |
distinctSamples | The list of the distinct samples. |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Prescore | ( | TreeType & | queryNode, |
TreeType & | referenceNode, | ||
TreeType & | referenceChildNode, | ||
const double | baseCaseResult | ||
) | const |
TOFIX: This function is specified for the cover tree (usually) so I need to think about it more algorithmically and keep its implementation mostly empty.
Also, since the access to the points in the subtree of a cover tree is non-trivial, we might have to re-work this. FOR NOW: I am just using as for a BSP-tree, I will fix it when we figure out cover trees.
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::PrescoreQ | ( | TreeType & | queryNode, |
TreeType & | queryChildNode, | ||
TreeType & | referenceNode, | ||
const double | baseCaseResult | ||
) | const |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Rescore | ( | const size_t | queryIndex, |
TreeType & | referenceNode, | ||
const double | oldScore | ||
) |
Re-evaluate the score for recursion order.
A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned). This is used when the score has already been calculated, but another recursion may have modified the bounds for pruning. So the old score is checked against the new pruning bound.
For rank-approximation, it also checks if the number of samples left for a query to satisfy the rank constraint is small enough at this point of the algorithm, then this node is approximated by sampling and given a new score of 'DBL_MAX'.
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Rescore | ( | TreeType & | queryNode, |
TreeType & | referenceNode, | ||
const double | oldScore | ||
) |
Re-evaluate the score for recursion order.
A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned). This is used when the score has already been calculated, but another recursion may have modified the bounds for pruning. So the old score is checked against the new pruning bound.
For the rank-approximation, we check if the referenceNode can be approximated by sampling. If it can be, enough samples are made for every query in the queryNode. No further query-tree traversal is performed.
The 'NumSamplesMade' query stat is propagated up the tree. And then if pruning occurs (by distance or by sampling), the 'NumSamplesMade' stat is not propagated down the tree. If no pruning occurs, the stat is propagated down the tree.
queryNode | Candidate query node to recurse into. |
referenceNode | Candidate reference node to recurse into. |
oldScore | Old score produced by Socre() (or Rescore()). |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score | ( | const size_t | queryIndex, |
TreeType & | referenceNode | ||
) |
Get the score for recursion order.
A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).
For rank-approximation, the scoring function first checks if pruning by distance is possible. If yes, then the node is given the score of 'DBL_MAX' and the expected number of samples from that node are added to the number of samples made for the query.
If no, then the function tries to see if the node can be pruned by approximation. If number of samples required from this node is small enough, then that number of samples are acquired from this node and the score is set to be 'DBL_MAX'.
If the pruning by approximation is not possible either, the algorithm continues with the usual tree-traversal.
queryIndex | Index of query point. |
referenceNode | Candidate node to be recursed into. |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score | ( | const size_t | queryIndex, |
TreeType & | referenceNode, | ||
const double | baseCaseResult | ||
) |
Get the score for recursion order.
A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).
For rank-approximation, the scoring function first checks if pruning by distance is possible. If yes, then the node is given the score of 'DBL_MAX' and the expected number of samples from that node are added to the number of samples made for the query.
If no, then the function tries to see if the node can be pruned by approximation. If number of samples required from this node is small enough, then that number of samples are acquired from this node and the score is set to be 'DBL_MAX'.
If the pruning by approximation is not possible either, the algorithm continues with the usual tree-traversal.
queryIndex | Index of query point. |
referenceNode | Candidate node to be recursed into. |
baseCaseResult | Result of BaseCase(queryIndex, referenceNode). |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score | ( | TreeType & | queryNode, |
TreeType & | referenceNode | ||
) |
Get the score for recursion order.
A low score indicates priority for recursionm while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).
For the rank-approximation, we check if the referenceNode can be approximated by sampling. If it can be, enough samples are made for every query in the queryNode. No further query-tree traversal is performed.
The 'NumSamplesMade' query stat is propagated up the tree. And then if pruning occurs (by distance or by sampling), the 'NumSamplesMade' stat is not propagated down the tree. If no pruning occurs, the stat is propagated down the tree.
queryNode | Candidate query node to recurse into. |
referenceNode | Candidate reference node to recurse into. |
double mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::Score | ( | TreeType & | queryNode, |
TreeType & | referenceNode, | ||
const double | baseCaseResult | ||
) |
Get the score for recursion order, passing the base case result (in the situation where it may be needed to calculate the recursion order).
A low score indicates priority for recursion, while DBL_MAX indicates that the node should not be recursed into at all (it should be pruned).
For the rank-approximation, we check if the referenceNode can be approximated by sampling. If it can be, enough samples are made for every query in the queryNode. No further query-tree traversal is performed.
The 'NumSamplesMade' query stat is propagated up the tree. And then if pruning occurs (by distance or by sampling), the 'NumSamplesMade' stat is not propagated down the tree. If no pruning occurs, the stat is propagated down the tree.
queryNode | Candidate query node to recurse into. |
referenceNode | Candidate reference node to recurse into. |
baseCaseResult | Result of BaseCase(queryIndex, referenceNode). |
|
private |
Perform actual scoring for single-tree case.
|
private |
Perform actual scoring for dual-tree case.
|
private |
Compute the success probability of obtaining 'k'-neighbors from a set of size 'n' within the top 't' neighbors if 'm' samples are made.
n | Size of the set being sampled from. |
k | The number of neighbors required within the rank-approximation. |
m | The number of random samples. |
t | The desired rank-approximation. |
|
private |
The matrix the resultant neighbor distances should be stored in.
Definition at line 235 of file ra_search_rules.hpp.
|
private |
Whether to do exact computation on the first leaf before any sampling.
Definition at line 244 of file ra_search_rules.hpp.
|
private |
The instantiated metric.
Definition at line 238 of file ra_search_rules.hpp.
|
private |
The matrix the resultant neighbor indices should be stored in.
Definition at line 232 of file ra_search_rules.hpp.
|
private |
Definition at line 259 of file ra_search_rules.hpp.
Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumDistComputations().
|
private |
The number of samples made for every query.
Definition at line 253 of file ra_search_rules.hpp.
Referenced by mlpack::neighbor::RASearchRules< SortPolicy, MetricType, TreeType >::NumEffectiveSamples().
|
private |
The minimum number of samples required per query.
Definition at line 250 of file ra_search_rules.hpp.
|
private |
The query set.
Definition at line 229 of file ra_search_rules.hpp.
|
private |
The reference set.
Definition at line 226 of file ra_search_rules.hpp.
|
private |
Whether to sample at leaves or just use all of it.
Definition at line 241 of file ra_search_rules.hpp.
|
private |
The sampling ratio.
Definition at line 256 of file ra_search_rules.hpp.
|
private |
The limit on the largest node that can be approximated by sampling.
Definition at line 247 of file ra_search_rules.hpp.