001/*
002 * Copyright (c) 2015-2020, 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.util.Pair;
020import libsvm.svm_parameter;
021import org.tribuo.Example;
022import org.tribuo.Excuse;
023import org.tribuo.ImmutableFeatureMap;
024import org.tribuo.ImmutableOutputInfo;
025import org.tribuo.Model;
026import org.tribuo.Output;
027import org.tribuo.common.libsvm.protos.SVMModelProto;
028import org.tribuo.common.libsvm.protos.SVMNodeArrayProto;
029import org.tribuo.common.libsvm.protos.SVMParameterProto;
030import org.tribuo.provenance.ModelProvenance;
031import libsvm.svm_model;
032import libsvm.svm_node;
033import org.tribuo.util.Util;
034
035import java.io.Serializable;
036import java.util.ArrayList;
037import java.util.Arrays;
038import java.util.Collections;
039import java.util.List;
040import java.util.Map;
041import java.util.Optional;
042import java.util.logging.Logger;
043import java.util.stream.Collectors;
044
045/**
046 * A model that uses an underlying libSVM model to make the
047 * predictions.
048 * <p>
049 * See:
050 * <pre>
051 * Chang CC, Lin CJ.
052 * "LIBSVM: a library for Support Vector Machines"
053 * ACM transactions on intelligent systems and technology (TIST), 2011.
054 * </pre>
055 * for the nu-svm algorithm:
056 * <pre>
057 * Schölkopf B, Smola A, Williamson R, Bartlett P L.
058 * "New support vector algorithms"
059 * Neural Computation, 2000, 1207-1245.
060 * </pre>
061 * and for the original algorithm:
062 * <pre>
063 * Cortes C, Vapnik V.
064 * "Support-Vector Networks"
065 * Machine Learning, 1995.
066 * </pre>
067 */
068public abstract class LibSVMModel<T extends Output<T>> extends Model<T> implements Serializable {
069    private static final long serialVersionUID = 3L;
070
071    private static final Logger logger = Logger.getLogger(LibSVMModel.class.getName());
072
073    /**
074     * The LibSVM models. Multiple models are used for multi-label or multidimensional regression outputs.
075     * <p>
076     * Not final to support deserialization reordering of multidimensional regression models which have an incorrect id mapping.
077     * Will be final again in some future version which doesn't maintain serialization compatibility with 4.X.
078     */
079    protected List<svm_model> models;
080
081    /**
082     * Constructs a LibSVMModel from the supplied arguments.
083     * @param name The model name.
084     * @param description The model provenance.
085     * @param featureIDMap The features the model knows about.
086     * @param outputIDInfo The outputs the model can produce.
087     * @param generatesProbabilities Does the model generate probabilities or not?
088     * @param models The svm models themselves.
089     */
090    protected LibSVMModel(String name, ModelProvenance description, ImmutableFeatureMap featureIDMap, ImmutableOutputInfo<T> outputIDInfo, boolean generatesProbabilities, List<svm_model> models) {
091        super(name, description, featureIDMap, outputIDInfo, generatesProbabilities);
092        this.models = models;
093    }
094
095    /**
096     * Returns an unmodifiable copy of the underlying list of libsvm models.
097     * @deprecated Deprecated to unify the names across LibLinear, LibSVM and XGBoost.
098     * @return The underlying model list.
099     */
100    @Deprecated
101    public List<svm_model> getModel() {
102        return getInnerModels();
103    }
104
105    /**
106     * Returns an unmodifiable copy of the underlying list of libsvm models.
107     * @return The underlying model list.
108     */
109    public List<svm_model> getInnerModels() {
110        List<svm_model> copy = new ArrayList<>();
111
112        for (svm_model m : models) {
113            copy.add(copyModel(m));
114        }
115
116        return Collections.unmodifiableList(copy);
117    }
118
119    @Override
120    public Map<String, List<Pair<String,Double>>> getTopFeatures(int n) {
121        return Collections.emptyMap();
122    }
123
124    @Override
125    public Optional<Excuse<T>> getExcuse(Example<T> example) {
126        return Optional.empty();
127    }
128
129    /**
130     * Copies an svm_model, as it does not provide a copy method.
131     *
132     * @param model The svm_model to copy.
133     * @return A deep copy of the model.
134     */
135    protected static svm_model copyModel(svm_model model) {
136        svm_model newModel = new svm_model();
137
138        newModel.param = SVMParameters.copyParameters(model.param);
139        newModel.l = model.l;
140        newModel.nr_class = model.nr_class;
141        newModel.rho = model.rho != null ? Arrays.copyOf(model.rho,model.rho.length) : null;
142        newModel.probA = model.probA != null ? Arrays.copyOf(model.probA,model.probA.length) : null;
143        newModel.probB = model.probB != null ? Arrays.copyOf(model.probB,model.probB.length) : null;
144        newModel.label = model.label != null ? Arrays.copyOf(model.label,model.label.length) : null;
145        newModel.sv_indices = model.sv_indices != null ? Arrays.copyOf(model.sv_indices,model.sv_indices.length) : null;
146        newModel.nSV = model.nSV != null ? Arrays.copyOf(model.nSV,model.nSV.length) : null;
147        if (model.SV != null) {
148            newModel.SV = new svm_node[model.SV.length][];
149            for (int i = 0; i < newModel.SV.length; i++) {
150                if (model.SV[i] != null) {
151                    svm_node[] copy = new svm_node[model.SV[i].length];
152                    for (int j = 0; j < copy.length; j++) {
153                        if (model.SV[i][j] != null) {
154                            svm_node curCopy = new svm_node();
155                            curCopy.index = model.SV[i][j].index;
156                            curCopy.value = model.SV[i][j].value;
157                            copy[j] = curCopy;
158                        }
159                    }
160                    newModel.SV[i] = copy;
161                }
162            }
163        }
164        if (model.sv_coef != null) {
165            newModel.sv_coef = new double[model.sv_coef.length][];
166            for (int i = 0; i < newModel.sv_coef.length; i++) {
167                if (model.sv_coef[i] != null) {
168                    newModel.sv_coef[i] = Arrays.copyOf(model.sv_coef[i],model.sv_coef[i].length);
169                }
170            }
171        }
172
173        return newModel;
174    }
175
176    /**
177     * Checks for equality between two svm_models.
178     * <p>
179     * Equality is defined as bit-wise exact for SV, rho, sv_coeff, probA and probB.
180     * @param first The first model.
181     * @param second The second model.
182     * @return True if the models are identical.
183     */
184    public static boolean modelEquals(svm_model first, svm_model second) {
185        boolean svCoeffEquals = Arrays.deepEquals(first.sv_coef, second.sv_coef);
186        boolean probAEquals = Arrays.equals(first.probA, second.probA);
187        boolean probBEquals = Arrays.equals(first.probB, second.probB);
188        boolean nSVEquals = Arrays.equals(first.nSV, second.nSV);
189        boolean rhoEquals = Arrays.equals(first.rho, second.rho);
190        boolean labelEquals = Arrays.equals(first.label, second.label);
191        if (svCoeffEquals && probAEquals && probBEquals && nSVEquals && rhoEquals && labelEquals) {
192            // Check SVs.
193            try {
194                for (int i = 0; i < first.SV.length; i++) {
195                    for (int j = 0; j < first.SV[i].length; j++) {
196                        svm_node firstNode = first.SV[i][j];
197                        svm_node secondNode = second.SV[i][j];
198                        if (firstNode.index != secondNode.index) {
199                            return false;
200                        } else if (Double.compare(firstNode.value,secondNode.value) != 0) {
201                            return false;
202                        }
203                    }
204                }
205                return true;
206            } catch (NullPointerException e) {
207                return false;
208            }
209        } else {
210            return false;
211        }
212    }
213
214    /**
215     * Serializes a svm_parameter to a protobuf.
216     * @param param The parameters to serialize.
217     * @return The protobuf.
218     */
219    protected static SVMParameterProto serializeParameters(svm_parameter param) {
220        SVMParameterProto.Builder paramBuilder = SVMParameterProto.newBuilder();
221        paramBuilder.setSvmType(param.svm_type);
222        paramBuilder.setKernelType(param.kernel_type);
223        paramBuilder.setDegree(param.degree);
224        paramBuilder.setGamma(param.gamma);
225        paramBuilder.setCoef0(param.coef0);
226        paramBuilder.setCacheSize(param.cache_size);
227        paramBuilder.setEps(param.eps);
228        paramBuilder.setC(param.C);
229        paramBuilder.setNrWeight(param.nr_weight);
230        paramBuilder.setNu(param.nu);
231        paramBuilder.setP(param.p);
232        paramBuilder.setShrinking(param.shrinking);
233        paramBuilder.setProbability(param.probability);
234        if (param.weight != null) {
235            for (int i = 0; i < param.weight.length; i++) {
236                paramBuilder.addWeight(param.weight[i]);
237            }
238        }
239        if (param.weight_label != null) {
240            for (int i = 0; i < param.weight_label.length; i++) {
241                paramBuilder.addWeightLabel(param.weight_label[i]);
242            }
243        }
244        return paramBuilder.build();
245    }
246
247    /**
248     * Serializes a LibSVM svm_model to a protobuf.
249     * @param model The model to serialize.
250     * @return The protobuf representation.
251     */
252    protected static SVMModelProto serializeModel(svm_model model) {
253        SVMModelProto.Builder modelBuilder = SVMModelProto.newBuilder();
254        modelBuilder.setParam(serializeParameters(model.param));
255        modelBuilder.setNrClass(model.nr_class);
256        modelBuilder.setL(model.l);
257        if (model.SV != null) {
258            for (int i = 0; i < model.SV.length; i++) {
259                SVMNodeArrayProto.Builder nodeBuilder = SVMNodeArrayProto.newBuilder();
260                for (int j = 0; j < model.SV[i].length; j++) {
261                    nodeBuilder.addIndex(model.SV[i][j].index);
262                    nodeBuilder.addValue(model.SV[i][j].value);
263                }
264                modelBuilder.addSV(nodeBuilder.build());
265            }
266        }
267        if (model.sv_coef != null) {
268            for (int i = 0; i < model.sv_coef.length; i++) {
269                modelBuilder.addSvCoefLengths(model.sv_coef[i].length);
270                for (int j = 0; j < model.sv_coef[i].length; j++) {
271                    modelBuilder.addSvCoef(model.sv_coef[i][j]);
272                }
273            }
274        }
275        if (model.rho != null) {
276            modelBuilder.addAllRho(Arrays.stream(model.rho).boxed().collect(Collectors.toList()));
277        }
278        if (model.probA != null) {
279            modelBuilder.addAllProbA(Arrays.stream(model.probA).boxed().collect(Collectors.toList()));
280        }
281        if (model.probB != null) {
282            modelBuilder.addAllProbB(Arrays.stream(model.probB).boxed().collect(Collectors.toList()));
283        }
284        if (model.sv_indices != null) {
285            modelBuilder.addAllSvIndices(Arrays.stream(model.sv_indices).boxed().collect(Collectors.toList()));
286        }
287        if (model.label != null) {
288            modelBuilder.addAllLabel(Arrays.stream(model.label).boxed().collect(Collectors.toList()));
289        }
290        if (model.nSV != null) {
291            modelBuilder.addAllNSV(Arrays.stream(model.nSV).boxed().collect(Collectors.toList()));
292        }
293        return modelBuilder.build();
294    }
295
296    /**
297     * Deserializes svm_parameter from a protobuf.
298     * @param proto The protobuf to deserialize.
299     * @return The parameters.
300     */
301    protected static svm_parameter deserializeParameters(SVMParameterProto proto) {
302        svm_parameter param = new svm_parameter();
303        param.svm_type = proto.getSvmType();
304        param.kernel_type = proto.getKernelType();
305        param.degree = proto.getDegree();
306        param.gamma = proto.getGamma();
307        param.coef0 = proto.getCoef0();
308        param.cache_size = proto.getCacheSize();
309        param.eps = proto.getEps();
310        param.C = proto.getC();
311        param.nr_weight = proto.getNrWeight();
312        param.nu = proto.getNu();
313        param.p = proto.getP();
314        param.shrinking = proto.getShrinking();
315        param.probability = proto.getProbability();
316        if (proto.getWeightCount() > 0) {
317            param.weight = new double[proto.getWeightCount()];
318            for (int i = 0; i < proto.getWeightCount(); i++) {
319                param.weight[i] = proto.getWeight(i);
320            }
321        }
322        if (proto.getWeightLabelCount() > 0) {
323            param.weight_label = new int[proto.getWeightLabelCount()];
324            for (int i = 0; i < proto.getWeightLabelCount(); i++) {
325                param.weight_label[i] = proto.getWeightLabel(i);
326            }
327        }
328        return param;
329    }
330
331    /**
332     * Deserializes a LibSVM svm_model from a protobuf.
333     * @param proto The protobuf to deserialize.
334     * @return The svm_model.
335     */
336    protected static svm_model deserializeModel(SVMModelProto proto) {
337        svm_model model = new svm_model();
338        model.param = deserializeParameters(proto.getParam());
339        model.nr_class = proto.getNrClass();
340        model.l = proto.getL();
341        if (proto.getSVCount() > 0) {
342            model.SV = new svm_node[proto.getSVCount()][];
343            for (int i = 0; i < proto.getSVCount(); i++) {
344                SVMNodeArrayProto nodes = proto.getSV(i);
345                if (nodes.getIndexCount() != nodes.getValueCount()) {
346                    throw new IllegalStateException("Invalid protobuf, expected the same number of indices and values, found " + nodes.getIndexCount() + " indices and " + nodes.getValueCount() + " values");
347                } else {
348                    model.SV[i] = new svm_node[nodes.getIndexCount()];
349                    for (int j = 0; j < nodes.getIndexCount(); j++) {
350                        model.SV[i][j] = new svm_node();
351                        model.SV[i][j].index = nodes.getIndex(j);
352                        model.SV[i][j].value = nodes.getValue(j);
353                    }
354                }
355            }
356        }
357        if (proto.getSvCoefCount() > 0) {
358            if (proto.getSvCoefLengthsCount() > 0) {
359                model.sv_coef = new double[proto.getSvCoefLengthsCount()][];
360                for (int i = 0; i < proto.getSvCoefLengthsCount(); i++) {
361                    model.sv_coef[i] = new double[proto.getSvCoefLengths(i)];
362                }
363                int i = 0;
364                int j = 0;
365                for (int k = 0; k < proto.getSvCoefCount(); k++) {
366                    model.sv_coef[i][j] = proto.getSvCoef(k);
367                    j++;
368                    if (j >= proto.getSvCoefLengths(i)) {
369                        i++;
370                        j = 0;
371                    }
372                }
373            } else {
374                throw new IllegalStateException("Invalid protobuf, length counts not stored for sv_coef");
375            }
376        }
377        if (proto.getRhoCount() > 0) {
378            model.rho = Util.toPrimitiveDouble(proto.getRhoList());
379        }
380        if (proto.getProbACount() > 0) {
381            model.probA = Util.toPrimitiveDouble(proto.getProbAList());
382        }
383        if (proto.getProbBCount() > 0) {
384            model.probB = Util.toPrimitiveDouble(proto.getProbBList());
385        }
386        if (proto.getSvIndicesCount() > 0) {
387            model.sv_indices = Util.toPrimitiveInt(proto.getSvIndicesList());
388        }
389        if (proto.getLabelCount() > 0) {
390            model.label = Util.toPrimitiveInt(proto.getLabelList());
391        }
392        if (proto.getNSVCount() > 0) {
393            model.nSV = Util.toPrimitiveInt(proto.getNSVList());
394        }
395
396        return model;
397    }
398}