Source code

001/*
002 * Copyright (c) 2015-2021, Oracle and/or its affiliates. All rights reserved.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.tribuo.common.libsvm;
018
019import com.oracle.labs.mlrg.olcut.config.Config;
020import com.oracle.labs.mlrg.olcut.provenance.Provenance;
021import com.oracle.labs.mlrg.olcut.util.Pair;
022import libsvm.svm_model;
023import libsvm.svm_node;
024import libsvm.svm_parameter;
025import org.tribuo.Dataset;
026import org.tribuo.Example;
027import org.tribuo.Feature;
028import org.tribuo.ImmutableFeatureMap;
029import org.tribuo.ImmutableOutputInfo;
030import org.tribuo.Output;
031import org.tribuo.Trainer;
032import org.tribuo.provenance.ModelProvenance;
033import org.tribuo.provenance.TrainerProvenance;
034import org.tribuo.provenance.impl.TrainerProvenanceImpl;
035import org.tribuo.util.Util;
036
037import java.time.OffsetDateTime;
038import java.util.ArrayList;
039import java.util.Collections;
040import java.util.List;
041import java.util.Map;
042import java.util.SplittableRandom;
043import java.util.logging.Logger;
044
045/**
046 * A trainer that will train using libsvm's Java implementation.
047 * <p>
048 * Note the train method is synchronized on {@code LibSVMTrainer.class} due to a global RNG in LibSVM.
049 * This is insufficient to ensure reproducibility if LibSVM is used directly in the same JVM as Tribuo, but
050 * avoids locking on classes Tribuo does not control.
051 * <p>
052 * See:
053 * <pre>
054 * Chang CC, Lin CJ.
055 * "LIBSVM: a library for Support Vector Machines"
056 * ACM transactions on intelligent systems and technology (TIST), 2011.
057 * </pre>
058 * for the nu-svm algorithm:
059 * <pre>
060 * Schölkopf B, Smola A, Williamson R, Bartlett P L.
061 * "New support vector algorithms"
062 * Neural Computation, 2000, 1207-1245.
063 * </pre>
064 * and for the original algorithm:
065 * <pre>
066 * Cortes C, Vapnik V.
067 * "Support-Vector Networks"
068 * Machine Learning, 1995.
069 * </pre>
070 */
071public abstract class LibSVMTrainer<T extends Output<T>> implements Trainer<T> {
072    
073    private static final Logger logger = Logger.getLogger(LibSVMTrainer.class.getName());
074
075    /**
076     * The SVM parameters suitable for use by LibSVM.
077     */
078    protected svm_parameter parameters;
079
080    /**
081     * The type of SVM algorithm.
082     */
083    @Config(mandatory=true,description="Type of SVM algorithm.")
084    protected SVMType<T> svmType;
085
086    @Config(description="Type of Kernel.")
087    private KernelType kernelType = KernelType.LINEAR;
088
089    @Config(description="Polynomial degree.")
090    private int degree = 3;
091
092    @Config(description="Width of the RBF kernel, or scalar on sigmoid kernel.")
093    private double gamma = 0.0;
094
095    @Config(description="Polynomial coefficient or shift in sigmoid kernel.")
096    private double coef0 = 0.0;
097
098    @Config(description="nu value in NU SVM.")
099    private double nu = 0.5;
100
101    @Config(description="Internal cache size, most of the time should be left at default.")
102    private double cache_size = 500;
103
104    @Config(description="Cost parameter for incorrect predictions.")
105    private double cost = 1.0; // aka svm_parameters.C
106
107    @Config(description="Tolerance of the termination criterion.")
108    private double eps = 1e-3;
109
110    @Config(description="Epsilon in EPSILON_SVR.")
111    private double p = 1e-3;
112
113    @Config(description="Regularise the weight parameters.")
114    private boolean shrinking = true;
115
116    @Config(description="Generate probability estimates.")
117    private boolean probability = false;
118
119    @Config(description="RNG seed.")
120    private long seed = Trainer.DEFAULT_SEED;
121
122    private SplittableRandom rng;
123
124    private int trainInvocationCounter = 0;
125
126    /**
127     * For olcut.
128     */
129    protected LibSVMTrainer() {}
130
131    /**
132     * Constructs a LibSVMTrainer from the parameters.
133     * @param parameters The SVM parameters.
134     * @param seed The RNG seed.
135     */
136    protected LibSVMTrainer(SVMParameters<T> parameters, long seed) {
137        this.parameters = parameters.getParameters();
138        // Unpack the parameters for the provenance system.
139        this.svmType = parameters.getSvmType();
140        this.kernelType = parameters.getKernelType();
141        this.degree = this.parameters.degree;
142        this.gamma = parameters.getGamma();
143        this.coef0 = this.parameters.coef0;
144        this.nu = this.parameters.nu;
145        this.cache_size = this.parameters.cache_size;
146        this.cost = this.parameters.C;
147        this.eps = this.parameters.eps;
148        this.p = this.parameters.p;
149        this.shrinking = this.parameters.shrinking == 1;
150        this.probability = this.parameters.probability == 1;
151        this.seed = seed;
152        this.rng = new SplittableRandom(seed);
153    }
154
155    /**
156     * Used by the OLCUT configuration system, and should not be called by external code.
157     */
158    @Override
159    public void postConfig() {
160        parameters = new svm_parameter();
161        parameters.svm_type = svmType.getNativeType();
162        parameters.kernel_type = kernelType.getNativeType();
163        parameters.degree = degree;
164        parameters.gamma = gamma;
165        parameters.coef0 = coef0;
166        parameters.nu = nu;
167        parameters.cache_size = cache_size;
168        parameters.C = cost;
169        parameters.eps = eps;
170        parameters.p = p;
171        parameters.shrinking = shrinking ? 1 : 0;
172        parameters.probability = probability ? 1 : 0;
173        this.rng = new SplittableRandom(seed);
174    }
175
176    @Override
177    public String toString() {
178        StringBuilder buffer = new StringBuilder();
179
180        buffer.append("LibSVMTrainer(");
181        buffer.append("svm_params=");
182        buffer.append(SVMParameters.svmParamsToString(parameters));
183        buffer.append(",seed=");
184        buffer.append(seed);
185        buffer.append(")");
186
187        return buffer.toString();
188    }
189
190    @Override
191    public LibSVMModel<T> train(Dataset<T> examples) {
192        return train(examples, Collections.emptyMap());
193    }
194
195    @Override
196    public LibSVMModel<T> train(Dataset<T> examples, Map<String, Provenance> runProvenance) {
197        return (train(examples, runProvenance, INCREMENT_INVOCATION_COUNT));
198    }
199
200    @Override
201    public LibSVMModel<T> train(Dataset<T> examples, Map<String, Provenance> runProvenance, int invocationCount) {
202        if (examples.getOutputInfo().getUnknownCount() > 0) {
203            throw new IllegalArgumentException("The supplied Dataset contained unknown Outputs, and this Trainer is supervised.");
204        }
205        ImmutableFeatureMap featureIDMap = examples.getFeatureIDMap();
206        ImmutableOutputInfo<T> outputIDInfo = examples.getOutputIDInfo();
207
208        // Creates a new RNG, adds one to the invocation count, generates a local optimiser.
209        TrainerProvenance trainerProvenance;
210        SplittableRandom localRNG;
211        synchronized(this) {
212            if(invocationCount != INCREMENT_INVOCATION_COUNT) {
213                setInvocationCount(invocationCount);
214            }
215            localRNG = rng.split();
216            trainerProvenance = getProvenance();
217            trainInvocationCounter++;
218        }
219
220        svm_parameter curParams = setupParameters(outputIDInfo);
221
222        Pair<svm_node[][],double[][]> data = extractData(examples,outputIDInfo,featureIDMap);
223
224        List<svm_model> models;
225        synchronized (LibSVMTrainer.class) {
226            // localRNG is used to seed LibSVM's global RNG before each call to svm.svm_train
227            models = trainModels(curParams, featureIDMap.size() + 1, data.getA(), data.getB(), localRNG);
228        }
229
230        ModelProvenance provenance = new ModelProvenance(LibSVMModel.class.getName(), OffsetDateTime.now(), examples.getProvenance(), trainerProvenance, runProvenance);
231        return createModel(provenance,featureIDMap,outputIDInfo,models);
232    }
233
234    /**
235     * Construct the appropriate subtype of LibSVMModel for the prediction task.
236     * @param provenance The model provenance.
237     * @param featureIDMap The feature id map.
238     * @param outputIDInfo The output id info.
239     * @param models The svm models.
240     * @return An implementation of LibSVMModel.
241     */
242    protected abstract LibSVMModel<T> createModel(ModelProvenance provenance, ImmutableFeatureMap featureIDMap, ImmutableOutputInfo<T> outputIDInfo, List<svm_model> models);
243
244    /**
245     * Train all the LibSVM instances necessary for this dataset.
246     * @param curParams The LibSVM parameters.
247     * @param numFeatures The number of features in this dataset.
248     * @param features The features themselves.
249     * @param outputs The outputs.
250     * @param localRNG The RNG to use for seeding LibSVM's RNG.
251     * @return A list of LibSVM models.
252     */
253    protected abstract List<svm_model> trainModels(svm_parameter curParams, int numFeatures, svm_node[][] features, double[][] outputs, SplittableRandom localRNG);
254
255    /**
256     * Extracts the features and {@link Output}s in LibSVM's format.
257     * @param data The input data.
258     * @param outputInfo The output info.
259     * @param featureMap The feature info.
260     * @return The features and outputs.
261     */
262    protected abstract Pair<svm_node[][],double[][]> extractData(Dataset<T> data, ImmutableOutputInfo<T> outputInfo, ImmutableFeatureMap featureMap);
263
264    /**
265     * Constructs the svm_parameter. Most of the time this is a no-op, but
266     * classification overrides it to incorporate label weights if they exist.
267     * @param info The output info.
268     * @return The svm_parameters to use for training.
269     */
270    protected svm_parameter setupParameters(ImmutableOutputInfo<T> info) {
271        return SVMParameters.copyParameters(parameters);
272    }
273
274    @Override
275    public int getInvocationCount() {
276        return trainInvocationCounter;
277    }
278
279    @Override
280    public synchronized void setInvocationCount(int invocationCount) {
281        if(invocationCount < 0){
282            throw new IllegalArgumentException("The supplied invocationCount is less than zero.");
283        }
284
285        rng = new SplittableRandom(seed);
286
287        for (trainInvocationCounter = 0; trainInvocationCounter < invocationCount; trainInvocationCounter++){
288            SplittableRandom localRNG = rng.split();
289        }
290    }
291
292    /**
293     * Convert the example into an array of svm_node which represents a sparse feature vector.
294     * <p>
295     * If there are collisions in the feature ids then the values are summed.
296     * @param example The example to convert.
297     * @param featureIDMap The feature id map which holds the indices.
298     * @param features A buffer to use.
299     * @param <T> The type of the ouput.
300     * @return A sparse feature vector.
301     */
302    public static <T extends Output<T>> svm_node[] exampleToNodes(Example<T> example, ImmutableFeatureMap featureIDMap, List<svm_node> features) {
303        if (features == null) {
304            features = new ArrayList<>();
305        }
306        features.clear();
307        int prevIdx = -1;
308        for (Feature f : example) {
309            int id = featureIDMap.getID(f.getName());
310            double value = f.getValue();
311            if (id > prevIdx){
312                prevIdx = id;
313                svm_node n = new svm_node();
314                n.index = id;
315                n.value = value;
316                features.add(n);
317            } else if (id > -1) {
318                //
319                // Collision, deal with it.
320                int collisionIdx = Util.binarySearch(features,id,(svm_node n) -> n.index);
321                if (collisionIdx < 0) {
322                    //
323                    // Collision but not present in features
324                    // move data and bump i
325                    collisionIdx = - (collisionIdx + 1);
326                    svm_node n = new svm_node();
327                    n.index = id;
328                    n.value = value;
329                    features.add(collisionIdx,n);
330                } else {
331                    //
332                    // Collision present in features
333                    // add the values.
334                    svm_node n = features.get(collisionIdx);
335                    n.value += value;
336                }
337            }
338        }
339        return features.toArray(new svm_node[0]);
340    }
341
342    @Override
343    public TrainerProvenance getProvenance() {
344        return new TrainerProvenanceImpl(this);
345    }
346}
347