SVD for a Low-Dimensional Embedding of Instacart Products

Goal: A word2vec-style Representation of Products

Using word2vec is all the rage to derive numeric vector representations of words in natural language processing. The result is be a \(N\times K\) matrix of \(N\) words represented by \(K\) vectors. Since \(K \ll N\), such a low-dimensional representation is extremely useful as input for subsequent tasks such as classification, or to perform word2vec’s hallmark word vector operations such as zuckerberg - facebook + microsoft ~ nadella.

In our case, we deal with \(N=8979\) products, which is manageable. Still, by using a small \(K = 64\) we are able to go from a \(N \times N\) pointwise mutual information matrix to a small-ish set of vectors summarizing the information. And since we will be using singular value decomposition to do so, (hopefully most) vectors will even highlight different groups of related products! That’s a nice side effect when trying to derive higher level abstractions and patterns in the purchase data—compared to individual product-to-product relations—and comparable to topics derived from topic models like Latent Dirichlet Allocation.

This blog post is inspired by Chris Moody’s Stop Using word2vec on StichFix’ MultiThreaded blog, in which Chris applied SVD in combination with PMI on the more typical NLP task of embedding words from the Hacker News corpus. In the following, we will see that one can use the exact same method to derive a representation of items sold on Instacart.

From PMI Matrix to SVD

The previous blog post introduced the Pointwise Mutual Information and how it can be applied to derive product recommendations for products that have been purchased in the same order. We finished with a long table called pp_rec_smooth in which every row represented an observed combination of two products that have been purchased together a couple of times, as well as their corresponding pointwise mutual information.

Consequently, the table is quite long with 31708163 rows. This is still smaller than the \(8979\cdot 8979 = 80622441\) row table for all combinations of products. The latter, however, is exactly what we need for the matrix factorization through singular value decomposition: A \(N \times N\) item-by-item pointwise mutual information matrix. We create this matrix by widening the long table; it’s not beautiful, but it does the job.

pmi_matrix <- pp_rec_smooth %>%
  select(product_id.x, product_id.y, pmi) %>%
  tidyr::spread(product_id.y, pmi)
pmi_matrix_product_ids <- pmi_matrix[,1]
pmi_matrix <- pmi_matrix[,-1]

pmi_matrix[1:5,1:5]

## # A tibble: 5 x 5
##     `1`    `10`   `23`    `25`  `28`
##   <dbl>   <dbl>  <dbl>   <dbl> <dbl>
## 1  5.59  NA      NA     NA     NA   
## 2 NA      5.29  - 1.71 - 0.548 NA   
## 3 NA    - 1.51    5.89 - 1.36  NA   
## 4 NA    - 0.498 - 1.51   5.44  NA   
## 5 NA     NA      NA     NA      6.14

All NAs in this table represent product combinations that have not been observed in the data and for which we consequently do not have a PMI value.

The problem with the NAs is that we cannot perform singular value decomposition on a matrix with missing entries. But assigning those entries any other value would give them meaning: A very negative value would convey a negative relationship, while setting all of them to zero implies no relationship. Neither is something we would like to simply assume in the following.

A good alternative described in Jurafsky and Martin is to set not only the NAs to zero, but also the negative PMI values. This can furthermore be justified by the observation that it is generally more difficult to observe a negative relationship using PMI—as described in the previous blog post and by Jurafsky and Martin. Thus we proceed by replacing both NAs and negative values by zero.

pmi_matrix[is.na(pmi_matrix)] <- 0
pmi_matrix[pmi_matrix < 0] <- 0
pmi_matrix[1:5,1:5]

## # A tibble: 5 x 5
##     `1`  `10`  `23`  `25`  `28`
##   <dbl> <dbl> <dbl> <dbl> <dbl>
## 1  5.59  0     0     0     0   
## 2  0     5.29  0     0     0   
## 3  0     0     5.89  0     0   
## 4  0     0     0     5.44  0   
## 5  0     0     0     0     6.14

colSums(pmi_matrix)[1:5] # not only the diagonal is positive

##        1       10       23       25       28 
## 281.6510 126.0473 162.0798 265.7752 323.0297

The \(N \times N\) matrix is now prepared for singular value decomposition. Though, it’s not actually a matrix yet. So let’s change that, and let’s use the fact that the matrix has become really sparse by converting the object into a sparse matrix.

