package jsat.linear;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* This class is used to create an implicit representation of the degree 2
* polynomial of an input vector, with an implicit bias term added so that the
* original vector values are present in the implicit vector. This means no
* extra memory will be allocated, and all values accessed will be re-computed
* as needed. This works with sparse vectors, and work bet with algorithms that
* iterate over the nonzero values once.
*
* Any change in the base vector will change the values in this vector. Because
* changing one value in the base effects multiple values in this one, altering
* this vector directly is not allowed.
*
* If the base vector has {@code N} non zero values, then this vec will have
* O(N2) non zero values. (N+2)(N+1)/2 non zero values to be exact.
*
* @author Edward Raff
*/
public class Poly2Vec extends Vec
{
private static final long serialVersionUID = -5653680966558726340L;
private Vec base;
/**
* This maps values pas the original coefficients (and bias term) shifted to
* start from zero, to the appropriate value for the fist coefficient.
*
* This will be created lazily as needed. Call {@link #getReverseIndex() }
* to access this value
*/
private int[] reverseIndex;
public Poly2Vec(Vec base)
{
setBase(base);
}
/*
* Some math needed for this class to make sense. Given an input we want to poly 2 form plus a bias term. So for
* (x + y + z)
* we want
* (1 + x+ y + z + x^2 + x y + x z + y^2 + y z + z^2)
*
* Then for an input of size N, the poly 2 version has length (N+2)(N+1)/2
*
* The bias term and maintaining the original is easy. So lets assume we
* only want to get the value for the x^2 term and after. IE: given a term x
* and y, give me the index of the coeff that contains their product. Let x
* start from 0 and let x^2 also start from zero, so we map from one space
* to the other.
*
* The exact index location, when x <= y, is then x N + y - x (x+1) / 2
*
*/
/**
* Creates a new vector that implicitly represents the degree 2 polynomial
* of the base vector.
*
* @param base the base vector
*/
public void setBase(Vec base)
{
this.base = base;
}
private int[] getReverseIndex()
{
if(reverseIndex != null && reverseIndex.length == base.length())
Arrays.fill(reverseIndex, 0);
else
reverseIndex = new int[base.length()];
reverseIndex[0] = base.length();
for(int i = 1; i < reverseIndex.length; i++)
reverseIndex[i] = reverseIndex[i-1]+(base.length()-i);
return reverseIndex;
}
@Override
public int length()
{
return (base.length()+2)*(base.length()+1)/2;
}
@Override
public int nnz()
{
return (base.nnz()+2)*(base.nnz()+1)/2;
}
@Override
public double get(int index)
{
if(index == 0)
return 1;
else if (index <= base.length())
return base.get(index-1);
else if (index >= length())
throw new IndexOutOfBoundsException("Vector is of length " + length() +", but index "+ index + " was requested");
int x = Arrays.binarySearch(getReverseIndex(), index-base.length()-1);
if(x < 0)
x = -x -1;
else
x++;
double xVal = base.get(x);
int y = (x*x+x)/2 + (index-base.length()-1) - base.length()*x;//the first term is safe b/c it will always be an even number before division
return xVal*base.get(y);
}
@Override
public void set(int index, double val)
{
throw new UnsupportedOperationException("Poly2Vec may not be altered");
}
@Override
public boolean isSparse()
{
return base.isSparse();
}
@Override
public Vec clone()
{
return new Poly2Vec(base.clone());
}
@Override
public Iterator getNonZeroIterator(int start)
{
//First case: empty base vector
if (base.nnz() == 0)
return new Iterator()
{
boolean hasNext = true;
@Override
public boolean hasNext()
{
return hasNext;
}
@Override
public IndexValue next()
{
if (!hasNext)
throw new NoSuchElementException("Iterator is empty");
hasNext = false;
return new IndexValue(0, 1.0);
}
@Override
public void remove()
{
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
};
//Else, general case
final int startStage;
final Iterator startOuterIter, startInerIter;
boolean stage1Good = true;//fail occurs when the last index (or more) in the base vector is zero
if(start == 0)
{
startStage = 0;
startInerIter = startOuterIter = null;
}
else if(start <= base.length() && (stage1Good=base.getNonZeroIterator(start-1).hasNext()))
{
startStage = 1;
startOuterIter = base.getNonZeroIterator(start-1);
startInerIter = null;
}
else if(start >= length())
{
startStage = 3;
startInerIter = startOuterIter = null;
}
else//where do we start?
{
if (!stage1Good)
start = base.length() + 1;
Iterator candidateOuterIter, candidateInerIter;
start--;//lazy ness so we can update first thing in each iteration (we dont actually want to change the first value in the looping
do
{
start++;
int x = Arrays.binarySearch(getReverseIndex(), start - base.length() - 1);
if (x < 0)
x = -x - 1;
else
x++;
int y = (x * x + x) / 2 + (start - base.length() - 1) - base.length() * x;//the first term is safe b/c it will always be an even number before division
candidateOuterIter = base.getNonZeroIterator(x);
/*
* If the x coefficeint is zero, we will jump to the next non
* zero x. This means y must change as well, so we will check if
* that has happened by grabbing another iterator to get the
* value. If this has happened, we know that y should be set to
* x's value
*/
int nextXIndex = candidateOuterIter.hasNext() ? base.getNonZeroIterator(x).next().getIndex() : -1;
if(candidateOuterIter.hasNext() && nextXIndex > x)//x is at a zero, so we need to inner iter to go back to the "begining"
candidateInerIter = base.getNonZeroIterator(nextXIndex);//next variable starts at val^2
else
candidateInerIter = base.getNonZeroIterator(y);
}
while ( (!candidateOuterIter.hasNext() || !candidateInerIter.hasNext()) && start < length());
if (candidateOuterIter.hasNext() && candidateInerIter.hasNext() && start < length())
{
startStage = 2;
startOuterIter = candidateOuterIter;
startInerIter = candidateInerIter;
}
else
return new Iterator()
{
@Override
public boolean hasNext()
{
return false;
}
@Override
public IndexValue next()
{
throw new NoSuchElementException("Iterator is empty");
}
@Override
public void remove()
{
throw new UnsupportedOperationException("Not supported yet.");
}
};
}
return new Iterator()
{
int stage = startStage;//0 is for bias, 1 is for stanrdard values, 2 is for combinations, 3 is for empty
Iterator outerIter = startOuterIter, inerIter = startInerIter;
IndexValue curOuterVal = inerIter != null ? outerIter.next() : null;
IndexValue toReturn = new IndexValue(0, 0);
@Override
public boolean hasNext()
{
if(stage < 3)
return true;
return false;
}
@Override
public IndexValue next()
{
if(stage == 0)
{
stage++;
outerIter = base.getNonZeroIterator();//we know its non empty b/c of first case
return new IndexValue(0, 1.0);
}
else if (stage == 1)//outerIter must always have a next item if stage = 1
{
IndexValue iv = outerIter.next();
if (!outerIter.hasNext())
{
stage++;
outerIter = base.getNonZeroIterator();
curOuterVal = outerIter.next();
inerIter = base.getNonZeroIterator();
}
toReturn.setIndex(1+iv.getIndex());
toReturn.setValue(iv.getValue());
return toReturn;
}
else if(stage == 2)
{
IndexValue innerVal = inerIter.next();
int x = curOuterVal.getIndex();
int y = innerVal.getIndex();
int N = base.length();
toReturn.setIndex(1+N+x*N+y-x*(x+1)/2);
toReturn.setValue(curOuterVal.getValue()*innerVal.getValue());
if(!inerIter.hasNext())
{
if(!outerIter.hasNext())//we are out!
{
stage++;
outerIter = inerIter = null;
}
else//Still at least one more round!
{
curOuterVal = outerIter.next();
//new inner itter starts at idx^2
inerIter = base.getNonZeroIterator(curOuterVal.getIndex());
}
}
return toReturn;
}
else //stage >= 3
throw new NoSuchElementException("Iterator is empty");
}
@Override
public void remove()
{
throw new UnsupportedOperationException("Not supported yet.");
}
};
}
}
Ads help maintain this website.