svmfusvmkerncache.cpp

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

using namespace std;

#include <stdio.h>
#include <iostream>
#include <fstream>

#include "SvmFuSvmKernCache.h"

// for set_difference
#include <algorithm>

#ifdef CallTemplate
#undef CallTemplate
#endif

#define CallTemplate(rettype, funcname) \
template<class DataPt, class KernVal> \
rettype SvmKernCache<DataPt, KernVal>::funcname

#ifdef InlineTemplate
#undef InlineTemplate
#endif

#define InlineTemplate(rettype, funcname) \
template<class DataPt, class KernVal> \
rettype SvmKernCache<DataPt, KernVal>::funcname

/*! \class SvmKernCache
 *
 * New design by [e-mail], spring 2001.
 *
 * Maintains a row and column for each point in the working set,
 * plus a configurable number of extra rows which are assigned
 * to the most violating points from outside the working set.
 * All kernel computations are now done internally on demand.
 * Kernel product access functions are available for working set
 * indices and training set indices.
 *
 * Original rif comments:
 * 
 * It's designed to be passed and forth between SmallOpt and 
 * LargeOpt.  There is some redundancy here (both the Svm and the
 * KernCache store the trnSetPtr and the kernProdFuncPtr, sadly; this
 * could potentially lead to hard-to-find bugs later)

 * Even though it is redundant, we store full rows.  We could save half
 * the space by storing in an upper triangular form, but then we would
 * take longer and have to copy to provide entire rows, which is the most 
 * common operation.
 *
 * Index arguments to functions are into the full training set,
 * not the working set. Mappings from working set indices to
 * training set indices are left to using code.
 */

template<class DataPt, class KernVal>
SvmKernCache<DataPt, KernVal>::SvmKernCache
(int workingSetSize,
 int extraRows,
 int trnSetSize,
 const DataPt * const trnSetPtr,
 const KernVal (*kernProdFuncPtr)(const DataPt &,
				  const DataPt &))
  : columns_(workingSetSize), rows_(workingSetSize + extraRows),
    trnSetSize_(trnSetSize), trnSetPtr_(trnSetPtr),
    kernProdFuncPtr_(kernProdFuncPtr)
{ 
  if (rows_ > trnSetSize_) rows_ = trnSetSize_;

  kernelRows_ = new KernVal *[rows_];
  kernelRowsGeneratedP_ = new bool[rows_];
  kernelRowsAllocatedP_ = new bool[rows_];
  
  colToTrnSet_ = new int[columns_];
  rowToTrnSet_ = new int[rows_];

  trnSetToRow_ = new int[trnSetSize_];
  trnSetToCol_ = new int[trnSetSize_];

  for (int i = 0; i < columns_; i++)
  {
    colToTrnSet_[i] = -1;
  }
  
  for (int i = 0; i < rows_; i++) {
    rowToTrnSet_[i] = -1;
    kernelRowsGeneratedP_[i] = false;
    kernelRowsAllocatedP_[i] = false;
  }
  
  for (int i = 0; i < trnSetSize_; i++)
  {
    trnSetToRow_[i] = -1;
    trnSetToCol_[i] = -1;
  }

  kernelComputations_ = 0;
  readFromFile_ = false;
}
  
template<class DataPt, class KernVal>
SvmKernCache<DataPt, KernVal>::~SvmKernCache() {
  int rA = 0;

  for (int i = 0; i < rows_; i++) {
    if (kernelRowsAllocatedP_[i]) {
      rA++;
      delete[] kernelRows_[i];
    }
  }

  cout << "ROWS ALLOCATED: " << rA << endl;
  cout << "KERNEL COMPUTATIONS: " << kernelComputations_ << endl;

  delete[] kernelRows_;
  delete[] kernelRowsGeneratedP_;
  delete[] kernelRowsAllocatedP_;

  delete[] rowToTrnSet_;
  delete[] colToTrnSet_;
  delete[] trnSetToRow_;
  delete[] trnSetToCol_;
}

/*! \fn SvmKernCache<DataPt, KernVal>::workingSetChanged (int *, set<QueueElt_)
 *
 * Assign a column to each point specified by workingSetIndices
 * and an extra row to as many of the points from the top of
 * others as space allows.
 *
 * Algorithm: use the new working set array as our column assignments.
 * Then compute the set of points to add to rows and the set of points
 * to remove from rows by subtracting the new set of points we want to
 * assign rows from the points that are currently assigned to rows,
 * and swap the two sets pairwise.
 *
 */
