Pointwise Mutual Information for Instacart Product Recommendations

Pointwise Mutual Information

Pointwise Mutual Information is a measure of association from information theory and has found a popular application in natural language processing. There, it measures the association between a word and the word’s context, e.g. close words in a sentence (bi-grams, n-grams, etc.). It does so by comparing how often the word and the context appear together against how often they would appear together were they independent events.

Following Wikipedia, we have for the outcomes \(x\) and \(c\) of two discrete random variables \(X\) and \(C\):

\[ pmi(x;c) = \log \frac{p(x,c)}{p(x)p(c)} \]

Here, the numerator describes the joint probability, while the denominator describes the joint probability under independence. Thus, were the two events independent, we would have \(pmi(x;c) = \log(1) = 0\). Consequently, positive PMI values imply positive association between the events (e.g., the word and its context, or between two products).

Similarly, negative PMI values should indicate negative relationships—but it’s generally not as easy to think in terms of words that do not appear together. While it’s easy to come up with co-occuring words (Google & Facebook, Scrum & Agile, Obama & Merkel), I failed to quickly come up with examples for the opposite. It’s not how we’re tuned to think. Also, the necessary corpus to correctly measure the PMI of words that do not appear together is very, very large—because they don’t appear together (see this book chapter by Daniel Jurafsky and James H. Martin).

Data Preparation

We’ll now prepare the Instacart data and apply the PMI measure on the observed orders to find products that have been bought together.

To follow along, download the csv files from Instacart. First, we load some libraries and read the csv files. Note that these are the only packages we’ll need. This goes to show that we can do the same analysis in SQL, even though what follows is written in R.

library(dplyr)
library(readr)

# this is on order level
orders <- read_csv("orders.csv")
# this is on product level
products <- read_csv("products.csv")
# this is on order-product level
order_products <- read_csv("order_products__prior.csv")

Note that we only read one of the available order_products tables, since we will not perform an evaluation based on a test set. The orders table, however, contains information on more orders than those contained in order_products, so we slim it down:

# number of all orders
length(unique(orders$order_id))

## [1] 3421083

# number of orders in our subset
length(unique(order_products$order_id))

## [1] 3214874

# we focus on the "prior" evaluation set for now
orders <- orders %>%
  filter(eval_set == "prior") %>%
  select(-eval_set)

In the next few steps, we trim down the set of considered customers and products to only include those for which we have enough observations.

# first, get for every user his number of orders
users <- orders %>%
  group_by(user_id) %>%
  summarize(orders = n())
summary(users$orders)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    3.00    5.00    9.00   15.59   19.00   99.00

# drop all users who had a single order or a very large number of orders
# (customers who only made one order might have bought "trial baskets")
good_users <- users %>%
  filter(orders <= 50, orders >= 1) %>%
  pull(user_id)
# filter for the corresponding orders
good_orders <- orders %>%
  filter(user_id %in% good_users)

# count for every user the number of different items he bought
product_by_customer_count <- order_products %>%
  inner_join(select(good_orders, order_id, user_id)) %>%
  distinct(user_id, product_id) %>%
  count(product_id)

# A considered product should have been bought by 
# at least 0.1% of the customers
product_threshold <- length(unique(good_orders$user_id)) * 0.001

good_products <- product_by_customer_count %>% 
  filter(n >= product_threshold) %>%
  pull(product_id)

op <- order_products %>%
  select(order_id, product_id) %>%
  inner_join(select(good_orders, order_id, user_id)) %>%
  filter(product_id %in% good_products)

# as last step, exclude all orders with a basket size of 1
op_size_one <- op %>% 
  group_by(order_id) %>%
  summarize(basket_size = n()) %>%
  ungroup %>% 
  filter(basket_size == 1) %>%
  pull(order_id)

op <- op %>% 
  filter(!(order_id %in% op_size_one))

After this initial data cleaning, let’s see how many orders, users, and products we are dealing here:

length(unique(op$order_id))

## [1] 2315386

length(unique(op$user_id))

## [1] 194760

length(unique(op$product_id))

## [1] 8979

So after dropping some customers and orders, we are left with about 200k users who bought about 9000 different products across 2.3 million orders. That should more than suffice to compute some PMI values.

