PLearn 0.1
ExhaustiveNearestNeighbors.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // ExhaustiveNearestNeighbors.cc
00004 //
00005 // Copyright (C) 2004 Nicolas Chapados
00006 // 
00007 // Redistribution and use in source and binary forms, with or without
00008 // modification, are permitted provided that the following conditions are met:
00009 // 
00010 //  1. Redistributions of source code must retain the above copyright
00011 //     notice, this list of conditions and the following disclaimer.
00012 // 
00013 //  2. Redistributions in binary form must reproduce the above copyright
00014 //     notice, this list of conditions and the following disclaimer in the
00015 //     documentation and/or other materials provided with the distribution.
00016 // 
00017 //  3. The name of the authors may not be used to endorse or promote
00018 //     products derived from this software without specific prior written
00019 //     permission.
00020 // 
00021 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00022 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00023 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00024 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00025 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00026 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031 // 
00032 // This file is part of the PLearn library. For more information on the PLearn
00033 // library, go to the PLearn Web site at www.plearn.org
00034 
00035 /* *******************************************************      
00036  * $Id: ExhaustiveNearestNeighbors.cc 8184 2007-10-15 20:09:46Z nouiz $ 
00037  ******************************************************* */
00038 
00039 // Authors: Nicolas Chapados
00040 
00044 #include "ExhaustiveNearestNeighbors.h"
00045 #include <assert.h>
00046 #include <plearn/base/stringutils.h>
00047 #include <plearn/ker/DistanceKernel.h>
00048 
00049 namespace PLearn {
00050 using namespace std;
00051 
00052 PLEARN_IMPLEMENT_OBJECT(
00053     ExhaustiveNearestNeighbors,
00054     "Classical nearest-neighbors implementation using exhaustive search",
00055     "This class provides the basic implementation of the classical O(N^2)\n"
00056     "nearest-neighbors algorithm.  For each test point, it performs an\n"
00057     "exhaustive search in the training set to find the K (specified by the\n"
00058     "inherited 'num_neighbors' option) closest examples according to a\n"
00059     "user-specified Kernel.\n"
00060     "\n"
00061     "It is important to specify whether the Kernel denotes a SIMILARITY or a\n"
00062     "(pseudo-)DISTANCE measure.  A similarity measure is HIGHER for points\n"
00063     "that are closer.  The GaussianKernel is a similarity measure.  On the\n"
00064     "other hand, a distance measure is LOWER for points that are closer.  A\n"
00065     "DistanceKernel is a distance measure.  The option\n"
00066     "'kernel_is_pseudo_distance' controls this:\n"
00067     "\n"
00068     "   - if false: the distance_kernel is a similarity measure\n"
00069     "   - if true (the default): the distance_kernel is a distance measure\n"
00070     "\n"
00071     "The output costs are simply the kernel values for each found training\n"
00072     "point.  The costs are named 'ker0', 'ker1', ..., 'kerK-1'.\n"
00073     "\n"
00074 //    "The training set is SAVED with this learner, under the option name\n"
00075 //    "'train_set'. Otherwise, one would NOT be able to reload the learner\n"
00076 //    "and carry out test operations!\n"
00077     );
00078 
00079 Ker ExhaustiveNearestNeighbors::default_kernel = new DistanceKernel();
00080   
00081 ExhaustiveNearestNeighbors::ExhaustiveNearestNeighbors(
00082     Ker distance_kernel_, bool kernel_is_pseudo_distance_)
00083     : inherited(),
00084       kernel_is_pseudo_distance(kernel_is_pseudo_distance_)
00085 {
00086     distance_kernel = distance_kernel_;
00087 }
00088 
00089 void ExhaustiveNearestNeighbors::declareOptions(OptionList& ol)
00090 {
00091     /* // No longer needed: train_set is saved as part of the options of 
00092        // parent class GenericNearestNeighbors. See comment there.
00093     declareOption(
00094         ol, "training_mat", &ExhaustiveNearestNeighbors::training_mat,
00095         OptionBase::learntoption,
00096         "Saved training set");
00097     */
00098 
00099     declareOption(
00100         ol, "kernel_is_pseudo_distance",
00101         &ExhaustiveNearestNeighbors::kernel_is_pseudo_distance,
00102         OptionBase::buildoption,
00103         "Whether the kernel defined by the 'distance_kernel' option should be\n"
00104         "interpreted as a (pseudo-)distance measure (true) or a similarity\n"
00105         "measure (false). Default = true.  Note that this interpretation is\n"
00106         "strictly specific to the class ExhaustiveNearestNeighbors.\n");
00107 
00108     declareOption(
00109         ol, "kernel", &GenericNearestNeighbors::distance_kernel,
00110         OptionBase::buildoption | OptionBase::nosave,
00111         "Alternate name for 'distance_kernel'.  (Deprecated; use only so that\n"
00112         "existing scripts can run.)");
00113 
00114     // Now call the parent class' declareOptions
00115     inherited::declareOptions(ol);
00116 }
00117 
00118 void ExhaustiveNearestNeighbors::build_()
00119 {
00120     if (! distance_kernel)
00121         PLERROR("ExhaustiveNearestNeighbors::build_: the 'distance_kernel' option "
00122                 "must be specified");
00123 }
00124 
00125 // ### Nothing to add here, simply calls build_
00126 void ExhaustiveNearestNeighbors::build()
00127 {
00128     inherited::build();
00129     build_();
00130 }
00131 
00132 
00133 void ExhaustiveNearestNeighbors::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00134 {
00135     inherited::makeDeepCopyFromShallowCopy(copies);
00136 
00137     deepCopyField(dummy_vec,        copies);
00138     deepCopyField(tmp_indices,      copies);
00139     deepCopyField(tmp_distances,    copies);
00140     deepCopyField(cached_inputs,    copies);
00141 }
00142 
00143 void ExhaustiveNearestNeighbors::setTrainingSet(VMat training_set,
00144                                                 bool call_forget)
00145 {
00146     inherited::setTrainingSet(training_set, call_forget);
00147     cached_inputs.resize(0,0);
00148 }
00149 
00150 
00151 void ExhaustiveNearestNeighbors::forget()
00152 {
00153     cached_inputs.resize(0,0);
00154 }
00155 
00156 void ExhaustiveNearestNeighbors::train()
00157 {
00158     // Train is nearly instantaneous. :-)
00159     // Note: this conversion is performed on train() rather than
00160     // setTrainingSet since the training VMat may depend upon some
00161     // PLearners which may not have been trained when setTrainingSet is
00162     // called.  It's safer to delay the conversion until necessary.
00163     cached_inputs.resize(0,0);
00164     preloadInputCache();
00165 }
00166 
00167 // New implementation (more efficient)
00168 void ExhaustiveNearestNeighbors::findNearestNeighbors(const Vec& input, int K, TVec<int>& indices, Vec& distances) const
00169 {
00170     PLASSERT(pq.empty());
00171     if(cached_inputs.size()==0)
00172         preloadInputCache();    
00173 
00174     int l = train_set->length();
00175     for(int i=0; i<l; ++i) 
00176     {
00177         real d = distance_kernel(input, cached_inputs(i));
00178         if(!kernel_is_pseudo_distance) // make it distance-like (smaller means closer)
00179             d = -d;
00180         if(int(pq.size())<K)
00181             pq.push(pair<double,int>(d,i));
00182         else if(d<pq.top().first)
00183         {
00184             pq.pop();
00185             pq.push(pair<double,int>(d,i));
00186         }
00187     }
00188 
00189     int pqsize = (int)pq.size();
00190     indices.resize(pqsize);
00191     distances.resize(pqsize);
00192 
00193     for(int j=pqsize-1; j>=0; j--)
00194     {
00195         const pair<real,int>& cur_top = pq.top();
00196         real d = cur_top.first;
00197         if(!kernel_is_pseudo_distance) // restore actual kernel value (larger means closer)
00198             d = -d;
00199         distances[j] = d;
00200         indices[j] = cur_top.second;
00201         pq.pop();
00202     }
00203 }
00204 
00205 
00206 void ExhaustiveNearestNeighbors::computeOutputAndCosts(
00207     const Vec& input, const Vec& target, Vec& output, Vec& costs) const
00208 {
00209     findNearestNeighbors(input, num_neighbors, tmp_indices, tmp_distances);
00210     int effective_num_neighbors = tmp_indices.size();
00211     costs.resize(num_neighbors);
00212     for(int j=0; j<effective_num_neighbors; j++)
00213         costs[j] = tmp_distances[j];
00214     // Make remaining costs into missing values if the found number of
00215     // neighbors is smaller than the requested number of neighbors
00216     for(int j=effective_num_neighbors; j<num_neighbors; j++)
00217         costs[j] = MISSING_VALUE;
00218 
00219     constructOutputVector(tmp_indices, output);
00220 }
00221 
00222 
00223 void ExhaustiveNearestNeighbors::computeOutput(const Vec& input, Vec& output) const
00224 {
00225     findNearestNeighbors(input, num_neighbors, tmp_indices, tmp_distances);
00226     constructOutputVector(tmp_indices, output);
00227 }
00228 
00229 
00230 void ExhaustiveNearestNeighbors::computeCostsFromOutputs(
00231     const Vec& input, const Vec& output, const Vec& target, Vec& costs) const
00232 {
00233     // Not really efficient (the output has probably already been computed).
00234     dummy_vec.resize(outputsize());
00235     computeOutputAndCosts(input, target, dummy_vec, costs);
00236 }
00237 
00238 
00239 TVec<string> ExhaustiveNearestNeighbors::getTestCostNames() const
00240 {
00241     TVec<string> costs(num_neighbors);
00242     for (int i=0, n=num_neighbors ; i<n ; ++i)
00243         costs[i] = "ker" + tostring(i);
00244     return costs;
00245 }
00246 
00247 
00248 int ExhaustiveNearestNeighbors::nTestCosts() const
00249 {
00250     return num_neighbors;
00251 }
00252 
00253 
00254 TVec<string> ExhaustiveNearestNeighbors::getTrainCostNames() const
00255 {
00256     // No training statistics
00257     return TVec<string>();
00258 }
00259 
00260 void ExhaustiveNearestNeighbors::preloadInputCache() const
00261 {
00262     int l = train_set->length();
00263     int ninputs = train_set->inputsize();
00264     cached_inputs.resize(l,ninputs);
00265     for(int i=0; i<l; i++)
00266         train_set->getSubRow(i,0,cached_inputs(i));
00267 }
00268 
00269 } // end of namespace PLearn
00270 
00271 
00272 /*
00273   Local Variables:
00274   mode:c++
00275   c-basic-offset:4
00276   c-file-style:"stroustrup"
00277   c-file-offsets:((innamespace . 0)(inline-open . 0))
00278   indent-tabs-mode:nil
00279   fill-column:79
00280   End:
00281 */
00282 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines