SVM289_BFS::Solver Class Reference

Inheritance diagram for SVM289_BFS::Solver:

Classes
struct	SolutionInfo

Public Member Functions
	Solver ()
virtual	~Solver ()
void	Solve (kkint32 l, QMatrix &Q, const double *p_, const schar *y_, double *alpha_, double Cp, double Cn, double eps, SolutionInfo *si, kkint32 shrinking)

Protected Types
enum	{ LOWER_BOUND, UPPER_BOUND, FREE }

Protected Member Functions
virtual double	calculate_rho ()
virtual void	do_shrinking ()
double	get_C (kkint32 i)
bool	is_free (kkint32 i)
bool	is_lower_bound (kkint32 i)
bool	is_upper_bound (kkint32 i)
void	reconstruct_gradient ()
virtual kkint32	select_working_set (kkint32 &i, kkint32 &j)
void	swap_index (kkint32 i, kkint32 j)
void	update_alpha_status (kkint32 i)

Protected Attributes
kkint32 *	active_set
kkint32	active_size
double *	alpha
char *	alpha_status
double	Cn
double	Cp
double	eps
double *	G
double *	G_bar
kkint32	l
double *	p
QMatrix *	Q
const Qfloat *	QD
bool	unshrink
schar *	y

Detailed Description

Definition at line 1163 of file svm289_BFS.cpp.

Member Enumeration Documentation

anonymous enum

protected

Enumerator
LOWER_BOUND
UPPER_BOUND
FREE

Definition at line 1192 of file svm289_BFS.cpp.

{LOWER_BOUND, UPPER_BOUND, FREE};

Constructor & Destructor Documentation

SVM289_BFS::Solver::Solver ( )

inline

Definition at line 1165 of file svm289_BFS.cpp.

{};

virtual SVM289_BFS::Solver::~Solver ( )

inlinevirtual

Definition at line 1166 of file svm289_BFS.cpp.

{};

Member Function Documentation

double SVM289_BFS::Solver::calculate_rho ( )

protectedvirtual

Definition at line 1825 of file svm289_BFS.cpp.

References active_size, G, is_lower_bound(), is_upper_bound(), and y.

Referenced by Solve().

{
  double  r;
  kkint32 nr_free  = 0;
  double  ub       = INF;
  double  lb       = -INF;
  double  sum_free = 0;

  for  (kkint32 i = 0;  i < active_size;  i++)
  {
    double yG = y[i] * G[i];

    if  (is_upper_bound(i))
    {
      if  (y[i] == -1)
        ub = Min (ub, yG);
      else
        lb = Max (lb, yG);
    }

    else if  (is_lower_bound(i))
    {
      if  (y[i] == +1)
        ub = Min (ub,yG);
      else
        lb = Max (lb,yG);
    }
    else
    {
      ++nr_free;
      sum_free += yG;
    }
  }

  if  (nr_free > 0)
    r = sum_free / nr_free;
  else
    r = (ub + lb) / 2;

  return r;
}  /* calculate_rho */

void Solver::do_shrinking ( )

protectedvirtual

Definition at line 1757 of file svm289_BFS.cpp.

References active_size, eps, G, info(), is_lower_bound(), is_upper_bound(), l, reconstruct_gradient(), swap_index(), unshrink, and y.

Referenced by Solve().

