AbstractBudgetMaintenanceStrategy.h
Go to the documentation of this file.
1//===========================================================================
2/*!
3 *
4 *
5 * \brief Abstract Budget maintenance strategy
6 *
7 * \par
8 * This holds the interface for any budget maintenance strategy.
9 *
10 *
11 *
12 *
13 * \author Aydin Demircioglu
14 * \date 2014
15 *
16 *
17 * \par Copyright 1995-2017 Shark Development Team
18 *
19 * <BR><HR>
20 * This file is part of Shark.
21 * <https://shark-ml.github.io/Shark/>
22 *
23 * Shark is free software: you can redistribute it and/or modify
24 * it under the terms of the GNU Lesser General Public License as published
25 * by the Free Software Foundation, either version 3 of the License, or
26 * (at your option) any later version.
27 *
28 * Shark is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public License
34 * along with Shark. If not, see <http://www.gnu.org/licenses/>.
35 *
36 */
37//===========================================================================
38
39
40#ifndef SHARK_MODELS_ABSTRACTBUDGETMAINTENANCESTRATEGY_H
41#define SHARK_MODELS_ABSTRACTBUDGETMAINTENANCESTRATEGY_H
42
43#include <shark/Data/Dataset.h>
44#include <shark/Data/DataView.h>
45#include <shark/Models/Kernels/AbstractKernelFunction.h>
46#include <shark/Models/Kernels/KernelExpansion.h>
47
48
49namespace shark
50{
51
52///
53/// \brief This is the abstract interface for any budget maintenance strategy.
54///
55/// To allow for easy exchange of budget maintenance strategies, each of
56/// them should derive from this class. The only function it defines is addToModel,
57/// which, when implemented, will add a given supportvector and given alphas
58/// to the provided model by applying the respective budget maintenance strategy.
59/// (Note that not all merging strategies need the alphas, but some do)
60///
61template<class InputType>
62class AbstractBudgetMaintenanceStrategy
63{
64
65public:
66 typedef KernelExpansion<InputType> ModelType;
67 typedef LabeledData<InputType, unsigned int> DataType;
68 typedef typename DataType::element_type ElementType;
69
72
73
74 /// this is the main interface, which adds a given supportvector with
75 /// given alpha coefficients to the model.
76 ///
77 /// @param[in,out] model the model the strategy will work with
78 /// @param[in] alpha alphas for the new budget vector
79 /// @param[in] supportVector the vector to add to the model by applying the maintenance strategy
80 ///
81 virtual void addToModel(ModelType& model, InputType const& alpha, ElementType const& supportVector) = 0;
82
83
84
85 /// this will find the vector with the smallest alpha, measured in 2-norm
86 /// in the given model. now there is a special case: if there is somewhere a zero
87 /// coefficient, then obviously this is the smallest element. in this case we
88 /// just proceed as usual. the caller must decide what to do with such a vector.
89 /// \par note: The model is not allowed to be empty and an exception is thrown in this case.
90 ///
91 /// @param[in] model the model we want to search
92 /// @param[out] minIndex the index of the vector with smallest coefficient
93 /// @param[out] minAlpha the 2-norm of the alpha coefficient of the found vector
94 ///
95 static void findSmallestVector(ModelType const& model, size_t &minIndex, double &minAlpha){
96 SHARK_RUNTIME_CHECK(model.alpha().size1(), "Model is empty!");
97 // we do not have it, so we remove the vector with the
98 // smallest 'influcence', measured by the smallest alpha
99
100 minAlpha = norm_2(row(model.alpha(), 0));
101 minIndex = 0;
102
103 for(size_t j = 1; j < model.alpha().size1(); j++)
104 {
105 double currentNorm = blas::norm_2(row(model.alpha(), j));
106
107 if(currentNorm < minAlpha)
108 {
109 minAlpha = norm_2(row(model.alpha(), j));
110 minIndex = j;
111 }
112 }
113 }
114
115
116 /// return the class name
117 std::string name() const
118 { return "AbstractBudgetMaintenanceStrategy"; }
119};
120
121
122}
123#endif