package jsat.distributions.kernels;

import static java.lang.Math.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import jsat.classifiers.linear.kernelized.Projectron;
import jsat.linear.*;
import jsat.math.FastMath;
import jsat.math.Function;
import jsat.math.Function1D;
import jsat.math.optimization.GoldenSearch;
import jsat.regression.KernelRLS;
import jsat.utils.DoubleList;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;

/**
 * The Kernel Point represents a kernelized weight vector by a linear 
 * combination of vectors transformed through a 
 * {@link KernelTrick kernel fuctiion}. This implementation allows the selection
 * of multiple different budget maintenance strategies 
*
* See {@link KernelRLS} and {@link Projectron} for methods and papers based on * the same ideas used to create this class.
* Credit goes to Davis King of the dlib * library for the idea of this type of class.
*
* Changing the * {@link #setBudgetStrategy(jsat.distributions.kernels.KernelPoint.BudgetStrategy) * budget maintinance method} or other parameters should be done before * adding any data points to the KernelPoint.
* If a maximum budget is specified, it may always be increased - but may not be * decreased. * * @author Edward Raff */ public class KernelPoint { protected KernelTrick k; private double errorTolerance; protected List vecs; protected List kernelAccel; protected Matrix K; protected Matrix InvK; protected Matrix KExpanded; protected Matrix InvKExpanded; protected DoubleList alpha; protected BudgetStrategy budgetStrategy = BudgetStrategy.PROJECTION; protected int maxBudget = Integer.MAX_VALUE; /** * These enums control the method used to reduce the size of the support * vector set in the kernel point. */ public enum BudgetStrategy { /** * The budget is maintained by projecting the incoming vector onto * the set of current vectors. If the error in the projection is less * than {@link #setErrorTolerance(double) } the projection is used, and * the input is added to the support vector set if the error was too * large.
* Once the maximum budget size is reached, the projection is used * regardless of the error of the projection.
*
* The time complexity of each update is O(B2) and * uses O(B2) memory. * */ PROJECTION, /** * The budget is maintained by merging two support vectors to minimize * the error in the squared norm. The merged support vector is not a * member of the training set. This method is only valid for the * {@link RBFKernel} . Using any other kernel may cause invalid * results
*
* See:
*
    *
  • Wang, Z., Crammer, K.,&Vucetic, S. (2012). Breaking the * Curse of Kernelization : Budgeted Stochastic Gradient Descent for * Large-Scale SVM Training. The Journal of Machine Learning * Research, 13(1), 3103–3131.
  • *
  • Wang, Z., Crammer, K.,&Vucetic, S. (2010). Multi-class * pegasos on a budget. In 27th International Conference on Machine * Learning (pp. 1143–1150). Retrieved from * * here
  • *
*
* The time complexity of each update is O(B) and * uses O(B) memory. */ MERGE_RBF, /** * The budget is maintained by refusing to add new data points once the * budget is reached.
*
* The time complexity of each update is O(B) and * uses O(B) memory. */ STOP, /** * The budget is maintained by randomly dropping a previous support * vector.
*
* The time complexity of each update is O(B) and * uses O(B) memory. */ RANDOM, } //Internal structure private double sqrdNorm = 0; private boolean normGood = true; /** * Creates a new Kernel Point, which is a point in the kernel space * represented by an accumulation of vectors and uses the * {@link BudgetStrategy#PROJECTION} strategy with an unbounded maximum * budget * * @param k the kernel to use * @param errorTolerance the maximum error in [0, 1] allowed for projecting * a vector instead of adding it to the basis set */ public KernelPoint(KernelTrick k, double errorTolerance) { this.k = k; setErrorTolerance(errorTolerance); setBudgetStrategy(BudgetStrategy.PROJECTION); setMaxBudget(Integer.MAX_VALUE); if(k.supportsAcceleration()) kernelAccel = new DoubleList(16); alpha = new DoubleList(16); vecs = new ArrayList(16); } /** * Copy constructor * @param toCopy the object to copy */ public KernelPoint(KernelPoint toCopy) { this.k = toCopy.k.clone(); this.errorTolerance = toCopy.errorTolerance; if(toCopy.vecs != null) { this.vecs = new ArrayList(toCopy.vecs.size()); for(Vec v : toCopy.vecs) this.vecs.add(v.clone()); if(toCopy.kernelAccel != null) this.kernelAccel = new DoubleList(toCopy.kernelAccel); this.alpha = new DoubleList(toCopy.alpha); } if(toCopy.KExpanded != null) { this.KExpanded = toCopy.KExpanded.clone(); this.InvKExpanded = toCopy.InvKExpanded.clone(); this.K = new SubMatrix(KExpanded, 0, 0, toCopy.K.rows(), toCopy.K.cols()); this.InvK = new SubMatrix(InvKExpanded, 0, 0, toCopy.InvK.rows(), toCopy.InvK.rows()); } this.maxBudget = toCopy.maxBudget; this.sqrdNorm = toCopy.sqrdNorm; this.normGood = toCopy.normGood; } /** * Sets the maximum budget for support vectors to allow. Setting to * {@link Integer#MAX_VALUE} is essentially an unbounded number of support * vectors. Increasing the budget after adding the first vector is always * allowed, but it may not be possible to reduce the number of current * support vectors is above the desired budget. * * @param maxBudget the maximum number of allowed support vectors */ public void setMaxBudget(int maxBudget) { if(maxBudget < 1) throw new IllegalArgumentException("Budget must be positive, not " + maxBudget); this.maxBudget = maxBudget; } /** * Returns the current maximum budget for support vectors * @return the maximum budget for support vectors */ public int getMaxBudget() { return maxBudget; } /** * Sets the method used for maintaining the budget of support vectors. This * method must be called before any vectors are added to the * KernelPoint.
*
* The budget maintenance strategy used controls the time complexity and * memory use of the model. * @param budgetStrategy the budget maintenance strategy */ public void setBudgetStrategy(BudgetStrategy budgetStrategy) { if(getBasisSize() > 0) throw new RuntimeException("KerenlPoint already started, budget may not be changed"); this.budgetStrategy = budgetStrategy; } /** * Returns the budget method used * @return the budget method used */ public BudgetStrategy getBudgetStrategy() { return budgetStrategy; } /** * Sets the error tolerance used for projection maintenance strategies such * as {@link BudgetStrategy#PROJECTION} * @param errorTolerance the error tolerance in [0, 1] */ public void setErrorTolerance(double errorTolerance) { if(Double.isNaN(errorTolerance) || errorTolerance < 0 || errorTolerance > 1) throw new IllegalArgumentException("Error tolerance must be in [0, 1], not " + errorTolerance); this.errorTolerance = errorTolerance; } /** * Returns the error tolerance that is used depending on the * {@link BudgetStrategy} in use * @return the error tolerance value */ public double getErrorTolerance() { return errorTolerance; } /** * Returns the squared values of the 2 norm of the point this object * represents * * @return the squared value of the 2 norm */ public double getSqrdNorm() { if(!normGood) { sqrdNorm = 0; for(int i = 0; i < alpha.size(); i++) { if(K != null)//we already know all the values of K { sqrdNorm += alpha.get(i)*alpha.get(i)*K.get(i, i); for(int j = i+1; j < alpha.size(); j++) sqrdNorm += 2*alpha.get(i)*alpha.get(j)*K.get(i, j); } else//nope, compute as needed { sqrdNorm += alpha.get(i)*alpha.get(i)*k.eval(i, i, vecs, kernelAccel); for(int j = i+1; j < alpha.size(); j++) sqrdNorm += 2*alpha.get(i)*alpha.get(j)*k.eval(i, j, vecs, kernelAccel); } } normGood = true; } return sqrdNorm; } /** * Computes the dot product between the kernel point this object represents * and the given input vector in the kernel space. * * @param x the input vector to work with * @return the dot product in the kernel space between this point and {@code x} */ public double dot(Vec x) { return dot(x, k.getQueryInfo(x)); } /** * Computes the dot product between the kernel point this object represents * and the given input vector in the kernel space * * @param x the input vector to work with * @param qi the query information for the vector, or {@code null} only if * the kernel in use does not support acceleration. * @return the dot product in the kernel space between this point and {@code x} */ public double dot(Vec x, List qi) { if(getBasisSize() == 0) return 0; return k.evalSum(vecs, kernelAccel, alpha.getBackingArray(), x, qi, 0, alpha.size()); } /** * Returns the dot product between this point and another in the kernel * space * @param x the point to take the dot product with * @return the dot product in the kernel space between this point and {@code x} */ public double dot(KernelPoint x) { if(getBasisSize() == 0 || x.getBasisSize() == 0) return 0; int shift = this.alpha.size(); List mergedVecs = ListUtils.mergedView(this.vecs, x.vecs); List mergedCache; if(this.kernelAccel == null || x.kernelAccel == null) mergedCache = null; else mergedCache = ListUtils.mergedView(this.kernelAccel, x.kernelAccel); double dot = 0; for(int i = 0; i < this.alpha.size(); i++) for(int j = 0; j < x.alpha.size(); j++) { dot += this.alpha.get(i)*x.alpha.get(j)*k.eval(i, j+shift, mergedVecs, mergedCache); } return dot; } /** * Computes the Euclidean distance between this kernel point and the given * input in the kernel space * @param x the input vector to work with * @return the Euclidean distance between this point and {@code x} in the * kernel space */ public double dist(Vec x) { return dist(x, k.getQueryInfo(x)); } /** * Computes the Euclidean distance between this kernel point and the given * input in the kernel space * @param x the input vector to work with * @param qi the query information for the vector, or {@code null} only if * the kernel in use does not support acceleration. * @return the Euclidean distance between this point and {@code x} in the * kernel space */ public double dist(Vec x, List qi) { double k_xx = k.eval(0, 0, Arrays.asList(x), qi); return Math.sqrt(k_xx+getSqrdNorm()-2*dot(x, qi)); } /** * Computes the Euclidean distance between this kernel point and the given * kernel point in the kernel space * @param x the input point to work with * @return the Euclidean distance between this point and {@code x} in the * kernel space */ public double dist(KernelPoint x) { if(this == x)//dist to self is 0 return 0; double d = this.getSqrdNorm() + x.getSqrdNorm() - 2 * dot(x); return Math.sqrt(Math.max(0, d));//Avoid rare cases wehre 2*dot might be slightly larger } /** * Alters this point to be multiplied by the given value * @param c the value to multiply by */ public void mutableMultiply(double c) { if(Double.isNaN(c) || Double.isInfinite(c)) throw new IllegalArgumentException("multiplier must be a real value, not " + c); if(getBasisSize() == 0) return; sqrdNorm *= c*c; alpha.getVecView().mutableMultiply(c); } /** * Alters this point to contain the given input vector as well * @param x_t the vector to add */ public void mutableAdd(Vec x_t) { mutableAdd(1.0, x_t); } /** * Alters this point to contain the given input vector as well * @param c the multiplicative constant to apply with the vector * @param x_t the vector to add */ public void mutableAdd(double c, Vec x_t) { mutableAdd(c, x_t, k.getQueryInfo(x_t)); } /** * Alters this point to contain the given input vector as well * @param c the multiplicative constant to apply with the vector * @param x_t the vector to add * @param qi the query information for the vector, or {@code null} only if * the kernel in use does not support acceleration. */ public void mutableAdd(double c, Vec x_t, final List qi) { if(c == 0) return; normGood = false; double y_t = c; final double k_tt = k.eval(0, 0, Arrays.asList(x_t), qi); if(budgetStrategy == BudgetStrategy.PROJECTION) { if(K == null)//first point to be added { KExpanded = new DenseMatrix(16, 16); K = new SubMatrix(KExpanded, 0, 0, 1, 1); K.set(0, 0, k_tt); InvKExpanded = new DenseMatrix(16, 16); InvK = new SubMatrix(InvKExpanded, 0, 0, 1, 1); InvK.set(0, 0, 1/k_tt); alpha.add(y_t); vecs.add(x_t); if(kernelAccel != null) kernelAccel.addAll(qi); return; } //Normal case DenseVector kxt = new DenseVector(K.rows()); for (int i = 0; i < kxt.length(); i++) kxt.set(i, k.eval(i, x_t, qi, vecs, kernelAccel)); //ALD test final Vec alphas_t = InvK.multiply(kxt); final double delta_t = k_tt-alphas_t.dot(kxt); final int size = K.rows(); if(delta_t > errorTolerance && size < maxBudget)//add to the dictionary { vecs.add(x_t); if(kernelAccel != null) kernelAccel.addAll(qi); if(size == KExpanded.rows())//we need to grow first { KExpanded.changeSize(size*2, size*2); InvKExpanded.changeSize(size*2, size*2); } Matrix.OuterProductUpdate(InvK, alphas_t, alphas_t, 1/delta_t); K = new SubMatrix(KExpanded, 0, 0, size+1, size+1); InvK = new SubMatrix(InvKExpanded, 0, 0, size+1, size+1); //update bottom row and side columns for(int i = 0; i < size; i++) { K.set(size, i, kxt.get(i)); K.set(i, size, kxt.get(i)); InvK.set(size, i, -alphas_t.get(i)/delta_t); InvK.set(i, size, -alphas_t.get(i)/delta_t); } //update bottom right corner K.set(size, size, k_tt); InvK.set(size, size, 1/delta_t); alpha.add(y_t); } else//project onto dictionary { Vec alphaVec = alpha.getVecView(); alphaVec.mutableAdd(y_t, alphas_t); normGood = false; } } else if(budgetStrategy == BudgetStrategy.MERGE_RBF) { normGood = false; addPoint(x_t, qi, y_t); if(vecs.size() > maxBudget) { /* * we use the same approximation method as in projection * (Section 4.2) by fixing m as theSV with the smallest value * of || α_m ||^2 */ int m = 0; double alpha_m = abs(alpha.get(m)); for(int i = 1; i < alpha.size(); i++) if(abs(alpha.getD(i)) < abs(alpha_m)) { alpha_m = alpha.getD(i); m = i; } double minLoss = Double.POSITIVE_INFINITY; int n = -1; double n_h = 0; double n_alpha_z = 0; double tol = 1e-3; while (n == -1) { for (int i = 0; i < alpha.size(); i++) { if (i == m) continue; double a_m = alpha_m, a_n = alpha.getD(i); double normalize = a_m+a_n; if (abs(normalize) < tol)//avoid alphas that nearly cancle out continue; final double k_mn = k.eval(i, m, vecs, kernelAccel); double h = getH(k_mn, a_m/normalize, a_n/normalize); /* * we can get k(m, z) without forming z when using RBF * * exp(-(m-z)^2) = exp(-(m- (h m+(1-h) n))^2 ) = * exp(-(x-y)^2(h-1)^2) = exp((x-y)^2)^(h-1)^2 * * and since: 0 < h < 1 (h-1)^2 = (1-h)^2 */ double k_mz = pow(k_mn, (1 - h) * (1 - h)); double k_nz = pow(k_mn, h * h); //TODO should we fall back to forming z if we use a non RBF kernel? /* * Determin the best by the smallest change in norm, 2x2 * matrix for the original alphs and alpha_z on its own */ double alpha_z = a_m * k_mz + a_n * k_nz; double loss = a_m * a_m + a_n * a_n + 2 * k_mn * a_m * a_n - alpha_z*alpha_z; if (loss < minLoss) { minLoss = loss; n = i; n_h = h; n_alpha_z = alpha_z; } } tol /= 10; } Vec n_z = vecs.get(m).multiply(n_h); n_z.mutableAdd(1-n_h, vecs.get(n)); final List nz_qi = k.getQueryInfo(n_z); finalMergeStep(m, n, n_z, nz_qi, n_alpha_z, true); } } else if(budgetStrategy == BudgetStrategy.STOP) { normGood = false; if(getBasisSize() < maxBudget) addPoint(x_t, qi, y_t); } else if(budgetStrategy == BudgetStrategy.RANDOM) { normGood = false; if(getBasisSize() >= maxBudget) { Random rand = RandomUtil.getRandom();//TODO should probably move this out int toRemove = rand.nextInt(vecs.size()); removeIndex(toRemove); } addPoint(x_t, qi, y_t); } else throw new RuntimeException("BUG: report me!"); } /** * Adds a point to the set * @param x_t the value to add * @param qi the query information for the value * @param y_t the constant value to add */ private void addPoint(Vec x_t, final List qi, double y_t) { vecs.add(x_t); if (kernelAccel != null) kernelAccel.addAll(qi); alpha.add(y_t); } /** * Performs the last merging step removing the old vecs and adding the new * merged one * @param m the first of the original index to remove * @param n the second of the original index to remove * @param n_z the merged vec to replace them with * @param nz_qi the query info for the new vec * @param n_alpha_z the alpha value for the new merged vec */ protected void finalMergeStep(int m, int n, Vec n_z, final List nz_qi, double n_alpha_z, boolean alterVecs) { int smallIndx = min(m, n); int largeIndx = max(m, n); alpha.remove(largeIndx); alpha.remove(smallIndx); if(alterVecs) { vecs.remove(largeIndx); vecs.remove(smallIndx); kernelAccel.remove(largeIndx); kernelAccel.remove(smallIndx); vecs.add(n_z); //XXX the following check was redundant // if (kernelAccel != null) kernelAccel.addAll(nz_qi); } alpha.add(n_alpha_z); } /** * Gets the minimum of H in [0, 1] the for RBF merging
* amkmn(1-h)^2 + ankmnh^2 *
. * THIS METHOD IS A BOTTLE NECK, so it has some optimization hacks
* Only one of the coefficients can be negative. * @param k_mn the shared kernel value on both halves of the equation * @param a_m the first coefficient * @param a_n the second coefficient * @return the value of h that maximizes the response */ protected static double getH(final double k_mn, final double a_m, final double a_n) { if(a_m == a_n) return 0.5; final Function1D f = (double x) -> { final double h = x; //negative to maximize isntead of minimize /* * We aren't solving to a super high degree of accuracy anyway, * so use an approximate pow. Its impact is only noticible for * very small budget sizes */ return -(a_m * FastMath.pow(k_mn, (1 - h) * (1 - h)) + a_n * FastMath.pow(k_mn, h * h)); }; /* * Only a few iterations of golden search are done. Often the exact min * is very nearly 0 or 1, and that dosn't seem to really help with the * merging. I've gotten better generalization so far by allowing only a * small number of fininte steps. */ /* * if one is pos and the other is negative, the minimum value is going * to be near 0 or 1 */ if(Math.signum(a_m) != Math.signum(a_n)) if(a_m < 0)//we give a return GoldenSearch.minimize(1e-3, 100, 0.0, 0.2, f); else if(a_n < 0) return GoldenSearch.minimize(1e-3, 100, 0.8, 1.0, f); if(a_m > a_n) return GoldenSearch.minimize(1e-3, 100, 0.5, 1.0, f); else return GoldenSearch.minimize(1e-3, 100, 0.0, 0.5, f); } /** * Removes the vec, alpha, and kernel cache associate with the given index * @param toRemove the index to remove */ protected void removeIndex(int toRemove) { if(kernelAccel != null) { int num = this.kernelAccel.size()/vecs.size(); for(int i = 0; i < num; i++) kernelAccel.remove(toRemove); } alpha.remove(toRemove); vecs.remove(toRemove); } /** * Returns the number of vectors serving as the basis set * @return the number of vectors serving as the basis set */ public int getBasisSize() { if(vecs == null) return 0; return vecs.size(); } /** * Returns the list of the raw vectors being used by the kernel points. * Altering this vectors will alter the same vectors used by the KernelPoint * and will cause inconsistent results.
*
* The returned list may not be modified * * @return a the list of all the vectors in use as a basis set by this KernelPoint */ public List getRawBasisVecs() { return Collections.unmodifiableList(vecs); } @Override public KernelPoint clone() { return new KernelPoint(this); } }

Ads help maintain this website.