{
  kkint32 i;
  double  Gmax1 = -INF;    // Max { -y_i * grad(f)_i | i in I_up(\alpha) }
  double  Gmax2 = -INF;    // Max { y_i * grad(f)_i | i in I_low(\alpha) }

  // find maximal violating pair first
  for  (i = 0;  i < active_size;  i++)
  {
    if  (y[i] == +1)
    {
      if  (!is_upper_bound (i))  
      {
        if  (-G[i] >= Gmax1)
          Gmax1 = -G[i];
      }
      if  (!is_lower_bound (i))  
      {
        if  (G[i] >= Gmax2)
          Gmax2 = G[i];
      }
    }

    else  
    {
      if  (!is_upper_bound (i))
      {
        if  (-G[i] >= Gmax2)
          Gmax2 = -G[i];
      }

      if  (!is_lower_bound (i))
      {
        if  (G[i] >= Gmax1)
          Gmax1 = G[i];
      }
    }
  }

  if  ((unshrink == false) && ((Gmax1 + Gmax2) <= (eps * 10)))
  {
    unshrink = true;
    reconstruct_gradient();
    active_size = l;
    info ("*");
  }

  for  (i = 0;  i < active_size;  i++)
  {
    if  (be_shrunk(i, Gmax1, Gmax2))
    {
      active_size--;
      while  (active_size > i)
      {
        if  (!be_shrunk (active_size, Gmax1, Gmax2))
        {
          swap_index (i, active_size);
          break;
        }
        active_size--;
      }
    }
  }
}  /* do_shrinking */

double SVM289_BFS::Solver::get_C ( kkint32  i )

inlineprotected

Definition at line 1207 of file svm289_BFS.cpp.

References Cn, Cp, and y.

Referenced by Solve(), and update_alpha_status().

  {
    return (y[i] > 0) ? Cp : Cn;
  }

bool SVM289_BFS::Solver::is_free ( kkint32  i )

inlineprotected

Definition at line 1227 of file svm289_BFS.cpp.

References alpha_status, and FREE.

Referenced by reconstruct_gradient().

{return alpha_status[i] == FREE;}

bool SVM289_BFS::Solver::is_lower_bound ( kkint32  i )

inlineprotected

Definition at line 1226 of file svm289_BFS.cpp.

References alpha_status, and LOWER_BOUND.

Referenced by calculate_rho(), do_shrinking(), select_working_set(), and Solve().

{return alpha_status[i] == LOWER_BOUND;}

bool SVM289_BFS::Solver::is_upper_bound ( kkint32  i )

inlineprotected

Definition at line 1225 of file svm289_BFS.cpp.

References alpha_status, and UPPER_BOUND.

Referenced by calculate_rho(), do_shrinking(), select_working_set(), and Solve().

{return alpha_status[i] == UPPER_BOUND;}

void SVM289_BFS::Solver::reconstruct_gradient ( )

protected

Definition at line 1264 of file svm289_BFS.cpp.

References active_size, alpha, G, G_bar, SVM289_BFS::QMatrix::get_Q(), info(), is_free(), l, p, and Q.

Referenced by do_shrinking(), and Solve().

{
  // reconstruct inactive elements of G from G_bar and free variables

  if  (active_size == l) 
    return;

  kkint32 i,j;
  kkint32 nr_free = 0;

  for  (j = active_size;  j < l;  j++)
    G[j] = G_bar[j] + p[j];

  for  (j = 0;  j < active_size;  j++)
  {
    if  (is_free(j))
      nr_free++;
  }

  if  (2 * nr_free < active_size)
    info("\nWarning: using -h 0 may be faster\n");

  if  (nr_free*l > 2 * active_size * (l - active_size))
  {
    for  (i = active_size;  i < l;  i++)
    {
      Qfloat *Q_i = Q->get_Q (i, active_size);
      for  (j = 0;  j < active_size;  j++)
      {
        if  (is_free (j))
          G[i] += alpha[j] * Q_i[j];
      }
    }
  }
  else
  {
    for  (i = 0;  i < active_size;  i++)
    {
      if  (is_free (i))
      {
        Qfloat*  Q_i = Q->get_Q (i,l);
        double alpha_i = alpha[i];
        for  (j = active_size;  j < l;  j++)
          G[j] += alpha_i * Q_i[j];
      }
    }
  }
}  /* reconstruct_gradient */

kkint32 SVM289_BFS::Solver::select_working_set ( kkint32 &  i, kkint32 &  j  )

