package jsat.regression;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.DataPoint;
import jsat.distributions.kernels.KernelTrick;
import jsat.linear.*;
import jsat.parameters.Parameter;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
/**
* Provides an implementation of the Kernel Recursive Least Squares algorithm.
* This algorithm updates the model one per data point, and induces sparsity by
* projecting data points down onto a set of basis vectors learned from the data
* stream.
*
* See: Engel, Y., Mannor, S.,&Meir, R. (2004). The Kernel Recursive
* Least-Squares Algorithm. IEEE Transactions on Signal Processing, 52(8),
* 2275–2285. doi:10.1109/TSP.2004.830985
*
* @author Edward Raff
*/
public class KernelRLS implements UpdateableRegressor, Parameterized
{
private static final long serialVersionUID = -7292074388953854317L;
@ParameterHolder
private KernelTrick k;
private double errorTolerance;
private List vecs;
private List kernelAccel;
private Matrix K;
private Matrix InvK;
private Matrix P;
private Matrix KExpanded;
private Matrix InvKExpanded;
private Matrix PExpanded;
private double[] alphaExpanded;
/**
* Creates a new Kernel RLS learner
* @param k the kernel trick to use
* @param errorTolerance the tolerance for errors in the projection
*/
public KernelRLS(KernelTrick k, double errorTolerance)
{
this.k = k;
setErrorTolerance(errorTolerance);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
protected KernelRLS(KernelRLS toCopy)
{
this.k = toCopy.k.clone();
this.errorTolerance = toCopy.errorTolerance;
if(toCopy.vecs != null)
{
this.vecs = new ArrayList(toCopy.vecs.size());
for(Vec vec : toCopy.vecs)
this.vecs.add(vec.clone());
}
if(toCopy.KExpanded != null)
{
this.KExpanded = toCopy.KExpanded.clone();
this.K = new SubMatrix(KExpanded, 0, 0, vecs.size(), vecs.size());
}
if(toCopy.InvKExpanded != null)
{
this.InvKExpanded = toCopy.InvKExpanded.clone();
this.InvK = new SubMatrix(InvKExpanded, 0, 0, vecs.size(), vecs.size());
}
if(toCopy.PExpanded != null)
{
this.PExpanded = toCopy.PExpanded.clone();
this.P = new SubMatrix(PExpanded, 0, 0, vecs.size(), vecs.size());
}
if(toCopy.alphaExpanded != null)
this.alphaExpanded = Arrays.copyOf(toCopy.alphaExpanded, toCopy.alphaExpanded.length);
}
/**
* Sets the tolerance for errors in approximating a data point by projecting
* it onto the set of basis vectors. In general: as the tolerance increases
* the sparsity of the model increases but the accuracy may go down.
*
* Values in the range 10x ∀ x ∈ {-1, -2, -3, -4}
* often work well for this algorithm.
*
* @param v the approximation tolerance
*/
public void setErrorTolerance(double v)
{
if(Double.isNaN(v) || Double.isInfinite(v) || v <= 0)
throw new IllegalArgumentException("The error tolerance must be a positive constant, not " + v);
this.errorTolerance = v;
}
/**
* Returns the projection approximation tolerance
* @return the projection approximation tolerance
*/
public double getErrorTolerance()
{
return errorTolerance;
}
/**
* Returns the number of basis vectors that make up the model
* @return the number of basis vectors that make up the model
*/
public int getModelSize()
{
if(vecs == null)
return 0;
return vecs.size();
}
/**
* Finalizes the model. During online training, the the gram matrix and its
* inverse must be stored to perform updates, at the cost of
* O(n2) memory. One training is completed, these matrices are no
* longer needed - and can be removed to reclaim memory by finalizing the
* model. Once finalized, the model can no longer be updated - unless reset
* (destroying the model) by calling
* {@link #setUp(jsat.classifiers.CategoricalData[], int) }
*/
public void finalizeModel()
{
alphaExpanded = Arrays.copyOf(alphaExpanded, vecs.size());//dont need extra
K = KExpanded = InvK = InvKExpanded = P = PExpanded = null;
}
@Override
public double regress(DataPoint data)
{
final Vec y = data.getNumericalValues();
return k.evalSum(vecs, kernelAccel, alphaExpanded, y, 0, vecs.size());
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(RegressionDataSet dataSet)
{
setUp(dataSet.getCategories(), dataSet.getNumNumericalVars());
IntList randOrder = new IntList(dataSet.getSampleSize());
ListUtils.addRange(randOrder, 0, dataSet.getSampleSize(), 1);
for(int i : randOrder)
update(dataSet.getDataPoint(i), dataSet.getTargetValue(i));
}
@Override
public boolean supportsWeightedData()
{
return false;
}
@Override
public KernelRLS clone()
{
return new KernelRLS(this);
}
@Override
public void setUp(CategoricalData[] categoricalAttributes, int numericAttributes)
{
vecs = new ArrayList();
if(k.supportsAcceleration())
kernelAccel = new DoubleList();
else
kernelAccel = null;
K = null;
InvK = null;
P = null;
KExpanded = new DenseMatrix(100, 100);
InvKExpanded = new DenseMatrix(100, 100);
PExpanded = new DenseMatrix(100, 100);
alphaExpanded = new double[100];
}
@Override
public void update(DataPoint dataPoint, final double y_t)
{
/*
* TODO a lot of temporary allocations are done in this code, but
* potentially change size - investigate storing them as well.
*/
Vec x_t = dataPoint.getNumericalValues();
final List qi = k.getQueryInfo(x_t);
final double k_tt = k.eval(0, 0, Arrays.asList(x_t), qi);
if(K == null)//first point to be added
{
K = new SubMatrix(KExpanded, 0, 0, 1, 1);
K.set(0, 0, k_tt);
InvK = new SubMatrix(InvKExpanded, 0, 0, 1, 1);
InvK.set(0, 0, 1/k_tt);
P = new SubMatrix(PExpanded, 0, 0, 1, 1);
P.set(0, 0, 1);
alphaExpanded[0] = y_t/k_tt;
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();
final double alphaConst = kxt.dot(new DenseVector(alphaExpanded, 0, size));
if(delta_t > errorTolerance)//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);
PExpanded.changeSize(size*2, size*2);
alphaExpanded = Arrays.copyOf(alphaExpanded, 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);
P = new SubMatrix(PExpanded, 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);
//P is zeros, no change
}
//update bottom right corner
K.set(size, size, k_tt);
InvK.set(size, size, 1/delta_t);
P.set(size, size, 1.0);
for(int i = 0; i < size; i++)
alphaExpanded[i] -= alphas_t.get(i)*(y_t-alphaConst)/delta_t;
alphaExpanded[size] = (y_t-alphaConst)/delta_t;
}
else//project onto dictionary
{
Vec q_t =P.multiply(alphas_t);
q_t.mutableDivide(1+alphas_t.dot(q_t));
Matrix.OuterProductUpdate(P, q_t, alphas_t.multiply(P), -1);
Vec InvKqt = InvK.multiply(q_t);
for(int i = 0; i < size; i++)
alphaExpanded[i] += InvKqt.get(i)*(y_t-alphaConst);
}
}
}
Ads help maintain this website.