00001
00005 #include <assert.h>
00006 #include <cmath>
00007 #include <svm.h>
00008 #include "svm.h"
00009
00010 REGISTER_CREATOR(lemga::SVM);
00011
00012
00013
00014
00015 struct svm_model {
00016 svm_parameter param;
00017 int nr_class;
00018 int l;
00019 svm_node **SV;
00020 double **sv_coef;
00021 double *rho;
00022 double *probA;
00023 double *probB;
00024 int *label;
00025 int *nSV;
00026 int free_sv;
00027 };
00028
00029 namespace lemga {
00030
00031 typedef struct svm_node* p_svm_node;
00032
00033 struct SVM_detail {
00034 struct svm_parameter param;
00035 struct svm_problem prob;
00036 struct svm_model *model;
00037 struct svm_node *x_space;
00038 UINT n_class, n_sv;
00039 int *labels;
00040
00041 SVM_detail ();
00042 SVM_detail (const SVM_detail&);
00043 ~SVM_detail () {
00044 clean_model(); clean_data(); svm_destroy_param(¶m); }
00045 bool fill_svm_problem (const pDataSet&, const pDataWgt&);
00046 bool train (const pDataSet&, const pDataWgt&);
00047 void clean_model ();
00048 void clean_data ();
00049 };
00050
00051 SVM_detail::SVM_detail () : model(0), x_space(0) {
00052
00053 param.svm_type = C_SVC;
00054 param.kernel_type = RBF;
00055 param.degree = 3;
00056 param.gamma = 0;
00057 param.coef0 = 0;
00058 param.nu = 0.5;
00059 param.cache_size = 40;
00060 param.C = 1;
00061 param.eps = 1e-3;
00062 param.p = 0.1;
00063 param.shrinking = 1;
00064 param.probability = 0;
00065 param.nr_weight = 0;
00066 param.weight_label = NULL;
00067 param.weight = NULL;
00068 }
00069
00070 SVM_detail::SVM_detail (const SVM_detail& s)
00071 : param(s.param), model(0), x_space(0) {
00072
00073 assert(!s.param.weight && !s.param.weight_label);
00074 assert(!s.model);
00075 assert(!s.x_space);
00076 }
00077
00078 void SVM_detail::clean_model () {
00079 if (!model) return;
00080 svm_destroy_model(model);
00081 delete[] labels;
00082 model = 0;
00083 }
00084
00085 void SVM_detail::clean_data () {
00086 if (!x_space) return;
00087 delete[] prob.x; delete[] prob.y;
00088 delete[] prob.W;
00089 delete[] x_space; x_space = 0;
00090 }
00091
00092 p_svm_node fill_svm_node (const Input& x, struct svm_node *pool) {
00093 for (UINT j = 0; j < x.size(); ++j, ++pool) {
00094 pool->index = j+1;
00095 pool->value = x[j];
00096 }
00097 pool->index = -1;
00098 return ++pool;
00099 }
00100
00101 bool SVM_detail::fill_svm_problem (const pDataSet& ptd, const pDataWgt& ptw) {
00102 assert(ptd->size() == ptw->size());
00103 const UINT n_samples = ptd->size();
00104 if (n_samples == 0 || ptd->y(0).size() != 1) return false;
00105 const UINT n_in = ptd->x(0).size();
00106
00107 clean_data();
00108 prob.l = n_samples;
00109 prob.x = new p_svm_node[n_samples];
00110 prob.y = new double[n_samples];
00111 prob.W = new double[n_samples];
00112 x_space = new struct svm_node[n_samples*(n_in+1)];
00113 if (!x_space) return false;
00114
00115 struct svm_node *psn = x_space;
00116 for (UINT i = 0; i < n_samples; ++i) {
00117 prob.x[i] = psn;
00118 prob.y[i] = ptd->y(i)[0];
00119 psn = fill_svm_node(ptd->x(i), psn);
00120 prob.W[i] = (*ptw)[i] * n_samples;
00121 }
00122 return true;
00123 }
00124
00125 bool SVM_detail::train (const pDataSet& ptd, const pDataWgt& ptw) {
00126 if (!fill_svm_problem(ptd, ptw)) {
00127 std::cerr << "Error in filling SVM problem (training data)\n";
00128 return false;
00129 }
00130 const char* error_msg = svm_check_parameter(&prob,¶m);
00131 if (error_msg) {
00132 std::cerr << "Error: " << error_msg << '\n';
00133 return false;
00134 }
00135
00136 clean_model();
00137 model = svm_train(&prob, ¶m);
00138 n_class = svm_get_nr_class(model);
00139 labels = new int[n_class];
00140 svm_get_labels(model, labels);
00141 n_sv = model->l;
00142 return true;
00143 }
00144
00145 namespace kernel {
00146
00147 void Linear::set_params (SVM_detail* sd) const {
00148 sd->param.kernel_type = ::LINEAR;
00149 }
00150
00151 void Polynomial::set_params (SVM_detail* sd) const {
00152 sd->param.kernel_type = ::POLY;
00153 sd->param.degree = degree;
00154 sd->param.gamma = gamma;
00155 sd->param.coef0 = coef0;
00156 }
00157
00158 void RBF::set_params (SVM_detail* sd) const {
00159 sd->param.kernel_type = ::RBF;
00160 sd->param.gamma = gamma;
00161 }
00162
00163 void Sigmoid::set_params (SVM_detail* sd) const {
00164 sd->param.kernel_type = ::SIGMOID;
00165 sd->param.gamma = gamma;
00166 sd->param.coef0 = coef0;
00167 }
00168
00169 void Stump::set_params (SVM_detail* sd) const {
00170 sd->param.kernel_type = ::STUMP;
00171 }
00172
00173 void Perceptron::set_params (SVM_detail* sd) const {
00174 sd->param.kernel_type = ::PERCEPTRON;
00175 }
00176
00177 }
00178
00179 bool SVM::serialize (std::ostream& os, ver_list& vl) const {
00180 OBJ_FUNC_UNDEFINED("serialize");
00181 }
00182
00183 bool SVM::unserialize (std::istream& is, ver_list& vl, const id_t& d) {
00184 OBJ_FUNC_UNDEFINED("unserialize");
00185 }
00186
00187 SVM::SVM (const kernel::Kernel& k, UINT n_in) : LearnModel(n_in, 1), ker(k) {
00188 detail = new struct SVM_detail;
00189 ker.set_params(detail);
00190 }
00191
00192 SVM::SVM (const SVM& s) : LearnModel(s), ker(s.ker) {
00193 detail = new struct SVM_detail(*s.detail);
00194 }
00195
00196 SVM::~SVM () {
00197 delete detail;
00198 }
00199
00200 const SVM& SVM::operator= (const SVM& s) {
00201 if (&s == this) return *this;
00202
00203 OBJ_FUNC_UNDEFINED("operator=");
00204
00205 LearnModel::operator=(s);
00206 delete detail;
00207 detail = new struct SVM_detail(*s.detail);
00208 return *this;
00209 }
00210
00211 REAL SVM::C () const {
00212 return detail->param.C;
00213 }
00214
00215 void SVM::set_C (REAL c) {
00216 detail->param.C = c;
00217 }
00218
00219 UINT SVM::n_support_vectors () const {
00220 assert(detail->model);
00221 return detail->n_sv;
00222 }
00223
00224 REAL SVM::kernel (const Input& x1, const Input& x2) const {
00225 #ifndef NDEBUG
00226 struct svm_node sx1[n_input()+1], sx2[n_input()+1];
00227 fill_svm_node(x1, sx1);
00228 fill_svm_node(x2, sx2);
00229 REAL svmk = svm_kernel(sx1, sx2, detail->param);
00230 #endif
00231 REAL k = ker(x1, x2);
00232 assert(std::fabs(svmk - k) < EPSILON);
00233 return k;
00234 }
00235
00236 void SVM::initialize () {
00237 detail->clean_model();
00238 }
00239
00240 REAL SVM::train () {
00241 assert(n_input() == ptd->x(0).size() && n_output() == ptd->y(0).size());
00242 assert(n_samples == ptd->size());
00243 if (!detail->train(ptd, ptw)) exit(-1);
00244 return -1;
00245 }
00246
00247 REAL SVM::margin_of (const Input& x, const Input& y) const {
00248 assert(std::fabs(std::fabs(y[0]) - 1) < INFINITESIMAL);
00249 return signed_margin(x) * y[0];
00250 }
00251
00252 REAL SVM::signed_margin (const Input& x) const {
00253 assert(x.size() == n_input());
00254 assert(detail && detail->model);
00255 assert(detail->n_class > 0 && detail->n_class <= 2);
00256 if (detail->n_class == 1) return detail->labels[0];
00257
00258 struct svm_node sx[n_input()+1];
00259 fill_svm_node(x, sx);
00260 REAL m;
00261 svm_predict_values(detail->model, sx, &m);
00262 if (detail->labels[0] < detail->labels[1]) m = -m;
00263
00264 #ifndef NDEBUG
00265 const UINT nsv = n_support_vectors();
00266 REAL sum = bias();
00267 for (UINT i = 0; i < nsv; ++i)
00268 sum += support_vector_coef(i) * ker(support_vector(i), x);
00269 #endif
00270 assert(std::fabs(sum - m) < EPSILON);
00271
00272 return m;
00273 }
00274
00275 REAL SVM::w_norm () const {
00276 assert(detail && detail->model);
00277 assert(detail->n_class == 2);
00278 const UINT nsv = n_support_vectors();
00279
00280 REAL sum = 0;
00281 for (UINT i = 0; i < nsv; ++i) {
00282 for (UINT j = i; j < nsv; ++j) {
00283 REAL ip = ker(support_vector(i), support_vector(j))
00284 * support_vector_coef(i) * support_vector_coef(j);
00285 #ifndef NDEBUG
00286
00287 REAL ve = svm_kernel(detail->model->SV[i],
00288 detail->model->SV[j], detail->param)
00289 * detail->model->sv_coef[0][i] * detail->model->sv_coef[0][j];
00290 #endif
00291 assert(std::fabs(ip - ve) < EPSILON);
00292 sum += ip + (i==j? 0 : ip);
00293 }
00294 }
00295 assert(sum > 0);
00296 return std::sqrt(sum);
00297 }
00298
00299 Output SVM::operator() (const Input& x) const {
00300 assert(x.size() == n_input());
00301 assert(detail && detail->model);
00302
00303 REAL y = (signed_margin(x) > 0? 1 : -1);
00304 #ifndef NDEBUG
00305 struct svm_node sx[n_input()+1];
00306 fill_svm_node(x, sx);
00307 REAL l = svm_predict(detail->model, sx);
00308 #endif
00309 assert(std::fabs(y - l) < INFINITESIMAL);
00310
00311 return Output(1, y);
00312 }
00313
00314 Input SVM::support_vector (UINT i) const {
00315 assert(i < n_support_vectors());
00316 assert(detail->n_class == 2);
00317
00318 svm_node *SVi = detail->model->SV[i];
00319
00320 Input sv(_n_in, 0);
00321 for (; SVi->index != -1; ++SVi) {
00322 assert(SVi->index > 0 && (UINT) SVi->index <= sv.size());
00323 sv[SVi->index-1] = SVi->value;
00324 }
00325 return sv;
00326 }
00327
00328 REAL SVM::support_vector_coef (UINT i) const {
00329 assert(i < n_support_vectors());
00330 assert(detail->n_class == 2);
00331
00332 REAL coef = detail->model->sv_coef[0][i];
00333 return (detail->labels[0] < detail->labels[1])?
00334 -coef : coef;
00335 }
00336
00337 REAL SVM::bias () const {
00338 assert(detail && detail->model);
00339 assert(detail->n_class == 2);
00340
00341 REAL rho = detail->model->rho[0];
00342 return (detail->labels[0] < detail->labels[1])?
00343 rho : -rho;
00344 }
00345
00346 }