Omnibox - Boost Frequency Scores Based on Number of Matching Pages

components/omnibox/browser/scored_history_match.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/omnibox/browser/scored_history_match.h"
 
 #include <math.h>
 
 #include <algorithm>
 #include <vector>
@@ skipping 91 matching lines @@
 }
 
 }  // namespace
 
 // static
 bool ScoredHistoryMatch::also_do_hup_like_scoring_;
 float ScoredHistoryMatch::bookmark_value_;
 float ScoredHistoryMatch::typed_value_;
 bool ScoredHistoryMatch::fix_few_visits_bug_;
 bool ScoredHistoryMatch::frequency_uses_sum_;
+OmniboxFieldTrial::NumMatchesMultipliers*
+    ScoredHistoryMatch::num_matches_to_frequency_multiplier_ = nullptr;
 size_t ScoredHistoryMatch::max_visits_to_score_;
 bool ScoredHistoryMatch::allow_tld_matches_;
 bool ScoredHistoryMatch::allow_scheme_matches_;
 size_t ScoredHistoryMatch::num_title_words_to_allow_;
 bool ScoredHistoryMatch::hqp_experimental_scoring_enabled_;
 
 // Default topicality threshold.  See GetTopicalityScore() for details.
 float ScoredHistoryMatch::topicality_threshold_ = 0.8f;
 
 // Default HQP relevance buckets. See GetFinalRelevancyScore() for more details
 // on these numbers.
 char ScoredHistoryMatch::hqp_relevance_buckets_str_[] =
     "0.0:400,1.5:600,5.0:900,10.5:1203,15.0:1300,20.0:1399";
 std::vector<ScoredHistoryMatch::ScoreMaxRelevance>*
     ScoredHistoryMatch::hqp_relevance_buckets_ = nullptr;
 
 ScoredHistoryMatch::ScoredHistoryMatch()
     : ScoredHistoryMatch(history::URLRow(),
                          VisitInfoVector(),
                          base::string16(),
                          String16Vector(),
                          WordStarts(),
                          RowWordStarts(),
                          false,
-                         base::Time::Max()) {
-}
+                         1,
+                         base::Time::Max()) {}
 
 ScoredHistoryMatch::ScoredHistoryMatch(
     const history::URLRow& row,
     const VisitInfoVector& visits,
     const base::string16& lower_string,
     const String16Vector& terms_vector,
     const WordStarts& terms_to_word_starts_offsets,
     const RowWordStarts& word_starts,
     bool is_url_bookmarked,
+    size_t num_matching_pages,
     base::Time now)
     : HistoryMatch(row, 0, false, false), raw_score(0) {
   // NOTE: Call Init() before doing any validity checking to ensure that the
   // class is always initialized after an instance has been constructed. In
   // particular, this ensures that the class is initialized after an instance
   // has been constructed via the no-args constructor.
   ScoredHistoryMatch::Init();
 
   // Figure out where each search term appears in the URL and/or page title
   // so that we can score as well as provide autocomplete highlighting.
@@ skipping 96 matching lines @@
         // the prefix that makes it inlineable may be empty.
         likely_can_inline = true;
         innermost_match = (best_inlineable_prefix->num_components ==
                            best_prefix->num_components);
       }
     }
   }
 
   const float topicality_score = GetTopicalityScore(
       terms_vector.size(), url, terms_to_word_starts_offsets, word_starts);
