SHOGUN  4.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
OnlineSVMSGD.cpp
Go to the documentation of this file.
1 /*
2  SVM with stochastic gradient
3  Copyright (C) 2007- Leon Bottou
4 
5  This program is free software; you can redistribute it and/or
6  modify it under the terms of the GNU Lesser General Public
7  License as published by the Free Software Foundation; either
8  version 2.1 of the License, or (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU Lesser General Public
16  License along with this library; if not, write to the Free Software
17  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18  $Id: svmsgd.cpp,v 1.13 2007/10/02 20:40:06 cvs Exp $
19 
20  Shogun adjustments (w) 2008-2009 Soeren Sonnenburg
21 */
22 
25 #include <shogun/base/Parameter.h>
26 #include <shogun/lib/Signal.h>
27 #include <shogun/loss/HingeLoss.h>
28 
29 using namespace shogun;
30 
33 {
34  init();
35 }
36 
39 {
40  init();
41 
42  C1=C;
43  C2=C;
44 }
45 
48 {
49  init();
50  C1=C;
51  C2=C;
52 
53  set_features(traindat);
54 }
55 
57 {
58  SG_UNREF(loss);
59 }
60 
62 {
63  SG_REF(loss_func);
64  SG_UNREF(loss);
65  loss=loss_func;
66 }
67 
69 {
70  if (data)
71  {
72  if (!data->has_property(FP_STREAMING_DOT))
73  SG_ERROR("Specified features are not of type CStreamingDotFeatures\n")
75  }
76 
78 
79  // allocate memory for w and initialize everyting w and bias with 0
82  if (w)
83  SG_FREE(w);
84  w_dim=1;
85  w=new float32_t;
86  bias=0;
87 
88  // Shift t in order to have a
89  // reasonable initial learning rate.
90  // This assumes |x| \approx 1.
91  float64_t maxw = 1.0 / sqrt(lambda);
92  float64_t typw = sqrt(maxw);
93  float64_t eta0 = typw / CMath::max(1.0,-loss->first_derivative(-typw,1));
94  t = 1 / (eta0 * lambda);
95 
96  SG_INFO("lambda=%f, epochs=%d, eta0=%f\n", lambda, epochs, eta0)
97 
98  //do the sgd
99  calibrate();
100  if (features->is_seekable())
102 
104 
105  ELossType loss_type = loss->get_loss_type();
106  bool is_log_loss = false;
107  if ((loss_type == L_LOGLOSS) || (loss_type == L_LOGLOSSMARGIN))
108  is_log_loss = true;
109 
110  int32_t vec_count;
111  for(int32_t e=0; e<epochs && (!CSignal::cancel_computations()); e++)
112  {
113  vec_count=0;
114  count = skip;
115  while (features->get_next_example())
116  {
117  vec_count++;
118  // Expand w vector if more features are seen in this example
120 
121  float64_t eta = 1.0 / (lambda * t);
123  float64_t z = y * (features->dense_dot(w, w_dim) + bias);
124 
125  if (z < 1 || is_log_loss)
126  {
127  float64_t etd = -eta * loss->first_derivative(z,1);
128  features->add_to_dense_vec(etd * y / wscale, w, w_dim);
129 
130  if (use_bias)
131  {
132  if (use_regularized_bias)
133  bias *= 1 - eta * lambda * bscale;
134  bias += etd * y * bscale;
135  }
136  }
137 
138  if (--count <= 0)
139  {
140  float32_t r = 1 - eta * lambda * skip;
141  if (r < 0.8)
142  r = pow(1 - eta * lambda, skip);
144  count = skip;
145  }
146  t++;
147 
149  }
150 
151  // If the stream is seekable, reset the stream to the first
152  // example (for epochs > 1)
153  if (features->is_seekable() && e < epochs-1)
155  else
156  break;
157 
158  }
159 
160  features->end_parser();
161  float64_t wnorm = CMath::dot(w,w, w_dim);
162  SG_INFO("Norm: %.6f, Bias: %.6f\n", wnorm, bias)
163 
164  return true;
165 }
166 
167 void COnlineSVMSGD::calibrate(int32_t max_vec_num)
168 {
169  int32_t c_dim=1;
170  float32_t* c=SG_CALLOC(float32_t, c_dim);
171 
172  // compute average gradient size
173  int32_t n = 0;
174  float64_t m = 0;
175  float64_t r = 0;
176 
177  while (features->get_next_example())
178  {
179  //Expand c if more features are seen in this example
180  features->expand_if_required(c, c_dim);
181 
183  features->add_to_dense_vec(1, c, c_dim, true);
184 
185  //waste cpu cycles for readability
186  //(only changed dims need checking)
187  m=CMath::max(c, c_dim);
188  n++;
189 
191  if (n>=max_vec_num || m > 1000)
192  break;
193  }
194 
195  SG_PRINT("Online SGD calibrated using %d vectors.\n", n)
196 
197  // bias update scaling
198  bscale = 0.5*m/n;
199 
200  // compute weight decay skip
201  skip = (int32_t) ((16 * n * c_dim) / r);
202 
203  SG_INFO("using %d examples. skip=%d bscale=%.6f\n", n, skip, bscale)
204 
205  SG_FREE(c);
206 }
207 
208 void COnlineSVMSGD::init()
209 {
210  t=1;
211  C1=1;
212  C2=1;
213  lambda=1e-4;
214  wscale=1;
215  bscale=1;
216  epochs=1;
217  skip=1000;
218  count=1000;
219  use_bias=true;
220 
221  use_regularized_bias=false;
222 
223  loss=new CHingeLoss();
224  SG_REF(loss);
225 
226  m_parameters->add(&C1, "C1", "Cost constant 1.");
227  m_parameters->add(&C2, "C2", "Cost constant 2.");
228  m_parameters->add(&lambda, "lambda", "Regularization parameter.");
229  m_parameters->add(&wscale, "wscale", "W scale");
230  m_parameters->add(&bscale, "bscale", "b scale");
231  m_parameters->add(&epochs, "epochs", "epochs");
232  m_parameters->add(&skip, "skip", "skip");
233  m_parameters->add(&count, "count", "count");
234  m_parameters->add(&use_bias, "use_bias", "Indicates if bias is used.");
235  m_parameters->add(&use_regularized_bias, "use_regularized_bias", "Indicates if bias is regularized.");
236 }
#define SG_INFO(...)
Definition: SGIO.h:118
Class OnlineLinearMachine is a generic interface for linear machines like classifiers which work thro...
Class CLossFunction is the base class of all loss functions.
Definition: LossFunction.h:57
virtual void start_parser()=0
virtual float32_t dense_dot(const float32_t *vec2, int32_t vec2_len)=0
#define SG_ERROR(...)
Definition: SGIO.h:129
void calibrate(int32_t max_vec_num=1000)
Parameter * m_parameters
Definition: SGObject.h:378
#define SG_REF(x)
Definition: SGObject.h:51
static void scale_vector(T alpha, T *vec, int32_t len)
Scale vector inplace.
Definition: SGVector.cpp:822
virtual void set_features(CStreamingDotFeatures *feat)
void add(bool *param, const char *name, const char *description="")
Definition: Parameter.cpp:37
#define SG_PRINT(...)
Definition: SGIO.h:137
virtual bool get_next_example()=0
virtual ELossType get_loss_type()=0
#define ASSERT(x)
Definition: SGIO.h:201
static void clear_cancel()
Definition: Signal.cpp:129
void set_loss_function(CLossFunction *loss_func)
virtual bool train(CFeatures *data=NULL)
double float64_t
Definition: common.h:50
virtual void expand_if_required(float32_t *&vec, int32_t &len)
static T max(T a, T b)
Definition: Math.h:168
static float64_t dot(const bool *v1, const bool *v2, int32_t n)
Compute dot product between v1 and v2 (blas optimized)
Definition: Math.h:627
Streaming features that support dot products among other operations.
static bool cancel_computations()
Definition: Signal.h:86
float float32_t
Definition: common.h:49
virtual void add_to_dense_vec(float32_t alpha, float32_t *vec2, int32_t vec2_len, bool abs_val=false)=0
#define SG_UNREF(x)
Definition: SGObject.h:52
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
virtual void end_parser()=0
CStreamingDotFeatures * features
The class Features is the base class of all feature objects.
Definition: Features.h:68
virtual void release_example()=0
virtual float64_t get_label()=0
CHingeLoss implements the hinge loss function.
Definition: HingeLoss.h:29
virtual int32_t get_nnz_features_for_vector()
virtual float64_t first_derivative(float64_t prediction, float64_t label)
Definition: LossFunction.h:101
bool has_property(EFeatureProperty p) const
Definition: Features.cpp:295
ELossType
shogun loss type
Definition: LossFunction.h:28

SHOGUN Machine Learning Toolbox - Documentation