libocas.h

Go to the documentation of this file.
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation