SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LPBoost.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-2009 Soeren Sonnenburg
8  * Copyright (C) 2007-2009 Fraunhofer Institute FIRST and Max-Planck-Society
9  */
10 
11 #include <shogun/lib/config.h>
12 
13 #ifdef USE_CPLEX
14 
16 #include <shogun/features/Labels.h>
20 #include <shogun/lib/Signal.h>
21 #include <shogun/lib/Time.h>
22 
23 using namespace shogun;
24 
26 : CLinearClassifier(), C1(1), C2(1), use_bias(true), epsilon(1e-3)
27 {
28  u=NULL;
29  dim=NULL;
30  num_sfeat=0;
31  num_svec=0;
32  sfeat=NULL;
33 }
34 
35 
37 {
38  cleanup();
39 }
40 
41 bool CLPBoost::init(int32_t num_vec)
42 {
43  u=SG_MALLOC(float64_t, num_vec);
44  for (int32_t i=0; i<num_vec; i++)
45  u[i]=1.0/num_vec;
46 
47  dim=new CDynamicArray<int32_t>(100000);
48 
49  sfeat= ((CSparseFeatures<float64_t>*) features)->get_transposed(num_sfeat, num_svec);
50 
51  if (sfeat)
52  return true;
53  else
54  return false;
55 }
56 
58 {
59  SG_FREE(u);
60  u=NULL;
61 
62  ((CSparseFeatures<float64_t>*) features)->clean_tsparse(sfeat, num_svec);
63  sfeat=NULL;
64 
65  delete dim;
66  dim=NULL;
67 }
68 
70 {
71  float64_t max_val=0;
72  max_dim=-1;
73 
74  for (int32_t i=0; i<num_svec; i++)
75  {
76  float64_t valplus=0;
77  float64_t valminus=0;
78 
79  for (int32_t j=0; j<sfeat[i].num_feat_entries; j++)
80  {
81  int32_t idx=sfeat[i].features[j].feat_index;
82  float64_t v=u[idx]*labels->get_label(idx)*sfeat[i].features[j].entry;
83  valplus+=v;
84  valminus-=v;
85  }
86 
87  if (valplus>max_val || max_dim==-1)
88  {
89  max_dim=i;
90  max_val=valplus;
91  }
92 
93  if (valminus>max_val)
94  {
95  max_dim=num_svec+i;
96  max_val=valminus;
97  }
98  }
99 
100  dim->append_element(max_dim);
101  return max_val;
102 }
103 
105 {
106  ASSERT(labels);
107  ASSERT(features);
108  int32_t num_train_labels=labels->get_num_labels();
109  int32_t num_feat=features->get_dim_feature_space();
110  int32_t num_vec=features->get_num_vectors();
111 
112  ASSERT(num_vec==num_train_labels);
113  SG_FREE(w);
114  w=SG_MALLOC(float64_t, num_feat);
115  memset(w,0,sizeof(float64_t)*num_feat);
116  w_dim=num_feat;
117 
118  CCplex solver;
119  solver.init(E_LINEAR);
120  SG_PRINT("setting up lpboost\n");
121  solver.setup_lpboost(C1, num_vec);
122  SG_PRINT("finished setting up lpboost\n");
123 
124  float64_t result=init(num_vec);
125  ASSERT(result);
126 
127  int32_t num_hypothesis=0;
128  CTime time;
130 
131  while (!(CSignal::cancel_computations()))
132  {
133  int32_t max_dim=0;
134  float64_t violator=find_max_violator(max_dim);
135  SG_PRINT("iteration:%06d violator: %10.17f (>1.0) chosen: %d\n", num_hypothesis, violator, max_dim);
136  if (violator <= 1.0+epsilon && num_hypothesis>1) //no constraint violated
137  {
138  SG_PRINT("converged after %d iterations!\n", num_hypothesis);
139  break;
140  }
141 
142  float64_t factor=+1.0;
143  if (max_dim>=num_svec)
144  {
145  factor=-1.0;
146  max_dim-=num_svec;
147  }
148 
150  int32_t len=sfeat[max_dim].num_feat_entries;
151  solver.add_lpboost_constraint(factor, h, len, num_vec, labels);
152  solver.optimize(u);
153  //CMath::display_vector(u, num_vec, "u");
154  num_hypothesis++;
155 
156  if (get_max_train_time()>0 && time.cur_time_diff()>get_max_train_time())
157  break;
158  }
159  float64_t* lambda=SG_MALLOC(float64_t, num_hypothesis);
160  solver.optimize(u, lambda);
161 
162  //CMath::display_vector(lambda, num_hypothesis, "lambda");
163  for (int32_t i=0; i<num_hypothesis; i++)
164  {
165  int32_t d=dim->get_element(i);
166  if (d>=num_svec)
167  w[d-num_svec]+=lambda[i];
168  else
169  w[d]-=lambda[i];
170 
171  }
172  //solver.write_problem("problem.lp");
173  solver.cleanup();
174 
175  cleanup();
176 
177  return true;
178 }
179 #endif

SHOGUN Machine Learning Toolbox - Documentation