-  const float frequency_score = GetFrequency(now, is_url_bookmarked, visits);
+  const float frequency_score =
+      GetFrequency(now, is_url_bookmarked, visits, num_matching_pages);
   raw_score = base::saturated_cast<int>(GetFinalRelevancyScore(
       topicality_score, frequency_score, *hqp_relevance_buckets_));
 
   if (also_do_hup_like_scoring_ && likely_can_inline) {
     // HistoryURL-provider-like scoring gives any match that is
     // capable of being inlined a certain minimum score.  Some of these
     // are given a higher score that lets them be shown in inline.
     // This test here derives from the test in
     // HistoryURLProvider::PromoteMatchForInlineAutocomplete().
     const bool promote_to_inline =
@@ skipping 131 matching lines @@
   if (initialized)
     return;
 
   initialized = true;
   also_do_hup_like_scoring_ = OmniboxFieldTrial::HQPAlsoDoHUPLikeScoring();
   bookmark_value_ = OmniboxFieldTrial::HQPBookmarkValue();
   typed_value_ = OmniboxFieldTrial::HQPTypedValue();
   max_visits_to_score_ = OmniboxFieldTrial::HQPMaxVisitsToScore();
   frequency_uses_sum_ = OmniboxFieldTrial::HQPFreqencyUsesSum();
   fix_few_visits_bug_ = OmniboxFieldTrial::HQPFixFewVisitsBug();
+  num_matches_to_frequency_multiplier_ =
+      new OmniboxFieldTrial::NumMatchesMultipliers();

[Peter Kasting, 2016/12/01 07:07:53]

This leaks.  If you want a leaky object of class type, prefer something like
CR_DEFINE_STATIC_LOCAL.

[Mark P, 2016/12/04 01:06:42]

Still TODO.

[Mark P, 2016/12/06 21:02:47]

I don't understand how this macro should be used in this context.  That macro
talks about static local variables, not static class member variables.  From
some code searching, I couldn't easily find examples of use in the class
context.  Can you more clearly explain what you want me to do?  (Is that the
right macro you wanted to point me to?)

[Peter Kasting, 2016/12/06 21:41:27]

There are two ways to do this I can think of:

(1) Use CR_DEFINE_STATIC_LOCAL in the method that returns the correct document
specificity score.  Provide a (static or not) class member pointer that's
normally set to the address of this static.  Tests can temporarily override this
pointer to point at a different vector.  The method then just unconditionally
dereferences the pointer.

(2) Use a base::LazyInstance in the method or as a static class member.  The
rest of (1) still applies.  This will be slightly trickier since you need a
separate static local bool "initialized" or similar to guard the code that sets
up the vector contents the first time it's accessed.

I'd do (1).

[Mark P, 2016/12/08 00:21:31]

Thanks for the explanation.  I'll do something like (1).  It'll first appear in
another changelist (where I have to make a similar change).  Once that
changelist is acceptable, I'll make the analogous change here.

+  OmniboxFieldTrial::HQPGetNumMatchesMultipliers(
+      num_matches_to_frequency_multiplier_);
   allow_tld_matches_ = OmniboxFieldTrial::HQPAllowMatchInTLDValue();
   allow_scheme_matches_ = OmniboxFieldTrial::HQPAllowMatchInSchemeValue();
   num_title_words_to_allow_ = OmniboxFieldTrial::HQPNumTitleWordsToAllow();
 
   InitRawTermScoreToTopicalityScoreArray();
   InitDaysAgoToRecencyScoreArray();
   InitHQPExperimentalParams();
 }
 
 float ScoredHistoryMatch::GetTopicalityScore(
@@ skipping 149 matching lines @@
   // Lookup the score in days_ago_to_recency_score, treating
   // everything older than what we've precomputed as the oldest thing
   // we've precomputed.  The std::max is to protect against corruption
   // in the database (in case last_visit_days_ago is negative).
   return days_ago_to_recency_score[std::max(
       std::min(last_visit_days_ago, kDaysToPrecomputeRecencyScoresFor - 1), 0)];
 }
 
 float ScoredHistoryMatch::GetFrequency(const base::Time& now,
                                        const bool bookmarked,
-                                       const VisitInfoVector& visits) const {
+                                       const VisitInfoVector& visits,
+                                       const size_t num_matching_pages) const {
   // Compute the weighted sum of |value_of_transition| over the last at most
   // |max_visits_to_score_| visits, where each visit is weighted using
   // GetRecencyScore() based on how many days ago it happened.
   float summed_visit_points = 0;
   auto visits_end =
       visits.begin() + std::min(visits.size(), max_visits_to_score_);
   // Visits should be in newest to oldest order.
   DCHECK(std::adjacent_find(
              visits.begin(), visits_end,
              [](const history::VisitInfo& a, const history::VisitInfo& b) {
                return a.first < b.first;
              }) == visits_end);
   for (auto i = visits.begin(); i != visits_end; ++i) {
     const bool is_page_transition_typed =
         ui::PageTransitionCoreTypeIs(i->second, ui::PAGE_TRANSITION_TYPED);
     float value_of_transition = is_page_transition_typed ? typed_value_ : 1;
     if (bookmarked)
       value_of_transition = std::max(value_of_transition, bookmark_value_);
     const float bucket_weight = GetRecencyScore((now - i->first).InDays());
     summed_visit_points += (value_of_transition * bucket_weight);
   }
-  if (frequency_uses_sum_)
-    return summed_visit_points;
-
-  // Compute the average weighted value_of_transition and return it.
-  // Use |max_visits_to_score_| as the denominator for the average regardless of
-  // how many visits there were in order to penalize a match that has
-  // fewer visits than kMaxVisitsToScore.
-  if (fix_few_visits_bug_)
-    return summed_visit_points / ScoredHistoryMatch::max_visits_to_score_;
-  return visits.size() * summed_visit_points /
-         ScoredHistoryMatch::max_visits_to_score_;
+  float frequency;
+  if (frequency_uses_sum_) {
+    frequency = summed_visit_points;
+  } else {
+    // Compute the average weighted value_of_transition and return it.
+    // Use |max_visits_to_score_| as the denominator for the average regardless
+    // of how many visits there were in order to penalize a match that has
+    // fewer visits than kMaxVisitsToScore.
+    if (fix_few_visits_bug_) {
+      frequency =
+          summed_visit_points / ScoredHistoryMatch::max_visits_to_score_;
+    } else {
+      frequency = visits.size() * summed_visit_points /
+                  ScoredHistoryMatch::max_visits_to_score_;
+    }
+  }
+  // Boost the score if applicable.
+  if (num_matches_to_frequency_multiplier_->find(num_matching_pages) !=
+      num_matches_to_frequency_multiplier_->end())
+    frequency *= (*num_matches_to_frequency_multiplier_)[num_matching_pages];
+  return frequency;

[Peter Kasting, 2016/12/01 07:07:53]

I don't love putting this here.

Part of this is complexity.  The function is already complicated enough and the
code that was at the end was easier to read before adding the temp to store the
intermediate result in.  From a readability perspective, it seems like wrapping
this in a helper that does the adjustment, or simply doing it on the caller
side, might be nice.

Part of this is testability.  Long-term, if we want to do this all the time, it
seems like it might be nice to accurately test "find the real frequency"
separately from the boosting here.

And part is readability.  I find it confusing that you implemented this by
boosting frequency early instead of making an adjustment when calculating the
final score.  Conceptually, why not claim the final algorithm is "frequency +
recency + relevance" (I don't mean "add" by "+", I just mean those are the
relevant inputs) and have this be the way we compute the "relevance" factor?  In
terms of concrete implementation, you could do it however you want to, I am just
interested in where the computation happens.

And even if we do this by just tweaking the frequency number early, a function
called "GetFrequency()" and a separate one like
"GetRelevanceAdjustedFrequency()" or some other similar name that makes it clear
what it does and what it returns seems like it would be less confusing to
understand.

[Mark P, 2016/12/04 01:06:42]

I agree with your reasoning below.  After some thought, I realized it shouldn't
be part of the frequency score at all.  I called this new factor a "document
specificity score" and added it as a third factor (in addition to frequency and
topicality) to go into the final relevancy calculation.  This makes a lot more
conceptual sense, makes the code cleaner and more readable and more testable. 
Win all around.

 }
 
 // static
 float ScoredHistoryMatch::GetFinalRelevancyScore(
     float topicality_score,
     float frequency_score,
     const std::vector<ScoreMaxRelevance>& hqp_relevance_buckets) {
   DCHECK(hqp_relevance_buckets.size() > 0);
   DCHECK_EQ(hqp_relevance_buckets[0].first, 0.0);
 
@@ skipping 94 matching lines @@
           base::StringToDouble(it->first, &bucket.first);
       DCHECK(is_valid_intermediate_score);
       bool is_valid_hqp_score = base::StringToInt(it->second, &bucket.second);
       DCHECK(is_valid_hqp_score);
       hqp_buckets->push_back(bucket);
     }
     return true;
   }
   return false;
 }