svmfusvmlargeopt.h

This is SvmFu, a package for training and testing support vector machines (SVMs). It s written in C

//     This is a part of the SvmFu library, a library for training
//     Support Vector Machines.
//     Copyright (C) 2000  rif and MIT
//
//     Contact: [e-mail]

//     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 [e-mail] 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