package jsat.distributions.kernels;

import static java.lang.Math.abs;
import static java.lang.Math.pow;
import java.util.*;
import static jsat.distributions.kernels.KernelPoint.getH;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.utils.DoubleList;
import jsat.utils.random.RandomUtil;

/**
 * This class represents a list of {@link KernelPoint} objects. This is done to 
 * avoid excessive memory duplication that can occur when multiple KernelPoints
 * are in use at the same time. 
 * 
 * @author Edward Raff
 */
public class KernelPoints
{
    private KernelTrick k;
    private double errorTolerance;
    private KernelPoint.BudgetStrategy budgetStrategy = KernelPoint.BudgetStrategy.PROJECTION;
    private int maxBudget = Integer.MAX_VALUE;
    private List points;
    
    /**
     * Creates a new set of kernel points that uses one unified gram matrix for 
     * each KernelPoint 
     * @param k the kernel trick to use in which to represent a vector in the 
     * kernel space
     * @param points the initial number of kernel points to store in this set
     * @param errorTolerance the maximum error allowed for projecting a vector 
     * instead of adding it to the basis set
     */
    public KernelPoints(KernelTrick k, int points, double errorTolerance)
    {
        this(k, points, errorTolerance, true);
    }

    /**
     * Creates a new set of kernel points
     * @param k the kernel trick to use in which to represent a vector in the 
     * kernel space
     * @param points the initial number of kernel points to store in this set
     * @param errorTolerance the maximum error allowed for projecting a vector 
     * instead of adding it to the basis set
     * @param mergeGrams whether or not to merge the gram matrices of each 
     * KernelPoint. 
     */
    public KernelPoints(KernelTrick k, int points, double errorTolerance, boolean mergeGrams)
    {
        if(points < 1)
            throw new IllegalArgumentException("Number of points must be positive, not " + points);
        this.k = k;
        this.errorTolerance = errorTolerance;
        this.points = new ArrayList(points);
        this.points.add(new KernelPoint(k, errorTolerance));
        this.points.get(0).setMaxBudget(maxBudget);
        this.points.get(0).setBudgetStrategy(budgetStrategy);
        for(int i = 1; i < points; i++)
            addNewKernelPoint();
    }

    /**
     * Copy constructor
     * @param toCopy the object to copy
     */
    public KernelPoints(KernelPoints toCopy)
    {
        this.k = toCopy.k.clone();
        this.errorTolerance = toCopy.errorTolerance;
        this.points = new ArrayList(toCopy.points.size());
        if(toCopy.points.get(0).getBasisSize() == 0)//special case, nothing has been added
        {
            for(int i = 0; i < toCopy.points.size(); i++)
                this.points.add(new KernelPoint(k, errorTolerance));
        }
        else
        {
            KernelPoint source = this.points.get(0).clone();
            for (int i = 1; i < toCopy.points.size(); i++)
            {
                KernelPoint toAdd = new KernelPoint(k, errorTolerance);
                standardMove(toAdd, source);
                toAdd.kernelAccel = source.kernelAccel;
                toAdd.vecs = source.vecs;
                toAdd.alpha = new DoubleList(toCopy.points.get(i).alpha);
            }
        }
    }

