PLearn 0.1
|
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 :