PLearn 0.1
|
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 :