svm289_BFS.cpp File Reference

#include "FirstIncludes.h"
#include <ctype.h>
#include <float.h>
#include <fstream>
#include <iostream>
#include <istream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <stdarg.h>
#include <vector>
#include <string.h>
#include "MemoryDebug.h"
#include "KKException.h"
#include "KKStr.h"
#include "OSservices.h"
#include "FeatureVector.h"
#include "svm289_BFS.h"

Go to the source code of this file.

Classes
class	SVM289_BFS::Cache
struct	SVM289_BFS::decision_function
class	SVM289_BFS::Kernel
class	SVM289_BFS::ONE_CLASS_Q
class	SVM289_BFS::QMatrix
class	SVM289_BFS::Solver
struct	SVM289_BFS::Solver::SolutionInfo
class	SVM289_BFS::Solver_NU
class	SVM289_BFS::SVC_Q
class	SVM289_BFS::SVR_Q

Namespaces
	SVM289_BFS
	Namespace used to wrap implementation of libSVM version 2.89 to be used as a pair-wise SVM.

Macros
#define	INF   HUGE_VAL
#define	TAU   1e-12

Functions
template<class T >
T *	SVM289_BFS::GrowAllocation (T *src, kkint32 origSize, kkint32 newSize)
static void	info (const char *fmt,...)
void	SVM289_BFS::multiclass_probability (kkint32 k, double **r, double *p)
double	SVM289_BFS::powi (double base, kkint32 times)
static void	print_string_stdout (const char *s)
double	SVM289_BFS::sigmoid_predict (double decision_value, double A, double B)
void	SVM289_BFS::sigmoid_train (kkint32 l, const double *dec_values, const double *labels, double &A, double &B)
void	SVM289_BFS::solve_c_svc (const svm_problem *prob, const svm_parameter *param, double *alpha, Solver::SolutionInfo *si, double Cp, double Cn, RunLog &_log)
void	SVM289_BFS::solve_epsilon_svr (const svm_problem *prob, const svm_parameter *param, double *alpha, Solver::SolutionInfo *si, RunLog &_log)
void	SVM289_BFS::solve_nu_svc (const svm_problem *prob, const svm_parameter *param, double *alpha, Solver::SolutionInfo *si, RunLog &_log)
static void	solve_nu_svr (const svm_problem *prob, const svm_parameter *param, double *alpha, Solver::SolutionInfo *si, RunLog &_log)
void	SVM289_BFS::solve_one_class (const svm_problem *prob, const svm_parameter *param, double *alpha, Solver::SolutionInfo *si, RunLog &_log)
void	svm_binary_svc_probability (const svm_problem *prob, const svm_parameter *param, double Cp, double Cn, double &probA, double &probB, RunLog &log)
const char *	svm_check_parameter (const svm_problem *prob, const svm_parameter *param)
kkint32	svm_check_probability_model (const svm_model *model)
void	SVM289_BFS::svm_cross_validation (const svm_problem &prob, const svm_parameter &param, kkint32 nr_fold, double *target, RunLog &log)
void	svm_destroy_param (svm_parameter *&param)
void	svm_get_labels (const svm_model *model, kkint32 *label)
SVM_Type	svm_get_svm_type (const svm_model *model)
double	svm_get_svr_probability (const svm_model *model)
void	svm_group_classes (const svm_problem *prob, kkint32 *nr_class_ret, kkint32 **label_ret, kkint32 **start_ret, kkint32 **count_ret, kkint32 *perm)
double	svm_svr_probability (const svm_problem &prob, const svm_parameter &param, RunLog &log)
decision_function	SVM289_BFS::svm_train_one (const svm_problem &prob, const svm_parameter &param, double Cp, double Cn, RunLog &_log)

Macro Definition Documentation

#define INF   HUGE_VAL

Definition at line 109 of file svm289_BFS.cpp.

#define TAU   1e-12

Definition at line 110 of file svm289_BFS.cpp.

Function Documentation

static void info ( const char *  fmt,   ...  )

static

Definition at line 626 of file svm289_BFS.cpp.

Referenced by SVM289_BFS::Solver::do_shrinking(), SVM289_BFS::multiclass_probability(), SVM289_BFS::Solver::reconstruct_gradient(), SVM289_BFS::sigmoid_train(), SVM289_BFS::Solver::Solve(), SVM289_BFS::solve_epsilon_svr(), SVM289_BFS::solve_nu_svc(), solve_nu_svr(), svm_svr_probability(), and SVM289_BFS::svm_train().

