//     This is a part of the SvmFu library, a library for training//     Support Vector Machines.//     Copyright (C) 2000  rif and MIT////     Contact: rif@mit.edu//     This program is free software; you can redistribute it and/or//     modify it under the terms of the GNU General Public License as//     published by the Free Software Foundation; either version 2 of//     the License, or (at your option) any later version.//     This program is distributed in the hope that it will be useful,//     but WITHOUT ANY WARRANTY; without even the implied warranty of//     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the//     GNU General Public License for more details.//     You should have received a copy of the GNU General Public//     License along with this program; if not, write to the Free//     Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,//     MA 02111-1307 USA#ifndef SVMFU_SVM_LARGE_OPT_HEADER#define SVMFU_SVM_LARGE_OPT_HEADER#include <set>#include <list>#include <queue>#include <vector>#include "SvmFuSvmConstants.h"#include "SvmFuSvmTypedefs.h"#include "SvmFuSvmSmallOpt.h"#include "SvmFuSvmBase.h"#include "SvmFuSvmKernCache.h"//! Contains an index into the training set and an alpha delta.//! For use in containers.//! This class could be functionally replaced by QueueElt_,//! but with a loss of program clarity.class AlphaDiffElt_ { public:  int elt_;  double diff_;    AlphaDiffElt_(int elt, double diff)     : elt_(elt), diff_(diff) {}  AlphaDiffElt_() : elt_(0), diff_(0) {}};//! Chunking Svm/*! * This class is used for solving * large-scale Svm optimization problems.  It makes repeated * use of SvmFuSvmSmallOpt to solve subproblems.  It declares a single * SvmFuSvmKernCache object, then repeatedly modifies it and a trnSetPtr, * and creates and optimizes successive SvmFuSvmSmallOpt objects. * * For best results, PRE-RANDOMIZE THE TRAINING SET!  (We include * the perl script randomize.pl that does this on the distribution * end.) * * We maintain a priority queue that contains an integer priority for * each element not in the working set.  When elements are removed from * the working set, they are given a priority of 1 if they still violate, * 2 otherwise (note that if we have to remove violators, we're in BAD * shape...)  At each iteration, we check all the points at the lowest priority * that contains at least one violator. * * modifications by vking@mit.edu spring 2001: *  - use the new higher-level cache * */template <class DataPt, class KernVal> class SvmLargeOpt :   public virtual SvmBase<DataPt, KernVal> {public:  //! The standard, cold-start constructor   SvmLargeOpt(int svmSize,	      const IntVec y,	      DataPt *trnSetPtr, // not const so kernCache can switch points	      const KernVal (*kernProdFuncPtr)(const DataPt &pt1,					       const DataPt &pt2),	      int chunkSize=SVM_LARGEOPT_DEFAULT_CHUNK_SIZE,	      double C=10, double tol=10E-4, double eps = 10E-12,	      int verbosity=1);    //! The standard, cold-start constructor, with an extraCacheRows arg  SvmLargeOpt(int svmSize,	      const IntVec y,	      DataPt *trnSetPtr, // not const so kernCache can switch points	      int extraCacheRows,	      const KernVal (*kernProdFuncPtr)(const DataPt &pt1,					       const DataPt &pt2),	      int chunkSize=SVM_LARGEOPT_DEFAULT_CHUNK_SIZE,	      double C=10, double tol=10E-4, double eps = 10E-12,	      int verbosity=1);    //! The warm-start constructor  SvmLargeOpt(int svmSize, const IntVec y,	      DataPt *trnSetPtr,	      const KernVal (*kernProdFuncPtr)(const DataPt &pt1,					       const DataPt &pt2),	      DoubleVec cVec, DoubleVec alphaVec, DoubleVec outputVec, 	      double b, int chunkSize=SVM_LARGEOPT_DEFAULT_CHUNK_SIZE,	      double tol=10E-4, double eps = 10E-12, int verbosity=1);    //! The hot-start constructor  SvmLargeOpt(int svmSize, const IntVec y,	      DataPt *trnSetPtr,	      const KernVal (*kernProdFuncPtr)(const DataPt &pt1,					       const DataPt &pt2),	      DoubleVec cVec, DoubleVec alphaVec, DoubleVec outputVec,	      double b, int chunkSize, 	      SvmKernCache<DataPt, KernVal> *chunkKernCache,	      double tol=10E-4, double eps = 10E-12, int verbosity=1);    void useLinearKernel(int dims, const void(*afunc)(double *&w, const DataPt &p, double amt), const double(*mfunc)(double *w, const DataPt &p));    virtual ~SvmLargeOpt();    void optimize();  void reoptimize();  virtual double outputAtTrainingExample(int ex) const;  virtual double dualObjFunc() const;  //! These are not guaranteed to be correct in general.  //! They are correct immediately after a call to computeTrainingSetPerf().  void getCurrentOutputVals(DoubleVec outputVals);  int computeLeaveOneOutErrors(DoubleVec LOO_Vals);private:  // Support for Linear SVMs  const void(*addToWPtr_) (double *& w, const DataPt &p, double amt);  const double(*multWPtr_) (double *w, const DataPt &p);  bool usingLinear_;  double *w_;  int linDims_;  int chunkSize_;    double tol_;  int verbosity_;    SvmSmallOpt<DataPt, KernVal> *chunkSvm_;    //! chunkSize_ indexes into the training set  IntVec workingSet_;  //! svmSize_ indexes into workingSet_  IntVec workingSetPos_;    IntVec chunkY_;  DataPt *chunkTrnSetPtr_;  SvmKernCache<DataPt, KernVal> *chunkKernCache_;  bool chunkKernCacheAllocatedP_;  int extraCacheRows_;    DoubleVec chunkC_Vec_;  DoubleVec chunkAlphas_;  int numChunkSVs_, numChunkUSVs_;    mutable DoubleVec outputs_;    // Note that QueueElt_'s are set up so that the front item  // of the queue is the one with the LARGEST priority:  //   eltQueue_: priority = -KKT_Dist  //   removalQueue_: priority = KKT_Dist + 1 * (alpha == 0)  priority_queue<QueueElt_> eltQueue_; // examples to check  priority_queue<QueueElt_> removalQueue_; // removal from working set    vector<AlphaDiffElt_ *> alphaDiffHistory_;  vector<double> alphaDiffLengths_;  vector<double> bHistory_;    int majorIterations_;  //! Number of the last major iteration   IntVec lastCheckIter_;    //! for use by update in outputAtTrainingExample  mutable IntVec updateHelper_;     //! used to store temporary kernel products  mutable KernVal *tempKernProds_;   mutable int updateNumber_;    KernVal *selfProds_;  vector<double> phis_;    //! number of times we have to check a point before shrinking it.  //! For large chunk sizes, 0 seems to work pretty well...  int checksBeforeShrinking_;    //! we keep this percentage of the points we would otherwise shrink  double nonShrinkProportion_;   bool optimized_;  enum {coldStart, warmStart, hotStart} startType_;  void initInternal();  void setupAndSolveInitialChunk();  bool setupAndSolveNewChunk();  void forceCurrentChunk();    void createInitialWorkingSet();  void createInitialWorkingSetCold();  void createInitialWorkingSetWarm();  void createInitialWorkingSetHot();    void setupInitialChunkData();  void buildAndSolveChunk();  void updateAlphasAndB();  void destroyChunk();    bool updateWorkingSetAndChunkData();    void pivotWorkingSet(int pointToAdd, int pointToRemove);  //! POSITIVE results -> violation, NEGATIVE results ->  //! how far we are FROM being a violation.  double KKT_ViolationAmt(int ex) const;  int computeLeaveOneOutErrorsInternal(BoolVec LOO_CompNeededP,				       DoubleVec LOO_Vals);};#endif // SVMFU_SVM_LARGE_OPT_HEADER