SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
OnlineLibLinear.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2007-2010 Soeren Sonnenburg
8  * Written (W) 2011 Shashwat Lal Das
9  * Copyright (c) 2007-2009 The LIBLINEAR Project.
10  * Copyright (C) 2007-2010 Fraunhofer Institute FIRST and Max-Planck-Society
11  */
12 
14 #include <shogun/lib/Time.h>
15 
16 using namespace shogun;
17 
20 {
21  init();
22 }
23 
25 {
26  init();
27  C1=C;
28  C2=C;
29  use_bias=true;
30 }
31 
33  float64_t C, CStreamingDotFeatures* traindat)
34 {
35  init();
36  C1=C;
37  C2=C;
38  use_bias=true;
39 
40  set_features(traindat);
41 }
42 
43 
44 void COnlineLibLinear::init()
45 {
46  C1=1;
47  C2=1;
48  use_bias=false;
49 
50  m_parameters->add(&C1, "C1", "C Cost constant 1.");
51  m_parameters->add(&C2, "C2", "C Cost constant 2.");
52  m_parameters->add(&use_bias, "use_bias", "Indicates if bias is used.");
53 }
54 
56 {
57 }
58 
60 {
61  if (data)
62  {
63  if (!data->has_property(FP_STREAMING_DOT))
64  SG_ERROR("Specified features are not of type CStreamingDotFeatures\n");
66  }
67 
68  float64_t C, d, G;
69  float64_t QD;
70 
71  // y and alpha for example being processed
72  int32_t y_current;
73  float64_t alpha_current;
74 
75  // Cost constants
76  float64_t Cp=C1;
77  float64_t Cn=C2;
78 
79  // PG: projected gradient, for shrinking and stopping
80  float64_t PG;
81  float64_t PGmax_old = CMath::INFTY;
82  float64_t PGmin_old = -CMath::INFTY;
83  float64_t PGmax_new = -CMath::INFTY;
84  float64_t PGmin_new = CMath::INFTY;
85 
86  // Diag is probably unnecessary
87  float64_t diag[3] = {0, 0, 0};
88  float64_t upper_bound[3] = {Cn, 0, Cp};
89 
90  // Bias
91  bias = 0;
92 
93  PGmax_new = -CMath::INFTY;
94  PGmin_new = CMath::INFTY;
95 
96  // Objective value = v/2
97  float64_t v = 0;
98  // Number of support vectors
99  int32_t nSV = 0;
100 
101  // Start reading the examples
103 
104  CTime start_time;
105  while (features->get_next_example())
106  {
107  alpha_current = 0;
108  if (features->get_label() > 0)
109  y_current = +1;
110  else
111  y_current = -1;
112 
113  QD = diag[y_current + 1];
114  // Dot product of vector with itself
115  QD += features->dot(features);
116 
118 
119  G = features->dense_dot(w, w_dim);
120  if (use_bias)
121  G += bias;
122  G = G*y_current - 1;
123  // LINEAR TERM PART?
124 
125  C = upper_bound[y_current + 1];
126  G += alpha_current*diag[y_current + 1]; // Can be eliminated, since diag = 0 vector
127 
128  PG = 0;
129  if (alpha_current == 0) // This condition will always be true in the online version
130  {
131  if (G > PGmax_old)
132  {
134  continue;
135  }
136  else if (G < 0)
137  PG = G;
138  }
139  else if (alpha_current == C)
140  {
141  if (G < PGmin_old)
142  {
144  continue;
145  }
146  else if (G > 0)
147  PG = G;
148  }
149  else
150  PG = G;
151 
152  PGmax_new = CMath::max(PGmax_new, PG);
153  PGmin_new = CMath::min(PGmin_new, PG);
154 
155  if (fabs(PG) > 1.0e-12)
156  {
157  float64_t alpha_old = alpha_current;
158  alpha_current = CMath::min(CMath::max(alpha_current - G/QD, 0.0), C);
159  d = (alpha_current - alpha_old) * y_current;
160 
162 
163  if (use_bias)
164  bias += d;
165  }
166 
167  v += alpha_current*(alpha_current*diag[y_current + 1] - 2);
168  if (alpha_current > 0)
169  nSV++;
170 
172  }
173 
174  features->end_parser();
175 
176  float64_t gap = PGmax_new - PGmin_new;
177 
178  SG_DONE();
179  SG_INFO("Optimization finished.\n");
180 
181  // calculate objective value
182  for (int32_t i=0; i<w_dim; i++)
183  v += w[i]*w[i];
184  v += bias*bias;
185 
186  SG_INFO("Objective value = %lf\n", v/2);
187  SG_INFO("nSV = %d\n", nSV);
188  SG_INFO("gap = %g\n", gap);
189 
190  return true;
191 }

SHOGUN Machine Learning Toolbox - Documentation