=Paper=
{{Paper
|id=Vol-1247/recsys14_poster15
|storemode=property
|title=Long Term Recommender Benchmarking for Mobile Shopping List Applications using Markov Chains
|pdfUrl=https://ceur-ws.org/Vol-1247/recsys14_poster15.pdf
|volume=Vol-1247
|dblpUrl=https://dblp.org/rec/conf/recsys/SchopferK14
}}
==Long Term Recommender Benchmarking for Mobile Shopping List Applications using Markov Chains==
https://ceur-ws.org/Vol-1247/recsys14_poster15.pdf
Long Term Recommender Benchmarking for Mobile
Shopping List Applications using Markov Chains
Sandro Schopfer Thorben Keller
Chair of Information Management Cosibon AG
ETH Zurich, Switzerland St.Gallen, Switzerland
sandro.schopfer@ethz.ch thorben.keller@cosibon.com
ABSTRACT for some period of time while cyclically changing the status
This paper presents a method to estimate the performance between to be purchased and purchased and eventually ter-
and success rate of a recommender system for digital shop- minate in the state deleted. Under these circumstances, the
ping lists. The list contains a number of items that are success rate of a recommended product can be continuously
allowed to occupy three different states (to be purchased, evaluated given a certain type of recommender system. Fur-
purchased and deleted ) as a function of time. Using Markov thermore, the durability horizon and therewith the probabil-
chains, the probability distribution function over time can be ity that a recommended item will be purchased repetitively
estimated for each state, and thus, the probability that a rec- can be characterized. Recommendation applied to digital
ommendation is deleted from the list can be used to bench- shopping list is unique in one point: no purchase data from
mark a recommender on its endurance and performance. An the retailer is needed to build a recommender and to esti-
experimental set up is described that allows to test the pre- mate its performance.
sented method in an actual mobile application. The appli- The present paper describes a methodology and an exper-
cation of the method will allow to benchmark a variety of imental set up which allows to benchmark different kinds
recommenders. An outlook is given on how the presented of recommender systems with respect to their success rate.
method can be used iteratively to support a recommender A recommender system can be benchmarked based on the
in finding the user’s favourite items/products. probability that a recommended item is still actively used
in the list after some time it has been suggested to the user.
1. INTRODUCTION 2. METHODOLOGY
Shopping lists have served for many decades as a tool This section presents a method that allows to determine
to keep track of items to be purchased in physical stores. the performance of a recommendation. A straight forward
Consequently, shopping lists have been subject to a vast solution to this problem is to track whether a recommended
amount of scientific studies [2], [3] and [4]. product has been accepted and consequently added to the
With further advancement of mobile computing, the tra- list (in state to be purchased ). However, this study aims to
ditional hand-written shopping list has been digitalized and investigate the long term effect and therewith the durability
implemented as mobile applications. Many applications with of a recommended item. To that end, this section presents a
different degrees of functionality have been deployed for all model for long term analysis of a recommended item using
major mobile platforms. However, at the core they share the Markov chains.
same functionality represented by one or more lists consist- A shopping list is represented as a vector
ing of items which are displayed to and modified by the user I(t) = (I1 (t), I2 (t), . . . , In (t))T with n items, where each
in one of three possible states (to be purchased, purchased item Ik (t) corresponds to a stochastic process continuous
or deleted ). Such a shopping list can potentially serve as in time t with finite state space S = {−1, 0, 1} which cor-
a commercial platform which is realized as a brand recom- responds to deleted, purchased and to be purchased, respec-
mendation system. Usually, recommendations on a mobile tively.
platform or web store occur based on popular items that
are suggested to the user only once during a shopping ses-
sion and rely heavily on purchase data. If the recommended
item has been bought, the recommendation is considered to −1 0 1
be successful. However, the items of a shopping list remain
To be
Deleted Purchased
purchased
Figure 1: State space of a dynamic shopping list
These definitions allow the application of the theory and
formalism of time continuous Markov processes with three
Copyright is held by the author/owner(s).
RecSys 2014 Poster Proceedings, October 6-10, 2014, Foster City, Silicon discrete states for each item. The state space of the sys-
Valley, USA. tem with its possible transitions is visualized in Figure 1.
The probability that an item k occupies a state at time t is 3. EXPERIMENTAL SETUP
formally summarized in the vector A generic shopping list application – currently under de-
π k (t) =
(1) (2)
(πk , πk , πk )T
(3) velopment – will be exposed to a broader audience to gen-
erate item data. Grocery items are chosen as experimental
= (P [Ik (t) = −1] , P [Ik (t) = 0] , P [Ik (t) = 1])T context, but the methodology may be applied to other types
We define that every recommended item will be initialized of items as well. A master data set that maps electronic arti-
in the state 1 to be purchased with π k (t = t0k ) = (0, 0, 1)T cle numbers (EAN) to product names and categories serves
where t0k represents the point in time when item k is recom- as a basis for this application. Thus, the user can add/delete
mended. The occupancy probability over time for each state items in accordance with the master data set and change
is governed by the Master Equation (1) with the solution (2) the status Ik (t) of each item, depending on wheter the item
needs to be purchased or not.
d Using a selection of recommender systems, alternative and/or
πk = πk Q (1)
dt complementary items may be recommended. In reference
π k (t) = π k (t0k ) · exp (t − t0k )Q
(2) with Figure (1), a recommended product k may be placed in
to state 1 to be purchased at t = t0k if accepted by the user. In
where Q describes the transition rate matrix and represents
case of acceptance, item k cyclically populates through the
the probability that the process changes from state i to state
states Ik (t) as illustrated in Figure (2). Each item and action
j per infinitesimal time interval dt. In this context Q is not
of a user will be logged to a database allowing straightfor-
given, but can be estimated using a trajectory Ik (t) which
ward insights into the item dynamics using the methodology
is a sample of Ik (t) as shown in Figure (2).
presented in the previous chapter.
Ik
4. EVALUATION & OUTLOOK
1
4.1 Recommender Benchmarking
As a benchmarking score we define the probability of re-
(1)
0 t jecting a recommended item πk at a specified ∆tk = t − t0k .
In general this score will depend on the user, the recom-
t0k mender system (implicitly the item) used and the time ∆tk
-1 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 dif-
ferent users, products, and periods of time ∆tk . The lower
Figure 2: Visualization of a possible trajectory of a the benchmark score, the better the performance of the rec-
recommended item ommender.
Once the transition rate matrix is known, the probabil- 4.2 Outlook: Iterative Recommendation
ity distribution π k for all states at all times t ≥ t0k can be
computed using the solution of the Master Equation (2). Of It is assumed that within the context of a shopping list,
particular interest is the probability that the process of an an ideal recommender is characterized with infinite lifetime
item occupies the deleted state as this yields a direct feed- which implies that the probability that the process occupies
back on how likely a recommended product will be rejected state −1 is below a critical value. This fact may be used
after some time the item has been recommended to the user to rank all used recommenders [1] during operation across
at t = t0k as illustrated in Figure (3). different users to help them to find their favourite products
that reside in the list for long periods of time. This may
πk (1)
be obtained by minimizing πk (t), and successively replac-
(3) ing a rejected recommender until the user finds stationary
1 πk (1)
πk items/products that reside over long periods of time in the
list.
(2) 5. REFERENCES
πk [1] P. Nurmi et al. Promotionrank: Ranking and
recommending grocery product promotions using
0 t personal shopping lists. ACM Transactions on
t0k Interactive Intelligent Systems, 4(1), 2014.
[2] A. Thomas and A. Garland. Supermarket shopping
Figure 3: Distribution of the probability for state lists: their effect on consumer expenditure.
occupation over time International journal of distribution management,
22(2), 1993.
The probability that a recommended item ends up in the [3] A. Thomas and A. Garland. Grocery shopping: list and
deleted state −1 is given by the first component of Equation non-list usage. Marketing Intelligence and Planning,
(1)
(2), which is πk (t). The probability of rejecting a recom- 22(6), 2004.
(1) [4] F. J. Webster and F. Pechmann. A replication of the
mended item πk (t) can be used as a benchmark score for
different recommenders, users and observed period ∆tk . ”shopping list” study. Journal of Marketing, 34(2), 1970.