SVMLight.h

Go to the documentation of this file.

/***********************************************************************/
/*                                                                     */
/*   SVMLight.h                                                        */
/*                                                                     */
/*   Author: Thorsten Joachims                                         */
/*   Date: 19.07.99                                                    */
/*                                                                     */
/*   Copyright (c) 1999  Universitaet Dortmund - All rights reserved   */
/*                                                                     */
/*   This software is available for non-commercial use only. It must   */
/*   not be modified and distributed without prior permission of the   */
/*   author. The author is not responsible for implications from the   */
/*   use of this software.                                             */
/*                                                                     */
/*   THIS INCLUDES THE FOLLOWING ADDITIONS                             */
/*   Generic Kernel Interfacing: Soeren Sonnenburg                     */
/*   Parallizations: Soeren Sonnenburg                                 */
/*   Multiple Kernel Learning: Gunnar Raetsch, Soeren Sonnenburg       */
/*   Linadd Speedup: Gunnar Raetsch, Soeren Sonnenburg                 */
/*                                                                     */
/***********************************************************************/
#ifndef _SVMLight_H___
#define _SVMLight_H___

#include <shogun/lib/config.h>

#ifdef USE_SVMLIGHT
#include <shogun/classifier/svm/SVM.h>
#include <shogun/kernel/Kernel.h>
#include <shogun/mathematics/Math.h>
#include <shogun/lib/common.h>

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

namespace shogun
{
//# define VERSION       "V3.50 -- correct??"
//# define VERSION_DATE  "01.11.00 -- correct??"

# define DEF_PRECISION 1E-14
# define MAXSHRINK 50000

#ifndef DOXYGEN_SHOULD_SKIP_THIS

struct MODEL {
int32_t    sv_num;
int32_t    at_upper_bound;
float64_t b;
int32_t*   supvec;
float64_t *alpha;
int32_t    *index;
int32_t    totdoc;
CKernel* kernel;

/* the following values are not written to file */
float64_t loo_error;
float64_t loo_recall;
float64_t loo_precision;

float64_t xa_error;
float64_t xa_recall;
float64_t xa_precision;
};

typedef struct quadratic_program {
  int32_t   opt_n;
  int32_t   opt_m;
  float64_t *opt_ce;
  float64_t *opt_ce0;
  float64_t *opt_g;
  float64_t *opt_g0;
  float64_t *opt_xinit;
  float64_t *opt_low;
  float64_t *opt_up;
} QP;

typedef int32_t FNUM;

typedef float64_t FVAL;

struct LEARN_PARM {
  int32_t   type;
  float64_t svm_c;
  float64_t* eps;
  float64_t svm_costratio;
  float64_t transduction_posratio;
  /* classified as positives */
  int32_t   biased_hyperplane;
  int32_t   sharedslack;
  int32_t   svm_maxqpsize;
  int32_t   svm_newvarsinqp;
  int32_t   kernel_cache_size;
  float64_t epsilon_crit;
  float64_t epsilon_shrink;
  int32_t   svm_iter_to_shrink;
  int32_t   maxiter;
  int32_t   remove_inconsistent;
  int32_t   skip_final_opt_check;
  int32_t   compute_loo;
  float64_t rho;
  int32_t   xa_depth;
  char predfile[200];
  char alphafile[200];

  /* you probably do not want to touch the following */
  float64_t epsilon_const;
  float64_t epsilon_a;
  float64_t opt_precision;

  /* the following are only for internal use */
  int32_t   svm_c_steps;
  float64_t svm_c_factor;
  float64_t svm_costratio_unlab;
  float64_t svm_unlabbound;
  float64_t *svm_cost;
};

struct TIMING {
  int32_t   time_kernel;
  int32_t   time_opti;
  int32_t   time_shrink;
  int32_t   time_update;
  int32_t   time_model;
  int32_t   time_check;
  int32_t   time_select;
};


struct SHRINK_STATE
{
  int32_t   *active;
  int32_t   *inactive_since;
  int32_t   deactnum;
  float64_t **a_history;
  int32_t   maxhistory;
  float64_t *last_a;
  float64_t *last_lin;
};
#endif // DOXYGEN_SHOULD_SKIP_THIS

class CSVMLight : public CSVM
{
 public:
  CSVMLight();

  CSVMLight(float64_t C, CKernel* k, CLabels* lab);
  virtual ~CSVMLight();

  void init();

  virtual inline EClassifierType get_classifier_type() { return CT_LIGHT; }

  int32_t   get_runtime();


  void   svm_learn();

  int32_t optimize_to_convergence(
    int32_t* docs, int32_t* label, int32_t totdoc, SHRINK_STATE *shrink_state,
    int32_t *inconsistent, float64_t *a, float64_t *lin, float64_t *c,
    TIMING *timing_profile, float64_t *maxdiff, int32_t heldout,
    int32_t retrain);

  virtual float64_t compute_objective_function(
    float64_t *a, float64_t *lin, float64_t *c, float64_t* eps, int32_t *label,
    int32_t totdoc);

  void   clear_index(int32_t *index);

  void   add_to_index(int32_t *index, int32_t elem);

  int32_t   compute_index(int32_t *binfeature, int32_t range, int32_t *index);

