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.google.protobuf.Any;
020import com.google.protobuf.ByteString;
021import com.google.protobuf.InvalidProtocolBufferException;
022import com.oracle.labs.mlrg.olcut.provenance.Provenance;
023import com.oracle.labs.mlrg.olcut.util.Pair;
024import java.util.Arrays;
025import java.util.stream.Collectors;
026import ml.dmlc.xgboost4j.java.Booster;
027import ml.dmlc.xgboost4j.java.DMatrix;
028import ml.dmlc.xgboost4j.java.XGBoost;
029import ml.dmlc.xgboost4j.java.XGBoostError;
030import org.tribuo.Example;
031import org.tribuo.ImmutableFeatureMap;
032import org.tribuo.ImmutableOutputInfo;
033import org.tribuo.Model;
034import org.tribuo.Output;
035import org.tribuo.OutputFactory;
036import org.tribuo.Prediction;
037import org.tribuo.common.xgboost.protos.XGBoostExternalModelProto;
038import org.tribuo.impl.ModelDataCarrier;
039import org.tribuo.interop.ExternalDatasetProvenance;
040import org.tribuo.interop.ExternalModel;
041import org.tribuo.interop.ExternalTrainerProvenance;
042import org.tribuo.math.la.SparseVector;
043import org.tribuo.protos.ProtoUtil;
044import org.tribuo.protos.core.ModelProto;
045import org.tribuo.provenance.DatasetProvenance;
046import org.tribuo.provenance.ModelProvenance;
047import org.tribuo.util.Util;
048
049import java.io.ByteArrayInputStream;
050import java.io.File;
051import java.io.IOException;
052import java.io.ObjectInputStream;
053import java.io.ObjectOutputStream;
054import java.net.MalformedURLException;
055import java.net.URL;
056import java.nio.file.Files;
057import java.nio.file.Path;
058import java.time.OffsetDateTime;
059import java.util.ArrayList;
060import java.util.Collections;
061import java.util.Comparator;
062import java.util.HashMap;
063import java.util.List;
064import java.util.Map;
065import java.util.PriorityQueue;
066import java.util.logging.Level;
067import java.util.logging.Logger;
068
069/**
070 * A {@link Model} which wraps around a XGBoost.Booster which was trained by a system other than Tribuo.
071 * <p>
072 * XGBoost is a fast implementation of gradient boosted decision trees.
073 * <p>
074 * Throws IllegalStateException if the XGBoost C++ library fails to load or throws an exception.
075 * <p>
076 * See:
077 * <pre>
078 * Chen T, Guestrin C.
079 * "XGBoost: A Scalable Tree Boosting System"
080 * Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
081 * </pre>
082 * <p>
083 * and for the original algorithm:
084 * <pre>
085 * Friedman JH.
086 * "Greedy Function Approximation: a Gradient Boosting Machine"
087 * Annals of statistics, 2001.
088 * </pre>
089 * <p>
090 * N.B.: XGBoost4J wraps the native C implementation of xgboost that links to various C libraries, including libgomp
091 * and glibc (on Linux). If you're running on Alpine, which does not natively use glibc, you'll need to install glibc
092 * into the container.
093 * On the macOS binary on Maven Central is compiled without
094 * OpenMP support, meaning that XGBoost is single threaded on macOS. You can recompile the macOS binary with
095 * OpenMP support after installing libomp from homebrew if necessary.
096 */
097public final class XGBoostExternalModel<T extends Output<T>> extends ExternalModel<T,DMatrix,float[][]> {
098    private static final long serialVersionUID = 1L;
099
100    private static final Logger logger = Logger.getLogger(XGBoostExternalModel.class.getName());
101
102    /**
103     * Protobuf serialization version.
104     */
105    public static final int CURRENT_VERSION = 0;
106
107    private final XGBoostOutputConverter<T> converter;
108
109    /**
110     * Transient as we rely upon the native serialisation mechanism to bytes rather than Java serializing the Booster.
111     */
112    protected transient Booster model;
113
114    private XGBoostExternalModel(String name, ModelProvenance provenance,
115                                 ImmutableFeatureMap featureIDMap, ImmutableOutputInfo<T> outputIDInfo,
116                                 Map<String, Integer> featureMapping, Booster model,
117                                 XGBoostOutputConverter<T> converter) {
118        super(name, provenance, featureIDMap, outputIDInfo, converter.generatesProbabilities(), featureMapping);
119        this.model = model;
120        this.converter = converter;
121    }
122
123    private XGBoostExternalModel(String name, ModelProvenance provenance,
124                                 ImmutableFeatureMap featureIDMap, ImmutableOutputInfo<T> outputIDInfo,
125                                 int[] featureForwardMapping, int[] featureBackwardMapping,
126                                 Booster model, XGBoostOutputConverter<T> converter) {
127        super(name,provenance,featureIDMap,outputIDInfo,featureForwardMapping,featureBackwardMapping,
128              converter.generatesProbabilities());
129        this.model = model;
130        this.converter = converter;
131    }
132
133    /**
134     * Deserialization factory.
135     * @param version The serialized object version.
136     * @param className The class name.
137     * @param message The serialized data.
138     * @throws InvalidProtocolBufferException If the protobuf could not be parsed from the {@code message}.
139     * @throws XGBoostError If the XGBoost byte array failed to parse.
140     * @throws IOException If the XGBoost byte array failed to parse.
141     * @return The deserialized object.
142     */
143    @SuppressWarnings({"unchecked","rawtypes"}) // output converter and domain are checked via getClass.
144    public static XGBoostExternalModel<?> deserializeFromProto(int version, String className, Any message) throws InvalidProtocolBufferException, XGBoostError, IOException {
145        if (version < 0 || version > CURRENT_VERSION) {
146            throw new IllegalArgumentException("Unknown version " + version + ", this class supports at most version " + CURRENT_VERSION);
147        }
148        XGBoostExternalModelProto proto = message.unpack(XGBoostExternalModelProto.class);
149
150        XGBoostOutputConverter<?> converter = ProtoUtil.deserialize(proto.getConverter());
151        Class<?> converterWitness = converter.getTypeWitness();
152        ModelDataCarrier<?> carrier = ModelDataCarrier.deserialize(proto.getMetadata());
153        if (!carrier.outputDomain().getOutput(0).getClass().equals(converterWitness)) {
154            throw new IllegalStateException("Invalid protobuf, output domain does not match the converter, found " + carrier.outputDomain().getClass() + " and " + converterWitness);
155        }
156        int[] featureForwardMapping = Util.toPrimitiveInt(proto.getForwardFeatureMappingList());
157        int[] featureBackwardMapping = Util.toPrimitiveInt(proto.getBackwardFeatureMappingList());
158        if (!validateFeatureMapping(featureForwardMapping,featureBackwardMapping,carrier.featureDomain())) {
159            throw new IllegalStateException("Invalid protobuf, external<->Tribuo feature mapping does not form a bijection");
160        }
161
162        Booster model = XGBoost.loadModel(proto.getModel().toByteArray());
163
164        return new XGBoostExternalModel(carrier.name(), carrier.provenance(), carrier.featureDomain(),
165                carrier.outputDomain(), featureForwardMapping, featureBackwardMapping, model, converter);
166    }
167
168    @Override
169    protected DMatrix convertFeatures(SparseVector input) {
170        try {
171            return XGBoostTrainer.convertSparseVector(input);
172        } catch (XGBoostError e) {
173            logger.severe("XGBoost threw an error while constructing the DMatrix.");
174            throw new IllegalStateException(e);
175        }
176    }
177
178    @Override
179    protected DMatrix convertFeaturesList(List<SparseVector> input) {
180        try {
181            return XGBoostTrainer.convertSparseVectors(input);
182        } catch (XGBoostError e) {
183            logger.severe("XGBoost threw an error while constructing the DMatrix.");
184            throw new IllegalStateException(e);
185        }
186    }
187
188    @Override
189    protected float[][] externalPrediction(DMatrix input) {
190        try {
191            return model.predict(input);
192        } catch (XGBoostError e) {
193            logger.severe("XGBoost threw an error while predicting.");
194            throw new IllegalStateException(e);
195        }
196    }
197
198    @Override
199    protected Prediction<T> convertOutput(float[][] output, int numValidFeatures, Example<T> example) {
200        return converter.convertOutput(outputIDInfo,Collections.singletonList(output[0]),numValidFeatures,example);
201    }
202
203    @SuppressWarnings("unchecked") // generic array creation
204    @Override
205    protected List<Prediction<T>> convertOutput(float[][] output, int[] numValidFeatures, List<Example<T>> examples) {
206        return converter.convertBatchOutput(outputIDInfo,Collections.singletonList(output),numValidFeatures,(Example<T>[])examples.toArray(new Example[0]));
207    }
208
209    /**
210     * Creates objects to report feature importance metrics for XGBoost. See the documentation of {@link XGBoostFeatureImportance}
211     * for more information on what those metrics mean. Typically this list will contain a single instance for the entire
212     * model. For multidimensional regression the list will have one entry per dimension, in dimension order.
213     * @return The feature importance object(s).
214     */
215    public List<XGBoostFeatureImportance> getFeatureImportance() {
216        return Collections.singletonList(new XGBoostFeatureImportance(model, this));
217    }
218
219    @Override
220    public Map<String, List<Pair<String, Double>>> getTopFeatures(int n) {
221        try {
222            int maxFeatures = n < 0 ? featureIDMap.size() : n;
223            Map<String, Integer> xgboostMap = model.getFeatureScore("");
224            Comparator<Pair<String, Double>> comparator = Comparator.comparingDouble(p -> Math.abs(p.getB()));
225            PriorityQueue<Pair<String,Double>> q = new PriorityQueue<>(maxFeatures,comparator);
226            //iterate over the scored features
227            for (Map.Entry<String, Integer> f : xgboostMap.entrySet()) {
228                int id = Integer.parseInt(f.getKey().substring(1));
229                Pair<String,Double> cur = new Pair<>(featureIDMap.get(featureBackwardMapping[id]).getName(), (double) f.getValue());
230
231                if (q.size() < maxFeatures) {
232                    q.offer(cur);
233                } else if (comparator.compare(cur,q.peek()) > 0) {
234                    q.poll();
235                    q.offer(cur);
236                }
237            }
238            List<Pair<String,Double>> list = new ArrayList<>();
239            while(q.size() > 0) {
240                list.add(q.poll());
241            }
242            Collections.reverse(list);
243
244            Map<String, List<Pair<String,Double>>> map = new HashMap<>();
245            map.put(Model.ALL_OUTPUTS,list);
246
247            return map;
248        } catch (XGBoostError e) {
249            logger.log(Level.SEVERE, "XGBoost threw an error", e);
250            return Collections.emptyMap();
251        }
252    }
253
254    @Override
255    public ModelProto serialize() {
256        ModelDataCarrier<T> carrier = createDataCarrier();
257
258        XGBoostExternalModelProto.Builder modelBuilder = XGBoostExternalModelProto.newBuilder();
259        modelBuilder.setMetadata(carrier.serialize());
260        modelBuilder.setConverter(converter.serialize());
261        modelBuilder.addAllForwardFeatureMapping(Arrays.stream(featureForwardMapping).boxed().collect(
262            Collectors.toList()));
263        modelBuilder.addAllBackwardFeatureMapping(Arrays.stream(featureBackwardMapping).boxed().collect(Collectors.toList()));
264        try {
265            modelBuilder.setModel(ByteString.copyFrom(model.toByteArray()));
266        } catch (XGBoostError e) {
267            throw new IllegalStateException("Failed to serialize XGBoost model");
268        }
269
270        ModelProto.Builder builder = ModelProto.newBuilder();
271        builder.setSerializedData(Any.pack(modelBuilder.build()));
272        builder.setClassName(XGBoostExternalModel.class.getName());
273        builder.setVersion(CURRENT_VERSION);
274
275        return builder.build();
276    }
277
278    @Override
279    protected XGBoostExternalModel<T> copy(String newName, ModelProvenance newProvenance) {
280        return new XGBoostExternalModel<>(newName, newProvenance, featureIDMap, outputIDInfo,
281                                          featureForwardMapping, featureBackwardMapping,
282                                          XGBoostModel.copyModel(model), converter);
283    }
284
285    /**
286     * Creates an {@code XGBoostExternalModel} from the supplied model on disk.
287     * @param factory The output factory to use.
288     * @param featureMapping The feature mapping between Tribuo names and XGBoost integer ids.
289     * @param outputMapping The output mapping between Tribuo outputs and XGBoost integer ids.
290     * @param outputFunc The XGBoostOutputConverter function for the output type.
291     * @param path The path to the model on disk.
292     * @param <T> The type of the output.
293     * @return An XGBoostExternalModel ready to score new inputs.
294     */
295    public static <T extends Output<T>> XGBoostExternalModel<T> createXGBoostModel(OutputFactory<T> factory, Map<String, Integer> featureMapping, Map<T,Integer> outputMapping, XGBoostOutputConverter<T> outputFunc, String path) {
296        try {
297            Booster model = XGBoost.loadModel(path);
298            ExternalTrainerProvenance trainerProvenance = new ExternalTrainerProvenance(new File(path).toURI().toURL());
299            return createXGBoostModel(factory,featureMapping,outputMapping,outputFunc,model,trainerProvenance,Collections.emptyMap());
300        } catch (XGBoostError | MalformedURLException e) {
301            throw new IllegalArgumentException("Unable to load model from path " + path, e);
302        }
303    }
304
305    /**
306     * Creates an {@code XGBoostExternalModel} from the supplied model on disk.
307     * @param factory The output factory to use.
308     * @param featureMapping The feature mapping between Tribuo names and XGBoost integer ids.
309     * @param outputMapping The output mapping between Tribuo outputs and XGBoost integer ids.
310     * @param outputFunc The XGBoostOutputConverter function for the output type.
311     * @param path The path to the model on disk.
312     * @param <T> The type of the output.
313     * @return An XGBoostExternalModel ready to score new inputs.
314     */
315    public static <T extends Output<T>> XGBoostExternalModel<T> createXGBoostModel(OutputFactory<T> factory, Map<String, Integer> featureMapping, Map<T,Integer> outputMapping, XGBoostOutputConverter<T> outputFunc, Path path) {
316        try {
317            Booster model = XGBoost.loadModel(Files.newInputStream(path));
318            ExternalTrainerProvenance trainerProvenance = new ExternalTrainerProvenance(path.toUri().toURL());
319            return createXGBoostModel(factory,featureMapping,outputMapping,outputFunc,model,trainerProvenance,Collections.emptyMap());
320        } catch (XGBoostError | IOException e) {
321            throw new IllegalArgumentException("Unable to load model from path " + path, e);
322        }
323    }
324
325    /**
326     * Creates an {@code XGBoostExternalModel} from the supplied model.
327     * <p>
328     * Note: the provenance system requires that the URL point to a valid local file and
329     * will throw an exception if it is not. However it doesn't check that the file is
330     * where the Booster was created from.
331     * @param factory The output factory to use.
332     * @param featureMapping The feature mapping between Tribuo names and XGBoost integer ids.
333     * @param outputMapping The output mapping between Tribuo outputs and XGBoost integer ids.
334     * @param outputFunc The XGBoostOutputConverter function for the output type.
335     * @param model The XGBoost model to wrap.
336     * @param provenanceLocation The location where the model was loaded from.
337     * @param <T> The type of the output.
338     * @return An XGBoostExternalModel ready to score new inputs.
339     * @deprecated As the URL argument must always be valid. To wrap an in-memory booster use {@link #createXGBoostModel(OutputFactory, Map, Map, XGBoostOutputConverter, Booster, Map)}.
340     */
341    @Deprecated
342    public static <T extends Output<T>> XGBoostExternalModel<T> createXGBoostModel(OutputFactory<T> factory, Map<String,Integer> featureMapping, Map<T,Integer> outputMapping, XGBoostOutputConverter<T> outputFunc, Booster model, URL provenanceLocation) {
343        ExternalTrainerProvenance trainerProvenance = new ExternalTrainerProvenance(provenanceLocation);
344        return createXGBoostModel(factory,featureMapping,outputMapping,outputFunc,model,trainerProvenance,Collections.emptyMap());
345    }
346
347    /**
348     * Creates an {@code XGBoostExternalModel} from the supplied in-memory XGBoost {@code Booster}.
349     * @param factory The output factory to use.
350     * @param featureMapping The feature mapping between Tribuo names and XGBoost integer ids.
351     * @param outputMapping The output mapping between Tribuo outputs and XGBoost integer ids.
352     * @param outputFunc The XGBoostOutputConverter function for the output type.
353     * @param model The XGBoost model to wrap.
354     * @param instanceProvenance Provenance for this model.
355     * @param <T> The type of the output.
356     * @return An XGBoostExternalModel ready to score new inputs.
357     */
358    public static <T extends Output<T>> XGBoostExternalModel<T> createXGBoostModel(OutputFactory<T> factory, Map<String,Integer> featureMapping, Map<T,Integer> outputMapping, XGBoostOutputConverter<T> outputFunc, Booster model, Map<String, Provenance> instanceProvenance) {
359        try {
360            ExternalTrainerProvenance trainerProvenance = new ExternalTrainerProvenance(model.toByteArray());
361            return createXGBoostModel(factory,featureMapping,outputMapping,outputFunc,model,trainerProvenance,instanceProvenance);
362        } catch (XGBoostError e) {
363            throw new IllegalStateException("Unable to extract byte array from booster",e);
364        }
365    }
366
367    /**
368     * Creates an {@code XGBoostExternalModel} from the supplied model.
369     * @param factory The output factory to use.
370     * @param featureMapping The feature mapping between Tribuo names and XGBoost integer ids.
371     * @param outputMapping The output mapping between Tribuo outputs and XGBoost integer ids.
372     * @param outputFunc The XGBoostOutputConverter function for the output type.
373     * @param model The XGBoost model to wrap.
374     * @param trainerProvenance The constructed trainer provenance.
375     * @param instanceProvenance Provenance for this model.
376     * @param <T> The type of the output.
377     * @return An XGBoostExternalModel ready to score new inputs.
378     */
379    private static <T extends Output<T>> XGBoostExternalModel<T> createXGBoostModel(OutputFactory<T> factory, Map<String,Integer> featureMapping, Map<T,Integer> outputMapping, XGBoostOutputConverter<T> outputFunc, Booster model, ExternalTrainerProvenance trainerProvenance, Map<String, Provenance> instanceProvenance) {
380        ImmutableFeatureMap featureMap = ExternalModel.createFeatureMap(featureMapping.keySet());
381        ImmutableOutputInfo<T> outputInfo = ExternalModel.createOutputInfo(factory,outputMapping);
382        OffsetDateTime now = OffsetDateTime.now();
383        DatasetProvenance datasetProvenance = new ExternalDatasetProvenance("unknown-external-data",factory,false,featureMapping.size(),outputMapping.size());
384        ModelProvenance provenance = new ModelProvenance(XGBoostExternalModel.class.getName(),now,datasetProvenance,trainerProvenance,instanceProvenance);
385        return new XGBoostExternalModel<>("external-model",provenance,featureMap,outputInfo,
386                featureMapping,model,outputFunc);
387    }
388
389    private void writeObject(ObjectOutputStream out) throws IOException {
390        out.defaultWriteObject();
391        try {
392            byte[] serialisedBooster = model.toByteArray();
393            out.writeObject(serialisedBooster);
394        } catch (XGBoostError e) {
395            throw new IOException("Failed to serialize the XGBoost model",e);
396        }
397    }
398
399    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
400        in.defaultReadObject();
401        try {
402            // Now read in the byte array and rebuild the Booster
403            byte[] serialisedBooster = (byte[]) in.readObject();
404            model = XGBoost.loadModel(new ByteArrayInputStream(serialisedBooster));
405        } catch (XGBoostError e) {
406            throw new IOException("Failed to deserialize the XGBoost model",e);
407        }
408    }
409}