/*
 * 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.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.calibration.BinaryScoreClassifier;
import jsat.classifiers.neuralnetwork.RBFNet;
import jsat.clustering.kmeans.ElkanKernelKMeans;
import jsat.clustering.kmeans.KernelKMeans;
import jsat.clustering.kmeans.LloydKernelKMeans;
import jsat.distributions.kernels.KernelTrick;
import jsat.distributions.kernels.RBFKernel;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.FakeExecutor;
import jsat.utils.IntList;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;

/**
 * This is an implementation of the Divide-and-Conquer Support Vector Machine
 * (DC-SVM). It uses a a combination of clustering and warm-starting to train
 * faster, as well as an early stopping strategy to provide a fast approximate
 * SVM solution. The final accuracy should often be at or near that of a normal
 * SVM, while being faster to train. 
*
* The current implementation is based on {@link SVMnoBias}, meaning this code * does not have a bias term and it only works with normalized kernels. Any * non-normalized kernel will be normalized automatically. This is not a problem * for the common RBF kernel.
*
* * See: *
    *
  • Hsieh, C.-J., Si, S., & Dhillon, I. S. (2014). A Divide-and-Conquer * Solver for Kernel Support Vector Machines. In Proceedings of the 31st * International Conference on Machine Learning. Beijing, China.
  • *
* * @author Edward Raff */ public class DCSVM extends SupportVectorLearner implements Classifier, Parameterized, BinaryScoreClassifier { private double C = 1; private double tolerance = 1e-3; private KernelKMeans clusters; private int m = 2000; private int l_max = 4; private int l_early = 3; private int k = 4; private Map early_models; private long cache_size = 0; /** * Creates a new DC-SVM for the given kernel * @param k the kernel to use */ public DCSVM(KernelTrick k) { super(k, CacheMode.ROWS); this.cache_size = Runtime.getRuntime().freeMemory()/2; } /** * Creates a new DC-SVM for the RBF kernel */ public DCSVM() { this(new RBFKernel()); } /** * Copy Constructor * @param toCopy object to copy */ public DCSVM(DCSVM toCopy) { super(toCopy); this.C = toCopy.C; this.tolerance = toCopy.tolerance; if(toCopy.clusters != null) this.clusters = toCopy.clusters.clone(); this.cache_size = toCopy.cache_size; this.m = toCopy.m; this.l_early = toCopy.l_early; this.l_max = toCopy.l_max; this.k = toCopy.k; if(toCopy.early_models != null) { this.early_models = new ConcurrentHashMap(); for(Map.Entry x : toCopy.early_models.entrySet()) this.early_models.put(x.getKey(), x.getValue().clone()); } } /** * The DC-SVM algorithm works by creating a hierarchy of levels, and * iteratively refining the solution from one level to the next. Level 0 * corresponds to the exact SVM solution, and higher levels are courser * approximations. This method controls which level the training starts at. * * @param l_max which level to start the training at. */ public void setStartLevel(int l_max) { if(l_max < 0) throw new IllegalArgumentException("l_max must be a non-negative integer, not " + l_max); this.l_max = l_max; } /** * * @return which level to start the training at. */ public int getStartLevel() { return l_max; } /** * The DC-SVM algorithm works by creating a hierarchy of levels, and * iteratively refining the solution from one level to the next. Level 0 * corresponds to the exact SVM solution, and higher levels are courser * approximations. This method controls which level the training stops at, * with 0 being the latest it can stop. The default stopping level is 3. * * @param l_early which level to stop the training at, and use for * classification. */ public void setEndLevel(int l_early) { if(l_early < 0) throw new IllegalArgumentException("l_early must be a non-negative integer, not " + l_early); this.l_early = l_early; } /** * * @return which level to stop the training at, and use for * classification. */ public int getEndLevel() { return l_early; } /** * At each level of the DC-SVM training, a clustering algorithm is used to * divide the dataset into sub-groups for independent training. Increasing * the number of points used for clustering improves model accuracy, but * also increases training time. The default value is 2000. This value may * need to be increased if using a higher staring level. * * @param m the number of data points to sample for each cluster size */ public void setClusterSampleSize(int m) { if(m <= 0) throw new IllegalArgumentException("Cluster Sample Size must be a positive integer, not " + m); this.m = m; } public int getClusterSampleSize() { return m; } @Override public CategoricalResults classify(DataPoint data) { 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 double getScore(DataPoint dp) { if (vecs == null) throw new UntrainedModelException("Classifier has yet to be trained"); Vec x = dp.getNumericalValues(); int c; if(early_models.size() > 1) c = clusters.findClosestCluster(x, getKernel().getQueryInfo(x)); else c = 0; return early_models.get(c).getScore(dp); } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { final int N = dataSet.getSampleSize(); vecs = dataSet.getDataVectors(); early_models = new ConcurrentHashMap<>(); // weights = dataSet.getDataWeights(); // label = new short[N]; // for(int i = 0; i < N; i++) // label[i] = (short) (dataSet.getDataPointCategory(i)*2-1); setCacheMode(CacheMode.NONE);//Initiates the accel cache //initialize alphas array to all zero alphas = new double[N];//zero is default value /** * Used to keep track of which sub cluster each training datapoint belongs to */ final int[] group = new int[N]; /** * Used to select subsamples of data points for clustering, and to map them back to their original indicies */ IntList indicies = new IntList(); //for l = lmax, . . . , 1 do for(int l = l_max; l >= l_early; l--) { // System.out.println("Level " + l); early_models.clear(); //sub-sampled dataset to use for clustering ClassificationDataSet toCluster = new ClassificationDataSet(dataSet.getNumNumericalVars(), dataSet.getCategories(), dataSet.getPredicting()); //Set number of clusters in the current level k_l = k^l int k_l = (int) Math.pow(k, l); //number of datapoints to use in clustering //increase M = m by default. Increase to M=7 m if less than 7 points per cluster int M; if( N/k_l < 7 ) M = k_l*7; else M = m; if(l == l_max) { ListUtils.addRange(indicies, 0, N, 1); Collections.shuffle(indicies); for(int i = 0; i < Math.min(M, N); i++) toCluster.addDataPoint(dataSet.getDataPoint(i), dataSet.getDataPointCategory(i)); } else { indicies.clear(); for(int i = 0; i < N; i++) if(alphas[i] != 0) indicies.add(i); Collections.shuffle(indicies); for(int i = 0; i < Math.min(M, indicies.size()); i++) toCluster.addDataPoint(dataSet.getDataPoint(i), dataSet.getDataPointCategory(i)); } //Run kernel kmeans on {xi1, . . . ,xim} to get cluster centers c1, . . . , ckl ; clusters = new ElkanKernelKMeans(getKernel()); clusters.setMaximumIterations(100); // System.out.println("Finding " + k_l + " clusters"); k_l = Math.min(k_l, toCluster.getSampleSize()/2);//Few support vectors? Make clustering smaller then int[] sub_results; if(k_l <= 1)//dont run cluster, we are doing final refinement step! { sub_results = new int[N];//will be all 0, for 1 'cluster' indicies.clear(); ListUtils.addRange(indicies, 0, N, 1); } else sub_results = clusters.cluster(toCluster, k_l, parallel, (int[])null); //create partitioning //First, don't bother with distance computations for people we just clustered Arrays.fill(group, -1); Set found_clusters = new IntSet(k_l); for(int i = 0; i < sub_results.length; i++) { group[indicies.get(i)] = sub_results[i]; found_clusters.add(sub_results[i]); } //find who everyone else belongs to ParallelUtils.run(parallel, N, (i)-> { if (group[i] >= 0) return;//you already got assigned above List qi = null; if (accelCache != null) { int multiplier = accelCache.size() / N; qi = accelCache.subList(i * multiplier, i * multiplier + multiplier); } group[i] = clusters.findClosestCluster(vecs.get(i), qi); }); //everyone has now been assigned to their closest cluster //build SVM model for each cluster for(int c : found_clusters) { // System.out.println("\tBuilding model for " + c); ClassificationDataSet V_c = new ClassificationDataSet(dataSet.getNumNumericalVars(), dataSet.getCategories(), dataSet.getPredicting()); DoubleList V_alphas = new DoubleList(); IntList orig_index = new IntList(); for (int i = 0; i < N; i++) { if (group[i] != c) continue;//well get to you later //else, create dataset V_c.addDataPoint(dataSet.getDataPoint(i), dataSet.getDataPointCategory(i)); V_alphas.add(Math.abs(alphas[i])); orig_index.add(i); } SVMnoBias svm = new SVMnoBias(getKernel()); if(cache_size > 0) svm.setCacheSize(V_alphas.size(), cache_size); else svm.setCacheMode(CacheMode.NONE); //Train model if(l == l_max)//first round, no warm start svm.train(V_c, parallel); else//warm start { svm.train(V_c, V_alphas.getBackingArray(), parallel); } early_models.put(c, svm); //Update larger set of alphas for(int i = 0; i < orig_index.size(); i++) this.alphas[orig_index.get(i)] = svm.alphas[i]; } } if(l_early == 0)//fully solve the problem! Refinement step was done implicitly in above loop { SVMnoBias svm = new SVMnoBias(getKernel()); if (cache_size > 0) svm.setCacheSize(dataSet.getSampleSize(), cache_size ); else svm.setCacheMode(CacheMode.NONE); svm.train(dataSet, Arrays.copyOf(this.alphas, this.alphas.length), parallel); early_models.clear(); early_models.put(0, svm); //Update all alphas for (int i = 0; i < N; i++) this.alphas[i] = svm.alphas[i]; } } @Override public boolean supportsWeightedData() { return true; } @Override public DCSVM clone() { return new DCSVM(this); } /** * 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; } }

Ads help maintain this website.