1
/*    Copyright 2006 Vikas Sindhwani (vikass@cs.uchicago.edu)
2
      SVM-lin: Fast SVM Solvers for Supervised and Semi-supervised Learning
3

4
      This file is part of SVM-lin.
5

6
      SVM-lin is free software; you can redistribute it and/or modify
7
      it under the terms of the GNU General Public License as published by
8
      the Free Software Foundation; either version 2 of the License, or
9
      (at your option) any later version.
10

11
      SVM-lin is distributed in the hope that it will be useful,
12
      but WITHOUT ANY WARRANTY; without even the implied warranty of
13
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
      GNU General Public License for more details.
15

16
      You should have received a copy of the GNU General Public License
17
      along with SVM-lin (see gpl.txt); if not, write to the Free Software
18
      Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
19
*/
20
#ifndef _svmlin_H
21
#define _svmlin_H
22
#include <vector>
23
#include <ctime>
24

25
using namespace std;
26

27
/* OPTIMIZATION CONSTANTS */
28
#define CGITERMAX 10000 /* maximum number of CGLS iterations */
29
#define SMALL_CGITERMAX 10 /* for heuristic 1 in reference [2] */
30
#define EPSILON   1e-6 /* most tolerances are set to this value */
31
#define BIG_EPSILON 0.01 /* for heuristic 2 in reference [2] */
32
#define RELATIVE_STOP_EPS 1e-9 /* for L2-SVM-MFN relative stopping criterion */
33
#define MFNITERMAX 50 /* maximum number of MFN iterations */
34
#define TSVM_ANNEALING_RATE 1.5 /* rate at which lambda_u is increased in TSVM */
35
#define TSVM_LAMBDA_SMALL 1e-5 /* lambda_u starts from this value */
36
#define DA_ANNEALING_RATE 1.5 /* annealing rate for DA */
37
#define DA_INIT_TEMP 10 /* initial temperature relative to lambda_u */
38
#define DA_INNER_ITERMAX 100 /* maximum fixed temperature iterations for DA */
39
#define DA_OUTER_ITERMAX 30 /* maximum number of outer loops for DA */
40

41
#define VERBOSE_CGLS 0
42

43
/* Data: Input examples are stored in sparse (Compressed Row Storage) format */
44
struct data
45
{
46
  int m; /* number of examples */
47
  int l; /* number of labeled examples */
48
  int u; /* number of unlabeled examples l+u = m */
49
  int n; /* number of features */
50
  int nz; /* number of non-zeros */
51
  double *val; /* data values (nz elements) [CRS format] */
52
  int *rowptr; /* n+1 vector [CRS format] */
53
  int *colind; /* nz elements [CRS format] */
54
  double *Y;   /* labels */
55
  double *C;   /* cost associated with each example */
56
};
57

58
struct vector_double /* defines a vector of doubles */
59
{
60
  int d; /* number of elements */
61
  double *vec; /* ptr to vector elements*/
62
};
63

64

65

66
struct vector_int /* defines a vector of ints for index subsets */
67
{
68
  int d; /* number of elements */
69
  int *vec; /* ptr to vector elements */
70
};
71

72
enum { RLS, SVM, TSVM, DA_SVM }; /* currently implemented algorithms */
73

74
struct options
75
{
76
  /* user options */
77
  int algo; /* 1 to 4 for RLS,SVM,TSVM,DASVM */
78
  double lambda; /* regularization parameter */
79
  double lambda_u; /* regularization parameter over unlabeled examples */
80
  int S; /* maximum number of TSVM switches per fixed-weight label optimization */
81
  double R; /* expected fraction of unlabeled examples in positive class */
82
  double Cp; /* cost for positive examples */
83
  double Cn; /* cost for negative examples */
84
  /*  internal optimization options */
85
  double epsilon; /* all tolerances */
86
  int cgitermax;  /* max iterations for CGLS */
87
  int mfnitermax; /* max iterations for L2_SVM_MFN */
88
  bool verbose; /* Should the output be verbose? */
89
};
90

91 1
class timer { /* to output run time */
92
protected:
93
  double start, finish;
94
public:
95
  vector<double> times;
96
  void record() {
97
    times.push_back(time());
98
  }
99
  void reset_vectors() {
100
    times.erase(times.begin(), times.end());
101
  }
102 1
  void restart() { start = clock(); }
103 1
  void stop() { finish = clock(); }
104 0
  double time() const { return ((double)(finish - start))/CLOCKS_PER_SEC; }
105
};
106
class Delta { /* used in line search */
107
 public:
108 0
   Delta() {delta=0.0; index=0;s=0;};
109
   double delta;
110
   int index;
111
   int s;
112
};
113 0
inline bool operator<(const Delta& a , const Delta& b) { return (a.delta < b.delta);}
114

