PLearn 0.1
LiftStatsCollector.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PLearn (A C++ Machine Learning Library)
00004 // Copyright (C) 1998 Pascal Vincent
00005 // Copyright (C) 1999-2002 Pascal Vincent, Yoshua Bengio and University of Montreal
00006 // Copyright (C) 2003 Olivier Delalleau
00007 //
00008 
00009 // Redistribution and use in source and binary forms, with or without
00010 // modification, are permitted provided that the following conditions are met:
00011 //
00012 //  1. Redistributions of source code must retain the above copyright
00013 //     notice, this list of conditions and the following disclaimer.
00014 //
00015 //  2. Redistributions in binary form must reproduce the above copyright
00016 //     notice, this list of conditions and the following disclaimer in the
00017 //     documentation and/or other materials provided with the distribution.
00018 //
00019 //  3. The name of the authors may not be used to endorse or promote
00020 //     products derived from this software without specific prior written
00021 //     permission.
00022 //
00023 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00024 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00025 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00026 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00027 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00028 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00029 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00030 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00031 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00032 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00033 //
00034 // This file is part of the PLearn library. For more information on the PLearn
00035 // library, go to the PLearn Web site at www.plearn.org
00036 
00037 /* *******************************************************
00038  * $Id: LiftStatsCollector.cc 4511 2005-11-14 17:02:00Z tihocan $
00039  * This file is part of the PLearn library.
00040  ******************************************************* */
00041 
00044 #include "LiftStatsCollector.h"
00045 #include "TMat_maths.h"
00046 #include <plearn/base/stringutils.h>
00047 #include <plearn/io/openString.h>
00048 
00049 namespace PLearn {
00050 using namespace std;
00051 
00053 // LiftStatsCollector //
00055 LiftStatsCollector::LiftStatsCollector() 
00056     : inherited(),
00057       count_fin(0),
00058       is_finalized(false),
00059       nstored(0),
00060       nsamples(0),
00061       npos(0),
00062       output_column_index(0),
00063       lift_file(""),
00064       lift_fraction(0.1),
00065       opposite_lift(false),
00066       output_column(""),
00067       roc_file(""),
00068       sign_trick(0),
00069       target_column(1),
00070       verbosity(0)
00071 {
00072 }
00073 
00075 // Object stuff //
00077 PLEARN_IMPLEMENT_OBJECT(
00078     LiftStatsCollector,
00079     "(DEPRECATED) Used to evaluate the performance of a binary classifier.",
00080     "The following statistics can be requested out of getStat():\n"
00081     "- LIFT = % of positive examples in the first n samples, divided by the % of positive examples in the whole database\n"
00082     "- LIFT_MAX = best performance that could be achieved, if all positive examples were selected in the first n samples\n"
00083     "- AUC = Area Under the Curve (i.e. the ROC curve), approximated by evaluation at each point of 'roc_fractions'\n"
00084     "(where n = lift_fraction * nsamples).\n"
00085     "IMPORTANT: if you add more samples after you call finalize() (or get any of the statistics above), some samples may\n"
00086     "be wrongly discarded and further statistics may be wrong\n\n"
00087     "Here are the typical steps to follow to optimize the lift with a neural network:\n"
00088     "- add a lift_output cost to cost_funcs (e.g. cost_funcs = [ \"stable_cross_entropy\" \"lift_output\"];)\n"
00089     "- change the template_stats_collector of your PTester:\n"
00090     "    template_stats_collector =\n"
00091     "      LiftStatsCollector (\n"
00092     "        output_column = \"lift_output\" ;\n"
00093     "        opposite_lift = 1 ; # if you want to optimize the lift\n"
00094     "        sign_trick = 1 ;\n"
00095     "      )\n"
00096     "- add the lift to its statnames:\n"
00097     "    statnames = [ \"E[train.E[stable_cross_entropy]]\",\"E[test.E[stable_cross_entropy]]\",\n"
00098     "                  \"E[train.LIFT]\", \"E[test.LIFT]\" ]\n"
00099     "- maybe also change which_cost in your HyperOptimize strategy.\n"
00100 
00101     );
00102 
00103 void LiftStatsCollector::declareOptions(OptionList& ol)
00104 {
00105 
00106     declareOption(ol, "lift_fraction", &LiftStatsCollector::lift_fraction, OptionBase::buildoption,
00107                   "    the % of samples to consider (default = 0.1)\n");
00108 
00109     declareOption(ol, "opposite_lift", &LiftStatsCollector::opposite_lift, OptionBase::buildoption,
00110                   "    If set to 1, the LIFT stat will return -LIFT, so that it can be considered as a cost (default = 0)\n"
00111                   "    Similarly, the AUC stat will return -AUC.");
00112 
00113     declareOption(ol, "output_column", &LiftStatsCollector::output_column, OptionBase::buildoption,
00114                   "    the name of the column in which is the output value (the default value, \"\", assumes it is the first column))\n");
00115 
00116     declareOption(ol, "sign_trick", &LiftStatsCollector::sign_trick, OptionBase::buildoption,
00117                   "    if set to 1, then you won't have to specify a target column: if the output is\n"
00118                   "    negative, the target will be assumed to be 0, and 1 otherwise - and in both cases\n"
00119                   "    we only consider the absolute value of the output\n"
00120                   "    (default = 0)\n"
00121         );
00122 
00123     declareOption(ol, "target_column", &LiftStatsCollector::target_column, OptionBase::buildoption,
00124                   "    the column in which is the target value (default = 1)\n");
00125 
00126     declareOption(ol, "verbosity", &LiftStatsCollector::verbosity, OptionBase::buildoption,
00127                   "    to be set >= 2 in order to display more info (default = 0)\n");
00128 
00129     declareOption(ol, "roc_file", &LiftStatsCollector::roc_file, OptionBase::buildoption,
00130                   "If provided, the points of the ROC curve computed for different fractions (see\n"
00131                   "'roc_fractions') will be appended in ASCII format to the given file.");
00132 
00133     declareOption(ol, "lift_file", &LiftStatsCollector::lift_file, OptionBase::buildoption,
00134                   "If provided, the lifts computed for different fractions (see 'roc_fractions')\n"
00135                   "will be appended in ASCII format to the given file.");
00136 
00137     declareOption(ol, "roc_fractions", &LiftStatsCollector::roc_fractions, OptionBase::buildoption,
00138                   "(Ordered) fractions used to compute and save points in the ROC curve, or additional lifts.");
00139 
00140     declareOption(ol, "count_fin", &LiftStatsCollector::count_fin, OptionBase::learntoption,
00141                   "    the number of times finalize() has been called since the last forget()");
00142 
00143     declareOption(ol, "roc_values", &LiftStatsCollector::roc_values, OptionBase::learntoption,
00144                   "    The values of the ROC curve, evaluated at the 'roc_fractions' points.");
00145 
00146     // Now call the parent class' declareOptions
00147     inherited::declareOptions(ol);
00148 }
00149 
00151 // build //
00153 void LiftStatsCollector::build()
00154 {
00155     inherited::build();
00156     build_();
00157 }
00158 
00160 // build_ //
00162 void LiftStatsCollector::build_()
00163 {
00164     /*
00165     PLDEPRECATED("The 'LiftStatsCollector class is now deprecated: one should "
00166                  "instead use a standard 'VecStatsCollector', that is now able"
00167                  " to compute lift statistics");
00168                  */
00169     if (output_column != "") {
00170         int i = this->getFieldNum(output_column);
00171         if (i >= 0) {
00172             output_column_index = i;
00173         } else {
00174             // Not found.
00175             output_column_index = 0;
00176         }
00177     } else {
00178         output_column_index = 0;
00179     }
00180 }
00181 
00183 // computeLift //
00185 real LiftStatsCollector::computeAUC() {
00186     if (!is_finalized)
00187         finalize();
00188     // Compute statistics.
00189     int n = roc_fractions.length();
00190     if (n <= 0)
00191         PLERROR("In LiftStatsCollector::computeAUC - You need to use the 'roc_fractions' option if you want to compute the AUC");
00192     real previous_val = 0;
00193     real previous_fraction = 0;
00194     real auc = 0;
00195     roc_fractions.append(1);  // Make sure we take into account the whole curve.
00196     roc_values.append(1);
00197     n++;
00198     for (int i = 0; i < n; i++) {
00199         real mean_val = (roc_values[i] + previous_val) / 2;
00200         real interval_width = roc_fractions[i] - previous_fraction;
00201         auc += interval_width * mean_val;
00202         previous_val = roc_values[i];
00203         previous_fraction = roc_fractions[i];
00204     }
00205     // Remove appended '1'.
00206     roc_fractions.resize(roc_fractions.length() - 1);
00207     roc_values.resize(roc_values.length() - 1);
00208     if (opposite_lift)
00209         return -auc;
00210     else
00211         return auc;
00212 }
00213 
00215 // computeLift //
00217 real LiftStatsCollector::computeLift() {
00218     if (!is_finalized)
00219         finalize();
00220     // Compute statistics.
00221 
00222     int npos_in_n_first = (int) sum(n_first_updates.column(1));
00223     real first_samples_perf = npos_in_n_first/ (real) n_samples_to_keep;
00224     real targets_perf = (npos_in_n_first + npos) / (real) nsamples;
00225     real lift = first_samples_perf/targets_perf*100.0;
00226     if (verbosity >= 10) {
00227         cout << "LiftStatsCollector : is_finalized=" << is_finalized << ", nstored="
00228              << nstored << ", nsamples=" << nsamples << ", npos=" << npos
00229              << ", n_samples_to_keep=" << n_samples_to_keep << ", lift_fraction="
00230              << lift_fraction << ", output_column=" << output_column << ", sign_trick="
00231              << sign_trick << ", target_column=" << target_column << ", verbosity= "
00232              << verbosity << endl;
00233     }
00234     if (verbosity >= 2) {
00235         cout << "There is a total of " << npos_in_n_first + npos <<
00236             " positive examples to discover." << endl;
00237         cout << "The learner found " << npos_in_n_first << 
00238             " of them in the fraction considered (" << lift_fraction << ")." << endl;
00239     }
00240     if (opposite_lift == 1) {
00241         return -lift;
00242     }
00243     return lift;
00244 }
00245 
00247 // computeLiftMax //
00249 real LiftStatsCollector::computeLiftMax() {
00250     if (!is_finalized)
00251         finalize();
00252     int npos_in_n_first = (int) sum(n_first_updates.column(1));
00253     real nones = npos_in_n_first + npos;
00254     real max_first_samples_perf =
00255         MIN(nones,(real)n_samples_to_keep) / (real) n_samples_to_keep;
00256     real targets_perf = (npos_in_n_first + npos) / (real) nsamples;
00257     real max_lift = max_first_samples_perf/targets_perf*100.0;
00258     return max_lift;
00259 }
00260 
00262 // finalize //
00264 void LiftStatsCollector::finalize()
00265 {
00266     n_first_updates.resize(nstored,2); // get rid of the extra space allocated.
00267 
00268     n_samples_to_keep = int(lift_fraction*nsamples);
00269 
00270     if (nstored > n_samples_to_keep) {
00271         // If not, then no change has to be made to n_first_updates.
00272 
00273         // Compute additional lifts if required.
00274         if (roc_fractions.length() > 0) {
00275             // Copy data to make sure we do not change anything.
00276             Mat data(n_first_updates.length(), n_first_updates.width());
00277             data << n_first_updates;
00278             sortRows(data, 0, false);
00279             // Create result file if does not exist already.
00280             string command;
00281             if (roc_file != "") {
00282                 command = "touch " + roc_file;
00283                 // cout << "Command: " << command << endl;
00284                 system(command.c_str());
00285             }
00286             if (lift_file != "") {
00287                 command = "touch " + lift_file;
00288                 // cout << "Command: " << command << endl;
00289                 system(command.c_str());
00290             }
00291             // Compute lifts.
00292             int nones = npos + int(sum(data.column(1)) + 1e-3);
00293             real frac_pos = nones / real(nsamples * 100);
00294             int lift_index = 0;
00295             int count_pos = 0;
00296             int sample_index = 0;
00297             string result_roc = "";
00298             string result_lift = "";
00299             roc_values.resize(roc_fractions.length());
00300             while (lift_index < roc_fractions.length()) {
00301                 while (sample_index < real(nsamples) * roc_fractions[lift_index]) {
00302                     if (data(sample_index, 1) == 1)
00303                         count_pos++;
00304                     sample_index++;
00305                 }
00306                 real lift_value = real(count_pos) / real(sample_index) / frac_pos;
00307                 real roc_value = real(count_pos) / real(nones);
00308                 roc_values[lift_index] = roc_value;
00309                 lift_index++;
00310                 result_roc += tostring(roc_value) + "\t";
00311                 result_lift += tostring(lift_value) + "\t";
00312             }
00313             // Save the lifts in the given file.
00314             // We only save if the number of samples seen is > 1, because it may happen
00315             // that when using an HyperLearner, train statistics are computed, and we
00316             // could have nsamples == 1.
00317             if (lift_file != "" && nsamples > 1) {
00318                 command = "echo " + result_lift + " >> " + lift_file;
00319                 // cout << "Command: " << command << endl;
00320                 system(command.c_str());
00321             }
00322             if (roc_file != "" && nsamples > 1) {
00323                 command = "echo " + result_roc + " >> " + roc_file;
00324                 // cout << "Command: " << command << endl;
00325                 system(command.c_str());
00326             }
00327         }
00328 
00329         // Make sure the highest ouputs are in the last n_samples_to_keep elements
00330         // of n_first_updates.
00331         if (n_samples_to_keep > 0) {
00332             selectAndOrder(n_first_updates, nstored - n_samples_to_keep);
00333         }
00334 
00335         // Count the number of positive examples in the lowest outputs.
00336         for (int i = 0; i < nstored - n_samples_to_keep; i++) {
00337             if (n_first_updates(i,1) == 1) {
00338                 npos++;
00339             }
00340         }
00341   
00342         // Clear the lowest outputs, that are now useless.
00343         for (int i = 0; i < n_samples_to_keep; i++) {
00344             n_first_updates(i,0) = n_first_updates(i + nstored - n_samples_to_keep, 0);
00345             n_first_updates(i,1) = n_first_updates(i + nstored - n_samples_to_keep, 1);
00346         }
00347         n_first_updates.resize(n_samples_to_keep, 2);
00348         nstored = n_samples_to_keep;
00349     }
00350 
00351     inherited::finalize();
00352     is_finalized = true;
00353     count_fin++;
00354     if (verbosity >= 10) {
00355         cout << "Called finalized " << count_fin << " times" << endl;
00356     }
00357 }
00358 
00360 // forget //
00362 void LiftStatsCollector::forget()
00363 {
00364     is_finalized = false;
00365     nstored = 0;
00366     npos = 0;
00367     nsamples = 0;
00368     n_first_updates.resize(0,0);
00369     n_first_updates.resize(1000,2);
00370     inherited::forget();
00371     count_fin = 0;
00372     roc_values.resize(0);
00373 }
00374 
00376 // getStat //
00378 double LiftStatsCollector::getStat(const string& statspec)
00379 {
00380     PStream str = openString(statspec,PStream::plearn_ascii);
00381     string parsed;
00382     str.smartReadUntilNext("(",parsed);
00383     if (parsed == "LIFT") {
00384         return computeLift();
00385     }
00386     else if (parsed == "LIFT_MAX") {
00387         return computeLiftMax();
00388     }
00389     else if (parsed == "AUC") {
00390         return computeAUC();
00391     }
00392     else
00393         return inherited::getStat(statspec);
00394 }
00395 
00397 // makeDeepCopyFromShallowCopy //
00399 void LiftStatsCollector::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00400 {
00401     inherited::makeDeepCopyFromShallowCopy(copies);
00402     deepCopyField(roc_values, copies);
00403     deepCopyField(n_first_updates, copies);
00404     deepCopyField(roc_fractions, copies);
00405 }
00406 
00408 // remove_observation //
00410 void LiftStatsCollector::remove_observation(const Vec& x, real weight) {
00411     // Not supported.
00412     PLERROR("In LiftStatsCollector::remove_observation - This method is not implemented");
00413 }
00414 
00416 // update //
00418 void LiftStatsCollector::update(const Vec& x, real w)
00419 {
00420     if (count_fin > 0) {
00421         // Depending on whether we compute additional lifts, this may be fatal or not.
00422         string msg = "In LiftStatsCollector::update - Called update after finalize (see help of LiftStatsCollector)";
00423         if (roc_file != "")
00424             PLERROR(msg.c_str());
00425         else
00426             PLWARNING(msg.c_str());
00427     }
00428     if (nstored == n_first_updates.length()) {
00429         n_first_updates.resize(MAX(1000,10*n_first_updates.length()), 2);
00430     }
00431     real output_val = x[output_column_index];
00432     if (is_missing(output_val)) {
00433         // Missing value: we just discard it.
00434         is_finalized = false;
00435         inherited::update(x,w);
00436         return;
00437     }
00438     real target = -1;
00439     switch(sign_trick) {
00440     case 0:
00441         // Normal behavior.
00442         n_first_updates(nstored, 0) = output_val;
00443         target = x[target_column];
00444         break;
00445     case 1:
00446         // Sign trick.
00447         n_first_updates(nstored, 0) = FABS(output_val);
00448         if (output_val <= 0) {
00449             x[output_column_index] = -output_val;
00450             target = 0;
00451         } else {
00452             target = 1;
00453 //        cout << "Positive example : " << x << " (output_val = " << output_val << ")" << endl;
00454         }
00455         break;
00456     default:
00457         PLERROR("Wrong value for sign_trick in LiftStatsCollector");
00458         break;
00459     }
00460     n_first_updates(nstored, 1) = target;
00461     if (target != 0 && target != 1) {
00462         PLERROR("In LiftStatsCollector::update - Target must be 0 or 1 !");
00463     }
00464     nsamples++;
00465     nstored++;
00466     is_finalized = false;
00467 
00468     inherited::update(x,w);
00469 }
00470 
00471 } // end of namespace PLearn
00472 
00473 
00474 /*
00475   Local Variables:
00476   mode:c++
00477   c-basic-offset:4
00478   c-file-style:"stroustrup"
00479   c-file-offsets:((innamespace . 0)(inline-open . 0))
00480   indent-tabs-mode:nil
00481   fill-column:79
00482   End:
00483 */
00484 // 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