PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // AdditiveNormalizationKernel.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: AdditiveNormalizationKernel.cc 3994 2005-08-25 13:35:03Z chapados $ 00037 ******************************************************* */ 00038 00039 // Authors: Olivier Delalleau 00040 00044 #include "AdditiveNormalizationKernel.h" 00045 00046 namespace PLearn { 00047 using namespace std; 00048 00050 // AdditiveNormalizationKernel // 00052 AdditiveNormalizationKernel::AdditiveNormalizationKernel() 00053 : total_average(0.), 00054 total_average_unbiased(0.), 00055 data_will_change(false), 00056 double_centering(false), 00057 remove_bias(false), 00058 remove_bias_in_evaluate(false) 00059 { } 00060 00061 AdditiveNormalizationKernel::AdditiveNormalizationKernel 00062 (Ker the_source, bool the_remove_bias, bool the_remove_bias_in_evaluate, 00063 bool the_double_centering) 00064 : total_average(0.), 00065 total_average_unbiased(0.), 00066 data_will_change(false), 00067 double_centering(the_double_centering), 00068 remove_bias(the_remove_bias), 00069 remove_bias_in_evaluate(the_remove_bias_in_evaluate) 00070 { 00071 source_kernel = the_source; 00072 build(); 00073 } 00074 00075 PLEARN_IMPLEMENT_OBJECT(AdditiveNormalizationKernel, 00076 "Normalizes additively an underlying kernel with respect to a training set.", 00077 "From a kernel K, defines a new kernel K' such that:\n" 00078 " K'(x,y) = K(x,y) - E[K(x,x_i)] - E[K(x_i,y)] + E[K(x_i,x_j)]\n" 00079 "where the expectation is performed on the data set.\n" 00080 "If the 'remove_bias' option is set, then the expectation will not\n" 00081 "take into account terms of the form K(x_i,x_i).\n" 00082 "If the 'double_centering' option is set, this kernel K' will be\n" 00083 "multiplied by -1/2 (this turns a squared distance kernel into a\n" 00084 "centered dot product kernel).\n" 00085 ); 00086 00088 // declareOptions // 00090 void AdditiveNormalizationKernel::declareOptions(OptionList& ol) 00091 { 00092 // Build options. 00093 00094 declareOption(ol, "double_centering", &AdditiveNormalizationKernel::double_centering, OptionBase::buildoption, 00095 "If set to 1, then the resulting kernel will be multiplied by -1/2,\n" 00096 "which corresponds to the double-centering formula."); 00097 00098 declareOption(ol, "data_will_change", &AdditiveNormalizationKernel::data_will_change, OptionBase::buildoption, 00099 "If set to 1, then the Gram matrix will be always recomputed, even if\n" 00100 "it's not completely sure the data has changed."); 00101 00102 declareOption(ol, "remove_bias", &AdditiveNormalizationKernel::remove_bias, OptionBase::buildoption, 00103 "If set to 1, then the bias induced by the K(x_i,x_i) will be removed.\n"); 00104 00105 declareOption(ol, "remove_bias_in_evaluate", &AdditiveNormalizationKernel::remove_bias_in_evaluate, OptionBase::buildoption, 00106 "If set to 1, then the bias induced by the K(x_i,x_i) will be removed, but only when\n" 00107 "evaluating K(x,y) on test points (you don't need to do this if 'remove_bias' == 1)."); 00108 00109 // Learnt options. 00110 00111 declareOption(ol, "average_col", &AdditiveNormalizationKernel::average_col, OptionBase::learntoption, 00112 "The average of the underlying kernel over each column of the Gram matrix."); 00113 00114 declareOption(ol, "average_row", &AdditiveNormalizationKernel::average_row, OptionBase::learntoption, 00115 "The average of the underlying kernel over each row of the Gram matrix."); 00116 00117 declareOption(ol, "total_average_unbiased", &AdditiveNormalizationKernel::total_average_unbiased, OptionBase::learntoption, 00118 "The average of the underlying kernel over the whole Gram matrix, without\n" 00119 "the diagonal terms."); 00120 00121 declareOption(ol, "total_average", &AdditiveNormalizationKernel::total_average, OptionBase::learntoption, 00122 "The average of the underlying kernel over the whole Gram matrix."); 00123 00124 // Now call the parent class' declareOptions 00125 inherited::declareOptions(ol); 00126 } 00127 00129 // build // 00131 void AdditiveNormalizationKernel::build() 00132 { 00133 // ### Nothing to add here, simply calls build_ 00134 inherited::build(); 00135 build_(); 00136 } 00137 00139 // build_ // 00141 void AdditiveNormalizationKernel::build_() 00142 { 00143 // ### This method should do the real building of the object, 00144 // ### according to set 'options', in *any* situation. 00145 // ### Typical situations include: 00146 // ### - Initial building of an object from a few user-specified options 00147 // ### - Building of a "reloaded" object: i.e. from the complete set of all serialised options. 00148 // ### - Updating or "re-building" of an object after a few "tuning" options have been modified. 00149 // ### You should assume that the parent class' build_() has already been called. 00150 if (double_centering) 00151 factor = -0.5; 00152 else 00153 factor = 1; 00154 } 00155 00157 // computeAverage // 00159 real AdditiveNormalizationKernel::computeAverage(const Vec& x, bool on_row, real squared_norm_of_x) const { 00160 all_k_x.resize(n_examples); 00161 if (is_symmetric || !on_row) { 00162 source_kernel->evaluate_all_i_x(x, all_k_x, squared_norm_of_x); 00163 } else { 00164 source_kernel->evaluate_all_x_i(x, all_k_x, squared_norm_of_x); 00165 } 00166 return sum(all_k_x) / real(n_examples); 00167 } 00168 00170 // computeGramMatrix // 00172 void AdditiveNormalizationKernel::computeGramMatrix(Mat K) const { 00173 // Uses default Kernel implementation. 00174 Kernel::computeGramMatrix(K); 00175 } 00176 00178 // evaluate // 00180 real AdditiveNormalizationKernel::evaluate(const Vec& x1, const Vec& x2) const { 00181 real avg_1 = computeAverage(x1, true); 00182 real avg_2 = computeAverage(x2, false); 00183 if (remove_bias || !remove_bias_in_evaluate) { 00184 // We can use the 'total_average'. 00185 return factor * (source_kernel->evaluate(x1, x2) - avg_1 - avg_2 + total_average); 00186 } else { 00187 // We need to use the 'total_average_unbiased'. 00188 return factor * (source_kernel->evaluate(x1, x2) - avg_1 - avg_2 + total_average_unbiased); 00189 } 00190 } 00191 00193 // evaluate_i_j // 00195 real AdditiveNormalizationKernel::evaluate_i_j(int i, int j) const { 00196 return factor * (source_kernel->evaluate_i_j(i,j) - average_row[i] - average_col[j] + total_average); 00197 } 00198 00200 // evaluate_i_x // 00202 real AdditiveNormalizationKernel::evaluate_i_x(int i, const Vec& x, real squared_norm_of_x) const { 00203 return factor * (source_kernel->evaluate_i_x(i, x, squared_norm_of_x) 00204 - average_row[i] - computeAverage(x, false, squared_norm_of_x) + total_average); 00205 } 00206 00208 // evaluate_i_x_again // 00210 real AdditiveNormalizationKernel::evaluate_i_x_again(int i, const Vec& x, real squared_norm_of_x, bool first_time) const { 00211 if (first_time) { 00212 avg_evaluate_i_x_again = computeAverage(x, false, squared_norm_of_x); 00213 } 00214 return factor * (source_kernel->evaluate_i_x_again(i, x, squared_norm_of_x, first_time) 00215 - average_row[i] - avg_evaluate_i_x_again + total_average); 00216 } 00217 00219 // evaluate_x_i // 00221 real AdditiveNormalizationKernel::evaluate_x_i(const Vec& x, int i, real squared_norm_of_x) const { 00222 return factor * (source_kernel->evaluate_x_i(x, i, squared_norm_of_x) 00223 - average_col[i] - computeAverage(x, true, squared_norm_of_x) + total_average); 00224 } 00225 00227 // evaluate_x_i_again // 00229 real AdditiveNormalizationKernel::evaluate_x_i_again(const Vec& x, int i, real squared_norm_of_x, bool first_time) const { 00230 if (first_time) { 00231 avg_evaluate_x_i_again = computeAverage(x, true, squared_norm_of_x); 00232 } 00233 return factor * (source_kernel->evaluate_x_i_again(x, i, squared_norm_of_x, first_time) 00234 - average_col[i] - avg_evaluate_x_i_again + total_average); 00235 } 00236 00238 // makeDeepCopyFromShallowCopy // 00240 void AdditiveNormalizationKernel::makeDeepCopyFromShallowCopy(CopiesMap& copies) 00241 { 00242 inherited::makeDeepCopyFromShallowCopy(copies); 00243 deepCopyField(all_k_x, copies); 00244 deepCopyField(average_col, copies); 00245 deepCopyField(average_row, copies); 00246 } 00247 00249 // setDataForKernelMatrix // 00251 void AdditiveNormalizationKernel::setDataForKernelMatrix(VMat the_data) { 00252 bool there_was_data_and_it_changed = data && !(data->looksTheSameAs(the_data)); 00253 // Set the data for this kernel as well as for the underlying kernel. 00254 inherited::setDataForKernelMatrix(the_data); 00255 // Check whether we need to recompute the Gram matrix and its average. 00256 int n = the_data->length(); 00257 if ( data_will_change 00258 || average_row.length() != n 00259 || there_was_data_and_it_changed) { 00260 // Compute the underlying Gram matrix. 00261 Mat gram(n, n); 00262 source_kernel->computeGramMatrix(gram); 00263 // Compute the row (and column) average. 00264 average_row.resize(n); 00265 average_row.fill(0); 00266 if (is_symmetric) { 00267 average_col = average_row; 00268 } else { 00269 average_col.resize(n); 00270 average_col.fill(0); 00271 } 00272 real k_x_x; 00273 total_average_unbiased = 0; 00274 for (int i = 0; i < n; i++) { 00275 if (is_symmetric) { 00276 real v; 00277 k_x_x = gram(i,i); 00278 if (!remove_bias) { 00279 average_row[i] += k_x_x; 00280 total_average_unbiased -= k_x_x; 00281 } 00282 for (int j = i + 1; j < n; j++) { 00283 v = gram(i,j); 00284 average_row[i] += v; 00285 average_row[j] += v; 00286 } 00287 } else { 00288 for (int j = 0; j < n; j++) { 00289 if (!remove_bias || j != i) { 00290 average_row[i] += gram(i,j); 00291 average_col[i] += gram(j,i); 00292 if (j == i) { 00293 total_average_unbiased -= gram(i,j); 00294 } 00295 } 00296 } 00297 } 00298 } 00299 total_average = sum(average_row); 00300 if (remove_bias) { 00301 // The sum is already unbiased. 00302 total_average_unbiased = total_average; 00303 } else { 00304 // At this point, 'total_average_unbiased' = - \sum K(x_i,x_i). 00305 total_average_unbiased += total_average; 00306 } 00307 real n_terms_in_sum; // The number of terms summed in average_row. 00308 if (remove_bias) { 00309 // The diagonal terms were not added. 00310 n_terms_in_sum = real(n - 1); 00311 } else { 00312 n_terms_in_sum = real(n); 00313 } 00314 total_average /= real(n * n_terms_in_sum); 00315 total_average_unbiased /= real(n * (n-1)); 00316 average_row /= n_terms_in_sum; 00317 if (!is_symmetric) { 00318 average_col /= n_terms_in_sum; 00319 } 00320 } 00321 } 00322 00323 } // end of namespace PLearn 00324 00325 00326 /* 00327 Local Variables: 00328 mode:c++ 00329 c-basic-offset:4 00330 c-file-style:"stroustrup" 00331 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00332 indent-tabs-mode:nil 00333 fill-column:79 00334 End: 00335 */ 00336 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :