PLearn 0.1
RemoveDuplicateVMatrix.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // RemoveDuplicateVMatrix.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: RemoveDuplicateVMatrix.cc 9192 2008-07-02 16:48:44Z nouiz $
00037  ******************************************************* */
00038 
00039 // Authors: Olivier Delalleau
00040 
00044 #include "RemoveDuplicateVMatrix.h"
00045 #include <plearn/base/tostring.h>
00046 #include <plearn/ker/DistanceKernel.h>
00047 
00048 namespace PLearn {
00049 using namespace std;
00050 
00052 // RemoveDuplicateVMatrix //
00054 RemoveDuplicateVMatrix::RemoveDuplicateVMatrix()
00055     : epsilon(1e-6),
00056       max_source_length(10000),
00057       only_input(false),
00058       verbosity(1)
00059 {
00060     // ...
00061     // ### You may or may not want to call build_() to finish building the object
00062     // build_();
00063 }
00064 
00065 PLEARN_IMPLEMENT_OBJECT(RemoveDuplicateVMatrix,
00066                         "A VMatrix that removes any duplicated entry in its source VMat.",
00067                         ""
00068     );
00069 
00071 // declareOptions //
00073 void RemoveDuplicateVMatrix::declareOptions(OptionList& ol)
00074 {
00075     // ### Declare all of this object's options here
00076     // ### For the "flags" of each option, you should typically specify
00077     // ### one of OptionBase::buildoption, OptionBase::learntoption or
00078     // ### OptionBase::tuningoption. Another possible flag to be combined with
00079     // ### is OptionBase::nosave
00080 
00081     declareOption(ol, "epsilon", &RemoveDuplicateVMatrix::epsilon, OptionBase::buildoption,
00082                   "Two points will be considered equal iff their square distance is < epsilon.\n"
00083                   "If epsilon is set to 0, a more accurate check is performed and only samples\n"
00084                   "which are perfectly equal are removed.\n");
00085 
00086     declareOption(ol, "only_input", &RemoveDuplicateVMatrix::only_input, OptionBase::buildoption,
00087                   "If set to 1, only the input part will be considered when computing the inter-points\n"
00088                   "distance. If set to 0, the whole row of the matrix is considered.\n");
00089 
00090     declareOption(ol, "max_source_length", &RemoveDuplicateVMatrix::max_source_length, OptionBase::buildoption,
00091                   "If the source's length is higher than this value, the whole Gram matrix will\n"
00092                   "not be stored in memory (which will be slightly slower).\n");
00093 
00094     declareOption(ol, "verbosity", &RemoveDuplicateVMatrix::verbosity, OptionBase::buildoption,
00095                   "Controls the amount of output.");
00096 
00097     // Now call the parent class' declareOptions
00098     inherited::declareOptions(ol);
00099 
00100     redeclareOption(ol, "indices", &RemoveDuplicateVMatrix::indices, OptionBase::nosave,
00101                     "The indices will be computed at build time.");
00102     redeclareOption(ol, "indices_vmat", &RemoveDuplicateVMatrix::indices_vmat, OptionBase::nosave,
00103                     "Unused.");
00104 }
00105 
00107 // build //
00109 void RemoveDuplicateVMatrix::build()
00110 {
00111     // ### Nothing to add here, simply calls build_
00112     inherited::build();
00113     build_();
00114 }
00115 
00117 // build_ //
00119 void RemoveDuplicateVMatrix::build_()
00120 {
00121     updateMtime(indices_vmat);
00122     updateMtime(source);
00123 
00124     if (source) {
00125         DistanceKernel dk;
00126         dk.pow_distance = true;
00127         if (verbosity >= 1)
00128             dk.report_progress = true;
00129         else
00130             dk.report_progress = false;
00131         dk.build();
00132         int old_is = source->inputsize();
00133         int old_ts = source->targetsize();
00134         int old_ws = source->weightsize();
00135         if (!only_input)
00136             source->defineSizes(source->width(), 0, 0);
00137         dk.setDataForKernelMatrix(source);
00138         int n = source.length();
00139         bool compute_gram = (n <= max_source_length);
00140         Mat distances;
00141         if (compute_gram) {
00142             if (n > 10000 && verbosity >= 2)
00143                 PLWARNING("In RemoveDuplicateVMatrix::build_ - Computing a large Gram "
00144                           "matrix (%d x %d), there may not be enough memory available", n, n);
00145             distances.resize(n, n);
00146             dk.computeGramMatrix(distances);
00147         }
00148         if (!only_input)
00149             source->defineSizes(old_is, old_ts, old_ws);
00150         TVec<bool> removed(n);
00151         removed.fill(false);
00152         Vec row_i, row_j;
00153         if (fast_exact_is_equal(epsilon, 0) || !compute_gram) {
00154             int w = only_input ? source->inputsize() : source->width();
00155             row_i.resize(w);
00156             row_j.resize(w);
00157         }
00158         real delta = epsilon > 0 ? epsilon : 1e-4;
00159         int count = 0;
00160         PP<ProgressBar> pb;
00161         bool report_progress = (!compute_gram && verbosity >= 1);
00162         int iterate = 0;
00163         if (report_progress)
00164             pb = new ProgressBar("Looking for duplicated entries", (n * (n - 1)) / 2);
00165         for (int i = 0; i < n; i++) {
00166             if (!removed[i]) {
00167                 if (!compute_gram)
00168                     source->getSubRow(i, 0, row_i);
00169                 for (int j = i + 1; j < n; j++) {
00170                     if (!removed[j]) {
00171                         bool equal;
00172                         if (compute_gram)
00173                             equal = (distances(i,j) < delta);
00174                         else {
00175                             source->getSubRow(j, 0, row_j);
00176                             equal = (dk.evaluate(row_i, row_j) < delta);
00177                         }
00178                         if (equal && fast_exact_is_equal(epsilon, 0)) {
00179                             // More accurate check.
00180                             if (compute_gram) {
00181                                 source->getSubRow(i, 0, row_i);
00182                                 source->getSubRow(j, 0, row_j);
00183                             }
00184                             real* data_i = row_i->data();
00185                             real* data_j = row_j->data();
00186                             int w = row_i->length();
00187                             for (int k = 0; k < w; k++, data_i++, data_j++)
00188                                 if (!fast_exact_is_equal(*data_i, *data_j))
00189                                     equal = false;
00190                         }
00191                         if (equal) {
00192                             if (verbosity >= 5)
00193                                 pout << "Removed sample "           << j
00194                                      << " (duplicated with sample " << i << ")" << endl;
00195                             removed[j] = true;
00196                             count++;
00197                         }
00198                     }
00199                 }
00200             }
00201             iterate += (n - i);
00202             if (report_progress)
00203                 pb->update(iterate);
00204         }
00205         indices.resize(0);
00206         for (int i = 0; i < n; i++)
00207             if (!removed[i])
00208                 indices.append(i);
00209         inherited::build();
00210         if (verbosity >= 2){
00211             if (count > 0)
00212                 pout << "Removed a total of " << count << " duplicated samples (new length: "
00213                      << length() << ")" << endl;
00214             else
00215                 pout << "No duplicated samples found." << endl;
00216         }
00217     }
00218 }
00219 
00221 // makeDeepCopyFromShallowCopy //
00223 void RemoveDuplicateVMatrix::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00224 {
00225     inherited::makeDeepCopyFromShallowCopy(copies);
00226 
00227     // ### Call deepCopyField on all "pointer-like" fields
00228     // ### that you wish to be deepCopied rather than
00229     // ### shallow-copied.
00230     // ### ex:
00231     // deepCopyField(trainvec, copies);
00232 
00233     // ### Remove this line when you have fully implemented this method.
00234     PLERROR("RemoveDuplicateVMatrix::makeDeepCopyFromShallowCopy not fully (correctly) implemented yet!");
00235 }
00236 
00237 } // end of namespace PLearn
00238 
00239 
00240 /*
00241   Local Variables:
00242   mode:c++
00243   c-basic-offset:4
00244   c-file-style:"stroustrup"
00245   c-file-offsets:((innamespace . 0)(inline-open . 0))
00246   indent-tabs-mode:nil
00247   fill-column:79
00248   End:
00249 */
00250 // 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