Everything so far has been about words. But look back at what we actually needed.

1. A set of discrete things with IDs (a vocabulary).
2. A source of co-occurrence or interaction signal ("these appear together", "this user liked that item").
3. An objective that rewards giving related things similar vectors.

None of that is specific to language. If it can be indexed, it can be embedded. And in every case, the objective defines what "similar" means. This section is a tour of the most important non-word embeddings, and it previews where the rest of the book takes the idea.

Recommender systems put users and items in one space

The Netflix Prize (2006 to 2009) made matrix factorization the workhorse of recommendation (Koren, Bell & Volinsky, 2009). Give every user $u$ a vector $\mathbf{p}_u\in\mathbb{R}^d$ and every item $i$ a vector $\mathbf{q}_i\in\mathbb{R}^d$, and predict a rating as

where $\mu$ is the global average rating, $b_u$ captures "this user rates everything high", and $b_i$ captures "this item is generally popular". The dot product captures the personal match, whether this user's tastes align with this item's traits. A worked example. If the average rating is $\mu = 3.6$, this user rates $0.3$ above average, this film is rated $0.5$ below average, and their vectors have dot product $0.4$, the prediction is $3.6 + 0.3 - 0.5 + 0.4 = 3.8$ stars.

Train on the observed ratings only (a set $\Omega$ of user and item pairs), with L2 regularization of strength $\lambda$,

In plain words, fit the ratings we have, with user and item vectors whose dot products explain what's left after the biases, while keeping the vectors small. Training only on observed entries is the crucial difference from the SVD of §1.4. A missing rating is unknown, not zero, so we can't just decompose a matrix with holes filled in.

Nobody tells the model about genres, but the item vectors end up encoding them. Two horror films get similar $\mathbf{q}$'s because the same users like both. It's the distributional hypothesis again. Items are known by the users they keep.

import numpy as np

def mf_loss_grad(P, Q, bu, bi, mu, u, i, r, lam):
    raise NotImplementedError

Let's watch genres emerge. We simulate users with hidden taste for three genres, generate ratings, hide 70% of them, and fit the factorization with full-batch gradient descent.

Alternating least squares

Gradient descent is not the only way to fit this. Look at the loss with the item vectors held fixed (drop the biases for clarity). Each user's vector then appears in a separate ridge regression, with the items that user rated as the "features",