template<class DataPt, class KernVal> void
SvmKernCache<DataPt, KernVal>::workingSetChanged
(const int * const workingSet,
 const priority_queue<QueueElt_> &others)
{
  // copy non-working-set queue
  priority_queue<QueueElt_> nonWorkingSet = others;

  // for rows and columns
  set<int> pointsToCache;
  set<int> currentlyCachedPoints;

  // for rows
  list<int> pointsToRemoveFromRows;
  list<int> pointsToAddToRows;
  list<int> availableRows;

  // for columns
  list<int> pointsToRemoveFromCols;
  list<int> pointsToAddToCols;
  list<int> availableCols;

  //////////////////////////////
  // update column assignments
  //////////////////////////////

  // we assign columns in the same order as the working set,
  // because it's guaranteed to be an optimal assignment,
  // and because it lets us pass out pointers to cache rows
  // which are in the same order as the working set.

  list<int> reassignedCols;
  for (int i = 0; i < columns_; i++)
    {
      // remember which columns changed, adjust mappings
      if (colToTrnSet_[i] != workingSet[i]) {
	reassignedCols.push_back(i);
	if (colToTrnSet_[i] != -1) {
	  trnSetToCol_[colToTrnSet_[i]] = -1;
	}

	colToTrnSet_[i] = workingSet[i];
	trnSetToCol_[workingSet[i]] = i;
      }
    }
  
  // invalidate the columns row-wise to help linearity of reference
  if (!readFromFile_) {
    for (int cacheRow = 0; cacheRow < rows_; cacheRow++)
      {
	kernelRowsGeneratedP_[cacheRow] = false; // sadly...

	if (kernelRowsAllocatedP_[cacheRow])
	  {
	    for (list<int>::iterator it = reassignedCols.begin();
		 it != reassignedCols.end(); it++)
	      {
		invalidateCell(cacheRow, *it);
	      }
	  }
      }
  }
  ///////////////////////////
  // update row assignments
  ///////////////////////////
    
  // collect points from the new working set
  for (int i = 0; i < columns_; i++)
    {
      pointsToCache.insert(workingSet[i]);
    }

  // collect sets from our row mapping
  for (int i = 0; i < rows_; i++)
    {
      if (rowToTrnSet_[i] != -1) {
	currentlyCachedPoints.insert(rowToTrnSet_[i]);
      } else {
	availableRows.push_back(i);
      }
    }

  // gather enough points off the queue to fill up our extra rows
  int nws_size = nonWorkingSet.size();
  for (int i = 0; (i < rows_ - columns_) && (i < nws_size); i++)
    {
      pointsToCache.insert(nonWorkingSet.top().elt_);
      nonWorkingSet.pop();
    }
  
  // compute their differences
  set_difference(currentlyCachedPoints.begin(),
		 currentlyCachedPoints.end(),
		 pointsToCache.begin(),
		 pointsToCache.end(),
		 inserter(pointsToRemoveFromRows,
			  pointsToRemoveFromRows.begin()));
  
  set_difference(pointsToCache.begin(),
		 pointsToCache.end(),
		 currentlyCachedPoints.begin(),
		 currentlyCachedPoints.end(),
		 inserter(pointsToAddToRows,
			  pointsToAddToRows.begin()));
  
  // for each point to add, either swap it with the next point
  // to remove, or assign it to an empty row
  list<int>::iterator pointToRemove = pointsToRemoveFromRows.begin();
  list<int>::iterator emptyRow = availableRows.begin();
  for (list<int>::iterator it = pointsToAddToRows.begin();
       it != pointsToAddToRows.end(); it++) {
    int trnSetPtToAdd = *it;
    int destRow;
    
    if (pointToRemove != pointsToRemoveFromRows.end())
      {
	int trnSetIndex = *pointToRemove;
	pointToRemove++;
	destRow = trnSetToRow_[trnSetIndex];
	
	// purge obsolete point from map
	trnSetToRow_[trnSetIndex] = -1;
      }
    else
      {
	destRow = *emptyRow;
	emptyRow++;
      }
    
    // update our mappings
    rowToTrnSet_[destRow] = trnSetPtToAdd;
    trnSetToRow_[trnSetPtToAdd] = destRow;
    
    // mark the row as invalid
    if (kernelRowsAllocatedP_[destRow] && !readFromFile_)
      {
	for (int i = 0; i < columns_; i++)
	  {
	    invalidateCell(destRow, i);
	  }
      }
  }
}

CallTemplate(void, saveToFile)(char *fileName)
{