SHOGUN  v2.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
gpdt.h
Go to the documentation of this file.
1 /******************************************************************************
2  *** GPDT - Gradient Projection Decomposition Technique ***
3  ******************************************************************************
4  *** ***
5  *** GPDT is a C++ software designed to train large-scale Support Vector ***
6  *** Machines for binary classification in both scalar and distributed ***
7  *** memory parallel environments. It uses the Joachims' problem ***
8  *** decomposition technique to split the whole quadratic programming (QP) ***
9  *** problem into a sequence of smaller QP subproblems, each one being ***
10  *** solved by a suitable gradient projection method (GPM). The presently ***
11  *** implemented GPMs are the Generalized Variable Projection Method ***
12  *** GVPM (T. Serafini, G. Zanghirati, L. Zanni, "Gradient Projection ***
13  *** Methods for Quadratic Programs and Applications in Training Support ***
14  *** Vector Machines"; Optim. Meth. Soft. 20, 2005, 353-378) and the ***
15  *** Dai-Fletcher Method DFGPM (Y. Dai and R. Fletcher,"New Algorithms for ***
16  *** Singly Linear Constrained Quadratic Programs Subject to Lower and ***
17  *** Upper Bounds"; Math. Prog. to appear). ***
18  *** ***
19  *** Authors: ***
20  *** Thomas Serafini, Luca Zanni ***
21  *** Dept. of Mathematics, University of Modena and Reggio Emilia - ITALY ***
22  *** serafini.thomas@unimo.it, zanni.luca@unimo.it ***
23  *** Gaetano Zanghirati ***
24  *** Dept. of Mathematics, University of Ferrara - ITALY ***
25  *** g.zanghirati@unife.it ***
26  *** ***
27  *** Software homepage: http://dm.unife.it/gpdt ***
28  *** ***
29  *** This work is supported by the Italian FIRB Projects ***
30  *** 'Statistical Learning: Theory, Algorithms and Applications' ***
31  *** (grant RBAU01877P), http://slipguru.disi.unige.it/ASTA ***
32  *** and ***
33  *** 'Parallel Algorithms and Numerical Nonlinear Optimization' ***
34  *** (grant RBAU01JYPN), http://dm.unife.it/pn2o ***
35  *** ***
36  *** Copyright (C) 2004 by T. Serafini, G. Zanghirati, L. Zanni. ***
37  *** ***
38  *** COPYRIGHT NOTIFICATION ***
39  *** ***
40  *** Permission to copy and modify this software and its documentation ***
41  *** for internal research use is granted, provided that this notice is ***
42  *** retained thereon and on all copies or modifications. The authors and ***
43  *** their respective Universities makes no representations as to the ***
44  *** suitability and operability of this software for any purpose. It is ***
45  *** provided "as is" without express or implied warranty. ***
46  *** Use of this software for commercial purposes is expressly prohibited ***
47  *** without contacting the authors. ***
48  *** ***
49  *** This program is free software; you can redistribute it and/or modify ***
50  *** it under the terms of the GNU General Public License as published by ***
51  *** the Free Software Foundation; either version 3 of the License, or ***
52  *** (at your option) any later version. ***
53  *** ***
54  *** This program is distributed in the hope that it will be useful, ***
55  *** but WITHOUT ANY WARRANTY; without even the implied warranty of ***
56  *** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ***
57  *** GNU General Public License for more details. ***
58  *** ***
59  *** You should have received a copy of the GNU General Public License ***
60  *** along with this program; if not, write to the Free Software ***
61  *** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. ***
62  *** ***
63  *** File: gpdt.h ***
64  *** Type: scalar ***
65  *** Version: 1.0 ***
66  *** Date: October, 2005 ***
67  *** Revision: 1 ***
68  *** ***
69  ******************************************************************************/
70 #include <shogun/kernel/Kernel.h>
71 
72 #ifndef DOXYGEN_SHOULD_SKIP_THIS
73 
74 namespace shogun
75 {
76 #define MAXLENGTH 256
77 #define cachetype KERNELCACHE_ELEM
78 #define EPS_SV 1.0e-9 /* precision for multipliers */
79 
80 enum {
81  SOLVER_VPM = 0,
82  SOLVER_FLETCHER = 1
83 };
84 
86 class sKernel
87 {
88 public:
90  int32_t ker_type;
92  int32_t *lx;
94  int32_t **ix;
96  float32_t **x;
98  float64_t *nor;
100  float64_t sigma;
102  float64_t degree;
104  float64_t norm;
106  float64_t c_poly;
108  float64_t KernelEvaluations;
109 
116  float64_t (sKernel::*kernel_fun)(int32_t i, int32_t j);
117 
123  sKernel (shogun::CKernel* k, int32_t ell);
124  ~sKernel();
125 
134  void SetData(
135  float32_t **x_, int32_t **ix_, int32_t *lx_, int32_t ell, int32_t dim);
136 
143  void SetSubproblem (sKernel* ker, int32_t len, int32_t *perm);
144 
151  float64_t Get(int32_t i, int32_t j)
152  {
153  KernelEvaluations += 1.0F;
154  return kernel->kernel(i, j);
155  }
156 
163  void Add (float64_t *v, int32_t j, float64_t mul);
164 
171  float64_t Prod (float64_t *v, int32_t j);
172 
177  inline CKernel* get_kernel()
178  {
179  return kernel;
180  }
181 
182 private:
183  CKernel* kernel;
184  int32_t vauxRow;
185  int32_t IsSubproblem;
186  int32_t ell, dim;
187  float32_t *vaux;
188 
189  float64_t dot (int32_t i, int32_t j);
190 };
191 
192 void SplitParts (
193  int32_t n, int32_t part, int32_t parts, int32_t *dim, int32_t *off);
194 void SplitNum (int32_t n, int32_t *nloc, int32_t *noff);
195 }
196 #endif // DOXYGEN_SHOULD_SKIP_THIS
197 
198 /******************************************************************************/
199 /*** End of gpdt.h file ***/
200 /******************************************************************************/
SHOGUN Machine Learning Toolbox - Documentation