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 DOXYGEN_SHOULD_SKIP_THIS
00021 
00022 #ifndef _SSL_H
00023 #define _SSL_H
00024 
00025 /* OPTIMIZATION CONSTANTS */
00026 #define CGITERMAX 10000 /* maximum number of CGLS iterations */
00027 #define SMALL_CGITERMAX 10 /* for heuristic 1 in reference [2] */
00028 #define EPSILON   1e-6 /* most tolerances are set to this value */
00029 #define BIG_EPSILON 0.01 /* for heuristic 2 in reference [2] */
00030 #define RELATIVE_STOP_EPS 1e-9 /* for L2-SVM-MFN relative stopping criterion */
00031 #define MFNITERMAX 50 /* maximum number of MFN iterations */
00032 #define TSVM_ANNEALING_RATE 1.5 /* rate at which lambda_u is increased in TSVM */
00033 #define TSVM_LAMBDA_SMALL 1e-5 /* lambda_u starts from this value */
00034 #define DA_ANNEALING_RATE 1.5 /* annealing rate for DA */
00035 #define DA_INIT_TEMP 10 /* initial temperature relative to lambda_u */
00036 #define DA_INNER_ITERMAX 100 /* maximum fixed temperature iterations for DA */
00037 #define DA_OUTER_ITERMAX 30 /* maximum number of outer loops for DA */
00038 
00039 #include "lib/common.h"
00040 #include "features/DotFeatures.h"
00041 
00042 
00044 struct data
00045 {
00047     int32_t m;
00049     int32_t l;
00051     int32_t u;
00053     int32_t n;
00055     int32_t nz;
00056 
00058     CDotFeatures* features;
00060     float64_t *Y;
00062     float64_t *C;
00063 };
00064 
00066 struct vector_double
00067 {
00069     int32_t d;
00071     float64_t *vec;
00072 };
00073 
00075 struct vector_int
00076 {
00078     int32_t d;
00080     int32_t *vec;
00081 };
00082 
00083 enum { RLS, SVM, TSVM, DA_SVM }; /* currently implemented algorithms */
00084 
00086 struct options
00087 {
00088     /* user options */
00090     int32_t algo;
00092     float64_t lambda;
00094     float64_t lambda_u;
00096     int32_t S;
00098     float64_t R;
00100     float64_t Cp;
00102     float64_t Cn;
00103 
00104     /*  internal optimization options */
00106     float64_t epsilon;
00108     int32_t cgitermax;
00110     int32_t mfnitermax;
00111 
00113     float64_t bias;
00114 };
00115 
00117 class Delta {
00118     public:
00120         Delta() { delta=0.0; index=0;s=0; }
00121 
00123         float64_t delta;
00125         int32_t index;
00127         int32_t s;
00128 };
00129 
00130 inline bool operator<(const Delta& a , const Delta& b)
00131 {
00132     return (a.delta < b.delta);
00133 }
00134 
00135 void initialize(struct vector_double *A, int32_t k, float64_t a);
00136 /* initializes a vector_double to be of length k, all elements set to a */
00137 void initialize(struct vector_int *A, int32_t k);
00138 /* initializes a vector_int to be of length k, elements set to 1,2..k. */
00139 void GetLabeledData(struct data *Data_Labeled, const struct data *Data); 
00140 /* extracts labeled data from Data and copies it into Data_Labeled */
00141 float64_t norm_square(const vector_double *A); /* returns squared length of A */
00142 
00143 /* ssl_train: takes data, options, uninitialized weight and output
00144    vector_doubles, routes it to the algorithm */
00145 /* the learnt weight vector and the outputs it gives on the data matrix are saved */
00146 void ssl_train(
00147     struct data *Data,
00148     struct options *Options,
00149     struct vector_double *W, /* weight vector */
00150     struct vector_double *O); /* output vector */
00151 
00152 /* svmlin algorithms and their subroutines */
00153 
00154 /* Conjugate Gradient for Sparse Linear Least Squares Problems */
00155 /* Solves: min_w 0.5*Options->lamda*w'*w + 0.5*sum_{i in Subset} Data->C[i] (Y[i]- w' x_i)^2 */
00156 /* over a subset of examples x_i specified by vector_int Subset */
00157 int32_t CGLS(
00158     const struct data *Data,
00159     const struct options *Options,
00160     const struct vector_int *Subset,
00161     struct vector_double *Weights,
00162     struct vector_double *Outputs);
00163 
00164 /* Linear Modified Finite Newton L2-SVM*/
00165 /* 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 */
00166 int32_t L2_SVM_MFN(
00167     const struct data *Data,
00168     struct options *Options,
00169     struct vector_double *Weights,
00170     struct vector_double *Outputs,
00171     int32_t ini); /* use ini=0 if no good starting guess for Weights, else 1 */
00172 
00173 float64_t line_search(
00174     float64_t *w,
00175     float64_t *w_bar,
00176     float64_t lambda,
00177     float64_t *o,
00178     float64_t *o_bar,
00179     float64_t *Y,
00180     float64_t *C,
00181     int32_t d,
00182     int32_t l);
00183 
00184 /* Transductive L2-SVM */
00185 /* 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 
00186    subject to: (1/Data->u)*sum_{i in UNlabeled} max(0,Y[i]) = Options->R */
00187 int32_t TSVM_MFN(
00188     const struct data *Data,
00189     struct options *Options,
00190     struct vector_double *Weights,
00191     struct vector_double *Outputs);
00192 
00193 int32_t switch_labels(
00194     float64_t* Y,
00195     float64_t* o,
00196     int32_t* JU,
00197     int32_t u,
00198     int32_t S);
00199 
00200 /* Deterministic Annealing*/
00201 int32_t DA_S3VM(
00202     struct data *Data,
00203     struct options *Options,
00204     struct vector_double *Weights,
00205     struct vector_double *Outputs);
00206 
00207 void optimize_p(
00208     const float64_t* g, int32_t u, float64_t T, float64_t r, float64_t*p);
00209 
00210 int32_t optimize_w(
00211     const struct data *Data,
00212     const  float64_t *p,
00213     struct options *Options,
00214     struct vector_double *Weights,
00215     struct vector_double *Outputs,
00216     int32_t ini);
00217 
00218 float64_t transductive_cost(
00219     float64_t normWeights,
00220     float64_t *Y,
00221     float64_t *Outputs,
00222     int32_t m,
00223     float64_t lambda,
00224     float64_t lambda_u);
00225 
00226 float64_t entropy(const  float64_t *p, int32_t u);
00227 
00228 /* KL-divergence */
00229 float64_t KL(const  float64_t *p, const  float64_t *q, int32_t u);
00230 
00231 #endif // _SSL_H
00232 
00233 #endif // DOXYGEN_SHOULD_SKIP_THIS

SHOGUN Machine Learning Toolbox - Documentation