PLearn 0.1
Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Static Protected Attributes | Private Types | Private Member Functions
PLearn::ExhaustiveNearestNeighbors Class Reference

This class provides the basic implementation of the classical O(N^2) nearest-neighbors algorithm. More...

#include <ExhaustiveNearestNeighbors.h>

Inheritance diagram for PLearn::ExhaustiveNearestNeighbors:
Inheritance graph
[legend]
Collaboration diagram for PLearn::ExhaustiveNearestNeighbors:
Collaboration graph
[legend]

List of all members.

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 OptionListgetOptionList () const
virtual OptionMapgetOptionMap () const
virtual RemoteMethodMapgetRemoteMethodMap () 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 PPathdeclaringFile ()

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

Detailed Description

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.


Member Typedef Documentation

Reimplemented from PLearn::GenericNearestNeighbors.

Definition at line 82 of file ExhaustiveNearestNeighbors.h.


Constructor & Destructor Documentation

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_;
}

Member Function Documentation

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.

bool PLearn::ExhaustiveNearestNeighbors::_isa_ ( const Object o) [static]

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

Here is the call graph for this function:

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");
}

Here is the caller graph for this function:

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);
}

Here is the call graph for this function:

void PLearn::ExhaustiveNearestNeighbors::computeOutput ( const Vec input,
Vec output 
) const [virtual]
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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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);
}

Here is the call graph for this function:

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();
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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);
}

Here is the call graph for this function:

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;
}

Here is the call graph for this function:

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.

Here is the call graph for this function:

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));
}

Here is the call graph for this function:

Here is the caller graph for this function:

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);
}

Here is the call graph for this function:

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();
}

Here is the call graph for this function:


Member Data Documentation

Reimplemented from PLearn::GenericNearestNeighbors.

Definition at line 139 of file ExhaustiveNearestNeighbors.h.

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

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.

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

Internal vector for storing computed kernel values.

Definition at line 99 of file ExhaustiveNearestNeighbors.h.

Referenced by computeOutput(), computeOutputAndCosts(), and makeDeepCopyFromShallowCopy().

Internal vector for storing computed indices.

Definition at line 96 of file ExhaustiveNearestNeighbors.h.

Referenced by computeOutput(), computeOutputAndCosts(), and makeDeepCopyFromShallowCopy().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines