mlpack  1.0.12
ra_search_rules.hpp
Go to the documentation of this file.
1 
16 #ifndef __MLPACK_METHODS_RANN_RA_SEARCH_RULES_HPP
17 #define __MLPACK_METHODS_RANN_RA_SEARCH_RULES_HPP
18 
19 #include "../neighbor_search/ns_traversal_info.hpp"
20 #include "ra_search.hpp" // For friend declaration.
21 
22 namespace mlpack {
23 namespace neighbor {
24 
25 template<typename SortPolicy, typename MetricType, typename TreeType>
27 {
28  public:
29  RASearchRules(const arma::mat& referenceSet,
30  const arma::mat& querySet,
31  arma::Mat<size_t>& neighbors,
32  arma::mat& distances,
33  MetricType& metric,
34  const double tau = 5,
35  const double alpha = 0.95,
36  const bool naive = false,
37  const bool sampleAtLeaves = false,
38  const bool firstLeafExact = false,
39  const size_t singleSampleLimit = 20);
40 
41 
42 
43  double BaseCase(const size_t queryIndex, const size_t referenceIndex);
44 
67  double Score(const size_t queryIndex, TreeType& referenceNode);
68 
92  double Score(const size_t queryIndex,
93  TreeType& referenceNode,
94  const double baseCaseResult);
95 
113  double Rescore(const size_t queryIndex,
114  TreeType& referenceNode,
115  const double oldScore);
116 
135  double Score(TreeType& queryNode, TreeType& referenceNode);
136 
157  double Score(TreeType& queryNode,
158  TreeType& referenceNode,
159  const double baseCaseResult);
160 
183  double Rescore(TreeType& queryNode,
184  TreeType& referenceNode,
185  const double oldScore);
186 
187 
190  {
191  if (numSamplesMade.n_elem == 0)
192  return 0;
193  else
194  return arma::sum(numSamplesMade);
195  }
196 
198 
199  const TraversalInfoType& TraversalInfo() const { return traversalInfo; }
200  TraversalInfoType& TraversalInfo() { return traversalInfo; }
201 
202  private:
204  const arma::mat& referenceSet;
205 
207  const arma::mat& querySet;
208 
210  arma::Mat<size_t>& neighbors;
211 
213  arma::mat& distances;
214 
216  MetricType& metric;
217 
220 
223 
226 
229 
231  arma::Col<size_t> numSamplesMade;
232 
235 
236  // TO REMOVE: just for testing
238 
239  TraversalInfoType traversalInfo;
240 
250  void InsertNeighbor(const size_t queryIndex,
251  const size_t pos,
252  const size_t neighbor,
253  const double distance);
254 
264  size_t MinimumSamplesReqd(const size_t n,
265  const size_t k,
266  const double tau,
267  const double alpha) const;
268 
278  double SuccessProbability(const size_t n,
279  const size_t k,
280  const size_t m,
281  const size_t t) const;
282 
292  void ObtainDistinctSamples(const size_t numSamples,
293  const size_t rangeUpperBound,
294  arma::uvec& distinctSamples) const;
295 
299  double Score(const size_t queryIndex,
300  TreeType& referenceNode,
301  const double distance,
302  const double bestDistance);
303 
307  double Score(TreeType& queryNode,
308  TreeType& referenceNode,
309  const double distance,
310  const double bestDistance);
311 
312  // So that RASearch can access ObtainDistinctSamples() and
313  // MinimumSamplesReqd(). Maybe refactoring is a better solution but this is
314  // okay for now.
315  friend class RASearch<SortPolicy, MetricType, TreeType>;
316 }; // class RASearchRules
317 
318 }; // namespace neighbor
319 }; // namespace mlpack
320 
321 // Include implementation.
322 #include "ra_search_rules_impl.hpp"
323 
324 #endif // __MLPACK_METHODS_RANN_RA_SEARCH_RULES_HPP
bool firstLeafExact
Whether to do exact computation on the first leaf before any sampling.
double samplingRatio
The sampling ratio.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:23
size_t numSamplesReqd
The minimum number of samples required per query.
MetricType & metric
The instantiated metric.
double Rescore(const size_t queryIndex, TreeType &referenceNode, const double oldScore)
Re-evaluate the score for recursion order.
arma::mat & distances
The matrix the resultant neighbor distances should be stored in.
double Score(const size_t queryIndex, TreeType &referenceNode)
Get the score for recursion order.
neighbor::NeighborSearchTraversalInfo< TreeType > TraversalInfoType
arma::Col< size_t > numSamplesMade
The number of samples made for every query.
The RASearch class: This class provides a generic manner to perform rank-approximate search via rando...
Definition: ra_search.hpp:63
const TraversalInfoType & TraversalInfo() const
Traversal information for NeighborSearch.
const arma::mat & querySet
The query set.
bool sampleAtLeaves
Whether to sample at leaves or just use all of it.
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)
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 ...
const arma::mat & referenceSet
The reference set.
TraversalInfoType & TraversalInfo()
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.
see subsection cli_alt_reg_tut Alternate DET regularization The usual regularized error f $R_ alpha(t)\f $of a node\f $t\f $is given by
Definition: det.txt:367
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 ...
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' ...
size_t singleSampleLimit
The limit on the largest node that can be approximated by sampling.
double BaseCase(const size_t queryIndex, const size_t referenceIndex)
arma::Mat< size_t > & neighbors
The matrix the resultant neighbor indices should be stored in.