SHOGUN
v2.0.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * libocas.h: Implementation of the OCAS solver for training 00008 * linear SVM classifiers. 00009 * 00010 * Copyright (C) 2008, 2009 Vojtech Franc, xfrancv@cmp.felk.cvut.cz 00011 * Soeren Sonnenburg, soeren.sonnenburg@first.fraunhofer.de 00012 * Implementation of SVM-Ocas solver. 00013 *-------------------------------------------------------------------- */ 00014 00015 #include <shogun/lib/common.h> 00016 00017 #ifndef libocas_h 00018 #define libocas_h 00019 #ifndef DOXYGEN_SHOULD_SKIP_THIS 00020 namespace shogun 00021 { 00022 #define LIBOCAS_PLUS_INF (-log(0.0)) 00023 #define LIBOCAS_CALLOC(x,y) calloc(x,y) 00024 #define LIBOCAS_FREE(x) SG_FREE(x) 00025 #define LIBOCAS_INDEX(ROW,COL,NUM_ROWS) ((COL)*(NUM_ROWS)+(ROW)) 00026 #define LIBOCAS_MIN(A,B) ((A) > (B) ? (B) : (A)) 00027 #define LIBOCAS_MAX(A,B) ((A) < (B) ? (B) : (A)) 00028 #define LIBOCAS_ABS(A) ((A) < 0 ? -(A) : (A)) 00029 00030 typedef struct { 00031 uint32_t nIter; /* number of iterations */ 00032 uint32_t nCutPlanes; /* number of cutitng buffered planes */ 00033 uint32_t nNZAlpha; /* number of non-zero Lagrangeans (effective number of CPs) */ 00034 uint32_t trn_err; /* number of training errors */ 00035 float64_t Q_P; /* primal objective value */ 00036 float64_t Q_D; /* dual objective value */ 00037 float64_t output_time; /* time spent in computing outputs */ 00038 float64_t sort_time; /* time spent in sorting */ 00039 float64_t add_time; /* time spent in adding examples to compute cutting planes */ 00040 float64_t w_time; /* time spent in computing parameter vector */ 00041 float64_t qp_solver_time; /* time spent in inner QP solver */ 00042 float64_t ocas_time; /* total time spent in svm_ocas_solver */ 00043 float64_t print_time; /* time spent in ocas_print function */ 00044 int8_t qp_exitflag; /* exitflag from the last call of the inner QP solver */ 00045 int8_t exitflag; /* 1 .. ocas.Q_P - ocas.Q_D <= TolRel*ABS(ocas.Q_P) 00046 2 .. ocas.Q_P - ocas.Q_D <= TolAbs 00047 3 .. ocas.Q_P <= QPBound 00048 4 .. optimization time >= MaxTime 00049 -1 .. ocas.nCutPlanes >= BufSize 00050 -2 .. not enough memory for the solver */ 00051 } ocas_return_value_T; 00052 00053 /* binary linear SVM solver */ 00054 ocas_return_value_T svm_ocas_solver( 00055 float64_t C, /* regularizarion constant */ 00056 uint32_t nData, /* number of exmaples */ 00057 float64_t TolRel, /* halts if 1-Q_P/Q_D <= TolRel */ 00058 float64_t TolAbs, /* halts if Q_P-Q_D <= TolRel */ 00059 float64_t QPBound, /* halts if QP <= QPBound */ 00060 float64_t MaxTime, /* maximal time in seconds spent in optmization */ 00061 uint32_t BufSize, /* maximal number of buffered cutting planes */ 00062 uint8_t Method, /* 0..standard CP (SVM-Perf,BMRM), 1..OCAS */ 00063 void (*compute_W)(float64_t*, float64_t*, float64_t*, uint32_t, void*), 00064 float64_t (*update_W)(float64_t, void*), 00065 int (*add_new_cut)(float64_t*, uint32_t*, uint32_t, uint32_t, void*), 00066 int (*compute_output)( float64_t*, void* ), 00067 int (*sort)(float64_t*, float64_t*, uint32_t), 00068 void (*ocas_print)(ocas_return_value_T), 00069 void* user_data); 00070 00071 /* binary linear SVM solver which allows using different C for each example*/ 00072 ocas_return_value_T svm_ocas_solver_difC( 00073 float64_t *C, /* regularizarion constants for each example */ 00074 uint32_t nData, /* number of exmaples */ 00075 float64_t TolRel, /* halts if 1-Q_P/Q_D <= TolRel */ 00076 float64_t TolAbs, /* halts if Q_P-Q_D <= TolRel */ 00077 float64_t QPBound, /* halts if QP <= QPBound */ 00078 float64_t MaxTime, /* maximal time in seconds spent in optmization */ 00079 uint32_t BufSize, /* maximal number of buffered cutting planes */ 00080 uint8_t Method, /* 0..standard CP (SVM-Perf,BMRM), 1..OCAS */ 00081 void (*compute_W)(float64_t*, float64_t*, float64_t*, uint32_t, void*), 00082 float64_t (*update_W)(float64_t, void*), 00083 int (*add_new_cut)(float64_t*, uint32_t*, uint32_t, uint32_t, void*), 00084 int (*compute_output)( float64_t*, void* ), 00085 int (*sort)(float64_t*, float64_t*, uint32_t), 00086 void (*ocas_print)(ocas_return_value_T), 00087 void* user_data); 00088 00089 /* multi-class (Singer-Crammer formulation) linear SVM solver */ 00090 ocas_return_value_T msvm_ocas_solver( 00091 float64_t C, 00092 float64_t *data_y, 00093 uint32_t nY, 00094 uint32_t nData, 00095 float64_t TolRel, 00096 float64_t TolAbs, 00097 float64_t QPBound, 00098 float64_t MaxTime, 00099 uint32_t _BufSize, 00100 uint8_t Method, 00101 void (*compute_W)(float64_t*, float64_t*, float64_t*, uint32_t, void*), 00102 float64_t (*update_W)(float64_t, void*), 00103 int (*add_new_cut)(float64_t*, uint32_t*, uint32_t, void*), 00104 int (*compute_output)(float64_t*, void* ), 00105 int (*sort)(float64_t*, float64_t*, uint32_t), 00106 void (*ocas_print)(ocas_return_value_T), 00107 void* user_data); 00108 00109 00110 /* binary linear SVM solver */ 00111 ocas_return_value_T svm_ocas_solver_nnw( 00112 float64_t C, /* regularizarion constant */ 00113 uint32_t nData, /* number of exmaples */ 00114 uint32_t num_nnw, /* number of components of W which must non-negative*/ 00115 uint32_t* nnw_idx, /* indices of W which must be non-negative */ 00116 float64_t TolRel, /* halts if 1-Q_P/Q_D <= TolRel */ 00117 float64_t TolAbs, /* halts if Q_P-Q_D <= TolRel */ 00118 float64_t QPBound, /* halts if QP <= QPBound */ 00119 float64_t MaxTime, /* maximal time in seconds spent in optmization */ 00120 uint32_t BufSize, /* maximal number of buffered cutting planes */ 00121 uint8_t Method, /* 0..standard CP (SVM-Perf,BMRM), 1..OCAS */ 00122 int (*add_pw_constr)(uint32_t, uint32_t, void*), 00123 void (*clip_neg_w)(uint32_t, uint32_t*, void*), 00124 void (*compute_W)(float64_t*, float64_t*, float64_t*, uint32_t, void*), 00125 float64_t (*update_W)(float64_t, void*), 00126 int (*add_new_cut)(float64_t*, uint32_t*, uint32_t, uint32_t, void*), 00127 int (*compute_output)( float64_t*, void* ), 00128 int (*sort)(float64_t*, float64_t*, uint32_t), 00129 void (*ocas_print)(ocas_return_value_T), 00130 void* user_data); 00131 00132 } 00133 #endif // DOXYGEN_SHOULD_SKIP_THIS 00134 #endif /* libocas_h */ 00135