[mlpack-svn] r15828 - mlpack/trunk/src/mlpack/methods/fastmks

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: rcurtin
Date: Mon Sep 23 12:52:30 2013
New Revision: 15828

Log:
The parent-child pruning bounds were too tight.  They did not consider one of
the bound terms and the cross-term, and thus failed, especially when considering
a leaf node where the furthest descendant distance was 0.  Also update
documentation a bit so that big chunk of code makes a bit more sense.


Modified:
   mlpack/trunk/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp

Modified: mlpack/trunk/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp	Mon Sep 23 12:52:30 2013
@@ -208,13 +208,26 @@
 
   const double queryDistBound = (queryParentDist + queryDescDist);
   const double refDistBound = (refParentDist + refDescDist);
+  const double dualTerm = queryDistBound * refDistBound;
 
+  // The parent-child and parent-parent prunes work by applying the same pruning
+  // condition, except they are tighter because
+  //    queryDistBound < queryNode.Parent()->FurthestDescendantDistance()
+  // and
+  //    refDistBound < referenceNode.Parent()->FurthestDescendantDistance()
+  // so we construct the same bounds that were used when Score() was called with
+  // the parents, except with the tighter distance bounds.  Sometimes this
+  // allows us to prune nodes without evaluating the base cases between them.
   if ((queryParent != NULL) &&
       (queryParent->Stat().LastKernelNode() == (void*) &referenceNode))
   {
     // Query parent was last evaluated with reference node.
-    const double maxKernelBound = queryParent->Stat().LastKernel() +
+    const double queryKernelTerm =
+        refDistBound * queryParent->Stat().SelfKernel();
+    const double refKernelTerm =
         queryDistBound * referenceNode.Stat().SelfKernel();
+    const double maxKernelBound = queryParent->Stat().LastKernel() +
+        queryKernelTerm + refKernelTerm + dualTerm;
 
     if (maxKernelBound < bestKernel)
       return DBL_MAX;
@@ -223,8 +236,11 @@
       (refParent->Stat().LastKernelNode() == (void*) &queryNode))
   {
     // Reference parent was last evaluated with query node.
+    const double queryKernelTerm = refDistBound * queryNode.Stat().SelfKernel();
+    const double refKernelTerm =
+        queryDistBound * refParent->Stat().SelfKernel();
     const double maxKernelBound = refParent->Stat().LastKernel() +
-        (refParentDist + refDescDist) * queryNode.Stat().SelfKernel();
+        queryKernelTerm + refKernelTerm + dualTerm;
 
     if (maxKernelBound < bestKernel)
       return DBL_MAX;
@@ -250,12 +266,10 @@
       (refParent->Stat().LastKernelNode() == (void*) queryParent))
   {
     // Reference parent was last calculated with query parent.
-    const double queryKernelTerm = (refParentDist + refDescDist) *
+    const double queryKernelTerm = refDistBound *
         queryParent->Stat().SelfKernel();
-    const double refKernelTerm = (queryParentDist + queryDescDist) *
+    const double refKernelTerm = queryDistBound *
         refParent->Stat().SelfKernel();
-    const double dualTerm = (queryParentDist + queryDescDist) *
-        (refParentDist + refDescDist);
 
     const double maxKernelBound = refParent->Stat().LastKernel() +
         queryKernelTerm + refKernelTerm + dualTerm;
@@ -264,10 +278,13 @@
       return DBL_MAX;
   }
 
-  // Calculate kernel evaluation, if necessary.
+  // We were unable to perform a parent-child or parent-parent prune, so now we
+  // must calculate kernel evaluation, if necessary.
   double kernelEval = 0.0;
   if (tree::TreeTraits<TreeType>::FirstPointIsCentroid)
   {
+    // For this type of tree, we may have already calculated the base case in
+    // the parents.  So see if it is already cached there.
     bool alreadyDone = false;
     if ((queryNode.Parent() != NULL) &&
         (queryNode.Parent()->Point(0) == queryNode.Point(0)))