    /**
     * 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(KernelPoint.BudgetStrategy budgetStrategy) { this.budgetStrategy = budgetStrategy; for(KernelPoint kp : points) kp.setBudgetStrategy(budgetStrategy); } /** * Returns the budget method used * @return the budget method used */ public KernelPoint.BudgetStrategy getBudgetStrategy() { return budgetStrategy; } public KernelTrick getKernel() { return k; } /** * Sets the error tolerance used for projection maintenance strategies such * as {@link KernelPoint.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; for(KernelPoint kp : points) kp.setErrorTolerance(errorTolerance); } /** * Returns the error tolerance that is used depending on the * {@link KernelPoint.BudgetStrategy} in use * @return the error tolerance value */ public double getErrorTolerance() { return errorTolerance; } /** * 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; for(KernelPoint kp : points) kp.setMaxBudget(maxBudget); } /** * Returns the current maximum budget for support vectors * @return the maximum budget for support vectors */ public int getMaxBudget() { return maxBudget; } /** * Returns the squared 2 norm value of the {@code k}'th KernelPoint * @param k the KernelPoint to get the norm of * @return the squared 2 norm of the {@code k}'th KernelPoint */ public double getSqrdNorm(int k) { return points.get(k).getSqrdNorm(); } /** * Computes the dot product between the {@code k}'th KernelPoint and the * given vector in the kernel space. * @param k the index of the KernelPoint in this set to contribute to the * dot product * @param x the vector to contribute to the dot product * @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 between the {@code k}'th KernelPoint and the * given vector */ public double dot(int k, Vec x, List qi) { return points.get(k).dot(x, qi); } /** * Computes the dot product between each KernelPoint in this set and the * given vector in the kernel space. The results are equivalent to an array * and setting each value using * {@link #dot(int, jsat.linear.Vec, java.util.List) }
* This method should be faster than computing the dot products individual * since it avoids redundant kernel computations * * @param x the vector to contribute to the dot product * @param qi the query information for the vector, or {@code null} only if * the kernel in use does not support acceleration. * @return an array where the i'th index contains the dot product of * the i'th KernelPoint and the given vector */ public double[] dot(Vec x, List qi) { double[] dots = new double[points.size()]; final List vecs = points.get(0).vecs; final List cache = points.get(0).kernelAccel; for(int i = 0; i < vecs.size(); i++) { double k_ix = k.eval(i, x, qi, vecs, cache); for(int j = 0; j < points.size(); j++) { double alpha = points.get(j).alpha.getD(i); if(alpha != 0) dots[j] += k_ix*alpha; } } return dots; } /** * Computes the dot product between the {@code k}'th KernelPoint and the * given KernelPoint * @param k the index of the KernelPoint in this set to contribute to the * dot product * @param x the other KernelPoint to contribute to the dot product * @return the dot product between the {@code k}'th KernelPoint and the * given KernelPoint */ public double dot(int k, KernelPoint x) { return points.get(k).dot(x); } /** * Computes the dot product between the {@code k}'th KernelPoint and the * {@code j}'th KernelPoint in the given set of points. * @param k the index of the KernelPoint in this set to contribute to the * dot product * @param X the other set of KernelPoints * @param j the index of the KernelPoint in the given set to contribute to * the dot product * @return the dot product between the {@code k}'th KernelPoint and the * {@code j}'th KernelPoint in the given set */ public double dot(int k, KernelPoints X, int j) { return points.get(k).dot(X.points.get(j)); } /** * Computes the Euclidean distance in the kernel space between the * {@code k}'th KernelPoint and the given vector * @param k the index of the KernelPoint in this set to contribute to the * dot product * @param x the point to get the Euclidean distance to * @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 the {@code k}'th KernelPoint and * {@code x} in the kernel space */ public double dist(int k, Vec x, List qi) { return points.get(k).dist(x, qi); } /** * Computes the Euclidean distance in the kernel space between the * {@code k}'th KernelPoint and the given KernelPoint * @param k the index of the KernelPoint in this set to contribute to the * dot product * @param x the kernel point to get the Euclidean distance to * @return the Euclidean distance between the {@code k}'th KernelPoint and * {@code x} in the kernel space */ public double dist(int k, KernelPoint x) { return points.get(k).dist(x); } /** * Computes the Euclidean distance in the kernel space between the * {@code k}'th KernelPoint and the {@code j}'th KernelPoint in the given * set * * @param k the index of the KernelPoint in this set to contribute to the * dot product * @param X the other set of kernel points to obtain the target KernelPoint * @param j the index of the KernelPoint in the given set to contribute to * the dot product * @return the Euclidean distance between the {@code k}'th KernelPoint and * the {@code j}'th KernelPoint in the other set */ public double dist(int k, KernelPoints X, int j) { return points.get(k).dist(X.points.get(j)); } /** * Alters the {@code k}'th KernelPoint by multiplying it with a constant * value * @param k the index of the KernelPoint to modify * @param c the constant to multiply the KernelPoint by */ public void mutableMultiply(int k, double c) { points.get(k).mutableMultiply(c); } /** * Alters all the KernelPoint objects contained in this set by the same * constant value * @param c the constant to multiply the KernelPoints by */ public void mutableMultiply(double c) { for(KernelPoint kp : points) kp.mutableMultiply(c); } /** * Alters ones of the KernelPoint objects by adding / subtracting a vector * from it * @param k the index of the KernelPoint to use * @param c the constant to multiply the vector being added by * @param x_t the vector to add to the kernel point * @param qi the query information for the vector, or {@code null} only if * the kernel in use does not support acceleration. */ public void mutableAdd(int k, double c, Vec x_t, final List qi) { } /** * Alters some of the KernelPoints by adding / subtracting a vector from it * @param x_t the vector to add to the kernel point * @param cs the array with the constant multiplies. Each non zero in * {@code cs} is a constant to update one of the vectors by. The vector * updated is the one corresponding to the index of the non zero value * @param qi the query information for the vector, or {@code null} only if * the kernel in use does not support acceleration. */ public void mutableAdd(Vec x_t, Vec cs, final List qi) { int origSize = getBasisSize(); if(cs.nnz() == 0) return; if(budgetStrategy == KernelPoint.BudgetStrategy.PROJECTION) { for(IndexValue iv : cs) { int k = iv.getIndex(); KernelPoint kp_k = points.get(k); double c = iv.getValue(); if(kp_k.getBasisSize() == 0)//Special case, init people { kp_k.mutableAdd(c, x_t, qi); //That initializes the structure, now we need to make people point to the same ones for(int i = 0; i < points.size(); i++) { if(i == k) continue; KernelPoint kp_i = points.get(i); standardMove(kp_i, kp_k); //Only done one time since structures are mutable kp_i.kernelAccel = kp_k.kernelAccel; kp_i.vecs = kp_k.vecs; //and then everyone gets their own private alphas added too kp_i.alpha = new DoubleList(16); kp_i.alpha.add(0.0); } } else//standard case { kp_k.mutableAdd(c, x_t, qi); if(origSize != kp_k.getBasisSize())//update kernels & add alpha { for(int i = 0; i < points.size(); i++) if(i != k) { KernelPoint kp_i = points.get(i); standardMove(kp_i, kp_k); kp_i.alpha.add(0.0); } } } origSize = getBasisSize();//may have changed, but only once } } else if (budgetStrategy == KernelPoint.BudgetStrategy.MERGE_RBF) { Iterator cIter = cs.getNonZeroIterator(); if (getBasisSize() < maxBudget) { IndexValue firstIndx = cIter.next(); KernelPoint kp_k = points.get(firstIndx.getIndex()); kp_k.mutableAdd(firstIndx.getValue(), x_t, qi); //fill in the non zeros while (cIter.hasNext()) { IndexValue iv = cIter.next(); points.get(iv.getIndex()).alpha.add(iv.getValue()); } addMissingZeros(); } else//we are going to exceed the budget { KernelPoint kp_k = points.get(0); //inser the new vector before merging kp_k.vecs.add(x_t); if (kp_k.kernelAccel != null) kp_k.kernelAccel.addAll(qi); for (IndexValue iv : cs) points.get(iv.getIndex()).alpha.add(iv.getValue()); addMissingZeros(); //now go through and merge /* * 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 = 0; for (KernelPoint kp : points) alpha_m += pow(kp.alpha.getD(m), 2); for (int i = 1; i < kp_k.alpha.size(); i++) { double tmp = 0; for (KernelPoint kp : points) tmp += pow(kp.alpha.getD(i), 2); if (tmp < alpha_m) { alpha_m = tmp; m = i; } } double minLoss = Double.POSITIVE_INFINITY; int n = -1; double n_h = 0; double tol = 1e-3; double n_k_mz = 0; double n_k_nz = 0; while (n == -1) { for (int i = 0; i < kp_k.alpha.size(); i++) { if (i == m) continue; double a_m = 0, a_n = 0; for (KernelPoint kp : points) { double a1 = kp.alpha.getD(m); double a2 = kp.alpha.getD(i); double normalize = a1 + a2; if (normalize < 1e-7) continue; a_m += a1 / normalize; a_n += a2 / normalize; } if (abs(a_m + a_n) < tol)//avoid alphas that nearly cancle out break; double k_mn = this.k.eval(i, m, kp_k.vecs, kp_k.kernelAccel); double h = getH(k_mn, a_m, a_n); /* * 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? double loss = 0; /* * Determin the best by the smallest change in norm, 2x2 * matrix for the original alphs and alpha_z on its own */ for (KernelPoint kp : points) { double aml = kp.alpha.getD(m); double anl = kp.alpha.getD(i); double alpha_z = aml * k_mz + anl * k_nz; loss += aml * aml + anl * anl + 2 * k_mn * aml * anl - alpha_z * alpha_z; } if (loss < minLoss) { minLoss = loss; n = i; n_h = h; n_k_mz = k_mz; n_k_nz = k_nz; } } tol /= 10; } Vec n_z = kp_k.vecs.get(m).multiply(n_h); n_z.mutableAdd(1 - n_h, kp_k.vecs.get(n)); final List nz_qi = this.k.getQueryInfo(n_z); for (int z = 0; z < points.size(); z++) { KernelPoint kp = points.get(z); double aml = kp.alpha.getD(m); double anl = kp.alpha.getD(n); double alpha_z = aml * n_k_mz + anl * n_k_nz; kp.finalMergeStep(m, n, n_z, nz_qi, alpha_z, z == 0); } } } else if (budgetStrategy == KernelPoint.BudgetStrategy.STOP) { if(getBasisSize() < maxBudget) { this.points.get(0).vecs.add(x_t); if(this.points.get(0).kernelAccel != null) this.points.get(0).kernelAccel.addAll(qi); for(IndexValue iv : cs) this.points.get(iv.getIndex()).alpha.add(iv.getValue()); addMissingZeros(); } } else if(budgetStrategy == KernelPoint.BudgetStrategy.RANDOM) { if(getBasisSize() >= maxBudget) { int toRemove = RandomUtil.getRandom().nextInt(getBasisSize()); if (getBasisSize() == maxBudget) this.points.get(0).removeIndex(toRemove);//now remove alpha from others for (int i = 1; i < this.points.size(); i++) this.points.get(i).removeIndex(toRemove); } //now add the point this.points.get(0).vecs.add(x_t); if (this.points.get(0).kernelAccel != null) this.points.get(0).kernelAccel.addAll(qi); for (IndexValue iv : cs) this.points.get(iv.getIndex()).alpha.add(iv.getValue()); addMissingZeros(); } else throw new RuntimeException("BUG: Report Me!"); } /** * Adds a new Kernel Point to the internal list this object represents. The * new Kernel Point will be equivalent to creating a new KernelPoint * directly. */ public void addNewKernelPoint() { KernelPoint source = points.get(0); KernelPoint toAdd = new KernelPoint(k, errorTolerance); toAdd.setMaxBudget(maxBudget); toAdd.setBudgetStrategy(budgetStrategy); standardMove(toAdd, source); toAdd.kernelAccel = source.kernelAccel; toAdd.vecs = source.vecs; toAdd.alpha = new DoubleList(source.alpha.size()); for (int i = 0; i < source.alpha.size(); i++) toAdd.alpha.add(0.0); points.add(toAdd); } /** * Updates the gram matrix storage of the destination to point at the exact * same objects as the ones from the source. * @param destination the destination object * @param source the source object */ private void standardMove(KernelPoint destination, KernelPoint source) { destination.InvK = source.InvK; destination.InvKExpanded = source.InvKExpanded; destination.K = source.K; destination.KExpanded = source.KExpanded; } /** * Returns the number of basis vectors in use. * If a vector has been added to more than one * Kernel Point it may get double counted (or more), so the value returned * may not be reasonable in that case. * @return the number of basis vectors in use */ public int getBasisSize() { return this.points.get(0).getBasisSize(); } /** * Returns a list of the raw vectors being used by the kernel points. * Altering this vectors will alter the same vectors used by these objects * and will cause inconsistent results. * * @return the list of raw basis vectors used by the Kernel points */ public List getRawBasisVecs() { List vecs = new ArrayList(getBasisSize()); vecs.addAll(this.points.get(0).vecs); return vecs; } /** * Returns the number of KernelPoints stored in this set * @return the number of KernelPoints stored in this set */ public int size() { return points.size(); } @Override public KernelPoints clone() { return new KernelPoints(this); } /** * Adds zeros to all alpha vecs that are not of the same length as the * vec list */ private void addMissingZeros() { //go back and add 0s for the onces we missed for (int i = 0; i < points.size(); i++) while(points.get(i).alpha.size() < this.points.get(0).vecs.size()) points.get(i).alpha.add(0.0); } }

Ads help maintain this website.