package jsat.classifiers.svm;

import java.io.Serializable;
import java.util.*;
import jsat.distributions.kernels.KernelTrick;
import jsat.distributions.kernels.LinearKernel;
import jsat.linear.Vec;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.utils.DoubleList;
import jsat.utils.ListUtils;
import jsat.utils.concurrent.ConcurrentCacheLRU;

/**
 * Base class for support vector style learners. This means that the learner
 * performs batch training on a fixed set of training points using a
 * {@link KernelTrick kernel} to project the data into a different space. The
 * final set of vectors used may or may not be sparse. It does not necessarily
 * have to be a Support Vector machine.
 * 

* This class provides caching mechanism to transparently provide faster kernel. * * @author Edward Raff */ public abstract class SupportVectorLearner implements Serializable { static final long serialVersionUID = 210140232301130063L; //Implementation note, NaN is used to indicate a cache value that has not been computed yet. @ParameterHolder private KernelTrick kernel; /** * The array of vectors. In the training phase, this should be the set of * all training vectors. After training, this should contain only the set of * support vectors. */ protected List vecs; /** * The array of coefficients associated with each support vector. This * should be instantiated directly when training. When the set of alphas and * support vectors is finalized, {@link #setAlphas(double[]) } should be * called with a reference to itself or the array where the final alphas are * stored. This will initialized any accelerating structures so that * {@link #kEvalSum(jsat.linear.Vec) } can be called. */ protected double[] alphas; private CacheMode cacheMode; /** * Kernel evaluation acceleration cache */ protected List accelCache = null; private double[][] fullCache; /** * Stores rows of a cache matrix. */ private ConcurrentCacheLRU partialCache; /** * We allow algorithms that know they are going to access a specific row to * hint, and save that row in this object to avoid overhead of hitting the * LRU. See {@link #accessingRow(int) } */ private double[] specific_row_cache_values = null; /** * The row that has been explicitly cached */ private int specific_row_cache_row = -1; /** * Holds an available row for inserting into the cache, null if not * available. All values already set to Nan */ private double[] availableRow; private int cacheConst = 500; /** * Sets the final set of alphas, and indicates that the final accelerating * structures (if available) should be constructed for performing kernel * evaluations against unseen vectors. *
* This may be called multiple times in an online scenario, but calls will * involve a re-construction of the whole cache. * * @param alphas the final array of alphas */ protected void setAlphas(double[] alphas) { this.alphas = alphas; accelCache = kernel.getAccelerationCache(vecs); } /** * Determines how the final kernel values are cached. The total number of * raw kernel evaluations can be tracked using {@link #evalCount}
* {@link #setCacheMode(jsat.classifiers.svm.SupportVectorLearner.CacheMode) } * should be called before training begins by the training algorithm as * described in the method documentation. */ public enum CacheMode { /** * No kernel value caching will be performed. */ NONE, /** * The entire kernel matrix will be created and cached ahead of time. * This is the best option if your data set is small and the kernel * cache can fit into memory. */ FULL, /** * Only the most recently used rows of the kernel matrix will be cached * (LRU). When a call to {@link #k(int, int) } occurs, the first value * will be taken to be the row of the matrix.
* Because the kernel matrix is symmetric, if a cache miss occurs - the * column value will be checked for its existence. If the row is * present, it will be used instead. If both rows are not present, then * a new row is inserted for the first index, and another row evicted if * necessary. *
* The {@link #cacheEvictions} indicates how many times a row has been * evicted from the cache. *
* Row values are computed lazily. */ ROWS }; /** * This constructor is meant manly for Serialization to work. It uses a * linear kernel and no caching. */ protected SupportVectorLearner() { this(new LinearKernel(), CacheMode.NONE); } /** * Creates a new Support Vector Learner * @param kernel the kernel trick to use * @param cacheMode the kernel caching method to use */ public SupportVectorLearner(KernelTrick kernel, CacheMode cacheMode) { this.cacheMode = cacheMode; setKernel(kernel); } /** * Copy constructor * @param toCopy the object to copy */ public SupportVectorLearner(SupportVectorLearner toCopy) { if(toCopy.kernel != null) this.kernel = toCopy.kernel.clone(); if(toCopy.vecs != null) { this.vecs = new ArrayList(toCopy.vecs.size()); for(Vec v : toCopy.vecs) this.vecs.add(v.clone()); } if(toCopy.alphas != null) this.alphas = Arrays.copyOf(toCopy.alphas, toCopy.alphas.length); this.cacheMode = toCopy.cacheMode; if(toCopy.accelCache != null) this.accelCache = new DoubleList(toCopy.accelCache); if(toCopy.fullCache != null) { this.fullCache = new double[toCopy.fullCache.length][]; for(int i = 0; i < toCopy.fullCache.length; i++) this.fullCache[i] = Arrays.copyOf(toCopy.fullCache[i], toCopy.fullCache[i].length); } if(toCopy.partialCache != null)//TODO handling this better needs to be done { setCacheMode(cacheMode); // if(toCopy.availableRow != null) // this.availableRow = Arrays.copyOf(toCopy.availableRow, toCopy.availableRow.length); } this.cacheConst = toCopy.cacheConst; } /** * Sets the kernel trick to use * @param kernel the kernel trick to use */ public void setKernel(KernelTrick kernel) { this.kernel = kernel; } /** * Sets the cache value, which may be interpreted differently by different * caching schemes.
* This is currently only used for {@link CacheMode#ROWS}, where the value * indicates how many rows will be cached. * * @param cacheValue the cache value to be used */ public void setCacheValue(int cacheValue) { this.cacheConst = cacheValue; } /** * Sets the {@link #setCacheValue(int) cache value} to one that will use the * specified amount of memory. If the amount of memory specified is great * enough, this method will automatically set the * {@link #setCacheMode(jsat.classifiers.svm.SupportVectorLearner.CacheMode) * cache mode} to {@link CacheMode#FULL}. * * @param N the number of data points * @param bytes the number of bytes of memory to make the cache */ public void setCacheSize(long N, long bytes) { int DS = Double.SIZE/8; bytes /= DS;//Gets the total number of doubles we can store if(bytes > N*N/2) setCacheMode(CacheMode.FULL); else//How many rows can we handle? { //guessing 2 work overhead for object header + one pointer reference to the array, asusming 64 bit long bytesPerRow = N*DS+3*Long.SIZE/8; int rows = (int) Math.min(Math.max(1, bytes/bytesPerRow), Integer.MAX_VALUE); if(rows > 25) setCacheValue(rows); else//why bother? just use NONE setCacheMode(CacheMode.NONE); } } /** * Returns the current cache value * @return the current cache value */ public int getCacheValue() { return cacheConst; } /** * Returns the current caching mode in use * @return the current caching mode in use */ public CacheMode getCacheMode() { return cacheMode; } /** * Calling this sets the method of caching that will be used.
* This is called called by the implementing class to initialize and clear * the caches. Calling this with the current cache mode will initialize the * caches. Once training is complete, call again with {@code null} to * deinitialize the caches. * * @param cacheMode */ public void setCacheMode(CacheMode cacheMode) { if(cacheMode == null) { fullCache = null; partialCache = null; availableRow = null; return; } this.cacheMode = cacheMode; if(vecs != null) accelCache = kernel.getAccelerationCache(vecs); evalCount = 0; cacheEvictions = 0; final int N = vecs == null ? 0 : vecs.size(); if(cacheMode == CacheMode.FULL && vecs != null) { fullCache = new double[N][]; for(int i = 0; i < N; i++) { fullCache[i] = new double[N-i]; Arrays.fill(fullCache[i], Double.NaN); } //Switched to lazy init, hence NaN above // for(int i = 0; i < N; i++) // for(int j = i; j < N; j++) // fullCache[i][j-i] = k(i, j); } else if(cacheMode == CacheMode.ROWS && vecs != null) { partialCache = new ConcurrentCacheLRU(cacheConst); } else if(cacheMode == CacheMode.NONE) fullCache = null; } protected int evalCount = 0; protected int cacheEvictions = 0; public KernelTrick getKernel() { return kernel; } /** * Performs a summation of the form
* ∑ αi k(xi, y)
* for each support vector and associated alpha value currently stored in * the support vector machine. It is not necessary to call * {@link #setAlphas(double[]) } before calling this, but kernel evaluations * may be slower if this is not done. * @param y the vector to perform the kernel product sum against * @return the sum of the scaled kernel products */ protected double kEvalSum(Vec y) { if (alphas == null) throw new RuntimeException("alphas have not been set"); return kernel.evalSum(vecs, accelCache, alphas, y, 0, alphas.length); } /** * Performs a kernel evaluation of the product between two vectors directly. * This is the slowest way to do a kernel evaluation, and should be avoided * unless there is a specific reason to do so. *
* These evaluations will not be counted in {@link #evalCount} * @param a the first vector * @param b the second vector * @return the kernel evaluation of k(a, b) */ protected double kEval(Vec a, Vec b) { return kernel.eval(a, b); } /** * Performs a kernel evaluation of the a'th and b'th vectors in the * {@link #vecs} array. * * @param a the first vector index * @param b the second vector index * @return the kernel evaluation of k(a, b) */ protected double kEval(int a, int b) { if(cacheMode == CacheMode.FULL) { if(a > b) { int tmp = a; a = b; b = tmp; } double val = fullCache[a][b-a]; if(Double.isNaN(val))//lazy init return fullCache[a][b-a] = k(a, b); return val; } else if(cacheMode == CacheMode.ROWS) { double[] cache; if(specific_row_cache_row == a) cache = specific_row_cache_values; else cache = partialCache.get(a); if (cache == null)//not present { //make a row cache = new double[vecs.size()]; Arrays.fill(cache, Double.NaN); double[] cache_missed = partialCache.putIfAbsentAndGet(a, cache); if(cache_missed != null) cache = cache_missed; if (Double.isNaN(cache[b])) return cache[b] = k(a, b); else return cache[b]; } } return k(a, b); } /** * This method allows the caller to hint that they are about to access many * kernel values for a specific row. The row may be selected out from the * cache into its own location to avoid excess LRU overhead. Giving a * negative index indicates that we are done with the row, and removes it. * This method may be called multiple times with different row values. But * when done accessing a specific row, a negative value should be passed in. * * * @param r the row to cache explicitly to avoid LRU overhead. Or a negative * value to indicate that we are done with any specific row. */ protected void accessingRow(int r) { if (r < 0) { specific_row_cache_row = -1; specific_row_cache_values = null; return; } if(cacheMode == CacheMode.ROWS) { double[] cache = partialCache.get(r); if (cache == null)//not present { //make a row cache = new double[vecs.size()]; Arrays.fill(cache, Double.NaN); double[] cache_missed = partialCache.putIfAbsentAndGet(r, cache); if(cache_missed != null) cache = cache_missed; } specific_row_cache_values = cache; specific_row_cache_row = r; } } /** * Internal kernel eval source. Only call directly if you KNOW you will not * be re-using the resulting value and intentionally wish to skip the * caching system * * @param a the first vector index * @param b the second vector index * @return the kernel evaluation of k(a, b) */ protected double k(int a, int b) { evalCount++; return kernel.eval(a, b, vecs, accelCache); } /** * Sparsifies the SVM by removing the vectors with α = 0 from the * dataset. */ protected void sparsify() { final int N = vecs.size(); int accSize = accelCache == null ? 0 : accelCache.size()/N; int svCount = 0; for(int i = 0; i < N; i++) if(alphas[i] != 0)//Its a support vector { ListUtils.swap(vecs, svCount, i); if(accelCache != null) for(int j = i*accSize; j < (i+1)*accSize; j++) ListUtils.swap(accelCache, svCount*accSize+j-i*accSize, j); alphas[svCount++] = alphas[i]; } vecs = new ArrayList(vecs.subList(0, svCount)); alphas = Arrays.copyOfRange(alphas, 0, svCount); } }

Ads help maintain this website.