svmfusvmkerncache.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_KERN_CACHE_HEADER
#define SVMFU_SVM_KERN_CACHE_HEADER

#include "SvmFuSvmConstants.h"
#include "SvmFuSvmTypedefs.h"

#include <set>
#include <list>
#include <map>
#include <queue>

//! Contains a index into the training set and a priority.
/*! For use in a priority queue.  
 * \sa SvmLargeOpt
 */
class QueueElt_ {
 public:
  int elt_;
  double priority_;
  
  bool operator<(const QueueElt_& x) const { 
    return priority_ < x.priority_; 
  }

  QueueElt_(int elt, double priority) : elt_(elt), priority_(priority) {}
};

//! This is a helper class for SvmFu.  It stores cached kernel values.
template <class DataPt, class KernVal> class SvmKernCache {
 public:
  
  //! Constructor
  SvmKernCache(int workingSetSize, int extraRows, int trnSetSize,
 	       const DataPt * const trnSetPtr,
	       const KernVal (*kernProdFuncPtr)(const DataPt &,
						const DataPt &));
  
  //! Destructor
  ~SvmKernCache();
  
  /////////////
  // Mutators
  /////////////

  //! Notify of new working set and KKT violations
  void workingSetChanged (const int * const workingSet,
			  const priority_queue<QueueElt_> &others);
  void saveToFile(char *filename);
  void readFromFile(char *kernelTrainFile);

  int getColToTrnSet(int ex) const;
  int getTrnSetToCol(int ex) const;
  int getTrnSetToRow(int ex) const;
  
  //////////////
  // Accessors
  //////////////
  
  //! Returns the kernel product of the pair of working set points
  KernVal cachedKernProd (int ex1, int ex2) const;

  //! Returns the kernel product of the pair of training set points
  KernVal trnSetKernProd (int ex1, int ex2) const;
  
  //! Returns a pointer to the kernel row for the working set point
  KernVal *cachedKernProdRowPtr (int ex) const;

  //! Return our number of extra rows
  int numExtraRows () const;

  bool readFromFile_;
protected:
  
  //! Allocates, updates data structures, and populates with invalid values
  inline void initializeRow (int row) const;

  //! Indicates whether the specified cell is valid or not
  inline bool cellValid (int row, int col) const;
  
  //! Marks the cell as invalid
  inline void invalidateCell (int row, int col) const;

  //! Number of rows in our matrix
  int rows_;

  //! Number of columns in our matrix
  int columns_;

  //! Number of examples in the working set
  int trnSetSize_;

  //! The full data set
  const DataPt * const trnSetPtr_;

  //! The kernel function
  const KernVal(*kernProdFuncPtr_) (const DataPt &pt1, const DataPt &pt2);

  //! Marks which cache rows have been allocated
  mutable BoolVec kernelRowsAllocatedP_;

  //! Marks which cache rows have been fully computed
  mutable BoolVec kernelRowsGeneratedP_;

  //! Maps our rows to their training set positions
  int *rowToTrnSet_;

  //! Maps our columns to their training set positions
  int *colToTrnSet_;
  // NOTE: Equivalent to "workingSet"

  //! Maps the training set examples to their rows
  int *trnSetToRow_;

  //! Maps the training set examples to their columns
  int *trnSetToCol_;
  // NOTE: Equivalent to "workingSetPos"

  //! The cache of kernel values
  mutable KernVal **kernelRows_;

  // statistics
  mutable int kernelComputations_;
};

#endif // SVMFU_SVM_KERN_CACHE_HEADER