Line data Source code
1 : /**
2 : * @file gensvm_gridsearch.c
3 : * @author G.J.J. van den Burg
4 : * @date 2014-01-07
5 : * @brief Functions for finding the optimal parameters for the dataset
6 : *
7 : * @details
8 : * The GenSVM algorithm takes a number of parameters. The functions in
9 : * this file are used to find the optimal parameters.
10 : *
11 : * @copyright
12 : Copyright 2016, G.J.J. van den Burg.
13 :
14 : This file is part of GenSVM.
15 :
16 : GenSVM is free software: you can redistribute it and/or modify
17 : it under the terms of the GNU General Public License as published by
18 : the Free Software Foundation, either version 3 of the License, or
19 : (at your option) any later version.
20 :
21 : GenSVM is distributed in the hope that it will be useful,
22 : but WITHOUT ANY WARRANTY; without even the implied warranty of
23 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 : GNU General Public License for more details.
25 :
26 : You should have received a copy of the GNU General Public License
27 : along with GenSVM. If not, see <http://www.gnu.org/licenses/>.
28 :
29 : */
30 :
31 : #include "gensvm_gridsearch.h"
32 :
33 : extern FILE *GENSVM_OUTPUT_FILE;
34 :
35 : /**
36 : * @brief Initialize a GenQueue from a Training instance
37 : *
38 : * @details
39 : * A Training instance describes the grid to search over. This funtion
40 : * creates all tasks that need to be performed and adds these to
41 : * a GenQueue. Each task contains a pointer to the train and test datasets
42 : * which are supplied. Note that the tasks are created in a specific order of
43 : * the parameters, to ensure that the GenModel::V of a previous parameter
44 : * set provides the best possible initial estimate of GenModel::V for the next
45 : * parameter set.
46 : *
47 : * @param[in] grid Training struct describing the grid search
48 : * @param[in] queue pointer to a GenQueue that will be used to
49 : * add the tasks to
50 : * @param[in] train_data GenData of the training set
51 : * @param[in] test_data GenData of the test set
52 : *
53 : */
54 2 : void gensvm_fill_queue(struct GenGrid *grid, struct GenQueue *queue,
55 : struct GenData *train_data, struct GenData *test_data)
56 : {
57 : long i, j, k;
58 2 : long N, cnt = 0;
59 2 : struct GenTask *task = NULL;
60 2 : queue->i = 0;
61 :
62 2 : N = grid->Np;
63 2 : N *= grid->Nl;
64 2 : N *= grid->Nk;
65 2 : N *= grid->Ne;
66 2 : N *= grid->Nw;
67 : // these parameters are not necessarily non-zero
68 2 : N *= grid->Ng > 0 ? grid->Ng : 1;
69 2 : N *= grid->Nc > 0 ? grid->Nc : 1;
70 2 : N *= grid->Nd > 0 ? grid->Nd : 1;
71 :
72 2 : queue->tasks = Calloc(struct GenTask *, N);
73 2 : queue->N = N;
74 :
75 : // initialize all tasks
76 80 : for (i=0; i<N; i++) {
77 78 : task = gensvm_init_task();
78 78 : task->ID = i;
79 78 : task->train_data = train_data;
80 78 : task->test_data = test_data;
81 78 : task->folds = grid->folds;
82 78 : task->kerneltype = grid->kerneltype;
83 78 : queue->tasks[i] = task;
84 : }
85 :
86 : // These loops mimick a large nested for loop. The advantage is that
87 : // Nd, Nc and Ng which are on the outside of the nested for loop can
88 : // now be zero, without large modification (see below). Whether this
89 : // is indeed better than the nested for loop has not been tested.
90 2 : cnt = 1;
91 2 : i = 0;
92 30 : while (i < N) {
93 104 : for (j=0; j<grid->Np; j++) {
94 156 : for (k=0; k<cnt; k++) {
95 78 : queue->tasks[i]->p = grid->ps[j];
96 78 : i++;
97 : }
98 : }
99 : }
100 :
101 2 : cnt *= grid->Np;
102 2 : i = 0;
103 17 : while (i < N) {
104 39 : for (j=0; j<grid->Nl; j++) {
105 104 : for (k=0; k<cnt; k++) {
106 156 : queue->tasks[i]->lambda =
107 78 : grid->lambdas[j];
108 78 : i++;
109 : }
110 : }
111 : }
112 :
113 2 : cnt *= grid->Nl;
114 2 : i = 0;
115 17 : while (i < N) {
116 26 : for (j=0; j<grid->Nk; j++) {
117 91 : for (k=0; k<cnt; k++) {
118 78 : queue->tasks[i]->kappa = grid->kappas[j];
119 78 : i++;
120 : }
121 : }
122 : }
123 :
124 2 : cnt *= grid->Nk;
125 2 : i = 0;
126 17 : while (i < N) {
127 26 : for (j=0; j<grid->Nw; j++) {
128 91 : for (k=0; k<cnt; k++) {
129 156 : queue->tasks[i]->weight_idx =
130 78 : grid->weight_idxs[j];
131 78 : i++;
132 : }
133 : }
134 : }
135 :
136 2 : cnt *= grid->Nw;
137 2 : i = 0;
138 17 : while (i < N) {
139 26 : for (j=0; j<grid->Ne; j++) {
140 91 : for (k=0; k<cnt; k++) {
141 78 : queue->tasks[i]->epsilon = grid->epsilons[j];
142 78 : i++;
143 : }
144 : }
145 : }
146 :
147 2 : cnt *= grid->Ne;
148 2 : i = 0;
149 10 : while (i < N && grid->Ng > 0) {
150 18 : for (j=0; j<grid->Ng; j++) {
151 84 : for (k=0; k<cnt; k++) {
152 72 : queue->tasks[i]->gamma = grid->gammas[j];
153 72 : i++;
154 : }
155 : }
156 : }
157 :
158 2 : cnt *= grid->Ng > 0 ? grid->Ng : 1;
159 2 : i = 0;
160 6 : while (i < N && grid->Nc > 0) {
161 8 : for (j=0; j<grid->Nc; j++) {
162 78 : for (k=0; k<cnt; k++) {
163 72 : queue->tasks[i]->coef = grid->coefs[j];
164 72 : i++;
165 : }
166 : }
167 : }
168 :
169 2 : cnt *= grid->Nc > 0 ? grid->Nc : 1;
170 2 : i = 0;
171 5 : while (i < N && grid->Nd > 0) {
172 3 : for (j=0; j<grid->Nd; j++) {
173 74 : for (k=0; k<cnt; k++) {
174 72 : queue->tasks[i]->degree = grid->degrees[j];
175 72 : i++;
176 : }
177 : }
178 : }
179 2 : }
180 :
181 : /**
182 : * @brief Check if the kernel parameters change between tasks
183 : *
184 : * @details
185 : * In the current strategy for training the kernel matrix is decomposed once,
186 : * and tasks with the same kernel settings are performed sequentially. When a
187 : * task needs to be done with different kernel parameters, the kernel matrix
188 : * needs to be recalculated. This function is used to check whether this is
189 : * the case.
190 : *
191 : * @param[in] newtask the next task
192 : * @param[in] oldtask the old task
193 : * @return whether the kernel needs to be reevaluated
194 : */
195 9 : bool gensvm_kernel_changed(struct GenTask *newtask, struct GenTask *oldtask)
196 : {
197 9 : if (oldtask == NULL)
198 1 : return true;
199 8 : if (newtask->kerneltype != oldtask->kerneltype) {
200 1 : return true;
201 7 : } else if (newtask->kerneltype == K_POLY) {
202 2 : if (newtask->gamma != oldtask->gamma)
203 0 : return true;
204 2 : if (newtask->coef != oldtask->coef)
205 0 : return true;
206 2 : if (newtask->degree != oldtask->degree)
207 1 : return true;
208 1 : return false;
209 5 : } else if (newtask->kerneltype == K_RBF) {
210 2 : if (newtask->gamma != oldtask->gamma)
211 1 : return true;
212 1 : return false;
213 3 : } else if (newtask->kerneltype == K_SIGMOID) {
214 2 : if (newtask->gamma != oldtask->gamma)
215 0 : return true;
216 2 : if (newtask->coef != oldtask->coef)
217 1 : return true;
218 1 : return false;
219 : }
220 1 : return false;
221 : }
222 :
223 : /**
224 : * @brief Compute the kernels for the folds of the train and test datasets
225 : *
226 : * @details
227 : * When the kernel parameters change in a kernel grid search, the kernel
228 : * pre- and post-processing has to be done for the new kernel parameters. This
229 : * is done here for each of the folds. Each of the training folds is
230 : * preprocessed, and each of the test folds is postprocessed.
231 : *
232 : * @param[in] folds number of cross validation folds
233 : * @param[in] model GenModel with new kernel parameters
234 : * @param[in,out] train_folds array of train datasets
235 : * @param[in,out] test_folds array of test datasets
236 : *
237 : */
238 0 : void gensvm_kernel_folds(long folds, struct GenModel *model,
239 : struct GenData **train_folds, struct GenData **test_folds)
240 : {
241 : long f;
242 :
243 0 : if (model->kerneltype != K_LINEAR)
244 0 : note("Computing kernel ... ");
245 0 : for (f=0; f<folds; f++) {
246 0 : if (train_folds[f]->Z != train_folds[f]->RAW)
247 0 : free(train_folds[f]->Z);
248 0 : if (test_folds[f]->Z != test_folds[f]->RAW)
249 0 : free(test_folds[f]->Z);
250 0 : gensvm_kernel_preprocess(model, train_folds[f]);
251 0 : gensvm_kernel_postprocess(model, train_folds[f],
252 0 : test_folds[f]);
253 : }
254 0 : if (model->kerneltype != K_LINEAR)
255 0 : note("done.\n");
256 0 : }
257 :
258 : /**
259 : * @brief Run the grid search for a GenQueue
260 : *
261 : * @details
262 : * Given a GenQueue of GenTask struct to be trained, a grid search is launched to
263 : * find the optimal parameter configuration. As is also done within
264 : * cross_validation(), the optimal weights of one parameter set are used as
265 : * initial estimates for GenModel::V in the next parameter set. Note that to
266 : * optimally exploit this feature of the optimization algorithm, the order in
267 : * which tasks are considered is important. This is considered in
268 : * make_queue().
269 : *
270 : * The performance found by cross validation is stored in the GenTask struct.
271 : *
272 : * @param[in,out] q GenQueue with GenTask instances to run
273 : */
274 0 : void gensvm_train_queue(struct GenQueue *q)
275 : {
276 : long f, folds;
277 0 : double perf, duration, current_max = 0;
278 0 : struct GenTask *task = get_next_task(q);
279 0 : struct GenTask *prevtask = NULL;
280 0 : struct GenModel *model = gensvm_init_model();
281 : struct timespec main_s, main_e, loop_s, loop_e;
282 :
283 0 : folds = task->folds;
284 :
285 0 : model->n = 0;
286 0 : model->m = task->train_data->m;
287 0 : model->K = task->train_data->K;
288 0 : gensvm_allocate_model(model);
289 0 : gensvm_init_V(NULL, model, task->train_data);
290 :
291 0 : long *cv_idx = Calloc(long, task->train_data->n);
292 0 : gensvm_make_cv_split(task->train_data->n, task->folds, cv_idx);
293 :
294 0 : struct GenData **train_folds = Malloc(struct GenData *, task->folds);
295 0 : struct GenData **test_folds = Malloc(struct GenData *, task->folds);
296 0 : for (f=0; f<folds; f++) {
297 0 : train_folds[f] = gensvm_init_data();
298 0 : test_folds[f] = gensvm_init_data();
299 0 : gensvm_get_tt_split(task->train_data, train_folds[f],
300 0 : test_folds[f], cv_idx, f);
301 : }
302 :
303 0 : Timer(main_s);
304 0 : while (task) {
305 0 : gensvm_task_to_model(task, model);
306 0 : if (gensvm_kernel_changed(task, prevtask)) {
307 0 : gensvm_kernel_folds(task->folds, model, train_folds,
308 : test_folds);
309 : }
310 :
311 0 : Timer(loop_s);
312 0 : perf = gensvm_cross_validation(model, train_folds, test_folds,
313 0 : folds, task->train_data->n);
314 0 : Timer(loop_e);
315 :
316 0 : current_max = maximum(current_max, perf);
317 0 : duration = gensvm_elapsed_time(&loop_s, &loop_e);
318 :
319 0 : gensvm_gridsearch_progress(task, q->N, perf, duration,
320 : current_max);
321 :
322 0 : q->tasks[task->ID]->performance = perf;
323 0 : prevtask = task;
324 0 : task = get_next_task(q);
325 : }
326 0 : Timer(main_e);
327 :
328 0 : note("\nTotal elapsed training time: %8.8f seconds\n",
329 : gensvm_elapsed_time(&main_s, &main_e));
330 :
331 0 : gensvm_free_model(model);
332 0 : for (f=0; f<folds; f++) {
333 0 : gensvm_free_data(train_folds[f]);
334 0 : gensvm_free_data(test_folds[f]);
335 : }
336 0 : free(train_folds);
337 0 : free(test_folds);
338 0 : free(cv_idx);
339 0 : }
340 :
341 : /**
342 : * @brief Print the description of the current task on screen
343 : *
344 : * @details
345 : * To track the progress of the grid search the parameters of the current task
346 : * are written to the output specified in GENSVM_OUTPUT_FILE. Since the
347 : * parameters differ with the specified kernel, this function writes a
348 : * parameter string depending on which kernel is used.
349 : *
350 : * @param[in] task the GenTask specified
351 : * @param[in] N total number of tasks
352 : * @param[in] perf performance of the current task
353 : * @param[in] duration time duration of the current task
354 : * @param[in] current_max current best performance
355 : *
356 : */
357 4 : void gensvm_gridsearch_progress(struct GenTask *task, long N, double perf,
358 : double duration, double current_max)
359 : {
360 : char buffer[GENSVM_MAX_LINE_LENGTH];
361 4 : sprintf(buffer, "(%03li/%03li)\t", task->ID+1, N);
362 4 : if (task->kerneltype == K_POLY)
363 1 : sprintf(buffer + strlen(buffer), "d = %2.2f\t", task->degree);
364 4 : if (task->kerneltype == K_POLY || task->kerneltype == K_SIGMOID)
365 2 : sprintf(buffer + strlen(buffer), "c = %2.2f\t", task->coef);
366 6 : if (task->kerneltype == K_POLY || task->kerneltype == K_SIGMOID ||
367 2 : task->kerneltype == K_RBF)
368 3 : sprintf(buffer + strlen(buffer), "g = %3.3f\t", task->gamma);
369 4 : sprintf(buffer + strlen(buffer), "eps = %g\tw = %i\tk = %2.2f\t"
370 : "l = %f\tp = %2.2f\t", task->epsilon,
371 : task->weight_idx, task->kappa, task->lambda, task->p);
372 4 : note(buffer);
373 4 : note("\t%3.3f%% (%3.3fs)\t(best = %3.3f%%)\n", perf, duration,
374 : current_max);
375 4 : }
|
