ssl.h

Go to the documentation of this file.
00001 /*    Copyright 2006 Vikas Sindhwani (vikass@cs.uchicago.edu)
00002       SVM-lin: Fast SVM Solvers for Supervised and Semi-supervised Learning
00003 
00004       This file is part of SVM-lin.      
00005 
00006       SVM-lin is free software; you can redistribute it and/or modify
00007       it under the terms of the GNU General Public License as published by
00008       the Free Software Foundation; either version 2 of the License, or
00009       (at your option) any later version.
00010 
00011       SVM-lin is distributed in the hope that it will be useful,
00012       but WITHOUT ANY WARRANTY; without even the implied warranty of
00013       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014       GNU General Public License for more details.
00015 
00016       You should have received a copy of the GNU General Public License
00017       along with SVM-lin (see gpl.txt); if not, write to the Free Software
00018       Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00019       */
00020 #ifndef _SSL_H
00021 #define _SSL_H
00022 
00023 /* OPTIMIZATION CONSTANTS */
00024 #define CGITERMAX 10000 /* maximum number of CGLS iterations */
00025 #define SMALL_CGITERMAX 10 /* for heuristic 1 in reference [2] */
00026 #define EPSILON   1e-6 /* most tolerances are set to this value */
00027 #define BIG_EPSILON 0.01 /* for heuristic 2 in reference [2] */
00028 #define RELATIVE_STOP_EPS 1e-9 /* for L2-SVM-MFN relative stopping criterion */
00029 #define MFNITERMAX 50 /* maximum number of MFN iterations */
00030 #define TSVM_ANNEALING_RATE 1.5 /* rate at which lambda_u is increased in TSVM */
00031 #define TSVM_LAMBDA_SMALL 1e-5 /* lambda_u starts from this value */
00032 #define DA_ANNEALING_RATE 1.5 /* annealing rate for DA */
00033 #define DA_INIT_TEMP 10 /* initial temperature relative to lambda_u */
00034 #define DA_INNER_ITERMAX 100 /* maximum fixed temperature iterations for DA */
00035 #define DA_OUTER_ITERMAX 30 /* maximum number of outer loops for DA */
00036 
00037 #include "lib/common.h"
00038 #include "features/SparseFeatures.h"
00039 
00041 struct data
00042 {
00044     int m;
00046     int l;
00048     int u;
00050     int n;
00052     int nz;
00053 
00055     CSparseFeatures<DREAL>* features;
00057     double *Y;
00059     double *C;
00060 };
00061 
00063 struct vector_double
00064 {
00066     int d;
00068     double *vec;
00069 };
00070 
00072 struct vector_int
00073 {
00075     int d;
00077     int *vec;
00078 };
00079 
00080 enum { RLS, SVM, TSVM, DA_SVM }; /* currently implemented algorithms */
00081 
00083 struct options
00084 {
00085     /* user options */
00087     int algo;
00089     double lambda;
00091     double lambda_u;
00093     int S;
00095     double R;
00097     double Cp;
00099     double Cn;
00100 
00101     /*  internal optimization options */
00103     double epsilon;
00105     int cgitermax;
00107     int mfnitermax;
00108 
00110     double bias;
00111 };
00112 
00114 class Delta {
00115     public:
00117         Delta() {delta=0.0; index=0;s=0;};
00118 
00120         double delta;
00122         int index;
00124         int s;
00125 };
00126 inline bool operator<(const Delta& a , const Delta& b) { return (a.delta < b.delta);};
00127 
00128 void initialize(struct vector_double *A, int k, double a);  
00129 /* initializes a vector_double to be of length k, all elements set to a */
00130 void initialize(struct vector_int *A, int k); 
00131 /* initializes a vector_int to be of length k, elements set to 1,2..k. */
00132 void GetLabeledData(struct data *Data_Labeled, const struct data *Data); 
00133 /* extracts labeled data from Data and copies it into Data_Labeled */
00134 double norm_square(const vector_double *A); /* returns squared length of A */
00135 
00136 /* ssl_train: takes data, options, uninitialized weight and output
00137    vector_doubles, routes it to the algorithm */
00138 /* the learnt weight vector and the outputs it gives on the data matrix are saved */
00139 void ssl_train(struct data *Data, 
00140         struct options *Options,
00141         struct vector_double *W, /* weight vector */
00142         struct vector_double *O); /* output vector */
00143 
00144 /* svmlin algorithms and their subroutines */
00145 
00146 /* Conjugate Gradient for Sparse Linear Least Squares Problems */
00147 /* Solves: min_w 0.5*Options->lamda*w'*w + 0.5*sum_{i in Subset} Data->C[i] (Y[i]- w' x_i)^2 */
00148 /* over a subset of examples x_i specified by vector_int Subset */
00149 int CGLS(const struct data *Data, 
00150         const struct options *Options, 
00151         const struct vector_int *Subset,
00152         struct vector_double *Weights,
00153         struct vector_double *Outputs);
00154 
00155 /* Linear Modified Finite Newton L2-SVM*/
00156 /* 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 */
00157 int L2_SVM_MFN(const struct data *Data, 
00158         struct options *Options, 
00159         struct vector_double *Weights,
00160         struct vector_double *Outputs,
00161         int ini); /* use ini=0 if no good starting guess for Weights, else 1 */
00162 double line_search(double *w, 
00163         double *w_bar,
00164         double lambda,
00165         double *o, 
00166         double *o_bar, 
00167         double *Y, 
00168         double *C,
00169         int d,
00170         int l);
00171 
00172 /* Transductive L2-SVM */
00173 /* 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 
00174    subject to: (1/Data->u)*sum_{i in UNlabeled} max(0,Y[i]) = Options->R */
00175 int   TSVM_MFN(const struct data *Data, 
00176         struct options *Options, 
00177         struct vector_double *Weights,
00178         struct vector_double *Outputs);
00179 int switch_labels(double* Y, double* o, int* JU, int u, int S);
00180 
00181 /* Deterministic Annealing*/
00182 int DA_S3VM(struct data *Data, 
00183         struct options *Options, 
00184         struct vector_double *Weights,
00185         struct vector_double *Outputs);
00186 void optimize_p(const double* g, int u, double T, double r, double*p);
00187 int optimize_w(const struct data *Data, 
00188         const  double *p,
00189         struct options *Options, 
00190         struct vector_double *Weights,
00191         struct vector_double *Outputs,
00192         int ini);
00193 double transductive_cost(double normWeights,double *Y, double *Outputs, int m, double lambda,double lambda_u);
00194 double entropy(const  double *p, int u); 
00195 double KL(const  double *p, const  double *q, int u); /* KL-divergence */
00196 
00197 #endif

SHOGUN Machine Learning Toolbox - Documentation