Name
Abstract | ||
|---|---|---|
We consider the problem of inferring choices made by users based only on aggregate data containing the relative popularity of each item. We propose a framework that models the problem as that of inferring a Markov chain given a stationary distribution. Formally, we are given a graph and a target steady-state distribution on its nodes. We are also give a mapping from per-node scores to a transition matrix, from a broad family of such mappings. The goal is to set the scores of each node such that the resulting transition matrix induces the desired steady state. We prove sufficient conditions under which this problem is feasible and, for the feasible instances, obtain a simple algorithm for a generic version of the problem. This iterative algorithm provably finds the unique solution to this problem and has a polynomial rate of convergence; in practice we find that the algorithm converges after fewer than ten iterations. We then apply this framework to choice problems in online settings and show that our algorithm is able to explain the observed data and predict the user choices much better than other competing baselines across a variety of diverse datasets. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2684822.2685310 | WSDM |
Keywords | Field | DocType |
steady-state distributions,miscellaneous,choice theory,transition matrix,markov chains | Data mining,Mathematical optimization,Stochastic matrix,Polynomial,Iterative method,Computer science,Markov chain,Rate of convergence,Stationary distribution,Aggregate data,SIMPLE algorithm | Conference |
Citations | PageRank | References |
2 | 0.46 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ravi Kumar | 1 | 13932 | 1642.48 |
| Andrew Tomkins | 2 | 9388 | 1401.23 |
| Sergei Vassilvitskii | 3 | 2750 | 139.31 |
| Erik Vee | 4 | 747 | 43.61 |