CosineTree Class Reference

Public Member Functions

 CosineTree (const arma::mat &dataset)
 CosineTree constructor for the root node of the tree. More...

 
 CosineTree (CosineTree &parentNode, const std::vector< size_t > &subIndices)
 CosineTree constructor for nodes other than the root node of the tree. More...

 
 CosineTree (const arma::mat &dataset, const double epsilon, const double delta)
 Construct the CosineTree and the basis for the given matrix, and passed 'epsilon' and 'delta' parameters. More...

 
 CosineTree (const CosineTree &other)
 Copy the given tree. More...

 
 CosineTree (CosineTree &&other)
 Move the given tree. More...

 
 ~CosineTree ()
 Clean up the CosineTree: release allocated memory (including children). More...

 
void BasisVector (arma::vec &bVector)
 Set the basis vector of the node. More...

 
arma::vec & BasisVector ()
 Get the basis vector of the node. More...

 
size_t BinarySearch (arma::vec &cDistribution, double value, size_t start, size_t end)
 Sample a column based on the cumulative Length-Squared distribution of the cosine node, and a randomly generated value in the range [0, 1]. More...

 
void CalculateCentroid ()
 Calculate centroid of the columns present in the node. More...

 
void CalculateCosines (arma::vec &cosines)
 Calculate cosines of the columns present in the node, with respect to the sampled splitting point. More...

 
arma::vec & Centroid ()
 Get pointer to the centroid vector. More...

 
size_t ColumnSampleLS ()
 Sample a point from the Length-Squared distribution of the cosine node. More...

 
void ColumnSamplesLS (std::vector< size_t > &sampledIndices, arma::vec &probabilities, size_t numSamples)
 Sample 'numSamples' points from the Length-Squared distribution of the cosine node. More...

 
void ConstructBasis (CosineNodeQueue &treeQueue)
 Constructs the final basis matrix, after the cosine tree construction. More...

 
void CosineNodeSplit ()
 This function splits the cosine node into two children based on the cosines of the columns contained in the node, with respect to the sampled splitting point. More...

 
double FrobNormSquared () const
 Get the Frobenius norm squared of columns in the node. More...

 
const arma::mat & GetDataset () const
 Get pointer to the dataset matrix. More...

 
void GetFinalBasis (arma::mat &finalBasis)
 Returns the basis of the constructed subspace. More...

 
void L2Error (const double error)
 Set the Monte Carlo error. More...

 
double L2Error () const
 Get the Monte Carlo error. More...

 
CosineTreeLeft () const
 Get pointer to the left child of the node. More...

 
CosineTree *& Left ()
 Modify the pointer to the left child of the node. More...

 
void ModifiedGramSchmidt (CosineNodeQueue &treeQueue, arma::vec &centroid, arma::vec &newBasisVector, arma::vec *addBasisVector=NULL)
 Calculates the orthonormalization of the passed centroid, with respect to the current vector subspace. More...

 
double MonteCarloError (CosineTree *node, CosineNodeQueue &treeQueue, arma::vec *addBasisVector1=NULL, arma::vec *addBasisVector2=NULL)
 Estimates the squared error of the projection of the input node's matrix onto the current vector subspace. More...

 
size_t NumColumns () const
 Get number of columns of input matrix in the node. More...

 
CosineTreeoperator= (const CosineTree &other)
 Copy the given Cosine Tree. More...

 
CosineTreeoperator= (CosineTree &&other)
 Take ownership of the given Cosine Tree. More...

 
CosineTreeParent () const
 Get pointer to the parent node. More...

 
CosineTree *& Parent ()
 Modify the pointer to the parent node. More...

 
CosineTreeRight () const
 Get pointer to the right child of the node. More...

 
CosineTree *& Right ()
 Modify the pointer to the left child of the node. More...

 
size_t SplitPointIndex () const
 Get the column index of split point of the node. More...

 
std::vector< size_t > & VectorIndices ()
 Get the indices of columns in the node. More...

 

Detailed Description

Definition at line 29 of file cosine_tree.hpp.

Constructor & Destructor Documentation

◆ CosineTree() [1/5]

CosineTree ( const arma::mat &  dataset)

CosineTree constructor for the root node of the tree.

It initializes the necessary variables required for splitting of the node, and building the tree further. It takes a pointer to the input matrix and calculates the relevant variables using it.

