SVM233::Solver Class Reference

Inheritance diagram for SVM233::Solver:

Classes
struct	SolutionInfo

Public Member Functions
	Solver ()
virtual	~Solver ()
void	Solve (kkint32 l, const Kernel &Q, const double *b_, const schar *y_, double *alpha_, double Cp, double Cn, double eps, SolutionInfo *si, kkint32 shrinking)
void	Solve (kkint32 l, const Kernel &Q, const double *b_, const schar *y_, double *alpha_, double *C_, 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 *	b
double *	C
double	eps
double *	G
double *	G_bar
kkint32	l
const Kernel *	Q
bool	unshrinked
schar *	y

Detailed Description

Definition at line 532 of file svm.cpp.

Member Enumeration Documentation

anonymous enum

protected

Enumerator
LOWER_BOUND
UPPER_BOUND
FREE

Definition at line 573 of file svm.cpp.

{LOWER_BOUND, UPPER_BOUND, FREE};

Constructor & Destructor Documentation

SVM233::Solver::Solver ( )

inline

Definition at line 535 of file svm.cpp.

{};

virtual SVM233::Solver::~Solver ( )

inlinevirtual

Definition at line 536 of file svm.cpp.

{};

Member Function Documentation

double SVM233::Solver::calculate_rho ( )

protectedvirtual

Definition at line 2348 of file svm.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, lb = -INF, sum_free = 0;
  for  (kkint32 i = 0;  i < active_size;  i++)
  {
    double yG = y[i]*G[i];

    if(is_lower_bound(i))
    {
      if(y[i] > 0)
        ub = min(ub,yG);
      else
        lb = max(lb,yG);
    }
    else if(is_upper_bound(i))
    {
      if(y[i] < 0)
        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;
}

void SVM233::Solver::do_shrinking ( )

protectedvirtual

Definition at line 2276 of file svm.cpp.

References active_size, eps, G, is_lower_bound(), is_upper_bound(), l, reconstruct_gradient(), select_working_set(), swap_index(), unshrinked, and y.

Referenced by Solve().

{
  kkint32 i,j,k;
  if  (select_working_set (i,j) != 0) 
    return;

  double Gm1 = -y[j]*G[j];
  double Gm2 = y[i]*G[i];

  // shrink

  for  (k = 0;  k < active_size;  k++)
  {
    if  (is_lower_bound (k))
    {
      if  (y[k]==+1)
      {
        if(-G[k] >= Gm1) continue;
      }
      else if  (-G[k] >= Gm2) continue;
    }
    else if  (is_upper_bound(k))
    {
      if(y[k]==+1)
      {
        if(G[k] >= Gm2) continue;
      }
      else if(G[k] >= Gm1) continue;
    }
    else continue;

    --active_size;
    swap_index(k,active_size);
    --k;  // look at the newcomer
  }

  // unshrink, check all variables again before final iterations

  if(unshrinked || -(Gm1 + Gm2) > eps*10) return;

  unshrinked = true;
  reconstruct_gradient();

  for(k=l-1;k>=active_size;k--)
  {
    if(is_lower_bound(k))
    {
      if(y[k]==+1)
      {
        if(-G[k] < Gm1) continue;
      }
      else if(-G[k] < Gm2) continue;
    }
    else if(is_upper_bound(k))
    {
      if(y[k]==+1)
      {
        if(G[k] < Gm2) continue;
      }
      else if(G[k] < Gm1) continue;
    }
    else continue;

    swap_index(k,active_size);
    active_size++;
    ++k;  // look at the newcomer
  }
}

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

inlineprotected

Definition at line 585 of file svm.cpp.

References C.

Referenced by Solve(), and update_alpha_status().

    {
      return C[i];
    }

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

inlineprotected

Definition at line 603 of file svm.cpp.

References alpha_status, and FREE.

Referenced by reconstruct_gradient().

{ return alpha_status[i] == FREE; }

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

inlineprotected

Definition at line 602 of file svm.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 SVM233::Solver::is_upper_bound ( kkint32  i )

inlineprotected

Definition at line 601 of file svm.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 SVM233::Solver::reconstruct_gradient ( )

protected

Definition at line 1897 of file svm.cpp.

References active_size, alpha, b, G, G_bar, SVM233::Kernel::get_Q(), is_free(), l, 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;
  for(i=active_size;i<l;i++)
    G[i] = G_bar[i] + b[i];

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

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

protectedvirtual

Definition at line 2212 of file svm.cpp.

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

Referenced by do_shrinking(), and Solve().

{
  // return i,j which maximize -grad(f)^T d , under constraint
  // if alpha_i == C, d != +1
  // if alpha_i == 0, d != -1

  double Gmax1 = -INF;  // max { -grad(f)_i * d | y_i*d = +1 }
  kkint32 Gmax1_idx = -1;

  double Gmax2 = -INF;  // max { -grad(f)_i * d | y_i*d = -1 }
  kkint32 Gmax2_idx = -1;

  for(kkint32 i=0;i<active_size;i++)
  {
    if(y[i]==+1)  // y = +1
    {
      if(!is_upper_bound(i))  // d = +1
      {
        if(-G[i] > Gmax1)
        {
          Gmax1 = -G[i];
          Gmax1_idx = i;
        }
      }
      if(!is_lower_bound(i))  // d = -1
      {
        if(G[i] > Gmax2)
        {
          Gmax2 = G[i];
          Gmax2_idx = i;
        }
      }
    }
    else  // y = -1
    {
      if(!is_upper_bound(i))  // d = +1
      {
        if(-G[i] > Gmax2)
        {
          Gmax2 = -G[i];
          Gmax2_idx = i;
        }
      }
      if(!is_lower_bound(i))  // d = -1
      {
        if(G[i] > Gmax1)
        {
          Gmax1 = G[i];
          Gmax1_idx = i;
        }
      }
    }
  }

  if(Gmax1+Gmax2 < eps)
    return 1;

  out_i = Gmax1_idx;
  out_j = Gmax2_idx;
  return 0;
}

void SVM233::Solver::Solve	(	kkint32	l,
		const Kernel &	Q,
		const double *	b_,
		const schar *	y_,
		double *	alpha_,
		double	Cp,
		double	Cn,
		double	eps,
		SolutionInfo *	si,
		kkint32	shrinking
	)

Definition at line 2186 of file svm.cpp.

References Solve(), SVM233::Solver::SolutionInfo::upper_bound_n, and SVM233::Solver::SolutionInfo::upper_bound_p.

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

{
  double* C_ = new double[l];
  for(kkint32 i=0;i<l;i++)
    C_[i] = (y_[i] > 0 ? Cp : Cn);

  Solve (l, Q, b_, y_, alpha_, C_, eps, si, shrinking);

  si->upper_bound_p = Cp;
  si->upper_bound_n = Cn;
  delete [] C_;
}

void SVM233::Solver::Solve	(	kkint32	l,
		const Kernel &	Q,
		const double *	b_,
		const schar *	y_,
		double *	alpha_,
		double *	C_,
		double	eps,
		SolutionInfo *	si,
		kkint32	shrinking
	)

Definition at line 1920 of file svm.cpp.

References active_set, active_size, alpha, alpha_status, b, C, calculate_rho(), do_shrinking(), eps, G, G_bar, get_C(), SVM233::Kernel::get_Q(), SVM233::info(), SVM233::info_flush(), is_lower_bound(), is_upper_bound(), l, SVM233::Solver::SolutionInfo::obj, Q, reconstruct_gradient(), SVM233::Solver::SolutionInfo::rho, select_working_set(), unshrinked, update_alpha_status(), and y.

Referenced by Solve(), and SVM233::solve_c_svc().

{
  this->l = l;
  this->Q = &Q;
  clone (b, b_,l);
  clone (y, y_,l);
  clone (alpha,alpha_,l);
  clone (C, C_, l);
  this->eps = eps;
  unshrinked = 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] = b[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 ((kkint32)l, (kkint32)1000) + 1;

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

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

    kkint32 i,j;
    if(select_working_set(i,j)!=0)
    {
      // reconstruct the whole gradient
      reconstruct_gradient();
      // reset active set size and check
      active_size = l;
      info("*"); info_flush();
      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 delta = (-G[i]-G[j])/max(Q_i[i]+Q_j[j]+2*Q_i[j],(Qfloat)0);
      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 delta = (G[i]-G[j])/max(Q_i[i]+Q_j[j]-2*Q_i[j],(Qfloat)0);
      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] + b[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]);
  }*/

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

  delete[] C;
  delete[] b;
  delete[] y;
  delete[] alpha;
  delete[] alpha_status;
  delete[] active_set;
  delete[] G;
  delete[] G_bar;
}

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

