We present our preliminary ideas for developing SoCRATe, a framework and an online system dedicated to providing recommendations to users when items' availability is limited. SoCRATe is relevant to several real-world applications, among which movie and task recommendations. SoCRATe has several appealing features: it watches users as they consume recommendations and accounts for user feedback in refining recommendations in the next round, it implements loss compensation strategies to make up for sub-optimal recommendations, in terms of accuracy, when items have limited availability, and it decides when to re-generate recommendations on a need-based fashion. SoCRATe accommodates real users as well as simulated users to enable testing multiple recommendation choice models. To frame evaluation, SoCRATe introduces a new set of measures that capture recommendation accuracy over time as well as throughput and user satisfaction. All these features make SoCRATe unique and able to adapt recommendations to user preferences in a resource-limited setting.
The goal of a recommendation system is to produce a set of items that are highly relevant
to a user. A typical recommendation workflow takes historical user data, applies a strategy
that produces relevant recommendations, and measures accuracy [
Formalizing adaptive recommendations and developing an online system that enables them must address several new challenges. The first challenge C1 is to model user behavior, i.e., how users consume recommendations, and capture both explicit and implicit feedback. Explicit feedback represents the actions taken by the users when provided with recommendations. Examples of actions include rating movies, and completing a task. When users are simulated, diferent assumptions can be made to reflect how they choose their recommendations. When users are real, their explicit choice of items out of recommended ones needs to be captured. Additionally, several implicit signals can be represented, including the order and speed at which they consume recommendations. The second challenge C2 is to determine at what moment and for which users recommendations are re-optimized based on their behavior and feedback. The third challenge C3 is to leverage the observed feedback to refine recommendations in the next iteration. This challenge is coupled with the need to be adaptive regardless of the recommendation strategy. This allows us to deploy a generic solution on top of any recommender. It also raises the question of managing how users compete on recommendations. Indeed, when the number of instances of an item is limited (referred to as availability), some users may not get an item even if it is in their top choices. This may happen, e.g., in book recommendation, in case a limited number of copies of a physical book exists, or in crowdsourcing, where the number of workers who complete the same task is limited. Addressing these challenges will enable us to develop SoCRATe, a framework and a system to produce recommendations, evaluate them, and refine them on the fly in order to comply with user behavior.
SoCRATe has several appealing features: it watches recommendation consumption and decides when to apply a loss compensation strategy to make up for sub-optimal recommendations due to limited item availability.
To address C1, we introduce an objective function in the form of a linear combination of
several dimensions that capture users’ strategic behaviors when consuming recommendations.
For instance, when presented with a list of movie recommendations, users may choose highly
relevant items (utility-based) while also favoring items that are diferent from each other
(diversity). In the case of crowdsourcing, users may pick tasks that are relevant to their profile
(utility-based) while also looking for tasks posted by diferent requesters (diversity) and with
high compensation (payment). We devise a generic objective function where each dimension
receives a weight according to a user’s choice model. When users are simulated, SoCRATe
assumes that they choose out of provided recommendations according to one of three
common choice models [
To address C2, we develop three temporal granularities: fixed , where recommendations of all users are re-optimized at fixed time periods; single-user, where the best moment for re-optimizing recommendations is determined for each user separately as a function of when the user is done and ready to receive new recommendations; and user-group, where the best moment is determined for a group of users as a function of when they are all ready.
To address C3, SoCRATe captures each user’s feedback as a weight vector, where each entry represents the preference of a user for an optimization dimension. This representation is generic enough to capture a variety of applications. To refine weight vectors, SoCRATe runs a regression that compares the chosen recommendations against the remaining − . Refined weight vectors are used to re-rank the recommendations produced for each user to match their feedback. Due to limited item availabilities in some applications, users may compete for some items and not receive their optimal recommendations. Hence, we model the loss for a user as the diference between the proposed recommendations and the optimal recommendations that would have been returned to the user if other users were not considered. This loss is leveraged in the next iteration to compensate users, either individually or in groups according to the temporal granularity. We develop two loss compensation strategies: preference-driven, where users are compensated in decreasing loss order by receiving recommendations in preference order before the user with the next smaller loss is served, and round-robin, where users are considered in decreasing loss order but items are recommended to them in round-robin with respect to item availability.
Our work relates to sequential recommendations [
Our work also relates to observing users and modeling an objective function accordingly.
We propose to generalize the work in [
We present the data model of SoCRATe and the problem variants we plan to tackle.
We are given a set of users and a set of items . Each item ∈ has an availability, avail (, ), that represents the number of copies left of item at time . At a given timestamp , a list of recommendations ⊆ is provided to a user ∈ . The list of optimal recommendations, in terms of accuracy, a user could get at time is referred to as . Due to the presence of other users and limited item availability, may difer from . When user receives a list of recommendations , may choose to adopt a list ⊆ of size ≤ to consume. The user choice incurs the computation of a weight vector that represents the importance the user gives to the dimensions of an objective function . The lists and are used to compute , a vector of losses (one entry per dimension in ) for user at time .
Our framework raises several problem variants we plan to tackle in the future. We may formulate the problem of determining the best time granularity and compensation strategy that reduce cumulated loss. We may formulate another problem where the optimization goal is to reduce users’ idling time. We may again formulate another problem where the goal is to optimize item throughput. All these problem variants give rise to hard problems for which eficient greedy solutions will be designed.
For instance, the problem of refining recommendations in such a way that previously incurred loss is minimized can be expressed as: for each user, find a list , s.t.: ∑︁ − 1 × − 1
∈
Our problem is a variant of the Knapsack Problem [
The architecture of SoCRATe is provided in Figure 1. The Orchestrator (1) is in charge of determining the moment at which recommendations are re-generated for individuals or for user groups. It monitors when users are done consuming recommendations from the previous iteration and uses that to determine when to re-generate recommendations and start the next iteration. It implements our three time granularity splits: fixed , single-user, and user-group. It makes use of the recommendations adopted by users (2), and triggers the Weight Update (3) module to obtain the new weights. Weight computation admits , − 1, − 1 and returns the updated weights . Following that, the Individual Recommender module (4) is CHOICE MODEL 2 WEIGHT UPDATE 3
INDIVIDUAL 4 RECOMMENDER
COMPENSATION STRATEGY USER 5 SORTING
6 RECOMIMTEEMNDATION
COMLPOUSTASTIO7N called to produce new recommendations based on the weights associated to each user. This module returns , which is fed to the Compensation Strategy module. Here the User Sorting module (5) sorts users according to their loss and calls the Item Recommendation module (6). This module implements two strategies: preference-driven and round-robin. The output is a set of new recommendations that are fed to the Loss Computation module (7) to compute each user’s incurred loss. SoCRATe then iterates by calling the Orchestrator.
Algorithm 1 is generic. It contains the main steps of our solution regardless of the problem we tackle (Section 3.2). It is illustrated for fixed time, the same applies to single-user and user-groups. It takes as input , the moment where a new iteration starts according to the Orchestrator, and for each user , − 1, − 1, − 1, − 1. It outputs for each user , , , . The line numbers in the overall algorithm reflect the module numbers in Figure 1).
Input: ∀, − 1, − 1, − 1, − 1
Output: ∀, , , , 1: for all ∈ do 2: ← ChoiceModel(− 1) 3: ← WeightUpdate(− 1, − 1, − 1, ) 4: ← IndividualRecommender() 5: ← UserSorting(, − 1,) 6: ← ItemRecommendation( , , ∀, (, )) 7: ← LossComputation(, ) 8: end for
We now focus on lines 5 and 6 which correspond to the compensation strategy. Each strategy receives a list of users sorted in decreasing loss, , the optimal recommendations, in terms of accuracy, for each user, , the availability for each item, avail (, ), and produces a list of recommended items for each user, .
When the preference-based compensation strategy is adopted (see Algorithm 2), N items are recommended to the first user in the sorted list of users before moving to the next one in the list. The round-robin variant (see Algorithm 3) recommends one item at a time to each user (according to the order dictated by the sorted list of users), until N items are recommended to each user.
Choosing the right compensation strategy is crucial when there is a limited set of items that are very popular among all users and when the availability of these items is limited and not suficient to satisfy all the users. The preference-based compensation strategy is expected to be more efective at maximizing the satisfaction of the first users in the list. As a result, this strategy should be preferred when the system detects that some users are unsatisfied with the recommendations they are getting, and thus may be prone to abandon the system, thereby afecting overall user retention. On the other hand, the round-robin compensation strategy should be preferred when the main concern is to consume as many items as possible. In fact, when adopting this compensation strategy, it is very likely that all users get at least a few items they like, which will afect their consumption rate.
Input: , , (, ) 1: for all ∈ do 2: for ← 1 to do 3: ← pop() 4: while is available do 5: ← pop() 6: end while 7: ← ∪ 8: (, + 1) ← (, ) − 1 9: end for 10: end for 11: return ∀, Availability = Low = 1 Preference-Based
Round-Robin 1 u1 A B C D 3
The example in Figure 2 illustrates the diference between our compensation strategies. In the left part, users have similar recommendations (i.e., similar item rankings) and item availability is low (= 1). In the right part, their recommendations difer. We can see that on the left, preferencebased favors 1 and round-robin treats 1 and 2 similarly. On the right, the two compensation strategies behave similarly. A deeper exploration of compensation is therefore warranted.
We presented our plan to develop SoCRATe, a framework and online system that watches users as they choose and consume items and refines upcoming recommendations accordingly. SoCRATe raises three novel challenges: how to model user behavior, when and for whom the recommendations should be re-generated, and how to leverage user feedback to refine recommendations and compensate users for the loss incurred in previous iterations. In this paper, we describe our preliminary solution, including a formalization, an architecture, a set of algorithms, and a revised set of evaluation measures to address our challenges.
Our work opens many new perspectives. First, we plan to formalize a series of optimization
problems following the discussion in Section 3.2. In doing so, we will strive to preserve the
genericity of our solution (Algorithm 1). That will allow us to explore new opportunities in
addressing challenges C2 and C3. One compensation strategy we want to formalize is to account
for consumer fairness by adding notions such as statistical parity [
Second, we have started implementing a first in-memory version of our online system
SoCRATe. We are currently investigating an in-DBMS implementation of the diferent
components of SoCRATe. Being able to create and maintain dynamic user profiles in a DBMS has
many appealing features, including the ability to query evolving user profiles. This will require
to incorporate learning and optimizing user recommendations as a foundational extension
of the relational algebra. Queries over profiles will be handled within the relational query
runtime without exfiltrating data into memory. This will also open new directions in DB/ML
cross-optimizations, such as pushing predicates and model inlining. Existing frameworks such
as Raven and its runtime environment ONNX [
Our third endeavor is to complete the implementation of our system and design an evaluation framework. To evaluate recommendations in SoCRATe, we must revisit traditional accuracy measures and combine them with user-aware measures. A particular focus must be put on capturing users’ satisfaction by measuring precision and recall as well as user retention. Precision will be revisited to measure the number of items the user appreciated over all adopted items. Appreciation may correspond to a high rating in the case of movie recommendation or a good quality contribution (wrt a ground-truth) in the case of task recommendation. Recall will be measured as a function of the number of adopted items over all recommended items. Retention will measure the percentage of users who leave after a certain number of iterations. Other measures such as item throughput will capture the speed at which items are consumed wrt their availabilities. These measures can be computed for individual users or for user groups; not all measures will be possible, depending on whether we work with simulated or real users. We are indeed considering a novel setting where semi-synthetic data will be generated using as input real users’ data and expanding it to simulate diferent users and choice models. This will allow us to develop a preliminary benchmark for adaptive recommendations.