pmi_matrix <- as.matrix(pmi_matrix)
row.names(pmi_matrix) <- pmi_matrix_product_ids$product_id.x
colnames(pmi_matrix) <- pmi_matrix_product_ids$product_id.x

library(Matrix)
pmi_sparse_matrix <- Matrix(pmi_matrix, sparse = TRUE)
pmi_sparse_matrix[1:5,1:5]

## 5 x 5 sparse Matrix of class "dgCMatrix"
##           1       10       23       25       28
## 1  5.587646 .        .        .        .       
## 10 .        5.291013 .        .        .       
## 23 .        .        5.891188 .        .       
## 25 .        .        .        5.442685 .       
## 28 .        .        .        .        6.135897

To make use of the sparsity when performing singular value decomposition, we can for example use the sparsesvd package. Here, we choose to find a representation of rank 64. This means in particular that we will have 64 vectors representing what was previously represented by 8979 vectors. Using the singular value decomposition, we arrange the available information in a more compact way; we lose some information, but hopefully retain most of it. Feel free to experiment with different values for the rank \(K\). Problematic is that there is no good quantitative way of finding a good \(K\). One could examine the eigenvalues, or check whether the vectors corresponding to the smallest eigenvalue for a given value of \(K\) make some sense, and, if not, choose a smaller \(K\) instead.

library(sparsesvd)
set.seed(80495)
pmi_svd <- sparsesvd(pmi_sparse_matrix, 
                     rank = 64)

The result looks as follows. We have the \(N \times K\) matrix, pmi_svd$u, as well as the corresponding \(K\) singular values. If we plot them, we can see how much information is contained in just the first couple of dimensions.

dim(pmi_svd$u)

## [1] 8979   64

Working with the SVD

Before we start using the result of the singular value decomposition, we add the product names to the rows of the left-singular vectors.

products <- readr::read_csv("products.csv")
departments <- readr::read_csv("departments.csv")

id_name_dict <- data.frame(product_id = as.numeric(row.names(pmi_sparse_matrix))) %>%
  inner_join(select(products, product_id, 
                    product_name, aisle_id, department_id)) %>%
  left_join(departments)

product_vectors <- pmi_svd$u
row.names(product_vectors) <- id_name_dict$product_name

With the row names added, we can easily search for specific products as well as the products that are closest in the \(K\)-dimensional space as measured by a measure as simple as the dot product. That is, we’re starting to apply the typical techniques from word embeddings on our product matrix!

# first a function to find the actual product names
search_product <- function(products, name) {
  products[grepl(name, products, fixed = TRUE)]
}

# then the function that finds similar products by dot product
search_synonyms <- function(word_vectors, selected_vector) {
  # https://juliasilge.com/blog/tidy-word-vectors/
  require(broom)
  
  similarities <- word_vectors %*% selected_vector %>%
    tidy() %>%
    as_tibble() %>%
    rename(product = .rownames,
           similarity = unrowname.x.)
  
  similarities %>%
    arrange(-similarity)    
}

We search for products containing the word Ketchup and then look for similar products, where the similarity is based on the dot product on a singular value decomposition of commonly bought together items.

search_product(row.names(product_vectors), "Ketchup")

##  [1] "Reduced Sugar Tomato Ketchup" "Tomato Ketchup"              
##  [3] "Organic Ketchup Gluten Free"  "Organic Ketchup"             
##  [5] "Simply Heinz Tomato Ketchup"  "Organic Unsweetened Ketchup" 
##  [7] "Classic Ketchup"              "Squeeze Tomato Ketchup"      
##  [9] "Ketchup"                      "Organic Tomato Ketchup"

search_synonyms(product_vectors, 
                product_vectors["Tomato Ketchup",]) %>% 
  head(10) %>%
  knitr::kable(digits = 4)

search_product(row.names(product_vectors), "Smoothie") %>% tail()

## [1] "Blueberry B Fruit Smoothie"                              
## [2] "Organic Original Acai Berry + Guarana Smoothie Packs"    
## [3] "Protein Smoothie Choc-a-lot Flavor"                      
## [4] "Power C Machine All Natural Fruit + Boost Juice Smoothie"
## [5] "Danimals Strawberry Explosion Flavored Smoothie"         
## [6] "Green Machine Juice Smoothie"