{
  char buf[BUFSIZ];
  va_list ap;
  va_start(ap,fmt);

#if  defined(USE_SECURE_FUNCS)
  vsprintf_s(buf, BUFSIZ, fmt, ap);
#else
  vsprintf(buf,fmt,ap);
#endif

  va_end(ap);
  (*SVM289_BFS::svm_print_string)(buf);
}

static void print_string_stdout ( const char *  s )

static

Definition at line 617 of file svm289_BFS.cpp.

{
  fputs(s,stdout);
  fflush(stdout);
}

static void solve_nu_svr ( const svm_problem *  prob, const svm_parameter *  param, double *  alpha, Solver::SolutionInfo *  si, RunLog &  _log  )

static

Definition at line 2709 of file svm289_BFS.cpp.

References SVM289_BFS::svm_parameter::C, SVM289_BFS::svm_parameter::eps, info(), SVM289_BFS::svm_problem::l, SVM289_BFS::svm_parameter::nu, SVM289_BFS::Solver::SolutionInfo::r, SVM289_BFS::svm_parameter::shrinking, SVM289_BFS::Solver_NU::Solve(), SVM289_BFS::SVR_Q::SVR_Q(), and SVM289_BFS::svm_problem::y.

Referenced by SVM289_BFS::svm_train_one().

{
  kkint32  l = prob->l;
  double   C = param->C;

  double*  alpha2      = new double [2 * l];
  double*  linear_term = new double [2 * l];
  schar*   y           = new schar  [2 * l];
  kkint32 i;

  double sum = C * param->nu * l / 2;

  for  (i = 0;  i < l;  i++)
  {
    alpha2[i] = alpha2[i + l] = Min (sum, C);
    sum -= alpha2[i];

    linear_term[i] = - prob->y[i];
    y          [i] = 1;

    linear_term[i + l] = prob->y[i];
    y          [i + l] = -1;
  }


  SVR_Q*  jester = new SVR_Q (*prob, *param, _log);
  Solver_NU  s;
  s.Solve (2 * l, 
           *jester, 
           linear_term, 
           y,
           alpha2, 
           C, 
           C, 
           param->eps, 
           si, 
           param->shrinking
          );
  delete  jester;
  jester = NULL;

  info ("epsilon = %f\n", -si->r);

  for  (i = 0;  i < l;  i++)
    alpha[i] = alpha2[i] - alpha2[i + l];

  delete[] alpha2;
  delete[] linear_term;
  delete[] y;
}  /* solve_nu_svr */

void svm_binary_svc_probability	(	const svm_problem *	prob,
		const svm_parameter *	param,
		double	Cp,
		double	Cn,
		double &	probA,
		double &	probB,
		RunLog &	log
	)

Definition at line 3131 of file svm289_BFS.cpp.

References SVM289_BFS::svm_parameter::C, SVM289_BFS::svm_problem::l, SVM289_BFS::svm_model::label, SVM289_BFS::svm_parameter::nr_weight, SVM289_BFS::svm_parameter::probability, KKMLL::FeatureVectorList::PushOnBack(), SVM289_BFS::svm_problem::selFeatures, SVM289_BFS::sigmoid_train(), SVM289_BFS::svm_problem::svm_problem(), SVM289_BFS::svm_train(), SVM289_BFS::svm_parameter::weight, SVM289_BFS::svm_parameter::weight_label, and SVM289_BFS::svm_problem::y.

Referenced by SVM289_BFS::svm_train().

{
  kkint32 i;
  kkint32  nr_fold = 5;
  kkint32 *perm = new kkint32[prob->l];

  FeatureVectorPtr*  subX    = NULL;
  svm_problem*       subProb = NULL;

  double *dec_values = new double[prob->l];

  // random shuffle
  for  (i = 0;  i < prob->l;  i++) 
    perm[i]=i;
  
  for  (i = 0;  i < prob->l;  i++)
  {
    kkint32 j = i + rand() % (prob->l-i);
    SVM289_BFS::swap (perm[i], perm[j]);
  }
    
  for  (i = 0;  i < nr_fold;  i++)
  {
    kkint32 begin = i * prob->l / nr_fold;
    kkint32 end   = (i + 1) * prob->l / nr_fold;
    kkint32 j, k;

    kkint32  subL = prob->l - (end - begin);
    subX = new FeatureVectorPtr[subL];
    for  (j = 0;  j < subL;  j++)
      subX[j] = NULL;
    float*  subY = new float[subL];

    k = 0;
    for  (j = 0;  j < begin;  j++)
    {
      subX[k] = prob->x.IdxToPtr (perm[j]);
      subY[k] = (float)prob->y[perm[j]];
      ++k;
    }

    for  (j = end;  j < prob->l;  j++)
    {
      subX[k] = prob->x.IdxToPtr (perm[j]);
      subY[k] = (float)prob->y[perm[j]];
      ++k;
    }

    {
      FeatureVectorListPtr  subXX = new FeatureVectorList (prob->x.FileDesc (), false);
      for  (j = 0;  j < k;  j++)
        subXX->PushOnBack (subX[j]);
      subProb = new svm_problem (*subXX, subY, prob->selFeatures);
      delete  subXX;
    }

    kkint32  p_count=0, n_count = 0;

    for  (j = 0;  j < k;  j++)
    {
      if  (subY[j] > 0)
        p_count++;
      else
        n_count++;
    }


    if  ((p_count == 0)  &&  (n_count == 0))
    {
      for  (j = begin;  j < end;  j++)
        dec_values[perm[j]] = 0;
    }

    else if  ((p_count > 0) && (n_count == 0))
    {
      for  (j = begin;  j < end;  j++)
        dec_values[perm[j]] = 1;
    }

    else if  ((p_count == 0)  &&  (n_count > 0))
    {
      for  (j = begin;  j < end;  j++)
        dec_values[perm[j]] = -1;
    }
    
    else
    {
      svm_parameter subparam = *param;
      subparam.probability=0;
      subparam.C=1.0;
      subparam.nr_weight=2;
      subparam.weight_label = new kkint32[2];
      subparam.weight = new double[2];
      subparam.weight_label[0]=+1;
      subparam.weight_label[1]=-1;
      subparam.weight[0]=Cp;
      subparam.weight[1]=Cn;
      svm_model* submodel = svm_train (*subProb, subparam, log);

      for  (j = begin;  j < end;  j++)
      {
        svm_predict_values (submodel, prob->x[perm[j]], &(dec_values[perm[j]])); 
        // ensure +1 -1 order; reason not using CV subroutine
        dec_values[perm[j]] *= submodel->label[0];
      }    

      delete  submodel;  submodel = NULL;
      //svm_destroy_param (&subparam);
    }

    delete  subProb;  subProb = NULL;
    delete  subX;     subX    = NULL;
    delete  subY;     subY    = NULL;
  }    

  sigmoid_train (prob->l, dec_values, prob->y, probA, probB);
  delete  dec_values;  dec_values = NULL;
  delete  perm;        perm       = NULL;
}  /* svm_binary_svc_probability */

const char* svm_check_parameter	(	const svm_problem *	prob,
		const svm_parameter *	param
	)

Definition at line 4672 of file svm289_BFS.cpp.

References SVM289_BFS::svm_parameter::C, SVM289_BFS::C_SVC, SVM289_BFS::svm_parameter::cache_size, SVM289_BFS::svm_parameter::degree, SVM289_BFS::svm_parameter::eps, SVM289_BFS::EPSILON_SVR, SVM289_BFS::svm_parameter::kernel_type, SVM289_BFS::svm_problem::l, SVM289_BFS::LINEAR, SVM289_BFS::svm_parameter::nu, SVM289_BFS::NU_SVC, SVM289_BFS::NU_SVR, SVM289_BFS::ONE_CLASS, SVM289_BFS::svm_parameter::p, SVM289_BFS::POLY, SVM289_BFS::PRECOMPUTED, SVM289_BFS::svm_parameter::probability, SVM289_BFS::RBF, SVM289_BFS::svm_parameter::shrinking, SVM289_BFS::SIGMOID, SVM289_BFS::svm_parameter::svm_type, and SVM289_BFS::svm_problem::y.

