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 int ker_type; 00088 int *lx; 00090 int **ix; 00092 float **x; 00094 double *nor; 00096 double sigma; 00098 double degree; 00100 double norm; 00102 double c_poly; 00104 double KernelEvaluations; 00105 00112 double (sKernel::*kernel_fun)(int i, int j); 00113 00119 sKernel (CKernel* k, int ell); 00120 ~sKernel(); 00121 00130 void SetData (float **x_, int **ix_, int *lx_, int ell, int dim); 00131 00138 void SetSubproblem (sKernel* ker, int len, int *perm); 00139 00146 double Get(int i, int j) 00147 { 00148 KernelEvaluations += 1.0F; 00149 return kernel->kernel(i, j); 00150 } 00151 00158 void Add (double *v, int j, double mul); 00159 00166 double Prod (double *v, int j); 00167 00172 inline CKernel* get_kernel() 00173 { 00174 return kernel; 00175 } 00176 00177 private: 00178 CKernel* kernel; 00179 int vauxRow; 00180 int IsSubproblem; 00181 int ell, dim; 00182 float *vaux; 00183 00184 double dot (int i, int j); 00185 }; 00186 00187 void SplitParts (int n, int part, int parts, int *dim, int *off); 00188 void SplitNum (int n, int *nloc, int *noff); 00189 00190 /******************************************************************************/ 00191 /*** End of gpdt.h file ***/ 00192 /******************************************************************************/