PLearn 0.1
PruningLinearRegressor.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PruningLinearRegressor.cc
00004 //
00005 // Copyright (C) 2008 Rejean Ducharme
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 // Authors: Rejean Ducharme
00036 
00039 #include "PruningLinearRegressor.h"
00040 #include <plearn/math/plapack.h>
00041 
00042 namespace PLearn {
00043 using namespace std;
00044 
00045 PLEARN_IMPLEMENT_OBJECT(
00046     PruningLinearRegressor,
00047     "Same as LinearRegressor, but adding the pruning of the regression coefficients",
00048     "This class permits to reduce the degree of freedom of a LinearRegressor by\n"
00049     "pruning some regression coefficients.  Several pruning methods are supported:\n"
00050     "  - minimum t-ratio: keep only the coefficients for which the t-ratio exceeds a threshold\n"
00051     "  - absolute max: keep only a maximum number of coefficient (with best t-ratios)\n"
00052     "  - relative max: keep only a maximum fraction of coefficient (with best t-ratios)\n"
00053     );
00054 
00055 PruningLinearRegressor::PruningLinearRegressor()
00056     : pruning_method("max_number"),
00057       min_t_ratio(0.05),
00058       max_number(50),
00059       max_fraction(0.5)
00060 { }
00061 
00062 void PruningLinearRegressor::declareOptions(OptionList& ol)
00063 {
00064     //#####  Build Options  ####################################################
00065 
00066     declareOption(ol, "pruning_method", &PruningLinearRegressor::pruning_method,
00067                   OptionBase::buildoption,
00068                   "The pruning method:\n"
00069                   " - \"max_number\"    = keep only the weights with the k-best t-ratio\n"
00070                   " - \"max_fraction\"  = same as \"max_number\", but using a fraction rather than a hard threshold\n"
00071                   " - \"min_t_ratio\"   = keep only the weights with t-ratio > min_t_ratio");
00072 
00073     declareOption(ol, "min_t_ratio", &PruningLinearRegressor::min_t_ratio,
00074                   OptionBase::buildoption,
00075                   "Minimum t-ratio for not pruning a coefficient");
00076 
00077     declareOption(ol, "max_number", &PruningLinearRegressor::max_number,
00078                   OptionBase::buildoption,
00079                   "Maximum number of coefficients (the default)");
00080 
00081     declareOption(ol, "max_fraction", &PruningLinearRegressor::max_fraction,
00082                   OptionBase::buildoption,
00083                   "Maximum fraction (in [0,1]) of coefficients");
00084 
00085     //#####  Learnt Options  ###################################################
00086 
00087     declareOption(ol, "t_ratio", &PruningLinearRegressor::t_ratio,
00088                   OptionBase::learntoption,
00089                   "t-ratio statistics for the estimator b (regression coefficients)\n"
00090                   "Saved as a learned option to allow computing statistical significance\n"
00091                   "of the coefficients when the model is reloaded and used in test mode.");
00092 
00093     declareOption(ol, "input_indices", &PruningLinearRegressor::input_indices,
00094                   OptionBase::learntoption,
00095                   "Indices of inputs kept for regression");
00096 
00097     inherited::declareOptions(ol);
00098 }
00099 
00100 void PruningLinearRegressor::build_()
00101 {
00102     if (pruning_method == "max_number")
00103     {
00104         if (max_number < 1)
00105             PLERROR("\"max_number\" should be strictly positive");
00106     }
00107     else if (pruning_method == "max_fraction")
00108     {
00109         if (max_fraction <= 0.0  ||  max_fraction >= 1.0)
00110             PLERROR("\"max_fraction\" should be in range ]0,1[");
00111     }
00112     else if (pruning_method == "min_t_ratio")
00113     {
00114         if (min_t_ratio <= 0.0)
00115             PLERROR("\"min_t_ratio\" should be strictly positive");
00116     }
00117     else
00118         PLERROR("Pruning method \"%s\" not supported", pruning_method.c_str());
00119 }
00120 
00121 void PruningLinearRegressor::build()
00122 {
00123     inherited::build();
00124     build_();
00125 }
00126 
00127 void PruningLinearRegressor::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00128 {
00129     inherited::makeDeepCopyFromShallowCopy(copies);
00130     deepCopyField(t_ratio, copies);
00131     deepCopyField(input_indices, copies);
00132 }
00133 
00134 void PruningLinearRegressor::setTrainingSet(VMat training_set, bool call_forget)
00135 {
00136     inherited::setTrainingSet(training_set, call_forget);
00137     if (targetsize() > 1)
00138         PLERROR("PruningLinearRegressor works only with single target problems");
00139 }
00140 
00141 void PruningLinearRegressor::train()
00142 {
00143     // train with all coefficients
00144     inherited::train();
00145 
00146     // find the dataset indices corresponding to coefficients not pruned
00147     newDatasetIndices();
00148 
00149     // Add target and (possibly) weight indices
00150     TVec<int> all_indices = input_indices.copy();
00151     all_indices.append(inputsize());        // target index = inputsize
00152     if (weightsize())
00153         all_indices.append(inputsize()+1);  // weight index = target index + 1
00154 
00155     // Build new training set
00156     VMat new_trainset = train_set.columns(all_indices);
00157     int new_inputsize = input_indices.length();
00158     new_trainset->defineSizes(new_inputsize, 1, weightsize());
00159 
00160     // Train with this new training set
00161     setTrainingSet(new_trainset);
00162     inherited::train();
00163 }
00164 
00165 void PruningLinearRegressor::computeOutput(const Vec& input, Vec& output) const
00166 {
00167     Vec actual_input(input_indices.length());
00168     selectElements(input, input_indices, actual_input);
00169     inherited::computeOutput(actual_input, output);
00170 }
00171 
00172 void PruningLinearRegressor::computeTRatio()
00173 {
00174     // We wish to compute the t-ratio of the estimator coefficients.
00175     // For that purpose, we use the following formula:
00176     //
00177     //    t = |b| / sigma_b
00178     //
00179     // where b is the coefficients vector and sigma_b is the stderr matrix
00180     // of the estimator of b.  The latter is computed as:
00181     //
00182     //     sigma_b = s^2 * inverse(X'X)
00183     //
00184     // where s^2 is the residual variance (estimated using the
00185     // LinearRegressor::computeResidualsVariance method)
00186     // and X is the matrix of regressors..
00187 
00188     const int ninputs = weights.length();
00189     Mat sigma_b(ninputs, ninputs);
00190     t_ratio.resize(ninputs);
00191 
00192     // We compute the estimator
00193     PLASSERT(resid_variance.length() == 1);
00194     PLASSERT(weights.width() == 1);
00195     real residual_variance = resid_variance[0];
00196  
00197     Mat XtX_copy = XtX.copy();  // matInvert overwrite the input matrix
00198     Mat XtX_inverse(XtX.length(), XtX.width());
00199     matInvert(XtX_copy, XtX_inverse);
00200     for (int i=0; i<ninputs; i++)
00201     {
00202         real sigma_b = sqrt(residual_variance*XtX_inverse(i,i));
00203         t_ratio[i] = abs(weights(i,0)) / sigma_b;
00204     }
00205 }
00206 
00207 void PruningLinearRegressor::newDatasetIndices()
00208 {
00209     // Compute first the t-ratios
00210     computeTRatio();
00211 
00212     // Sort all t-ratios
00213     int nb_weights = weights.length();
00214     PLASSERT(nb_weights == t_ratio.length());
00215     Vec t_ratio_sort = t_ratio.copy();
00216     sortElements(t_ratio_sort, true);
00217 
00218     // Find the t-ratio threshold
00219     real t_ratio_threshold = 0.0;
00220     if (pruning_method == "max_number")
00221     {
00222         int keep_n_weights = min(max_number, nb_weights);
00223         // Add one coefficient if max is not yet reached
00224         if (include_bias  &&  keep_n_weights<nb_weights)
00225             ++keep_n_weights;
00226         t_ratio_threshold = t_ratio_sort[keep_n_weights-1];
00227     }
00228     else if (pruning_method == "max_fraction")
00229     {
00230         int keep_n_weights = max_fraction*nb_weights;
00231         t_ratio_threshold = t_ratio_sort[keep_n_weights-1];
00232     }
00233     else if (pruning_method == "min_t_ratio")
00234     {
00235         t_ratio_threshold = min_t_ratio;
00236     }
00237 
00238     // Find kept (not pruned) coefficient indices
00239     input_indices.resize(0);
00240     int offset = include_bias ? 1 : 0;
00241     for (int i=0; i<nb_weights; i++)
00242     {
00243         if (t_ratio[i] >= t_ratio_threshold)
00244         {
00245             int data_index = i - offset;
00246             if (data_index >= 0)  // = -1 for bias
00247                 input_indices.append(data_index);
00248         }
00249     }
00250 }
00251 
00252 
00253 } // end of namespace PLearn
00254 
00255 
00256 /*
00257   Local Variables:
00258   mode:c++
00259   c-basic-offset:4
00260   c-file-style:"stroustrup"
00261   c-file-offsets:((innamespace . 0)(inline-open . 0))
00262   indent-tabs-mode:nil
00263   fill-column:79
00264   End:
00265 */
00266 // 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