PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // OptimizeOptionOracle.cc 00004 // 00005 // Copyright (C) 2004 Olivier Delalleau 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: OptimizeOptionOracle.cc 7690 2007-07-04 02:55:38Z lamblin $ 00037 ******************************************************* */ 00038 00039 // Authors: Olivier Delalleau 00040 00043 #include "OptimizeOptionOracle.h" 00044 #include <plearn/math/random.h> 00045 #include <plearn/base/stringutils.h> 00046 00047 namespace PLearn { 00048 using namespace std; 00049 00050 PLEARN_IMPLEMENT_OBJECT(OptimizeOptionOracle, 00051 "This Oracle tries to optimize a given option (which must be a real number).", 00052 "It starts from the value provided by the user, then tries higher and lower\n" 00053 "values in order to try and find the minimum cost.\n" 00054 "The algorithm employed is very basic, and subject to fall into local minima.\n" 00055 ); 00056 00058 // OptimizeOptionOracle // 00060 OptimizeOptionOracle::OptimizeOptionOracle() 00061 : current_direction("not_started"), 00062 lower_bound(1), 00063 n_steps(0), 00064 upper_bound(-1), 00065 factor(2), 00066 max_steps(10), 00067 max_value(REAL_MAX), 00068 min_value(-REAL_MAX), 00069 relative_precision(0.5), 00070 option(""), 00071 start_direction("random"), 00072 start_value(0) 00073 {} 00074 00076 // declareOptions // 00078 void OptimizeOptionOracle::declareOptions(OptionList& ol) 00079 { 00080 declareOption(ol, "option", &OptimizeOptionOracle::option, OptionBase::buildoption, 00081 "The name of the option to optimize."); 00082 00083 declareOption(ol, "max_steps", &OptimizeOptionOracle::max_steps, OptionBase::buildoption, 00084 "The maximum number of steps performed."); 00085 00086 declareOption(ol, "start_value", &OptimizeOptionOracle::start_value, OptionBase::buildoption, 00087 "The value we start from for this option."); 00088 00089 declareOption(ol, "min_value", &OptimizeOptionOracle::min_value, OptionBase::buildoption, 00090 "The minimum value that should be tried."); 00091 00092 declareOption(ol, "max_value", &OptimizeOptionOracle::max_value, OptionBase::buildoption, 00093 "The maximum value that should be tried."); 00094 00095 declareOption(ol, "relative_precision", &OptimizeOptionOracle::relative_precision, OptionBase::buildoption, 00096 "The precision to which we want to find the optimal option. For instance\n" 00097 "0.1 would indicate we want the 'best' value to be found in an interval\n" 00098 "of the kind [best - 10% * best, best + 10% * best]."); 00099 00100 declareOption(ol, "factor", &OptimizeOptionOracle::factor, OptionBase::buildoption, 00101 "The factor by which we multiply / divide the current value after\n" 00102 "we started from 'start_value'."); 00103 00104 declareOption(ol, "start_direction", &OptimizeOptionOracle::start_direction, OptionBase::buildoption, 00105 "The direction we start going to ('up', 'down' or 'random')."); 00106 00107 //*************** 00108 00109 declareOption(ol, "best", &OptimizeOptionOracle::best, OptionBase::learntoption, 00110 "The best value found so far."); 00111 00112 declareOption(ol, "best_objective", &OptimizeOptionOracle::best_objective, OptionBase::learntoption, 00113 "The objective obtained with option = 'best'."); 00114 00115 declareOption(ol, "current_direction", &OptimizeOptionOracle::current_direction, OptionBase::learntoption, 00116 "The current direction we are going ('up', 'down' or 'not_started')."); 00117 00118 declareOption(ol, "lower_bound", &OptimizeOptionOracle::lower_bound, OptionBase::learntoption, 00119 "The lower bound of the interval in which we working."); 00120 00121 declareOption(ol, "n_steps", &OptimizeOptionOracle::n_steps, OptionBase::learntoption, 00122 "The number of steps performed so far."); 00123 00124 declareOption(ol, "upper_bound", &OptimizeOptionOracle::upper_bound, OptionBase::learntoption, 00125 "The upper bound of the interval in which we working."); 00126 00127 // Now call the parent class' declareOptions 00128 inherited::declareOptions(ol); 00129 } 00130 00132 // build // 00134 void OptimizeOptionOracle::build() { 00135 inherited::build(); 00136 build_(); 00137 } 00138 00140 // build_ // 00142 void OptimizeOptionOracle::build_() 00143 { 00144 if (min_value > max_value) { 00145 PLERROR("In OptimizeOptionOracle::build_ - You specified a min_value higher than max_value"); 00146 } 00147 if (lower_bound > upper_bound) { 00148 // Should only happen when this object is built for the first time. 00149 lower_bound = min_value; 00150 upper_bound = max_value; 00151 } 00152 } 00153 00155 // forget // 00157 void OptimizeOptionOracle::forget() 00158 { 00159 current_direction = "not_started"; 00160 lower_bound = min_value; 00161 upper_bound = max_value; 00162 n_steps = 0; 00163 } 00164 00166 // getOptionNames // 00168 TVec<string> OptimizeOptionOracle::getOptionNames() const { 00169 return TVec<string>(1,option); 00170 } 00171 00173 // generateNextTrial // 00175 TVec<string> OptimizeOptionOracle::generateNextTrial(const TVec<string>& older_trial, real obtained_objective) 00176 { 00177 if (n_steps >= max_steps) { 00178 // Time to stop. 00179 TVec<string> empty(0); 00180 return empty; 00181 } else { 00182 n_steps++; 00183 } 00184 00185 if (older_trial.length() == 0) { 00186 // This is the first try: we just start with the given start value. 00187 best = start_value; 00188 best_objective = REAL_MAX; 00189 return TVec<string>(1, tostring(start_value)); 00190 } 00191 00192 // We can stop if the interval is restrained enough. 00193 if (lower_bound >= best - (best * relative_precision) && 00194 upper_bound <= best + (best * relative_precision)) { 00195 TVec<string> empty(0); 00196 return empty; 00197 } 00198 00199 real last = toreal(older_trial[0]); // The last value tried 00200 bool improved = false; 00201 if (obtained_objective < best_objective) { 00202 improved = true; 00203 best_objective = obtained_objective; 00204 } 00205 00206 if (current_direction == "not_started") { 00207 // This is the second try. 00208 if (start_direction == "random") { 00209 // Need to start with a random direction. 00210 real t = uniform_sample(); 00211 if (t < 0.5) { 00212 current_direction = "up"; 00213 } else { 00214 current_direction = "down"; 00215 } 00216 } else { 00217 current_direction = start_direction; 00218 } 00219 } else { 00220 // Find out in which direction we should go now. 00221 if (improved) { 00222 // Going in the 'current_direction' helped, let's keep going. 00223 if (current_direction == "up") { 00224 lower_bound = best; 00225 } else { 00226 upper_bound = best; 00227 } 00228 } else { 00229 // Going in the 'current_direction' didn't help. We go the other way. 00230 if (current_direction == "up") { 00231 current_direction = "down"; 00232 upper_bound = last; 00233 } else { 00234 current_direction = "up"; 00235 lower_bound = last; 00236 } 00237 } 00238 } 00239 00240 if (improved) { 00241 best = last; 00242 } 00243 00244 real next = 0; // The next value we are going to try. 00245 if (current_direction == "up") { 00246 if (best * factor < upper_bound*0.99) { 00247 // We can try much higher (the 0.99 is there to ensure we do not indefinitely 00248 // try the same 'upper_bound' value). 00249 next = best * factor; 00250 } else { 00251 // We take the middle point between 'best' and 'upper_bound'. 00252 next = (best + upper_bound) / 2; 00253 } 00254 } else if (current_direction == "down") { 00255 if (best / factor > lower_bound*1.01) { 00256 // We can try much lower. 00257 next = best / factor; 00258 } else { 00259 // We take the middle point between 'best' and 'lower_bound'. 00260 next = (best + lower_bound) / 2; 00261 } 00262 } else { 00263 PLERROR("In OptimizeOptionOracle::generateNextTrial - Wrong value for 'current_direction'"); 00264 } 00265 return TVec<string>(1, tostring(next)); 00266 } 00267 00269 // makeDeepCopyFromShallowCopy // 00271 void OptimizeOptionOracle::makeDeepCopyFromShallowCopy(CopiesMap& copies) 00272 { 00273 inherited::makeDeepCopyFromShallowCopy(copies); 00274 00275 // ### Call deepCopyField on all "pointer-like" fields 00276 // ### that you wish to be deepCopied rather than 00277 // ### shallow-copied. 00278 // ### ex: 00279 // deepCopyField(trainvec, copies); 00280 00281 // ### Remove this line when you have fully implemented this method. 00282 PLERROR("OptimizeOptionOracle::makeDeepCopyFromShallowCopy not fully (correctly) implemented yet!"); 00283 } 00284 00285 } // end of namespace PLearn 00286 00287 00288 /* 00289 Local Variables: 00290 mode:c++ 00291 c-basic-offset:4 00292 c-file-style:"stroustrup" 00293 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00294 indent-tabs-mode:nil 00295 fill-column:79 00296 End: 00297 */ 00298 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :