loss_machine.cc

   1 /*
   2  *  folded-ctf is an implementation of the folded hierarchy of
   3  *  classifiers for object detection, developed by Francois Fleuret
   4  *  and Donald Geman.
   5  *
   6  *  Copyright (c) 2008 Idiap Research Institute, http://www.idiap.ch/
   7  *  Written by Francois Fleuret <francois.fleuret@idiap.ch>
   8  *
   9  *  This file is part of folded-ctf.
  10  *
  11  *  folded-ctf is free software: you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License version 3 as
  13  *  published by the Free Software Foundation.
  14  *
  15  *  folded-ctf is distributed in the hope that it will be useful, but
  16  *  WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  *  General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with folded-ctf.  If not, see <http://www.gnu.org/licenses/>.
  22  *
  23  */
  24
  25 #include "tools.h"
  26 #include "loss_machine.h"
  27
  28 LossMachine::LossMachine(int loss_type) {
  29   _loss_type = loss_type;
  30 }
  31
  32 void LossMachine::get_loss_derivatives(SampleSet *samples,
  33                                        scalar_t *responses,
  34                                        scalar_t *derivatives) {
  35
  36   switch(_loss_type) {
  37
  38   case LOSS_EXPONENTIAL:
  39     {
  40       for(int n = 0; n < samples->nb_samples(); n++) {
  41         derivatives[n] =
  42           - samples->label(n) * exp( - samples->label(n) * responses[n]);
  43       }
  44     }
  45     break;
  46
  47   case LOSS_HINGE:
  48     {
  49       for(int n = 0; n < samples->nb_samples(); n++) {
  50         if(samples->label(n) != 0 && samples->label(n) * responses[n] < 1)
  51           derivatives[n] = 1;
  52         else
  53           derivatives[n] = 0;
  54       }
  55     }
  56     break;
  57
  58   case LOSS_LOGISTIC:
  59     {
  60       for(int n = 0; n < samples->nb_samples(); n++) {
  61         if(samples->label(n) == 0)
  62           derivatives[n] = 0.0;
  63         else
  64           derivatives[n] = samples->label(n) * 1/(1 + exp(samples->label(n) * responses[n]));
  65       }
  66     }
  67     break;
  68
  69   default:
  70     cerr << "Unknown loss type in BoostedClassifier::get_loss_derivatives."
  71          << endl;
  72     exit(1);
  73   }
  74
  75 }
  76
  77 scalar_t LossMachine::loss(SampleSet *samples, scalar_t *responses) {
  78   scalar_t l = 0;
  79
  80   switch(_loss_type) {
  81
  82   case LOSS_EXPONENTIAL:
  83     {
  84       for(int n = 0; n < samples->nb_samples(); n++) {
  85         l += exp( - samples->label(n) * responses[n]);
  86         ASSERT(!isinf(l));
  87       }
  88     }
  89     break;
  90
  91   case LOSS_HINGE:
  92     {
  93       for(int n = 0; n < samples->nb_samples(); n++) {
  94         if(samples->label(n) != 0) {
  95           if(samples->label(n) * responses[n] < 1)
  96             l += (1 - samples->label(n) * responses[n]);
  97         }
  98       }
  99     }
 100     break;
 101
 102   case LOSS_LOGISTIC:
 103     {
 104       for(int n = 0; n < samples->nb_samples(); n++) {
 105         if(samples->label(n) != 0) {
 106           scalar_t u = - samples->label(n) * responses[n];
 107           if(u > 20) {
 108             l += u;
 109           } if(u > -20) {
 110             l += log(1 + exp(u));
 111           }
 112         }
 113       }
 114     }
 115     break;
 116
 117   default:
 118     cerr << "Unknown loss type in LossMachine::loss." << endl;
 119     exit(1);
 120   }
 121
 122   return l;
 123 }
 124
 125 scalar_t LossMachine::optimal_weight(SampleSet *sample_set,
 126                                      scalar_t *weak_learner_responses,
 127                                      scalar_t *current_responses) {
 128
 129   switch(_loss_type) {
 130
 131   case LOSS_EXPONENTIAL:
 132     {
 133       scalar_t num = 0, den = 0, z;
 134
 135       for(int n = 0; n < sample_set->nb_samples(); n++) {
 136         z = sample_set->label(n) * weak_learner_responses[n];
 137         if(z > 0) {
 138           num += exp( - sample_set->label(n) * current_responses[n]);
 139         } else if(z < 0) {
 140           den += exp( - sample_set->label(n) * current_responses[n]);
 141         }
 142       }
 143
 144       return 0.5 * log(num / den);
 145     }
 146     break;
 147
 148   case LOSS_HINGE:
 149   case LOSS_LOGISTIC:
 150     {
 151
 152       scalar_t u = 0, du = -0.1;
 153       scalar_t *responses = new scalar_t[sample_set->nb_samples()];
 154
 155       scalar_t l, prev_l = -1;
 156
 157       const scalar_t minimum_delta_for_optimization = 1e-5;
 158
 159       int n = 0;
 160       while(n < 100 && abs(du) > minimum_delta_for_optimization) {
 161         n++;
 162         u += du;
 163         for(int s = 0; s < sample_set->nb_samples(); s++) {
 164           responses[s] = current_responses[s] + u * weak_learner_responses[s] ;
 165         }
 166         l = loss(sample_set, responses);
 167         if(l > prev_l) du = du * -0.25;
 168         prev_l = l;
 169       }
 170
 171       (*global.log_stream) << "END l = " << l << " du = " << du << endl;
 172
 173       delete[] responses;
 174
 175       return u;
 176     }
 177
 178   default:
 179     cerr << "Unknown loss type in LossMachine::optimal_weight." << endl;
 180     exit(1);
 181   }
 182
 183 }
 184
 185 void LossMachine::subsample(int nb, scalar_t *labels, scalar_t *responses,
 186                             int nb_to_sample, int *sample_nb_occurences, scalar_t *sample_responses,
 187                             int allow_duplicates) {
 188
 189   switch(_loss_type) {
 190
 191   case LOSS_EXPONENTIAL:
 192     {
 193       scalar_t *weights = new scalar_t[nb];
 194
 195       for(int n = 0; n < nb; n++) {
 196         if(labels[n] == 0) {
 197           weights[n] = 0;
 198         } else {
 199           weights[n] = exp( - labels[n] * responses[n]);
 200         }
 201         sample_nb_occurences[n] = 0;
 202         sample_responses[n] = 0.0;
 203       }
 204
 205       scalar_t total_weight;
 206       int nb_sampled = 0, sum_sample_nb_occurences = 0;
 207
 208       int *sampled_indexes = new int[nb_to_sample];
 209
 210       (*global.log_stream) << "Sampling " << nb_to_sample << " samples." << endl;
 211
 212       do {
 213         total_weight = robust_sampling(nb,
 214                                        weights,
 215                                        nb_to_sample,
 216                                        sampled_indexes);
 217
 218         for(int k = 0; nb_sampled < nb_to_sample && k < nb_to_sample; k++) {
 219           int i = sampled_indexes[k];
 220           if(allow_duplicates || sample_nb_occurences[i] == 0) nb_sampled++;
 221           sample_nb_occurences[i]++;
 222           sum_sample_nb_occurences++;
 223         }
 224       } while(nb_sampled < nb_to_sample);
 225
 226       (*global.log_stream) << "Done." << endl;
 227
 228       delete[] sampled_indexes;
 229
 230       scalar_t unit_weight = log(total_weight / scalar_t(sum_sample_nb_occurences));
 231
 232       for(int n = 0; n < nb; n++) {
 233         if(sample_nb_occurences[n] > 0) {
 234           if(allow_duplicates) {
 235             sample_responses[n] = - labels[n] * unit_weight;
 236           } else {
 237             sample_responses[n] = - labels[n] * (unit_weight + log(scalar_t(sample_nb_occurences[n])));
 238             sample_nb_occurences[n] = 1;
 239           }
 240         }
 241       }
 242
 243       delete[] weights;
 244
 245     }
 246     break;
 247
 248   default:
 249     cerr << "Unknown loss type in LossMachine::resample." << endl;
 250     exit(1);
 251   }
 252
 253
 254 }