/*
 * Copyright (C) 2016 Edward Raff
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */
package jsat.classifiers.svm;

import java.util.concurrent.ExecutorService;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.distributions.kernels.KernelTrick;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.Vec;
import static java.lang.Math.*;
import java.util.Arrays;
import jsat.distributions.kernels.NormalizedKernel;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;

/**
 * This class implements a version of the Support Vector Machine without a bias
 * term. In addition, the current implementation requires that the Kernel Trick
 * used be a {@link KernelTrick#normalized() normalized} kernel. If the given
 * kernel is not normalized, this class will automatically wrap it to become
 * normalized.
*
* Because there is no bias term, this class should never be used with the * Linear kernel. But for the more common RBF kernel the lack of bias term * should have minimal impact on accuracy.
*
* See: Steinwart, I., Hush, D., & Scovel, C. (2011). Training SVMs Without * Offset. The Journal of Machine Learning Research, 12, 141–202. * * @author Edward Raff */ public class SVMnoBias extends SupportVectorLearner implements BinaryScoreClassifier { private double C = 1; private double tolerance = 1e-3; /** * Stores the true label value (-1 or +1) of the data point */ protected short[] label; /** * Weight values to apply to each data point */ protected Vec weights; //Variables used during training private double T_a; private double S_a; /** * Creates a new SVM object that uses no cache mode. * * @param kf the kernel trick to use */ public SVMnoBias(KernelTrick kf) { super(kf, SupportVectorLearner.CacheMode.NONE); } public SVMnoBias(SVMnoBias toCopy) { super(toCopy); if(toCopy.weights != null) this.weights = toCopy.weights.clone(); if(toCopy.label != null) this.label = Arrays.copyOf(toCopy.label, toCopy.label.length); this.C = toCopy.C; this.tolerance = toCopy.tolerance; } @Override public void setKernel(KernelTrick kernel) { if(kernel.normalized()) super.setKernel(kernel); else super.setKernel(new NormalizedKernel(kernel)); } @Override public double getScore(DataPoint dp) { return kEvalSum(dp.getNumericalValues()); } @Override public SVMnoBias clone() { return new SVMnoBias(this); } @Override public CategoricalResults classify(DataPoint data) { if (vecs == null) throw new UntrainedModelException("Classifier has yet to be trained"); CategoricalResults cr = new CategoricalResults(2); double sum = getScore(data); if (sum > 0) cr.setProb(1, 1); else cr.setProb(0, 1); return cr; } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { bookKeepingInit(dataSet); double[] nabla_W = procedure3_init(); solver_1d(nabla_W, parallel); setCacheMode(null); } /** * * @param dataSet the dataset to train on * @param warm_start Array of initial alpha values to use for support * vectors. The absolute value of the inputs will be used. may be longer * than the number of data points. */ protected void train(ClassificationDataSet dataSet, double[] warm_start) { train(dataSet, warm_start, false); } protected void train(ClassificationDataSet dataSet, double[] warm_start, boolean parallel) { bookKeepingInit(dataSet); for(int i = 0; i < alphas.length; i++) alphas[i] = Math.abs(warm_start[i]); double[] nabla_W = procedure4m_init(parallel); solver_1d(nabla_W, parallel); setCacheMode(null); } private void solver_1d(final double[] nabla_W, boolean parallel) { final int N = alphas.length; final double lambda = 1/(2*C*N); //Algorithm 1 1D-SVM solver while(S_a > tolerance/(2*lambda)) { // System.out.println(S_a + " > " + tolerance/(2*lambda)); //Procedure 1 Calculate i∗ ∈ argmaxi=1,...,n δi · (∇Wi(α)−δi/2) double bestgain = -1; int i_max = -1; double best_delta = -1; for(int i = 0; i < N; i++) { double a_star_i = max(min(weights.get(i)*C, nabla_W[i]+alphas[i]), 0); double delta = a_star_i-alphas[i]; ///gain←δ· (∇Wi(α)−δ/2) double gain = delta*(nabla_W[i]-delta/2); if(gain >= bestgain) { bestgain = gain; i_max = i; best_delta = delta; } } //adjust alhpa alphas[i_max] += best_delta; //fuzzy clip to get hard 0/Cs if(alphas[i_max] + 1e-7 > weights.get(i_max)*C )//round to max alphas[i_max] = weights.get(i_max)*C; else if(alphas[i_max] - 1e-7 < 0)//round to 0 alphas[i_max] = 0; final double delta = best_delta; final int i = i_max; //use Procedure 2 to update ∇W(α) in direction i∗ by δ and calculate S(α) //T(α)←T(α)−δ(2∇Wi(α)−1−δ) T_a -= best_delta*(2*nabla_W[i_max]-1-best_delta); final AtomicDouble E_a = new AtomicDouble(0.0); accessingRow(i);//hint to caching scheme ParallelUtils.run(parallel, N, (start, end) -> { double Ea_delta = 0; for (int j = start; j < end; j++) { nabla_W[j] -= delta * label[i] * label[j] * kEval(i, j); Ea_delta += weights.get(j) * C * min(max(0, nabla_W[j]), 2); } E_a.addAndGet(Ea_delta); }); S_a = T_a + E_a.get(); } accessingRow(-1);//no more row accesses //collapse label into signed alphas for(int i = 0; i < label.length; i++) alphas[i] *= label[i]; } private double[] procedure3_init() { int N = alphas.length; //Procedure 3 Initialize by αi←0 and compute ∇W(α), S(α), and T(α). T_a = 0; S_a = 0; double[] nabla_W = new double[N]; for(int i = 0; i < N; i++) { nabla_W[i] = 1; S_a += weights.get(i)*C; } return nabla_W; } private double[] procedure4m_init(boolean parallel) { final int N = alphas.length; //Procedure 3 Initialize by αi←0 and compute ∇W(α), S(α), and T(α). T_a = 0; final AtomicDouble E_a = new AtomicDouble(0.0); final AtomicDouble T_a_accum = new AtomicDouble(0.0); final double[] nabla_W = new double[N]; ParallelUtils.run(parallel, N, (start, end)-> { double Ta_delta = 0; double Ea_delta = 0; for(int i = start; i < end; i++) { nabla_W[i] = 1; double nabla_Wi_delta = 0; for(int j = 0; j < N; j++) { if(alphas[j] == 0) continue; //We call k instead of kEval b/c we are accing most //of the n^2 values, so nothing will get to stay in //cache. Unless we are using FULL cacheing, in which //case we will get re-use. //Using k avoids LRU overhead which can be significant //for fast to evaluate datasets double k_ij; if(getCacheMode() == CacheMode.FULL) k_ij = kEval(i, j); else k_ij = k(i, j); nabla_Wi_delta -= alphas[j] * label[i] * label[j] * k_ij; } nabla_W[i] += nabla_Wi_delta; Ta_delta -= alphas[i]*nabla_W[i]; Ea_delta += weights.get(i)*C*min(max(nabla_W[i], 0), 2); } E_a.addAndGet(Ea_delta); T_a_accum.addAndGet(Ta_delta); }); T_a = T_a_accum.get(); S_a = T_a + E_a.get(); return nabla_W; } private void bookKeepingInit(ClassificationDataSet dataSet) { final int N = dataSet.getSampleSize(); vecs = dataSet.getDataVectors(); weights = dataSet.getDataWeights(); label = new short[N]; for(int i = 0; i < N; i++) label[i] = (short) (dataSet.getDataPointCategory(i)*2-1); setCacheMode(getCacheMode());//Initiates the cahce //initialize alphas array to all zero alphas = new double[N];//zero is default value } @Override public boolean supportsWeightedData() { return true; } /** * Sets the complexity parameter of SVM. The larger the C value the harder * the margin SVM will attempt to find. Lower values of C allow for more * misclassification errors. * @param C the soft margin parameter */ // @Parameter.WarmParameter(prefLowToHigh = true) public void setC(double C) { if(C <= 0) throw new ArithmeticException("C must be a positive constant"); this.C = C; } /** * Returns the soft margin complexity parameter of the SVM * @return the complexity parameter of the SVM */ public double getC() { return C; } /** * Sets the tolerance for the solution. Higher values converge to worse * solutions, but do so faster * @param tolerance the tolerance for the solution */ public void setTolerance(double tolerance) { this.tolerance = tolerance; } /** * Returns the solution tolerance * @return the solution tolerance */ public double getTolerance() { return tolerance; } }

Ads help maintain this website.