Mercurial > hg > camir-aes2014

comparison toolboxes/SVM-light/src/svm_common.h @ 0:e9a9cd732c1e tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:e9a9cd732c1e
1 /************************************************************************/
2 /* */
3 /* svm_common.h */
4 /* */
5 /* Definitions and functions used in both svm_learn and svm_classify. */
6 /* */
7 /* Author: Thorsten Joachims */
8 /* Date: 02.07.02 */
9 /* */
10 /* Copyright (c) 2002 Thorsten Joachims - All rights reserved */
11 /* */
12 /* This software is available for non-commercial use only. It must */
13 /* not be modified and distributed without prior permission of the */
14 /* author. The author is not responsible for implications from the */
15 /* use of this software. */
16 /* */
17 /************************************************************************/
18
19 #ifndef SVM_COMMON
20 #define SVM_COMMON
21
22 # define MAXSHRINK 50000 /* maximum number of shrinking rounds */
23 # define MAXFEATNUM 99999999 /* maximum feature number (must be in
24 valid range of long int type!) */
25
26 # include <stdio.h>
27 # include <ctype.h>
28 # include <math.h>
29 # include <string.h>
30 # include <stdlib.h>
31 # include <time.h>
32 # include <float.h>
33
34 # define VERSION "V6.01"
35 # define VERSION_DATE "01.09.04"
36
37 # define CFLOAT float /* the type of float to use for caching */
38 /* kernel evaluations. Using float saves */
39 /* us some memory, but you can use double, too */
40 # define FNUM long /* the type used for storing feature ids */
41 # define FVAL float /* the type used for storing feature values */
42
43 # define LINEAR 0 /* linear kernel type */
44 # define POLY 1 /* polynoial kernel type */
45 # define RBF 2 /* rbf kernel type */
46 # define SIGMOID 3 /* sigmoid kernel type */
47
48 # define CLASSIFICATION 1 /* train classification model */
49 # define REGRESSION 2 /* train regression model */
50 # define RANKING 3 /* train ranking model */
51 # define OPTIMIZATION 4 /* train on general set of constraints */
52
53 typedef struct word {
54 FNUM wnum; /* word number */
55 FVAL weight; /* word weight */
56 } WORD;
57
58 typedef struct svector {
59 WORD *words; /* The features/values in the vector by
60 increasing feature-number. Feature
61 numbers that are skipped are
62 interpreted as having value zero. */
63 double twonorm_sq; /* The squared euclidian length of the
64 vector. Used to speed up the RBF kernel. */
65 char *userdefined; /* You can put additional information
66 here. This can be useful, if you are
67 implementing your own kernel that
68 does not work with feature/values
69 representations (for example a
70 string kernel). By default,
71 svm-light will put here the string
72 after the # sign from each line of
73 the input file. */
74 long kernel_id; /* Feature vectors with different
75 kernel_id's are orthogonal (ie. the
76 feature number do not match). This
77 is used for computing component
78 kernels for linear constraints which
79 are a sum of several different
80 weight vectors. (currently not
81 implemented). */
82 struct svector *next; /* Let's you set up a list of SVECTOR's
83 for linear constraints which are a
84 sum of multiple feature
85 vectors. List is terminated by
86 NULL. */
87 double factor; /* Factor by which this feature vector
88 is multiplied in the sum. */
89 } SVECTOR;
90
91 typedef struct doc {
92 long docnum; /* Document ID. This has to be the position of
93 the document in the training set array. */
94 long queryid; /* for learning rankings, constraints are
95 generated for documents with the same
96 queryID. */
97 double costfactor; /* Scales the cost of misclassifying this
98 document by this factor. The effect of this
99 value is, that the upper bound on the alpha
100 for this example is scaled by this factor.
101 The factors are set by the feature
102 'cost:<val>' in the training data. */
103 long slackid; /* Index of the slack variable
104 corresponding to this
105 constraint. All constraints with the
106 same slackid share the same slack
107 variable. This can only be used for
108 svm_learn_optimization. */
109 SVECTOR *fvec; /* Feature vector of the example. The
110 feature vector can actually be a
111 list of feature vectors. For
112 example, the list will have two
113 elements, if this DOC is a
114 preference constraint. The one
115 vector that is supposed to be ranked
116 higher, will have a factor of +1,
117 the lower ranked one should have a
118 factor of -1. */
119 } DOC;
120
121 typedef struct learn_parm {
122 long type; /* selects between regression and
123 classification */
124 double svm_c; /* upper bound C on alphas */
125 double eps; /* regression epsilon (eps=1.0 for
126 classification */
127 double svm_costratio; /* factor to multiply C for positive examples */
128 double transduction_posratio;/* fraction of unlabeled examples to be */
129 /* classified as positives */
130 long biased_hyperplane; /* if nonzero, use hyperplane w*x+b=0
131 otherwise w*x=0 */
132 long sharedslack; /* if nonzero, it will use the shared
133 slack variable mode in
134 svm_learn_optimization. It requires
135 that the slackid is set for every
136 training example */
137 long svm_maxqpsize; /* size q of working set */
138 long svm_newvarsinqp; /* new variables to enter the working set
139 in each iteration */
140 long kernel_cache_size; /* size of kernel cache in megabytes */
141 double epsilon_crit; /* tolerable error for distances used
142 in stopping criterion */
143 double epsilon_shrink; /* how much a multiplier should be above
144 zero for shrinking */
145 long svm_iter_to_shrink; /* iterations h after which an example can
146 be removed by shrinking */
147 long maxiter; /* number of iterations after which the
148 optimizer terminates, if there was
149 no progress in maxdiff */
150 long remove_inconsistent; /* exclude examples with alpha at C and
151 retrain */
152 long skip_final_opt_check; /* do not check KT-Conditions at the end of
153 optimization for examples removed by
154 shrinking. WARNING: This might lead to
155 sub-optimal solutions! */
156 long compute_loo; /* if nonzero, computes leave-one-out
157 estimates */
158 double rho; /* parameter in xi/alpha-estimates and for
159 pruning leave-one-out range [1..2] */
160 long xa_depth; /* parameter in xi/alpha-estimates upper
161 bounding the number of SV the current
162 alpha_t is distributed over */
163 char predfile[200]; /* file for predicitions on unlabeled examples
164 in transduction */
165 char alphafile[200]; /* file to store optimal alphas in. use
166 empty string if alphas should not be
167 output */
168
169 /* you probably do not want to touch the following */
170 double epsilon_const; /* tolerable error on eq-constraint */
171 double epsilon_a; /* tolerable error on alphas at bounds */
172 double opt_precision; /* precision of solver, set to e.g. 1e-21
173 if you get convergence problems */
174
175 /* the following are only for internal use */
176 long svm_c_steps; /* do so many steps for finding optimal C */
177 double svm_c_factor; /* increase C by this factor every step */
178 double svm_costratio_unlab;
179 double svm_unlabbound;
180 double *svm_cost; /* individual upper bounds for each var */
181 long totwords; /* number of features */
182 } LEARN_PARM;
183
184 typedef struct kernel_parm {
185 long kernel_type; /* 0=linear, 1=poly, 2=rbf, 3=sigmoid, 4=custom */
186 long poly_degree;
187 double rbf_gamma;
188 double coef_lin;
189 double coef_const;
190 char custom[50]; /* for user supplied kernel */
191 } KERNEL_PARM;
192
193 typedef struct model {
194 long sv_num;
195 long at_upper_bound;
196 double b;
197 DOC **supvec;
198 double *alpha;
199 long *index; /* index from docnum to position in model */
200 long totwords; /* number of features */
201 long totdoc; /* number of training documents */
202 KERNEL_PARM kernel_parm; /* kernel */
203
204 /* the following values are not written to file */
205 double loo_error,loo_recall,loo_precision; /* leave-one-out estimates */
206 double xa_error,xa_recall,xa_precision; /* xi/alpha estimates */
207 double *lin_weights; /* weights for linear case using
208 folding */
209 double maxdiff; /* precision, up to which this
210 model is accurate */
211 } MODEL;
212
213 typedef struct quadratic_program {
214 long opt_n; /* number of variables */
215 long opt_m; /* number of linear equality constraints */
216 double *opt_ce,*opt_ce0; /* linear equality constraints */
217 double *opt_g; /* hessian of objective */
218 double *opt_g0; /* linear part of objective */
219 double *opt_xinit; /* initial value for variables */
220 double *opt_low,*opt_up; /* box constraints */
221 } QP;
222
223 typedef struct kernel_cache {
224 long *index; /* cache some kernel evalutations */
225 CFLOAT *buffer; /* to improve speed */
226 long *invindex;
227 long *active2totdoc;
228 long *totdoc2active;
229 long *lru;
230 long *occu;
231 long elems;
232 long max_elems;
233 long time;
234 long activenum;
235 long buffsize;
236 } KERNEL_CACHE;
237
238
239 typedef struct timing_profile {
240 long time_kernel;
241 long time_opti;
242 long time_shrink;
243 long time_update;
244 long time_model;
245 long time_check;
246 long time_select;
247 } TIMING;
248
249 typedef struct shrink_state {
250 long *active;
251 long *inactive_since;
252 long deactnum;
253 double **a_history; /* for shrinking with non-linear kernel */
254 long maxhistory;
255 double *last_a; /* for shrinking with linear kernel */
256 double *last_lin; /* for shrinking with linear kernel */
257 } SHRINK_STATE;
258
259 double classify_example(MODEL *, DOC *);
260 double classify_example_linear(MODEL *, DOC *);
261 CFLOAT kernel(KERNEL_PARM *, DOC *, DOC *);
262 CFLOAT single_kernel(KERNEL_PARM *, SVECTOR *, SVECTOR *);
263 double custom_kernel(KERNEL_PARM *, SVECTOR *, SVECTOR *);
264 SVECTOR *create_svector(WORD *, char *, double);
265 SVECTOR *copy_svector(SVECTOR *);
266 void free_svector(SVECTOR *);
267 double sprod_ss(SVECTOR *, SVECTOR *);
268 SVECTOR* sub_ss(SVECTOR *, SVECTOR *);
269 SVECTOR* add_ss(SVECTOR *, SVECTOR *);
270 SVECTOR* add_list_ss(SVECTOR *);
271 void append_svector_list(SVECTOR *a, SVECTOR *b);
272 SVECTOR* smult_s(SVECTOR *, double);
273 int featvec_eq(SVECTOR *, SVECTOR *);
274 double model_length_s(MODEL *, KERNEL_PARM *);
275 void clear_vector_n(double *, long);
276 void add_vector_ns(double *, SVECTOR *, double);
277 double sprod_ns(double *, SVECTOR *);
278 void add_weight_vector_to_linear_model(MODEL *);
279 DOC *create_example(long, long, long, double, SVECTOR *);
280 void free_example(DOC *, long);
281 MODEL *read_model(char *);
282 MODEL *copy_model(MODEL *);
283 void free_model(MODEL *, int);
284 void read_documents(char *, DOC ***, double **, long *, long *);
285 int parse_document(char *, WORD *, double *, long *, long *, double *, long *, long, char **);
286 double *read_alphas(char *,long);
287 void nol_ll(char *, long *, long *, long *);
288 long minl(long, long);
289 long maxl(long, long);
290 long get_runtime(void);
291 int space_or_null(int);
292 void *my_malloc(size_t);
293 void copyright_notice(void);
294 # ifdef _MSC_VER
295 int isnan(double);
296 # endif
297
298 extern long verbosity; /* verbosity level (0-4) */
299 extern long kernel_cache_statistic;
300
301 #endif