where $\Omega_u$ is the set of items user $u$ rated. In plain words, with the items frozen, the best vector for each user has a closed form, and all users can be solved independently and in parallel. Then freeze the users and solve for every item the same way, and alternate. Each half-step can only lower the loss, so alternating least squares (ALS) converges steadily without a learning rate (Hu, Koren & Volinsky, 2008, extended it to implicit feedback, and Spark's recommender uses it). Each solve is a $d\times d$ system, so one sweep costs $O(\lvert\Omega\rvert d^2 + (n_{\text{users}} + n_{\text{items}})d^3)$.

import numpy as np

def als_user_step(Q, u, i, r, n_users, lam):
    """Q: (n_items, d); u, i, r: (N,) observed triples -> P: (n_users, d)"""
    raise NotImplementedError

Implicit feedback, two towers, and retrieval

Most real data isn't star ratings. It's implicit, such as clicks, plays, and purchases. There are no explicit negatives, so systems use the trick you know from §1.5. They sample negatives and train "interacted versus random". item2vec (Barkan & Koenigstein, 2016) literally runs SGNS on shopping baskets or listening sessions, treating items that appear together as context.

Modern systems generalize matrix factorization into two-tower models. One neural network (the user or query tower) maps everything known about a user (history, location, time) to a vector. Another (the item tower) maps item features to a vector. The score is their dot product. YouTube's candidate generator (Covington, Adams & Sargin, 2016) framed retrieval as a huge softmax over videos given a user vector, and a later YouTube system (Yi et al., 2019) trained both towers with an in-batch softmax. Because item vectors don't depend on the user, you can precompute them for all items and answer "best items for this user" with a fast maximum inner-product search over millions of vectors (the norm-augmentation trick of §1.3, and the indexes of §7.4). Feature-based towers also soften the cold-start problem, because a brand-new item with no interactions still gets a vector from its features.

In-batch negatives, and the popularity bias they create

The cheapest negatives are already in memory. Take a batch of $B$ (user, item) pairs, embed the users as rows of $\mathbf{U} \in \mathbb{R}^{B\times d}$ and the items as rows of $\mathbf{I} \in \mathbb{R}^{B\times d}$, and treat every other item in the batch as a negative for each user. The logits are $\mathbf{U}\mathbf{I}^\top/\tau$ for a temperature $\tau$, and the loss is cross-entropy with the diagonal as the right answers, the same structure as the CLIP loss in §1.8.

There's a catch. Items enter batches in proportion to their popularity, so a popular item is used as a negative far more often than a niche one, and the model learns to push popular items down. Yi et al. (2019) correct for this the same way NCE corrects negative sampling (§1.5). Subtract the log of each item's sampling probability $q_j$ from its logit,

where $\mathbf{u}_i$ and $\mathbf{v}_j$ are rows $i$ and $j$ of $\mathbf{U}$ and $\mathbf{I}$. In plain words, an item that shows up as a negative ten times more often gets its logit lowered by $\log 10 \approx 2.3$ in training, so the model doesn't have to distort its vector to compensate. At serving time the correction is dropped and the raw dot product is used. A second practical fix is to mask out "negatives" that are actually the same item as the positive, which happens often for popular items in large batches.

import numpy as np

def inbatch_softmax_loss(U, I, item_ids, item_prob, tau=0.1, correct=True):
    raise NotImplementedError

Categorical features in tabular models

Tabular datasets are full of high-cardinality categories, such as store ID, product SKU, zip code, and user agent. One-hot encoding them hits all the problems of §1.1. Entity embeddings (Guo & Berkhahn, 2016) give each category value a learned vector, trained end to end with the rest of the network on the actual prediction target. In the Rossmann store-sales Kaggle competition, the learned embeddings of the German states the stores were in, visualized in 2-D, roughly recovered the map of Germany, purely from sales patterns.

The hashing trick, and how often it collides

When a feature has millions of values, or values unseen at training time (new users, new URLs), the hashing trick (Weinberger et al., 2009) maps each value to one of $B$ buckets with a hash function and embeds the buckets. (In this subsection $B$ counts buckets, not batch items.) Memory is fixed at $B\times d$. The price is collisions, where unrelated values share a vector.

How often? Hash $n$ values uniformly into $B$ buckets. A given bucket stays empty with probability $(1 - 1/B)^n \approx e^{-n/B}$, and a given value shares its bucket with at least one other value with probability

In plain words, the collision rate depends only on the load $n/B$. With as many buckets as values ($n = B = 10^6$), 63% of values share their vector with someone and 37% of the buckets sit empty. Even with ten times more buckets than values, 9.5% of values collide. Collisions are not rare events. They are a constant tax that only shrinks linearly with memory.

Using two or more independent hashes per value and summing (or concatenating) their vectors helps a lot, because two values now share their entire representation only if they collide in every hash. With two hashes into $10^6$ buckets each, a given value fully collides with another with probability about $n/B^2 = 10^{-6}$. This is the idea behind hash embeddings (Svenstrup, Hansen & Winther, 2017) and the compositional embeddings used in large recommendation models (Shi et al., 2020).

def bucket(value, n_buckets):
    raise NotImplementedError

import numpy as np

def expected_collision_rate(n, B):
    raise NotImplementedError

def collision_rate(buckets):
    raise NotImplementedError

Graphs, where random walks are sentences

How do you embed the nodes of a graph (people in a social network, papers in a citation graph, proteins in an interaction network)? DeepWalk (Perozzi, Al-Rfou & Skiena, 2014) had a delightfully simple answer. Generate random walks and treat them as sentences. Then run skip-gram. Nodes that appear close together on walks, meaning nodes in the same neighborhood or community, get similar vectors.

node2vec (Grover & Leskovec, 2016) biases the walks with two parameters. Suppose the walk just moved from node $s$ to node $v$, and $x$ is a neighbor of $v$. The next step goes to $x$ with unnormalized weight $1/p$ if $x = s$ (going back), $1$ if $x$ is also a neighbor of $s$ (staying close), and $1/q$ otherwise (moving outward). With $p = 4$ and $q = 0.5$, a node with one way back, one shared neighbor, and two outward neighbors gives weights $(0.25, 1, 2, 2)$, so the walk moves outward with probability $4/5.25 \approx 0.76$. Small $q$ gives depth-first walks that explore communities, and large $q$ gives breadth-first walks that stay local and capture structural roles, like "hub". Qiu et al. (2018) later showed that DeepWalk, like SGNS (§1.5), implicitly factorizes a matrix, in this case a log-transformed sum of powers of the random-walk transition matrix.

Here is DeepWalk end to end, reusing the SGNS step from §1.5 unchanged.

Same algorithm, different "corpus". The model never saw the community labels.

From tables to encoders

Every embedding in this section lived in a table, one row per ID. The most powerful embeddings today aren't lookup tables at all. They're neural networks that compute a vector from raw input, whether that's a sentence, a photograph, or a recording. The geometry from §1.3 carries over completely, and so do the visualization caveats from §1.6. Here's a real sentence-embedding model running in your browser, as a preview of §1.8.

In PyTorch

That loss, in-batch negatives with a cross-entropy over a similarity matrix, is the same InfoNCE loss behind CLIP and modern sentence embedders. You'll derive it properly in §7.2.

Read more

• Koren, Bell & Volinsky (2009). Matrix Factorization Techniques for Recommender Systems. The Netflix Prize model with biases.
• Hu, Koren & Volinsky (2008). Collaborative Filtering for Implicit Feedback Datasets. ALS with confidence weights for clicks and plays.
• Covington, Adams & Sargin (2016), Deep Neural Networks for YouTube Recommendations, and Yi et al. (2019), Sampling-Bias-Corrected Neural Modeling. Two-tower retrieval in production, and the logQ correction.
• Weinberger et al. (2009), Feature Hashing for Large Scale Multitask Learning, and Svenstrup, Hansen & Winther (2017), Hash Embeddings for Efficient Word Representations. The hashing trick and its multi-hash refinement.
• Perozzi et al. (2014), DeepWalk, Grover & Leskovec (2016), node2vec, and Qiu et al. (2018), Network Embedding as Matrix Factorization.
• Grbovic & Cheng (2018). Real-time Personalization using Embeddings for Search Ranking at Airbnb. item2vec ideas at scale.
• Murphy (2022). Probabilistic Machine Learning, Chapter 22. Recommender systems, including matrix factorization and BPR.

Watch next

▶

▶