PLearn 0.1
|
This class provides the basic implementation of the classical O(N^2) nearest-neighbors algorithm. More...
#include <ExhaustiveNearestNeighbors.h>
Public Member Functions | |
ExhaustiveNearestNeighbors (Ker kernel=default_kernel, bool kernel_is_pseudo_distance=true) | |
Default constructor. | |
virtual void | build () |
Simply calls inherited::build() then build_(). | |
virtual void | makeDeepCopyFromShallowCopy (CopiesMap &copies) |
Transforms a shallow copy into a deep copy. | |
virtual string | classname () const |
virtual OptionList & | getOptionList () const |
virtual OptionMap & | getOptionMap () const |
virtual RemoteMethodMap & | getRemoteMethodMap () const |
virtual ExhaustiveNearestNeighbors * | deepCopy (CopiesMap &copies) const |
virtual void | setTrainingSet (VMat training_set, bool call_forget=true) |
Overridden to make an in-memory version of the training set. | |
virtual void | forget () |
(Re-)initializes the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!). | |
virtual void | train () |
The role of the train method is to bring the learner up to stage==nstages, updating the train_stats collector with training costs measured on-line in the process. | |
virtual void | computeOutputAndCosts (const Vec &input, const Vec &target, Vec &output, Vec &costs) const |
Compute the output and cost from the input. | |
virtual void | computeOutput (const Vec &input, Vec &output) const |
Computes the output from the input. | |
virtual void | computeCostsFromOutputs (const Vec &input, const Vec &output, const Vec &target, Vec &costs) const |
Computes the costs from already computed output. | |
virtual TVec< std::string > | getTestCostNames () const |
Returns the names of the costs computed by computeCostsFromOutpus. | |
virtual int | nTestCosts () const |
Return num_neighbors. | |
virtual TVec< std::string > | getTrainCostNames () const |
Returns the names of the objective costs that the train method computes and for which it updates the VecStatsCollector train_stats. | |
Static Public Member Functions | |
static string | _classname_ () |
static OptionList & | _getOptionList_ () |
static RemoteMethodMap & | _getRemoteMethodMap_ () |
static Object * | _new_instance_for_typemap_ () |
static bool | _isa_ (const Object *o) |
static void | _static_initialize_ () |
static const PPath & | declaringFile () |
Public Attributes | |
bool | kernel_is_pseudo_distance |
Kernel that must be used to evaluate distances. | |
Static Public Attributes | |
static StaticInitializer | _static_initializer_ |
Protected Member Functions | |
void | preloadInputCache () const |
Loads the input part of the train_set in cached_inputs. | |
void | findNearestNeighbors (const Vec &input, int K, TVec< int > &indices, Vec &distances) const |
Fills the indices and distances vector with the K nearest neighbors. | |
Static Protected Member Functions | |
static void | declareOptions (OptionList &ol) |
Declares this class' options. | |
Protected Attributes | |
Vec | dummy_vec |
Matrixified version of the training set. Saved. | |
TVec< int > | tmp_indices |
Internal vector for storing computed indices. | |
Vec | tmp_distances |
Internal vector for storing computed kernel values. | |
Mat | cached_inputs |
pre-loaded input part of the training set | |
priority_queue< pair< real, int > > | pq |
The priority queue for finding the k nearest neighbors. | |
Static Protected Attributes | |
static Ker | default_kernel = new DistanceKernel() |
Default kernel is a DistanceKernel; static so as not to introduce strong coupling between this .h and that defining DistanceKernel. | |
Private Types | |
typedef GenericNearestNeighbors | inherited |
Private Member Functions | |
void | build_ () |
This does the actual building. |
This class provides the basic implementation of the classical O(N^2) nearest-neighbors algorithm.
For each test point, it performs an exhaustive search in the training set to find the K (specified by the inherited 'num_neighbors' option) closest examples according to a user-specified Kernel.
It is important to specify whether the Kernel denotes a SIMILARITY or a (pseudo-)DISTANCE measure. A similarity measure is HIGHER for points that are closer. The GaussianKernel is a similarity measure. On the other hand, a distance measure is LOWER for points that are closer. A DistanceKernel is a distance measure. The option 'kernel_is_pseudo_distance' controls this:
The output costs are simply the kernel values for each found training point. The costs are named 'ker0', 'ker1', ..., 'kerK-1'.
The training set is SAVED with this learner, under the option name 'train_set'. Otherwise, one would NOT be able to reload the learner and carry out test operations!
Definition at line 80 of file ExhaustiveNearestNeighbors.h.
typedef GenericNearestNeighbors PLearn::ExhaustiveNearestNeighbors::inherited [private] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 82 of file ExhaustiveNearestNeighbors.h.
PLearn::ExhaustiveNearestNeighbors::ExhaustiveNearestNeighbors | ( | Ker | kernel = default_kernel , |
bool | kernel_is_pseudo_distance = true |
||
) |
Default constructor.
Definition at line 81 of file ExhaustiveNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::distance_kernel.
: inherited(), kernel_is_pseudo_distance(kernel_is_pseudo_distance_) { distance_kernel = distance_kernel_; }
string PLearn::ExhaustiveNearestNeighbors::_classname_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
OptionList & PLearn::ExhaustiveNearestNeighbors::_getOptionList_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
RemoteMethodMap & PLearn::ExhaustiveNearestNeighbors::_getRemoteMethodMap_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
Object * PLearn::ExhaustiveNearestNeighbors::_new_instance_for_typemap_ | ( | ) | [static] |
Reimplemented from PLearn::Object.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
StaticInitializer ExhaustiveNearestNeighbors::_static_initializer_ & PLearn::ExhaustiveNearestNeighbors::_static_initialize_ | ( | ) | [static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
void PLearn::ExhaustiveNearestNeighbors::build | ( | ) | [virtual] |
Simply calls inherited::build() then build_().
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 126 of file ExhaustiveNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::build(), and build_().
{ inherited::build(); build_(); }
void PLearn::ExhaustiveNearestNeighbors::build_ | ( | ) | [private] |
This does the actual building.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 118 of file ExhaustiveNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::distance_kernel, and PLERROR.
Referenced by build().
{ if (! distance_kernel) PLERROR("ExhaustiveNearestNeighbors::build_: the 'distance_kernel' option " "must be specified"); }
string PLearn::ExhaustiveNearestNeighbors::classname | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
void PLearn::ExhaustiveNearestNeighbors::computeCostsFromOutputs | ( | const Vec & | input, |
const Vec & | output, | ||
const Vec & | target, | ||
Vec & | costs | ||
) | const [virtual] |
Computes the costs from already computed output.
Implements PLearn::PLearner.
Definition at line 230 of file ExhaustiveNearestNeighbors.cc.
References computeOutputAndCosts(), dummy_vec, PLearn::GenericNearestNeighbors::outputsize(), and PLearn::TVec< T >::resize().
{ // Not really efficient (the output has probably already been computed). dummy_vec.resize(outputsize()); computeOutputAndCosts(input, target, dummy_vec, costs); }
void PLearn::ExhaustiveNearestNeighbors::computeOutput | ( | const Vec & | input, |
Vec & | output | ||
) | const [virtual] |
Computes the output from the input.
Reimplemented from PLearn::PLearner.
Definition at line 223 of file ExhaustiveNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::constructOutputVector(), findNearestNeighbors(), PLearn::GenericNearestNeighbors::num_neighbors, tmp_distances, and tmp_indices.
{ findNearestNeighbors(input, num_neighbors, tmp_indices, tmp_distances); constructOutputVector(tmp_indices, output); }
void PLearn::ExhaustiveNearestNeighbors::computeOutputAndCosts | ( | const Vec & | input, |
const Vec & | target, | ||
Vec & | output, | ||
Vec & | costs | ||
) | const [virtual] |
Compute the output and cost from the input.
Reimplemented from PLearn::PLearner.
Definition at line 206 of file ExhaustiveNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::constructOutputVector(), findNearestNeighbors(), j, MISSING_VALUE, PLearn::GenericNearestNeighbors::num_neighbors, PLearn::TVec< T >::resize(), PLearn::TVec< T >::size(), tmp_distances, and tmp_indices.
Referenced by computeCostsFromOutputs().
{ findNearestNeighbors(input, num_neighbors, tmp_indices, tmp_distances); int effective_num_neighbors = tmp_indices.size(); costs.resize(num_neighbors); for(int j=0; j<effective_num_neighbors; j++) costs[j] = tmp_distances[j]; // Make remaining costs into missing values if the found number of // neighbors is smaller than the requested number of neighbors for(int j=effective_num_neighbors; j<num_neighbors; j++) costs[j] = MISSING_VALUE; constructOutputVector(tmp_indices, output); }
void PLearn::ExhaustiveNearestNeighbors::declareOptions | ( | OptionList & | ol | ) | [static, protected] |
Declares this class' options.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 89 of file ExhaustiveNearestNeighbors.cc.
References PLearn::OptionBase::buildoption, PLearn::declareOption(), PLearn::GenericNearestNeighbors::declareOptions(), PLearn::GenericNearestNeighbors::distance_kernel, kernel_is_pseudo_distance, and PLearn::OptionBase::nosave.
{ /* // No longer needed: train_set is saved as part of the options of // parent class GenericNearestNeighbors. See comment there. declareOption( ol, "training_mat", &ExhaustiveNearestNeighbors::training_mat, OptionBase::learntoption, "Saved training set"); */ declareOption( ol, "kernel_is_pseudo_distance", &ExhaustiveNearestNeighbors::kernel_is_pseudo_distance, OptionBase::buildoption, "Whether the kernel defined by the 'distance_kernel' option should be\n" "interpreted as a (pseudo-)distance measure (true) or a similarity\n" "measure (false). Default = true. Note that this interpretation is\n" "strictly specific to the class ExhaustiveNearestNeighbors.\n"); declareOption( ol, "kernel", &GenericNearestNeighbors::distance_kernel, OptionBase::buildoption | OptionBase::nosave, "Alternate name for 'distance_kernel'. (Deprecated; use only so that\n" "existing scripts can run.)"); // Now call the parent class' declareOptions inherited::declareOptions(ol); }
static const PPath& PLearn::ExhaustiveNearestNeighbors::declaringFile | ( | ) | [inline, static] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 139 of file ExhaustiveNearestNeighbors.h.
:
//##### PLearner Methods ################################################
ExhaustiveNearestNeighbors * PLearn::ExhaustiveNearestNeighbors::deepCopy | ( | CopiesMap & | copies | ) | const [virtual] |
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
void PLearn::ExhaustiveNearestNeighbors::findNearestNeighbors | ( | const Vec & | input, |
int | K, | ||
TVec< int > & | indices, | ||
Vec & | distances | ||
) | const [protected] |
Fills the indices and distances vector with the K nearest neighbors.
(if there are less than K points in the training set, then indices and distances are resized to the effective number of neighbours found).
Definition at line 168 of file ExhaustiveNearestNeighbors.cc.
References cached_inputs, d, PLearn::GenericNearestNeighbors::distance_kernel, i, j, kernel_is_pseudo_distance, PLearn::VMat::length(), PLASSERT, pq, preloadInputCache(), PLearn::TVec< T >::resize(), PLearn::TMat< T >::size(), and PLearn::PLearner::train_set.
Referenced by computeOutput(), and computeOutputAndCosts().
{ PLASSERT(pq.empty()); if(cached_inputs.size()==0) preloadInputCache(); int l = train_set->length(); for(int i=0; i<l; ++i) { real d = distance_kernel(input, cached_inputs(i)); if(!kernel_is_pseudo_distance) // make it distance-like (smaller means closer) d = -d; if(int(pq.size())<K) pq.push(pair<double,int>(d,i)); else if(d<pq.top().first) { pq.pop(); pq.push(pair<double,int>(d,i)); } } int pqsize = (int)pq.size(); indices.resize(pqsize); distances.resize(pqsize); for(int j=pqsize-1; j>=0; j--) { const pair<real,int>& cur_top = pq.top(); real d = cur_top.first; if(!kernel_is_pseudo_distance) // restore actual kernel value (larger means closer) d = -d; distances[j] = d; indices[j] = cur_top.second; pq.pop(); } }
void PLearn::ExhaustiveNearestNeighbors::forget | ( | ) | [virtual] |
(Re-)initializes the PLearner in its fresh state (that state may depend on the 'seed' option) And sets 'stage' back to 0 (this is the stage of a fresh learner!).
Reimplemented from PLearn::PLearner.
Definition at line 151 of file ExhaustiveNearestNeighbors.cc.
References cached_inputs, and PLearn::TMat< T >::resize().
{ cached_inputs.resize(0,0); }
OptionList & PLearn::ExhaustiveNearestNeighbors::getOptionList | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
OptionMap & PLearn::ExhaustiveNearestNeighbors::getOptionMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
RemoteMethodMap & PLearn::ExhaustiveNearestNeighbors::getRemoteMethodMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 77 of file ExhaustiveNearestNeighbors.cc.
TVec< string > PLearn::ExhaustiveNearestNeighbors::getTestCostNames | ( | ) | const [virtual] |
Returns the names of the costs computed by computeCostsFromOutpus.
These are always kernel evaluations; there are num_neighbors test costs.
Implements PLearn::PLearner.
Definition at line 239 of file ExhaustiveNearestNeighbors.cc.
References i, n, PLearn::GenericNearestNeighbors::num_neighbors, and PLearn::tostring().
{ TVec<string> costs(num_neighbors); for (int i=0, n=num_neighbors ; i<n ; ++i) costs[i] = "ker" + tostring(i); return costs; }
TVec< string > PLearn::ExhaustiveNearestNeighbors::getTrainCostNames | ( | ) | const [virtual] |
Returns the names of the objective costs that the train method computes and for which it updates the VecStatsCollector train_stats.
Implements PLearn::PLearner.
Definition at line 254 of file ExhaustiveNearestNeighbors.cc.
{ // No training statistics return TVec<string>(); }
void PLearn::ExhaustiveNearestNeighbors::makeDeepCopyFromShallowCopy | ( | CopiesMap & | copies | ) | [virtual] |
Transforms a shallow copy into a deep copy.
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 133 of file ExhaustiveNearestNeighbors.cc.
References cached_inputs, PLearn::deepCopyField(), dummy_vec, PLearn::GenericNearestNeighbors::makeDeepCopyFromShallowCopy(), tmp_distances, and tmp_indices.
{ inherited::makeDeepCopyFromShallowCopy(copies); deepCopyField(dummy_vec, copies); deepCopyField(tmp_indices, copies); deepCopyField(tmp_distances, copies); deepCopyField(cached_inputs, copies); }
int PLearn::ExhaustiveNearestNeighbors::nTestCosts | ( | ) | const [virtual] |
Return num_neighbors.
Reimplemented from PLearn::PLearner.
Definition at line 248 of file ExhaustiveNearestNeighbors.cc.
References PLearn::GenericNearestNeighbors::num_neighbors.
{ return num_neighbors; }
void PLearn::ExhaustiveNearestNeighbors::preloadInputCache | ( | ) | const [protected] |
Loads the input part of the train_set in cached_inputs.
Definition at line 260 of file ExhaustiveNearestNeighbors.cc.
References cached_inputs, PLearn::VMat::getSubRow(), i, PLearn::VMat::length(), PLearn::TMat< T >::resize(), and PLearn::PLearner::train_set.
Referenced by findNearestNeighbors(), and train().
{ int l = train_set->length(); int ninputs = train_set->inputsize(); cached_inputs.resize(l,ninputs); for(int i=0; i<l; i++) train_set->getSubRow(i,0,cached_inputs(i)); }
void PLearn::ExhaustiveNearestNeighbors::setTrainingSet | ( | VMat | training_set, |
bool | call_forget = true |
||
) | [virtual] |
Overridden to make an in-memory version of the training set.
Reimplemented from PLearn::PLearner.
Definition at line 143 of file ExhaustiveNearestNeighbors.cc.
References cached_inputs, PLearn::TMat< T >::resize(), and PLearn::PLearner::setTrainingSet().
{ inherited::setTrainingSet(training_set, call_forget); cached_inputs.resize(0,0); }
void PLearn::ExhaustiveNearestNeighbors::train | ( | ) | [virtual] |
The role of the train method is to bring the learner up to stage==nstages, updating the train_stats collector with training costs measured on-line in the process.
Implements PLearn::PLearner.
Definition at line 156 of file ExhaustiveNearestNeighbors.cc.
References cached_inputs, preloadInputCache(), and PLearn::TMat< T >::resize().
{ // Train is nearly instantaneous. :-) // Note: this conversion is performed on train() rather than // setTrainingSet since the training VMat may depend upon some // PLearners which may not have been trained when setTrainingSet is // called. It's safer to delay the conversion until necessary. cached_inputs.resize(0,0); preloadInputCache(); }
Reimplemented from PLearn::GenericNearestNeighbors.
Definition at line 139 of file ExhaustiveNearestNeighbors.h.
Mat PLearn::ExhaustiveNearestNeighbors::cached_inputs [mutable, protected] |
pre-loaded input part of the training set
Definition at line 102 of file ExhaustiveNearestNeighbors.h.
Referenced by findNearestNeighbors(), forget(), makeDeepCopyFromShallowCopy(), preloadInputCache(), setTrainingSet(), and train().
Ker PLearn::ExhaustiveNearestNeighbors::default_kernel = new DistanceKernel() [static, protected] |
Default kernel is a DistanceKernel; static so as not to introduce strong coupling between this .h and that defining DistanceKernel.
Definition at line 87 of file ExhaustiveNearestNeighbors.h.
Vec PLearn::ExhaustiveNearestNeighbors::dummy_vec [mutable, protected] |
Matrixified version of the training set. Saved.
Internal vector for storing dummy data.
Definition at line 93 of file ExhaustiveNearestNeighbors.h.
Referenced by computeCostsFromOutputs(), and makeDeepCopyFromShallowCopy().
Kernel that must be used to evaluate distances.
Default is a DistanceKernel with n=2, which gives an Euclidian distance. Ker kernel; ==> SHOULD BE distance_kernel, defined in super-class Whether the kernel defined by the 'distance_kernel' option should be interpreted as a (pseudo-)distance measure (true) or a similarity measure (false). Default = true. Note that this interpretation is strictly specific to the class ExhaustiveNearestNeighbors.
Definition at line 121 of file ExhaustiveNearestNeighbors.h.
Referenced by declareOptions(), and findNearestNeighbors().
priority_queue< pair<real,int> > PLearn::ExhaustiveNearestNeighbors::pq [mutable, protected] |
The priority queue for finding the k nearest neighbors.
Definition at line 105 of file ExhaustiveNearestNeighbors.h.
Referenced by findNearestNeighbors().
Vec PLearn::ExhaustiveNearestNeighbors::tmp_distances [mutable, protected] |
Internal vector for storing computed kernel values.
Definition at line 99 of file ExhaustiveNearestNeighbors.h.
Referenced by computeOutput(), computeOutputAndCosts(), and makeDeepCopyFromShallowCopy().
TVec<int> PLearn::ExhaustiveNearestNeighbors::tmp_indices [mutable, protected] |
Internal vector for storing computed indices.
Definition at line 96 of file ExhaustiveNearestNeighbors.h.
Referenced by computeOutput(), computeOutputAndCosts(), and makeDeepCopyFromShallowCopy().