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.classification.sgd.kernel;
018
019import com.google.protobuf.Any;
020import com.google.protobuf.InvalidProtocolBufferException;
021import com.oracle.labs.mlrg.olcut.util.Pair;
022import org.tribuo.Example;
023import org.tribuo.Excuse;
024import org.tribuo.ImmutableFeatureMap;
025import org.tribuo.ImmutableOutputInfo;
026import org.tribuo.Model;
027import org.tribuo.Prediction;
028import org.tribuo.classification.Label;
029import org.tribuo.classification.sgd.protos.KernelSVMModelProto;
030import org.tribuo.impl.ModelDataCarrier;
031import org.tribuo.math.kernel.Kernel;
032import org.tribuo.math.la.DenseMatrix;
033import org.tribuo.math.la.DenseVector;
034import org.tribuo.math.la.SparseVector;
035import org.tribuo.math.la.Tensor;
036import org.tribuo.math.protos.TensorProto;
037import org.tribuo.protos.core.ModelProto;
038import org.tribuo.provenance.ModelProvenance;
039
040import java.util.Collections;
041import java.util.LinkedHashMap;
042import java.util.List;
043import java.util.Map;
044import java.util.Optional;
045
046/**
047 * The inference time version of a kernel model trained using Pegasos.
048 * <p>
049 * See:
050 * <pre>
051 * Shalev-Shwartz S, Singer Y, Srebro N, Cotter A
052 * "Pegasos: Primal Estimated Sub-Gradient Solver for SVM"
053 * Mathematical Programming, 2011.
054 * </pre>
055 */
056public class KernelSVMModel extends Model<Label> {
057    private static final long serialVersionUID = 2L;
058
059    /**
060     * Protobuf serialization version.
061     */
062    public static final int CURRENT_VERSION = 0;
063
064    private final Kernel kernel;
065    private final SparseVector[] supportVectors;
066    private final DenseMatrix weights;
067
068    KernelSVMModel(String name, ModelProvenance description,
069                          ImmutableFeatureMap featureIDMap, ImmutableOutputInfo<Label> labelIDMap,
070                          Kernel kernel, SparseVector[] supportVectors, DenseMatrix weights) {
071        super(name, description, featureIDMap, labelIDMap, false);
072        this.kernel = kernel;
073        this.supportVectors = supportVectors;
074        this.weights = weights;
075    }
076
077    /**
078     * Deserialization factory.
079     * @param version The serialized object version.
080     * @param className The class name.
081     * @param message The serialized data.
082     * @throws InvalidProtocolBufferException If the protobuf could not be parsed from the {@code message}.
083     * @return The deserialized object.
084     */
085    public static KernelSVMModel deserializeFromProto(int version, String className, Any message) throws InvalidProtocolBufferException {
086        if (version < 0 || version > CURRENT_VERSION) {
087            throw new IllegalArgumentException("Unknown version " + version + ", this class supports at most version " + CURRENT_VERSION);
088        }
089        KernelSVMModelProto proto = message.unpack(KernelSVMModelProto.class);
090
091        ModelDataCarrier<?> carrier = ModelDataCarrier.deserialize(proto.getMetadata());
092        if (!carrier.outputDomain().getOutput(0).getClass().equals(Label.class)) {
093            throw new IllegalStateException("Invalid protobuf, output domain is not a label domain, found " + carrier.outputDomain().getClass());
094        }
095        @SuppressWarnings("unchecked") // guarded by getClass
096        ImmutableOutputInfo<Label> outputDomain = (ImmutableOutputInfo<Label>) carrier.outputDomain();
097
098        SparseVector[] supportVectors = new SparseVector[proto.getSupportVectorsCount()];
099        int featureSize = carrier.featureDomain().size() + 1;
100        List<TensorProto> supportProtos = proto.getSupportVectorsList();
101        for (int i = 0; i < supportProtos.size(); i++) {
102            Tensor tensor = Tensor.deserialize(supportProtos.get(i));
103            if (!(tensor instanceof SparseVector)) {
104                throw new IllegalStateException("Invalid protobuf, support vector must be a sparse vector, found " + tensor.getClass());
105            }
106            SparseVector vec = (SparseVector) tensor;
107            if (vec.size() != featureSize) {
108                throw new IllegalStateException("Invalid protobuf, support vector size must equal feature domain size, found " + vec.size() + ", expected " + featureSize);
109            }
110            supportVectors[i] = vec;
111        }
112
113        Tensor weightTensor = Tensor.deserialize(proto.getWeights());
114        if (!(weightTensor instanceof DenseMatrix)) {
115            throw new IllegalStateException("Invalid protobuf, weights must be a dense matrix, found " + weightTensor.getClass());
116        }
117        DenseMatrix weights = (DenseMatrix) weightTensor;
118        if (weights.getDimension1Size() != carrier.outputDomain().size()) {
119            throw new IllegalStateException("Invalid protobuf, weights not the right size, expected " + carrier.outputDomain().size() + ", found " + weights.getDimension1Size());
120        }
121        if (weights.getDimension2Size() != supportVectors.length) {
122            throw new IllegalStateException("Invalid protobuf, weights not the right size, expected " + supportVectors.length + ", found " + weights.getDimension2Size());
123        }
124
125        Kernel kernel = Kernel.deserialize(proto.getKernel());
126
127        return new KernelSVMModel(carrier.name(), carrier.provenance(), carrier.featureDomain(), outputDomain,
128                kernel, supportVectors, weights);
129    }
130
131    /**
132     * Returns the number of support vectors used.
133     * @return The number of support vectors.
134     */
135    public int getNumberOfSupportVectors() {
136        return supportVectors.length;
137    }
138
139    @Override
140    public Prediction<Label> predict(Example<Label> example) {
141        SparseVector features = SparseVector.createSparseVector(example,featureIDMap,true);
142        // Due to bias feature
143        if (features.numActiveElements() == 1) {
144            throw new IllegalArgumentException("No features found in Example " + example.toString());
145        }
146        double[] scores = new double[supportVectors.length];
147        for (int i = 0; i < scores.length; i++) {
148            scores[i] = kernel.similarity(features,supportVectors[i]);
149        }
150        DenseVector scoreVector = DenseVector.createDenseVector(scores);
151        DenseVector prediction = weights.leftMultiply(scoreVector);
152
153        double maxScore = Double.NEGATIVE_INFINITY;
154        Label maxLabel = null;
155        Map<String,Label> predMap = new LinkedHashMap<>();
156        for (int i = 0; i < prediction.size(); i++) {
157            String labelName = outputIDInfo.getOutput(i).getLabel();
158            Label label = new Label(labelName, prediction.get(i));
159            predMap.put(labelName, label);
160            if (label.getScore() > maxScore) {
161                maxScore = label.getScore();
162                maxLabel = label;
163            }
164        }
165        return new Prediction<>(maxLabel, predMap, features.numActiveElements(), example, generatesProbabilities);
166    }
167
168    @Override
169    public Map<String, List<Pair<String, Double>>> getTopFeatures(int n) {
170        return Collections.emptyMap();
171    }
172
173    @Override
174    public Optional<Excuse<Label>> getExcuse(Example<Label> example) {
175        return Optional.empty();
176    }
177
178    @Override
179    public ModelProto serialize() {
180        ModelDataCarrier<Label> carrier = createDataCarrier();
181        KernelSVMModelProto.Builder modelBuilder = KernelSVMModelProto.newBuilder();
182        modelBuilder.setMetadata(carrier.serialize());
183        modelBuilder.setKernel(kernel.serialize());
184        modelBuilder.setWeights(weights.serialize());
185        for (SparseVector v : supportVectors) {
186            modelBuilder.addSupportVectors(v.serialize());
187        }
188
189        ModelProto.Builder builder = ModelProto.newBuilder();
190        builder.setVersion(CURRENT_VERSION);
191        builder.setClassName(KernelSVMModel.class.getName());
192        builder.setSerializedData(Any.pack(modelBuilder.build()));
193
194        return builder.build();
195    }
196
197    @Override
198    protected KernelSVMModel copy(String newName, ModelProvenance newProvenance) {
199        SparseVector[] vectorCopies = new SparseVector[supportVectors.length];
200        for (int i = 0; i < vectorCopies.length; i++) {
201            vectorCopies[i] = supportVectors[i].copy();
202        }
203        return new KernelSVMModel(newName,newProvenance,featureIDMap,outputIDInfo,kernel,vectorCopies,new DenseMatrix(weights));
204    }
205}