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 /******************************************************************************/