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 "kernel/Kernel.h"
00071 
00072 #define MAXLENGTH 256
00073 #define cachetype KERNELCACHE_ELEM
00074 #define EPS_SV    1.0e-9   /* precision for multipliers */
00075 
00076 enum {
00077   SOLVER_VPM      = 0,
00078   SOLVER_FLETCHER = 1
00079 };
00080 
00082 class sKernel
00083 {
00084 public:
00086   int32_t  ker_type;
00088   int32_t  *lx;
00090   int32_t  **ix;
00092   float32_t  **x;
00094   float64_t *nor;
00096   float64_t sigma;
00098   float64_t degree;
00100   float64_t norm;
00102   float64_t c_poly;
00104   float64_t KernelEvaluations;
00105 
00112   float64_t (sKernel::*kernel_fun)(int32_t i, int32_t j);
00113 
00119   sKernel (CKernel* k, int32_t ell);
00120   ~sKernel();
00121 
00130   void SetData(
00131     float32_t **x_, int32_t **ix_, int32_t *lx_, int32_t ell, int32_t dim);
00132 
00139   void   SetSubproblem (sKernel* ker, int32_t len, int32_t *perm);
00140 
00147   float64_t Get(int32_t i, int32_t j)
00148   {
00149     KernelEvaluations += 1.0F;
00150     return kernel->kernel(i, j);
00151   }
00152 
00159   void   Add           (float64_t *v, int32_t j, float64_t mul);
00160 
00167   float64_t Prod          (float64_t *v, int32_t j);
00168 
00173   inline CKernel* get_kernel()
00174   {
00175     return kernel;
00176   }
00177 
00178 private:
00179   CKernel* kernel;
00180   int32_t    vauxRow;
00181   int32_t    IsSubproblem;
00182   int32_t    ell, dim;
00183   float32_t  *vaux;
00184 
00185   float64_t dot     (int32_t i, int32_t j);
00186 };
00187 
00188 void SplitParts (
00189     int32_t n, int32_t part, int32_t parts, int32_t *dim, int32_t *off);
00190 void SplitNum   (int32_t n, int32_t *nloc, int32_t *noff);
00191 
00192 /******************************************************************************/
00193 /*** End of gpdt.h file                                                     ***/
00194 /******************************************************************************/

SHOGUN Machine Learning Toolbox - Documentation