protectedvirtual

Definition at line 1616 of file svm289_BFS.cpp.

References active_size, eps, G, SVM289_BFS::QMatrix::get_Q(), is_lower_bound(), is_upper_bound(), Q, QD, and y.

Referenced by Solve().

{
  // return i,j such that
  // i: maximizes -y_i * grad(f)_i, i in I_up(\alpha)
  // j: minimizes the decrease of obj value
  //    (if quadratic coefficient <= 0, replace it with tau)
  //    -y_j*grad(f)_j < -y_i*grad(f)_i, j in I_low(\alpha)
  
  double  Gmax         = -INF;
  double  Gmax2        = -INF;
  kkint32 Gmax_idx     = -1;
  kkint32 Gmin_idx     = -1;
  double  obj_diff_min = INF;

  for  (kkint32 t=0;t<active_size;t++)
  {
    if  (y[t] == +1)
    {
      if  (!is_upper_bound (t))
      {
        if  (-G[t] >= Gmax)
        {
          Gmax     = -G[t];
          Gmax_idx = t;
        }
      }
    }
    else
    {
      if  (!is_lower_bound (t))
      {
        if  (G[t] >= Gmax)
        {
          Gmax = G[t];
          Gmax_idx = t;
        }
      }
    }
  }


  kkint32 i = Gmax_idx;
  const Qfloat *Q_i = NULL;
  if  (i != -1) // NULL Q_i not accessed: Gmax=-INF if i=-1
    Q_i = Q->get_Q(i,active_size);

  for(kkint32 j=0;j<active_size;j++)
  {
    if(y[j]==+1)
    {
      if (!is_lower_bound(j))
      {
        double grad_diff=Gmax+G[j];
        if (G[j] >= Gmax2)
          Gmax2 = G[j];

        if  (grad_diff > 0)
        {
          double obj_diff; 
          double quad_coef = Q_i[i] + QD[j] - 2.0 * y[i] * Q_i[j];

          if  (quad_coef > 0)
            obj_diff = -(grad_diff*grad_diff)/quad_coef;
          else
            obj_diff = -(grad_diff*grad_diff)/TAU;

          if  (obj_diff <= obj_diff_min)
          {
            Gmin_idx=j;
            obj_diff_min = obj_diff;
          }
        }
      }
    }
    else
    {
      if  (!is_upper_bound(j))
      {
        double grad_diff= Gmax-G[j];
        if (-G[j] >= Gmax2)
          Gmax2 = -G[j];
        if (grad_diff > 0)
        {
          double obj_diff; 
          double quad_coef=Q_i[i]+QD[j]+2.0*y[i]*Q_i[j];
          if (quad_coef > 0)
            obj_diff = -(grad_diff*grad_diff)/quad_coef;
          else
            obj_diff = -(grad_diff*grad_diff)/TAU;

          if (obj_diff <= obj_diff_min)
          {
            Gmin_idx=j;
            obj_diff_min = obj_diff;
          }
        }
      }
    }
  }

  if  (Gmax + Gmax2  <  eps)
    return 1;

  out_i = Gmax_idx;
  out_j = Gmin_idx;
  return 0;
}  /* select_working_set */

void SVM289_BFS::Solver::Solve	(	kkint32	l,
		QMatrix &	Q,
		const double *	p_,
		const schar *	y_,
		double *	alpha_,
		double	Cp,
		double	Cn,
		double	eps,
		SolutionInfo *	si,
		kkint32	shrinking
	)

Definition at line 1317 of file svm289_BFS.cpp.

