PLearn 0.1
|
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 :