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 00081 #ifndef DOXYGEN_SHOULD_SKIP_THIS 00082 00083 class sKernel 00084 { 00085 public: 00087 int32_t ker_type; 00089 int32_t *lx; 00091 int32_t **ix; 00093 float32_t **x; 00095 float64_t *nor; 00097 float64_t sigma; 00099 float64_t degree; 00101 float64_t norm; 00103 float64_t c_poly; 00105 float64_t KernelEvaluations; 00106 00113 float64_t (sKernel::*kernel_fun)(int32_t i, int32_t j); 00114 00120 sKernel (CKernel* k, int32_t ell); 00121 ~sKernel(); 00122 00131 void SetData( 00132 float32_t **x_, int32_t **ix_, int32_t *lx_, int32_t ell, int32_t dim); 00133 00140 void SetSubproblem (sKernel* ker, int32_t len, int32_t *perm); 00141 00148 float64_t Get(int32_t i, int32_t j) 00149 { 00150 KernelEvaluations += 1.0F; 00151 return kernel->kernel(i, j); 00152 } 00153 00160 void Add (float64_t *v, int32_t j, float64_t mul); 00161 00168 float64_t Prod (float64_t *v, int32_t j); 00169 00174 inline CKernel* get_kernel() 00175 { 00176 return kernel; 00177 } 00178 00179 private: 00180 CKernel* kernel; 00181 int32_t vauxRow; 00182 int32_t IsSubproblem; 00183 int32_t ell, dim; 00184 float32_t *vaux; 00185 00186 float64_t dot (int32_t i, int32_t j); 00187 }; 00188 00189 void SplitParts ( 00190 int32_t n, int32_t part, int32_t parts, int32_t *dim, int32_t *off); 00191 void SplitNum (int32_t n, int32_t *nloc, int32_t *noff); 00192 #endif // DOXYGEN_SHOULD_SKIP_THIS 00193 00194 /******************************************************************************/ 00195 /*** End of gpdt.h file ***/ 00196 /******************************************************************************/