PLearn 0.1
LocalizedFeaturesLayerVariable.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PLearn (A C++ Machine Learning Library)
00004 // Copyright (C) 1998 Pascal Vincent
00005 // Copyright (C) 2005 Yoshua Bengio
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 /* *******************************************************      
00037  * $Id: LocalizedFeaturesLayerVariable.cc 6351 2006-10-25 19:05:45Z chapados $
00038  * This file is part of the PLearn library.
00039  ******************************************************* */
00040 
00041 #include "LocalizedFeaturesLayerVariable.h"
00042 #include <plearn/ker/GaussianKernel.h>
00043 #include <plearn/math/random.h>
00044 #include <plearn/math/BottomNI.h>
00045 #include <plearn/math/TMat_maths.h>
00046 #include <plearn/math/TMat_maths_specialisation.h>
00047 
00048 // #define UGLY_HACK
00049 
00050 #ifdef UGLY_HACK
00051 #define UGLY_DIV (16)
00052 #endif
00053 
00054 namespace PLearn {
00055 using namespace std;
00056 
00057 
00060 // Single layer of a neural network.
00061 
00062 PLEARN_IMPLEMENT_OBJECT(LocalizedFeaturesLayerVariable,
00063                         "Single layer of a neural network, with local connectivity on a set of localized features.\n",
00064                         "Each feature is associated with a location in some low-dimensional space\n"
00065                         "and each hidden unit takes input only from a subset of features that are\n"
00066                         "in some local region in that space.\n"
00067                         "The user can specify the feature subsets or specify the low-dimensional embedding\n"
00068                         "of the features. In the latter case the subsets are derived according to one of\n"
00069                         "several algorithms. The default one (knn_subsets) is simply that there is one\n"
00070                         "subset per feature, with n_neighbors_per_subset+1 features per subset, that include\n"
00071                         "the 'central' feature and its n_neighbors_per_subset embedding neighbors.\n"
00072                         "\n"
00073                         "TODO IN A FUTURE RELEASE(?):\n"
00074                         "The learning algorithm that estimates feature locations or directly the graph\n"
00075                         "that defines subsets of features could be embedded in this class.\n"
00076     );
00077 
00078 LocalizedFeaturesLayerVariable::LocalizedFeaturesLayerVariable()
00079     : n_features(-1),
00080       backprop_to_inputs(false),
00081       n_hidden_per_subset(1),
00082       knn_subsets(true),
00083       n_neighbors_per_subset(-1),
00084       gridding_subsets(false),
00085       center_on_feature_locations(true),
00086       seed(-1),
00087       shared_weights(false),
00088       n_box(-1),
00089       sigma(-1)
00090 {
00091 }
00092 
00093 void
00094 LocalizedFeaturesLayerVariable::build()
00095 {
00096     inherited::build();
00097     build_();
00098 }
00099 
00100 void
00101 LocalizedFeaturesLayerVariable::build_()
00102 {
00103     if (varray.length() == 0)
00104         // Cannot do anything yet.
00105         return;
00106     computeSubsets();
00107     if (   varray.size() != 3
00108            || n_weights != varray[1]->value.size()
00109            || n_hidden_per_subset * (shared_weights ? 1 : n_subsets) != varray[2]->value.size()  )
00110     {
00111         varray.resize(3);
00112         varray[1] = Var(n_weights);
00113         varray[2] = Var(n_hidden_per_subset * (shared_weights ? 1 : n_subsets));
00114         // varray[0] = input
00115         // varray[1] = connection weights
00116         // varray[2] = biases
00117     }
00118     if (varray[0]) {
00119         if (n_features != varray[0]->value.size())
00120             PLERROR("In LocalizedFeaturesLayerVariable: input var 0 (features) should have size = %d = n_features, but is %d\n",
00121                     n_features, varray[0]->value.size());
00122         // Initialize parameters.
00123         real n_inputs_per_neuron = 0;
00124         if (knn_subsets) {
00125             if (shared_weights && n_box >= 0)
00126                 n_inputs_per_neuron = ipow(n_box, feature_locations->width());
00127             else
00128                 n_inputs_per_neuron = 1 + n_neighbors_per_subset;
00129         }
00130         else
00131             PLERROR("In LocalizedFeaturesLayerVariable::build_ - Not supported");
00132         real delta = 1/n_inputs_per_neuron;
00133         if (seed >= 0)
00134             manual_seed(seed);
00135         fill_random_uniform(varray[1]->value, -delta, delta);
00136         varray[2]->value.clear();
00137     }
00138     resize(1, n_hidden_per_subset * n_subsets);
00139 }
00140 
00141 void LocalizedFeaturesLayerVariable::computeSubsets()
00142 {
00143     if (knn_subsets)
00144     {
00145         n_features = varray[0]->value.size();    // Get n_features from first var.
00146         n_subsets = n_features;
00147 #ifdef UGLY_HACK
00148         n_subsets = UGLY_DIV * UGLY_DIV;
00149 #endif
00150         n_weights = n_hidden_per_subset;
00151         int dim = feature_locations->width();
00152         if (!shared_weights)
00153             n_weights *= n_subsets * (1 + n_neighbors_per_subset);
00154         else {
00155             if (n_box == -1)
00156                 // No spatial sharing.
00157                 n_weights *= (1 + n_neighbors_per_subset);
00158             else
00159                 n_weights *= ipow(n_box, dim);
00160         }
00161         feature_subsets.resize(n_subsets);
00162         BottomNI<real> lowest_distances;
00163         Vec center(feature_locations->width());
00164         Vec feature(feature_locations->width());
00165         Mat mu_copy;
00166         real sig = sigma;
00167         if (shared_weights && n_box >= 0) {
00168             PLASSERT( n_box >= 2 );
00169             int count_max = ipow(n_box, dim);
00170             mu.resize(count_max, dim);
00171             mu_copy.resize(mu.length(), mu.width());
00172             // Find bounding box of the features.
00173             TVec< pair<real,real> > bbox = feature_locations->getBoundingBox();
00174             PLASSERT( bbox.length() == dim );
00175             // Heuristic for approximate volume of the neighbors.
00176             real total_volume = 1.0;
00177             for (int i = 0; i < dim; i++)
00178                 total_volume *= (bbox[i].second - bbox[i].first);
00179             real k_features_volume = total_volume / real(n_features)
00180                 * (n_neighbors_per_subset + 1);
00181             real step = pow(k_features_volume, 1.0 / dim) / n_box;
00182             // Precompute the offsets for the pre-defined centers.
00183             for (int count = 0; count < count_max; count++) {
00184                 int rest = count;
00185                 for (int i = 0; i < dim; i++) {
00186                     int coord_i = rest % n_box;
00187                     rest /= n_box;
00188                     mu(count, i) = (coord_i - n_box / 2) * step;
00189                 }
00190             }
00191             // Heuristic to compute sigma.
00192             if (sigma < 0) {
00193                 sig = step;
00194             }
00195         }
00196 
00197         GaussianKernel K(sig);
00198         local_weights.resize(n_features);
00199         for (int s=0; s<n_subsets; s++)
00200         {
00201             feature_subsets[s].resize(n_neighbors_per_subset + 1);
00202             // Find k-nearest neighbors of features according to feature_locations
00203             lowest_distances.init(n_neighbors_per_subset);
00204             feature_locations->getRow(s, center);
00205 #ifdef UGLY_HACK
00206             int w = int(sqrt(real(n_features)) + 1e-6);
00207             if (w % UGLY_DIV != 0)
00208                 PLERROR("Ouch");
00209             int w_s = UGLY_DIV;
00210             int w_zone = w / UGLY_DIV;
00211             int x_s = s % w_s;
00212             int y_s = s / w_s;
00213             int x_f = x_s * w_zone + w_zone / 2;
00214             int y_f = y_s * w_zone + w_zone / 2;
00215             int index_f = y_f * w + x_f;
00216             feature_locations->getRow(index_f, center);
00217 #endif
00218             for (int f=0;f<n_features;f++)
00219                 if (f!=s)
00220                 {
00221                     feature_locations->getRow(f, feature);
00222                     real dist = powdistance(center, feature);
00223                     lowest_distances.update(dist,f);
00224                 }
00225             TVec< pair<real,int> > neighbors = lowest_distances.getBottomN();
00226             feature_subsets[s][0] = s;
00227             for (int k=0;k<n_neighbors_per_subset;k++)
00228                 feature_subsets[s][k+1] = neighbors[k].second;
00229             if (shared_weights && n_box >= 0) {
00230                 mu_copy << mu;
00231                 mu_copy += center;
00232                 int n_neighb = feature_subsets[s].length();
00233                 local_weights[s].resize(mu.length(), n_neighb);
00234                 for (int j = 0; j < feature_subsets[s].length(); j++) {
00235                     for (int i = 0; i < mu.length(); i++) {
00236                         feature_locations->getRow(feature_subsets[s][j], feature);
00237                         real k = K.evaluate(mu_copy(i), feature);
00238                         local_weights[s](i,j) = k;
00239                     }
00240                 }
00241                 normalizeColumns(local_weights[s]);
00242             }
00243 #ifdef UGLY_HACK
00244             int a = int(sqrt(real(n_neighbors_per_subset + 1)) + 1e-6);
00245             if (fabs(a - sqrt(real(n_neighbors_per_subset + 1))) > 1e-8 || a % 2 != 1)
00246                 PLERROR("Arg");
00247             w = int(sqrt(real(n_features)) + 1e-6);
00248             int b = (a - 1) / 2;
00249             int n_start = index_f - b - b * w;
00250             int count = 0;
00251             for (int row = 0; row < a; row++) {
00252                 for (int col = 0; col < a; col++) {
00253                     int n = n_start + row * w + col;
00254                     if (n < 0)
00255                         n += n_features;
00256                     if (n >= n_features)
00257                         n -= n_features;
00258                     feature_subsets[s][count++] = n;
00259                 }
00260             }
00261 #endif
00262         }
00263     }
00264     else
00265         PLERROR("In LocalizedFeaturesLayerVariable: currently the only method for computing subsets is 'knn_subsets'.\n");
00266 }
00267 
00269 // declareOptions //
00271 void LocalizedFeaturesLayerVariable::declareOptions(OptionList& ol)
00272 {
00273     declareOption(ol, "backprop_to_inputs", &LocalizedFeaturesLayerVariable::backprop_to_inputs, OptionBase::buildoption, 
00274                   "    If true then gradient is propagated to the inputs. When this object is the first layer\n"
00275                   "    of a neural network, it is more efficient to set this option to false (which is its default).\n");
00276 
00277     declareOption(ol, "feature_locations", &LocalizedFeaturesLayerVariable::feature_locations, 
00278                   OptionBase::buildoption, 
00279                   "    (n_features x n_dim) matrix assigning each feature to a location in n_dimensional space.\n"
00280                   "    If feature_subsets is directly provided, it is not necessary to provide this option, as\n"
00281                   "    the feature locations are only used to infer the feature_subsets.\n");
00282 
00283     declareOption(ol, "feature_subsets", &LocalizedFeaturesLayerVariable::feature_subsets, 
00284                   OptionBase::buildoption, 
00285                   "    Sequence of vector indices, one sequence per subset, containing indices of features\n"
00286                   "    associated with each subset. If not specified (empty sequence) it will be inferred\n"
00287                   "    using the feature_locations (which MUST be specified, in that case).\n");
00288 
00289     declareOption(ol, "n_hidden_per_subset", &LocalizedFeaturesLayerVariable::n_hidden_per_subset, 
00290                   OptionBase::buildoption, 
00291                   "    Number of hidden units per unique feature subset.\n");
00292 
00293     declareOption(ol, "shared_weights", &LocalizedFeaturesLayerVariable::shared_weights, OptionBase::buildoption, 
00294                   "If true, similar hidden neurons in different subsets will share the same weights.");
00295 
00296     declareOption(ol, "n_box", &LocalizedFeaturesLayerVariable::n_box, OptionBase::buildoption, 
00297                   "Only used when 'shared_weights' is true: the gridding factor of the box around each feature\n"
00298                   "where we put the reference centers. The number of centers will thus be n_box^d.\n"
00299                   "If set to -1, a more basic weights sharing method is used, with no spatial consistency.");
00300 
00301     declareOption(ol, "sigma", &LocalizedFeaturesLayerVariable::sigma, OptionBase::buildoption, 
00302                   "Width of the Gaussian kernel for the local interpolation when sharing weights.\n"
00303                   "If set to -1, will be heuristically selected.");
00304 
00305     declareOption(ol, "knn_subsets", &LocalizedFeaturesLayerVariable::knn_subsets, 
00306                   OptionBase::buildoption, 
00307                   "    Whether to infer feature_subsets using the k-nearest-neighbor algorithm or not.\n"
00308                   "    This option is only used when feature_subsets is not directly provided by the user.\n"
00309                   "    Each subset will have size 'n_neighbors_per_subset' and there will be one subset\n"
00310                   "    per feature, comprising that feature and its 'n_neighbors_per_subset' neighbors\n"
00311                   "    in terms of Euclidean distance in feature locations.\n");
00312 
00313     declareOption(ol, "n_neighbors_per_subset", &LocalizedFeaturesLayerVariable::n_neighbors_per_subset, 
00314                   OptionBase::buildoption, 
00315                   "   Number of feature neighbors to consider in each subset, if knn_subsets == true and\n"
00316                   "   feature_subsets is not specified directly by the user.\n");
00317 
00318     declareOption(ol, "gridding_subsets", &LocalizedFeaturesLayerVariable::gridding_subsets, 
00319                   OptionBase::buildoption, 
00320                   "    Whether to infer feature_subsets using a gridding algorithm.\n"
00321                   "    NOT IMPLEMENTED YET.\n");
00322 
00323     declareOption(ol, "center_on_feature_locations", &LocalizedFeaturesLayerVariable::center_on_feature_locations,
00324                   OptionBase::buildoption, 
00325                   "    If gridding_subsets == true, whether to center each subset window on feature locations\n"
00326                   "    or on regularly spaced centers in a volume.\n"
00327                   "    NOT IMPLEMENTED YET.\n");
00328 
00329     declareOption(ol, "seed", &LocalizedFeaturesLayerVariable::seed, OptionBase::buildoption,
00330                   "Positive seed to initialize the weights (will be ignored if set to -1).");
00331 
00332     inherited::declareOptions(ol);
00333 }
00334 
00335 
00336 void LocalizedFeaturesLayerVariable::recomputeSize(int& l, int& w) const
00337 {
00338     if (varray.length() >= 2 && varray[0] && varray[1]) {
00339         l = 1;
00340         w = n_hidden_per_subset * n_subsets;
00341     } else
00342         l = w = 0;
00343 }
00344 
00345 void LocalizedFeaturesLayerVariable::fprop()
00346 {
00347     real* x = varray[0]->valuedata;
00348     real* y = valuedata;
00349     real* w = varray[1]->valuedata;
00350     real* b = varray[2]->valuedata;
00351     for (int s=0;s<n_subsets;s++)
00352     {
00353         TVec<int> subset = feature_subsets[s];
00354         int subset_size = subset.length();
00355         Mat& local_weights_s = local_weights[s];
00356         for (int k=0;k<n_hidden_per_subset;k++,b++,y++)
00357         {
00358             real act = *b;
00359             if (shared_weights && n_box >= 0) {
00360                 real* w_ = w;
00361                 for (int j=0;j<subset_size;j++) {
00362                     w_ = w;
00363                     real x_val = x[subset[j]];
00364                     for (int i = 0; i < mu.length(); i++, w_++) {
00365                         act += *w_ * x_val * local_weights_s(i, j);
00366                     }
00367                 }
00368                 w = w_;
00369             } else
00370                 for (int j=0;j<subset_size;j++,w++)
00371                     act += *w * x[subset[j]];
00372             *y = tanh(act);
00373         }
00374         if (shared_weights) {
00375             b = varray[2]->valuedata;
00376             w = varray[1]->valuedata;
00377         }
00378     }
00379 }
00380 
00381 
00382 void LocalizedFeaturesLayerVariable::bprop()
00383 {
00384     real* x = varray[0]->valuedata;
00385     real* dx = varray[0]->gradientdata;
00386     real* y = valuedata;
00387     real* dy = gradientdata;
00388     real* w = varray[1]->valuedata;
00389     real* dw = varray[1]->gradientdata;
00390     real* db = varray[2]->gradientdata;
00391     for (int s=0;s<n_subsets;s++)
00392     {
00393         TVec<int> subset = feature_subsets[s];
00394         int subset_size = subset.length();
00395         Mat& local_weights_s = local_weights[s];
00396         for (int k=0;k<n_hidden_per_subset;k++,db++,y++,dy++)
00397         {
00398             real dact = *dy * (1 - *y * *y);
00399             *db += dact;
00400             if (shared_weights && n_box >= 0) {
00401                 real* dw_ = dw;
00402                 for (int j=0;j<subset_size;j++) {
00403                     dw_ = dw;
00404                     real x_val = x[subset[j]];
00405                     for (int i = 0; i < mu.length(); i++, dw_++) {
00406                         *dw_ += dact * x_val * local_weights_s(i, j);
00407                     }
00408                 }
00409                 dw = dw_;
00410             } else
00411                 for (int j=0;j<subset_size;j++,dw++)
00412                     *dw += dact * x[subset[j]];
00413             if (backprop_to_inputs) {
00414                 PLASSERT( !shared_weights || n_box < 0 ); // Case not handled.
00415                 for (int j=0;j<subset_size;j++,w++)
00416                     dx[subset[j]] += dact * *w;
00417             }
00418         }
00419         if (shared_weights) {
00420             w  = varray[1]->valuedata;
00421             dw = varray[1]->gradientdata;
00422             db = varray[2]->gradientdata;
00423         }
00424     }
00425 }
00426 
00428 // makeDeepCopyFromShallowCopy //
00430 void LocalizedFeaturesLayerVariable::makeDeepCopyFromShallowCopy(CopiesMap& copies) {
00431     inherited::makeDeepCopyFromShallowCopy(copies);
00432     deepCopyField(feature_locations, copies);
00433     deepCopyField(feature_subsets, copies);
00434 }
00435 
00436 } // end of namespace PLearn
00437 
00438 
00439 /*
00440   Local Variables:
00441   mode:c++
00442   c-basic-offset:4
00443   c-file-style:"stroustrup"
00444   c-file-offsets:((innamespace . 0)(inline-open . 0))
00445   indent-tabs-mode:nil
00446   fill-column:79
00447   End:
00448 */
00449 // 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