PLearn 0.1
RepeatSplitter.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // RepeatSplitter.cc
00004 //
00005 // Copyright (C) 2003 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: RepeatSplitter.cc 9408 2008-08-27 17:47:25Z nouiz $
00037  ******************************************************* */
00038 
00041 #include "RepeatSplitter.h"
00042 #include <plearn/math/random.h>
00043 #include "SelectRowsVMatrix.h"
00044 
00045 namespace PLearn {
00046 using namespace std;
00047 
00049 // RepeatSplitter //
00051 RepeatSplitter::RepeatSplitter()
00052     :
00053     last_n(-1),
00054     do_not_shuffle_first(0),
00055     force_proportion(-1),
00056     n(1),
00057     seed(-1),
00058     shuffle(0)
00059 {
00060 }
00061 
00062 PLEARN_IMPLEMENT_OBJECT(RepeatSplitter,
00063                         "Repeat a given splitter a certain amount of times, with the possibility to\n"
00064                         "shuffle randomly the dataset each time",
00065                         "NO HELP");
00066 
00068 // declareOptions //
00070 void RepeatSplitter::declareOptions(OptionList& ol)
00071 {
00072     declareOption(ol, "do_not_shuffle_first", &RepeatSplitter::do_not_shuffle_first, OptionBase::buildoption,
00073                   "If set to 1, then the dataset won't be shuffled the first time we do the splitting.\n"
00074                   "It only makes sense to use this option if 'shuffle' is set to 1.");
00075 
00076     declareOption(ol, "force_proportion", &RepeatSplitter::force_proportion, OptionBase::buildoption,
00077                   "If a target value appears at least once every x samples, will ensure that after\n"
00078                   "shuffling it appears at least once every (x * 'force_proportion') samples, and not\n"
00079                   "more than once every (x / 'force_proportion') samples. Will be ignored if < 1.\n"
00080                   "Note that this currently only works for a binary target! (and hasn't been 100% tested).");
00081 
00082     declareOption(ol, "n", &RepeatSplitter::n, OptionBase::buildoption,
00083                   "How many times we want to repeat.");
00084 
00085     declareOption(ol, "seed", &RepeatSplitter::seed, OptionBase::buildoption,
00086                   "Initializes the random number generator (only if shuffle is set to 1).\n"
00087                   "If set to -1, the initialization will depend on the clock.");
00088 
00089     declareOption(ol, "shuffle", &RepeatSplitter::shuffle, OptionBase::buildoption,
00090                   "If set to 1, the dataset will be shuffled differently at each repetition.");
00091 
00092     declareOption(ol, "to_repeat", &RepeatSplitter::to_repeat, OptionBase::buildoption,
00093                   "The splitter we want to repeat.");
00094 
00095     inherited::declareOptions(ol);
00096 }
00097 
00099 // build //
00101 void RepeatSplitter::build()
00102 {
00103     inherited::build();
00104     build_();
00105 }
00106 
00108 // build_ //
00110 void RepeatSplitter::build_()
00111 {
00112     if (shuffle && dataset) {
00113         // Prepare the shuffled indices.
00114         if (seed >= 0)
00115             manual_seed(seed);
00116         else
00117             PLearn::seed();
00118         int n_splits = nsplits();
00119         indices = TMat<int>(n_splits, dataset.length());
00120         TVec<int> shuffled;
00121         for (int i = 0; i < n_splits; i++) {
00122             shuffled = TVec<int>(0, dataset.length()-1, 1);
00123             // Don't shuffle if (i == 0) and do_not_shuffle_first is set to 1.
00124             if (!do_not_shuffle_first || i > 0) {
00125                 shuffleElements(shuffled);
00126                 if (force_proportion >= 1) {
00127                     // We need to ensure the proportions of target values are respected.
00128                     // First compute the target stats.
00129                     StatsCollector tsc(2000);
00130                     if (dataset->targetsize() != 1) {
00131                         PLERROR("In RepeatSplitter::build_ - 'force_proportion' is only implemented for a 1-dimensional target");
00132                     }
00133                     real t;
00134                     for (int j = 0; j < dataset->length(); j++) {
00135                         t = dataset->get(j, dataset->inputsize()); // We get the target.
00136                         tsc.update(t);
00137                     }
00138                     tsc.finalize();
00139                     // Make sure the target is binary.
00140                     int count = (int) tsc.getCounts()->size() - 1;
00141                     if (count != 2) {
00142                         PLERROR("In RepeatSplitter::build_ - 'force_proportion' is only implemented for a binary target");
00143                     }
00144                     // Ensure the proportion of the targets respect the constraints.
00145                     int index = 0;
00146                     for (map<real,StatsCollectorCounts>::iterator it =
00147                             tsc.getCounts()->begin(); index < count; index++)
00148                     {
00149                         t = it->first;
00150                         real prop_t = real(it->second.n) /
00151                                       real(dataset->length());
00152                         // Find the step to use to check the proportion is ok.
00153                         // We want a step such that each 'step' examples, there
00154                         // should be at least two with this target, but less
00155                         // than 'step - 10'.  For instance, for a proportion of
00156                         // 0.1, 'step' would be 20, and for a proportion of
00157                         // 0.95, it would be 200.  We also want the
00158                         // approximation made when rounding to be negligible.
00159                         int step = 20;
00160                         bool ok = false;
00161                         while (!ok) {
00162                             int n = int(step * prop_t + 0.5);
00163                             if (n >= 2  && n <= step - 10
00164                                 && abs(step * prop_t - real(n)) / real(step) < 0.01) {
00165                                 ok = true;
00166                             } else {
00167                                 // We try a higher step.
00168                                 step *= 2;
00169                             }
00170                         }
00171                         int expected_count = int(step * prop_t + 0.5);
00172                         // cout << "step = " << step << ", expected_count = " << expected_count << endl;
00173                         // Now verify the proportion.
00174                         ok = false;
00175                         int tc = dataset->inputsize(); // The target column.
00176                         while (!ok) {
00177                             ok = true;
00178                             // First pass: ensure there is enough.
00179                             int first_pass_step = int(step * force_proportion + 0.5);
00180                             int k,l;
00181                             for (k = 0; k < shuffled.length(); k += first_pass_step) {
00182                                 int count_target = 0;
00183                                 for (l = k; l < k + first_pass_step && l < shuffled.length(); l++) {
00184                                     if (fast_exact_is_equal(
00185                                             dataset->get(shuffled[l], tc), t))
00186                                         count_target++;
00187                                 }
00188                                 if (l - k == first_pass_step && count_target < expected_count) {
00189                                     // Not enough, need to add more.
00190                                     ok = false;
00191                                     // cout << "At l = " << l << ", need to add " << expected_count - count_target << " samples" << endl;
00192                                     for (int m = 0; m < expected_count - count_target; m++) {
00193                                         bool can_swap = false;
00194                                         int to_swap = -1;
00195                                         // Find a sample to swap in the current window.
00196                                         while (!can_swap) {
00197                                             to_swap = int(uniform_sample() * first_pass_step);
00198                                             if (!fast_exact_is_equal(dataset->get(shuffled[k + to_swap], tc), t)) {
00199                                                 can_swap = true;
00200                                             }
00201                                         }
00202                                         to_swap += k;
00203                                         // Find a sample to swap in the next samples.
00204                                         int next = k + first_pass_step - 1;
00205                                         can_swap = false;
00206                                         while (!can_swap) {
00207                                             next++;
00208                                             if (next >= shuffled.length()) {
00209                                                 next = 0;
00210                                             }
00211                                             if (fast_exact_is_equal(dataset->get(shuffled[next], tc), t)) {
00212                                                 can_swap = true;
00213                                             }
00214                                         }
00215                                         // And swap baby!
00216                                         int tmp = shuffled[next];
00217                                         shuffled[next] = shuffled[to_swap];
00218                                         shuffled[to_swap] = tmp;
00219                                     }
00220                                 }
00221                             }
00222                             // Second pass: ensure there aren't too many.
00223                             int second_pass_step = int(step / force_proportion + 0.5);
00224                             for (k = 0; k < shuffled.length(); k += second_pass_step) {
00225                                 int count_target = 0;
00226                                 for (l = k; l < k + second_pass_step && l < shuffled.length(); l++) {
00227                                     if (fast_exact_is_equal(dataset->get(shuffled[l], tc), count_target)) {
00228                                         count_target++;
00229                                     }
00230                                 }
00231                                 if (l - k == second_pass_step && count_target > expected_count) {
00232                                     // Too many, need to remove some.
00233                                     ok = false;
00234                                     PLWARNING("In RepeatSplitter::build_ - The code reached hasn't been tested yet");
00235                                     // cout << "At l = " << l << ", need to remove " << - expected_count + count_target << " samples" << endl;
00236                                     for (int m = 0; m < - expected_count + count_target; m++) {
00237                                         bool can_swap = false;
00238                                         int to_swap = k - 1;
00239                                         // Find a sample to swap in the current window.
00240                                         while (!can_swap) {
00241                                             to_swap++;
00242                                             if (fast_exact_is_equal(dataset->get(shuffled[to_swap], tc), t)) {
00243                                                 can_swap = true;
00244                                             }
00245                                         }
00246                                         // Find a sample to swap in the next samples.
00247                                         int next = k + first_pass_step - 1;
00248                                         can_swap = false;
00249                                         while (!can_swap) {
00250                                             next++;
00251                                             if (next >= shuffled.length()) {
00252                                                 next = 0;
00253                                             }
00254                                             if (!fast_exact_is_equal(dataset->get(shuffled[next], tc), t)) {
00255                                                 can_swap = true;
00256                                             }
00257                                         }
00258                                         // And swap baby!
00259                                         int tmp = shuffled[next];
00260                                         shuffled[next] = shuffled[to_swap];
00261                                         shuffled[to_swap] = tmp;
00262                                     }
00263                                 }
00264                             }
00265                         }
00266                         it++;
00267                     }
00268                 }
00269             }
00270             indices(i) << shuffled;
00271         }
00272     } else {
00273         indices = TMat<int>();
00274     }
00275     last_n = -1;
00276 }
00277 
00279 // makeDeepCopyFromShallowCopy //
00281 void RepeatSplitter::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00282 {
00283     inherited::makeDeepCopyFromShallowCopy(copies);
00284 
00285     // ### Call deepCopyField on all "pointer-like" fields
00286     // ### that you wish to be deepCopied rather than
00287     // ### shallow-copied.
00288     // ### ex:
00289     // deepCopyField(trainvec, copies);
00290 
00291     deepCopyField(to_repeat, copies);
00292 
00293 }
00294 
00296 // getSplit //
00298 TVec<VMat> RepeatSplitter::getSplit(int k)
00299 {
00300     int n_splits = this->nsplits();
00301     if (k >= n_splits) {
00302         PLERROR("In RepeatSplitter::getSplit: split asked is too high");
00303     }
00304     int child_splits = to_repeat->nsplits();
00305     int real_k = k % child_splits;
00306     if (shuffle && dataset) {
00307         int shuffle_indice = k / child_splits;
00308         if (shuffle_indice != last_n) {
00309             // We have to reshuffle the dataset, according to indices.
00310             VMat m = new SelectRowsVMatrix(dataset, indices(shuffle_indice),
00311                                            false, false);
00312             to_repeat->setDataSet(m);
00313             last_n = shuffle_indice;
00314         }
00315     }
00316     return to_repeat->getSplit(real_k);
00317 }
00318 
00320 // nSetsPerSplit //
00322 int RepeatSplitter::nSetsPerSplit() const
00323 {
00324     return to_repeat->nSetsPerSplit();
00325 }
00326 
00328 // nsplits //
00330 int RepeatSplitter::nsplits() const
00331 {
00332     return to_repeat->nsplits() * n;
00333 }
00334 
00336 // setDataSet //
00338 void RepeatSplitter::setDataSet(VMat the_dataset) {
00339     inherited::setDataSet(the_dataset);
00340     to_repeat->setDataSet(the_dataset);
00341     build(); // necessary to recompute the indices.
00342 }
00343 
00344 } // end of namespace PLearn
00345 
00346 
00347 /*
00348   Local Variables:
00349   mode:c++
00350   c-basic-offset:4
00351   c-file-style:"stroustrup"
00352   c-file-offsets:((innamespace . 0)(inline-open . 0))
00353   indent-tabs-mode:nil
00354   fill-column:79
00355   End:
00356 */
00357 // 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