This paper presents a method to estimate the performance and success rate of a recommender system for digital shopping lists. The list contains a number of items that are allowed to occupy three different states (to be purchased, purchased and deleted ) as a function of time. Using Markov chains, the probability distribution function over time can be estimated for each state, and thus, the probability that a recommendation is deleted from the list can be used to benchmark a recommender on its endurance and performance. An experimental set up is described that allows to test the presented method in an actual mobile application. The application of the method will allow to benchmark a variety of recommenders. An outlook is given on how the presented method can be used iteratively to support a recommender in finding the user's favourite items/products.
Shopping lists have served for many decades as a tool to keep track of items to be purchased in physical stores. Consequently, shopping lists have been subject to a vast amount of scientific studies [2], [3] and [4].
With further advancement of mobile computing, the traditional hand-written shopping list has been digitalized and implemented as mobile applications. Many applications with different degrees of functionality have been deployed for all major mobile platforms. However, at the core they share the same functionality represented by one or more lists consisting of items which are displayed to and modified by the user in one of three possible states (to be purchased, purchased or deleted ). Such a shopping list can potentially serve as a commercial platform which is realized as a brand recommendation system. Usually, recommendations on a mobile platform or web store occur based on popular items that are suggested to the user only once during a shopping session and rely heavily on purchase data. If the recommended item has been bought, the recommendation is considered to be successful. However, the items of a shopping list remain for some period of time while cyclically changing the status between to be purchased and purchased and eventually terminate in the state deleted. Under these circumstances, the success rate of a recommended product can be continuously evaluated given a certain type of recommender system. Furthermore, the durability horizon and therewith the probability that a recommended item will be purchased repetitively can be characterized. Recommendation applied to digital shopping list is unique in one point: no purchase data from the retailer is needed to build a recommender and to estimate its performance.
The present paper describes a methodology and an experimental set up which allows to benchmark different kinds of recommender systems with respect to their success rate. A recommender system can be benchmarked based on the probability that a recommended item is still actively used in the list after some time it has been suggested to the user.
This section presents a method that allows to determine the performance of a recommendation. A straight forward solution to this problem is to track whether a recommended product has been accepted and consequently added to the list (in state to be purchased ). However, this study aims to investigate the long term effect and therewith the durability of a recommended item. To that end, this section presents a model for long term analysis of a recommended item using Markov chains.
A shopping list is represented as a vector I(t) = (I1(t), I2(t), . . . , In(t)) T with n items, where each item I k (t) corresponds to a stochastic process continuous in time t with finite state space S = {−1, 0, 1} which corresponds to deleted, purchased and to be purchased, respectively.
Deleted Purchased To be purchased These definitions allow the application of the theory and formalism of time continuous Markov processes with three discrete states for each item. The state space of the system with its possible transitions is visualized in Figure 1.
The probability that an item k occupies a state at time t is formally summarized in the vector
We define that every recommended item will be initialized in the state 1 to be purchased with π k (t = t 0 k ) = (0, 0, 1) T where t 0 k represents the point in time when item k is recommended. The occupancy probability over time for each state is governed by the Master Equation (1) with the solution (2)
where Q describes the transition rate matrix and represents the probability that the process changes from state i to state j per infinitesimal time interval dt. In this context Q is not given, but can be estimated using a trajectory I k (t) which is a sample of I k (t) as shown in Once the transition rate matrix is known, the probability distribution π k for all states at all times t ≥ t 0 k can be computed using the solution of the Master Equation (2). Of particular interest is the probability that the process of an item occupies the deleted state as this yields a direct feedback on how likely a recommended product will be rejected after some time the item has been recommended to the user at t = t 0 k as illustrated in Figure (3). The probability that a recommended item ends up in the deleted state −1 is given by the first component of Equation ( 2), which is π
A generic shopping list application -currently under development -will be exposed to a broader audience to generate item data. Grocery items are chosen as experimental context, but the methodology may be applied to other types of items as well. A master data set that maps electronic article numbers (EAN) to product names and categories serves as a basis for this application. Thus, the user can add/delete items in accordance with the master data set and change the status I k (t) of each item, depending on wheter the item needs to be purchased or not.
Using a selection of recommender systems, alternative and/or complementary items may be recommended. In reference with Figure (1), a recommended product k may be placed in to state 1 to be purchased at t = t 0 k if accepted by the user. In case of acceptance, item k cyclically populates through the states I k (t) as illustrated in Figure (2). Each item and action of a user will be logged to a database allowing straightforward insights into the item dynamics using the methodology presented in the previous chapter.
As a benchmarking score we define the probability of rejecting a recommended item π (1) k at a specified ∆t k = t − t 0 k . In general this score will depend on the user, the recommender system (implicitly the item) used and the time ∆t k that passed after the item has been recommended to the user. Hence, the experiment will reveal how successful a recommender system performs during its "lifetime" for different users, products, and periods of time ∆t k . The lower the benchmark score, the better the performance of the recommender.
It is assumed that within the context of a shopping list, an ideal recommender is characterized with infinite lifetime which implies that the probability that the process occupies state −1 is below a critical value. This fact may be used to rank all used recommenders [1] during operation across different users to help them to find their favourite products that reside in the list for long periods of time. This may be obtained by minimizing π (1) k (t), and successively replacing a rejected recommender until the user finds stationary items/products that reside over long periods of time in the list.