Local Optimality of User Choices and Collaborative Competitive Filtering

1 Introduction

• CF uses chosen action dyads but disregards the offered context, even though choices among alternatives can reveal preferences that a choice alone does not.For example, choosing Die Hard over Terminator or Rocky may suggest a preference for Bruce Willis over other action heroes.Source: §1 · p. 2
• Users choose among competing items, but this local competition effect is absent from many collaborative-filtering approaches.Items compete for users’ attention, so the choice depends on the alternatives presented.Source: §1 · p. 3
• CCF uses a multiplicative latent-factor model for dyadic utility and learns from both chosen items and nonchosen items in the offered context.It presents two formulations and an efficient large-scale optimization algorithm.Source: §1 · pp. 3–4
• On a commercial recommender, CCF improved offline top-k ranking by up to 7% and online click rate prediction by up to 13% over CF models.Across two dyadic datasets, it also improved offline top-k ranking by up to 50+%.Source: §1 · p. 4

2.1 Problem formulation

• Each interaction session records a user, the offered item set, and the decision; the system aims to maximize satisfaction for a future visit.The formulation temporarily assumes one chosen item, while noting that more general choices are discussed later.Source: §2.1 · pp. 4–5

2.2 Collaborative filtering

• Collaborative filtering estimates dyadic user-item responses from sparse observations, using neighborhood or latent-factor models to predict missing responses.Latent-factor models associate vectors with users and items and use their multiplicative relationship to model dyadic responses.Source: §2.2 · pp. 5–6

2.3 Motivating discussions

• CF typically trains on chosen action dyads and treats other items in the offered set as missing, leaving choice behavior and local competition unmodeled.For binary responses, this can leave only positive observations and produce overly optimistic estimates that favor positive predictions.Source: §2.3 · pp. 6–7

3 Collaborative competitive filtering

• CCF is a framework for recommender learning that models the user-system interaction process.Its key insight is to account for the context in which each user decision is made.Source: §3 · p. 7
• A user’s decision can change with the offered context, including when a more interesting item is added to the set.An item cannot be chosen if it is not presented to the user.Source: §3 · p. 7
• The framework develops choice-behavior axioms, CCF learning formulations, optimization algorithms, implementation techniques, and extensions.Source: §3 · p. 7

3.1 Local optimality of user choices

• In an opportunity give-and-take interaction, the system offers a set of opportunities and the user selects one that may yield utility.Source: §3.1 · p. 8
• The user is assumed to compare only items in the offered set, with opportunity cost defined by the best utility among the alternatives excluded by a choice.Profit is the chosen item’s utility minus that opportunity cost.Source: §3.1 · p. 8
• A rational decision maximizes profit, so the chosen item is locally optimal within its offered set.Source: §3.1 · p. 8

3.2 Collaborative competitive filtering

• The local-optimality constraint alone permits arbitrary order-preserving utility transformations and is computationally intractable with its max operator, motivating two efficient surrogate objectives.The surrogates have close connections to existing models.Source: §3.2 · pp. 8–9

3.2.1 Softmax model

• The softmax model combines deterministic latent-factor utility with i.i.d. Weibull choice noise, using multinomial logit as a softmax surrogate for the local-optimality constraint.Source: §3.2.1 · p. 9

3.2.2 Hinge model

• The hinge model compares chosen-item utility with the average potential utility of non-chosen items, treating that average as a negative preference.It is related to maximum score estimation of the multinomial logit model and maximizes the marginal utility between the choice and average non-choices.Source: §3.2.2 · p. 10

3.2.3 Complexity

• O(|I| × |O|) learning complexity matches rating-oriented CF when offer sets are small, whereas ranking-oriented CF costs O(|I|^2) per user.The paper gives offer sizes of 7 movies for Netflix and 4 news items for Yahoo! as examples.Source: §3.2.3 · p. 10

