Algorithm-SVM
view release on metacpan or search on metacpan
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <float.h>
#include <string.h>
#include <stdarg.h>
#include "libsvm.h"
typedef float Qfloat;
typedef signed char schar;
#ifndef min
template <class T> inline T min(T x,T y) { return (x<y)?x:y; }
#endif
#ifndef max
template <class T> inline T max(T x,T y) { return (x>y)?x:y; }
#endif
template <class T> inline void swap(T& x, T& y) { T t=x; x=y; y=t; }
template <class S, class T> inline void clone(T*& dst, S* src, int n)
{
dst = new T[n];
memcpy((void *)dst,(void *)src,sizeof(T)*n);
}
inline double powi(double base, int times)
{
double tmp = base, ret = 1.0;
for(int t=times; t>0; t/=2)
{
if(t%2==1) ret*=tmp;
tmp = tmp * tmp;
}
return ret;
}
#define INF HUGE_VAL
#define TAU 1e-12
#define Malloc(type,n) (type *)malloc((n)*sizeof(type))
#if 1
void info(const char *fmt,...)
{
va_list ap;
va_start(ap,fmt);
vprintf(fmt,ap);
va_end(ap);
}
void info_flush()
{
fflush(stdout);
}
#else
void info(char *fmt,...) {}
void info_flush() {}
#endif
//
// Kernel Cache
//
// l is the number of total data items
// size is the cache size limit in bytes
//
class Cache
{
public:
Cache(int l,long int size);
~Cache();
// request data [0,len)
// return some position p where [p,len) need to be filled
// (p >= len if nothing needs to be filled)
int get_data(const int index, Qfloat **data, int len);
void swap_index(int i, int j); // future_option
private:
int l;
long int size;
struct head_t
{
head_t *prev, *next; // a cicular list
Qfloat *data;
int len; // data[0,len) is cached in this entry
};
head_t *head;
head_t lru_head;
void lru_delete(head_t *h);
void lru_insert(head_t *h);
};
Cache::Cache(int l_,long int size_):l(l_),size(size_)
{
head = (head_t *)calloc(l,sizeof(head_t)); // initialized to 0
size /= sizeof(Qfloat);
size -= l * sizeof(head_t) / sizeof(Qfloat);
size = max(size, 2 * (long int) l); // cache must be large enough for two columns
lru_head.next = lru_head.prev = &lru_head;
}
Cache::~Cache()
{
for(head_t *h = lru_head.next; h != &lru_head; h=h->next)
free(h->data);
free(head);
}
void Cache::lru_delete(head_t *h)
{
// delete from current location
h->prev->next = h->next;
h->next->prev = h->prev;
}
void Cache::lru_insert(head_t *h)
{
// insert to last position
h->next = &lru_head;
h->prev = lru_head.prev;
h->prev->next = h;
h->next->prev = h;
}
int Cache::get_data(const int index, Qfloat **data, int len)
{
head_t *h = &head[index];
if(h->len) lru_delete(h);
while(size < more)
{
head_t *old = lru_head.next;
lru_delete(old);
free(old->data);
size += old->len;
old->data = 0;
old->len = 0;
}
// allocate new space
h->data = (Qfloat *)realloc(h->data,sizeof(Qfloat)*len);
size -= more;
swap(h->len,len);
}
lru_insert(h);
*data = h->data;
return len;
}
void Cache::swap_index(int i, int j)
{
if(i==j) return;
if(head[i].len) lru_delete(&head[i]);
if(head[j].len) lru_delete(&head[j]);
swap(head[i].data,head[j].data);
swap(head[i].len,head[j].len);
if(head[i].len) lru_insert(&head[i]);
if(head[j].len) lru_insert(&head[j]);
if(i>j) swap(i,j);
for(head_t *h = lru_head.next; h!=&lru_head; h=h->next)
{
if(h->len > i)
{
if(h->len > j)
swap(h->data[i],h->data[j]);
else
{
// give up
lru_delete(h);
free(h->data);
size += h->len;
h->data = 0;
h->len = 0;
}
}
}
}
//
// Kernel evaluation
//
// the static method k_function is for doing single kernel evaluation
// the constructor of Kernel prepares to calculate the l*l kernel matrix
// the member function get_Q is for getting one column from the Q Matrix
//
class QMatrix {
public:
virtual Qfloat *get_Q(int column, int len) const = 0;
virtual Qfloat *get_QD() const = 0;
virtual void swap_index(int i, int j) const = 0;
virtual ~QMatrix() {}
};
class Kernel: public QMatrix {
public:
Kernel(int l, svm_node * const * x, const svm_parameter& param);
virtual ~Kernel();
static double k_function(const svm_node *x, const svm_node *y,
const svm_parameter& param);
virtual Qfloat *get_Q(int column, int len) const = 0;
virtual Qfloat *get_QD() const = 0;
virtual void swap_index(int i, int j) const // no so const...
{
swap(x[i],x[j]);
if(x_square) swap(x_square[i],x_square[j]);
}
protected:
double (Kernel::*kernel_function)(int i, int j) const;
private:
const svm_node **x;
double *x_square;
// svm_parameter
const int kernel_type;
const int degree;
const double gamma;
const double coef0;
static double dot(const svm_node *px, const svm_node *py);
double kernel_linear(int i, int j) const
{
return dot(x[i],x[j]);
}
double kernel_poly(int i, int j) const
{
return powi(gamma*dot(x[i],x[j])+coef0,degree);
}
double kernel_rbf(int i, int j) const
{
return exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));
}
double kernel_sigmoid(int i, int j) const
{
return tanh(gamma*dot(x[i],x[j])+coef0);
}
double kernel_precomputed(int i, int j) const
{
return x[i][(int)(x[j][0].value)].value;
}
};
Kernel::Kernel(int l, svm_node * const * x_, const svm_parameter& param)
:kernel_type(param.kernel_type), degree(param.degree),
gamma(param.gamma), coef0(param.coef0)
{
switch(kernel_type)
{
case LINEAR:
kernel_function = &Kernel::kernel_linear;
break;
case POLY:
kernel_function = &Kernel::kernel_poly;
++x;
++y;
}
else
{
if(x->index > y->index)
{
sum += y->value * y->value;
++y;
}
else
{
sum += x->value * x->value;
++x;
}
}
}
while(x->index != -1)
{
sum += x->value * x->value;
++x;
}
while(y->index != -1)
{
sum += y->value * y->value;
++y;
}
return exp(-param.gamma*sum);
}
case SIGMOID:
return tanh(param.gamma*dot(x,y)+param.coef0);
case PRECOMPUTED: //x: test (validation), y: SV
return x[(int)(y->value)].value;
default:
return 0; // Unreachable
}
}
// An SMO algorithm in Fan et al., JMLR 6(2005), p. 1889--1918
// Solves:
//
// min 0.5(\alpha^T Q \alpha) + p^T \alpha
//
// y^T \alpha = \delta
// y_i = +1 or -1
// 0 <= alpha_i <= Cp for y_i = 1
// 0 <= alpha_i <= Cn for y_i = -1
//
// Given:
//
// Q, p, y, Cp, Cn, and an initial feasible point \alpha
// l is the size of vectors and matrices
// eps is the stopping tolerance
//
// solution will be put in \alpha, objective value will be put in obj
//
class Solver {
public:
Solver() {};
virtual ~Solver() {};
struct SolutionInfo {
double obj;
double rho;
double upper_bound_p;
double upper_bound_n;
double r; // for Solver_NU
};
void Solve(int l, const QMatrix& Q, const double *p_, const schar *y_,
double *alpha_, double Cp, double Cn, double eps,
SolutionInfo* si, int shrinking);
protected:
int active_size;
schar *y;
double *G; // gradient of objective function
enum { LOWER_BOUND, UPPER_BOUND, FREE };
char *alpha_status; // LOWER_BOUND, UPPER_BOUND, FREE
double *alpha;
const QMatrix *Q;
const Qfloat *QD;
double eps;
double Cp,Cn;
double *p;
int *active_set;
double *G_bar; // gradient, if we treat free variables as 0
int l;
bool unshrinked; // XXX
double get_C(int i)
{
return (y[i] > 0)? Cp : Cn;
}
void update_alpha_status(int i)
{
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;
}
bool is_upper_bound(int i) { return alpha_status[i] == UPPER_BOUND; }
bool is_lower_bound(int i) { return alpha_status[i] == LOWER_BOUND; }
bool is_free(int i) { return alpha_status[i] == FREE; }
void swap_index(int i, int j);
void reconstruct_gradient();
virtual int select_working_set(int &i, int &j);
virtual double calculate_rho();
virtual void do_shrinking();
private:
bool be_shrunken(int i, double Gmax1, double Gmax2);
};
void Solver::swap_index(int i, int j)
{
Q->swap_index(i,j);
swap(y[i],y[j]);
swap(G[i],G[j]);
for(i=l-1;i>=active_size;i--)
if (!be_shrunken(i, Gmax1, Gmax2))
{
while (active_size < i)
{
if (be_shrunken(active_size, Gmax1, Gmax2))
{
swap_index(i,active_size);
break;
}
active_size++;
}
active_size++;
}
}
double Solver::calculate_rho()
{
double r;
int nr_free = 0;
double ub = INF, lb = -INF, sum_free = 0;
for(int 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;
}
//
// Solver for nu-svm classification and regression
//
// additional constraint: e^T \alpha = constant
//
class Solver_NU : public Solver
{
public:
Solver_NU() {}
void Solve(int l, const QMatrix& Q, const double *p, const schar *y,
double *alpha, double Cp, double Cn, double eps,
SolutionInfo* si, int shrinking)
{
this->si = si;
Solver::Solve(l,Q,p,y,alpha,Cp,Cn,eps,si,shrinking);
}
private:
SolutionInfo *si;
int select_working_set(int &i, int &j);
double calculate_rho();
bool be_shrunken(int i, double Gmax1, double Gmax2, double Gmax3, double Gmax4);
void do_shrinking();
};
// return 1 if already optimal, return 0 otherwise
int Solver_NU::select_working_set(int &out_i, int &out_j)
{
// return i,j such that y_i = y_j and
// i: maximizes -y_i * grad(f)_i, i in I_up(\alpha)
// j: minimizes the decrease of obj value
// (if quadratic coefficeint <= 0, replace it with tau)
// -y_j*grad(f)_j < -y_i*grad(f)_i, j in I_low(\alpha)
double Gmaxp = -INF;
double Gmaxp2 = -INF;
int Gmaxp_idx = -1;
double Gmaxn = -INF;
double Gmaxn2 = -INF;
int Gmaxn_idx = -1;
int Gmin_idx = -1;
double obj_diff_min = INF;
for(int t=0;t<active_size;t++)
if(y[t]==+1)
{
if(!is_upper_bound(t))
if(-G[t] >= Gmaxp)
{
Gmaxp = -G[t];
Gmaxp_idx = t;
}
}
else
{
if(!is_lower_bound(t))
if(G[t] >= Gmaxn)
{
Gmaxn = G[t];
Gmaxn_idx = t;
}
}
int ip = Gmaxp_idx;
int in = Gmaxn_idx;
const Qfloat *Q_ip = NULL;
const Qfloat *Q_in = NULL;
}
active_size++;
}
active_size++;
}
}
double Solver_NU::calculate_rho()
{
int nr_free1 = 0,nr_free2 = 0;
double ub1 = INF, ub2 = INF;
double lb1 = -INF, lb2 = -INF;
double sum_free1 = 0, sum_free2 = 0;
for(int i=0;i<active_size;i++)
{
if(y[i]==+1)
{
if(is_upper_bound(i))
lb1 = max(lb1,G[i]);
else if(is_lower_bound(i))
ub1 = min(ub1,G[i]);
else
{
++nr_free1;
sum_free1 += G[i];
}
}
else
{
if(is_upper_bound(i))
lb2 = max(lb2,G[i]);
else if(is_lower_bound(i))
ub2 = min(ub2,G[i]);
else
{
++nr_free2;
sum_free2 += G[i];
}
}
}
double r1,r2;
if(nr_free1 > 0)
r1 = sum_free1/nr_free1;
else
r1 = (ub1+lb1)/2;
if(nr_free2 > 0)
r2 = sum_free2/nr_free2;
else
r2 = (ub2+lb2)/2;
si->r = (r1+r2)/2;
return (r1-r2)/2;
}
//
// Q matrices for various formulations
//
class SVC_Q: public Kernel
{
public:
SVC_Q(const svm_problem& prob, const svm_parameter& param, const schar *y_)
:Kernel(prob.l, prob.x, param)
{
clone(y,y_,prob.l);
cache = new Cache(prob.l,(long int)(param.cache_size*(1<<20)));
QD = new Qfloat[prob.l];
for(int i=0;i<prob.l;i++)
QD[i]= (Qfloat)(this->*kernel_function)(i,i);
}
Qfloat *get_Q(int i, int len) const
{
Qfloat *data;
int start;
if((start = cache->get_data(i,&data,len)) < len)
{
for(int j=start;j<len;j++)
data[j] = (Qfloat)(y[i]*y[j]*(this->*kernel_function)(i,j));
}
return data;
}
Qfloat *get_QD() const
{
return QD;
}
void swap_index(int i, int j) const
{
cache->swap_index(i,j);
Kernel::swap_index(i,j);
swap(y[i],y[j]);
swap(QD[i],QD[j]);
}
~SVC_Q()
{
delete[] y;
delete cache;
delete[] QD;
}
private:
schar *y;
Cache *cache;
Qfloat *QD;
};
class ONE_CLASS_Q: public Kernel
{
public:
ONE_CLASS_Q(const svm_problem& prob, const svm_parameter& param)
:Kernel(prob.l, prob.x, param)
{
cache = new Cache(prob.l,(long int)(param.cache_size*(1<<20)));
QD = new Qfloat[prob.l];
for(int i=0;i<prob.l;i++)
QD[i]= (Qfloat)(this->*kernel_function)(i,i);
}
Qfloat *get_Q(int i, int len) const
{
Qfloat *data;
int start;
if((start = cache->get_data(i,&data,len)) < len)
{
for(int j=start;j<len;j++)
data[j] = (Qfloat)(this->*kernel_function)(i,j);
}
return data;
}
Qfloat *get_QD() const
{
return QD;
}
void swap_index(int i, int j) const
{
cache->swap_index(i,j);
Kernel::swap_index(i,j);
swap(QD[i],QD[j]);
}
~ONE_CLASS_Q()
{
delete cache;
delete[] QD;
}
private:
Cache *cache;
Qfloat *QD;
};
class SVR_Q: public Kernel
{
public:
SVR_Q(const svm_problem& prob, const svm_parameter& param)
:Kernel(prob.l, prob.x, param)
{
l = prob.l;
cache = new Cache(l,(long int)(param.cache_size*(1<<20)));
QD = new Qfloat[2*l];
sign = new schar[2*l];
index = new int[2*l];
for(int k=0;k<l;k++)
{
sign[k] = 1;
sign[k+l] = -1;
index[k] = k;
index[k+l] = k;
QD[k]= (Qfloat)(this->*kernel_function)(k,k);
QD[k+l]=QD[k];
}
buffer[0] = new Qfloat[2*l];
buffer[1] = new Qfloat[2*l];
next_buffer = 0;
}
void swap_index(int i, int j) const
{
swap(sign[i],sign[j]);
swap(index[i],index[j]);
swap(QD[i],QD[j]);
}
Qfloat *get_Q(int i, int len) const
{
Qfloat *data;
int real_i = index[i];
if(cache->get_data(real_i,&data,l) < l)
{
for(int j=0;j<l;j++)
data[j] = (Qfloat)(this->*kernel_function)(real_i,j);
}
// reorder and copy
Qfloat *buf = buffer[next_buffer];
next_buffer = 1 - next_buffer;
schar si = sign[i];
for(int j=0;j<len;j++)
buf[j] = si * sign[j] * data[index[j]];
return buf;
}
Qfloat *get_QD() const
{
return QD;
}
~SVR_Q()
{
delete cache;
delete[] sign;
delete[] index;
delete[] buffer[0];
delete[] buffer[1];
( run in 0.845 second using v1.01-cache-2.11-cpan-39bf76dae61 )