ssl.h

Go to the documentation of this file.

/*    Copyright 2006 Vikas Sindhwani (vikass@cs.uchicago.edu)
      SVM-lin: Fast SVM Solvers for Supervised and Semi-supervised Learning

      This file is part of SVM-lin.

      SVM-lin is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation; either version 2 of the License, or
      (at your option) any later version.

      SVM-lin is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.

      You should have received a copy of the GNU General Public License
      along with SVM-lin (see gpl.txt); if not, write to the Free Software
      Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
      */
#ifndef DOXYGEN_SHOULD_SKIP_THIS

#ifndef _SSL_H
#define _SSL_H

/* OPTIMIZATION CONSTANTS */
#define CGITERMAX 10000 /* maximum number of CGLS iterations */
#define SMALL_CGITERMAX 10 /* for heuristic 1 in reference [2] */
#define EPSILON   1e-6 /* most tolerances are set to this value */
#define BIG_EPSILON 0.01 /* for heuristic 2 in reference [2] */
#define RELATIVE_STOP_EPS 1e-9 /* for L2-SVM-MFN relative stopping criterion */
#define MFNITERMAX 50 /* maximum number of MFN iterations */
#define TSVM_ANNEALING_RATE 1.5 /* rate at which lambda_u is increased in TSVM */
#define TSVM_LAMBDA_SMALL 1e-5 /* lambda_u starts from this value */
#define DA_ANNEALING_RATE 1.5 /* annealing rate for DA */
#define DA_INIT_TEMP 10 /* initial temperature relative to lambda_u */
#define DA_INNER_ITERMAX 100 /* maximum fixed temperature iterations for DA */
#define DA_OUTER_ITERMAX 30 /* maximum number of outer loops for DA */

#include <shogun/lib/common.h>
#include <shogun/features/DotFeatures.h>

namespace shogun
{
struct data
{
    int32_t m;
    int32_t l;
    int32_t u;
    int32_t n;
    int32_t nz;

    shogun::CDotFeatures* features;
    float64_t *Y;
    float64_t *C;
};

struct vector_double
{
    int32_t d;
    float64_t *vec;
};

struct vector_int
{
    int32_t d;
    int32_t *vec;
};

enum { RLS, SVM, TSVM, DA_SVM }; /* currently implemented algorithms */

struct options
{
    /* user options */
    int32_t algo;
    float64_t lambda;
    float64_t lambda_u;
    int32_t S;
    float64_t R;
    float64_t Cp;
    float64_t Cn;

    /*  internal optimization options */
    float64_t epsilon;
    int32_t cgitermax;
    int32_t mfnitermax;

    float64_t bias;
};

class Delta {
    public:
        Delta() { delta=0.0; index=0;s=0; }

        float64_t delta;
        int32_t index;
        int32_t s;
};

inline bool operator<(const Delta& a , const Delta& b)
{
    return (a.delta < b.delta);
}

void initialize(struct vector_double *A, int32_t k, float64_t a);
/* initializes a vector_double to be of length k, all elements set to a */
void initialize(struct vector_int *A, int32_t k);
/* initializes a vector_int to be of length k, elements set to 1,2..k. */
void GetLabeledData(struct data *Data_Labeled, const struct data *Data);
/* extracts labeled data from Data and copies it into Data_Labeled */
float64_t norm_square(const vector_double *A); /* returns squared length of A */

/* ssl_train: takes data, options, uninitialized weight and output
   vector_doubles, routes it to the algorithm */
/* the learnt weight vector and the outputs it gives on the data matrix are saved */
void ssl_train(
    struct data *Data,
    struct options *Options,
    struct vector_double *W, /* weight vector */
    struct vector_double *O); /* output vector */

/* svmlin algorithms and their subroutines */

/* Conjugate Gradient for Sparse Linear Least Squares Problems */
/* Solves: min_w 0.5*Options->lamda*w'*w + 0.5*sum_{i in Subset} Data->C[i] (Y[i]- w' x_i)^2 */
/* over a subset of examples x_i specified by vector_int Subset */
int32_t CGLS(
    const struct data *Data,
    const struct options *Options,
    const struct vector_int *Subset,
    struct vector_double *Weights,
    struct vector_double *Outputs);

/* Linear Modified Finite Newton L2-SVM*/
/* Solves: min_w 0.5*Options->lamda*w'*w + 0.5*sum_i Data->C[i] max(0,1 - Y[i] w' x_i)^2 */
int32_t L2_SVM_MFN(
    const struct data *Data,
    struct options *Options,
    struct vector_double *Weights,
    struct vector_double *Outputs,
    int32_t ini); /* use ini=0 if no good starting guess for Weights, else 1 */

float64_t line_search(
    float64_t *w,
    float64_t *w_bar,
    float64_t lambda,
    float64_t *o,
    float64_t *o_bar,
    float64_t *Y,
    float64_t *C,
    int32_t d,
    int32_t l);

/* Transductive L2-SVM */
/* Solves : min_(w, Y[i],i in UNlabeled) 0.5*Options->lamda*w'*w + 0.5*(1/Data->l)*sum_{i in labeled} max(0,1 - Y[i] w' x_i)^2 + 0.5*(Options->lambda_u/Data->u)*sum_{i in UNlabeled} max(0,1 - Y[i] w' x_i)^2
   subject to: (1/Data->u)*sum_{i in UNlabeled} max(0,Y[i]) = Options->R */
int32_t TSVM_MFN(
    const struct data *Data,
    struct options *Options,
    struct vector_double *Weights,
    struct vector_double *Outputs);

int32_t switch_labels(
    float64_t* Y,
    float64_t* o,
    int32_t* JU,
    int32_t u,
    int32_t S);

/* Deterministic Annealing*/
int32_t DA_S3VM(
    struct data *Data,
    struct options *Options,
    struct vector_double *Weights,
    struct vector_double *Outputs);

void optimize_p(
    const float64_t* g, int32_t u, float64_t T, float64_t r, float64_t*p);

int32_t optimize_w(
    const struct data *Data,
    const  float64_t *p,
    struct options *Options,
    struct vector_double *Weights,
    struct vector_double *Outputs,
    int32_t ini);

float64_t transductive_cost(
    float64_t normWeights,
    float64_t *Y,
    float64_t *Outputs,
    int32_t m,
    float64_t lambda,
    float64_t lambda_u);

float64_t entropy(const  float64_t *p, int32_t u);

/* KL-divergence */
float64_t KL(const  float64_t *p, const  float64_t *q, int32_t u);
}
#endif // _SSL_H

#endif // DOXYGEN_SHOULD_SKIP_THIS