ProjectBudgetMaintenanceStrategy.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Project budget maintenance strategy
6  *
7  * \par
8  * This is an budget strategy that simply project one of the
9  * budget vectors onto the others. To save time, the smallest
10  * vector (measured in 2-norm of the alpha-coefficients) will
11  * be selected for projection.
12  *
13  *
14  *
15  *
16  * \author Aydin Demircioglu
17  * \date 2014
18  *
19  *
20  * \par Copyright 1995-2015 Shark Development Team
21  *
22  * <BR><HR>
23  * This file is part of Shark.
24  * <http://image.diku.dk/shark/>
25  *
26  * Shark is free software: you can redistribute it and/or modify
27  * it under the terms of the GNU Lesser General Public License as published
28  * by the Free Software Foundation, either version 3 of the License, or
29  * (at your option) any later version.
30  *
31  * Shark is distributed in the hope that it will be useful,
32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34  * GNU Lesser General Public License for more details.
35  *
36  * You should have received a copy of the GNU Lesser General Public License
37  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
38  *
39  */
40 //===========================================================================
41 
42 
43 #ifndef SHARK_MODELS_PROJECTBUDGETMAINTENANCESTRATEGY_H
44 #define SHARK_MODELS_PROJECTBUDGETMAINTENANCESTRATEGY_H
45 
46 #include <shark/Models/Converter.h>
49 #include <shark/Data/Dataset.h>
50 #include <shark/Data/DataView.h>
51 
52 
53 namespace shark {
54 
55  ///
56  /// \brief Budget maintenance strategy that projects a vector
57  ///
58  /// This is an budget strategy that simply projects one of the
59  /// budget vectors onto the others. The resulting coefficients are
60  /// then added to the other vectors and the projected vector is
61  /// removed from the budget.
62  ///
63  template<class InputType>
67  typedef typename DataType::element_type ElementType;
68 
69  public:
70 
71  /// constructor.
73  }
74 
75 
76  /// add to model.
77  /// this is just a fake here, as it is unclear in general how to merge two objects,
78  /// one needs to specialize this template.
79  ///
80  /// @param[in,out] model the model the strategy will work with
81  /// @param[in] alpha alphas for the new budget vector
82  /// @param[in] supportVector the vector to add to the model by applying the maintenance strategy
83  ///
84  virtual void addToModel (ModelType& model, InputType const& alpha, ElementType const& supportVector) {
85  // to project we simply utilize the kernel basis distance
86  }
87 
88 
89  /// class name
90  std::string name() const
91  { return "ProjectBudgetMaintenanceStrategy"; }
92 
93  protected:
94 
95  };
96 
97  ///
98  /// \brief Budget maintenance strategy that projects a vector
99  ///
100  /// \par This is an specialization of the project budget maintenance strategy
101  /// that handles simple real-valued vectors. This is a nearly 1:1 adoption of
102  /// the strategy presented in Wang, Cramer and Vucetic.
103  ///
104  template<>
106  typedef RealVector InputType;
109  typedef typename DataType::element_type ElementType;
110 
111  public:
112 
113  /// constructor.
115  }
116 
117 
118 
119  /// add a vector to the model.
120  /// this will add the given vector to the model and merge the budget so that afterwards
121  /// the budget size is kept the same. If the budget has a free entry anyway, no merging
122  /// will be performed, but instead the given vector is simply added to the budget.
123  ///
124  /// @param[in,out] model the model the strategy will work with
125  /// @param[in] alpha alphas for the new budget vector
126  /// @param[in] supportVector the vector to add to the model by applying the maintenance strategy
127  ///
128  virtual void addToModel (ModelType& model, InputType const& alpha, ElementType const& supportVector) {
129 
130  // projecting should try out every budget vector
131  // but as this would yield $O(B^3)$ runtime, the vector
132  // with the smallest alpha is taken instead.
133 
134  // first put the new vector into place
135  size_t maxIndex = model.basis().numberOfElements();
136  model.basis().element(maxIndex - 1) = supportVector.input;
137  row (model.alpha(), maxIndex - 1) = alpha;
138 
139 
140  size_t firstIndex = 0;
141  double firstAlpha = 0;
142  findSmallestVector (model, firstIndex, firstAlpha);
143 
144  // if the smallest vector has zero alpha,
145  // the budget is not yet filled so we can skip projecting.
146  if (firstAlpha == 0.0f)
147  {
148  // as we need the last vector to be zero, we put the new
149  // vector to that place and undo our putting-the-vector-to-back-position
150  model.basis().element(firstIndex) = supportVector.input;
151  row (model.alpha(), firstIndex) = alpha;
152 
153  // enough to zero out the alpha
154  row (model.alpha(), maxIndex - 1).clear();
155 
156  // ready.
157  return;
158  }
159 
160  // now solve the projection equation
161 
162  // we need to project the one vector we have chosen down
163  // to all others. so we need a model with just thet one vector
164  // and then we try to approximate alphas from the rest of thet
165  // vectors, such that the difference is small as possible.
166 
167  // create a KernelExpansion just with the one selected vector.
168  std::vector<RealVector> singlePointVector (1,model.basis().element(firstIndex));
169  std::vector<unsigned int> singlePointLabel (1, 0);
170  ClassificationDataset singlePointData = createLabeledDataFromRange(singlePointVector, singlePointLabel);
171  KernelExpansion<RealVector> singlePointExpansion(model.kernel(), singlePointData.inputs(), false, model.alpha().size2());
172  row (singlePointExpansion.alpha(), 0) = row (model.alpha(), firstIndex);
173  KernelBasisDistance distance(&singlePointExpansion, maxIndex - 1);
174 
175  // now create a whole new 'point' with all the other vectors.
176  // then our approximation will give us one coefficient to approximate
177  // the basis, which consits only of the one selected vector.
178  // thus, we approximate the one vector with the rest of them.
179  size_t inputDimension = model.basis().element(0).size();
180  RealVector point(inputDimension * (maxIndex - 1));
181 
182  // copy all other budget vectors into one big vector
183  size_t linearIndex = 0;
184  for(std::size_t t = 0; t < maxIndex; t++){
185  // do not copy the first index.
186  if (t == firstIndex)
187  continue;
188  noalias(subrange(point, linearIndex*inputDimension, (linearIndex+1)*inputDimension)) = (model.basis().element(t));
189  linearIndex++;
190  }
191 
192  //calculate solution found by the function and check that it is close
193  RealMatrix projectedAlphas = distance.findOptimalBeta(point);
194 
195  // stupid sanity check
196  SHARK_ASSERT (projectedAlphas.size2() == model.alpha().size2());
197 
198  // add the projected values to the budget
199  linearIndex = 0;
200  for (std::size_t j = 0; j < maxIndex; j++)
201  {
202  if (j == firstIndex)
203  continue;
204 
205  // for each class we add the alpha contribution to the true alphas.
206  for (std::size_t c = 0; c < model.alpha().size2(); c++)
207  model.alpha(j, c) += projectedAlphas(linearIndex, c);
208 
209  linearIndex++;
210  }
211 
212  // overwrite the projected vector with the last vector
213  model.basis().element(firstIndex) = supportVector.input;
214  row (model.alpha(), firstIndex) = alpha;
215 
216  // zero out buffer, enough to zero out the alpha
217  row (model.alpha(), maxIndex - 1).clear();
218  }
219 
220 
221  /// class name
222  std::string name() const
223  { return "ProjectBudgetMaintenanceStrategy"; }
224 
225  protected:
226 
227  };
228 
229 
230 }
231 #endif