  void optimize_svm(
    int32_t* docs, int32_t* label, int32_t *exclude_from_eq_const,
    float64_t eq_target, int32_t *chosen, int32_t *active2dnum, int32_t totdoc,
    int32_t *working2dnum, int32_t varnum, float64_t *a, float64_t *lin,
    float64_t *c, float64_t *aicache, QP *qp, float64_t *epsilon_crit_target);

  void compute_matrices_for_optimization(
    int32_t* docs, int32_t* label, int32_t *exclude_from_eq_const,
    float64_t eq_target, int32_t *chosen, int32_t *active2dnum, int32_t *key,
    float64_t *a, float64_t *lin, float64_t *c, int32_t varnum, int32_t totdoc,
    float64_t *aicache, QP *qp);

  void compute_matrices_for_optimization_parallel(
    int32_t* docs, int32_t* label, int32_t *exclude_from_eq_const,
    float64_t eq_target, int32_t *chosen, int32_t *active2dnum, int32_t *key,
    float64_t *a, float64_t *lin, float64_t *c, int32_t varnum, int32_t totdoc,
    float64_t *aicache, QP *qp);

  int32_t   calculate_svm_model(
    int32_t* docs, int32_t *label,float64_t *lin, float64_t *a,
    float64_t* a_old, float64_t *c, int32_t *working2dnum, int32_t *active2dnum);

  int32_t   check_optimality(
    int32_t *label, float64_t *a, float64_t* lin, float64_t *c, int32_t totdoc,
    float64_t *maxdiff, float64_t epsilon_crit_org, int32_t *misclassified,
    int32_t *inconsistent,int32_t* active2dnum, int32_t *last_suboptimal_at,
    int32_t iteration);

  virtual void update_linear_component(
    int32_t* docs, int32_t *label, int32_t *active2dnum, float64_t *a,
    float64_t* a_old, int32_t *working2dnum, int32_t totdoc, float64_t *lin,
    float64_t *aicache, float64_t* c);

  static void* update_linear_component_mkl_linadd_helper(void* p);

  void update_linear_component_mkl(
          int32_t* docs, int32_t *label, int32_t *active2dnum, float64_t *a,
          float64_t* a_old, int32_t *working2dnum, int32_t totdoc, float64_t *lin,
          float64_t *aicache);

  void update_linear_component_mkl_linadd(
          int32_t* docs, int32_t *label, int32_t *active2dnum, float64_t *a,
          float64_t* a_old, int32_t *working2dnum, int32_t totdoc, float64_t *lin,
          float64_t *aicache);

  void call_mkl_callback(float64_t* a, int32_t* label, float64_t* lin);

  int32_t select_next_qp_subproblem_grad(
    int32_t *label, float64_t *a, float64_t* lin, float64_t* c, int32_t totdoc,
    int32_t qp_size, int32_t *inconsistent, int32_t* active2dnum,
    int32_t* working2dnum, float64_t *selcrit, int32_t *select,
    int32_t cache_only, int32_t *key, int32_t *chosen);

  int32_t select_next_qp_subproblem_rand(
    int32_t* label, float64_t *a, float64_t *lin, float64_t *c,
    int32_t totdoc, int32_t qp_size, int32_t *inconsistent,
    int32_t *active2dnum, int32_t *working2dnum, float64_t *selcrit,
    int32_t *select, int32_t *key, int32_t *chosen, int32_t iteration);

  void   select_top_n(
    float64_t *selcrit, int32_t range, int32_t *select, int32_t n);

  void   init_shrink_state(
    SHRINK_STATE *shrink_state, int32_t totdoc, int32_t maxhistory);

  void   shrink_state_cleanup(SHRINK_STATE *shrink_state);

  int32_t shrink_problem(
    SHRINK_STATE *shrink_state, int32_t *active2dnum,
    int32_t *last_suboptimal_at, int32_t iteration, int32_t totdoc,
    int32_t minshrink, float64_t *a, int32_t *inconsistent, float64_t* c,
    float64_t* lin, int* label);

  virtual void   reactivate_inactive_examples(
    int32_t *label,float64_t *a,SHRINK_STATE *shrink_state, float64_t *lin,
    float64_t *c, int32_t totdoc,int32_t iteration, int32_t *inconsistent,
    int32_t *docs,float64_t *aicache, float64_t* maxdiff);

protected:
    inline virtual float64_t compute_kernel(int32_t i, int32_t j)
    {
        return kernel->kernel(i, j);
    }

    static void* compute_kernel_helper(void* p);

    static void* update_linear_component_linadd_helper(void* p);

    static void* reactivate_inactive_examples_vanilla_helper(void* p);

    static void* reactivate_inactive_examples_linadd_helper(void* p);

    inline virtual const char* get_name() const { return "SVMLight"; }

    /* interface to QP-solver */
    float64_t *optimize_qp( QP *qp,float64_t *epsilon_crit, int32_t nx,
            float64_t *threshold, int32_t& svm_maxqpsize);

    virtual bool train_machine(CFeatures* data=NULL);

 protected:
  MODEL* model;
  LEARN_PARM* learn_parm;
  int32_t   verbosity;

  float64_t init_margin;
  int32_t   init_iter;
  int32_t precision_violations;
  float64_t model_b;
  float64_t opt_precision;
  float64_t* primal;
  float64_t* dual;

  // MKL stuff

  float64_t* W;
  int32_t count;
  float64_t mymaxdiff;
  bool use_kernel_cache;
  bool mkl_converged;
};
}
#endif //USE_SVMLIGHT
#endif //_SVMLight_H___