{
  // svm_type

  SVM_Type  svm_type = param->svm_type;

  if  (svm_type != SVM_Type::C_SVC        &&
       svm_type != SVM_Type::NU_SVC       &&
       svm_type != SVM_Type::ONE_CLASS    &&
       svm_type != SVM_Type::EPSILON_SVR  &&
       svm_type != SVM_Type::NU_SVR
      )
    return "unknown svm type";
  
  // kernel_type, degree
  
  kkint32  kernel_type = param->kernel_type;

  if  (kernel_type != LINEAR       &&
       kernel_type != POLY         &&
       kernel_type != RBF          &&
       kernel_type != SIGMOID      &&
       kernel_type != PRECOMPUTED
      )
    return "unknown kernel type";

  if  (param->degree < 0)
    return "degree of polynomial kernel < 0";

  // cache_size,eps,C,nu,p,shrinking

  if  (param->cache_size <= 0)
    return "cache_size <= 0";

  if  (param->eps <= 0)
    return "eps <= 0";

  if  (svm_type == SVM_Type::C_SVC       ||
       svm_type == SVM_Type::EPSILON_SVR ||
       svm_type == SVM_Type::NU_SVR
      )
    if  (param->C <= 0)
      return "C <= 0";

  if  (svm_type == SVM_Type::NU_SVC     ||
       svm_type == SVM_Type::ONE_CLASS  ||
       svm_type == SVM_Type::NU_SVR
      )
    if  ((param->nu <= 0) || (param->nu > 1))
      return "nu <= 0 or nu > 1";

  if  (svm_type == SVM_Type::EPSILON_SVR)
  {
    if  (param->p < 0)
      return "p < 0";
  }

  if  (param->shrinking != 0 &&  param->shrinking != 1)
    return "shrinking != 0 and shrinking != 1";

  if  ((param->probability != 0)  &&  (param->probability != 1))
    return "probability != 0 and probability != 1";

  if  ((param->probability == 1)  &&  (svm_type == SVM_Type::ONE_CLASS))
    return "one-class SVM probability output not supported yet";


  // check whether nu-svc is feasible
  
  if  (svm_type == SVM_Type::NU_SVC)
  {
    kkint32 l = prob->l;
    kkint32 max_nr_class = 16;
    kkint32 nr_class = 0;
    kkint32*  label = new kkint32[max_nr_class];
    kkint32*  count = new kkint32[max_nr_class];

    kkint32 i;
    for  (i = 0;  i < l;  i++)
    {
      kkint32 this_label = (kkint32)prob->y[i];
      kkint32  j;
      for  (j = 0;  j < nr_class;  j++)
      {
        if  (this_label == label[j])
        {
          ++count[j];
          break;
        }
      }

      if  (j == nr_class)
      {
        if  (nr_class == max_nr_class)
        {
          kkint32  oldMaxNrClass = max_nr_class;
          max_nr_class *= 2;
          label = GrowAllocation (label, oldMaxNrClass, max_nr_class);
          count = GrowAllocation (count, oldMaxNrClass, max_nr_class);
        }
        label[nr_class] = this_label;
        count[nr_class] = 1;
        ++nr_class;
      }
    }
  

    for  (i = 0;  i < nr_class;  i++)
    {
      kkint32  n1 = count[i];
      for  (kkint32 j = i + 1;  j < nr_class;  j++)
      {
        kkint32 n2 = count[j];
        if  ((param->nu * (n1 + n2) / 2) > Min (n1, n2))
        {
          delete[]  label;  label = NULL;
          delete[]  count;  count = NULL;
          return "specified nu is infeasible";
        }
      }
    }

    delete[]  label;  label = NULL;
    delete[]  count;  count = NULL;
  }

  return NULL;
}  /* svm_check_parameter */

kkint32 svm_check_probability_model

(

const svm_model *

model

)

Definition at line 4806 of file svm289_BFS.cpp.

References SVM289_BFS::C_SVC, SVM289_BFS::EPSILON_SVR, SVM289_BFS::NU_SVC, SVM289_BFS::NU_SVR, SVM289_BFS::svm_model::param, SVM289_BFS::svm_model::probA, SVM289_BFS::svm_model::probB, and SVM289_BFS::svm_parameter::svm_type.

{
  return ((model->param.svm_type == SVM_Type::C_SVC       ||  model->param.svm_type == SVM_Type::NU_SVC) &&  model->probA!=NULL && model->probB!=NULL) ||
         ((model->param.svm_type == SVM_Type::EPSILON_SVR ||  model->param.svm_type == SVM_Type::NU_SVR) &&  model->probA!=NULL);
}

void svm_destroy_param

(

svm_parameter *&

param

)

Definition at line 4664 of file svm289_BFS.cpp.

{
  delete  param;
  param = NULL;
}

void svm_get_labels	(	const svm_model *	model,
		kkint32 *	label
	)

Definition at line 3869 of file svm289_BFS.cpp.

References SVM289_BFS::svm_model::label, and SVM289_BFS::svm_model::nr_class.

{
  if (model->label != NULL)
    for(kkint32 i=0;i<model->nr_class;i++)
      label[i] = model->label[i];
}

SVM_Type svm_get_svm_type

(

const svm_model *

model

)

Definition at line 3854 of file svm289_BFS.cpp.

References SVM289_BFS::svm_model::param, and SVM289_BFS::svm_parameter::svm_type.