Pointwise Mutual Information for Instacart Products

To compute the PMI value for every product, we first of all need to count how often products appear together. For the dataset at hand, the following expansion of the order_products table works fine (you should have quite some RAM though…); for every order, we join every product against every product in the order. This makes our table much longer, so depending on the average basket size and number of orders in another dataset, it might be a prohibitively expensive computation. We then immediately count how often products appear together:

op_pp <- inner_join(op, op,
                    by = c(order_id = "order_id")) %>%
  count(product_id.x, product_id.y)

dim(op_pp)

## [1] 31708163        3

Next, we need to count how often every product appears in orders, generally. This is used to compute the probabilities \(p(x)\) and \(p(c)\). We add these counts to the co-occurrence counts, and add the number of total orders in the total_n column. At this point we have all ingredients to compute the empirical probabilities and the PMIs.

product_count_train <- op %>%
  count(product_id)

pp_common_count <- op_pp %>%
  inner_join(product_count_train, by = c(product_id.x = "product_id")) %>%
  inner_join(product_count_train, by = c(product_id.y = "product_id")) %>%
  rename(common_n = n.x, x_n = n.y, y_n = n) %>%
  # total number of orders considered
  mutate(total_n = length(unique(op$order_id)))

Computing the PMI is now as simple as dividing columns and taking the logarithm. We add the corresponding product names to analyze the results afterwards.

pp_pmi <- pp_common_count %>%
  mutate(common_freq = log(common_n / total_n),
         x_freq = log(x_n / total_n),
         y_freq = log((y_n / total_n)),
         pmi = common_freq - x_freq - y_freq)

pp_rec <- pp_pmi %>%
  select(product_id.x, product_id.y, total_n, common_n, x_n, y_n, pmi) %>%
  left_join(select(products, product_id, product_name), 
            by = c(product_id.x = "product_id")) %>%
  left_join(select(products, product_id, product_name), 
            by = c(product_id.y = "product_id"))

Detailed Look at Recommendations

Given that we have not exactly fitted a model here, it’s not clear how to evaluate the results. We’re not explicitly optimizing for anything, so the following evaluation will be restricted to looking at some recommendations and judging whether the recommendations “make sense”.¹

Given the large sortiment, I had to pick some products at random to evaluate the recommendations. Also, I had to pick products that I actually know–I’m not living in the U.S., so what is Glacier Freeze Frost?

For a start, let’s act as if we are about to add Spicy Avocado Hummus to the cart. What could I buy with hummus? Apparently a lot of other hummus, yogurt, as well as crackers or chips:

pp_rec %>% 
  filter(product_id.x == 5973, product_id.x != product_id.y) %>%
  arrange(-pmi) %>%
  top_n(10, pmi) %>%
  select(product_name.x, product_name.y, pmi, common_n, x_n, y_n) %>%
  knitr::kable(digits = 2)

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Spicy Avocado Hummus	Organic Jalapeno Cilantro Hummus	4.70	118	2541	982
Spicy Avocado Hummus	Organic Kale Pesto Hummus	4.47	97	2541	1015
Spicy Avocado Hummus	Organic Thai Coconut Curry Hummus	4.32	78	2541	945
Spicy Avocado Hummus	Organic Sriracha Hummus	4.31	144	2541	1762
Spicy Avocado Hummus	Hummus, Hope, Original Recipe	3.71	206	2541	4572
Spicy Avocado Hummus	Total 2% Lowfat Greek Yogurt with Honey	3.12	12	2541	481
Spicy Avocado Hummus	Organic Jalapeno Crackers	3.11	12	2541	489
Spicy Avocado Hummus	Chomperz Original Crunchy Seaweed Chips	3.09	17	2541	707
Spicy Avocado Hummus	Teriyaki Turkey Jerky	3.06	11	2541	472
Spicy Avocado Hummus	Soft Toothbrush	3.03	9	2541	397

Observe how we don’t have the Hummus, Hope, Original Recipe as the top recommended product even though the avocado hummus was bought most often with it. That is because the PMI takes into account how often the two products appear in orders independently. We see that the Hummus, Hope, Original Recipe is quite popular, which is why the 206 common orders are not as impactful as the 118 orders together with Organic Jalapeno Cilantro Hummus for the PMI. And so we want to rank the jalapeno hummus higher.

