Fix volume regularization in DET

[rcurtin]

Reported by rcurtin on 16 May 42589854 11:37 UTC
When switching to using log-space, I did not take the time to figure out how to have the volume regularized calculation of alpha work in logspace. Currently the code looks like:

if (useVolReg)
{
  // This is incorrect.
  gT = alphaUpper; // / (subtreeLeavesVTInv - vTInv);
}

In normal space, the expression in the denominator is the sum of all the inverse volumes of the leaves, with the inverse volume of the node subtracted from it. How to do this in logspace is slightly less clear; we want to avoid non-logspace representation of volumes.

Migrated-From: http://trac.research.cc.gatech.edu/fastlab/ticket/238

[mlpack-bot]

This issue has been automatically marked as stale because it has not had any recent activity. It will be closed in 7 days if no further activity occurs. Thank you for your contributions! 👍

[SuvarshaChennareddy]

I have an idea, but I am not sure if it is the most efficient approach.
We could store all the log volumes of the leaves of the tree (keep adding them as we are growing and pruning) in a linked list (since we wouldn't know how many leaves there would be in the end). To find log(subtreeLeavesVTInv - vTInv) (which I believe is to be calculated according to this), we can retrieve the log volumes of the current sub tree's leaves from the linked list (which would have the log volumes of all the leaves found till then) and use a method similar to the one defined in log_add_impl.hpp.
Retrieving the log volumes of the current sub tree's leaves from the linked list can be done with the help of the variable subtreeLeaves. We can retrieve the last subtreeLeaves elements of the linked list logVolumes[(len(logVolumes)-1)-subtreeLeaves : len(logVolumes)-1]. These elements will be the log volumes of the current sub tree's leaves.

The logic is given below:

template<typename MatType, typename TagType>
double DTree<MatType, TagType>::Grow(MatType& data,
                                     arma::Col<size_t>& oldFromNew,
                                     const bool useVolReg,
                                     const size_t maxLeafSize,
                                     const size_t minLeafSize,
                                     std::List<typename MatType::elem_type>& logVolumes){...}

Here, the linked list logVolumes will be continuously updated as the tree grows (or is being pruned). subTreeLeaves keeps track of the number of leaves there are in the current sub tree.
In the case where the node is a leaf, logVolumes can be updated as follows:

subtreeLeaves = 1;
subtreeLeavesLogNegError = logNegError;
logVolumes.push_front(logVolume);

With logVolumes, we can calculate log(subtreeLeavesVTInv - vTInv) using a function similar to the one defined in log_add_impl.hpp. However, we would pass in the number of sub tree leaves (subtreeLeaves) and log(vTInV) (log volume of root node of the current sub tree) as arguments (along with logVolumes ).