References active_set, active_size, alpha, alpha_status, calculate_rho(), Cn, Cp, do_shrinking(), eps, G, G_bar, get_C(), SVM289_BFS::QMatrix::get_Q(), SVM289_BFS::QMatrix::get_QD(), info(), is_lower_bound(), is_upper_bound(), l, SVM289_BFS::Solver::SolutionInfo::obj, p, Q, QD, reconstruct_gradient(), SVM289_BFS::Solver::SolutionInfo::rho, select_working_set(), unshrink, update_alpha_status(), SVM289_BFS::Solver::SolutionInfo::upper_bound_n, SVM289_BFS::Solver::SolutionInfo::upper_bound_p, and y.

Referenced by SVM289_BFS::Solver_NU::Solve(), SVM289_BFS::solve_c_svc(), SVM289_BFS::solve_epsilon_svr(), and SVM289_BFS::solve_one_class().

{
  this->l = l;
  this->Q = &Q;
  QD=Q.get_QD();
  clone(p, p_,l);
  clone(y, y_,l);
  clone(alpha,alpha_,l);
  this->Cp = Cp;
  this->Cn = Cn;
  this->eps = eps;
  unshrink = false;

  // initialize alpha_status
  {
    alpha_status = new char[l];
    for  (kkint32 i = 0;  i < l;  i++)
      update_alpha_status (i);
  }

  // initialize active set (for shrinking)
  {
    active_set = new kkint32[l];
    for  (kkint32 i = 0;  i < l;  i++)
      active_set[i] = i;
    active_size = l;
  }

  // initialize gradient
  {
    G     = new double[l];
    G_bar = new double[l];
    kkint32  i;
    for  (i = 0;  i < l;  i++)
    {
      G[i]     = p[i];
      G_bar[i] = 0;
    }

    for(i=0;i<l;i++)
    {
      if  (!is_lower_bound (i))
      {
        Qfloat *Q_i = Q.get_Q(i,l);
        double alpha_i = alpha[i];
        kkint32  j;
        for  (j = 0;  j < l;  j++)
          G[j] += alpha_i*Q_i[j];

        if  (is_upper_bound (i))
        {
          for  (j = 0;  j < l;  j++)
            G_bar[j] += get_C(i) * Q_i[j];
        }
      }
    }
  }

  // optimization step

  kkint32 iter = 0;
  kkint32 counter = Min (l, 1000) + 1;

  while(1)
  {
    // show progress and do shrinking

    if (--counter == 0)
    {
      counter = Min (l, 1000);
      if  (shrinking) 
        do_shrinking();
      info(".");
    }

    kkint32 i, j;
    if  (select_working_set (i, j) != 0)   // 'select_working_set' == 1 if already optimal otherwise 0.
    {
      // reconstruct the whole gradient
      reconstruct_gradient ();
      // reset active set size and check
      active_size = l;
      info ("*");
      if  (select_working_set (i, j) != 0)
        break;
      else
        counter = 1;  // do shrinking next iteration
    }
    
    ++iter;

    // update alpha[i] and alpha[j], handle bounds carefully
    
    const Qfloat *Q_i = Q.get_Q(i,active_size);
    const Qfloat *Q_j = Q.get_Q(j,active_size);

    double C_i = get_C(i);
    double C_j = get_C(j);

    double old_alpha_i = alpha[i];
    double old_alpha_j = alpha[j];

    if  (y[i] != y[j])
    {
      double  quad_coef = Q_i[i] + Q_j[j] +2 *Q_i[j];
      if  (quad_coef <= 0)
        quad_coef = TAU;

      double delta = (-G[i] - G[j]) / quad_coef;
      double diff = alpha[i] - alpha[j];
      alpha[i] += delta;
      alpha[j] += delta;
      
      if  (diff > 0)
      {
        if  (alpha[j] < 0)
        {
          alpha[j] = 0;
          alpha[i] = diff;
        }
      }
      else
      {
        if  (alpha[i] < 0)
        {
          alpha[i] = 0;
          alpha[j] = -diff;
        }
      }
      if  (diff > C_i - C_j)
      {
        if(alpha[i] > C_i)
        {
          alpha[i] = C_i;
          alpha[j] = C_i - diff;
        }
      }
      else
      {
        if  (alpha[j] > C_j)
        {
          alpha[j] = C_j;
          alpha[i] = C_j + diff;
        }
      }
    }
    else
    {
      double quad_coef = Q_i[i] + Q_j[j] - 2 * Q_i[j];

      if  (quad_coef <= 0)
        quad_coef = TAU;

      double delta = (G[i] - G[j]) / quad_coef;
      double sum = alpha[i] + alpha[j];
      alpha[i] -= delta;
      alpha[j] += delta;

      if  (sum > C_i)
      {
        if  (alpha[i] > C_i)
        {
          alpha[i] = C_i;
          alpha[j] = sum - C_i;
        }
      }
      else
      {
        if  (alpha[j] < 0)
        {
          alpha[j] = 0;
          alpha[i] = sum;
        }
      }
      if  (sum > C_j)
      {
        if  (alpha[j] > C_j)
        {
          alpha[j] = C_j;
          alpha[i] = sum - C_j;
        }
      }
      else
      {
        if  (alpha[i] < 0)
        {
          alpha[i] = 0;
          alpha[j] = sum;
        }
      }
    }

    // update G

    double delta_alpha_i = alpha[i] - old_alpha_i;
    double delta_alpha_j = alpha[j] - old_alpha_j;
    
    for  (kkint32 k = 0;  k < active_size;  k++)
    {
      G[k] += Q_i[k] * delta_alpha_i + Q_j[k] * delta_alpha_j;
    }

    // update alpha_status and G_bar

    {
      bool ui = is_upper_bound(i);
      bool uj = is_upper_bound(j);
      update_alpha_status (i);
      update_alpha_status (j);
      kkint32 k;
      if  (ui != is_upper_bound (i))
      {
        Q_i = Q.get_Q (i,l);
        if  (ui)
        {
          for  (k = 0;  k < l;  k++)
            G_bar[k] -= C_i * Q_i[k];
        }
        else
        {
          for  (k = 0;  k < l;  k++)
            G_bar[k] += C_i * Q_i[k];
        }
      }

      if(uj != is_upper_bound(j))
      {
        Q_j = Q.get_Q(j,l);
        if  (uj)
        {
          for  (k = 0;  k < l;  k++)
            G_bar[k] -= C_j * Q_j[k];
        }
        else
        {
          for  (k = 0;  k < l;  k++)
            G_bar[k] += C_j * Q_j[k];
        }
      }
    }
  }

  // calculate rho
  si->rho = calculate_rho();

  // calculate objective value
  {
    double v = 0;
    kkint32 i;
    for  (i = 0;  i < l;  i++)
      v += alpha[i] * (G[i] + p[i]);

    si->obj = v/2;
  }

  // put back the solution
  {
    for  (kkint32 i = 0;  i < l;  i++)
    {
      alpha_[active_set[i]] = alpha[i];
    }
  }

  // juggle everything back
  /*{
    for(kkint32 i=0;i<l;i++)
      while(active_set[i] != i)
        swap_index(i,active_set[i]);
        // or Q.swap_index(i,active_set[i]);
  }*/

  si->upper_bound_p = Cp;
  si->upper_bound_n = Cn;

  //info("\noptimization finished, #iter = %d\n",iter);

  delete[] p;
  delete[] y;
  delete[] alpha;
  delete[] alpha_status;
  delete[] active_set;
  delete[] G;
  delete[] G_bar;
}  /* Solve */