Notice also how some recommendations are based on just 9, 11, 12, or 17 common orders. If we think about how many customers we have, 12 orders can be noise. The toothbrush, for example, does not look like a good recommendation. We will address this with a smoothing method in a minute.

If we pick a different hummus, Garlic Hummus, we get very different results. There is no other hummus recommended, and instead the recommendations focus on pita bread. But notice again how the PMI favors products with a small number of common orders.

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Garlic Hummus	Whole Wheat Pita	2.76	23	6893	489
Garlic Hummus	White Pita	2.75	71	6893	1518
Garlic Hummus	Peanut Butter Dark Chocolate Fruit & Nut Protein Bars	2.62	15	6893	368
Garlic Hummus	Gluten Free Black Bean and Quinoa Burrito	2.53	18	6893	480
Garlic Hummus	Organic Spinach & Potatoes 2, 6 Months+	2.50	18	6893	495
Garlic Hummus	Turkey Meatball Bites	2.50	13	6893	358
Garlic Hummus	100% Whole Wheat Hot Dog Buns	2.46	23	6893	659
Garlic Hummus	Organic White Pita Bread	2.42	37	6893	1102
Garlic Hummus	Lotus Forbidden Rice Ramen	2.38	10	6893	312
Garlic Hummus	Gochujang Fermented Garlic Chile Paste	2.20	7	6893	260

Similarly, here are recommendations for products that go well with Granny Smith Apples.

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Granny Smith Apples	Royal Gala Apples	2.24	238	27712	2127
Granny Smith Apples	Bag of Red Delicious Apples	2.00	74	27712	835
Granny Smith Apples	Seedless Grapes Green	1.98	34	27712	392
Granny Smith Apples	Dark Chocolate Chili Almond Nuts & Spices	1.96	34	27712	399
Granny Smith Apples	Outshine Lime Fruit Bars	1.95	55	27712	651
Granny Smith Apples	Golden Delicious Apple	1.95	359	27712	4258
Granny Smith Apples	Braeburn Apple	1.93	126	27712	1523
Granny Smith Apples	Garlic Parmesan Deli Style Pretzel Crisps	1.91	49	27712	606
Granny Smith Apples	Bag of Oranges	1.89	131	27712	1657
Granny Smith Apples	Whole Frozen Strawberries	1.88	35	27712	445

When you work yourself through a couple of examples, it might stand out to you that the PMI tends to favor products with a small probability, that is, rare products tend to be recommended more. This is not necessarily desired, in particular not from the standpoint of a business.

Context Distribution Smoothing

As explained in Jurafsky and Martin (2017) citing Levy at al. (2015), a simple way to address this bias is context distribution smoothing, where the context probability is raised to the power of \(\alpha\), where \(\alpha \in (0,1)\). Since, for example, \(0.1^{0.75} \approx 0.1778\), doing so increases the probability of the context, and consequently decreases the PMI.

While there is also an impact on events with larger probability, the effect on events with small probability can be more extreme as for example here, leading to a larger absolute discount of their PMI values:

\[ \log(0.25) - \log(0.5) - \log(0.3) \approx 0.511 \] \[ \log(0.01) - \log(0.5) - \log(0.01) \approx 0.693 \] \[ \log(0.25) - \log(0.5) - \log(0.3^{0.75}) \approx 0.210 \] \[ \log(0.01) - \log(0.5) - \log(0.01^{0.75}) \approx -0.458 \]

It also implies that everything that would have been perfectly independent previously does now become negatively associated:

\[ \log(0.25) - \log(0.5) - \log(0.5) = 0 \] \[ \log(0.25) - \log(0.5) - \log(0.5^{0.75}) \approx -0.173 \]

Setting this aside, the context distribution smoothing can help in many cases to make the top ranks more sensible by returning more mainstream results. We can add the exponent (here 0.75) and compare the results:

context_exponent <- 0.75
pp_pmi_smooth <- pp_common_count %>%
  # smooth using the prior
  mutate(common_freq = log(common_n / total_n),
         x_freq = log(x_n / total_n),
         y_freq = log((y_n / total_n)^context_exponent),
         pmi = common_freq - x_freq - y_freq)

