001/*
002 * Copyright (c) 2015, 2022, 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.xgboost;
018
019import com.oracle.labs.mlrg.olcut.config.Config;
020import com.oracle.labs.mlrg.olcut.config.PropertyException;
021import com.oracle.labs.mlrg.olcut.provenance.Provenance;
022import org.tribuo.Dataset;
023import org.tribuo.Example;
024import org.tribuo.Feature;
025import org.tribuo.ImmutableFeatureMap;
026import org.tribuo.ImmutableOutputInfo;
027import org.tribuo.Output;
028import org.tribuo.Trainer;
029import org.tribuo.WeightedExamples;
030import org.tribuo.math.la.SparseVector;
031import org.tribuo.math.la.VectorTuple;
032import org.tribuo.provenance.ModelProvenance;
033import org.tribuo.provenance.SkeletalTrainerProvenance;
034import org.tribuo.util.Util;
035import ml.dmlc.xgboost4j.java.Booster;
036import ml.dmlc.xgboost4j.java.DMatrix;
037import ml.dmlc.xgboost4j.java.XGBoostError;
038
039import java.util.ArrayList;
040import java.util.HashMap;
041import java.util.List;
042import java.util.Map;
043import java.util.function.Function;
044import java.util.logging.Logger;
045
046/**
047 * A {@link Trainer} which wraps the XGBoost training procedure.
048 * <p>
049 * This only exposes a few of XGBoost's training parameters.
050 * <p>
051 * It uses pthreads outside of the JVM to parallelise the computation.
052 * <p>
053 * See:
054 * <pre>
055 * Chen T, Guestrin C.
056 * "XGBoost: A Scalable Tree Boosting System"
057 * Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
058 * </pre>
059 * and for the original algorithm:
060 * <pre>
061 * Friedman JH.
062 * "Greedy Function Approximation: a Gradient Boosting Machine"
063 * Annals of statistics, 2001.
064 * </pre>
065 * N.B.: XGBoost4J wraps the native C implementation of xgboost that links to various C libraries, including libgomp
066 * and glibc (on Linux). If you're running on Alpine, which does not natively use glibc, you'll need to install glibc
067 * into the container.
068 * On the macOS binary on Maven Central is compiled without
069 * OpenMP support, meaning that XGBoost is single threaded on macOS. You can recompile the macOS binary with
070 * OpenMP support after installing libomp from homebrew if necessary.
071 */
072public abstract class XGBoostTrainer<T extends Output<T>> implements Trainer<T>, WeightedExamples {
073    /* Alpine install command
074     * <pre>
075     *    $ apk --no-cache add ca-certificates wget
076     *    $ wget -q -O /etc/apk/keys/sgerrand.rsa.pub https://alpine-pkgs.sgerrand.com/sgerrand.rsa.pub
077     *    $ wget https://github.com/sgerrand/alpine-pkg-glibc/releases/download/2.30-r0/glibc-2.30-r0.apk
078     *    $ apk add glibc-2.30-r0.apk
079     * </pre>
080     */
081
082    private static final Logger logger = Logger.getLogger(XGBoostTrainer.class.getName());
083
084    /**
085     * The tree building algorithm.
086     */
087    public enum TreeMethod {
088        /**
089         * XGBoost chooses between {@link TreeMethod#EXACT} and {@link TreeMethod#APPROX}
090         * depending on dataset size.
091         */
092        AUTO("auto"),
093        /**
094         * Exact greedy algorithm, enumerates all split candidates.
095         */
096        EXACT("exact"),
097        /**
098         * Approximate greedy algorithm, using a quantile sketch of the data and a gradient histogram.
099         */
100        APPROX("approx"),
101        /**
102         * Faster histogram optimized approximate algorithm.
103         */
104        HIST("hist"),
105        /**
106         * GPU implementation of the {@link TreeMethod#HIST} algorithm.
107         * <p>
108         * Note: GPU computation may not be supported on all platforms, and Tribuo is not tested with XGBoost GPU support.
109         */
110        GPU_HIST("gpu_hist");
111
112        /**
113         * The parameter name used by the XGBoost native library.
114         */
115        public final String paramName;
116
117        TreeMethod(String paramName) {
118            this.paramName = paramName;
119        }
120    }
121
122    /**
123     * The logging verbosity of the native library.
124     */
125    public enum LoggingVerbosity {
126        /**
127         * No logging.
128         */
129        SILENT(0),
130        /**
131         * Only warnings are logged.
132         */
133        WARNING(1),
134        /**
135         * Tree building info is logged as well as warnings.
136         */
137        INFO(2),
138        /**
139         * All the logging.
140         */
141        // You've never seen so much logging.
142        DEBUG(3);
143
144        /**
145         * The log value used by the XGBoost native library.
146         */
147        public final int value;
148
149        LoggingVerbosity(int value) {
150            this.value = value;
151        }
152    }
153
154    /**
155     * The type of XGBoost model.
156     */
157    public enum BoosterType {
158        /**
159         * A boosted linear model.
160         */
161        LINEAR("gblinear"),
162        /**
163         * A gradient boosted decision tree.
164         */
165        GBTREE("gbtree"),
166        /**
167         * A gradient boosted decision tree using dropout.
168         */
169        DART("dart");
170
171        /**
172         * The parameter value used by the XGBoost native library.
173         */
174        public final String paramName;
175
176        BoosterType(String paramName) {
177            this.paramName = paramName;
178        }
179    }
180
181    /**
182     * The XGBoost parameter map, only accessed internally.
183     */
184    protected final Map<String, Object> parameters = new HashMap<>();
185
186    /**
187     * Override for the parameter map, must contain all parameters, including the objective function.
188     */
189    @Config(description = "Override for parameters, if used must contain all the relevant parameters, including the objective")
190    protected Map<String, String> overrideParameters = new HashMap<>();
191
192    /**
193     * The number of trees to build.
194     */
195    @Config(mandatory = true,description="The number of trees to build.")
196    protected int numTrees;
197
198    /**
199     * The learning rate.
200     */
201    @Config(description = "The learning rate, shrinks the new tree output to prevent overfitting.")
202    private double eta = 0.3;
203
204    /**
205     * Minimum loss reduction to split a node.
206     */
207    @Config(description = "Minimum loss reduction needed to split a tree node.")
208    private double gamma = 0.0;
209
210    /**
211     * Max tree depth.
212     */
213    @Config(description="The maximum depth of any tree.")
214    private int maxDepth = 6;
215
216    /**
217     * Minimum weight in each child node before the split is valid.
218     */
219    @Config(description = "The minimum weight in each child node before a split is valid.")
220    private double minChildWeight = 1.0;
221
222    /**
223     * Subsample the examples (i.e., bagging).
224     */
225    @Config(description="Independently subsample the examples for each tree.")
226    private double subsample = 1.0;
227
228    /**
229     * Subsample the columns.
230     */
231    @Config(description="Independently subsample the features available for each node of each tree.")
232    private double featureSubsample = 1.0;
233
234    /**
235     * L2 regularisation term
236     */
237    @Config(description="l2 regularisation term on the weights.")
238    private double lambda = 1.0;
239
240    /**
241     * L1 regularisation term.
242     */
243    @Config(description="l1 regularisation term on the weights.")
244    private double alpha = 1.0;
245
246    /**
247     * Number of training threads.
248     */
249    @Config(description="The number of threads to use at training time.")
250    private int nThread = 4;
251
252    /**
253     * Deprecated by XGBoost in favour of the verbosity field.
254     */
255    @Deprecated
256    @Config(description="Quiesce all the logging output from the XGBoost C library. Deprecated in favour of 'verbosity'.")
257    private int silent = 1;
258
259    @Config(description="Logging verbosity, 0 is silent, 3 is debug.")
260    private LoggingVerbosity verbosity = LoggingVerbosity.SILENT;
261
262    @Config(description="Type of the weak learner.")
263    private BoosterType booster = BoosterType.GBTREE;
264
265    @Config(description="The tree building algorithm to use.")
266    private TreeMethod treeMethod = TreeMethod.AUTO;
267
268    @Config(description="The RNG seed.")
269    private long seed = Trainer.DEFAULT_SEED;
270
271    /**
272     * Number of times the {@code train} method has been called on this object.
273     */
274    protected int trainInvocationCounter = 0;
275
276    /**
277     * Constructs an XGBoost trainer using the specified number of trees.
278     * @param numTrees The number of trees.
279     */
280    protected XGBoostTrainer(int numTrees) {
281        this(numTrees, 0.3, 0, 6, 1, 1, 1, 1, 0, 4, true, Trainer.DEFAULT_SEED);
282    }
283
284    /**
285     * Constructs an XGBoost trainer using the specified number of trees.
286     * @param numTrees The number of trees.
287     * @param numThreads The number of training threads.
288     * @param silent Should the logging be silenced?
289     */
290    protected XGBoostTrainer(int numTrees, int numThreads, boolean silent) {
291        this(numTrees, 0.3, 0, 6, 1, 1, 1, 1, 0, numThreads, silent, Trainer.DEFAULT_SEED);
292    }
293
294    /**
295     * Create an XGBoost trainer.
296     * <p>
297     * Sets the boosting algorithm to {@link BoosterType#GBTREE} and the tree building algorithm to {@link TreeMethod#AUTO}.
298     *
299     * @param numTrees Number of trees to boost.
300     * @param eta Step size shrinkage parameter (default 0.3, range [0,1]).
301     * @param gamma Minimum loss reduction to make a split (default 0, range
302     * [0,inf]).
303     * @param maxDepth Maximum tree depth (default 6, range [1,inf]).
304     * @param minChildWeight Minimum sum of instance weights needed in a leaf
305     * (default 1, range [0, inf]).
306     * @param subsample Subsample size for each tree (default 1, range (0,1]).
307     * @param featureSubsample Subsample features for each tree (default 1,
308     * range (0,1]).
309     * @param lambda L2 regularization term on weights (default 1).
310     * @param alpha L1 regularization term on weights (default 0).
311     * @param nThread Number of threads to use (default 4).
312     * @param silent Silence the training output text.
313     * @param seed RNG seed.
314     */
315    protected XGBoostTrainer(int numTrees, double eta, double gamma, int maxDepth, double minChildWeight, double subsample, double featureSubsample, double lambda, double alpha, int nThread, boolean silent, long seed) {
316        this(BoosterType.GBTREE,TreeMethod.AUTO,numTrees,eta,gamma,maxDepth,minChildWeight,subsample,featureSubsample,lambda,alpha,nThread,silent ? LoggingVerbosity.SILENT : LoggingVerbosity.INFO,seed);
317    }
318
319    /**
320     * Create an XGBoost trainer.
321     *
322     * @param boosterType The base learning algorithm.
323     * @param treeMethod The tree building algorithm if using a tree booster.
324     * @param numTrees Number of trees to boost.
325     * @param eta Step size shrinkage parameter (default 0.3, range [0,1]).
326     * @param gamma Minimum loss reduction to make a split (default 0, range
327     * [0,inf]).
328     * @param maxDepth Maximum tree depth (default 6, range [1,inf]).
329     * @param minChildWeight Minimum sum of instance weights needed in a leaf
330     * (default 1, range [0, inf]).
331     * @param subsample Subsample size for each tree (default 1, range (0,1]).
332     * @param featureSubsample Subsample features for each tree (default 1,
333     * range (0,1]).
334     * @param lambda L2 regularization term on weights (default 1).
335     * @param alpha L1 regularization term on weights (default 0).
336     * @param nThread Number of threads to use (default 4).
337     * @param verbosity Set the logging verbosity of the native library.
338     * @param seed RNG seed.
339     */
340    protected XGBoostTrainer(BoosterType boosterType, TreeMethod treeMethod, int numTrees, double eta, double gamma, int maxDepth, double minChildWeight, double subsample, double featureSubsample, double lambda, double alpha, int nThread, LoggingVerbosity verbosity, long seed) {
341        if (numTrees < 1) {
342            throw new IllegalArgumentException("Must supply a positive number of trees. Received " + numTrees);
343        }
344        this.booster = boosterType;
345        this.treeMethod = treeMethod;
346        this.numTrees = numTrees;
347        this.eta = eta;
348        this.gamma = gamma;
349        this.maxDepth = maxDepth;
350        this.minChildWeight = minChildWeight;
351        this.subsample = subsample;
352        this.featureSubsample = featureSubsample;
353        this.lambda = lambda;
354        this.alpha = alpha;
355        this.nThread = nThread;
356        this.verbosity = verbosity;
357        this.silent = 0; // silent is deprecated
358        this.seed = seed;
359    }
360
361    /**
362     * This gives direct access to the XGBoost parameter map.
363     * <p>
364     * It lets you pick things that we haven't exposed like dropout trees, binary classification etc.
365     * <p>
366     * This sidesteps the validation that Tribuo provides for the hyperparameters, and so can produce unexpected results.
367     * @param numTrees Number of trees to boost.
368     * @param parameters A map from string to object, where object can be Number or String.
369     */
370    protected XGBoostTrainer(int numTrees, Map<String,Object> parameters) {
371        if (numTrees < 1) {
372            throw new IllegalArgumentException("Must supply a positive number of trees. Received " + numTrees);
373        }
374        this.numTrees = numTrees;
375        for (Map.Entry<String,Object> e : parameters.entrySet()) {
376            this.overrideParameters.put(e.getKey(),e.getValue().toString());
377        }
378    }
379
380    /**
381     * For olcut.
382     */
383    protected XGBoostTrainer() { }
384
385    /**
386     * Used by the OLCUT configuration system, and should not be called by external code.
387     */
388    @Override
389    public void postConfig() {
390        parameters.put("eta", eta);
391        parameters.put("gamma", gamma);
392        parameters.put("max_depth", maxDepth);
393        parameters.put("min_child_weight", minChildWeight);
394        parameters.put("subsample", subsample);
395        parameters.put("colsample_bytree", featureSubsample);
396        parameters.put("lambda", lambda);
397        parameters.put("alpha", alpha);
398        parameters.put("nthread", nThread);
399        parameters.put("seed", seed);
400        if (silent == 1) {
401            parameters.put("verbosity", 0);
402        } else {
403            parameters.put("verbosity", verbosity.value);
404        }
405        parameters.put("booster", booster.paramName);
406        parameters.put("tree_method", treeMethod.paramName);
407        if (!overrideParameters.isEmpty() && !overrideParameters.containsKey("objective")) {
408            throw new PropertyException("","overrideParameters","When using the override parameters must supply an objective");
409        }
410    }
411
412    @Override
413    public String toString() {
414        StringBuilder buffer = new StringBuilder();
415
416        buffer.append("XGBoostTrainer(numTrees=");
417        buffer.append(numTrees);
418        buffer.append(",parameters");
419        buffer.append(parameters.toString());
420        buffer.append(")");
421
422        return buffer.toString();
423    }
424
425    /**
426     * Creates an XGBoost model from the booster list.
427     * @param name The model name.
428     * @param provenance The model provenance.
429     * @param featureIDMap The feature domain.
430     * @param outputIDInfo The output domain.
431     * @param models The boosters.
432     * @param converter The converter from XGBoost's output to Tribuo predictions.
433     * @return An XGBoost model.
434     */
435    protected XGBoostModel<T> createModel(String name, ModelProvenance provenance, ImmutableFeatureMap featureIDMap, ImmutableOutputInfo<T> outputIDInfo, List<Booster> models, XGBoostOutputConverter<T> converter) {
436        return new XGBoostModel<>(name,provenance,featureIDMap,outputIDInfo,models,converter);
437    }
438
439    /**
440     * Returns a copy of the supplied parameter map which
441     * has the appropriate type for passing to XGBoost.train.
442     * @param input The parameter map.
443     * @return A (shallow) copy of the supplied map.
444     */
445    protected Map<String,Object> copyParams(Map<String, ?> input) {
446        return new HashMap<>(input);
447    }
448
449    @Override
450    public int getInvocationCount() {
451        return trainInvocationCounter;
452    }
453
454    @Override
455    public synchronized void setInvocationCount(int invocationCount) {
456        if(invocationCount < 0){
457            throw new IllegalArgumentException("The supplied invocationCount is less than zero.");
458        }
459
460        this.trainInvocationCounter = invocationCount;
461    }
462
463    /**
464     * Converts a dataset into a DMatrix.
465     * @param examples The examples to convert.
466     * @param responseExtractor The extraction function for the output.
467     * @param <T> The type of the output.
468     * @return A DMatrixTuple.
469     * @throws XGBoostError If the native library failed to construct the DMatrix.
470     */
471    protected static <T extends Output<T>> DMatrixTuple<T> convertDataset(Dataset<T> examples, Function<T,Float> responseExtractor) throws XGBoostError {
472        return convertExamples(examples.getData(), examples.getFeatureIDMap(), responseExtractor);
473    }
474
475    /**
476     * Converts a dataset into a DMatrix.
477     * @param examples The examples to convert.
478     * @param <T> The type of the output.
479     * @return A DMatrixTuple.
480     * @throws XGBoostError If the native library failed to construct the DMatrix.
481     */
482    protected static <T extends Output<T>> DMatrixTuple<T> convertDataset(Dataset<T> examples) throws XGBoostError {
483        return convertExamples(examples.getData(), examples.getFeatureIDMap(), null);
484    }
485
486    /**
487     * Converts an iterable of examples into a DMatrix.
488     * @param examples The examples to convert.
489     * @param featureMap The feature id map which supplies the indices.
490     * @param <T> The type of the output.
491     * @return A DMatrixTuple.
492     * @throws XGBoostError If the native library failed to construct the DMatrix.
493     */
494    protected static <T extends Output<T>> DMatrixTuple<T> convertExamples(Iterable<Example<T>> examples, ImmutableFeatureMap featureMap) throws XGBoostError {
495        return convertExamples(examples, featureMap, null);
496    }
497
498    /**
499     * Converts an iterable of examples into a DMatrix.
500     * @param examples The examples to convert.
501     * @param featureMap The feature id map which supplies the indices.
502     * @param responseExtractor The extraction function for the output.
503     * @param <T> The type of the output.
504     * @return A DMatrixTuple.
505     * @throws XGBoostError If the native library failed to construct the DMatrix.
506     */
507    protected static <T extends Output<T>> DMatrixTuple<T> convertExamples(Iterable<Example<T>> examples, ImmutableFeatureMap featureMap, Function<T,Float> responseExtractor) throws XGBoostError {
508        // headers = array of start points for a row
509        // indices = array of feature indices for all data
510        // data = array of feature values for all data
511        // SparseType = DMatrix.SparseType.CSR
512        //public DMatrix(long[] headers, int[] indices, float[] data, SparseType st) throws XGBoostError
513        //
514        // then call
515        //public void setLabel(float[] labels) throws XGBoostError
516
517        boolean labelled = responseExtractor != null;
518        ArrayList<Float> labelsList = new ArrayList<>();
519        ArrayList<Float> dataList = new ArrayList<>();
520        ArrayList<Long> headersList = new ArrayList<>();
521        ArrayList<Integer> indicesList = new ArrayList<>();
522        ArrayList<Float> weightsList = new ArrayList<>();
523        ArrayList<Integer> numValidFeatures = new ArrayList<>();
524        ArrayList<Example<T>> examplesList = new ArrayList<>();
525
526        long rowHeader = 0;
527        headersList.add(rowHeader);
528        for (Example<T> e : examples) {
529            if (labelled) {
530                labelsList.add(responseExtractor.apply(e.getOutput()));
531                weightsList.add(e.getWeight());
532            }
533            examplesList.add(e);
534            long newRowHeader = convertSingleExample(e,featureMap,dataList,indicesList,headersList,rowHeader);
535            numValidFeatures.add((int) (newRowHeader-rowHeader));
536            rowHeader = newRowHeader;
537        }
538
539        float[] data = Util.toPrimitiveFloat(dataList);
540        int[] indices = Util.toPrimitiveInt(indicesList);
541        long[] headers = Util.toPrimitiveLong(headersList);
542
543        DMatrix dataMatrix = new DMatrix(headers, indices, data, DMatrix.SparseType.CSR,featureMap.size());
544        if (labelled) {
545            float[] labels = Util.toPrimitiveFloat(labelsList);
546            dataMatrix.setLabel(labels);
547            float[] weights = Util.toPrimitiveFloat(weightsList);
548            dataMatrix.setWeight(weights);
549        }
550        @SuppressWarnings("unchecked") // Generic array creation
551        Example<T>[] exampleArray = (Example<T>[])examplesList.toArray(new Example[0]);
552        return new DMatrixTuple<>(dataMatrix,Util.toPrimitiveInt(numValidFeatures),exampleArray);
553    }
554
555    /**
556     * Converts an example into a DMatrix.
557     * @param example The example to convert.
558     * @param featureMap The feature id map which supplies the indices.
559     * @param <T> The type of the output.
560     * @return A DMatrixTuple.
561     * @throws XGBoostError If the native library failed to construct the DMatrix.
562     */
563    protected static <T extends Output<T>> DMatrixTuple<T> convertExample(Example<T> example, ImmutableFeatureMap featureMap) throws XGBoostError {
564        return convertExample(example,featureMap,null);
565    }
566
567    /**
568     * Converts an example into a DMatrix.
569     * @param example The example to convert.
570     * @param featureMap The feature id map which supplies the indices.
571     * @param responseExtractor The extraction function for the output.
572     * @param <T> The type of the output.
573     * @return A DMatrixTuple.
574     * @throws XGBoostError If the native library failed to construct the DMatrix.
575     */
576    protected static <T extends Output<T>> DMatrixTuple<T> convertExample(Example<T> example, ImmutableFeatureMap featureMap, Function<T,Float> responseExtractor) throws XGBoostError {
577        // headers = array of start points for a row
578        // indices = array of feature indices for all data
579        // data = array of feature values for all data
580        // SparseType = DMatrix.SparseType.CSR
581        //public DMatrix(long[] headers, int[] indices, float[] data, SparseType st) throws XGBoostError
582        //
583        // then call
584        //public void setLabel(float[] labels) throws XGBoostError
585
586        boolean labelled = responseExtractor != null;
587        ArrayList<Float> dataList = new ArrayList<>();
588        ArrayList<Integer> indicesList = new ArrayList<>();
589        ArrayList<Long> headersList = new ArrayList<>();
590        headersList.add(0L);
591
592        long header = convertSingleExample(example,featureMap,dataList,indicesList,headersList,0);
593
594        float[] data = Util.toPrimitiveFloat(dataList);
595        int[] indices = Util.toPrimitiveInt(indicesList);
596        long[] headers = Util.toPrimitiveLong(headersList);
597
598        DMatrix dataMatrix = new DMatrix(headers, indices, data, DMatrix.SparseType.CSR,featureMap.size());
599        if (labelled) {
600            float[] labels = new float[1];
601            labels[0] = responseExtractor.apply(example.getOutput());
602            dataMatrix.setLabel(labels);
603            float[] weights = new float[1];
604            weights[0] = example.getWeight();
605            dataMatrix.setWeight(weights);
606        }
607        @SuppressWarnings("unchecked") // Generic array creation
608        Example<T>[] exampleArray = (Example<T>[])new Example[]{example};
609        return new DMatrixTuple<>(dataMatrix,new int[]{(int)header},exampleArray);
610    }
611
612    /**
613     * Writes out the features from an example into the three supplied {@link ArrayList}s.
614     * <p>
615     * This is used to transform examples into the right format for an XGBoost call.
616     * It's used in both the Classification and Regression XGBoost backends.
617     * The ArrayLists must be non-null, and can contain existing values (as this
618     * method is called multiple times to build up an arraylist containing all the
619     * feature values for a dataset).
620     * <p>
621     * Features with colliding feature ids are summed together.
622     * <p>
623     * Can throw IllegalArgumentException if the {@link Example} contains no features.
624     * @param example The example to inspect.
625     * @param featureMap The feature map of the model/dataset (used to preserve hash information).
626     * @param dataList The output feature values.
627     * @param indicesList The output indices.
628     * @param headersList The output header position (an integer saying how long each sparse example is).
629     * @param header The current header position.
630     * @param <T> The type of the example.
631     * @return The updated header position.
632     */
633    protected static <T extends Output<T>> long convertSingleExample(Example<T> example, ImmutableFeatureMap featureMap, ArrayList<Float> dataList, ArrayList<Integer> indicesList, ArrayList<Long> headersList, long header) {
634        int numActiveFeatures = 0;
635        int prevIdx = -1;
636        int indicesSize = indicesList.size();
637        for (Feature f : example) {
638            int id = featureMap.getID(f.getName());
639            if (id > prevIdx){
640                prevIdx = id;
641                dataList.add((float) f.getValue());
642                indicesList.add(id);
643                numActiveFeatures++;
644            } else if (id > -1) {
645                //
646                // Collision, deal with it.
647                int collisionIdx = Util.binarySearch(indicesList,id,indicesSize,numActiveFeatures+indicesSize);
648                if (collisionIdx < 0) {
649                    //
650                    // Collision but not present in tmpIndices
651                    // move data and bump i
652                    collisionIdx = - (collisionIdx + 1);
653                    indicesList.add(collisionIdx,id);
654                    dataList.add(collisionIdx,(float) f.getValue());
655                    numActiveFeatures++;
656                } else {
657                    //
658                    // Collision present in tmpIndices
659                    // add the values.
660                    dataList.set(collisionIdx, dataList.get(collisionIdx) + (float) f.getValue());
661                }
662            }
663        }
664        if (numActiveFeatures == 0) {
665            throw new IllegalArgumentException("No features found in Example " + example.toString());
666        }
667        header += numActiveFeatures;
668        headersList.add(header);
669        return header;
670    }
671
672    /**
673     * Writes out the features from a SparseVector into the three supplied {@link ArrayList}s.
674     * <p>
675     * This is used to transform examples into the right format for an XGBoost call.
676     * It's used when predicting with an externally trained XGBoost model, as the
677     * external training may not respect Tribuo's feature ordering constraints.
678     * The ArrayLists must be non-null, and can contain existing values (as this
679     * method is called multiple times to build up an arraylist containing all the
680     * feature values for a dataset).
681     * </p>
682     * <p>
683     * This is much simpler than {@link XGBoostTrainer#convertSingleExample} as the validation
684     * of feature indices is done in the {@link org.tribuo.interop.ExternalModel} class.
685     * </p>
686     * @param vector The features to convert.
687     * @param dataList The output feature values.
688     * @param indicesList The output indices.
689     * @param headersList The output header position (an integer saying how long each sparse example is).
690     * @param header The current header position.
691     * @return The updated header position.
692     */
693    static long convertSingleExample(SparseVector vector, ArrayList<Float> dataList, ArrayList<Integer> indicesList, ArrayList<Long> headersList, long header) {
694        int numActiveFeatures = 0;
695        for (VectorTuple v : vector) {
696            dataList.add((float) v.value);
697            indicesList.add(v.index);
698            numActiveFeatures++;
699        }
700        header += numActiveFeatures;
701        headersList.add(header);
702        return header;
703    }
704
705    /**
706     * Used when predicting with an externally trained XGBoost model.
707     * @param vector The features to convert.
708     * @return A DMatrix representing the features.
709     * @throws XGBoostError If the native library returns an error state.
710     */
711    protected static DMatrix convertSparseVector(SparseVector vector) throws XGBoostError {
712        // headers = array of start points for a row
713        // indices = array of feature indices for all data
714        // data = array of feature values for all data
715        // SparseType = DMatrix.SparseType.CSR
716        //public DMatrix(long[] headers, int[] indices, float[] data, SparseType st) throws XGBoostError
717        ArrayList<Float> dataList = new ArrayList<>();
718        ArrayList<Long> headersList = new ArrayList<>();
719        ArrayList<Integer> indicesList = new ArrayList<>();
720
721        long rowHeader = 0;
722        headersList.add(rowHeader);
723        convertSingleExample(vector,dataList,indicesList,headersList,rowHeader);
724
725        float[] data = Util.toPrimitiveFloat(dataList);
726        int[] indices = Util.toPrimitiveInt(indicesList);
727        long[] headers = Util.toPrimitiveLong(headersList);
728
729        return new DMatrix(headers, indices, data, DMatrix.SparseType.CSR,vector.size());
730    }
731
732    /**
733     * Used when predicting with an externally trained XGBoost model.
734     * <p>
735     * It is assumed all vectors are the same size when passed into this function.
736     * @param vectors The batch of features to convert.
737     * @return A DMatrix representing the batch of features.
738     * @throws XGBoostError If the native library returns an error state.
739     */
740    protected static DMatrix convertSparseVectors(List<SparseVector> vectors) throws XGBoostError {
741        // headers = array of start points for a row
742        // indices = array of feature indices for all data
743        // data = array of feature values for all data
744        // SparseType = DMatrix.SparseType.CSR
745        //public DMatrix(long[] headers, int[] indices, float[] data, SparseType st) throws XGBoostError
746        ArrayList<Float> dataList = new ArrayList<>();
747        ArrayList<Long> headersList = new ArrayList<>();
748        ArrayList<Integer> indicesList = new ArrayList<>();
749
750        int numFeatures = 0;
751        long rowHeader = 0;
752        headersList.add(rowHeader);
753        for (SparseVector e : vectors) {
754            rowHeader = convertSingleExample(e,dataList,indicesList,headersList,rowHeader);
755            numFeatures = e.size(); // All vectors are assumed to be the same size.
756        }
757
758        float[] data = Util.toPrimitiveFloat(dataList);
759        int[] indices = Util.toPrimitiveInt(indicesList);
760        long[] headers = Util.toPrimitiveLong(headersList);
761
762        return new DMatrix(headers, indices, data, DMatrix.SparseType.CSR, numFeatures);
763    }
764
765    /**
766     * Tuple of a DMatrix, the number of valid features in each example, and the examples themselves.
767     * <p>
768     * One day it'll be a record.
769     * @param <T> The output type.
770     */
771    protected static class DMatrixTuple<T extends Output<T>> {
772        /**
773         * The data matrix.
774         */
775        public final DMatrix data;
776        /**
777         * The number of valid features in each example.
778         */
779        public final int[] numValidFeatures;
780        /**
781         * The examples.
782         */
783        public final Example<T>[] examples;
784
785        /**
786         * Constructs a tuple containing the data and some Tribuo metadata.
787         * @param data The data matrix.
788         * @param numValidFeatures The number of valid features in each example.
789         * @param examples The examples.
790         */
791        protected DMatrixTuple(DMatrix data, int[] numValidFeatures, Example<T>[] examples) {
792            this.data = data;
793            this.numValidFeatures = numValidFeatures;
794            this.examples = examples;
795        }
796    }
797
798    /**
799     * Provenance for {@link XGBoostTrainer}. No longer used.
800     * @deprecated Unused.
801     */
802    @Deprecated
803    protected static class XGBoostTrainerProvenance extends SkeletalTrainerProvenance {
804        private static final long serialVersionUID = 1L;
805
806        /**
807         * Constructs an XGBoostTrainerProvenance
808         * @param host The host object.
809         * @param <T> The output type.
810         */
811        protected <T extends Output<T>> XGBoostTrainerProvenance(XGBoostTrainer<T> host) {
812            super(host);
813        }
814
815        /**
816         * Deserializes an XGBoostTrainerProvenance.
817         * @param map The map to deserialize from.
818         */
819        protected XGBoostTrainerProvenance(Map<String,Provenance> map) {
820            super(map);
821        }
822    }
823}