Inferring random variables from their sum

Question

Suppose I have a large set of receipts that list the items I bought, but only list the total cost. One day I might have bought Milk, Butter, and Eggs. A different day I might have bought Bread, Milk, and Cereal. What I would like to do is fit a distribution of the price of each item.

To keep things simple, let's assume the price of each item is modeled by a Gaussian distribution (probably not ideal, since the prices can't be negative, but we'll start with this). And to make things even simpler, I assume that the distributions of Bread, Milk, etc. are independent from one another.

This means that $\mu_{total} = \mu_{Bread} + \mu_{Eggs} + ...$ and $\sigma^2_{total} = \sigma^2_{Bread} + \sigma^2_{Eggs} + ...$, which seems like it should make things straightforward. Here's what I've tried that didn't work:

• My first thought was to find MLE estimates for each of the $\mu_{Bread}$, etc. However, when I take the partial derivatives of the log-likelihood function, I get a function that also depends on all the other $\mu_{Eggs}, \mu_{Milk}$, etc.

• That made me think that maybe I should use EM, but I can't think of what would be the latent variable here.

• I considered stochastic gradient descent, but I'm worried that the space will be non-convex.

• I've also thought about using a Gaussian mixture model, but that doesn't seem appropriate since each receipt doesn't come from a single sub-population.

What would be a good way to infer the $\mu$ and $\sigma$ for each individual item?

Answer 1

Since you know the total cost of each purchase and the number of items of each type for each purchase, you can model the purchases

$Y = \beta_0 + \beta_{bread}*X_{bread} + \beta_{eggs}*X_{eggs} + \beta_{milk}*X_{milk} + \epsilon$

where $X_{item}$ is the number of that item in the purchase, and use regression to estimate the parameters. In this model, $\beta_{item}$ represents the average cost of that item across the population.

Answer 2

As jsk stated, linear regression can be used to estimate the prices of items. One disadvantage, however, of using linear regression is that it models mean values for each item, but groups all the error into a single $\epsilon$ term at the end. This means that, for example, it doesn't give you a good way to model how much the price of butter varies. You only know what the typical price of butter is.

It turns out that it is actually possible to solve this using an EM algorithm. In its simplest form, it models the price of each item $i$ as being distributed according to $\mathcal{N}(\mu_i, \sigma_i^2)$. Each $\mu_i$ and $\sigma_i^2$ is initialized to a reasonable value, such as the price that linear regression estimated. (a reasonable initial estimate makes the algorithm converge more quickly).

You can think of EM as using latent variables to successively approximate the parameters of the distributions. The latent variables here are the actual prices of individual items on each receipt, which we do not observe. We can call them $c_{i,j}$, which is the (latent) price of item $j$ on receipt $i$. We'll also let $x_{i,j}$ denote the number of item $j$ that were bought on receipt $i$ and $t_i$ denote the total cost listed on receipt $i$. The steps of the algorithm are then:

E-step: Find the latent prices for each receipt that have maximum probability according to the set of $\mathcal{N}(\mu_i, \sigma_i^2)$. This is a constrained optimization problem, where $\sum_{j=1}^{m} c_{i,j} x_{i,j} = t_i$. There are multiple ways you could solve it, but I used variable elimination and projected gradient descent to solve this optimization sub-problem.

M-step: With the $c_{i,j}$ estimates in hand, each of the $\mu_i$ and $\sigma_i^2$ parameters are re-estimated using maximum likelihood formulas.

These two steps can be simply repeated until convergence is reached. The main advantage of this formulation is that the variance in price for each type of item is explicitly modelled. While the variance parameters are useful on on their own for analysis of the data, an additional benefit is that the extra parameters allow this model to achieve higher accuracy than linear regression on gold standard data, when working with sufficiently large amounts of data.