ssl.h at a5c4412 ⋅ quanteda/quanteda.textmodels

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

      This file is part of SVM-lin.

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

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

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

using namespace std;

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

#define VERBOSE_CGLS 0

/* Data: Input examples are stored in sparse (Compressed Row Storage) format */
struct data
{
  int m; /* number of examples */
  int l; /* number of labeled examples */
  int u; /* number of unlabeled examples l+u = m */
  int n; /* number of features */
  int nz; /* number of non-zeros */
  double *val; /* data values (nz elements) [CRS format] */
  int *rowptr; /* n+1 vector [CRS format] */
  int *colind; /* nz elements [CRS format] */
  double *Y;   /* labels */
  double *C;   /* cost associated with each example */
};

struct vector_double /* defines a vector of doubles */
{
  int d; /* number of elements */
  double *vec; /* ptr to vector elements*/
};



struct vector_int /* defines a vector of ints for index subsets */
{
  int d; /* number of elements */
  int *vec; /* ptr to vector elements */
};

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

struct options
{
  /* user options */
  int algo; /* 1 to 4 for RLS,SVM,TSVM,DASVM */
  double lambda; /* regularization parameter */
  double lambda_u; /* regularization parameter over unlabeled examples */
  int S; /* maximum number of TSVM switches per fixed-weight label optimization */
  double R; /* expected fraction of unlabeled examples in positive class */
  double Cp; /* cost for positive examples */
  double Cn; /* cost for negative examples */
  /*  internal optimization options */
  double epsilon; /* all tolerances */
  int cgitermax;  /* max iterations for CGLS */
  int mfnitermax; /* max iterations for L2_SVM_MFN */
  bool verbose; /* Should the output be verbose? */
};

class timer { /* to output run time */
protected:
  double start, finish;
public:
  vector<double> times;
  void record() {
    times.push_back(time());
  }
  void reset_vectors() {
    times.erase(times.begin(), times.end());
  }
  void restart() { start = clock(); }
  void stop() { finish = clock(); }
  double time() const { return ((double)(finish - start))/CLOCKS_PER_SEC; }
};
class Delta { /* used in line search */
 public:
   Delta() {delta=0.0; index=0;s=0;};
   double delta;
   int index;
   int s;
};
inline bool operator<(const Delta& a , const Delta& b) { return (a.delta < b.delta);}

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

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

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

/* svmlin algorithms and their subroutines */

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

/* Linear Modified Finite Newton L2-SVM*/
/* 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 */
int L2_SVM_MFN(const struct data *Data,
	       struct options *Options,
	       struct vector_double *Weights,
	       struct vector_double *Outputs,
	       int ini); /* use ini=0 if no good starting guess for Weights, else 1 */
double line_search(double *w,
                   double *w_bar,
                   double lambda,
                   double *o,
                   double *o_bar,
                   double *Y,
                   double *C,
                   int d,
                   int l);

/* Transductive L2-SVM */
/* 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
 subject to: (1/Data->u)*sum_{i in UNlabeled} max(0,Y[i]) = Options->R */
int   TSVM_MFN(const struct data *Data,
	      struct options *Options,
	      struct vector_double *Weights,
	      struct vector_double *Outputs);
int switch_labels(double* Y, double* o, int* JU, int u, int S);

/* Deterministic Annealing*/
int DA_S3VM(struct data *Data,
	   struct options *Options,
	   struct vector_double *Weights,
	   struct vector_double *Outputs);
void optimize_p(const double* g, int u, double T, double r, double*p);
int optimize_w(const struct data *Data,
	       const  double *p,
	       struct options *Options,
	       struct vector_double *Weights,
	       struct vector_double *Outputs,
	       int ini);
double transductive_cost(double normWeights,double *Y, double *Outputs, int m, double lambda,double lambda_u);
double entropy(const  double *p, int u);
double KL(const  double *p, const  double *q, int u); /* KL-divergence */

#endif

Read our documentation on viewing source code .

Navigation	Overlay
`t` Navigate files	`h` Toggle hits
`y` Change url to tip of branch	`m` Toggle misses
`b / v` Jump to prev/next hit line	`p` Toggle partial
`z / x` Jump to prev/next missed or partial line	`1..9` Toggle flags
`shift + o` Open current page in GitHub	`a` Toggle all on
`/ or ?` Show keyboard shortcuts dialog	`c` Toggle context lines or commits

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.5Options->lamdaw'w + 0.5sum_{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.5Options->lamdaw'w + 0.5sum_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.5Options->lamdaw'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