void SVM289_BFS::Solver::swap_index ( kkint32  i, kkint32  j  )

protected

Definition at line 1250 of file svm289_BFS.cpp.

References Q, and SVM289_BFS::QMatrix::swap_index().

Referenced by do_shrinking().

{
  Q->swap_index (i, j);
  SVM289_BFS::swap (y[i], y[j]);
  SVM289_BFS::swap (G[i], G[j]);
  SVM289_BFS::swap (alpha_status[i], alpha_status[j]);
  SVM289_BFS::swap (alpha[i], alpha[j]);
  SVM289_BFS::swap (p[i], p[j]);
  SVM289_BFS::swap (active_set[i],active_set[j]);
  SVM289_BFS::swap (G_bar[i], G_bar[j]);
}  /* swap_index */

void SVM289_BFS::Solver::update_alpha_status ( kkint32  i )

inlineprotected

Definition at line 1213 of file svm289_BFS.cpp.

References alpha, alpha_status, FREE, get_C(), LOWER_BOUND, and UPPER_BOUND.

Referenced by Solve().

  {
    if  (alpha[i] >= get_C(i))
      alpha_status[i] = UPPER_BOUND;

    else  if(alpha[i] <= 0)
      alpha_status[i] = LOWER_BOUND;

    else alpha_status[i] = FREE;
  }

