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.classification.sgd.kernel;
018
019import com.oracle.labs.mlrg.olcut.config.Config;
020import com.oracle.labs.mlrg.olcut.provenance.Provenance;
021import org.tribuo.Dataset;
022import org.tribuo.Example;
023import org.tribuo.ImmutableFeatureMap;
024import org.tribuo.ImmutableOutputInfo;
025import org.tribuo.Trainer;
026import org.tribuo.WeightedExamples;
027import org.tribuo.classification.Label;
028import org.tribuo.classification.sgd.Util;
029import org.tribuo.math.kernel.Kernel;
030import org.tribuo.math.la.DenseMatrix;
031import org.tribuo.math.la.DenseVector;
032import org.tribuo.math.la.SGDVector;
033import org.tribuo.math.la.SparseVector;
034import org.tribuo.provenance.ModelProvenance;
035import org.tribuo.provenance.TrainerProvenance;
036import org.tribuo.provenance.impl.TrainerProvenanceImpl;
037
038import java.time.OffsetDateTime;
039import java.util.HashMap;
040import java.util.Map;
041import java.util.SplittableRandom;
042import java.util.logging.Logger;
043
044/**
045 * A trainer for a kernelised model using the Pegasos optimiser.
046 * <p>
047 * The Pegasos optimiser is extremely sensitive to the lambda parameter, and this
048 * value must be tuned to get good performance.
049 * <p>
050 * See:
051 * <pre>
052 * Shalev-Shwartz S, Singer Y, Srebro N, Cotter A
053 * "Pegasos: Primal Estimated Sub-Gradient Solver for SVM"
054 * Mathematical Programming, 2011.
055 * </pre>
056 */
057public class KernelSVMTrainer implements Trainer<Label>, WeightedExamples {
058    private static final Logger logger = Logger.getLogger(KernelSVMTrainer.class.getName());
059
060    @Config(mandatory = true,description="SVM kernel.")
061    private Kernel kernel;
062
063    @Config(mandatory = true,description="Step size.")
064    private double lambda;
065
066    @Config(description="Number of SGD epochs.")
067    private int epochs = 5;
068
069    @Config(description="Log values after this many updates.")
070    private int loggingInterval = -1;
071
072    @Config(mandatory = true,description="Seed for the RNG used to shuffle elements.")
073    private long seed;
074
075    @Config(description="Shuffle the data before each epoch. Only turn off for debugging.")
076    private boolean shuffle = true;
077
078    private SplittableRandom rng;
079
080    private int trainInvocationCounter;
081
082    /**
083     * Constructs a trainer for a kernel SVM model.
084     * @param kernel The kernel function to use as a similarity measure.
085     * @param epochs The number of epochs (complete passes through the training data).
086     * @param lambda l2 regulariser on the support vectors.
087     * @param loggingInterval Log the loss after this many iterations. If -1 don't log anything.
088     * @param seed A seed for the random number generator, used to shuffle the examples before each epoch.
089     */
090    public KernelSVMTrainer(Kernel kernel, double lambda, int epochs, int loggingInterval, long seed) {
091        this.kernel = kernel;
092        this.lambda = lambda;
093        this.epochs = epochs;
094        this.loggingInterval = loggingInterval;
095        this.seed = seed;
096        postConfig();
097    }
098
099    /**
100     * Constructs a trainer for a kernel SVM model.
101     * Sets the logging interval to 1000.
102     * @param kernel The kernel function to use as a similarity measure.
103     * @param lambda l2 regulariser on the support vectors.
104     * @param epochs The number of epochs (complete passes through the training data).
105     * @param seed A seed for the random number generator, used to shuffle the examples before each epoch.
106     */
107    public KernelSVMTrainer(Kernel kernel, double lambda, int epochs, long seed) {
108        this(kernel,lambda,epochs,1000,seed);
109    }
110
111    /**
112     * For olcut.
113     */
114    private KernelSVMTrainer() { }
115
116    /**
117     * Used by the OLCUT configuration system, and should not be called by external code.
118     */
119    @Override
120    public synchronized void postConfig() {
121        this.rng = new SplittableRandom(seed);
122    }
123
124    /**
125     * Turn on or off shuffling of examples.
126     * <p>
127     * This isn't exposed in the constructor as it defaults to on.
128     * This method should only be used for debugging.
129     * @param shuffle If true shuffle the examples, if false leave them in their current order.
130     */
131    public void setShuffle(boolean shuffle) {
132        this.shuffle = shuffle;
133    }
134
135    @Override
136    public KernelSVMModel train(Dataset<Label> examples, Map<String, Provenance> runProvenance) {
137        return(train(examples, runProvenance, INCREMENT_INVOCATION_COUNT));
138    }
139
140    @Override
141    public KernelSVMModel train(Dataset<Label> examples, Map<String, Provenance> runProvenance, int invocationCount) {
142        if (examples.getOutputInfo().getUnknownCount() > 0) {
143            throw new IllegalArgumentException("The supplied Dataset contained unknown Outputs, and this Trainer is supervised.");
144        }
145        // Creates a new RNG, adds one to the invocation count.
146        TrainerProvenance trainerProvenance;
147        SplittableRandom localRNG;
148        synchronized(this) {
149            if(invocationCount != INCREMENT_INVOCATION_COUNT) {
150                setInvocationCount(invocationCount);
151            }
152            localRNG = rng.split();
153            trainerProvenance = getProvenance();
154            trainInvocationCounter++;
155        }
156        ImmutableOutputInfo<Label> labelIDMap = examples.getOutputIDInfo();
157        ImmutableFeatureMap featureIDMap = examples.getFeatureIDMap();
158        SparseVector[] sgdFeatures = new SparseVector[examples.size()];
159        int[] sgdLabels = new int[examples.size()];
160        double[] weights = new double[examples.size()];
161        int[] indices = new int[examples.size()];
162        int n = 0;
163        for (Example<Label> example : examples) {
164            weights[n] = example.getWeight();
165            sgdFeatures[n] = SparseVector.createSparseVector(example,featureIDMap,true);
166            sgdLabels[n] = labelIDMap.getID(example.getOutput());
167            indices[n] = n;
168            n++;
169        }
170        logger.info(String.format("Training Kernel SVM with %d examples", n));
171        logger.info(labelIDMap.toReadableString());
172
173        double loss = 0.0;
174        int iteration = 0;
175        Map<Integer,SparseVector> supportVectors = new HashMap<>();
176        double[][] alphas = new double[labelIDMap.size()][examples.size()];
177
178        for (int i = 0; i < epochs; i++) {
179            if (shuffle) {
180                Util.shuffleInPlace(sgdFeatures, sgdLabels, weights, indices, localRNG);
181            }
182            for (int j = 0; j < sgdFeatures.length; j++) {
183                SGDVector pred = predict(sgdFeatures[j],supportVectors,alphas);
184                pred.add(sgdLabels[j],-1.0);
185                int predIndex = pred.indexOfMax();
186
187                if (sgdLabels[j] != predIndex) {
188                    loss += (pred.get(sgdLabels[j]) - pred.get(predIndex)) * weights[j];
189                    supportVectors.putIfAbsent(indices[j],sgdFeatures[j]);
190                    alphas[sgdLabels[j]][indices[j]] += weights[j];
191                }
192
193                iteration++;
194                if ((loggingInterval != -1) && (iteration % loggingInterval == 0)) {
195                    logger.info("At iteration " + iteration + ", average loss = " + loss/loggingInterval + " with " + supportVectors.size() + " support vectors.");
196                    loss = 0.0;
197                }
198            }
199            logger.fine("Finished epoch " + i);
200        }
201
202        DenseMatrix alphaMatrix = new DenseMatrix(alphas.length,supportVectors.size());
203        for (int i = 0; i < alphas.length; i++) {
204            int rowCounter = 0;
205            for (int j = 0; j < sgdFeatures.length; j++) {
206                if (supportVectors.containsKey(j)) {
207                    alphaMatrix.set(i, rowCounter, alphas[i][j]);
208                    rowCounter++;
209                }
210            }
211        }
212
213        int counter = 0;
214        SparseVector[] supportArray = new SparseVector[supportVectors.size()];
215        for (int i = 0; i < sgdFeatures.length; i++) {
216            SparseVector value = supportVectors.get(i);
217            if (value != null) {
218                supportArray[counter] = value;
219                counter++;
220            }
221        }
222
223        ModelProvenance provenance = new ModelProvenance(KernelSVMModel.class.getName(), OffsetDateTime.now(), examples.getProvenance(), trainerProvenance, runProvenance);
224        //public KernelSVMModel(String name, String description, ImmutableInfoMap featureIDMap, ImmutableInfoMap outputIDInfo, Kernel kernel, SparseVector[] supportVectors, DenseMatrix weights)
225        KernelSVMModel model = new KernelSVMModel("kernel-model",provenance,featureIDMap,labelIDMap,kernel,supportArray,alphaMatrix);
226        return model;
227    }
228
229    @Override
230    public int getInvocationCount() {
231        return trainInvocationCounter;
232    }
233
234    @Override
235    public synchronized void setInvocationCount(int invocationCount){
236        if(invocationCount < 0){
237            throw new IllegalArgumentException("The supplied invocationCount is less than zero.");
238        }
239
240        rng = new SplittableRandom(seed);
241
242        for (trainInvocationCounter = 0; trainInvocationCounter < invocationCount; trainInvocationCounter++){
243            SplittableRandom localRNG = rng.split();
244        }
245
246    }
247
248    @Override
249    public String toString() {
250        return "KernelSVMTrainer(kernel="+kernel.toString()+",lambda="+lambda+",epochs="+epochs+",seed="+seed+")";
251    }
252
253    private SGDVector predict(SparseVector features, Map<Integer,SparseVector> sv, double[][] alphas) {
254        double[] score = new double[alphas.length];
255
256        for (Map.Entry<Integer, SparseVector> e : sv.entrySet()) {
257            double distance = kernel.similarity(features,e.getValue());
258            for (int i = 0; i < alphas.length; i++) {
259                score[i] += alphas[i][e.getKey()] * distance;
260            }
261        }
262
263        return DenseVector.createDenseVector(score);
264    }
265
266    @Override
267    public TrainerProvenance getProvenance() {
268        return new TrainerProvenanceImpl(this);
269    }
270}