protected

Definition at line 1881 of file svm.cpp.

References Q, and SVM233::Kernel::swap_index().

Referenced by do_shrinking().

{
  Q->swap_index(i,j);
  Swap(y[i],y[j]);
  Swap(G[i],G[j]);
  Swap(alpha_status[i],alpha_status[j]);
  Swap(alpha[i],alpha[j]);
  Swap(b[i],b[j]);
  Swap(active_set[i],active_set[j]);
  Swap(G_bar[i],G_bar[j]);
  Swap(C[i], C[j]);
}

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

inlineprotected

Definition at line 589 of file svm.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* SVM233::Solver::active_set

protected

Definition at line 580 of file svm.cpp.

Referenced by Solve().

kkint32 SVM233::Solver::active_size

protected

Definition at line 570 of file svm.cpp.

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

double* SVM233::Solver::alpha

protected

Definition at line 575 of file svm.cpp.

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

char* SVM233::Solver::alpha_status

protected

Definition at line 574 of file svm.cpp.

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

double* SVM233::Solver::b

protected

Definition at line 579 of file svm.cpp.

Referenced by reconstruct_gradient(), and Solve().

double* SVM233::Solver::C

protected

Definition at line 578 of file svm.cpp.

Referenced by get_C(), and Solve().

double SVM233::Solver::eps

protected

Definition at line 577 of file svm.cpp.

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

double* SVM233::Solver::G

protected

Definition at line 572 of file svm.cpp.

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

double* SVM233::Solver::G_bar

protected

Definition at line 581 of file svm.cpp.

Referenced by reconstruct_gradient(), and Solve().

kkint32 SVM233::Solver::l

protected

Definition at line 582 of file svm.cpp.

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

const Kernel* SVM233::Solver::Q

protected

Definition at line 576 of file svm.cpp.

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

bool SVM233::Solver::unshrinked

protected

Definition at line 583 of file svm.cpp.

Referenced by do_shrinking(), and Solve().

schar* SVM233::Solver::y

protected

Definition at line 571 of file svm.cpp.

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

---

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

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