LooErrorCSvm.h
Go to the documentation of this file.
1/*!
2 *
3 *
4 * \brief Leave-one-out error for C-SVMs
5 *
6 *
7 *
8 * \author T.Glasmachers
9 * \date 2011
10 *
11 *
12 * \par Copyright 1995-2017 Shark Development Team
13 *
14 * <BR><HR>
15 * This file is part of Shark.
16 * <https://shark-ml.github.io/Shark/>
17 *
18 * Shark is free software: you can redistribute it and/or modify
19 * it under the terms of the GNU Lesser General Public License as published
20 * by the Free Software Foundation, either version 3 of the License, or
21 * (at your option) any later version.
22 *
23 * Shark is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * GNU Lesser General Public License for more details.
27 *
28 * You should have received a copy of the GNU Lesser General Public License
29 * along with Shark. If not, see <http://www.gnu.org/licenses/>.
30 *
31 */
32#ifndef SHARK_OBJECTIVEFUNCTIONS_LOOERRORCSVM_H
33#define SHARK_OBJECTIVEFUNCTIONS_LOOERRORCSVM_H
34
35
36#include <shark/ObjectiveFunctions/AbstractObjectiveFunction.h>
37#include <shark/ObjectiveFunctions/Loss/ZeroOneLoss.h>
38#include <shark/Algorithms/QP/BoxConstrainedProblems.h>
39#include <shark/Algorithms/QP/SvmProblems.h>
40#include <shark/LinAlg/CachedMatrix.h>
41#include <shark/LinAlg/KernelMatrix.h>
42#include <shark/Models/Kernels/KernelExpansion.h>
43
44namespace shark {
45
46///
47/// \brief Leave-one-out error, specifically optimized for C-SVMs.
48/// \ingroup kerneloptimization
49template<class InputType, class CacheType = float>
50class LooErrorCSvm : public AbstractObjectiveFunction< RealVector, double >
51{
52public:
53 typedef CacheType QpFloatType;
54 typedef AbstractKernelFunction<InputType> KernelType;
55 typedef LabeledData<InputType, unsigned int> DatasetType;
56
57 /// \brief Constructor.
58 LooErrorCSvm(DatasetType const& dataset, KernelType* kernel, bool withOffset)
59 : mep_dataset(&dataset)
60 , mep_kernel(kernel)
61 , m_withOffset(withOffset)
62 {
63 SHARK_RUNTIME_CHECK(kernel != NULL, "kernel is not allowed to be Null");
64 m_features |= HAS_VALUE;
65 }
66
67
68 /// \brief From INameable: return the class name.
69 std::string name() const
70 { return "LooErrorCSvm"; }
71
72 std::size_t numberOfVariables()const{
73 return mep_kernel->numberOfParameters()+1;
74 }
75
76 /// Evaluate the leave-one-out error for the given parameters.
77 /// These parameters describe the regularization
78 /// constant and the kernel parameters.
79 double eval(const RealVector& params){
80 QpStoppingCondition stop;
81 return eval(params, stop);
82 }
83 /// Evaluate the leave-one-out error for the given parameters.
84 /// These parameters describe the regularization constant and
85 /// the kernel parameters. Furthermore, the stopping
86 /// conditions for the solver are passed as an argument.
87 double eval(const RealVector& params, QpStoppingCondition &stop){
88 this->m_evaluationCounter++;
89
90 double C = params.back();
91 mep_kernel->setParameterVector(subrange(params,0,params.size() - 1));
92
93 ZeroOneLoss<unsigned int, RealVector> loss;
94
95 // prepare the quadratic program
96 typedef KernelMatrix<InputType, QpFloatType> KernelMatrixType;
97 typedef CachedMatrix< KernelMatrixType > CachedMatrixType;
98 typedef CSVMProblem<CachedMatrixType> SVMProblemType;
99 KernelMatrixType km(*mep_kernel, mep_dataset->inputs());
100 CachedMatrixType matrix(&km);
101 SVMProblemType svmProblem(matrix,mep_dataset->labels(),C);
102 std::size_t ell = km.size();
103
104 //QpStoppingCondition stop;
105
106 if (m_withOffset)
107 {
108 // solve the full problem with equality constraint and activated shrinking
109 typedef SvmProblem<SVMProblemType> ProblemType;
110 ProblemType problem(svmProblem);
111 QpSolver< ProblemType > solver(problem);
112 solver.solve(stop);
113 RealVector alphaFull(problem.dimensions());
114 for(std::size_t i = 0; i != problem.dimensions(); ++i){
115 alphaFull(i) = problem.alpha(i);
116 }
117 KernelExpansion<InputType> svm(mep_kernel,mep_dataset->inputs(),true);
118
119 // leave-one-out
120 //problem.setShrinking(false);
121 double mistakes = 0;
122 for (std::size_t i=0; i<ell; i++)
123 {
124 // use sparseness of the solution:
125 if (alphaFull(i) == 0.0) continue;
126 problem.deactivateVariable(i);
127
128 // solve the reduced problem
129 solver.solve(stop);
130
131 // predict using the previously removed example.
132 // we need to take into account that the initial problem is solved
133 // with shrinking and we thus need to get the initial permutation
134 // for the element index and the unpermuted alpha for the svm
135 column(svm.alpha(),0)= problem.getUnpermutedAlpha();
136 svm.offset(0) = computeBias(problem);
137 std::size_t elementIndex = i;//svmProblem.permutation[i];
138 unsigned int target = mep_dataset->element(elementIndex).label;
139 mistakes += loss(target, svm(mep_dataset->element(elementIndex).input));
140
141 problem.activateVariable(i);
142 }
143 return mistakes / (double)ell;
144 }
145 else
146 {
147 // solve the full problem without equality constraint and activated shrinking
148 typedef BoxConstrainedProblem<SVMProblemType> ProblemType;
149 ProblemType problem(svmProblem);
150 QpSolver< ProblemType > solver(problem);
151 solver.solve(stop);
152 RealVector alphaFull(problem.dimensions());
153 for(std::size_t i = 0; i != problem.dimensions(); ++i){
154 alphaFull(i) = problem.alpha(i);
155 }
156 KernelExpansion<InputType> svm(mep_kernel,mep_dataset->inputs(),false);
157
158 // leave-one-out
159 //problem.setShrinking(false);
160 double mistakes = 0;
161 for (std::size_t i=0; i<ell; i++)
162 {
163 // use sparseness of the solution:
164 if (alphaFull(i) == 0.0) continue;
165 problem.deactivateVariable(i);
166
167
168 // solve the reduced problem
169 solver.solve(stop);
170
171 // predict using the previously removed example.
172 // we need to take into account that the initial problem is solved
173 // with shrinking and we thus need to get the initial permutation
174 // for the element index and the unpermuted alpha for the svm
175 column(svm.alpha(),0)= problem.getUnpermutedAlpha();
176 std::size_t elementIndex = i;//svmProblem.permutation[i];
177 unsigned int target = mep_dataset->element(elementIndex).label;
178 mistakes += loss(target, svm(mep_dataset->element(elementIndex).input));
179
180 problem.activateVariable(i);
181 }
182 return mistakes / (double)ell;
183 }
184 }
185
186private:
187 /// Compute the SVM offset term (b).
188 template<class Problem>
189 double computeBias(Problem const& problem){
190 double lowerBound = -1e100;
191 double upperBound = 1e100;
192 double sum = 0.0;
193 std::size_t freeVars = 0;
194 std::size_t ell = problem.dimensions();
195 for (std::size_t i=0; i<ell; i++)
196 {
197 double value = problem.gradient(i);
198 if (problem.alpha(i) == problem.boxMin(i))
199 {
200 lowerBound = std::max(value,lowerBound);
201 }
202 else if (problem.alpha(i) == problem.boxMax(i))
203 {
204 upperBound = std::min(value,upperBound);
205 }
206 else
207 {
208 sum += value;
209 freeVars++;
210 }
211 }
212 if (freeVars > 0)
213 return sum / freeVars;
214 else
215 return 0.5 * (lowerBound + upperBound);
216 }
217
218 const DatasetType* mep_dataset;
219 KernelType* mep_kernel;
220 bool m_withOffset;
221};
222
223
224}
225#endif