PLearn 0.1
LLEKernel.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // LLEKernel.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: LLEKernel.cc 4313 2005-10-25 13:44:40Z tihocan $ 
00037  ******************************************************* */
00038 
00039 // Authors: Olivier Delalleau
00040 
00044 #include "LLEKernel.h"
00045 
00046 namespace PLearn {
00047 using namespace std;
00048 
00050 // LLEKernel //
00052 LLEKernel::LLEKernel() 
00053     : build_in_progress(false),
00054       reconstruct_ker(new ReconstructionWeightsKernel()),
00055       knn(5),
00056       reconstruct_coeff(-1),
00057       regularizer(1e-6)
00058 {
00059 }
00060 
00061 PLEARN_IMPLEMENT_OBJECT(LLEKernel,
00062                         "The kernel used in Locally Linear Embedding.",
00063                         "This kernel is the (weighted) sum of two kernels K' and K'', such that:\n"
00064                         " - K'(x_i, x_j) = \\delta_{ij}\n"
00065                         " - K'(x_i, x) = K'(x, x_i) = w(x, x_i), where w(x, x_i) is the weight of\n"
00066                         "   x_i in the reconstruction of x by its knn nearest neighbors in the\n"
00067                         "   training set\n"
00068                         " - K'(x, y) = 0\n"
00069                         " - K''(x_i, x_j) = W_{ij} + W_{ji} - \\sum_k W_{ki} W{kj}, where W is the\n"
00070                         "   matrix of weights w(x_i, x_j)\n"
00071                         " - K''(x, x_i) = K''(x_i, x) = 0\n"
00072                         "The weight of K' is given by the 'reconstruct_coeff' option: when this\n"
00073                         "weight tends to infinity, the mapping obtained is the same as the\n"
00074                         "out-of-sample extension proposed in (Saul and Roweis, 2002). To obtain\n"
00075                         "such a behavior, one should set 'reconstruct_coeff' to -1. This is the\n"
00076                         "default behavior, and it is suggested to keep it.\n"
00077     );
00078 
00080 // declareOptions //
00082 void LLEKernel::declareOptions(OptionList& ol)
00083 {
00084     declareOption(ol, "knn", &LLEKernel::knn, OptionBase::buildoption,
00085                   "The number of nearest neighbors considered.");
00086 
00087     declareOption(ol, "reconstruct_coeff", &LLEKernel::reconstruct_coeff, OptionBase::buildoption,
00088                   "The weight of K' in the weighted sum of K' and K''. If set to a negative\n"
00089                   "value, it will behave as its absolute value when evaluated on the training\n"
00090                   "points with the evaluate_i_j method, but will return only its absolute value\n"
00091                   "times K' when evaluated with the evaluate_i_x method.");
00092 
00093     declareOption(ol, "regularizer", &LLEKernel::regularizer, OptionBase::buildoption,
00094                   "The regularization factor used to make the linear systems stable.");
00095 
00096     // Now call the parent class' declareOptions
00097     inherited::declareOptions(ol);
00098 }
00099 
00101 // build //
00103 void LLEKernel::build()
00104 {
00105     build_in_progress = true;
00106     inherited::build();
00107     build_();
00108 }
00109 
00111 // build_ //
00113 void LLEKernel::build_()
00114 {
00115     // Let's make sure the value of 'reconstruct_coeff' is not set accidentally
00116     // to an unusual value.
00117     if (fast_exact_is_equal(reconstruct_coeff, 0)) {
00118         PLWARNING("In LLEKernel::build_ - 'reconstruct_coeff' is set to 0, you won't be able to apply this kernel out-of-sample");
00119     } else if (reconstruct_coeff > 0) {
00120         PLWARNING("In LLEKernel::build_ - 'reconstruct_coeff' is > 0, this may give weird results out-of-sample for small coefficients");
00121     } else if (fabs(reconstruct_coeff + 1) > 1e-6) {
00122         PLWARNING("In LLEKernel::build_ - 'reconstruct_coeff' is negative but not -1, this may give some very weird stuff out-of-sample");
00123     }
00124     reconstruct_ker->regularizer = this->regularizer;
00125     reconstruct_ker->knn = this->knn;
00126     reconstruct_ker->report_progress = this->report_progress;
00127     reconstruct_ker->build();
00128     build_in_progress = false;
00129     // This code, normally executed in Kernel::build_, can only be executed
00130     // now beause the kernel 'reconstruct_ker' has to be initialized.
00131     if (specify_dataset) {
00132         this->setDataForKernelMatrix(specify_dataset);
00133     }
00134 }
00135 
00137 // computeGramMatrix //
00139 void LLEKernel::computeGramMatrix(Mat K) const {
00140     reconstruct_ker->computeLLEMatrix(K);
00141     if (!fast_exact_is_equal(reconstruct_coeff, 0)) {
00142         for (int i = 0; i < n_examples; i++) {
00143             K(i, i) += fabs(reconstruct_coeff);
00144         }
00145     }
00146 }
00147 
00149 // evaluate //
00151 real LLEKernel::evaluate(const Vec& x1, const Vec& x2) const {
00152     static int j1, j2;
00153     if (isInData(x1, &j1)) {
00154         if (isInData(x2, &j2)) {
00155             // Both points are in the training set.
00156             return evaluate_i_j(j1, j2);
00157         } else {
00158             // Only x1 is in the training set.
00159             return evaluate_i_x(j1, x2);
00160         }
00161     } else {
00162         if (isInData(x2, &j2)) {
00163             // Only x2 is in the training set.
00164             return evaluate_i_x(j2, x1);
00165         } else {
00166             // Neither x1 nor x2 is in the training set.
00167             return 0;
00168         }
00169     }
00170 }
00171 
00173 // evaluate_i_j //
00175 real LLEKernel::evaluate_i_j(int i, int j) const {
00176     // When evaluated on training points, we must ignore the nearest neighbor
00177     // (because it is the point itself).
00178     real result;
00179     int tmp = reconstruct_ker->ignore_nearest;
00180     reconstruct_ker->ignore_nearest = 1;
00181     if (i == j) {
00182         result =
00183             fabs(reconstruct_coeff) +
00184             2 * reconstruct_ker->evaluate_i_j(i,i) -
00185             reconstruct_ker->evaluate_sum_k_i_k_j(i,i);
00186         reconstruct_ker->ignore_nearest = tmp;
00187         return result;
00188     } else {
00189         result =
00190             reconstruct_ker->evaluate_i_j(j,i) +
00191             reconstruct_ker->evaluate_i_j(i,j) -
00192             reconstruct_ker->evaluate_sum_k_i_k_j(i,j);
00193         reconstruct_ker->ignore_nearest = tmp;
00194         return result;
00195     }
00196 }
00197 
00199 // evaluate_i_x //
00201 real LLEKernel::evaluate_i_x(int i, const Vec& x, real squared_norm_of_x) const {
00202     return evaluate_i_x_again(i, x, squared_norm_of_x, true);
00203 }
00204 
00206 // evaluate_i_x_again //
00208 real LLEKernel::evaluate_i_x_again(int i, const Vec& x, real squared_norm_of_x, bool first_time) const {
00209     if (fast_exact_is_equal(reconstruct_coeff, 0)) {
00210         // This kernel should only be evaluated on training points.
00211         if (first_time) {
00212             x_is_training_point = isInData(x, &x_index);
00213         }
00214         if (!x_is_training_point)
00215             return 0;
00216         return evaluate_i_j(i, x_index);
00217     } else if (reconstruct_coeff > 0) {
00218         if (first_time) {
00219             x_is_training_point = isInData(x, &x_index);
00220         }
00221         if (x_is_training_point) {
00222             return evaluate_i_j(i, x_index);
00223         } else {
00224             return reconstruct_coeff * reconstruct_ker->evaluate_x_i_again(x, i, squared_norm_of_x, first_time);
00225         }
00226     } else {
00227         // reconstruct_coeff < 0: we assume x is not a training point.
00228         return fabs(reconstruct_coeff) * reconstruct_ker->evaluate_x_i_again(x, i, squared_norm_of_x, first_time);
00229     }
00230 }
00231 
00233 // makeDeepCopyFromShallowCopy //
00235 void LLEKernel::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00236 {
00237     inherited::makeDeepCopyFromShallowCopy(copies);
00238 
00239     // ### Call deepCopyField on all "pointer-like" fields 
00240     // ### that you wish to be deepCopied rather than 
00241     // ### shallow-copied.
00242     // ### ex:
00243     // deepCopyField(trainvec, copies);
00244 
00245     // ### Remove this line when you have fully implemented this method.
00246     PLERROR("LLEKernel::makeDeepCopyFromShallowCopy not fully (correctly) implemented yet!");
00247 }
00248 
00250 // setDataForKernelMatrix //
00252 void LLEKernel::setDataForKernelMatrix(VMat the_data) {
00253     if (build_in_progress)
00254         return;
00255     inherited::setDataForKernelMatrix(the_data);
00256     // We ignore the nearest neighbor when computing the reconstruction weights
00257     // on the training data.
00258     reconstruct_ker->ignore_nearest = 1;
00259     reconstruct_ker->setDataForKernelMatrix(the_data);
00260     // But we do not ignore it anymore when computing the reconstruction weights
00261     // on new samples.
00262     reconstruct_ker->ignore_nearest = 0;
00263 }
00264 
00265 } // end of namespace PLearn
00266 
00267 
00268 /*
00269   Local Variables:
00270   mode:c++
00271   c-basic-offset:4
00272   c-file-style:"stroustrup"
00273   c-file-offsets:((innamespace . 0)(inline-open . 0))
00274   indent-tabs-mode:nil
00275   fill-column:79
00276   End:
00277 */
00278 // 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