• CCF’s bilinear terms make both variants nonconvex, while convex reformulations can be impractical at scale; changing interactions also motivate incremental, dynamically updateable learning.The cited offline SVD and spectral methods involve large-scale matrices.Source: §3.3 · p. 11
• Stochastic gradient descent updates parameters over observations and decouples across interactions and users, enabling parallel implementation.A distributed averaging variant runs optimization on interaction-trace sub-blocks in MapReduce and combines item-factor results in the Reduce phase.Source: §3.3 · p. 11
• Feature hashing maps latent factors with random collisions to keep the representation in memory and accelerate optimization on large-scale data.The paper notes that 100 million users with 100 latent dimensions each would require 40 GB of RAM.Source: §3.3 · p. 12

3.4 Extensions

• The extensions address both interactions with no response and settings where user or item features are observable.Source: §3.4 · p. 12

Sessions without response

• For sessions with no action, a user-specific threshold represents the action level required for the offered items to warrant attention; the model assigns no response the remaining probability.The hinge extension uses a trade-off constant C to calibrate the importance of non-responses.Source: Sessions without response · pp. 12–13

Content features

• Combining latent and observable user and item features lets the utility model use content information for unseen users or items, where interaction observations are unavailable during training.With non-informative observable features the model reduces to factorization-style utility; with irrelevant latent factors it becomes a content-based relevance model.Source: Content features · pp. 13–14

4.1 Dyadic response data

• The dyadic tests use two datasets with simulated choice contexts because the datasets lack offer-set context information.The experiments also evaluate commercial session data with logged offer sets; the dyadic setup samples nine missing dyads as pseudo non-choices for each positive response.Source: §4 · p. 14, §4.1 · p. 17
• On Social, CCF improves AP@5 by 52.8%–53.6%; on Netflix-5 star, by 37.0%–37.8%, compared with CF.CCF also outperforms CF in AR@5 by up to 13.5% on Social and 30% on Netflix-5 star; the reported improvements are statistically significant.Source: Table 3 · p. 16, §4.1 · p. 17

4.2 User-system interaction data

• Up to 6.9% in average precision, 6.5% in average recall, and 7.5% in nDCG gains over CF, with all improvements significant.The offline comparison used training subsets of 30%, 50%, and 70%.Source: §4.2 · p. 19, Table 4 · p. 19
• On online predicted-click-probability tests for four-item offer sets in user-system interaction data, CCF models significantly outperformed the 0.25 random predictor and improved 11.3%–12.7% over two CF competitors.Source: §4.2 · p. 20, Table 5 · p. 20
• Offline nDCG curves are typically inverted U-shaped, with dimensionality around 10 and regularization weight around 0.0001 yielding the best performance for both CCF models.These values were the default settings used for the reported results.Source: Figure 2 · p. 21, §4.2 · p. 22
• Actual nonresponded sessions were unavailable, and a preliminary test using pseudo nonresponded sessions showed no significant performance improvement.The authors attribute this likely to an invalid surrogate distribution and leave analysis with more realistic data for future work.Source: §4.2 · p. 22

5 Related Work

• Prior CF work mainly approximates user-assigned ratings or recovers ordinal rankings from ratings [29, 16].Source: §5 · p. 22
• CF approaches model dyadic responses or ratings-derived rankings, whereas CCF reports better recommender performance when it also encodes local competition in user choices.The cited CF approaches include neighborhood-based and latent-factor methods.Source: §5 · pp. 22–23
• CCF’s multinomial-logit formulation follows random utility theory, while its hinge formulation relates to web-search pairwise preference learning.The hinge formulation uses multiplicative latent factors rather than learning a feature mapping as in.Source: §5 · p. 23

6 Summary and future research

• CCF models contexts in user decisions alongside action events, and the paper reports effective approaches with experiments on three large-scale real-world recommendation datasets.Source: §6 · p. 23
• The choice model assumes users decide solely by comparing utilities, leaving budgeted attention and position bias for future consideration.Users may attend only to a few top-ranked items and disregard others; the paper notes this bias in web search and recommendation.Source: §6 · pp. 23–24
• The paper assumes the recommender follows a deterministic strategic policy, while adaptive responses and inventory or promotion constraints remain outside its current analysis.The authors propose extending the analysis to model interaction between users and the recommender.Source: §6 · p. 24
• Data-collection constraints leave some parts of the proposed models without strict empirical evaluation, prompting planned further experiments.Source: §6 · p. 24