PLearn 0.1
AdditiveNormalizationKernel.cc
Go to the documentation of this file.
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 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines