svmfusvmkerncache.cpp

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

  int i, j;

  cout << "Saving kernelmatrix to " << fileName << ": " << endl;

  cout << "\tGenerating missing rows." << endl;
  for (i = 0; i < rows_; i++) {
    cachedKernProdRowPtr(i); // Called for side effects
  }

  cout << "\tWriting " << fileName << "." << endl;
  ofstream os;
  os.open(fileName, ios::out);
  if (!os) {
    cerr << "Error: Cannot open " << fileName << " for writing." << endl;
    exit(1);
    }

  os << rows_ << endl;
  for (i = 0; i < rows_; i++) {
    KernVal *kprp = cachedKernProdRowPtr(i); 
    for (j = 0; j < rows_; j++) {
      os << kprp[j] << " ";
    }
    os << endl;
  }

  os.close();
}

CallTemplate(void, readFromFile)(char *fileName)
{
  ifstream is;
  is.open(fileName, ios::in);
  if (!is) { 
    cerr << "Error: Cannot open " << fileName << " for reading." << endl;
    exit(1);
  }
  int rows, columns;
  is >> rows >> columns;
  int i, j;

  for (i = 0; i < rows; i++) {
    // generate the row if necessary
    if (! kernelRowsGeneratedP_[i]) {
      if (! kernelRowsAllocatedP_[i]) {
	initializeRow(i);
      }
    }
      
    for (j = 0; j < columns; j++) {
      is >> kernelRows_[i][j];
    }

    kernelRowsGeneratedP_[i] = true;
    colToTrnSet_[i] = i;
    trnSetToCol_[i] = i;
  }

  is.close();
  cout << "Read kernCache from " << fileName << "." << endl;
  readFromFile_ = true;
}

CallTemplate(int, getColToTrnSet)(int ex) const
{
  if ((ex < 0) || (ex >= columns_)) { 
    cerr << "Error: example " << ex << " out of range (0-" <<
      columns_ << ") for getColToTrnSet" << endl;
    exit(-1);
  }
      
  return colToTrnSet_[ex];
}

CallTemplate(int, getTrnSetToCol)(int ex) const
{
  if ((ex < 0) || (ex >= trnSetSize_)) { 
    cerr << "Error: example " << ex << " out of range (0-" <<
      trnSetSize_ << ") for getTrnSetToCol" << endl;
    exit(-1);
  }
      
  return trnSetToCol_[ex];
}

CallTemplate(int, getTrnSetToRow)(int ex) const
{
  if ((ex < 0) || (ex >= trnSetSize_)) { 
    cerr << "Error: example " << ex << " out of range (0-" <<
      trnSetSize_ << ") for getTrnSetToRow" << endl;
    exit(-1);
  }
      
  return trnSetToRow_[ex];
}

/*! \fn SvmKernCache::cachedKernProd (int ex1, int ex2)
 *
 * Get the kernel value for a pair of indices into the working set;
 * we are guaranteed to have cells for both (ex1, ex2) and (ex2, ex1)
 *
 */
CallTemplate(KernVal, cachedKernProd) (int ex1, int ex2) const
{
  // coordinates of the two points in our cache
  int cacheRow, cacheCol, cacheRow2, cacheCol2, tex1, tex2;

  tex1 = colToTrnSet_[ex1];
  tex2 = colToTrnSet_[ex2];

  cacheRow = trnSetToRow_[tex1];
  cacheCol = trnSetToCol_[tex2];
  
  cacheRow2 = trnSetToRow_[tex2];
  cacheCol2 = trnSetToCol_[tex1];

  KernVal kernProd;
  if (kernelRowsAllocatedP_[cacheRow] && cellValid(cacheRow, cacheCol)) {
    kernProd = kernelRows_[cacheRow][cacheCol];
  } else {
    if (kernelRowsAllocatedP_[cacheRow2] && cellValid(cacheRow2, cacheCol2)) {
      kernProd = kernelRows_[cacheRow2][cacheCol2];
    } else {
      kernProd = kernProdFuncPtr_(trnSetPtr_[tex1], trnSetPtr_[tex2]);
      kernelComputations_++;
    }
  }
  
  return kernProd;
}

/*! \fn SvmKernCache::cachedKernProdRowPtr (int ex)
 *
 * Get a pointer to an array of KernVals corresponding to the point's
 * kernel function with the rest of the points in the working set.
 *
 */
CallTemplate(KernVal *, cachedKernProdRowPtr) (int ex) const
{
  int trnSetPt = colToTrnSet_[ex];
  int cacheRow = trnSetToRow_[trnSetPt];  

  // generate the row if necessary
  if (! kernelRowsGeneratedP_[cacheRow]) {
    if (! kernelRowsAllocatedP_[cacheRow]) {
      initializeRow(cacheRow);
    }

    for (int cacheCol = 0; cacheCol < columns_; cacheCol++) {
      // share with symmetric point      
      KernVal kernProd;
      
      if (!cellValid(cacheRow, cacheCol)) {
	int row = trnSetToRow_[colToTrnSet_[cacheCol]];

	if (kernelRowsAllocatedP_[row] && cellValid(row, ex)) {
	  kernProd = kernelRows_[row][ex];
	} else {
	  kernProd = kernProdFuncPtr_(trnSetPtr_[trnSetPt],
				      trnSetPtr_[colToTrnSet_[cacheCol]]);
	  kernelComputations_++;       
	}
	kernelRows_[cacheRow][cacheCol] = kernProd;
      }      
    }
    kernelRowsGeneratedP_[cacheRow] = true;
  }
  
  return kernelRows_[cacheRow];
}

/*! \fn SvmKernCache::trnSetKernProd (int ex1, int ex2)
 *
 * Get the kernel value for a pair of indices into the training set;
 * we may have cache cells for both, one, or neither of (ex1, ex2) and (ex2, ex1)
 *
 */
CallTemplate(KernVal, trnSetKernProd) (int ex1, int ex2) const
{
  // coordinates of the two points in our cache
  int cacheRow, cacheCol, cacheRow2, cacheCol2;
  cacheRow = cacheCol = cacheRow2 = cacheCol2 = -1;

  // find the cell coordinates, if they exist
  if (trnSetToRow_[ex1] != -1 && trnSetToCol_[ex2] != -1)
  {
    cacheRow = trnSetToRow_[ex1];
    cacheCol = trnSetToCol_[ex2];
  }
  if (trnSetToRow_[ex2] != -1 && trnSetToCol_[ex1] != -1)
  {
    cacheRow2 = trnSetToRow_[ex2];
    cacheCol2 = trnSetToCol_[ex1];
  }
 
  KernVal kernProd;

  // use a cached value if it's in the cache and available;
  // else if it's allocated but not computed, compute it and share
  // it symmetrically if possible.
  if (cacheRow >= 0 && cacheCol >= 0)
  {
    if (! kernelRowsAllocatedP_[cacheRow])
      initializeRow(cacheRow);
    
    if (cellValid(cacheRow, cacheCol))
    {
      kernProd = kernelRows_[cacheRow][cacheCol];
    }
    else
    {
      kernProd = kernProdFuncPtr_(trnSetPtr_[ex1],
				  trnSetPtr_[ex2]);
      kernelRows_[cacheRow][cacheCol] = kernProd;
      
      kernelComputations_++; 

      // copy it to symmetrical cell if it exists
      if (cacheRow2 >= 0 && cacheCol2 >= 0)
      {
	if (! kernelRowsAllocatedP_[cacheRow2])
	  initializeRow(cacheRow2);
	kernelRows_[cacheRow2][cacheCol2] = kernProd;
      }
    }
  }
  else if (cacheRow2 >= 0 && cacheCol2 >= 0)
  {
    if (! kernelRowsAllocatedP_[cacheRow2])
      initializeRow(cacheRow2);

    if (cellValid(cacheRow2, cacheCol2))
    {
      kernProd = kernelRows_[cacheRow2][cacheCol2];

    }
    else
    {
      kernProd = kernProdFuncPtr_(trnSetPtr_[ex1],
				  trnSetPtr_[ex2]);
      kernelRows_[cacheRow2][cacheCol2] = kernProd;

      kernelComputations_++; 
    }
  }
  else // nowhere to cache it =(
  {
    kernProd = kernProdFuncPtr_(trnSetPtr_[ex1],
				trnSetPtr_[ex2]);

    kernelComputations_++; 
  }

  return kernProd;
}

/*! \fn void SvmKernCache::invalidateCell(int, int)
 *
 * Set a flag indicating that the specified cell is invalid.
 * 
 * Currently this stores a -1 in the cell. This should probably be
 * a per-kernel value, however.
 *
 */
CallTemplate(void, invalidateCell)
  (int row, int col) const
{
  kernelRows_[row][col] = -1;
}


/*! \fn bool SvmKernCache::cellValid(int, int)
 *
 * Returns whether the specified value is valid or not.
 * 
 */
CallTemplate(bool, cellValid)
  (int row, int col) const
{
  return kernelRows_[row][col] != -1;
}

/*! \fn void SvmKernCache::initializeRow (int)
 *
 * Allocates the row, updates metadata, and invalidates each cell.
 *
 */
CallTemplate (void, initializeRow) (int row) const
{
  kernelRows_[row] = new KernVal[columns_];
  
  kernelRowsAllocatedP_[row] = true;
  for (int i = 0; i < columns_; i++)
    invalidateCell(row, i);
}


#include "SvmFuSvmDataPoint.h"
#define IterateTypes(datatype, kerntype) \
    template class SvmKernCache<DataPoint<datatype>, kerntype>;
#include "SvmFuSvmTypes.h"