{
  return model->param.svm_type;
}

double svm_get_svr_probability

(

const svm_model *

model

)

Definition at line 3880 of file svm289_BFS.cpp.

References SVM289_BFS::EPSILON_SVR, SVM289_BFS::NU_SVR, SVM289_BFS::svm_model::param, SVM289_BFS::svm_model::probA, and SVM289_BFS::svm_parameter::svm_type.

{
  if ((model->param.svm_type == SVM_Type::EPSILON_SVR || model->param.svm_type == SVM_Type::NU_SVR) &&
      model->probA!=NULL)
    return model->probA[0];
  else
  {
    fprintf(stderr,"Model doesn't contain information for SVR probability inference\n");
    return 0;
  }
}

void svm_group_classes	(	const svm_problem *	prob,
		kkint32 *	nr_class_ret,
		kkint32 **	label_ret,
		kkint32 **	start_ret,
		kkint32 **	count_ret,
		kkint32 *	perm
	)

Definition at line 3310 of file svm289_BFS.cpp.

References SVM289_BFS::svm_problem::l, and SVM289_BFS::svm_problem::y.

Referenced by SVM289_BFS::svm_cross_validation(), and SVM289_BFS::svm_train().

{
  kkint32 l = prob->l;
  kkint32 max_nr_class = 16;
  kkint32 nr_class = 0;
  kkint32 *label      = new kkint32[max_nr_class];
  kkint32 *count      = new kkint32[max_nr_class];
  kkint32 *data_label = new kkint32[l];
  kkint32 i;

  // Count number of examples in each class
  for  (i = 0;  i < l;  i++)
  {
    kkint32 this_label = (kkint32)prob->y[i];
    kkint32 j;
    for  (j = 0;  j < nr_class;  j++)
    {
      if  (this_label == label[j])
      {
        ++count[j];
        break;
      }
    }

    data_label[i] = j;
    if  (j == nr_class)
    {
      // We have a new class
      if  (nr_class == max_nr_class)
      {
        kkint32  newMaxNumClass = max_nr_class * 2;
        label = GrowAllocation (label, max_nr_class, newMaxNumClass);
        count = GrowAllocation (count, max_nr_class, newMaxNumClass);
        max_nr_class = newMaxNumClass;
      }
      label[nr_class] = this_label;
      count[nr_class] = 1;
      ++nr_class;
    }
  }

  kkint32 *start = new kkint32[nr_class];
  start[0] = 0;
  for  (i = 1;  i < nr_class;  i++)
    start[i] = start[i - 1] + count[i - 1];

  for  (i = 0;  i < l;  i++)
  {
    perm[start[data_label[i]]] = i;
    ++start[data_label[i]];
  }

  start[0] = 0;
  for  (i = 1;  i < nr_class;  i++)
    start[i] = start[i - 1] + count[i - 1];

  *nr_class_ret = nr_class;
  *label_ret = label;
  *start_ret = start;
  *count_ret = count;
  delete  data_label;  data_label = NULL;
}  /* svm_group_classes*/

double svm_svr_probability	(	const svm_problem &	prob,
		const svm_parameter &	param,
		RunLog &	log
	)

Definition at line 3265 of file svm289_BFS.cpp.

References info(), SVM289_BFS::svm_problem::l, SVM289_BFS::svm_parameter::probability, SVM289_BFS::svm_cross_validation(), and SVM289_BFS::svm_problem::y.

Referenced by SVM289_BFS::svm_train().

{
  kkint32 i;
  kkint32 nr_fold = 5;
  double *ymv = new double[prob.l];
  double mae = 0;

  svm_parameter  newparam = param;
  newparam.probability = 0;
  svm_cross_validation (prob, newparam, nr_fold, ymv, log);

  for  (i = 0;  i < prob.l;  i++)
  {
    ymv[i] = prob.y[i] - ymv[i];
    mae += fabs (ymv[i]);
  }    

  mae /= prob.l;
  double  std = sqrt (2 * mae * mae);
  kkint32 count = 0;
  mae = 0;
  for  (i = 0;  i < prob.l;  i++)
  {
    if  (fabs(ymv[i]) > (5 * std)) 
      count = count + 1;
    else 
      mae += fabs (ymv[i]);
  }

  mae /= (prob.l - count);
  
  info("Prob. model for test data: target value = predicted value + z,\nz: Laplace distribution e^(-|z|/sigma)/(2sigma),sigma= %g\n", mae);
  delete  ymv;  ymv = NULL;
  return mae;
}  /* svm_svr_probability */