gpdt.h

Go to the documentation of this file.
00001 /******************************************************************************
00002  ***        GPDT - Gradient Projection Decomposition Technique              ***
00003  ******************************************************************************
00004  ***                                                                        ***
00005  *** GPDT is a C++ software designed to train large-scale Support Vector    ***
00006  *** Machines for binary classification in both scalar and distributed      ***
00007  *** memory parallel environments. It uses the Joachims' problem            ***
00008  *** decomposition technique to split the whole quadratic programming (QP)  ***
00009  *** problem into a sequence of smaller QP subproblems, each one being      ***
00010  *** solved by a suitable gradient projection method (GPM). The presently   ***
00011  *** implemented GPMs are the Generalized Variable Projection Method        ***
00012  *** GVPM (T. Serafini, G. Zanghirati, L. Zanni, "Gradient Projection       ***
00013  *** Methods for Quadratic Programs and Applications in Training Support    ***
00014  *** Vector Machines"; Optim. Meth. Soft. 20, 2005, 353-378) and the        ***
00015  *** Dai-Fletcher Method DFGPM (Y. Dai and R. Fletcher,"New Algorithms for  ***
00016  *** Singly Linear Constrained Quadratic Programs Subject to Lower and      ***
00017  *** Upper Bounds"; Math. Prog. to appear).                                 ***
00018  ***                                                                        ***
00019  *** Authors:                                                               ***
00020  ***  Thomas Serafini, Luca Zanni                                           ***
00021  ***   Dept. of Mathematics, University of Modena and Reggio Emilia - ITALY ***
00022  ***   serafini.thomas@unimo.it, zanni.luca@unimo.it                        ***
00023  ***  Gaetano Zanghirati                                                    ***
00024  ***   Dept. of Mathematics, University of Ferrara - ITALY                  ***
00025  ***   g.zanghirati@unife.it                                                ***
00026  ***                                                                        ***
00027  *** Software homepage: http://dm.unife.it/gpdt                             ***
00028  ***                                                                        ***
00029  *** This work is supported by the Italian FIRB Projects                    ***
00030  ***      'Statistical Learning: Theory, Algorithms and Applications'       ***
00031  ***      (grant RBAU01877P), http://slipguru.disi.unige.it/ASTA            ***
00032  *** and                                                                    ***
00033  ***      'Parallel Algorithms and Numerical Nonlinear Optimization'        ***
00034  ***      (grant RBAU01JYPN), http://dm.unife.it/pn2o                       ***
00035  ***                                                                        ***
00036  *** Copyright (C) 2004 by T. Serafini, G. Zanghirati, L. Zanni.            ***
00037  ***                                                                        ***
00038  ***                     COPYRIGHT NOTIFICATION                             ***
00039  ***                                                                        ***
00040  *** Permission to copy and modify this software and its documentation      ***
00041  *** for internal research use is granted, provided that this notice is     ***
00042  *** retained thereon and on all copies or modifications. The authors and   ***
00043  *** their respective Universities makes no representations as to the       ***
00044  *** suitability and operability of this software for any purpose. It is    ***
00045  *** provided "as is" without express or implied warranty.                  ***
00046  *** Use of this software for commercial purposes is expressly prohibited   ***
00047  *** without contacting the authors.                                        ***
00048  ***                                                                        ***
00049  *** This program is free software; you can redistribute it and/or modify   ***
00050  *** it under the terms of the GNU General Public License as published by   ***
00051  *** the Free Software Foundation; either version 3 of the License, or      ***
00052  *** (at your option) any later version.                                    ***
00053  ***                                                                        ***
00054  *** This program is distributed in the hope that it will be useful,        ***
00055  *** but WITHOUT ANY WARRANTY; without even the implied warranty of         ***
00056  *** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          ***
00057  *** GNU General Public License for more details.                           ***
00058  ***                                                                        ***
00059  *** You should have received a copy of the GNU General Public License      ***
00060  *** along with this program; if not, write to the Free Software            ***
00061  *** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.              ***
00062  ***                                                                        ***
00063  *** File:     gpdt.h                                                       ***
00064  *** Type:     scalar                                                       ***
00065  *** Version:  1.0                                                          ***
00066  *** Date:     October, 2005                                                ***
00067  *** Revision: 1                                                            ***
00068  ***                                                                        ***
00069  ******************************************************************************/
00070 #include <shogun/kernel/Kernel.h>
00071 
00072 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00073 
00074 namespace shogun
00075 {
00076 #define MAXLENGTH 256
00077 #define cachetype KERNELCACHE_ELEM
00078 #define EPS_SV    1.0e-9   /* precision for multipliers */
00079 
00080 enum {
00081   SOLVER_VPM      = 0,
00082   SOLVER_FLETCHER = 1
00083 };
00084 
00086 class sKernel
00087 {
00088 public:
00090   int32_t  ker_type;
00092   int32_t  *lx;
00094   int32_t  **ix;
00096   float32_t  **x;
00098   float64_t *nor;
00100   float64_t sigma;
00102   float64_t degree;
00104   float64_t norm;
00106   float64_t c_poly;
00108   float64_t KernelEvaluations;
00109 
00116   float64_t (sKernel::*kernel_fun)(int32_t i, int32_t j);
00117 
00123   sKernel (shogun::CKernel* k, int32_t ell);
00124   ~sKernel();
00125 
00134   void SetData(
00135     float32_t **x_, int32_t **ix_, int32_t *lx_, int32_t ell, int32_t dim);
00136 
00143   void   SetSubproblem (sKernel* ker, int32_t len, int32_t *perm);
00144 
00151   float64_t Get(int32_t i, int32_t j)
00152   {
00153     KernelEvaluations += 1.0F;
00154     return kernel->kernel(i, j);
00155   }
00156 
00163   void   Add           (float64_t *v, int32_t j, float64_t mul);
00164 
00171   float64_t Prod          (float64_t *v, int32_t j);
00172 
00177   inline CKernel* get_kernel()
00178   {
00179     return kernel;
00180   }
00181 
00182 private:
00183   CKernel* kernel;
00184   int32_t    vauxRow;
00185   int32_t    IsSubproblem;
00186   int32_t    ell, dim;
00187   float32_t  *vaux;
00188 
00189   float64_t dot     (int32_t i, int32_t j);
00190 };
00191 
00192 void SplitParts (
00193     int32_t n, int32_t part, int32_t parts, int32_t *dim, int32_t *off);
00194 void SplitNum   (int32_t n, int32_t *nloc, int32_t *noff);
00195 }
00196 #endif // DOXYGEN_SHOULD_SKIP_THIS
00197 
00198 /******************************************************************************/
00199 /*** End of gpdt.h file                                                     ***/
00200 /******************************************************************************/
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation