Understanding the "Wide" part of Google's wide and deep Google's wide and deep recommender model sounds really cool, but I'm struggling to believe I'm grasping the wide section right so wanted to check my understanding.

Their paper says the following:


  The wide component consists
  of  the  cross-product  transformation  of  user  installed  apps
  and impression apps  
  
  Each example
  corresponds to one impression


Let's say we have 5 apps, A through E. My understanding is that the cross-product transformation would represent that as 20 columns, representing each possible combination of installed and impressed app (making 25, but then presumably the 5 "matching" cross-products like and(installed=App_A, impressed=App_A) would be removed because presumably Google is smart enough not to impress Apps the user already has). Let's also say we have 3 Users, called X - Z. X has installed apps A and C, and is shown app B and D. Y has installed App B and is shown A and E. Z has installed apps A, C and D and is shown apps B and E. With that dataset, the cross-product transformation should look (I think) like this:



My question is; is my understanding of the transformation there correct? If so that's going to be one gigantic matrix in fairly short order, particularly given they have over a billion users and a million different apps.
Indeed you will have a large and very sparse matrix. The two important concepts in this are:


feature cross: you have two categorical features (here impressed and installed) and you do a carthesian product of both to create a new feature (as you did here). The issue is that crosses generate sparse matrices (as you can see in your example)


Neural netowrks perform well with dense, correlated features while linear models work better with sparse and low correlated feartures. Your cross features are sparse with low correlation, which leads to the second concept:


wide and deep network: since your dataset is a mix between dense features (continuous features) and sparse (cross) you can separate your network in two: the sparse will be directly sent to your output and thus treated as they would be in a linear model while your dense features will go through several hidden layers before going to the output. 


The wide part behaves just like a linear model (you can also use sparse matrix calculus to speed it up) and the deep part like a traditional neural network and you get the best of both worlds. Given the size of the dataset (billion users x million apps), treating part of the data as a sparse input will speed up training and inference.

I went a bit further than what you asked but I figured it could be of help.