PLearn 0.1
OptimizeOptionOracle.cc
Go to the documentation of this file.
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 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines