click_based_category_ranker.cc 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488
  1. // Copyright 2016 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/ntp_snippets/category_rankers/click_based_category_ranker.h"
  5. #include <algorithm>
  6. #include <string>
  7. #include <utility>
  8. #include "base/logging.h"
  9. #include "base/numerics/safe_conversions.h"
  10. #include "base/strings/string_number_conversions.h"
  11. #include "base/strings/string_util.h"
  12. #include "base/values.h"
  13. #include "components/ntp_snippets/category_rankers/constant_category_ranker.h"
  14. #include "components/ntp_snippets/content_suggestions_metrics.h"
  15. #include "components/ntp_snippets/pref_names.h"
  16. #include "components/ntp_snippets/time_serialization.h"
  17. #include "components/prefs/pref_registry_simple.h"
  18. #include "components/prefs/pref_service.h"
  19. namespace ntp_snippets {
  20. namespace {
  21. // In order to increase stability and predictability of the order, an extra
  22. // level of "confidence" is required before moving a category upwards. In other
  23. // words, the category is moved not when it reaches the previous one, but rather
  24. // when it leads by some amount. We refer to this required extra "confidence" as
  25. // a passing margin. Each position has its own passing margin. The category is
  26. // moved upwards (i.e. passes another category) when it has at least passing
  27. // margin of the previous category position more clicks.
  28. const int kPassingMargin = 5;
  29. // The first categories get more attention and, therefore, here more stability
  30. // is needed. The passing margin of such categories is increased and they are
  31. // referred to as top categories (with extra margin). Only category position
  32. // defines whether a category is top, but not its content.
  33. const int kNumTopCategoriesWithExtraMargin = 3;
  34. // The increase of passing margin for each top category compared to the next
  35. // category (e.g. the first top category has passing margin larger by this value
  36. // than the second top category, the last top category has it larger by this
  37. // value than the first non-top category).
  38. const int kExtraPassingMargin = 2;
  39. // The ranker must "forget" history with time, so that changes in the user
  40. // behavior are reflected by the order in reasonable time. This is done using
  41. // click count decay with time. However, if there is not enough data, there is
  42. // no need in "forgetting" it. This value defines how many total clicks (across
  43. // categories) are considered enough to decay.
  44. const int kMinNumClicksToDecay = 30;
  45. // Time between two consecutive decays (assuming enough clicks).
  46. constexpr auto kTimeBetweenDecays = base::Days(1);
  47. // Decay factor as a fraction. The current value approximates the seventh root
  48. // of 0.5. This yields a 50% decay per seven decays. Seven weak decays are used
  49. // instead of one 50% decay in order to decrease difference of click weight in
  50. // time.
  51. const int kDecayFactorNumerator = 91;
  52. const int kDecayFactorDenominator = 100; // pow(0.91, 7) = 0.517
  53. // Number of positions by which a dismissed category is downgraded.
  54. const int kDismissedCategoryPenalty = 1;
  55. const char kCategoryIdKey[] = "category";
  56. const char kClicksKey[] = "clicks";
  57. const char kLastDismissedKey[] = "last_dismissed";
  58. } // namespace
  59. ClickBasedCategoryRanker::ClickBasedCategoryRanker(PrefService* pref_service,
  60. base::Clock* clock)
  61. : pref_service_(pref_service), clock_(clock) {
  62. if (!ReadOrderFromPrefs(&ordered_categories_)) {
  63. // TODO(crbug.com/676273): Handle adding new hardcoded KnownCategories to
  64. // existing order from prefs. Currently such new category is completely
  65. // ignored and may be never shown.
  66. RestoreDefaultOrder();
  67. }
  68. if (ReadLastDecayTimeFromPrefs() == DeserializeTime(0)) {
  69. StoreLastDecayTimeToPrefs(clock_->Now());
  70. }
  71. }
  72. ClickBasedCategoryRanker::~ClickBasedCategoryRanker() = default;
  73. bool ClickBasedCategoryRanker::Compare(Category left, Category right) const {
  74. if (!ContainsCategory(left)) {
  75. LOG(DFATAL) << "The category with ID " << left.id()
  76. << " has not been added using AppendCategoryIfNecessary.";
  77. }
  78. if (!ContainsCategory(right)) {
  79. LOG(DFATAL) << "The category with ID " << right.id()
  80. << " has not been added using AppendCategoryIfNecessary.";
  81. }
  82. if (left == right) {
  83. return false;
  84. }
  85. for (const RankedCategory& ranked_category : ordered_categories_) {
  86. if (ranked_category.category == left) {
  87. return true;
  88. }
  89. if (ranked_category.category == right) {
  90. return false;
  91. }
  92. }
  93. // This fallback is provided only to satisfy "Compare" contract if by mistake
  94. // categories are not added using AppendCategoryIfNecessary. One should not
  95. // rely on this, instead the order must be defined explicitly using
  96. // AppendCategoryIfNecessary.
  97. return left.id() < right.id();
  98. }
  99. void ClickBasedCategoryRanker::ClearHistory(base::Time begin, base::Time end) {
  100. // Ignore all partial removals and react only to "entire" history removal.
  101. bool is_entire_history = (begin == base::Time() && end == base::Time::Max());
  102. if (!is_entire_history) {
  103. return;
  104. }
  105. StoreLastDecayTimeToPrefs(DeserializeTime(0));
  106. // The categories added through |AppendCategoryIfNecessary| cannot be
  107. // completely removed, since no one is required to reregister them. Instead
  108. // they are preserved in the default order (sorted by id).
  109. std::vector<RankedCategory> old_categories = ordered_categories_;
  110. RestoreDefaultOrder();
  111. std::vector<Category> added_categories;
  112. for (const RankedCategory& old_category : old_categories) {
  113. auto it =
  114. std::find_if(ordered_categories_.begin(), ordered_categories_.end(),
  115. [old_category](const RankedCategory& other) {
  116. return other.category == old_category.category;
  117. });
  118. if (it == ordered_categories_.end()) {
  119. added_categories.push_back(old_category.category);
  120. }
  121. }
  122. // Sort added categories by id to make their order history independent.
  123. std::sort(added_categories.begin(), added_categories.end(),
  124. Category::CompareByID());
  125. for (Category added_category : added_categories) {
  126. ordered_categories_.push_back(RankedCategory(
  127. added_category, /*clicks=*/0, /*last_dismissed=*/base::Time()));
  128. }
  129. StoreOrderToPrefs(ordered_categories_);
  130. }
  131. void ClickBasedCategoryRanker::AppendCategoryIfNecessary(Category category) {
  132. if (!ContainsCategory(category)) {
  133. ordered_categories_.push_back(RankedCategory(
  134. category, /*clicks=*/0, /*last_dismissed=*/base::Time()));
  135. StoreOrderToPrefs(ordered_categories_);
  136. }
  137. }
  138. void ClickBasedCategoryRanker::InsertCategoryBeforeIfNecessary(
  139. Category category_to_insert,
  140. Category anchor) {
  141. InsertCategoryRelativeToIfNecessary(category_to_insert, anchor,
  142. /*after=*/false);
  143. }
  144. void ClickBasedCategoryRanker::InsertCategoryAfterIfNecessary(
  145. Category category_to_insert,
  146. Category anchor) {
  147. InsertCategoryRelativeToIfNecessary(category_to_insert, anchor,
  148. /*after=*/true);
  149. }
  150. std::vector<CategoryRanker::DebugDataItem>
  151. ClickBasedCategoryRanker::GetDebugData() {
  152. std::vector<CategoryRanker::DebugDataItem> result;
  153. result.push_back(
  154. CategoryRanker::DebugDataItem("Type", "ClickBasedCategoryRanker"));
  155. std::vector<std::string> category_strings;
  156. for (const auto& ranked_category : ordered_categories_) {
  157. category_strings.push_back(base::ReplaceStringPlaceholders(
  158. "($1; $2)",
  159. {base::NumberToString(ranked_category.category.id()),
  160. base::NumberToString(ranked_category.clicks)},
  161. /*offsets=*/nullptr));
  162. }
  163. result.push_back(
  164. CategoryRanker::DebugDataItem("Current order (with click counts)",
  165. base::JoinString(category_strings, ", ")));
  166. return result;
  167. }
  168. void ClickBasedCategoryRanker::OnSuggestionOpened(Category category) {
  169. if (!ContainsCategory(category)) {
  170. LOG(DFATAL) << "The category with ID " << category.id()
  171. << " has not been added using AppendCategoryIfNecessary.";
  172. return;
  173. }
  174. DecayClicksIfNeeded();
  175. auto current = FindCategory(category);
  176. DCHECK_GE(current->clicks, 0);
  177. // The overflow is ignored. It is unlikely to happen, because of click count
  178. // decay.
  179. current->clicks++;
  180. // Move the category up if appropriate.
  181. if (current != ordered_categories_.begin()) {
  182. auto previous = current - 1;
  183. const int passing_margin = GetPositionPassingMargin(previous);
  184. if (current->clicks >= previous->clicks + passing_margin) {
  185. const int new_index = previous - ordered_categories_.begin();
  186. ntp_snippets::metrics::OnCategoryMovedUp(new_index);
  187. // It is intended to move only by one position per click in order to avoid
  188. // dramatic changes, which could confuse the user.
  189. std::swap(*current, *previous);
  190. }
  191. }
  192. StoreOrderToPrefs(ordered_categories_);
  193. }
  194. void ClickBasedCategoryRanker::OnCategoryDismissed(Category category) {
  195. if (!ContainsCategory(category)) {
  196. LOG(DFATAL) << "The category with ID " << category.id()
  197. << " has not been added using AppendCategoryIfNecessary.";
  198. return;
  199. }
  200. const int penalty = GetDismissedCategoryPenalty();
  201. if (penalty != 0) { // Dismissed category penalty is turned on?
  202. auto current = FindCategory(category);
  203. for (int downgrade = 0; downgrade < penalty; ++downgrade) {
  204. auto next = current + 1;
  205. if (next == ordered_categories_.end()) {
  206. break;
  207. }
  208. std::swap(*current, *next);
  209. current = next;
  210. }
  211. DCHECK(current != ordered_categories_.begin());
  212. auto previous = current - 1;
  213. int new_clicks = std::max(previous->clicks - GetPassingMargin(), 0);
  214. // The previous category may have more clicks (but not enough to pass the
  215. // margin, this is possible when penalty >= 2), therefore, we ensure that
  216. // for this category we don't increase clicks.
  217. current->clicks = std::min(current->clicks, new_clicks);
  218. }
  219. FindCategory(category)->last_dismissed = clock_->Now();
  220. StoreOrderToPrefs(ordered_categories_);
  221. }
  222. base::Time ClickBasedCategoryRanker::GetLastDecayTime() const {
  223. return ReadLastDecayTimeFromPrefs();
  224. }
  225. // static
  226. void ClickBasedCategoryRanker::RegisterProfilePrefs(
  227. PrefRegistrySimple* registry) {
  228. registry->RegisterListPref(prefs::kClickBasedCategoryRankerOrderWithClicks);
  229. registry->RegisterInt64Pref(prefs::kClickBasedCategoryRankerLastDecayTime,
  230. /*default_value=*/0);
  231. }
  232. // static
  233. int ClickBasedCategoryRanker::GetPassingMargin() {
  234. return kPassingMargin;
  235. }
  236. // static
  237. int ClickBasedCategoryRanker::GetNumTopCategoriesWithExtraMargin() {
  238. return kNumTopCategoriesWithExtraMargin;
  239. }
  240. // static
  241. int ClickBasedCategoryRanker::GetDismissedCategoryPenalty() {
  242. return kDismissedCategoryPenalty;
  243. }
  244. ClickBasedCategoryRanker::RankedCategory::RankedCategory(
  245. Category category,
  246. int clicks,
  247. const base::Time& last_dismissed)
  248. : category(category), clicks(clicks), last_dismissed(last_dismissed) {}
  249. // Returns passing margin for a given position taking into account whether it is
  250. // a top category.
  251. int ClickBasedCategoryRanker::GetPositionPassingMargin(
  252. std::vector<RankedCategory>::const_iterator category_position) const {
  253. int index = category_position - ordered_categories_.cbegin();
  254. int passing_margin_increase = 0;
  255. const int num_top_categories_with_extra_margin =
  256. GetNumTopCategoriesWithExtraMargin();
  257. if (index < num_top_categories_with_extra_margin) {
  258. passing_margin_increase =
  259. kExtraPassingMargin * (num_top_categories_with_extra_margin - index);
  260. }
  261. return GetPassingMargin() + passing_margin_increase;
  262. }
  263. void ClickBasedCategoryRanker::RestoreDefaultOrder() {
  264. ordered_categories_.clear();
  265. std::vector<KnownCategories> ordered_known_categories =
  266. ConstantCategoryRanker::GetKnownCategoriesDefaultOrder();
  267. for (KnownCategories known_category : ordered_known_categories) {
  268. AppendKnownCategory(known_category);
  269. }
  270. StoreOrderToPrefs(ordered_categories_);
  271. }
  272. void ClickBasedCategoryRanker::AppendKnownCategory(
  273. KnownCategories known_category) {
  274. Category category = Category::FromKnownCategory(known_category);
  275. DCHECK(!ContainsCategory(category));
  276. ordered_categories_.push_back(
  277. RankedCategory(category, /*clicks=*/0, /*last_dismissed=*/base::Time()));
  278. }
  279. namespace {
  280. base::Time ParseLastDismissedDate(const base::Value::Dict& value) {
  281. // We don't expect the last-dismissed value to be present in all cases (we
  282. // added this after the fact).
  283. const std::string* serialized_value = value.FindString(kLastDismissedKey);
  284. int64_t parsed_value;
  285. if (serialized_value &&
  286. base::StringToInt64(*serialized_value, &parsed_value)) {
  287. return DeserializeTime(parsed_value);
  288. }
  289. return base::Time();
  290. }
  291. } // namespace
  292. bool ClickBasedCategoryRanker::ReadOrderFromPrefs(
  293. std::vector<RankedCategory>* result_categories) const {
  294. result_categories->clear();
  295. const base::Value::List& list = pref_service_->GetValueList(
  296. prefs::kClickBasedCategoryRankerOrderWithClicks);
  297. if (list.size() == 0) {
  298. return false;
  299. }
  300. for (const base::Value& value : list) {
  301. const base::Value::Dict* dictionary = value.GetIfDict();
  302. if (!dictionary) {
  303. LOG(DFATAL) << "Failed to parse category data from prefs param "
  304. << prefs::kClickBasedCategoryRankerOrderWithClicks
  305. << " into dictionary.";
  306. return false;
  307. }
  308. absl::optional<int> category_id = dictionary->FindInt(kCategoryIdKey);
  309. if (!category_id) {
  310. LOG(DFATAL) << "Dictionary does not have '" << kCategoryIdKey << "' key.";
  311. return false;
  312. }
  313. absl::optional<int> clicks = dictionary->FindInt(kClicksKey);
  314. if (!clicks) {
  315. LOG(DFATAL) << "Dictionary does not have '" << kClicksKey << "' key.";
  316. return false;
  317. }
  318. base::Time last_dismissed = ParseLastDismissedDate(*dictionary);
  319. Category category = Category::FromIDValue(*category_id);
  320. result_categories->push_back(
  321. RankedCategory(category, *clicks, last_dismissed));
  322. }
  323. return true;
  324. }
  325. void ClickBasedCategoryRanker::StoreOrderToPrefs(
  326. const std::vector<RankedCategory>& ordered_categories) {
  327. base::Value::List list;
  328. for (const RankedCategory& category : ordered_categories) {
  329. base::Value::Dict dictionary;
  330. dictionary.Set(kCategoryIdKey, category.category.id());
  331. dictionary.Set(kClicksKey, category.clicks);
  332. dictionary.Set(
  333. kLastDismissedKey,
  334. base::NumberToString(SerializeTime(category.last_dismissed)));
  335. list.Append(std::move(dictionary));
  336. }
  337. pref_service_->Set(prefs::kClickBasedCategoryRankerOrderWithClicks,
  338. base::Value(std::move(list)));
  339. }
  340. std::vector<ClickBasedCategoryRanker::RankedCategory>::iterator
  341. ClickBasedCategoryRanker::FindCategory(Category category) {
  342. return std::find_if(ordered_categories_.begin(), ordered_categories_.end(),
  343. [category](const RankedCategory& ranked_category) {
  344. return category == ranked_category.category;
  345. });
  346. }
  347. bool ClickBasedCategoryRanker::ContainsCategory(Category category) const {
  348. for (const auto& ranked_category : ordered_categories_) {
  349. if (category == ranked_category.category) {
  350. return true;
  351. }
  352. }
  353. return false;
  354. }
  355. void ClickBasedCategoryRanker::InsertCategoryRelativeToIfNecessary(
  356. Category category_to_insert,
  357. Category anchor,
  358. bool after) {
  359. DCHECK(ContainsCategory(anchor));
  360. if (ContainsCategory(category_to_insert)) {
  361. return;
  362. }
  363. auto anchor_it = FindCategory(anchor);
  364. ordered_categories_.insert(anchor_it + (after ? 1 : 0),
  365. RankedCategory(category_to_insert,
  366. /*clicks=*/anchor_it->clicks,
  367. /*last_dismissed=*/base::Time()));
  368. StoreOrderToPrefs(ordered_categories_);
  369. }
  370. base::Time ClickBasedCategoryRanker::ReadLastDecayTimeFromPrefs() const {
  371. return DeserializeTime(
  372. pref_service_->GetInt64(prefs::kClickBasedCategoryRankerLastDecayTime));
  373. }
  374. void ClickBasedCategoryRanker::StoreLastDecayTimeToPrefs(
  375. base::Time last_decay_time) {
  376. pref_service_->SetInt64(prefs::kClickBasedCategoryRankerLastDecayTime,
  377. SerializeTime(last_decay_time));
  378. }
  379. bool ClickBasedCategoryRanker::IsEnoughClicksToDecay() const {
  380. int64_t num_clicks = 0;
  381. for (const RankedCategory& ranked_category : ordered_categories_) {
  382. num_clicks += ranked_category.clicks;
  383. }
  384. return num_clicks >= kMinNumClicksToDecay;
  385. }
  386. bool ClickBasedCategoryRanker::DecayClicksIfNeeded() {
  387. base::Time now = clock_->Now();
  388. base::Time last_decay = ReadLastDecayTimeFromPrefs();
  389. if (last_decay == base::Time::FromInternalValue(0)) {
  390. // No last decay time, start from now.
  391. StoreLastDecayTimeToPrefs(clock_->Now());
  392. return false;
  393. }
  394. DCHECK_LE(last_decay, now);
  395. int num_pending_decays =
  396. base::ClampFloor((now - last_decay) / kTimeBetweenDecays);
  397. int executed_decays = 0;
  398. while (executed_decays < num_pending_decays && IsEnoughClicksToDecay()) {
  399. for (RankedCategory& ranked_category : ordered_categories_) {
  400. DCHECK_GE(ranked_category.clicks, 0);
  401. const int64_t old_clicks = static_cast<int64_t>(ranked_category.clicks);
  402. ranked_category.clicks =
  403. old_clicks * kDecayFactorNumerator / kDecayFactorDenominator;
  404. }
  405. ++executed_decays;
  406. }
  407. // No matter how many decays were actually executed, all of them are marked
  408. // done. Even if some were ignored due to absense of clicks, they would have
  409. // no effect anyway for the same reason.
  410. StoreLastDecayTimeToPrefs(last_decay +
  411. num_pending_decays * kTimeBetweenDecays);
  412. if (executed_decays > 0) {
  413. StoreOrderToPrefs(ordered_categories_);
  414. return true;
  415. }
  416. return false;
  417. }
  418. } // namespace ntp_snippets