Parameters
datasetMatrix for which cosine tree is constructed.

◆ CosineTree() [2/5]

CosineTree ( CosineTree parentNode,
const std::vector< size_t > &  subIndices 
)

CosineTree constructor for nodes other than the root node of the tree.

It takes in a pointer to the parent node and a list of column indices which mentions the columns to be included in the node. The function calculate the relevant variables just like the constructor above.

Parameters
parentNodePointer to the parent cosine node.
subIndicesPointer to vector of column indices to be included.

◆ CosineTree() [3/5]

CosineTree ( const arma::mat &  dataset,
const double  epsilon,
const double  delta 
)

Construct the CosineTree and the basis for the given matrix, and passed 'epsilon' and 'delta' parameters.

The CosineTree is constructed by splitting nodes in the direction of maximum error, stored using a priority queue. Basis vectors are added from the left and right children of the split node. The basis vector from a node is the orthonormalized centroid of its columns. The splitting continues till the Monte Carlo estimate of the input matrix's projection on the obtained subspace is less than a fraction of the norm of the input matrix.

Parameters
datasetMatrix for which the CosineTree is constructed.
epsilonError tolerance fraction for calculated subspace.
deltaCumulative probability for Monte Carlo error lower bound.

◆ CosineTree() [4/5]

CosineTree ( const CosineTree other)

Copy the given tree.

Be careful! This may use a lot of memory.

Parameters
otherTree to copy from.

◆ CosineTree() [5/5]

CosineTree ( CosineTree &&  other)

Move the given tree.

The tree passed as a parameter will be emptied and will not be usable after this call.

Parameters
otherTree to move.

◆ ~CosineTree()

~CosineTree ( )

Clean up the CosineTree: release allocated memory (including children).

Member Function Documentation

◆ BasisVector() [1/2]

void BasisVector ( arma::vec &  bVector)
inline

Set the basis vector of the node.

Definition at line 215 of file cosine_tree.hpp.

◆ BasisVector() [2/2]

arma::vec& BasisVector ( )
inline

Get the basis vector of the node.

Definition at line 218 of file cosine_tree.hpp.

◆ BinarySearch()

size_t BinarySearch ( arma::vec &  cDistribution,
double  value,
size_t  start,
size_t  end 
)

Sample a column based on the cumulative Length-Squared distribution of the cosine node, and a randomly generated value in the range [0, 1].

Binary search is more efficient than searching linearly for the same. This leads a significant speedup when there are large number of columns to choose from and when a number of samples are to be drawn from the distribution.

Parameters
cDistributionCumulative LS distribution of columns in the node.
valueRandomly generated value in the range [0, 1].
startStarting index of the distribution interval to search in.
endEnding index of the distribution interval to search in.

◆ CalculateCentroid()

void CalculateCentroid ( )

Calculate centroid of the columns present in the node.

The calculated centroid is used as a basis vector for the cosine tree being constructed.

◆ CalculateCosines()

void CalculateCosines ( arma::vec &  cosines)

Calculate cosines of the columns present in the node, with respect to the sampled splitting point.

The calculated cosine values are useful for splitting the node into its children.

Parameters
cosinesVector to store the cosine values in.

◆ Centroid()

arma::vec& Centroid ( )
inline

Get pointer to the centroid vector.

Definition at line 212 of file cosine_tree.hpp.

◆ ColumnSampleLS()

size_t ColumnSampleLS ( )

Sample a point from the Length-Squared distribution of the cosine node.

The function uses 'l2NormsSquared' to calculate the cumulative probability distribution of the column vectors. The sampling is based on a randomly generated value in the range [0, 1].

◆ ColumnSamplesLS()

void ColumnSamplesLS ( std::vector< size_t > &  sampledIndices,
arma::vec &  probabilities,
size_t  numSamples 
)

Sample 'numSamples' points from the Length-Squared distribution of the cosine node.

The function uses 'l2NormsSquared' to calculate the cumulative probability distribution of the column vectors. The sampling is based on a randomly generated values in the range [0, 1].

◆ ConstructBasis()

void ConstructBasis ( CosineNodeQueue treeQueue)

Constructs the final basis matrix, after the cosine tree construction.

Parameters
treeQueuePriority queue of cosine nodes.

◆ CosineNodeSplit()

void CosineNodeSplit ( )

