/**
* @file FastMinKernel.cpp
* @brief Efficient GPs with HIK for classification by regression (Implementation)
* @author Alexander Freytag
* @date 06-12-2011 (dd-mm-yyyy)
*/
// STL includes
#include <iostream>
// NICE-core includes
#include <core/basics/vectorio.h>
#include <core/basics/Timer.h>
// gp-hik-core includes
#include "FastMinKernel.h"
using namespace std;
using namespace NICE;
/* protected methods*/
/////////////////////////////////////////////////////
/////////////////////////////////////////////////////
// PUBLIC METHODS
/////////////////////////////////////////////////////
/////////////////////////////////////////////////////
FastMinKernel::FastMinKernel()
{
this->d = -1;
this->n = -1;
this->noise = 1.0;
approxScheme = MEDIAN;
verbose = false;
this->setDebug(false);
}
FastMinKernel::FastMinKernel( const std::vector<std::vector<double> > & X, const double noise, const bool _debug, const int & _dim)
{
this->setDebug(_debug);
this->hik_prepare_kernel_multiplications ( X, this->X_sorted, _dim);
this->d = X_sorted.get_d();
this->n = X_sorted.get_n();
this->noise = noise;
approxScheme = MEDIAN;
verbose = false;
}
#ifdef NICE_USELIB_MATIO
FastMinKernel::FastMinKernel ( const sparse_t & X, const double noise, const std::map<int, int> & examples, const bool _debug, const int & _dim) : X_sorted( X, examples, _dim )
{
this->d = X_sorted.get_d();
this->n = X_sorted.get_n();
this->noise = noise;
approxScheme = MEDIAN;
verbose = false;
this->setDebug(_debug);
}
#endif
FastMinKernel::FastMinKernel ( const std::vector< const NICE::SparseVector * > & X, const double noise, const bool _debug, const bool & dimensionsOverExamples, const int & _dim)
{
this->setDebug(_debug);
this->hik_prepare_kernel_multiplications ( X, this->X_sorted, dimensionsOverExamples, _dim);
this->d = X_sorted.get_d();
this->n = X_sorted.get_n();
this->noise = noise;
approxScheme = MEDIAN;
verbose = false;
}
FastMinKernel::~FastMinKernel()
{
}
///////////////////// ///////////////////// /////////////////////
// GET / SET
// INCLUDING ACCESS OPERATORS
///////////////////// ///////////////////// ////////////////////
int FastMinKernel::get_n() const
{
return n;
}
int FastMinKernel::get_d() const
{
return d;
}
double FastMinKernel::getSparsityRatio() const
{
return X_sorted.computeSparsityRatio();
}
void FastMinKernel::setVerbose( const bool & _verbose)
{
verbose = _verbose;
}
bool FastMinKernel::getVerbose( ) const
{
return verbose;
}
void FastMinKernel::setDebug( const bool & _debug)
{
debug = _debug;
X_sorted.setDebug( _debug );
}
bool FastMinKernel::getDebug( ) const
{
return debug;
}
///////////////////// ///////////////////// /////////////////////
// CLASSIFIER STUFF
///////////////////// ///////////////////// /////////////////////
void FastMinKernel::applyFunctionToFeatureMatrix ( const NICE::ParameterizedFunction *pf)
{
this->X_sorted.applyFunctionToFeatureMatrix(pf);
}
void FastMinKernel::hik_prepare_kernel_multiplications(const std::vector<std::vector<double> > & X, NICE::FeatureMatrixT<double> & X_sorted, const int & _dim)
{
X_sorted.set_features(X, _dim);
}
void FastMinKernel::hik_prepare_kernel_multiplications(const std::vector< const NICE::SparseVector * > & X, NICE::FeatureMatrixT<double> & X_sorted, const bool & dimensionsOverExamples, const int & _dim)
{
X_sorted.set_features(X, dimensionsOverExamples, _dim);
}
void FastMinKernel::hik_prepare_alpha_multiplications(const NICE::Vector & alpha, NICE::VVector & A, NICE::VVector & B) const
{
// std::cerr << "FastMinKernel::hik_prepare_alpha_multiplications" << std::endl;
// std::cerr << "alpha: " << alpha << std::endl;
A.resize(d);
B.resize(d);
// efficient calculation of k*alpha
// ---------------------------------
//
// sum_i alpha_i k(x^i,x) = sum_i alpha_i sum_k min(x^i_k,x_k)
// = sum_k sum_i alpha_i min(x^i_k, x_k)
//
// now let us define l_k = { i | x^i_k <= x_k }
// and u_k = { i | x^i_k > x_k }, this leads to
//
// = sum_k ( sum_{l \in l_k} alpha_l x^i_k + sum_{u \in u_k} alpha_u x_k
// = sum_k ( sum_{l \in l_k} \alpha_l x^l_k + x_k * sum_{u \in u_k}
// alpha_u
//
// We also define
// l^j_k = { i | x^i_j <= x^j_k } and
// u^j_k = { i | x^i_k > x^j_k }
//
// We now need the partial sums
//
// (Definition 1)
// a_{k,j} = \sum_{l \in l^j_k} \alpha_l x^l_k
//
// and \sum_{u \in u^j_k} \alpha_u
// according to increasing values of x^l_k
//
// With
// (Definition 2)
// b_{k,j} = \sum_{l \in l^j_k} \alpha_l,
//
// we get
// \sum_{u \in u^j_k} \alpha_u = \sum_{u=1}^n alpha_u - \sum_{l \in l^j_k} \alpha_l
// = b_{k,n} - b_{k,j}
// we only need as many entries as we have nonZero entries in our features for the corresponding dimensions
for (int i = 0; i < d; i++)
{
uint numNonZero = X_sorted.getNumberOfNonZeroElementsPerDimension(i);
//DEBUG
//std::cerr << "number of non-zero elements in dimension " << i << " / " << d << ": " << numNonZero << std::endl;
A[i].resize( numNonZero );
B[i].resize( numNonZero );
}
// for more information see hik_prepare_alpha_multiplications
for (int dim = 0; dim < d; dim++)
{
double alpha_sum(0.0);
double alpha_times_x_sum(0.0);
int cntNonzeroFeat(0);
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
// loop through all elements in sorted order
for ( SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin(); i != nonzeroElements.end(); i++ )
{
const SortedVectorSparse<double>::dataelement & de = i->second;
// index of the feature
int index = de.first;
// transformed element of the feature
//
double elem( de.second );
alpha_times_x_sum += alpha[index] * elem;
A[dim][cntNonzeroFeat] = alpha_times_x_sum;
alpha_sum += alpha[index];
B[dim][cntNonzeroFeat] = alpha_sum;
cntNonzeroFeat++;
}
}
// A.store(std::cerr);
// B.store(std::cerr);
}
double *FastMinKernel::hik_prepare_alpha_multiplications_fast(const NICE::VVector & A, const NICE::VVector & B, const Quantization & q, const ParameterizedFunction *pf ) const
{
//NOTE keep in mind: for doing this, we already have precomputed A and B using hik_prepare_alpha_multiplications!
// number of quantization bins
uint hmax = q.size();
// store (transformed) prototypes
double *prototypes = new double [ hmax ];
for ( uint i = 0 ; i < hmax ; i++ )
if ( pf != NULL ) {
// FIXME: the transformed prototypes could change from dimension to another dimension
// We skip this flexibility ...but it should be changed in the future
prototypes[i] = pf->f ( 1, q.getPrototype(i) );
} else {
prototypes[i] = q.getPrototype(i);
}
// creating the lookup table as pure C, which might be beneficial
// for fast evaluation
double *Tlookup = new double [ hmax * this->d ];
// std::cerr << "size of LUT: " << hmax * this->d << std::endl;
// sizeOfLUT = hmax * this->d;
// loop through all dimensions
for (int dim = 0; dim < this->d; dim++)
{
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n )
continue;
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin();
SortedVectorSparse<double>::const_elementpointer iPredecessor = nonzeroElements.begin();
// index of the element, which is always bigger than the current value fval
int index = 0;
// we use the quantization of the original features! the transformed feature were
// already used to calculate A and B, this of course assumes monotonic functions!!!
int qBin = q.quantize ( i->first );
// the next loop is linear in max(hmax, n)
// REMARK: this could be changed to hmax*log(n), when
// we use binary search
for (int j = 0; j < (int)hmax; j++)
{
double fval = prototypes[j];
double t;
if ( (index == 0) && (j < qBin) ) {
// current element is smaller than everything else
// resulting value = fval * sum_l=1^n alpha_l
t = fval*( B[dim][this->n-1 - nrZeroIndices] );
} else {
// move to next example, if necessary
while ( (j >= qBin) && ( index < (this->n-1-nrZeroIndices)) )
{
index++;
iPredecessor = i;
i++;
if ( i->first != iPredecessor->first )
qBin = q.quantize ( i->first );
}
// compute current element in the lookup table and keep in mind that
// index is the next element and not the previous one
//NOTE pay attention: this is only valid if we all entries are positiv! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
if ( (j >= qBin) && ( index==(this->n-1-nrZeroIndices) ) ) {
// the current element (fval) is equal or bigger to the element indexed by index
// in fact, the term B[dim][this->n-1-nrZeroIndices] - B[dim][index] is equal to zero and vanishes, which is logical, since all elements are smaller than j!
t = A[dim][index];// + fval*( B[dim][this->n-1-nrZeroIndices] - B[dim][index] );
} else {
// standard case
t = A[dim][index-1] + fval*( B[dim][this->n-1-nrZeroIndices] - B[dim][index-1] );
}
}
Tlookup[ dim*hmax + j ] = t;
}
}
delete [] prototypes;
return Tlookup;
}
double *FastMinKernel::hikPrepareLookupTable(const NICE::Vector & alpha, const Quantization & q, const ParameterizedFunction *pf ) const
{
// number of quantization bins
uint hmax = q.size();
// store (transformed) prototypes
double *prototypes = new double [ hmax ];
for ( uint i = 0 ; i < hmax ; i++ )
if ( pf != NULL ) {
// FIXME: the transformed prototypes could change from dimension to another dimension
// We skip this flexibility ...but it should be changed in the future
prototypes[i] = pf->f ( 1, q.getPrototype(i) );
} else {
prototypes[i] = q.getPrototype(i);
}
// creating the lookup table as pure C, which might be beneficial
// for fast evaluation
double *Tlookup = new double [ hmax * this->d ];
// sizeOfLUT = hmax * this->d;
// loop through all dimensions
for (int dim = 0; dim < this->d; dim++)
{
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n )
continue;
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
double alphaSumTotalInDim(0.0);
double alphaTimesXSumTotalInDim(0.0);
for ( SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin(); i != nonzeroElements.end(); i++ )
{
alphaSumTotalInDim += alpha[i->second.first];
alphaTimesXSumTotalInDim += alpha[i->second.first] * i->second.second;
}
SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin();
SortedVectorSparse<double>::const_elementpointer iPredecessor = nonzeroElements.begin();
// index of the element, which is always bigger than the current value fval
int index = 0;
// we use the quantization of the original features! Nevetheless, the resulting lookupTable is computed using the transformed ones
int qBin = q.quantize ( i->first );
double alpha_sum(0.0);
double alpha_times_x_sum(0.0);
double alpha_sum_prev(0.0);
double alpha_times_x_sum_prev(0.0);
for (uint j = 0; j < hmax; j++)
{
double fval = prototypes[j];
double t;
if ( (index == 0) && (j < (uint)qBin) ) {
// current element is smaller than everything else
// resulting value = fval * sum_l=1^n alpha_l
//t = fval*( B[dim][this->n-1 - nrZeroIndices] );
t = fval*alphaSumTotalInDim;
} else {
// move to next example, if necessary
while ( (j >= (uint)qBin) && ( index < (this->n-1-nrZeroIndices)) )
{
alpha_times_x_sum_prev = alpha_times_x_sum;
alpha_sum_prev = alpha_sum;
alpha_times_x_sum += alpha[i->second.first] * i->second.second; //i->dataElement.transformedFeatureValue
alpha_sum += alpha[i->second.first]; //i->dataElement.OrigIndex
index++;
iPredecessor = i;
i++;
if ( i->first != iPredecessor->first )
qBin = q.quantize ( i->first );
}
// compute current element in the lookup table and keep in mind that
// index is the next element and not the previous one
//NOTE pay attention: this is only valid if all entries are positiv! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
if ( (j >= (uint)qBin) && ( index==(this->n-1-nrZeroIndices) ) ) {
// the current element (fval) is equal or bigger to the element indexed by index
// in fact, the term B[dim][this->n-1-nrZeroIndices] - B[dim][index] is equal to zero and vanishes, which is logical, since all elements are smaller than j!
// double lastTermAlphaTimesXSum;
// double lastTermAlphaSum;
t = alphaTimesXSumTotalInDim;
} else {
// standard case
t = alpha_times_x_sum + fval*( alphaSumTotalInDim - alpha_sum );
}
}
Tlookup[ dim*hmax + j ] = t;
}
}
delete [] prototypes;
return Tlookup;
}
void FastMinKernel::hikUpdateLookupTable(double * T, const double & alphaNew, const double & alphaOld, const int & idx, const Quantization & q, const ParameterizedFunction *pf ) const
{
if (T == NULL)
{
fthrow(Exception, "FastMinKernel::hikUpdateLookupTable LUT not initialized, run FastMinKernel::hikPrepareLookupTable first!");
return;
}
// number of quantization bins
uint hmax = q.size();
// store (transformed) prototypes
double *prototypes = new double [ hmax ];
for ( uint i = 0 ; i < hmax ; i++ )
if ( pf != NULL ) {
// FIXME: the transformed prototypes could change from dimension to another dimension
// We skip this flexibility ...but it should be changed in the future
prototypes[i] = pf->f ( 1, q.getPrototype(i) );
} else {
prototypes[i] = q.getPrototype(i);
}
double diffOfAlpha(alphaNew - alphaOld);
// loop through all dimensions
for ( int dim = 0; dim < this->d; dim++ )
{
double x_i ( (X_sorted(dim,idx)) );
//TODO we could also check wether x_i < tol, if we would store the tol explicitely
if ( x_i == 0.0 ) //nothing to do in this dimension
continue;
//TODO we could speed up this by first doing a binary search for the position where the min changes, and then do two separate for-loops
for (uint j = 0; j < hmax; j++)
{
double fval;
int q_bin = q.quantize(x_i);
if ( q_bin > (int) j )
fval = prototypes[j];
else
fval = x_i;
T[ dim*hmax + j ] += diffOfAlpha*fval;
}
}
delete [] prototypes;
}
void FastMinKernel::hik_kernel_multiply(const NICE::VVector & A, const NICE::VVector & B, const NICE::Vector & alpha, NICE::Vector & beta) const
{
beta.resize(n);
beta.set(0.0);
// runtime is O(n*d), we do no benefit from an additional lookup table here
for (int dim = 0; dim < d; dim++)
{
// -- efficient sparse solution
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all values are zero in this dimension :) and we can simply ignore the feature
continue;
}
int cnt(0);
for ( multimap< double, SortedVectorSparse<double>::dataelement>::const_iterator i = nonzeroElements.begin(); i != nonzeroElements.end(); i++, cnt++)
{
const SortedVectorSparse<double>::dataelement & de = i->second;
uint feat = de.first;
int inversePosition = cnt;
double fval = de.second;
// in which position was the element sorted in? actually we only care about the nonzero elements, so we have to subtract the number of zero elements.
//NOTE pay attention: this is only valid if all entries are positiv! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
//we definitly know that this element exists in inversePermutation, so we have not to check wether find returns .end() or not
//int inversePosition(inversePermutation.find(feat)->second - nrZeroIndices);
// sum_{l \in L_k} \alpha_l x^l_k
//
// A is zero for zero feature values (x^l_k is zero for all l \in L_k)
double firstPart( A[dim][inversePosition] );
// sum_{u \in U_k} alpha_u
// B is not zero for zero feature values, but we do not
// have to care about them, because it is multiplied with
// the feature value
// DEBUG for Björns code
if ( (uint)dim >= B.size() )
fthrow(Exception, "dim exceeds B.size: " << dim << " " << B.size() );
if ( B[dim].size() == 0 )
fthrow(Exception, "B[dim] is empty");
if ( (n-1-nrZeroIndices < 0) || ((uint)(n-1-nrZeroIndices) >= B[dim].size() ) )
fthrow(Exception, "n-1-nrZeroIndices is invalid: " << n << " " << nrZeroIndices << " " << B[dim].size() << " d: " << d);
if ( inversePosition < 0 || (uint)inversePosition >= B[dim].size() )
fthrow(Exception, "inverse position is invalid: " << inversePosition << " " << B[dim].size() );
double secondPart( B[dim][n-1-nrZeroIndices] - B[dim][inversePosition]);
beta[feat] += firstPart + fval * secondPart; // i->elementpointer->dataElement->Value
}
}
//do we really want to considere noisy labels?
for (int feat = 0; feat < n; feat++)
{
beta[feat] += noise*alpha[feat];
}
}
void FastMinKernel::hik_kernel_multiply_fast(const double *Tlookup, const Quantization & q, const NICE::Vector & alpha, NICE::Vector & beta) const
{
beta.resize(n);
beta.set(0.0);
// runtime is O(n*d), we do no benefit from an additional lookup table here
for (int dim = 0; dim < d; dim++)
{
// -- efficient sparse solution
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
int cnt(0);
for ( multimap< double, SortedVectorSparse<double>::dataelement>::const_iterator i = nonzeroElements.begin(); i != nonzeroElements.end(); i++, cnt++)
{
const SortedVectorSparse<double>::dataelement & de = i->second;
uint feat = de.first;
uint qBin = q.quantize(i->first);
beta[feat] += Tlookup[dim*q.size() + qBin];
}
}
//do we really want to considere noisy labels?
for (int feat = 0; feat < n; feat++)
{
beta[feat] += noise*alpha[feat];
}
}
void FastMinKernel::hik_kernel_sum(const NICE::VVector & A, const NICE::VVector & B, const NICE::SparseVector & xstar, double & beta, const ParameterizedFunction *pf) const
{
// sparse version of hik_kernel_sum, no really significant changes,
// we are just skipping zero elements
beta = 0.0;
for (SparseVector::const_iterator i = xstar.begin(); i != xstar.end(); i++)
{
int dim = i->first;
double fval = i->second;
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all features are zero and let us ignore it completely
continue;
}
int position;
//where is the example x^z_i located in
//the sorted array? -> perform binary search, runtime O(log(n))
// search using the original value
X_sorted.findFirstLargerInDimension(dim, fval, position);
position--;
//NOTE again - pay attention! This is only valid if all entries are NOT negative! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
//sum_{l \in L_k} \alpha_l x^l_k
double firstPart(0.0);
//TODO in the "overnext" line there occurs the following error
// Invalid read of size 8
if (position >= 0)
firstPart = (A[dim][position-nrZeroIndices]);
// sum_{u \in U_k} alpha_u
// sum_{u \in U_k} alpha_u
// => double secondPart( B(dim, n-1) - B(dim, position));
//TODO in the next line there occurs the following error
// Invalid read of size 8
double secondPart( B[dim][n-1-nrZeroIndices]);
//TODO in the "overnext" line there occurs the following error
// Invalid read of size 8
if (position >= 0)
secondPart-= B[dim][position-nrZeroIndices];
if ( pf != NULL )
{
fval = pf->f ( dim, fval );
}
// but apply using the transformed one
beta += firstPart + secondPart* fval;
}
}
void FastMinKernel::hik_kernel_sum(const NICE::VVector & A, const NICE::VVector & B, const NICE::Vector & xstar, double & beta, const ParameterizedFunction *pf) const
{
beta = 0.0;
int dim ( 0 );
for (NICE::Vector::const_iterator i = xstar.begin(); i != xstar.end(); i++, dim++)
{
double fval = *i;
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all features are zero and let us ignore it completely
continue;
}
int position;
//where is the example x^z_i located in
//the sorted array? -> perform binary search, runtime O(log(n))
// search using the original value
X_sorted.findFirstLargerInDimension(dim, fval, position);
position--;
//NOTE again - pay attention! This is only valid if all entries are NOT negative! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
//sum_{l \in L_k} \alpha_l x^l_k
double firstPart(0.0);
//TODO in the "overnext" line there occurs the following error
// Invalid read of size 8
if (position >= 0)
firstPart = (A[dim][position-nrZeroIndices]);
// sum_{u \in U_k} alpha_u
// sum_{u \in U_k} alpha_u
// => double secondPart( B(dim, n-1) - B(dim, position));
//TODO in the next line there occurs the following error
// Invalid read of size 8
double secondPart( B[dim][n-1-nrZeroIndices]);
//TODO in the "overnext" line there occurs the following error
// Invalid read of size 8
if (position >= 0)
secondPart-= B[dim][position-nrZeroIndices];
if ( pf != NULL )
{
fval = pf->f ( dim, fval );
}
// but apply using the transformed one
beta += firstPart + secondPart* fval;
}
}
void FastMinKernel::hik_kernel_sum_fast(const double *Tlookup, const Quantization & q, const NICE::Vector & xstar, double & beta) const
{
beta = 0.0;
if ((int) xstar.size() != d)
{
fthrow(Exception, "FastMinKernel::hik_kernel_sum_fast sizes of xstar and training data does not match!");
return;
}
// runtime is O(d) if the quantizer is O(1)
for (int dim = 0; dim < d; dim++)
{
double v = xstar[dim];
uint qBin = q.quantize(v);
beta += Tlookup[dim*q.size() + qBin];
}
}
void FastMinKernel::hik_kernel_sum_fast(const double *Tlookup, const Quantization & q, const NICE::SparseVector & xstar, double & beta) const
{
beta = 0.0;
// sparse version of hik_kernel_sum_fast, no really significant changes,
// we are just skipping zero elements
// for additional comments see the non-sparse version of hik_kernel_sum_fast
// runtime is O(d) if the quantizer is O(1)
for (SparseVector::const_iterator i = xstar.begin(); i != xstar.end(); i++ )
{
int dim = i->first;
double v = i->second;
uint qBin = q.quantize(v);
beta += Tlookup[dim*q.size() + qBin];
}
}
double *FastMinKernel::solveLin(const NICE::Vector & y, NICE::Vector & alpha, const Quantization & q, const ParameterizedFunction *pf, const bool & useRandomSubsets, uint maxIterations, const int & _sizeOfRandomSubset, double minDelta, bool timeAnalysis) const
{
int sizeOfRandomSubset(_sizeOfRandomSubset);
bool verbose ( false );
bool verboseMinimal ( false );
// number of quantization bins
uint hmax = q.size();
NICE::Vector diagonalElements(y.size(),0.0);
X_sorted.hikDiagonalElements(diagonalElements);
diagonalElements += this->noise;
NICE::Vector pseudoResidual (y.size(),0.0);
NICE::Vector delta_alpha (y.size(),0.0);
double alpha_old;
double alpha_new;
double x_i;
// initialization
if (alpha.size() != y.size())
alpha.resize(y.size());
alpha.set(0.0);
double *Tlookup = new double [ hmax * this->d ];
if ( (hmax*this->d) <= 0 ) return Tlookup;
memset(Tlookup, 0, sizeof(Tlookup[0])*hmax*this->d);
uint iter;
Timer t;
if ( timeAnalysis )
t.start();
if (useRandomSubsets)
{
std::vector<int> indices(y.size());
for (uint i = 0; i < y.size(); i++)
indices[i] = i;
if (sizeOfRandomSubset <= 0)
sizeOfRandomSubset = y.size();
for ( iter = 1; iter <= maxIterations; iter++ )
{
NICE::Vector perm;
randomPermutation(perm,indices,sizeOfRandomSubset);
if ( timeAnalysis )
{
t.stop();
Vector r;
this->hik_kernel_multiply_fast(Tlookup, q, alpha, r);
r = r - y;
double res = r.normL2();
double resMax = r.normInf();
cerr << "SimpleGradientDescent: TIME " << t.getSum() << " " << res << " " << resMax << endl;
t.start();
}
for ( int i = 0; i < sizeOfRandomSubset; i++)
{
pseudoResidual(perm[i]) = -y(perm[i]) + (this->noise*alpha(perm[i]));
for (uint j = 0; j < (uint)this->d; j++)
{
x_i = X_sorted(j,perm[i]);
pseudoResidual(perm[i]) += Tlookup[j*hmax + q.quantize(x_i)];
}
//NOTE: this threshhold could also be a parameter of the function call
if ( fabs(pseudoResidual(perm[i])) > 1e-7 )
{
alpha_old = alpha(perm[i]);
alpha_new = alpha_old - (pseudoResidual(perm[i])/diagonalElements(perm[i]));
alpha(perm[i]) = alpha_new;
delta_alpha(perm[i]) = alpha_old-alpha_new;
this->hikUpdateLookupTable(Tlookup, alpha_new, alpha_old, perm[i], q, pf ); // works correctly
} else
{
delta_alpha(perm[i]) = 0.0;
}
}
// after this only residual(i) is the valid residual... we should
// really update the whole vector somehow
double delta = delta_alpha.normL2();
if ( verbose ) {
cerr << "FastMinKernel::solveLin: iteration " << iter << " / " << maxIterations << endl;
cerr << "FastMinKernel::solveLin: delta = " << delta << endl;
cerr << "FastMinKernel::solveLin: pseudo residual = " << pseudoResidual.scalarProduct(pseudoResidual) << endl;
}
if ( delta < minDelta )
{
if ( verbose )
cerr << "FastMinKernel::solveLin: small delta" << endl;
break;
}
}
}
else //don't use random subsets
{
for ( iter = 1; iter <= maxIterations; iter++ )
{
for ( uint i = 0; i < y.size(); i++ )
{
pseudoResidual(i) = -y(i) + (this->noise*alpha(i));
for (uint j = 0; j < (uint) this->d; j++)
{
x_i = X_sorted(j,i);
pseudoResidual(i) += Tlookup[j*hmax + q.quantize(x_i)];
}
//NOTE: this threshhold could also be a parameter of the function call
if ( fabs(pseudoResidual(i)) > 1e-7 )
{
alpha_old = alpha(i);
alpha_new = alpha_old - (pseudoResidual(i)/diagonalElements(i));
alpha(i) = alpha_new;
delta_alpha(i) = alpha_old-alpha_new;
this->hikUpdateLookupTable(Tlookup, alpha_new, alpha_old, i, q, pf ); // works correctly
} else
{
delta_alpha(i) = 0.0;
}
}
double delta = delta_alpha.normL2();
if ( verbose ) {
cerr << "FastMinKernel::solveLin: iteration " << iter << " / " << maxIterations << endl;
cerr << "FastMinKernel::solveLin: delta = " << delta << endl;
cerr << "FastMinKernel::solveLin: pseudo residual = " << pseudoResidual.scalarProduct(pseudoResidual) << endl;
}
if ( delta < minDelta )
{
if ( verbose )
cerr << "FastMinKernel::solveLin: small delta" << endl;
break;
}
}
}
if (verboseMinimal)
std::cerr << "FastMinKernel::solveLin -- needed " << iter << " iterations" << std::endl;
return Tlookup;
}
void FastMinKernel::randomPermutation(NICE::Vector & permutation, const std::vector<int> & oldIndices, const int & newSize) const
{
std::vector<int> indices(oldIndices);
int resultingSize (std::min((int) (oldIndices.size()),newSize) );
permutation.resize(resultingSize);
for (int i = 0; i < resultingSize; i++)
{
int newIndex(rand() % indices.size());
permutation[i] = indices[newIndex ];
indices.erase(indices.begin() + newIndex);
}
}
double FastMinKernel::getFrobNormApprox()
{
double frobNormApprox(0.0);
switch (approxScheme)
{
case MEDIAN:
{
//\| K \|_F^1 ~ (n/2)^2 \left( \sum_k \median_k \right)^2
//motivation: estimate half of the values in dim k to zero and half of them to the median (-> lower bound expectation)
for (int i = 0; i < d; i++)
{
double median = this->X_sorted.getFeatureValues(i).getMedian();
frobNormApprox += median;
}
frobNormApprox = fabs(frobNormApprox) * n/2.0;
break;
}
case EXPECTATION:
{
std::cerr << "EXPECTATION" << std::endl;
//\| K \|_F^1^2 ~ \sum K_{ii}^2 + (n^2 - n) \left( \frac{1}{3} \sum_k \left( 2 a_k + b_k \right) \right)
// with a_k = minimal value in dim k and b_k maximal value
//first term
NICE::Vector diagEl;
X_sorted.hikDiagonalElements(diagEl);
frobNormApprox += diagEl.normL2();
//second term
double secondTerm(0.0);
for (int i = 0; i < d; i++)
{
double minInDim;
minInDim = this->X_sorted.getFeatureValues(i).getMin();
double maxInDim;
maxInDim = this->X_sorted.getFeatureValues(i).getMax();
std::cerr << "min: " << minInDim << " max: " << maxInDim << std::endl;
secondTerm += 2.0*minInDim + maxInDim;
}
secondTerm /= 3.0;
secondTerm = pow(secondTerm, 2);
secondTerm *= (this->n * ( this->n - 1 ));
frobNormApprox += secondTerm;
frobNormApprox = sqrt(frobNormApprox);
break;
}
default:
{ //do nothing, approximate with zero :)
break;
}
}
return frobNormApprox;
}
void FastMinKernel::setApproximationScheme(const int & _approxScheme)
{
switch(_approxScheme)
{
case 0:
{
approxScheme = MEDIAN;
break;
}
case 1:
{
approxScheme = EXPECTATION;
break;
}
default:
{
approxScheme = MEDIAN;
break;
}
}
}
void FastMinKernel::hikPrepareKVNApproximation(NICE::VVector & A) const
{
A.resize(d);
// efficient calculation of |k_*|^2 = k_*^T * k_*
// ---------------------------------
//
// \sum_{i=1}^{n} \left( \sum_{d=1}^{D} \min (x_d^*, x_d^i) \right)^2
// <=\sum_{i=1}^{n} \sum_{d=1}^{D} \left( \min (x_d^*, x_d^i) \right)^2
// = \sum_{d=1}^{D} \sum_{i=1}^{n} \left( \min (x_d^*, x_d^i) \right)^2
// = \sum_{d=1}^{D} \left( \sum_{i:x_d^i < x_*^d} (x_d^i)^2 + \sum_{j: x_d^* \leq x_d^j} (x_d^*)^2 \right)
//
// again let us define l_d = { i | x_d^i <= x_d^* }
// and u_d = { i | x_d^i > x_d^* }, this leads to
//
// = \sum_{d=1}^{D} ( \sum_{l \in l_d} (x_d^l)^2 + \sum_{u \in u_d} (x_d^*)^2
// = \sum_{d=1}^{D} ( \sum_{l \in l_d} (x_d^l)^2 + (x_d^*)^2 \sum_{u \in u_d} 1
//
// We also define
// l_d^j = { i | x_d^i <= x_d^j } and
// u_d^j = { i | x_d^i > x_d^j }
//
// We now need the partial sums
//
// (Definition 1)
// a_{d,j} = \sum_{l \in l_d^j} (x_d^l)^2
// according to increasing values of x_d^l
//
// We end at
// |k_*|^2 <= \sum_{d=1}^{D} \left( a_{d,r_d} + (x_d^*)^2 * |u_d^{r_d}| \right)
// with r_d being the index of the last example in the ordered sequence for dimension d, that is not larger than x_d^*
// we only need as many entries as we have nonZero entries in our features for the corresponding dimensions
for (int i = 0; i < d; i++)
{
uint numNonZero = X_sorted.getNumberOfNonZeroElementsPerDimension(i);
A[i].resize( numNonZero );
}
// for more information see hik_prepare_alpha_multiplications
for (int dim = 0; dim < d; dim++)
{
double squared_sum(0.0);
int cntNonzeroFeat(0);
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
// loop through all elements in sorted order
for ( SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin(); i != nonzeroElements.end(); i++ )
{
const SortedVectorSparse<double>::dataelement & de = i->second;
// de: first - index, second - transformed feature
double elem( de.second );
squared_sum += pow( elem, 2 );
A[dim][cntNonzeroFeat] = squared_sum;
cntNonzeroFeat++;
}
}
}
double * FastMinKernel::hikPrepareKVNApproximationFast(NICE::VVector & A, const Quantization & q, const ParameterizedFunction *pf ) const
{
//NOTE keep in mind: for doing this, we already have precomputed A using hikPrepareSquaredKernelVector!
// number of quantization bins
uint hmax = q.size();
// store (transformed) prototypes
double *prototypes = new double [ hmax ];
for ( uint i = 0 ; i < hmax ; i++ )
if ( pf != NULL ) {
// FIXME: the transformed prototypes could change from dimension to another dimension
// We skip this flexibility ...but it should be changed in the future
prototypes[i] = pf->f ( 1, q.getPrototype(i) );
} else {
prototypes[i] = q.getPrototype(i);
}
// creating the lookup table as pure C, which might be beneficial
// for fast evaluation
double *Tlookup = new double [ hmax * this->d ];
// loop through all dimensions
for (int dim = 0; dim < this->d; dim++)
{
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n )
continue;
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin();
SortedVectorSparse<double>::const_elementpointer iPredecessor = nonzeroElements.begin();
// index of the element, which is always bigger than the current value fval
int index = 0;
// we use the quantization of the original features! the transformed feature were
// already used to calculate A and B, this of course assumes monotonic functions!!!
int qBin = q.quantize ( i->first );
// the next loop is linear in max(hmax, n)
// REMARK: this could be changed to hmax*log(n), when
// we use binary search
for (int j = 0; j < (int)hmax; j++)
{
double fval = prototypes[j];
double t;
if ( (index == 0) && (j < qBin) ) {
// current element is smaller than everything else
// resulting value = fval * sum_l=1^n 1
t = pow( fval, 2 ) * (n-nrZeroIndices-index);
} else {
// move to next example, if necessary
while ( (j >= qBin) && ( index < (this->n-nrZeroIndices)) )
{
index++;
iPredecessor = i;
i++;
if ( i->first != iPredecessor->first )
qBin = q.quantize ( i->first );
}
// compute current element in the lookup table and keep in mind that
// index is the next element and not the previous one
//NOTE pay attention: this is only valid if all entries are positiv! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
if ( (j >= (uint)qBin) && ( index==(this->n-1-nrZeroIndices) ) ) {
// the current element (fval) is equal or bigger to the element indexed by index
// the second term vanishes, which is logical, since all elements are smaller than j!
t = A[dim][index];
} else {
// standard case
t = A[dim][index-1] + pow( fval, 2 ) * (n-nrZeroIndices-(index) );
// A[dim][index-1] + fval * (n-nrZeroIndices-(index) );//fval*fval * (n-nrZeroIndices-(index-1) );
}
}
Tlookup[ dim*hmax + j ] = t;
}
}
delete [] prototypes;
return Tlookup;
}
double* FastMinKernel::hikPrepareLookupTableForKVNApproximation(const Quantization & q, const ParameterizedFunction *pf ) const
{
// number of quantization bins
uint hmax = q.size();
// store (transformed) prototypes
double *prototypes = new double [ hmax ];
for ( uint i = 0 ; i < hmax ; i++ )
if ( pf != NULL ) {
// FIXME: the transformed prototypes could change from dimension to another dimension
// We skip this flexibility ...but it should be changed in the future
prototypes[i] = pf->f ( 1, q.getPrototype(i) );
} else {
prototypes[i] = q.getPrototype(i);
}
// creating the lookup table as pure C, which might be beneficial
// for fast evaluation
double *Tlookup = new double [ hmax * this->d ];
// loop through all dimensions
for (int dim = 0; dim < this->d; dim++)
{
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n )
continue;
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin();
SortedVectorSparse<double>::const_elementpointer iPredecessor = nonzeroElements.begin();
// index of the element, which is always bigger than the current value fval
int index = 0;
// we use the quantization of the original features! Nevetheless, the resulting lookupTable is computed using the transformed ones
int qBin = q.quantize ( i->first );
double sum(0.0);
for (uint j = 0; j < hmax; j++)
{
double fval = prototypes[j];
double t;
if ( (index == 0) && (j < (uint)qBin) ) {
// current element is smaller than everything else
// resulting value = fval * sum_l=1^n 1
t = pow( fval, 2 ) * (n-nrZeroIndices-index);
} else {
// move to next example, if necessary
while ( (j >= (uint)qBin) && ( index < (this->n-nrZeroIndices)) )
{
sum += pow( i->second.second, 2 ); //i->dataElement.transformedFeatureValue
index++;
iPredecessor = i;
i++;
if ( i->first != iPredecessor->first )
qBin = q.quantize ( i->first );
}
// compute current element in the lookup table and keep in mind that
// index is the next element and not the previous one
//NOTE pay attention: this is only valid if we all entries are positiv! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
if ( (j >= (uint)qBin) && ( index==(this->n-1-nrZeroIndices) ) ) {
// the current element (fval) is equal or bigger to the element indexed by index
// the second term vanishes, which is logical, since all elements are smaller than j!
t = sum;
} else {
// standard case
t = sum + pow( fval, 2 ) * (n-nrZeroIndices-(index) );
}
}
Tlookup[ dim*hmax + j ] = t;
}
}
delete [] prototypes;
return Tlookup;
}
//////////////////////////////////////////
// variance computation: sparse inputs
//////////////////////////////////////////
void FastMinKernel::hikComputeKVNApproximation(const NICE::VVector & A, const NICE::SparseVector & xstar, double & norm, const ParameterizedFunction *pf )
{
norm = 0.0;
for (SparseVector::const_iterator i = xstar.begin(); i != xstar.end(); i++)
{
int dim = i->first;
double fval = i->second;
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all features are zero so let us ignore them completely
continue;
}
int position;
//where is the example x^z_i located in
//the sorted array? -> perform binary search, runtime O(log(n))
// search using the original value
X_sorted.findFirstLargerInDimension(dim, fval, position);
position--;
//NOTE again - pay attention! This is only valid if all entries are NOT negative! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
double firstPart(0.0);
//TODO in the "overnext" line there occurs the following error
// Invalid read of size 8
if (position >= 0)
firstPart = (A[dim][position-nrZeroIndices]);
else
firstPart = 0.0;
double secondPart( 0.0);
if ( pf != NULL )
fval = pf->f ( dim, fval );
fval = fval * fval;
if (position >= 0)
secondPart = fval * (n-nrZeroIndices-(position+1));
else //if x_d^* is smaller than every non-zero training example
secondPart = fval * (n-nrZeroIndices);
// but apply using the transformed one
norm += firstPart + secondPart;
}
}
void FastMinKernel::hikComputeKVNApproximationFast(const double *Tlookup, const Quantization & q, const NICE::SparseVector & xstar, double & norm) const
{
norm = 0.0;
// runtime is O(d) if the quantizer is O(1)
for (SparseVector::const_iterator i = xstar.begin(); i != xstar.end(); i++ )
{
int dim = i->first;
double v = i->second;
// we do not need a parameterized function here, since the quantizer works on the original feature values.
// nonetheless, the lookup table was created using the parameterized function
uint qBin = q.quantize(v);
norm += Tlookup[dim*q.size() + qBin];
}
}
void FastMinKernel::hikComputeKernelVector ( const NICE::SparseVector& xstar, NICE::Vector & kstar ) const
{
//init
kstar.resize(this->n);
kstar.set(0.0);
//let's start :)
for (SparseVector::const_iterator i = xstar.begin(); i != xstar.end(); i++)
{
int dim = i->first;
double fval = i->second;
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all features are zero so let us ignore them completely
continue;
}
int position;
//where is the example x^z_i located in
//the sorted array? -> perform binary search, runtime O(log(n))
// search using the original value
X_sorted.findFirstLargerInDimension(dim, fval, position);
position--;
//get the non-zero elements for this dimension
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
//run over the non-zero elements and add the corresponding entries to our kernel vector
int count(nrZeroIndices);
for ( SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin(); i != nonzeroElements.end(); i++, count++ )
{
int origIndex(i->second.first); //orig index (i->second.second would be the transformed feature value)
if (count <= position)
kstar[origIndex] += i->first; //orig feature value
else
kstar[origIndex] += fval;
}
}
}
//////////////////////////////////////////
// variance computation: non-sparse inputs
//////////////////////////////////////////
void FastMinKernel::hikComputeKVNApproximation(const NICE::VVector & A, const NICE::Vector & xstar, double & norm, const ParameterizedFunction *pf )
{
norm = 0.0;
int dim ( 0 );
for (Vector::const_iterator i = xstar.begin(); i != xstar.end(); i++, dim++)
{
double fval = *i;
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all features are zero so let us ignore them completely
continue;
}
int position;
//where is the example x^z_i located in
//the sorted array? -> perform binary search, runtime O(log(n))
// search using the original value
X_sorted.findFirstLargerInDimension(dim, fval, position);
position--;
//NOTE again - pay attention! This is only valid if all entries are NOT negative! - if not, ask wether the current feature is greater than zero. If so, subtract the nrZeroIndices, if not do not
double firstPart(0.0);
//TODO in the "overnext" line there occurs the following error
// Invalid read of size 8
if (position >= 0)
firstPart = (A[dim][position-nrZeroIndices]);
else
firstPart = 0.0;
double secondPart( 0.0);
if ( pf != NULL )
fval = pf->f ( dim, fval );
fval = fval * fval;
if (position >= 0)
secondPart = fval * (n-nrZeroIndices-(position+1));
else //if x_d^* is smaller than every non-zero training example
secondPart = fval * (n-nrZeroIndices);
// but apply using the transformed one
norm += firstPart + secondPart;
}
}
void FastMinKernel::hikComputeKVNApproximationFast(const double *Tlookup, const Quantization & q, const NICE::Vector & xstar, double & norm) const
{
norm = 0.0;
// runtime is O(d) if the quantizer is O(1)
int dim ( 0 );
for (Vector::const_iterator i = xstar.begin(); i != xstar.end(); i++, dim++ )
{
double v = *i;
// we do not need a parameterized function here, since the quantizer works on the original feature values.
// nonetheless, the lookup table was created using the parameterized function
uint qBin = q.quantize(v);
norm += Tlookup[dim*q.size() + qBin];
}
}
void FastMinKernel::hikComputeKernelVector( const NICE::Vector & xstar, NICE::Vector & kstar) const
{
//init
kstar.resize(this->n);
kstar.set(0.0);
//let's start :)
int dim ( 0 );
for (NICE::Vector::const_iterator i = xstar.begin(); i != xstar.end(); i++, dim++)
{
double fval = *i;
int nrZeroIndices = X_sorted.getNumberOfZeroElementsPerDimension(dim);
if ( nrZeroIndices == n ) {
// all features are zero so let us ignore them completely
continue;
}
int position;
//where is the example x^z_i located in
//the sorted array? -> perform binary search, runtime O(log(n))
// search using the original value
X_sorted.findFirstLargerInDimension(dim, fval, position);
position--;
//get the non-zero elements for this dimension
const multimap< double, SortedVectorSparse<double>::dataelement> & nonzeroElements = X_sorted.getFeatureValues(dim).nonzeroElements();
//run over the non-zero elements and add the corresponding entries to our kernel vector
int count(nrZeroIndices);
for ( SortedVectorSparse<double>::const_elementpointer i = nonzeroElements.begin(); i != nonzeroElements.end(); i++, count++ )
{
int origIndex(i->second.first); //orig index (i->second.second would be the transformed feature value)
if (count <= position)
kstar[origIndex] += i->first; //orig feature value
else
kstar[origIndex] += fval;
}
}
}
///////////////////// INTERFACE PERSISTENT /////////////////////
// interface specific methods for store and restore
///////////////////// INTERFACE PERSISTENT /////////////////////
void FastMinKernel::restore ( std::istream & is, int format )
{
bool b_restoreVerbose ( false );
if ( is.good() )
{
if ( b_restoreVerbose )
std::cerr << " restore FastMinKernel" << std::endl;
std::string tmp;
is >> tmp; //class name
if ( ! this->isStartTag( tmp, "FastMinKernel" ) )
{
std::cerr << " WARNING - attempt to restore FastMinKernel, but start flag " << tmp << " does not match! Aborting... " << std::endl;
throw;
}
is.precision (numeric_limits<double>::digits10 + 1);
bool b_endOfBlock ( false ) ;
while ( !b_endOfBlock )
{
is >> tmp; // start of block
if ( this->isEndTag( tmp, "FastMinKernel" ) )
{
b_endOfBlock = true;
continue;
}
tmp = this->removeStartTag ( tmp );
if ( b_restoreVerbose )
std::cerr << " currently restore section " << tmp << " in FastMinKernel" << std::endl;
if ( tmp.compare("n") == 0 )
{
is >> n;
is >> tmp; // end of block
tmp = this->removeEndTag ( tmp );
}
else if ( tmp.compare("d") == 0 )
{
is >> d;
is >> tmp; // end of block
tmp = this->removeEndTag ( tmp );
}
else if ( tmp.compare("noise") == 0 )
{
is >> noise;
is >> tmp; // end of block
tmp = this->removeEndTag ( tmp );
}
else if ( tmp.compare("approxScheme") == 0 )
{
int approxSchemeInt;
is >> approxSchemeInt;
setApproximationScheme(approxSchemeInt);
is >> tmp; // end of block
tmp = this->removeEndTag ( tmp );
}
else if ( tmp.compare("X_sorted") == 0 )
{
X_sorted.restore(is,format);
is >> tmp; // end of block
tmp = this->removeEndTag ( tmp );
}
else
{
std::cerr << "WARNING -- unexpected FastMinKernel object -- " << tmp << " -- for restoration... aborting" << std::endl;
throw;
}
}
}
else
{
std::cerr << "FastMinKernel::restore -- InStream not initialized - restoring not possible!" << std::endl;
}
}
void FastMinKernel::store ( std::ostream & os, int format ) const
{
if (os.good())
{
// show starting point
os << this->createStartTag( "FastMinKernel" ) << std::endl;
os.precision (numeric_limits<double>::digits10 + 1);
os << this->createStartTag( "n" ) << std::endl;
os << n << std::endl;
os << this->createEndTag( "n" ) << std::endl;
os << this->createStartTag( "d" ) << std::endl;
os << d << std::endl;
os << this->createEndTag( "d" ) << std::endl;
os << this->createStartTag( "noise" ) << std::endl;
os << noise << std::endl;
os << this->createEndTag( "noise" ) << std::endl;
os << this->createStartTag( "approxScheme" ) << std::endl;
os << approxScheme << std::endl;
os << this->createEndTag( "approxScheme" ) << std::endl;
os << this->createStartTag( "X_sorted" ) << std::endl;
//store the underlying data
X_sorted.store(os, format);
os << this->createEndTag( "X_sorted" ) << std::endl;
// done
os << this->createEndTag( "FastMinKernel" ) << std::endl;
}
else
{
std::cerr << "OutStream not initialized - storing not possible!" << std::endl;
}
}
void FastMinKernel::clear ()
{
std::cerr << "FastMinKernel clear-function called" << std::endl;
}
///////////////////// INTERFACE ONLINE LEARNABLE /////////////////////
// interface specific methods for incremental extensions
///////////////////// INTERFACE ONLINE LEARNABLE /////////////////////
void FastMinKernel::addExample( const NICE::SparseVector * example,
const double & label,
const bool & performOptimizationAfterIncrement
)
{
// no parameterized function was given - use default
this->addExample ( example );
}
void FastMinKernel::addMultipleExamples( const std::vector< const NICE::SparseVector * > & newExamples,
const NICE::Vector & newLabels,
const bool & performOptimizationAfterIncrement
)
{
// no parameterized function was given - use default
this->addMultipleExamples ( newExamples );
}
void FastMinKernel::addExample( const NICE::SparseVector * example,
const NICE::ParameterizedFunction *pf
)
{
X_sorted.add_feature( *example, pf );
n++;
}
void FastMinKernel::addMultipleExamples( const std::vector< const NICE::SparseVector * > & newExamples,
const NICE::ParameterizedFunction *pf
)
{
for ( std::vector< const NICE::SparseVector * >::const_iterator exIt = newExamples.begin();
exIt != newExamples.end();
exIt++ )
{
X_sorted.add_feature( **exIt, pf );
n++;
}
}