Member Data Documentation

kkint32* SVM289_BFS::Solver::active_set

protected

Definition at line 1201 of file svm289_BFS.cpp.

Referenced by Solve().

kkint32 SVM289_BFS::Solver::active_size

protected

Definition at line 1189 of file svm289_BFS.cpp.

Referenced by calculate_rho(), do_shrinking(), reconstruct_gradient(), select_working_set(), and Solve().

double* SVM289_BFS::Solver::alpha

protected

Definition at line 1194 of file svm289_BFS.cpp.

Referenced by reconstruct_gradient(), Solve(), and update_alpha_status().

char* SVM289_BFS::Solver::alpha_status

protected

Definition at line 1193 of file svm289_BFS.cpp.

Referenced by is_free(), is_lower_bound(), is_upper_bound(), Solve(), and update_alpha_status().

double SVM289_BFS::Solver::Cn

protected

Definition at line 1199 of file svm289_BFS.cpp.

Referenced by get_C(), and Solve().

double SVM289_BFS::Solver::Cp

protected

Definition at line 1198 of file svm289_BFS.cpp.

Referenced by get_C(), and Solve().

double SVM289_BFS::Solver::eps

protected

Definition at line 1197 of file svm289_BFS.cpp.

Referenced by do_shrinking(), select_working_set(), and Solve().

double* SVM289_BFS::Solver::G

protected

Definition at line 1191 of file svm289_BFS.cpp.

Referenced by calculate_rho(), do_shrinking(), reconstruct_gradient(), select_working_set(), and Solve().

double* SVM289_BFS::Solver::G_bar

protected

Definition at line 1202 of file svm289_BFS.cpp.

Referenced by reconstruct_gradient(), and Solve().

kkint32 SVM289_BFS::Solver::l

protected

Definition at line 1203 of file svm289_BFS.cpp.

Referenced by do_shrinking(), reconstruct_gradient(), and Solve().

double* SVM289_BFS::Solver::p

protected

Definition at line 1200 of file svm289_BFS.cpp.

Referenced by reconstruct_gradient(), and Solve().

QMatrix* SVM289_BFS::Solver::Q

protected

Definition at line 1195 of file svm289_BFS.cpp.

Referenced by reconstruct_gradient(), select_working_set(), Solve(), and swap_index().

const Qfloat* SVM289_BFS::Solver::QD

protected

Definition at line 1196 of file svm289_BFS.cpp.

Referenced by select_working_set(), and Solve().

bool SVM289_BFS::Solver::unshrink

protected

Definition at line 1204 of file svm289_BFS.cpp.

Referenced by do_shrinking(), and Solve().

schar* SVM289_BFS::Solver::y

protected

Definition at line 1190 of file svm289_BFS.cpp.

Referenced by calculate_rho(), do_shrinking(), get_C(), select_working_set(), and Solve().

---

The documentation for this class was generated from the following file:

• C:/Users/Kurt/GitHub/KSquareLibraries/KKMachineLearning/svm289_BFS.cpp