pp_rec_smooth <- pp_pmi_smooth %>%
  select(product_id.x, product_id.y, total_n, common_n, x_n, y_n, pmi) %>%
  left_join(select(products, product_id, product_name), 
            by = c(product_id.x = "product_id")) %>%
  left_join(select(products, product_id, product_name), 
            by = c(product_id.y = "product_id"))

For the apples we can observe that the seedless grapes, the Dark Chocolate Chili Almond Nuts & Spices, as well as Outshine Lime Fruit Bars have all been replaced by more apples, and the most frequently purchased item of them all: bananas.

pp_rec_smooth %>%
  filter(product_id.x == 9387, product_id.x != product_id.y) %>%
  arrange(-pmi) %>%
  select(product_name.x, product_name.y, pmi, common_n, x_n, y_n) %>%
  head(10) %>%
  knitr::kable(digits = 2)

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Granny Smith Apples	Royal Gala Apples	0.49	238	27712	2127
Granny Smith Apples	Golden Delicious Apple	0.38	359	27712	4258
Granny Smith Apples	Gala Apples	0.37	1061	27712	18335
Granny Smith Apples	Banana	0.25	8919	27712	365728
Granny Smith Apples	Red Delicious Apple	0.21	236	27712	3062
Granny Smith Apples	Mandarins Bag	0.20	295	27712	4175
Granny Smith Apples	Bosc Pear	0.15	301	27712	4578
Granny Smith Apples	Braeburn Apple	0.10	126	27712	1523
Granny Smith Apples	Bag of Oranges	0.08	131	27712	1657
Granny Smith Apples	Organic Fuji Apple	0.08	2156	27712	69495

We see a similar effect for the garlic hummus. Compared to the previous recommendations, we also observe that more of the recommended items now have larger common_n values, i.e., by introducing the smoothing, we have implicitly ensured that the ranking relies more on common purchases.

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Garlic Hummus	White Pita	0.92	71	6893	1518
Garlic Hummus	Sea Salt Pita Chips	0.90	351	6893	13135
Garlic Hummus	Jalapeno Hummus	0.65	157	6893	6310
Garlic Hummus	Whole Wheat Pita	0.64	23	6893	489
Garlic Hummus	Lemon Hummus	0.59	250	6893	12625
Garlic Hummus	Organic White Pita Bread	0.51	37	6893	1102
Garlic Hummus	Pita Chips Simply Naked	0.48	175	6893	9110
Garlic Hummus	Organic Peeled Whole Baby Carrots	0.44	532	6893	42519
Garlic Hummus	Peanut Butter Dark Chocolate Fruit & Nut Protein Bars	0.43	15	6893	368
Garlic Hummus	100% Whole Wheat Hot Dog Buns	0.42	23	6893	659

Why PMI and not Common Order Count?

To quickly show the impact of using pointwise mutual information to rank the recommendations instead of the raw count of common orders, consider the following example. If we use the pointwise mutual information to get products that are bought together with Birthday Candles, we will get the following items as the top recommendations. The lighter is a natural complement, and everything else is to prepare the cake on which the candles are placed:

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Birthday Candles	Classic Lighters	2.69	4	208	331
Birthday Candles	Super Moist Chocolate Fudge Cake Mix	2.63	4	208	360
Birthday Candles	Creamy Classic Vanilla Frosting	2.55	3	208	273
Birthday Candles	Rich and Creamy Milk Chocolate Frosting	2.51	3	208	285
Birthday Candles	Funfetti Premium Cake Mix With Candy Bits	2.48	5	208	587

If we instead rank by the absolute count of common purchases, the recommended products would be the generally frequently purchased bananas, strawberries, etc., just as I alluded to in the beginning. This just goes to show that the raw count is not an alternative to come up with product recommendations.

product_name.x	product_name.y	pmi	common_n	x_n	y_n
Birthday Candles	Banana	-0.78	24	208	365728
Birthday Candles	Organic Strawberries	-0.69	16	208	189410
Birthday Candles	Large Lemon	-0.74	11	208	122928
Birthday Candles	Bag of Organic Bananas	-1.66	8	208	274515
Birthday Candles	Strawberries	-1.00	8	208	113606