PLearn 0.1
StepwiseSelectionOracle.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // StepwiseSelectionOracle.cc
00004 //
00005 // Copyright (C) 2004 ApSTAT Technologies Inc.
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: StepwiseSelectionOracle.cc 9042 2008-05-22 15:42:15Z nouiz $
00037  ******************************************************* */
00038 
00041 #include <algorithm>
00042 #include "StepwiseSelectionOracle.h"
00043 #include <plearn/base/stringutils.h>
00044 #include <plearn/io/openString.h>
00045 
00046 namespace PLearn {
00047 using namespace std;
00048 
00049 StepwiseSelectionOracle::StepwiseSelectionOracle()
00050     : option_name("selected_inputs"),
00051       maxvars(-1),
00052       last_combination(false)
00053 { }
00054 
00055 PLEARN_IMPLEMENT_OBJECT(
00056     StepwiseSelectionOracle,
00057     "This oracle implements a stepwise forward variable selection procedure.",
00058     "It supports the interface provided by SelectInputsLearner, wherein the\n"
00059     "variables to selected are specified by a vector of normalized\n"
00060     "'selected_inputs' ranging from 0 to n-1, where n is the maximum number\n"
00061     "of variables.  (The object SelectInputsLearner is then responsible for\n"
00062     "mapping back those normalized inputs to the real inputs of the\n"
00063     "learner).\n"
00064     "\n"
00065     "You simply specify to this oracle the maximum number of inputs that\n"
00066     "should be allowed.\n"
00067     "\n"
00068     "The current implementation is the simplest: it adds variables one at a\n"
00069     "time.  Look-ahead is not currently supported."
00070     );
00071 
00072 void StepwiseSelectionOracle::declareOptions(OptionList& ol)
00073 {
00074     declareOption(ol, "option_name", &StepwiseSelectionOracle::option_name,
00075                   OptionBase::buildoption,
00076                   "Name of option that should contain the returned list of selected\n"
00077                   "inputs  (default = 'selected_inputs')");
00078 
00079     declareOption(ol, "maxvars", &StepwiseSelectionOracle::maxvars,
00080                   OptionBase::buildoption,
00081                   "Maximum number of variables that should be permitted in the search");
00082 
00083     declareOption(ol, "current_indexes_searchset",
00084                   &StepwiseSelectionOracle:: current_indexes_searchset,
00085                   OptionBase::learntoption,
00086                   "Contains the remaining combinations to generate for the"
00087                   " current variable.");
00088 
00089     declareOption(ol, "combination_performance",
00090                   &StepwiseSelectionOracle:: combination_performance,
00091                   OptionBase::learntoption,
00092                   "This remembers the performance of each combination tried in the"
00093                   " current search set.");
00094 
00095     // Now call the parent class' declareOptions
00096     inherited::declareOptions(ol);
00097 }
00098 
00099 TVec<string>  StepwiseSelectionOracle::getOptionNames() const
00100 {
00101     return TVec<string>(1,option_name);
00102 }
00103 
00104 TVec<string> StepwiseSelectionOracle::generateNextTrial(
00105     const TVec<string>& older_trial, real obtained_objective)
00106 {
00107     if (last_combination)
00108         return TVec<string>();
00109     else {
00110         if (older_trial.size() > 0) {
00111             PLASSERT(older_trial.size() == 1);
00112             // insert negative of objective since priority_queue computes
00113             // the maximum of its inserted elements
00114             combination_performance.push(make_pair(- obtained_objective,
00115                                                    older_trial[0]));
00116         }
00117 
00118         if (current_indexes_searchset.empty())
00119             generateNewSearchset();
00120         if (last_combination)
00121             return TVec<string>();
00122 
00123         PLASSERT(current_indexes_searchset.begin() !=
00124                current_indexes_searchset.end());
00125 
00126         string optionval = *current_indexes_searchset.begin();
00127         current_indexes_searchset.erase(current_indexes_searchset.begin());
00128 
00129         return TVec<string>(1,optionval);
00130     }
00131 }
00132 
00133 void StepwiseSelectionOracle::forget()
00134 {
00135     base_selected_variables.resize(0);
00136     current_indexes_searchset.clear();
00137     combination_performance = priority_queue< pair<real,string> >();
00138     last_combination=false;
00139 }
00140 
00141 void StepwiseSelectionOracle::build_()
00142 {
00143     forget();
00144 }
00145 
00146 // ### Nothing to add here, simply calls build_
00147 void StepwiseSelectionOracle::build()
00148 {
00149     inherited::build();
00150     build_();
00151 }
00152 
00153 void StepwiseSelectionOracle::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00154 {
00155     inherited::makeDeepCopyFromShallowCopy(copies);
00156     deepCopyField(base_selected_variables, copies);
00157 }
00158 
00159 void StepwiseSelectionOracle::generateNewSearchset()
00160 {
00161     if (last_combination)
00162         return;
00163 
00164     // First find the best-performing combination in combination_performance
00165     // and convert the option string into a vector of ints to obtain the new
00166     // base_selected_variables
00167     if (combination_performance.size() > 0) {
00168         const pair<real,string>& min_objective = combination_performance.top();
00169         const string& option = min_objective.second;
00170         PStream option_stream = openString(option,PStream::plearn_ascii);
00171         option_stream >> base_selected_variables;
00172     }
00173     else {
00174         // There should have been nothing computed before...
00175         PLASSERT( base_selected_variables.size() == 0);
00176     }
00177 
00178     // Second, find the remaining variables (not in base_selected_variables)
00179     TVec<int> range(0,maxvars-1,1);
00180     set<int> remaining_vars(range.begin(), range.end());
00181     for(int i=0, n=base_selected_variables.size() ; i<n ; ++i)
00182         remaining_vars.erase(base_selected_variables[i]);
00183 
00184     // Third, make up a new current_indexes_searchset if we have not yet
00185     // reached maxvars
00186     current_indexes_searchset.clear();
00187     combination_performance = priority_queue< pair<real,string> >();
00188     int newsize = base_selected_variables.size() + 1;
00189     if (newsize > maxvars) {
00190         last_combination = true;
00191         return;
00192     }
00193 
00194     TVec<int> new_combination(newsize);
00195     new_combination.subVec(0, newsize-1) << base_selected_variables;
00196     for (set<int>::iterator it = remaining_vars.begin() ;
00197          it != remaining_vars.end() ; ++it) {
00198         new_combination[newsize-1] = *it;
00199         ostringstream newoption;
00200         PStream newoption_stream(&newoption, false /* don't own */);
00201         newoption_stream << new_combination;
00202         current_indexes_searchset.insert(newoption.str());
00203     }
00204 }
00205 
00206 } // end of namespace PLearn
00207 
00208 
00209 /*
00210   Local Variables:
00211   mode:c++
00212   c-basic-offset:4
00213   c-file-style:"stroustrup"
00214   c-file-offsets:((innamespace . 0)(inline-open . 0))
00215   indent-tabs-mode:nil
00216   fill-column:79
00217   End:
00218 */
00219 // 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