search_synonyms(product_vectors, 
                product_vectors["Green Machine Juice Smoothie",]) %>%
  head(10) %>%
  knitr::kable(digits = 4)

These results look quite good! But also similar to what we have been able to do based on the PMI alone.

Exploring Groups of Products via Dimensions

Something that the PMI values did not provide us with were groups of similar/frequently purchased together products. Similarly to how we would derive topics when applying Latent Dirichlet Allocation on news articles, it would be super nice to build entire groups of bought-together products. In the case of Instacart, we might even deduct entire recipes. While no one gave singular value decomposition a metaphor as good as the topic model one, the individual singular vectors still allow us to find groups of related products. This is the case because related products should have similar values in certain dimensions. In the extreme, SVD compresses the information about a group of related products onto a single dimension in which these products have particularly high values.

Thus we can find “important” groups of products by exploring for a given vector the products with the largest loading on that vector.

The graph below contrasts singular vectors 7 and 8 from the product_vectors matrix. We see that most observations are very close to 0 on both vectors, while comparatively few products are loaded in absolute terms on just one of the two vectors. This already indicates how the vectors split the work of representing the information that was previously spread across all 8979 vectors: By focusing on a few products per vector, we can more easily store the overall patterns in the data. If a single vector can contain information on about 140 products, then \(64 \cdot 140 = 8979\) products can be represented in 64 dimensions.

If the model works well, related products will load similarly on a given vector. Let’s check for example what kind of information vector 8 stores about products. To get an idea, let’s just look at the 20 most negatively loaded products on vector 8. You see the list of the products below. Given the many “vegan”, “beefless”, “dairy free”, “fishless” mentions in product names, it should be safe to say that vegan products tend to load negatively on vector 8. To hype it up a notch: Our model has learned the concept of a vegan lifestyle from products that were bought together!

We can also look at the other end of vector 8, by considering products that loaded positively. Here we find a selection of snacks. But not just any snacks; we have a selection of high protein snacks ranging from nut bars to turkey jerkey.

# show some of the products in the baby cluster
set.seed(5463)
product_vectors[,c(2,3)] %>%
  tidy() %>%
  bind_cols(id_name_dict) %>%
  filter(X1 > 0.05, X2 > 0.03) %>%
  select(product_name, department, X1, X2) %>%
  rename(X3 = X2, X2 = X1) %>%
  sample_n(5) %>%
  knitr::kable(digits = 2)

Closing Thoughts

In this post we have derived a low dimensional representation of products sold through Instacart. Even though a singular value decomposition is a simple model, the derived vector representation seems useful upon inspection. In this post, we have focused our attention on exploring the resulting vectors and showing how they compress and represent information about certain groups of products that are purchased together by customers.

We have seen that the singular vectors can be interpreted similarly to LDA’s topics given that a given group of products loads on a one or a few vectors. What is still to be explored in future blog posts is the ability to perform vector operations, i.e., operations such as Hamburger Buns - Beef + Wiener ~ Hot Dog Buns. We have quickly shown how one can similar products to a given product through the dot product, but we have not used the cosine similarity yet. A future blog post will use the two dimensional graphs above to show how the dot product and cosine similarity can be used to explore the space of products.

Until then, check out the product dimensions in the Shiny app to find more than just the group of vegan products.

References

The Instacart Online Grocery Shopping Dataset 2017. Accessed from https://www.instacart.com/datasets/grocery-shopping-2017 on May 2, 2018.

Chris Moody. Stop Using word2vec. Blog post on Stitchfix’ MultiThreaded blog, October 18, 2017.

Julia Silge. Word Vectors with Tidy Data Principles. Blog post, October 30, 2017.

Daniel Jurafsky and James H. Martin. Vector Semantics. Book chapter in Speech and Language Processing. Draft of August 7, 2017.

Omer Levy and Yoav Goldberg. Neural Word Embedding as Implicit Matrix Factorization. In Advances in Neural Information Processing Systems 27 (NIPS 2014).

Omer Levy, Yoav Goldberg and Ido Dagan. Improving Distributional Similarity with Lessons Learned from Word Embeddings. Transactions of the Association for Computational Linguistics, vol. 3, pp. 211–225, 2015.

Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado and Jeffrey Dean. Distributed Representations of Words and Phrases and their Compositionality.