115
void initialize(struct vector_double *A, int k, double a);
116
/* initializes a vector_double to be of length k, all elements set to a */
117
void initialize(struct vector_int *A, int k);
118
/* initializes a vector_int to be of length k, elements set to 1,2..k. */
119
void SetData(struct data *Data, int m,int n, int l,int u, int nz,
120
	     double *VAL, int *R, int *C, double *Y, double *COSTS); /* sets data fields */
121
void GetLabeledData(struct data *Data_Labeled, const struct data *Data);
122
/* extracts labeled data from Data and copies it into Data_Labeled */
123
void Write(const char *file_name, const struct vector_double *somevector);
124
/* writes a vector into filename, one element per line */
125
void Clear(struct data *a); /* deletes a */
126
void Clear(struct vector_double *a); /* deletes a */
127
void Clear(struct vector_int *a); /* deletes a */
128
double norm_square(const vector_double *A); /* returns squared length of A */
129

130
/* ssl_train: takes data, options, uninitialized weight and output
131
   vector_doubles, routes it to the algorithm */
132
/* the learnt weight vector and the outputs it gives on the data matrix are saved */
133
void ssl_train(struct data *Data,
134
	       struct options *Options,
135
	       struct vector_double *W, /* weight vector */
136
	       struct vector_double *O); /* output vector */
137

138
/* Main svmlin Subroutines */
139
/*ssl_predict: reads test inputs from input_file_name, a weight vector, and an
140
 uninitialized outputs vector. Performs */
141
void ssl_predict(char *inputs_file_name, const struct vector_double *Weights,
142
		 struct vector_double *Outputs);
143
/* ssl_evaluate: if test labels are given in the vector True, and predictions in vector Output,
144
   this code prints out various performance statistics. Currently only accuracy. */
145
void ssl_evaluate(struct vector_double *Outputs,struct vector_double *True);
146

147
/* svmlin algorithms and their subroutines */
148

149
/* Conjugate Gradient for Sparse Linear Least Squares Problems */
150
/* Solves: min_w 0.5*Options->lamda*w'*w + 0.5*sum_{i in Subset} Data->C[i] (Y[i]- w' x_i)^2 */
151
/* over a subset of examples x_i specified by vector_int Subset */
152
int CGLS(const struct data *Data,
153
	 const struct options *Options,
154
	 const struct vector_int *Subset,
155
	 struct vector_double *Weights,
156
	 struct vector_double *Outputs);
157

158
/* Linear Modified Finite Newton L2-SVM*/
159
/* Solves: min_w 0.5*Options->lamda*w'*w + 0.5*sum_i Data->C[i] max(0,1 - Y[i] w' x_i)^2 */
160
int L2_SVM_MFN(const struct data *Data,
161
	       struct options *Options,
162
	       struct vector_double *Weights,
163
	       struct vector_double *Outputs,
164
	       int ini); /* use ini=0 if no good starting guess for Weights, else 1 */
165
double line_search(double *w,
166
                   double *w_bar,
167
                   double lambda,
168
                   double *o,
169
                   double *o_bar,
170
                   double *Y,
171
                   double *C,
172
                   int d,
173
                   int l);
174

175
/* Transductive L2-SVM */
176
/* Solves : min_(w, Y[i],i in UNlabeled) 0.5*Options->lamda*w'*w + 0.5*(1/Data->l)*sum_{i in labeled} max(0,1 - Y[i] w' x_i)^2 + 0.5*(Options->lambda_u/Data->u)*sum_{i in UNlabeled} max(0,1 - Y[i] w' x_i)^2
177
 subject to: (1/Data->u)*sum_{i in UNlabeled} max(0,Y[i]) = Options->R */
178
int   TSVM_MFN(const struct data *Data,
179
	      struct options *Options,
180
	      struct vector_double *Weights,
181
	      struct vector_double *Outputs);
182
int switch_labels(double* Y, double* o, int* JU, int u, int S);
183

184
/* Deterministic Annealing*/
185
int DA_S3VM(struct data *Data,
186
	   struct options *Options,
187
	   struct vector_double *Weights,
188
	   struct vector_double *Outputs);
189
void optimize_p(const double* g, int u, double T, double r, double*p);
190
int optimize_w(const struct data *Data,
191
	       const  double *p,
192
	       struct options *Options,
193
	       struct vector_double *Weights,
194
	       struct vector_double *Outputs,
195
	       int ini);
196
double transductive_cost(double normWeights,double *Y, double *Outputs, int m, double lambda,double lambda_u);
197
double entropy(const  double *p, int u);
198
double KL(const  double *p, const  double *q, int u); /* KL-divergence */
199

200
#endif

Read our documentation on viewing source code .

Loading