diff options
| -rw-r--r-- | Makefile | 11 | ||||
| -rw-r--r-- | include/MSVMMaj.h | 1 | ||||
| -rw-r--r-- | include/libMSVMMaj.h | 3 | ||||
| -rw-r--r-- | include/matrix.h | 12 | ||||
| -rw-r--r-- | include/util.h | 10 | ||||
| -rw-r--r-- | src/libMSVMMaj.c | 120 | ||||
| -rw-r--r-- | src/matrix.c | 76 | ||||
| -rw-r--r-- | src/predMSVMMaj.c | 100 | ||||
| -rw-r--r-- | src/trainMSVMMaj.c | 24 | ||||
| -rw-r--r-- | src/util.c | 63 |
10 files changed, 322 insertions, 98 deletions
@@ -10,11 +10,11 @@ all: $(EXECS) override LDFLAGS+=-lblas -llapack -lm -trainMSVMMaj: src/trainMSVMMaj.c src/libMSVMMaj.o src/util.o - $(CC) -o trainMSVMMaj src/trainMSVMMaj.c src/libMSVMMaj.o src/util.o $(CFLAGS) $(INCLUDE) $(LDFLAGS) +trainMSVMMaj: src/trainMSVMMaj.c src/libMSVMMaj.o src/util.o src/matrix.o + $(CC) -o trainMSVMMaj src/trainMSVMMaj.c src/libMSVMMaj.o src/util.o src/matrix.o $(CFLAGS) $(INCLUDE) $(LDFLAGS) -predMSVMMaj: src/predMSVMMaj.c src/libMSVMMaj.o src/util.o - $(CC) -o predMSVMMaj src/predMSVMMaj.c src/libMSVMMaj.o src/util.o $(CFLAGS) $(INCLUDE) $(LDFLAGS) +predMSVMMaj: src/predMSVMMaj.c src/libMSVMMaj.o src/util.o src/matrix.o + $(CC) -o predMSVMMaj src/predMSVMMaj.c src/libMSVMMaj.o src/util.o src/matrix.o $(CFLAGS) $(INCLUDE) $(LDFLAGS) src/libMSVMMaj.o: $(CC) -c -o src/libMSVMMaj.o src/libMSVMMaj.c $(CFLAGS) $(INCLUDE) @@ -22,5 +22,8 @@ src/libMSVMMaj.o: src/util.o: $(CC) -c -o src/util.o src/util.c $(CFLAGS) $(INCLUDE) +src/matrix.o: + $(CC) -c -o src/matrix.o src/matrix.c $(CFLAGS) $(INCLUDE) + clean: rm -rf $(EXECS) *.o src/*.o diff --git a/include/MSVMMaj.h b/include/MSVMMaj.h index fbcea8c..021a341 100644 --- a/include/MSVMMaj.h +++ b/include/MSVMMaj.h @@ -24,7 +24,6 @@ struct Model { double *H; double *R; double *rho; - double training_error; char *data_file; }; diff --git a/include/libMSVMMaj.h b/include/libMSVMMaj.h index 74f1e10..3e0f25c 100644 --- a/include/libMSVMMaj.h +++ b/include/libMSVMMaj.h @@ -3,7 +3,9 @@ #include <math.h> #include <cblas.h> #include <string.h> + #include "util.h" +#include "matrix.h" void simplex_gen(long K, double *U); void category_matrix(struct Model *model, struct Data *data); @@ -21,6 +23,7 @@ void main_loop(struct Model *model, struct Data *data); int dposv(char UPLO, int N, int NRHS, double *A, int LDA, double *B, int LDB); +void seed_model_V(struct Model *from_model, struct Model *to_model); void initialize_weights(struct Data *data, struct Model *model); void predict_labels(struct Data *data, struct Model *model, long *predy); diff --git a/include/matrix.h b/include/matrix.h new file mode 100644 index 0000000..4157475 --- /dev/null +++ b/include/matrix.h @@ -0,0 +1,12 @@ + +void matrix_set(double *M, long cols, long i, long j, double val); +void matrix_add(double *M, long cols, long i, long j, double val); +void matrix_mul(double *M, long cols, long i, long j, double val); + +double matrix_get(double *M, long cols, long i, long j); + +void matrix3_set(double *M, long N2, long N3, long i, long j, long k, + double val); +double matrix3_get(double *M, long N2, long N3, long i, long j, long k); + +void print_matrix(double *M, long rows, long cols); diff --git a/include/util.h b/include/util.h index ec415ac..2cf36e8 100644 --- a/include/util.h +++ b/include/util.h @@ -27,17 +27,7 @@ void info(const char *fmt,...); double rnd(); -void matrix_set(double *M, long cols, long i, long j, double val); -void matrix_add(double *M, long cols, long i, long j, double val); -void matrix_mult(double *M, long cols, long i, long j, double val); -double matrix_get(double *M, long cols, long i, long j); - -void matrix3_set(double *M, long N2, long N3, long i, long j, long k, double val); -double matrix3_get(double *M, long N2, long N3, long i, long j, long k); - void allocate_model(struct Model *model); void free_model(struct Model *model); void free_data(struct Data *data); -void print_matrix(double *M, long rows, long cols); - diff --git a/src/libMSVMMaj.c b/src/libMSVMMaj.c index 64c7a26..202e228 100644 --- a/src/libMSVMMaj.c +++ b/src/libMSVMMaj.c @@ -1,10 +1,33 @@ +/** + * @file libMSVMMaj.c + * @author Gertjan van den Burg (burg@ese.eur.nl) + * @date August 8, 2013 + * @brief Main functions for the MSVMMaj algorithm + * + * @details + * The functions in this file are all functions needed + * to calculate the optimal separation boundaries for + * a multiclass classification problem, using the + * MSVMMaj algorithm. + * + */ + #include "libMSVMMaj.h" -/* - Generate the simplex matrix. A pointer to the matrix - must be given, and the matrix must have been - allocated. -*/ +/** + * @name simplex_gen + * @brief Generate matrix of simplex vertex coordinates + * @ingroup libMSVMMaj + * + * Generate the simplex matrix. Each row of the created + * matrix contains the coordinate vector of a single + * vertex of the K-simplex in K-1 dimensions. The simplex + * generated is a special simplex with edges of length 1. + * The simplex matrix U must already have been allocated. + * + * @param [in] K number of classes + * @param [in,out] U simplex matrix of size K * (K-1) + */ void simplex_gen(long K, double *U) { long i, j; @@ -21,7 +44,7 @@ void simplex_gen(long K, double *U) } } -/* +/*! Generate the category matrix R. The category matrix has 1's everywhere except at the column corresponding to the label of instance i. */ @@ -40,6 +63,9 @@ void category_matrix(struct Model *model, struct Data *dataset) } } +/*! + * Simplex diff + */ void simplex_diff(struct Model *model, struct Data *data) { long i, j, k; @@ -59,7 +85,7 @@ void simplex_diff(struct Model *model, struct Data *data) } } -/* +/*! Calculate the errors Q based on the current value of V. It is assumed that the memory for Q has already been allocated. In addition, the matrix ZV is calculated here. It is assigned to a @@ -103,7 +129,7 @@ void calculate_errors(struct Model *model, struct Data *data, double *ZV) } } -/* +/*! Calculate the Huber hinge errors for each error in the matrix Q. */ void calculate_huber(struct Model *model) @@ -125,7 +151,7 @@ void calculate_huber(struct Model *model) } } -/* +/*! Calculate the value of the loss function based on the current estimate of V. */ @@ -167,9 +193,46 @@ double get_msvmmaj_loss(struct Model *model, struct Data *data, double *ZV) return loss; } -/* + +/** + * @name seed_model_V + * @brief seed the matrix V from an existing model or using rand + * @ingroup libMSVMMaj + * + * The matrix V must be seeded before the main_loop() can start. + * This can be done by either seeding it with random numbers or + * using the solution from a previous model on the same dataset + * as initial seed. The latter option usually allows for a + * significant improvement in the number of iterations necessary + * because the seeded model V is closer to the optimal V. + * + * @param [in] from_model model from which to copy V + * @param [in,out] to_model model to which V will be copied + */ +void seed_model_V(struct Model *from_model, struct Model *to_model) +{ + long i, j; + long m = to_model->m; + long K = to_model->K; + double value; + + if (from_model == NULL) { + for (i=0; i<m+1; i++) + for (j=0; j<K-1; j++) + matrix_set(to_model->V, K-1, i, j, -1.0+2.0*rnd()); + } else { + for (i=0; i<m+1; i++) + for (j=0; j<K-1; j++) { + value = matrix_get(from_model->V, K-1, i, j); + matrix_set(to_model->V, K-1, i, j, value); + } + } +} + +/*! Training loop is defined here. */ + void main_loop(struct Model *model, struct Data *data) { long i, j, it = 0; @@ -203,12 +266,6 @@ void main_loop(struct Model *model, struct Data *data) simplex_diff(model, data); category_matrix(model, data); - // Initialize V - for (i=0; i<m+1; i++) - for (j=0; j<K-1; j++) - matrix_set(model->V, K-1, i, j, 1.0); - //matrix_set(model->V, K-1, i, j, -1.0+2.0*rnd()); - L = get_msvmmaj_loss(model, data, ZV); Lbar = L + 2.0*model->epsilon*L; @@ -244,6 +301,10 @@ void main_loop(struct Model *model, struct Data *data) free(ZAZVT); } +/*! + * Step doubling + */ + void step_doubling(struct Model *model) { long i, j; @@ -253,12 +314,16 @@ void step_doubling(struct Model *model) for (i=0; i<m+1; i++) { for (j=0; j<K-1; j++) { - matrix_mult(model->V, K-1, i, j, 2.0); + matrix_mul(model->V, K-1, i, j, 2.0); matrix_add(model->V, K-1, i, j, -matrix_get(model->Vbar, K-1, i, j)); } } } +/*! + * dposv + */ + int dposv(char UPLO, int N, int NRHS, double *A, int LDA, double *B, int LDB) { @@ -269,6 +334,10 @@ int dposv(char UPLO, int N, int NRHS, double *A, int LDA, double *B, return INFO; } +/*! + * dsysv + */ + int dsysv(char UPLO, int N, int NRHS, double *A, int LDA, int *IPIV, double *B, int LDB, double *WORK, int LWORK) { @@ -280,6 +349,10 @@ int dsysv(char UPLO, int N, int NRHS, double *A, int LDA, int *IPIV, return INFO; } +/*! + * msvmmaj_update + */ + void msvmmaj_update(struct Model *model, struct Data *data, double *B, double *ZAZ, double *ZAZV, double *ZAZVT) { @@ -526,6 +599,10 @@ void msvmmaj_update(struct Model *model, struct Data *data, } } +/*! + * initialize_weights + */ + void initialize_weights(struct Data *data, struct Model *model) { long *groups; @@ -550,9 +627,12 @@ void initialize_weights(struct Data *data, struct Model *model) fprintf(stderr, "Unknown weight specification.\n"); exit(1); } - } +/*! + * predict_labels + */ + void predict_labels(struct Data *data, struct Model *model, long *predy) { long i, j, k, label; @@ -609,6 +689,10 @@ void predict_labels(struct Data *data, struct Model *model, long *predy) free(S); } +/*! + * prediction_perf + */ + double prediction_perf(struct Data *data, long *predy) { long i, correct = 0; diff --git a/src/matrix.c b/src/matrix.c new file mode 100644 index 0000000..fc29ecf --- /dev/null +++ b/src/matrix.c @@ -0,0 +1,76 @@ +/** + * @file matrix.c + * @author Gertjan van den Burg (burg@ese.eur.nl) + * @date August 8, 2013 + * @brief Functions facilitating matrix access + * + * @details + * The functions contained in this file are used when + * accessing or writing to matrices. Seperate functions + * exist of adding and multiplying existing matrix + * elements, to ensure this is done in place. + * + */ + +#include "matrix.h" + +/** + * @name matrix_set + * @brief Set element of matrix + * @ingroup matrix + * + * Row-Major order is used to set a matrix element. Since matrices + * of type double are most common in MSVMMaj, this function only + * deals with that type. + * + * @param [in] M matrix to set element of + * @param [in] cols number of columns of M + * @param [in] i row index of element to write to + * @param [in] j column index of element to write to + * @param [out] val value to write to specified element of M + */ +void matrix_set(double *M, long cols, long i, long j, double val) +{ + M[i*cols+j] = val; +} + +double matrix_get(double *M, long cols, long i, long j) +{ + return M[i*cols+j]; +} + +void matrix_add(double *M, long cols, long i, long j, double val) +{ + M[i*cols+j] += val; +} + +void matrix_mul(double *M, long cols, long i, long j, double val) +{ + M[i*cols+j] *= val; +} + +void matrix3_set(double *M, long N2, long N3, long i, long j, + long k, double val) +{ + M[k+N3*(j+N2*i)] = val; +} + +double matrix3_get(double *M, long N2, long N3, long i, long j, + long k) +{ + return M[k+N3*(j+N2*i)]; +} + + +void print_matrix(double *M, long rows, long cols) +{ + long i, j; + + for (i=0; i<rows; i++) { + for (j=0; j<cols; j++) + info("%8.8f ", matrix_get(M, cols, i, j)); + info("\n"); + } + info("\n"); +} + diff --git a/src/predMSVMMaj.c b/src/predMSVMMaj.c new file mode 100644 index 0000000..5d26dc3 --- /dev/null +++ b/src/predMSVMMaj.c @@ -0,0 +1,100 @@ +#include "libMSVMMaj.h" + +#define MINARGS 3 + +void print_null(const char *s) {} +void exit_with_help(); +void parse_command_line(int argc, char **argv, struct Model *model, + char *input_filename, char *output_filename, + char *model_filename); + +void exit_with_help() +{ + printf("This is MSVMMaj, version %1.1f\n\n", VERSION); + printf("Usage: predMSVMMaj [options] test_data_file model_file\n"); + printf("Options:\n"); + printf("-o output_file : write output to file\n"); + printf("-q : quiet mode (no output)\n"); + exit(0); +} + +int main(int argc, char **argv) +{ + long *predy; + double performance; + + char input_filename[MAX_LINE_LENGTH]; + char model_filename[MAX_LINE_LENGTH]; + char output_filename[MAX_LINE_LENGTH];; + + struct Model *model = Malloc(struct Model, 1); + struct Data *data = Malloc(struct Data, 1); + + if (argc < MINARGS || check_argv(argc, argv, "-help") || check_argv_eq(argc, argv, "-h") ) + exit_with_help(); + parse_command_line(argc, argv, model, input_filename, output_filename, + model_filename); + + // TODO: make sure that read_data allows for files without labels + read_data(data, input_filename); + read_model(model, model_filename); + + // check if the number of attributes in data equals that in model + if (data->m != model->m) { + fprintf(stderr, "Error: number of attributes in data (%li) " + "does not equal the number of attributes in " + "model (%li)\n", data->m, model->m); + exit(1); + } + + predy = Calloc(long, data->n); + predict_labels(data, model, predy); + if (data->y != NULL) { + performance = prediction_perf(data, predy); + info("Predictive performance: %3.2f%%\n", performance); + } + + if (check_argv_eq(argc, argv, "-o")) { + write_predictions(data, predy, output_filename); + info("Predictions written to: %s\n", output_filename); + } + + free_model(model); + free_data(data); + free(predy); + + return 0; +} + +void parse_command_line(int argc, char **argv, struct Model *model, + char *input_filename, char *output_filename, char *model_filename) +{ + int i; + void (*print_func)(const char*) = NULL; + + for (i=1; i<argc; i++) { + if (argv[i][0] != '-') break; + if (++i >= argc) + exit_with_help(); + switch (argv[i-1][1]) { + case 'o': + strcpy(output_filename, argv[i]); + break; + case 'q': + print_func = &print_null; + i--; + default: + fprintf(stderr, "Unknown option: -%c\n", argv[i-1][1]); + exit_with_help(); + } + } + + set_print_string_function(print_func); + + if (i >= argc) + exit_with_help(); + + strcpy(input_filename, argv[i]); + i++; + strcpy(model_filename, argv[i]); +} diff --git a/src/trainMSVMMaj.c b/src/trainMSVMMaj.c index 311675c..5a403be 100644 --- a/src/trainMSVMMaj.c +++ b/src/trainMSVMMaj.c @@ -5,7 +5,7 @@ void print_null(const char *s) {} void exit_with_help(); void parse_command_line(int argc, char **argv, struct Model *model, - char *input_filename, char *output_filename); + char *input_filename, char *output_filename, char *model_filename); void exit_with_help() { @@ -17,6 +17,7 @@ void exit_with_help() printf("-h | -help : print this help.\n"); printf("-k kappa : set the value of kappa used in the Huber hinge\n"); printf("-l lambda : set the value of lambda (lambda > 0)\n"); + printf("-m model_file : use previous model as seed for W and t\n"); printf("-o output_file : write output to file\n"); printf("-p p-value : set the value of p in the lp norm (1.0 <= p <= 2.0)\n"); printf("-q : quiet mode (no output)\n"); @@ -32,13 +33,14 @@ int main(int argc, char **argv) { char input_filename[MAX_LINE_LENGTH]; char model_filename[MAX_LINE_LENGTH]; + char output_filename[MAX_LINE_LENGTH]; struct Model *model = Malloc(struct Model, 1); struct Data *data = Malloc(struct Data, 1); if (argc < MINARGS || check_argv(argc, argv, "-help") || check_argv_eq(argc, argv, "-h") ) exit_with_help(); - parse_command_line(argc, argv, model, input_filename, model_filename); + parse_command_line(argc, argv, model, input_filename, output_filename, model_filename); // read data file read_data(data, input_filename); @@ -53,13 +55,22 @@ int main(int argc, char **argv) allocate_model(model); initialize_weights(data, model); + if (check_argv_eq(argc, argv, "-m")) { + struct Model *seed_model = Malloc(struct Model, 1); + read_model(seed_model, model_filename); + seed_model_V(seed_model, model); + free_model(seed_model); + } else { + seed_model_V(NULL, model); + } + // start training main_loop(model, data); // write_model to file if (check_argv_eq(argc, argv, "-o")) { - write_model(model, model_filename); - info("Output written to %s\n", model_filename); + write_model(model, output_filename); + info("Output written to %s\n", output_filename); } // free model and data @@ -70,7 +81,7 @@ int main(int argc, char **argv) } void parse_command_line(int argc, char **argv, struct Model *model, - char *input_filename, char *output_filename) + char *input_filename, char *output_filename, char *model_filename) { int i; void (*print_func)(const char*) = NULL; @@ -98,6 +109,9 @@ void parse_command_line(int argc, char **argv, struct Model *model, case 'l': model->lambda = atof(argv[i]); break; + case 'm': + strcpy(model_filename, argv[i]); + break; case 'o': strcpy(output_filename, argv[i]); break; @@ -1,5 +1,5 @@ #include "util.h" - +#include "matrix.h" /* Read the data from the data_file. The data matrix X is augmented with a column of ones, to get the matrix Z. @@ -188,8 +188,6 @@ void read_model(struct Model *model, char *model_filename) } - - void write_model(struct Model *model, char *output_filename) { FILE *fid; @@ -318,63 +316,6 @@ double rnd() return (double) rand()/0x7FFFFFFF; } -/* - Set a matrix element using ROW Major order. i denotes row, - j denotes column. -*/ -void matrix_set(double *M, long cols, long i, long j, double val) -{ - M[i*cols+j] = val; -} - -/* - Get a matrix element using ROW Major order. i denotes row, - j denotes column. -*/ -double matrix_get(double *M, long cols, long i, long j) -{ - return M[i*cols+j]; -} - -/* - Add to an existing matrix element. Row-Major order is used. -*/ -void matrix_add(double *M, long cols, long i, long j, double val) -{ - M[i*cols+j] += val; -} - -/* - Multiply existing matrix element. Row-Major order is used. -*/ -void matrix_mult(double *M, long cols, long i, long j, double val) -{ - M[i*cols+j] *= val; -} - - -/* - Set a matrix element of a 3D matrix in ROW major order. - N2 and N3 are the second and third dimension respectively - and i, j, k are the indices of the first, second and third - dimensions respectively. -*/ -void matrix3_set(double *M, long N2, long N3, long i, long j, long k, double val) -{ - M[k+N3*(j+N2*i)] = val; -} - -/* - Get a matrix element of a 3D matrix in ROW major order. - N2 and N3 are the second and third dimension respectively, and - i, j and k are the indices of the first, second and third - dimension of the requested element respectively. -*/ -double matrix3_get(double *M, long N2, long N3, long i, long j, long k) -{ - return M[k+N3*(j+N2*i)]; -} - void allocate_model(struct Model *model) { long n = model->n; @@ -466,6 +407,7 @@ void free_data(struct Data *data) free(data); } +/* void print_matrix(double *M, long rows, long cols) { long i, j; @@ -477,3 +419,4 @@ void print_matrix(double *M, long rows, long cols) } info("\n"); } +*/ |