This function splits the cosine node into two children based on the cosines of the columns contained in the node, with respect to the sampled splitting point.

The function also calls the CosineTree constructor for the children.

◆ FrobNormSquared()

double FrobNormSquared ( ) const
inline

Get the Frobenius norm squared of columns in the node.

Definition at line 239 of file cosine_tree.hpp.

◆ GetDataset()

const arma::mat& GetDataset ( ) const
inline

Get pointer to the dataset matrix.

Definition at line 201 of file cosine_tree.hpp.

◆ GetFinalBasis()

void GetFinalBasis ( arma::mat &  finalBasis)
inline

Returns the basis of the constructed subspace.

Definition at line 198 of file cosine_tree.hpp.

◆ L2Error() [1/2]

void L2Error ( const double  error)
inline

Set the Monte Carlo error.

Definition at line 207 of file cosine_tree.hpp.

Referenced by CompareCosineNode::operator()().

◆ L2Error() [2/2]

double L2Error ( ) const
inline

Get the Monte Carlo error.

Definition at line 209 of file cosine_tree.hpp.

◆ Left() [1/2]

CosineTree* Left ( ) const
inline

Get pointer to the left child of the node.

Definition at line 226 of file cosine_tree.hpp.

◆ Left() [2/2]

CosineTree*& Left ( )
inline

Modify the pointer to the left child of the node.

Definition at line 228 of file cosine_tree.hpp.

◆ ModifiedGramSchmidt()

void ModifiedGramSchmidt ( CosineNodeQueue treeQueue,
arma::vec &  centroid,
arma::vec &  newBasisVector,
arma::vec *  addBasisVector = NULL 
)

Calculates the orthonormalization of the passed centroid, with respect to the current vector subspace.

Parameters
treeQueuePriority queue of cosine nodes.
centroidCentroid of the node being added to the basis.
newBasisVectorOrthonormalized centroid of the node.
addBasisVectorAddress to additional basis vector.

◆ MonteCarloError()

double MonteCarloError ( CosineTree node,
CosineNodeQueue treeQueue,
arma::vec *  addBasisVector1 = NULL,
arma::vec *  addBasisVector2 = NULL 
)

Estimates the squared error of the projection of the input node's matrix onto the current vector subspace.

A normal distribution is fit using weighted norms of projections of samples drawn from the input node's matrix columns. The error is calculated as the difference between the Frobenius norm of the input node's matrix and lower bound of the normal distribution.

Parameters
nodeNode for which Monte Carlo estimate is calculated.
treeQueuePriority queue of cosine nodes.
addBasisVector1Address to first additional basis vector.
addBasisVector2Address to second additional basis vector.

◆ NumColumns()

size_t NumColumns ( ) const
inline

Get number of columns of input matrix in the node.

Definition at line 236 of file cosine_tree.hpp.

◆ operator=() [1/2]

CosineTree& operator= ( const CosineTree other)

Copy the given Cosine Tree.

Parameters
otherThe tree to be copied.

◆ operator=() [2/2]

CosineTree& operator= ( CosineTree &&  other)

Take ownership of the given Cosine Tree.

Parameters
otherThe tree to take ownership of.

◆ Parent() [1/2]

CosineTree* Parent ( ) const
inline

Get pointer to the parent node.

Definition at line 221 of file cosine_tree.hpp.

◆ Parent() [2/2]

CosineTree*& Parent ( )
inline

Modify the pointer to the parent node.

Definition at line 223 of file cosine_tree.hpp.

◆ Right() [1/2]

CosineTree* Right ( ) const
inline

Get pointer to the right child of the node.

Definition at line 231 of file cosine_tree.hpp.

◆ Right() [2/2]

CosineTree*& Right ( )
inline

Modify the pointer to the left child of the node.

Definition at line 233 of file cosine_tree.hpp.

◆ SplitPointIndex()

size_t SplitPointIndex ( ) const
inline

Get the column index of split point of the node.

Definition at line 242 of file cosine_tree.hpp.

◆ VectorIndices()

std::vector<size_t>& VectorIndices ( )
inline

Get the indices of columns in the node.

Definition at line 204 of file cosine_tree.hpp.


The documentation for this class was generated from the following file:
  • /home/jenkins-mlpack/mlpack.org/_src/mlpack-3.3.1/src/mlpack/core/tree/cosine_tree/cosine_tree.hpp