[mlpack-git] master: Fix scoring for furthest neighbor sort. (1092b1c)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/1a702c583fff0319bed163f2e15bb112f1941720...8a0ad2fbe4db5614a6aad27cfb5e101ae8b1db96

>---------------------------------------------------------------

commit 1092b1cbbb35ea83be5679d8a2fa80464a859339
Author: Ryan Curtin <ryan at ratml.org>
Date:   Sun Aug 14 16:11:24 2016 -0400

    Fix scoring for furthest neighbor sort.


>---------------------------------------------------------------

1092b1cbbb35ea83be5679d8a2fa80464a859339
 .../neighbor_search/neighbor_search_rules_impl.hpp | 13 +++++++----
 .../sort_policies/furthest_neighbor_sort.hpp       | 25 ++++++++++++++++++++++
 .../sort_policies/nearest_neighbor_sort.hpp        | 20 +++++++++++++++++
 3 files changed, 54 insertions(+), 4 deletions(-)

diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
index b025ce0..a2e93f3 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
@@ -140,7 +140,8 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Score(
   double bestDistance = candidates[queryIndex].top().first;
   bestDistance = SortPolicy::Relax(bestDistance, epsilon);
 
-  return (SortPolicy::IsBetter(distance, bestDistance)) ? distance : DBL_MAX;
+  return (SortPolicy::IsBetter(distance, bestDistance)) ?
+      SortPolicy::ConvertToScore(distance) : DBL_MAX;
 }
 
 template<typename SortPolicy, typename MetricType, typename TreeType>
@@ -153,11 +154,13 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Rescore(
   if (oldScore == DBL_MAX)
     return oldScore;
 
+  const double distance = SortPolicy::ConvertToDistance(oldScore);
+
   // Just check the score again against the distances.
   double bestDistance = candidates[queryIndex].top().first;
   bestDistance = SortPolicy::Relax(bestDistance, epsilon);
 
-  return (SortPolicy::IsBetter(oldScore, bestDistance)) ? oldScore : DBL_MAX;
+  return (SortPolicy::IsBetter(distance, bestDistance)) ? oldScore : DBL_MAX;
 }
 
 template<typename SortPolicy, typename MetricType, typename TreeType>
@@ -355,7 +358,7 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Score(
       traversalInfo.LastScore() = distance;
     }
 
-    return distance;
+    return SortPolicy::ConvertToScore(distance);
   }
   else
   {
@@ -375,10 +378,12 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Rescore(
   if (oldScore == DBL_MAX)
     return oldScore;
 
+  const double distance = SortPolicy::ConvertToDistance(oldScore);
+
   // Update our bound.
   const double bestDistance = CalculateBound(queryNode);
 
-  return (SortPolicy::IsBetter(oldScore, bestDistance)) ? oldScore : DBL_MAX;
+  return (SortPolicy::IsBetter(distance, bestDistance)) ? oldScore : DBL_MAX;
 }
 
 // Calculate the bound for a given query node in its current state and update
diff --git a/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp b/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp
index 09c3d96..a66c8d1 100644
--- a/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp
+++ b/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp
@@ -144,6 +144,31 @@ class FurthestNeighborSort
       return DBL_MAX;
     return (1 / (1 - epsilon)) * value;
   }
+
+  /**
+   * Convert the given distance to a score.  Lower scores are better, but for
+   * furthest neighbor search, larger distances are better.  Therefore we must
+   * invert the given distance.
+   */
+  static inline double ConvertToScore(const double distance)
+  {
+    if (distance == DBL_MAX)
+      return 0.0;
+    else if (distance == 0.0)
+      return DBL_MAX;
+    else
+      return (1.0 / distance);
+  }
+
+  /**
+   * Convert the given score back to a distance.  This is the inverse of the
+   * operation of converting a distance to a score, and again, for furthest
+   * neighbor search, corresponds to inverting the value.
+   */
+  static inline double ConvertToDistance(const double score)
+  {
+    return ConvertToScore(score); // The two operations are identical.
+  }
 };
 
 } // namespace neighbor
diff --git a/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp b/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp
index 5ccce6d..a36fca2 100644
--- a/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp
+++ b/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp
@@ -147,6 +147,26 @@ class NearestNeighborSort
       return DBL_MAX;
     return (1 / (1 + epsilon)) * value;
   }
+
+  /**
+   * Convert the given distance into a score.  Lower scores are better, so in
+   * the case of nearest neighbor sort where lower distances are better, we just
+   * return the distance.
+   */
+  static inline double ConvertToScore(const double distance)
+  {
+    return distance;
+  }
+
+  /**
+   * Convert the given score to a distance.  This is the inverse of the
+   * operation provided by ConvertToScore().  For nearest neighbor search, there
+   * is no need for any change.
+   */
+  static inline double ConvertToDistance(const double score)
+  {
+    return score;
+  }
 };
 
 } // namespace neighbor