source: orange/source/orange/liblinear_interface.cpp @ 11670:d967a4ceb8b4

Revision 11670:d967a4ceb8b4, 12.9 KB checked in by Björn Esser <bjoern.esser@…>, 8 months ago (diff)

Updated the included LIBLINEAR to version 1.93.

Line 
1/*
2    This file is part of Orange.
3
4    Copyright 1996-2011 Faculty of Computer and Information Science, University of Ljubljana
5    Contact: janez.demsar@fri.uni-lj.si
6
7    Orange is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation, either version 3 of the License, or
10    (at your option) any later version.
11
12    Orange is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with Orange.  If not, see <http://www.gnu.org/licenses/>.
19*/
20
21#include <iostream>
22#include <sstream>
23
24#include <math.h>
25#include <stdio.h>
26#include <stdlib.h>
27#include <string.h>
28#include <stdarg.h>
29#include <assert.h>
30
31#include "liblinear_interface.ppp"
32
33#define Malloc(type,n) (type *) malloc((n)*sizeof(type))
34
35// Defined in linear.cpp. If a new solver is added this should be updated.
36
37static const char *solver_type_table[]=
38{
39    "L2R_LR", "L2R_L2LOSS_SVC_DUAL", "L2R_L2LOSS_SVC", "L2R_L1LOSS_SVC_DUAL", "MCSVM_CS",
40    "L1R_L2LOSS_SVC", "L1R_LR", "L2R_LR_DUAL",
41
42    #ifndef WITH_API_LIBLINEAR18
43        "", "", "",
44        "L2R_L2LOSS_SVR", "L2R_L2LOSS_SVR_DUAL", "L2R_L1LOSS_SVR_DUAL",
45    #endif
46
47    NULL
48};
49
50/*
51 *The folowing load save functions are used for orange pickling
52 */
53
54/*
55 * Save the model to an std::ostream. This is a modified `save_model` function
56 * from `linear.cpp` in LIBLINEAR package.
57 */
58int linear_save_model_alt(ostream &stream, struct model *model_)
59{
60    int i;
61    int nr_feature=model_->nr_feature;
62    int n;
63    const parameter& param = model_->param;
64
65    if(model_->bias>=0)
66        n=nr_feature+1;
67    else
68        n=nr_feature;
69
70    int nr_classifier;
71    if(model_->nr_class==2 && model_->param.solver_type != MCSVM_CS)
72        nr_classifier=1;
73    else
74        nr_classifier=model_->nr_class;
75
76    stream.precision(17);
77
78    stream << "solver_type " << solver_type_table[param.solver_type] << endl;
79    stream << "nr_class " << model_->nr_class << endl;
80    stream << "label";
81    for(i=0; i<model_->nr_class; i++)
82        stream << " " << model_->label[i];
83    stream << endl;
84
85    stream << "nr_feature " << nr_feature << endl;
86
87    stream << "bias " << model_->bias << endl;
88
89    stream << "w" << endl;
90    for(i=0; i<n; i++)
91    {
92        int j;
93        for(j=0; j<nr_classifier; j++)
94            stream << model_->w[i*nr_classifier+j] << " ";
95        stream << endl;
96    }
97
98    if (stream.good())
99        return 0;
100    else
101        return -1;
102}
103
104/*
105 * Save linear model into a std::string.
106 */
107int linear_save_model_alt(string &buffer, struct model *model_)
108{
109    std::ostringstream strstream;
110    int ret = linear_save_model_alt(strstream, model_);
111    buffer = strstream.rdbuf()->str();
112    return ret;
113}
114
115/*
116 * Load a linear model from std::istream. This is a modified `load_model`
117 * function from `linear.cpp` in LIBLINEAR package.
118 */
119struct model *linear_load_model_alt(istream &stream)
120{
121    int i;
122    int nr_feature;
123    int n;
124    int nr_class;
125    double bias;
126    model *model_ = Malloc(model,1);
127    parameter& param = model_->param;
128
129    model_->label = NULL;
130
131    char cmd[81];
132    stream.width(80);
133    while(stream.good())
134    {
135        stream >> cmd;
136        if(strcmp(cmd, "solver_type")==0)
137        {
138            stream >> cmd;
139            int i;
140            for(i=0;solver_type_table[i];i++)
141            {
142                if(strcmp(solver_type_table[i],cmd)==0)
143                {
144                    param.solver_type=i;
145                    break;
146                }
147            }
148            if(solver_type_table[i] == NULL)
149            {
150                fprintf(stderr,"unknown solver type.\n");
151                free(model_->label);
152                free(model_);
153                return NULL;
154            }
155        }
156        else if(strcmp(cmd,"nr_class")==0)
157        {
158            stream >> nr_class;
159            model_->nr_class=nr_class;
160        }
161        else if(strcmp(cmd,"nr_feature")==0)
162        {
163            stream >> nr_feature;
164            model_->nr_feature=nr_feature;
165        }
166        else if(strcmp(cmd,"bias")==0)
167        {
168            stream >> bias;
169            model_->bias=bias;
170        }
171        else if(strcmp(cmd,"w")==0)
172        {
173            break;
174        }
175        else if(strcmp(cmd,"label")==0)
176        {
177            int nr_class = model_->nr_class;
178            model_->label = Malloc(int, nr_class);
179            for(int i=0;i<nr_class;i++)
180                stream >> model_->label[i];
181        }
182        else
183        {
184            fprintf(stderr,"unknown text in model file: [%s]\n",cmd);
185            free(model_->label);
186            free(model_);
187            return NULL;
188        }
189    }
190
191    nr_feature=model_->nr_feature;
192    if(model_->bias>=0)
193        n=nr_feature+1;
194    else
195        n=nr_feature;
196
197    int nr_classifier;
198    if(nr_class==2 && param.solver_type != MCSVM_CS)
199        nr_classifier = 1;
200    else
201        nr_classifier = nr_class;
202
203    model_->w=Malloc(double, n*nr_classifier);
204    for(i=0; i<n; i++)
205    {
206        int j;
207        for(j=0; j<nr_classifier; j++)
208            stream >> model_->w[i*nr_classifier+j];
209    }
210    if (stream.fail())
211        return NULL;
212    else
213        return model_;
214}
215
216/*
217 * Load a linear model from a std:string.
218 */
219struct model *linear_load_model_alt(string &buffer)
220{
221    std::istringstream str_stream(buffer);
222    str_stream.exceptions(ios::failbit | ios::badbit);
223    return linear_load_model_alt(str_stream);
224}
225
226struct NodeSort{
227    bool operator () (const feature_node &lhs, const feature_node &rhs){
228        return lhs.index < rhs.index;
229    }
230};
231
232int countFeatures(const TExample &ex, bool includeMeta, bool includeRegular){
233    int count = 1;
234    if (includeRegular)
235        for (TExample::iterator i=ex.begin(); i!=ex.end(); i++)
236            if ((i->varType==TValue::INTVAR || i->varType==TValue::FLOATVAR) && i->isRegular() && i!=&ex.getClass())
237                count++;
238    if (includeMeta)
239        for (TMetaValues::const_iterator i=ex.meta.begin(); i!=ex.meta.end(); i++)
240            if ((i->second.varType==TValue::INTVAR || i->second.varType==TValue::FLOATVAR) && i->second.isRegular())
241                count++;
242    return count;
243}
244
245feature_node *feature_nodeFromExample(const TExample &ex, double bias){
246    int n_nodes = countFeatures(ex, false, true);
247
248    if (bias >= 0.0)
249        n_nodes++;
250
251    feature_node *nodes = new feature_node[n_nodes];
252    feature_node *ptr = nodes;
253
254    int index = 1;
255
256    for (TExample::iterator i=ex.begin(); i!=ex.end(); i++)
257        if (i!=&ex.getClass()){
258            if ((i->varType==TValue::INTVAR || (i->varType==TValue::FLOATVAR && (*i==*i))) && i->isRegular()){
259                if (i->varType==TValue::INTVAR)
260                    ptr->value = (int) *i;
261                else
262                    ptr->value = (float) *i;
263                ptr->index = index;
264                ptr++;
265            }
266            index++;
267        }
268
269    if (bias >= 0.0)
270    {
271        ptr->value = bias;
272        ptr->index = index;
273        ptr++;
274    }
275
276    ptr->index = -1;
277    return nodes;
278}
279
280problem *problemFromExamples(PExampleGenerator examples, double bias){
281    problem *prob = new problem;
282    prob->l = examples->numberOfExamples();
283    prob->n = examples->domain->attributes->size();
284
285    if (bias >= 0)
286        prob->n++;
287
288    prob->x = new feature_node* [prob->l];
289
290    #ifndef WITH_API_LIBLINEAR18
291        prob->y = new double [prob->l];
292    #else
293        prob->y = new int [prob->l];
294    #endif
295
296    prob->bias = bias;
297    feature_node **ptrX = prob->x;
298
299    #ifndef WITH_API_LIBLINEAR18
300        double *ptrY = prob->y;
301    #else
302        int *ptrY = prob->y;
303    #endif
304
305    PEITERATE(iter, examples){
306        *ptrX = feature_nodeFromExample(*iter, bias);
307
308        #ifndef WITH_API_LIBLINEAR18
309            *ptrY = (double) (*iter).getClass().intV;
310        #else
311            *ptrY = (int) (*iter).getClass();
312        #endif
313
314        ptrX++;
315        ptrY++;
316    }
317    return prob;
318}
319
320void destroy_problem(problem *prob){
321    for (int i = 0; i < prob->l; i++)
322        delete[] prob->x[i];
323    delete[] prob->x;
324    delete[] prob->y;
325}
326
327static void dont_print_string(const char *s){}
328
329
330/*
331 * Extract feature weights from a LIBLINEAR model.
332 * The number of class values must be provided.
333 */
334
335TFloatListList * extract_feature_weights(model * model, int nr_class_values) {
336    /* Number of liblinear classifiers.
337     *
338     * NOTE: If some class values do not have any data instances in
339     * the training set they are not present in the liblinear model
340     * so this number might be different than nr_class_values.
341     */
342    int nr_classifier = model->nr_class;
343    if (model->nr_class == 2 && model->param.solver_type != MCSVM_CS) {
344        // model contains a single weight vector
345        nr_classifier = 1;
346    }
347
348    // Number of weight vectors to return.
349    int nr_orange_weights = nr_class_values;
350    if (nr_class_values == 2 && model->param.solver_type != MCSVM_CS) {
351        nr_orange_weights = 1;
352    }
353
354    assert(nr_orange_weights >= nr_classifier);
355
356    int nr_feature = model->nr_feature;
357
358    if (model->bias >= 0.0){
359        nr_feature++;
360    }
361
362    int* labels = new int[model->nr_class];
363    get_labels(model, labels);
364
365    // Initialize the weight matrix (nr_orange_weights x nr_features).
366    TFloatListList * weights = mlnew TFloatListList(nr_orange_weights);
367    for (int i = 0; i < nr_orange_weights; i++){
368        weights->at(i) = mlnew TFloatList(nr_feature, 0.0f);
369    }
370
371    if (nr_classifier > 1) {
372        /*
373         * NOTE: If some class was missing from the training data set
374         * (had no instances) its weight vector will be left initialized
375         * to 0
376         */
377        for (int i = 0; i < nr_classifier; i++) {
378            for (int j = 0; j < nr_feature; j++) {
379                weights->at(labels[i])->at(j) = model->w[j * nr_classifier + i];
380            }
381        }
382    } else {
383        for (int j = 0; j < nr_feature; j++) {
384            if (nr_orange_weights > 1) {
385                /* There were more than 2 orange class values. This means
386                 * there were no instances for one or more classed in the
387                 * training data set. We cannot simply leave the 'negative'
388                 * class vector as zero because we would lose information
389                 * which class was used (i.e. we could not make a proper
390                 * negative classification using the weights).
391                 */
392                weights->at(labels[0])->at(j) = model->w[j];
393                weights->at(labels[1])->at(j) = - model->w[j];
394            } else {
395                weights->at(0)->at(j) = model->w[j];
396            }
397        }
398    }
399
400    delete[] labels;
401
402    return weights;
403}
404
405
406TLinearLearner::TLinearLearner(){
407    solver_type = L2R_LR;
408    eps = 0.01f;
409    C = 1;
410    bias = -1.0;
411    set_print_string_function(&dont_print_string);
412}
413
414
415PClassifier TLinearLearner::operator()(PExampleGenerator examples, const int &weight){
416    PDomain domain = examples->domain;
417
418    if (!domain->classVar) {
419        raiseError("classVar expected");
420    }
421
422    if (domain->classVar->varType != TValue::INTVAR) {
423        raiseError("Discrete class expected");
424    }
425
426    parameter *param = new parameter;
427    param->solver_type = solver_type;
428    param->eps = eps;
429    param->C = C;
430    param->nr_weight = 0;
431    param->weight_label = NULL;
432    param->weight = NULL;
433
434    #ifndef WITH_API_LIBLINEAR18
435        param->p = NULL;
436    #endif
437
438    // Shallow copy of examples.
439    PExampleTable train_data = mlnew TExampleTable(examples, /* owns= */ false);
440
441    /*
442     * Sort the training instances by class.
443     * This is necessary because LIBLINEAR's class/label/weight order
444     * is defined by the order of labels encountered in the training
445     * data. By sorting we make sure it matches classVar.values order.
446     */
447    vector<int> sort_column(domain->variables->size() - 1);
448    train_data->sort(sort_column);
449
450    problem *prob = problemFromExamples(train_data, bias);
451
452    const char * error_msg = check_parameter(prob, param);
453    if (error_msg){
454        delete param;
455        destroy_problem(prob);
456        raiseError("LIBLINEAR error: %s", error_msg);
457    }
458    /* The solvers in liblinear use rand() function.
459     * To make the results reproducible we set the seed from the data table's
460     * crc.
461     */
462    srand(train_data->checkSum(false));
463
464    model *model = train(prob, param);
465    destroy_problem(prob);
466
467    return PClassifier(mlnew TLinearClassifier(domain, model));
468}
469
470
471/*
472 * Construct a TLinearClassifer given a domain and a trained LIBLINEAR
473 * constructed model.
474 */
475
476TLinearClassifier::TLinearClassifier(PDomain domain, struct model * model) : TClassifierFD(domain) {
477    linmodel = model;
478    bias = model->bias;
479    dbias = model->bias;
480
481    computesProbabilities = check_probability_model(linmodel) != 0;
482
483    weights = extract_feature_weights(model, get_nr_values());
484}
485
486
487TLinearClassifier::~TLinearClassifier() {
488    if (linmodel)
489        free_and_destroy_model(&linmodel);
490}
491
492/* Return the number of discrete class values, or raise an error
493 * if the class_var is not discrete.
494 */
495int TLinearClassifier::get_nr_values()
496{
497    int nr_values = 0;
498    TEnumVariable * enum_var = NULL;
499    enum_var = dynamic_cast<TEnumVariable*>(classVar.getUnwrappedPtr());
500    if (enum_var) {
501        nr_values = enum_var->noOfValues();
502    }
503    else {
504        raiseError("Discrete class expected.");
505    }
506    return nr_values;
507}
508
509PDistribution TLinearClassifier::classDistribution(const TExample &example){
510    TExample new_example(domain, example);
511    int numClass = get_nr_class(linmodel);
512
513    feature_node *x = feature_nodeFromExample(new_example, bias);
514
515    int *labels = new int [numClass];
516    get_labels(linmodel, labels);
517
518    double *prob_est = new double [numClass];
519    predict_probability(linmodel, x, prob_est);
520
521    PDistribution dist = TDistribution::create(classVar);
522    for (int i=0; i<numClass; i++)
523        dist->setint(labels[i], prob_est[i]);
524
525    delete[] x;
526    delete[] labels;
527    delete[] prob_est;
528    return dist;
529}
530
531TValue TLinearClassifier::operator () (const TExample &example){
532    TExample new_example(domain, example);
533    int numClass = get_nr_class(linmodel);
534
535    feature_node *x = feature_nodeFromExample(new_example, bias);
536
537    #ifndef WITH_API_LIBLINEAR18
538        double predict_label = predict(linmodel, x);
539    #else
540        int predict_label = predict(linmodel, x);
541    #endif
542
543    delete[] x;
544
545    #ifndef WITH_API_LIBLINEAR18
546        return TValue((int) predict_label);
547    #else
548        return TValue(predict_label);
549    #endif
550}
Note: See TracBrowser for help on using the repository browser.