Chapter 10 — Other Forms of Learning

Most of this book has focused on the "big three" supervised tasks — classification, regression — plus a few unsupervised ones like clustering. But not every learning problem fits neatly into those boxes. Sometimes what we want to learn is a distance, a ranking, a recommendation, or even word meanings, and the methods for those problems have their own flavor. This chapter tours four of these "other" forms of learning so you recognize them when you meet them in the wild.

In this chapter you will learn:

• How metric learning turns "find a good distance" into a learning problem, and why it helps k-NN and clustering
• Why learning to rank cares about the order of items instead of absolute scores, plus how NDCG measures ranking quality
• How recommender systems work via content-based and collaborative filtering (factorization machines and denoising autoencoders)
• How self-supervised learning creates its own labels from raw text to learn word embeddings like word2vec

10.1 Metric Learning

A metric is just a rule that says how "far apart" two things are. The Euclidean distance you know from geometry is the most common metric for feature vectors, and cosine similarity is the most common for text. These choices are reasonable, but they are also a bit arbitrary — and the fact that one works better than another on a given dataset is a hint that no single fixed metric is perfect for every problem.

The key idea of metric learning is refreshingly simple: instead of guessing the distance formula, learn it from data. Once you have a good metric, you can plug it into any algorithm that needs a distance — k-NN, k-means, hierarchical clustering — and they all get better.

Everyday analogy: A friend who has never cooked might judge "how similar are these two recipes?" by weighing raw ingredient lists (plain Euclidean over counts). A trained chef weights which ingredients matter — a pinch of saffron counts far more than a pinch of water. The chef has, in effect, learned a metric.

Making Euclidean distance learnable

Recall the plain Euclidean distance between two vectors x and x':

$$d(\mathbf{x}, \mathbf{x'}) = \sqrt{(\mathbf{x}-\mathbf{x'})^\top (\mathbf{x}-\mathbf{x'})}.$$

We make this parametrizable by slipping a matrix A into the middle:

$$d_A(\mathbf{x}, \mathbf{x'}) = \sqrt{(\mathbf{x}-\mathbf{x'})^\top \, A \, (\mathbf{x}-\mathbf{x'})}.$$

• If A is the identity matrix, this collapses back to ordinary Euclidean distance.
• If A is diagonal, each feature gets its own weight — the bigger the diagonal entry, the more that feature "counts." (This is exactly the chef weighting ingredients.)
• If A is a full matrix, it can also rotate and rescale the axes, so distance is measured in a direction that separates your classes well.

For this to behave like a genuine distance, A must be positive semidefinite (the matrix version of "non-negative"): for any vector z, z^T A z >= 0. That guarantees the distance is never negative and respects the triangle inequality. The quantity sqrt(x^T A x) is also called the Mahalanobis distance governed by A.

A classic algorithm here is LMNN (Large-Margin Nearest Neighbor): it chooses A so that each example's nearest neighbors are same-class, while examples of other classes are pushed a large margin away. We won't implement LMNN from scratch, but we can capture its spirit with a built-in linear transform that learns a separating direction from the labels.

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.neighbors import NearestNeighbors

plt.rcParams["figure.figsize"] = (11, 4)
plt.rcParams["axes.grid"] = True

# --- A small 2D dataset where the feature SCALES are bad for plain Euclidean -
# Feature 1 is informative but on a tiny scale; feature 2 is useless noise but
# stretched to a huge scale. Plain Euclidean distance is dominated by feature 2,
# so k-NN mixes up the classes. A *learned* metric should fix this.
X, y = make_classification(n_samples=300, n_features=2, n_informative=1,
                           n_redundant=0, n_classes=2, n_clusters_per_class=1,
                           class_sep=2.5, random_state=7)
X = X.copy()
X[:, 0] *= 0.08    # squeeze the informative axis
X[:, 1] *= 12.0    # stretch the noise axis

# --- "Before": plain Euclidean space -----------------------------------------
query = np.array([[0.0, 0.0]])           # a point we'll classify with k-NN
nn_orig = NearestNeighbors(n_neighbors=5).fit(X)
_, idx_orig = nn_orig.kneighbors(query)

# --- "After": learn a linear transform with LDA, measure distance there -------
# LDA finds the direction that best separates the classes -- a stand-in for
# learning the matrix A in d_A(x, x'). With 2 classes it produces ONE axis.
lda = LinearDiscriminantAnalysis()
lda.fit(X, y)
Xt = lda.transform(X)                    # data in the learned metric's axes
query_t = lda.transform(query)
nn_new = NearestNeighbors(n_neighbors=5).fit(Xt)
_, idx_new = nn_new.kneighbors(query_t)

# --- Leave-one-out 5-NN accuracy in each space (the headline number) ----------
def loo_5nn_acc(features):
    nn6 = NearestNeighbors(n_neighbors=6).fit(features)   # 6 = self + 5
    _, idx = nn6.kneighbors(features)
    preds = np.array([np.bincount(y[idx[i, 1:]]).argmax() for i in range(len(y))])
    return (preds == y).mean()

acc_orig = loo_5nn_acc(X)
acc_new = loo_5nn_acc(Xt)

# --- Plot: original space (left) vs learned 1D metric (right) -----------------
fig, ax = plt.subplots(1, 2, figsize=(11, 4))
colors = ["tab:blue", "tab:orange"]

# Left: original 2D, equal aspect so the stretched noise axis is visible as
# the dominant direction (which is exactly why Euclidean k-NN struggles).
for c in range(2):
    ax[0].scatter(X[:, 0][y == c], X[:, 1][y == c], color=colors[c], s=18,
                  alpha=0.6, label=f"class {c}")
ax[0].scatter(query[:, 0], query[:, 1], color="black", marker="*", s=260,
              label="query")
ax[0].scatter(X[idx_orig[0], 0], X[idx_orig[0], 1], facecolors="none",
              edgecolors="red", s=130, linewidths=2, label="5 NN (Euclidean)")
ax[0].set_aspect("equal")
ax[0].set_title("Before: original space (plain Euclidean)")
ax[0].set_xlabel("feature 1 (informative, squeezed)")
ax[0].set_ylabel("feature 2 (noise, stretched)")
ax[0].legend(fontsize=8)

# Right: the single learned LDA axis. Points are spread along it by class.
rng_jit = np.random.default_rng(0)
jitter = rng_jit.uniform(-0.18, 0.18, size=len(y))   # vertical jitter for visibility
for c in range(2):
    sel = y == c
    ax[1].scatter(Xt[sel, 0], jitter[sel], color=colors[c], s=18, alpha=0.6,
                  label=f"class {c}")
ax[1].scatter(query_t[0, 0], 0.0, color="black", marker="*", s=260, label="query")
ax[1].scatter(Xt[idx_new[0], 0], jitter[idx_new[0]], facecolors="none",
              edgecolors="red", s=130, linewidths=2, label="5 NN (learned metric)")
ax[1].set_title("After: LDA-learned metric (1 axis)")
ax[1].set_xlabel("learned axis  (LDA component 1)")
ax[1].set_yticks([])
ax[1].legend(fontsize=8)

plt.tight_layout()
plt.show()

print(f"Leave-one-out 5-NN accuracy in ORIGINAL space     : {acc_orig:.3f}")
print(f"Leave-one-out 5-NN accuracy in LEARNED-metric space: {acc_new:.3f}")
print("Query's 5 neighbors (original) classes:", y[idx_orig[0]])
print("Query's 5 neighbors (learned)   classes:", y[idx_new[0]])

Leave-one-out 5-NN accuracy in ORIGINAL space     : 0.727
Leave-one-out 5-NN accuracy in LEARNED-metric space: 0.993
Query's 5 neighbors (original) classes: [0 0 1 0 1]
Query's 5 neighbors (learned)   classes: [1 1 1 1 1]

Reading the result

On the left (equal aspect), the data is really a tall, thin cloud: feature 2 is stretched so wide that, in plain Euclidean terms, points that are close are mostly close along the noisy vertical direction — so the query's five nearest neighbors (red rings) are a mix of both classes, and leave-one-out 5-NN accuracy is low.

On the right, LDA has learned the single direction that best separates the classes and measured distance along it. The two classes now sit cleanly apart, the query's neighbors are all one class, and 5-NN accuracy jumps to near-perfect. The learned metric effectively down-weighted the noise feature and up-weighted the informative one — exactly what LMNN-style metric learning aims for.

This is the whole pitch of metric learning: the distance itself is a model, and it can be trained.

10.2 Learning to Rank

Think about a search engine. When you type a query, it returns a list of documents. We don't really care about the absolute score of each document — we care about their order: the most relevant one should be first, the next-best second, and so on. Learning to rank is the supervised problem of learning a function that produces a good ordering, not good individual numbers.

This is subtly different from classification/regression:

• Classification asks "what category is this document?"
• Regression asks "what number is this document?"
• Ranking asks "in what order should these documents appear?"

There are three classic ways to frame it:

Approach	What it optimizes	Flavour
Pointwise	Each document's score independently (treated as regression)	Ignores that documents compete for positions
Pairwise	For each pair, which document should rank higher	Better, but still treats pairs in isolation
Listwise	A metric over the whole ranked list directly	Best in practice (e.g. LambdaMART)

The cleverness of LambdaMART (a gradient-boosted-tree ranker) is that it tweaks the gradient using the ranking metric itself, so the model optimizes the thing we actually care about — something ordinary supervised models rarely do. Usually we optimize a cost (like cross-entropy) and only afterwards check a metric; LambdaMART blurs that line.

Measuring a ranking: NDCG

To know whether a ranking is good, we need a metric. A popular one is NDCG (Normalized Discounted Cumulative Gain). The idea is intuitive, in four steps:

1. Relevance: each document has a relevance grade (say 0 = useless, 3 = perfect). Higher is better.
2. Cumulative Gain (CG): sum the relevances of the documents you returned.
3. Discount: a relevant document at position 10 helps the user far less than the same document at position 1, so we discount gains lower down the list — typically dividing by log2(rank + 1). This rewards putting good stuff on top.
4. Normalize: divide by the ideal DCG (the DCG of the perfect ordering) so the score lands in [0, 1], where 1.0 means "as good as it gets."

Looking at only the first k positions gives NDCG@k — we judge just the top of the list, because users rarely scroll past it.

import numpy as np

def dcg_at_k(relevances, k):
    """Discounted Cumulative Gain for the top k positions.
    relevances = list of relevance grades IN THE ORDER SHOWN to the user."""
    r = np.asarray(relevances, dtype=float)[:k]
    if r.size == 0:
        return 0.0
    # discount: position 1 -> /log2(2)=1, position 2 -> /log2(3), position 3 -> /log2(4)...
    discounts = 1.0 / np.log2(np.arange(2, r.size + 2))
    return float(np.sum(r * discounts))

def ndcg_at_k(relevances, k):
    """NDCG@k = DCG@k / IDCG@k, where IDCG uses the ideally sorted list."""
    dcg = dcg_at_k(relevances, k)
    ideal = sorted(relevances, reverse=True)   # best possible ordering
    idcg = dcg_at_k(ideal, k)
    return dcg / idcg if idcg > 0 else 0.0

# --- A tiny search result: 5 documents with relevance grades 0..3 ------------
# The TRUE best order would be [3, 3, 2, 1, 0]. Our model returns them
# in THIS order instead:
ranking = [1, 3, 0, 2, 3]
k = 3                         # judge only the top 3

print("Model ranking (top 5) :", ranking)
print(f"NDCG@{k} for model ranking : {ndcg_at_k(ranking, k):.3f}")

# --- Swap the first two positions to put a '3' on top ------------------------
better = [3, 1, 0, 2, 3]
print("Swapped ranking       :", better)
print(f"NDCG@{k} for swapped     : {ndcg_at_k(better, k):.3f}")

# --- The ideal ordering (sanity check: should be 1.0) ------------------------
ideal = [3, 3, 2, 1, 0]
print("Ideal ordering        :", ideal)
print(f"NDCG@{k} for ideal       : {ndcg_at_k(ideal, k):.3f}")

Model ranking (top 5) : [1, 3, 0, 2, 3]
NDCG@3 for model ranking : 0.491
Swapped ranking       : [3, 1, 0, 2, 3]
NDCG@3 for swapped     : 0.616
Ideal ordering        : [3, 3, 2, 1, 0]
NDCG@3 for ideal       : 1.000

Reading the result

• The model's ordering [1, 3, 0, 2, 3] puts a low-relevance 1 on top, so its NDCG@3 is well below 1.
• Swapping the first two slots to [3, 1, ...] lifts a high-relevance document to position 1, and NDCG@3 jumps up — that is the discount at work: gains at the top count much more than gains lower down.
• The ideal ordering [3, 3, 2, 1, 0] scores exactly 1.0.

A ranker's job is to push NDCG@k toward 1.0. Notice NDCG only cares about the order and the position — it completely ignores the raw scores the model emits, which is exactly the "ranking != regression" point from above.

10.3 Learning to Recommend

A recommender system suggests new content (a movie on Netflix, a book on Amazon, a song on Spotify) that a user is likely to enjoy, based on their consumption history. There are two traditional pillars:

• Content-based filtering learns what a user likes from the description of the content they consume. If you keep reading science-and-tech articles, it suggests more science-and-tech articles. You can think of it as building a small "will this user click?" classifier per user, using content features (words, topic, price, recency) as inputs.

• Collaborative filtering recommends based on what similar users consume or rate. If you and another user both loved the same ten movies, movies that user loved (but you haven't seen) are probably good picks for you. Crucially, it ignores the content itself and leans on the pattern of overlapping tastes.

Everyday analogy: Content-based is "you liked Italian food, here's more Italian food." Collaborative is "your foodie twin loved this place, so you probably will too."

Each has a weakness: content-based can trap users in a filter bubble (endless more-of-the-same, possibly items they already know about), while collaborative filtering struggles with cold starts and extremely sparse preference matrices (each user rates only a tiny fraction of items). Real systems are usually hybrid — they blend both signals.

The data: a giant, mostly-empty matrix

Collaborative filtering stores preferences in a user x item matrix: rows are users, columns are items, and each cell is a rating (or a 1 for "consumed"). In practice this matrix is huge and almost entirely empty — millions of users, hundreds of thousands of items, but each user touches only a handful. That sparsity is the central headache, and it is exactly what the next two algorithms (factorization machines and denoising autoencoders) are designed to handle. Let's visualize it first.

import numpy as np
import matplotlib.pyplot as plt

# --- Simulate a sparse user x item rating matrix (like a real recommender) ----
rng = np.random.default_rng(42)
n_users, n_items = 40, 60
density = 0.08                                  # each user rates ~8% of items
mask = rng.random((n_users, n_items)) < density
ratings = rng.integers(1, 6, size=(n_users, n_items)).astype(float)
R_sparse = np.where(mask, ratings, np.nan)      # missing -> NaN (drawn white)

plt.figure(figsize=(7, 5))
plt.imshow(R_sparse, aspect="auto", cmap="viridis", interpolation="nearest")
plt.colorbar(label="rating (1-5)")
plt.title("Sparse user x item matrix\n"
          f"({int(mask.sum())} known ratings out of {n_users*n_items} "
          f"= {100*mask.mean():.0f}% filled)")
plt.xlabel("item (movie)")
plt.ylabel("user")
plt.show()

10.3.1 Factorization Machines

Factorization machines (FM) were designed specifically for these sparse, high-dimensional datasets. A plain linear model is

$$f(\mathbf{x}) = b + \sum_i w_i\, x_i.$$

The problem: with one-hot user/item features, most $x_i$ are zero, so the model rarely sees most pairwise interactions $x_i x_j$, and it can't learn that "user A together with movie B" matters. Adding a separate weight $w_{ij}$ for every pair would explode the parameter count (about $D(D-1)$ new parameters).

FM's trick is to factorize each interaction weight as a dot product of two small learned vectors:

$$f(\mathbf{x}) = b + \sum_i w_i\, x_i + \sum_{i=1}^{D}\sum_{j=i+1}^{D} (\mathbf{v}_i \cdot \mathbf{v}_j)\, x_i x_j.$$

Each feature $i$ gets a $k$-dimensional factor vector $\mathbf{v}_i$ with $k \ll D$. Now the interaction weight between features $i$ and $j$ is $\mathbf{v}_i \cdot \mathbf{v}_j$, and the total extra parameters are only $Dk \ll D(D-1)$. Because factor vectors are shared across pairs, even a rarely-seen combination can borrow strength from related features — which is why FM generalizes far better than full pairwise weights on sparse data.

Everyday analogy: Instead of memorizing a separate opinion for every possible (user, movie) pair, FM gives each user and each movie a short "taste profile" vector, and estimates a pairing by how well the two profiles align.

import numpy as np

# --- A tiny user x movie rating matrix. NaN = "not rated" (the sparsity!) -----
R = np.array([
    [5, 4, np.nan, 1, np.nan],
    [np.nan, 5, 4, np.nan, 2],
    [1, np.nan, np.nan, 5, 4],
    [4, 3, np.nan, np.nan, 5],
])
print("Raw rating matrix (NaN = missing):\n", R)

# --- Fill the holes with the global mean, then TRUNCATED SVD ------------------
# This is the classic "matrix factorization" flavour of collaborative filtering:
# approximate the matrix as a low-rank product U @ V. The top factors capture
# the main "taste x item" structure and let us predict the missing cells.
# This is the same *factorization* spirit that FM generalizes to all features.
mask = ~np.isnan(R)
R_filled = np.where(mask, R, np.nanmean(R))     # temporary fill for the holes

k = 2                                           # keep only 2 factors (like FM's k)
U, s, Vt = np.linalg.svd(R_filled, full_matrices=False)
R_hat = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]   # low-rank reconstruction

print("\nLow-rank (k=2) prediction for EVERY user-item pair:\n",
      np.round(R_hat, 2))

# --- Highlight predicted ratings only for the originally-missing cells -------
pred_missing = R_hat.copy()
pred_missing[mask] = np.nan                     # blank out cells we already knew
print("\nPredicted ratings ONLY for missing cells (recommendation candidates):\n",
      np.round(pred_missing, 2))

Raw rating matrix (NaN = missing):
 [[ 5.  4. nan  1. nan]
 [nan  5.  4. nan  2.]
 [ 1. nan nan  5.  4.]
 [ 4.  3. nan nan  5.]]

Low-rank (k=2) prediction for EVERY user-item pair:
 [[5.21 3.95 3.54 1.25 3.25]
 [3.58 3.96 3.74 3.23 3.69]
 [1.2  3.48 3.53 5.22 3.78]
 [3.63 4.13 3.92 3.5  3.88]]

Predicted ratings ONLY for missing cells (recommendation candidates):
 [[ nan  nan 3.54  nan 3.25]
 [3.58  nan  nan 3.23  nan]
 [ nan 3.48 3.53  nan  nan]
 [ nan  nan 3.92 3.5   nan]]

Reading the result

The low-rank reconstruction R_hat predicts a rating for every user-movie pair, including the ones that were missing (NaN). The last matrix highlights just those predicted holes — these are exactly the cells a recommender would use to suggest "you haven't seen this, but you'd probably rate it four stars."

This is the factorization spirit that factorization machines generalize: represent users and items by small latent vectors, and estimate any pairing by how those vectors combine. FM extends the same idea to arbitrary sparse features (not just user/item IDs) by factorizing all pairwise interactions $x_i x_j$ through shared factor vectors.

10.3.2 Denoising Autoencoders (for recommendation)

You met denoising autoencoders (DAE) in Chapter 7: a neural net that rebuilds its input from a compressed bottleneck, after the input has been deliberately corrupted with noise. For recommendation, the trick is to reinterpret that corruption:

• The user's full set of liked items is the "clean" signal.
• Unseen-but-would-likely-enjoy items are treated as if a corruption process removed them.
• Train the autoencoder to reconstruct the clean, complete preference vector from the corrupted (partly-emptied) one.

At prediction time you feed in the user's known ratings, let the DAE reconstruct the full vector, and recommend the items whose reconstructed scores are highest — i.e. the ones the model "fills back in." Because the network must compress through a bottleneck, it learns latent tastes rather than memorizing ratings, which is what makes it work on sparse data.

A related collaborative-filtering model is a small two-input neural net: one one-hot input for the user, one for the item, and a single output predicting the rating $r$ (a sigmoid for $r \in [0,1]$, or a ReLU for $r \in [1,5]$). We leave these as concepts — the takeaway is that both factorization and autoencoders attack the same sparse-matrix problem from different angles.

10.4 Self-Supervised Learning: Word Embeddings

Where do word embeddings — the feature vectors that represent words, where similar words get similar vectors — actually come from? They are learned from data, and the clever part is that the data is unlabeled text. The labels are created automatically from the text itself, which is why this is called self-supervised learning.

The flagship algorithm is word2vec, and its most popular variant is skip-gram. The intuition is pure common sense:

You can often guess a missing word from its neighbors. In "I almost finished reading the ___ on machine learning," you'd guess book, article, or paper. Words that appear in similar contexts tend to have similar meanings.

Skip-gram turns this into a training task: take a center word and train a small neural net to predict the surrounding context words within a window (e.g. window size 5 = two words on each side). Each (center word -> context word) pair becomes a self-generated labeled example — no human annotation needed. After training, the weights of the hidden embedding layer are the word vectors: feed in a word's one-hot encoding, read out its embedding.

This is the essence of self-supervised learning: the structure of the data itself supplies the labels. (Large word2vec models use tricks like hierarchical softmax and negative sampling to stay tractable across huge vocabularies — good topics for further reading.)

import numpy as np

# --- A tiny corpus and a small vocabulary ------------------------------------
sentence = "the cat sat on the mat the dog sat on the log".split()
vocab = sorted(set(sentence))
word_to_idx = {w: i for i, w in enumerate(vocab)}
print("Vocabulary:", vocab)

# --- Extract skip-gram (center -> context) pairs with window size 2 ----------
# For each center word, pair it with the 2 words on its left and its right.
# These (center, context) pairs are the SELF-SUPERVISED training examples.
window = 2
pairs = []
for i, center in enumerate(sentence):
    for j in range(max(0, i - window), min(len(sentence), i + window + 1)):
        if j != i:
            pairs.append((word_to_idx[center], word_to_idx[sentence[j]],
                          center, sentence[j]))

print(f"\nGenerated {len(pairs)} self-supervised (center -> context) pairs")
print("(center_idx, context_idx, center_word, context_word):")
for p in pairs:
    print(p)

Vocabulary: ['cat', 'dog', 'log', 'mat', 'on', 'sat', 'the']

Generated 42 self-supervised (center -> context) pairs
(center_idx, context_idx, center_word, context_word):
(6, 0, 'the', 'cat')
(6, 5, 'the', 'sat')
(0, 6, 'cat', 'the')
(0, 5, 'cat', 'sat')
(0, 4, 'cat', 'on')
(5, 6, 'sat', 'the')
(5, 0, 'sat', 'cat')
(5, 4, 'sat', 'on')
(5, 6, 'sat', 'the')
(4, 0, 'on', 'cat')
(4, 5, 'on', 'sat')
(4, 6, 'on', 'the')
(4, 3, 'on', 'mat')
(6, 5, 'the', 'sat')
(6, 4, 'the', 'on')
(6, 3, 'the', 'mat')
(6, 6, 'the', 'the')
(3, 4, 'mat', 'on')
(3, 6, 'mat', 'the')
(3, 6, 'mat', 'the')
(3, 1, 'mat', 'dog')
(6, 6, 'the', 'the')
(6, 3, 'the', 'mat')
(6, 1, 'the', 'dog')
(6, 5, 'the', 'sat')
(1, 3, 'dog', 'mat')
(1, 6, 'dog', 'the')
(1, 5, 'dog', 'sat')
(1, 4, 'dog', 'on')
(5, 6, 'sat', 'the')
(5, 1, 'sat', 'dog')
(5, 4, 'sat', 'on')
(5, 6, 'sat', 'the')
(4, 1, 'on', 'dog')
(4, 5, 'on', 'sat')
(4, 6, 'on', 'the')
(4, 2, 'on', 'log')
(6, 5, 'the', 'sat')
(6, 4, 'the', 'on')
(6, 2, 'the', 'log')
(2, 4, 'log', 'on')
(2, 6, 'log', 'the')

Reading the result

From a single short sentence, window size 2 already produced a couple dozen (center -> context) training pairs — for free, with no labels provided by any human. Scale this up to billions of words of web text and you get the hundreds of millions of skip-grams that train real word2vec models. Words like "cat" and "dog" end up with similar embeddings because they share similar contexts ("sat", "the", "on"), which is exactly how the model discovers meaning from raw text.

That is self-supervised learning in one sentence: turn the data's own structure into supervised examples.

Key Takeaways

• A metric is a learnable object: by parametrizing Euclidean distance as $d_A(\mathbf{x},\mathbf{x'})=\sqrt{(\mathbf{x}-\mathbf{x'})^\top A (\mathbf{x}-\mathbf{x'})}$ with A positive semidefinite, we can train the distance (e.g. LMNN) and boost k-NN and clustering.
• Learning to rank optimizes the order of items, not absolute scores. The three framings are pointwise, pairwise, and listwise (LambdaMART is listwise and optimizes a ranking metric directly).
• NDCG@k measures ranking quality by discounting gains lower in the list and normalizing by the ideal ordering; 1.0 means a perfect ranking.
• Recommender systems use content-based filtering (item descriptions) and collaborative filtering (taste overlap); real systems are hybrid.
• The core challenge in recommendation is a huge, sparse user x item matrix.
• Factorization machines handle sparse features by factorizing pairwise interaction weights as $\mathbf{v}_i \cdot \mathbf{v}_j$, adding only $Dk$ parameters instead of $D(D-1)$.
• Denoising autoencoders recommend by reconstructing a user's (corrupted) preference vector and filling in the "missing" liked items.
• Self-supervised learning (e.g. word2vec skip-gram) manufactures its own labels from unlabeled data — a center word predicts its context — to learn word embeddings.

What's Next

In Chapter 11 — Conclusion, we'll step back and reflect on the whole journey: what you now know, what we deliberately left out, and where to go next as a practicing machine learning practitioner.

Exercises

These exercises cover the "other forms of learning" from Chapter 10: metric learning, learning to rank, recommender systems, and self-supervised word embeddings. Try each before reading the hint.

1. (Conceptual) What is the core idea of metric learning, and how does inserting a matrix A into the distance make it learnable? Hint: learn the distance from data; $d_A=\sqrt{(x-x')^\top A (x-x')}$; A = identity ⇒ plain Euclidean, diagonal A weights features, a full A also rotates/rescales the axes.
2. (Conceptual) Why must A be positive semidefinite for $d_A$ to be a valid metric? Hint: it guarantees the distance is never negative and respects the triangle inequality (this is the Mahalanobis distance governed by A).
3. (Conceptual) How does learning to rank differ from regression/classification, and what are the three framings? Hint: it optimizes the order of items, not absolute scores; the framings are pointwise, pairwise, and listwise (LambdaMART is listwise and optimizes a ranking metric directly).
4. (Conceptual) Explain NDCG in its four steps (relevance, cumulative gain, discount, normalize) and what NDCG@k = 1.0 means. Hint: sum the relevances, divide each by $\log_2(\text{rank}+1)$ so top positions count more, normalize by the ideal DCG; 1.0 means a perfect ordering.
5. (Conceptual) Contrast content-based and collaborative filtering, and name each one's main weakness. Hint: content-based uses item descriptions (risk of a filter bubble); collaborative uses taste overlap (cold-start and huge sparse matrices); real systems are usually hybrid.
6. (Conceptual) Why do factorization machines beat full pairwise weights on sparse data, in parameter-count terms? Hint: they factorize each interaction weight $w_{ij}$ as $\mathbf{v}_i \cdot \mathbf{v}_j$, adding only $Dk$ parameters instead of $D(D-1)$; shared factor vectors let rare combinations borrow strength.
7. (Conceptual) How does a denoising autoencoder recommend items? Hint: treat a user's liked items as the clean signal, corrupt it by removing some, train the net to reconstruct the full preference vector, and recommend the items it "fills back in."
8. (Conceptual) In word2vec skip-gram, where do the training labels come from, and what part of the network becomes the word vectors? Hint: no human labels — a center word predicts its context words within a window, so the text's own structure supplies the labels; the hidden embedding layer's weights become the word vectors.

Hands-On Coding Problems

9. (Coding) Metric learning via LDA: make a 2-feature dataset where feature 2 is mostly noise (stretch it wide), fit LinearDiscriminantAnalysis, transform X, then compare 5-NN accuracy on the raw vs transformed features. Hint: lda.transform(X) projects onto a learned separating direction; pass it to KNeighborsClassifier(n_neighbors=5).
10. (Coding) Learnable weighted distance: given a query and a few points, compute plain Euclidean distances and a diagonal-A weighted distance (up-weighting the informative feature); print both rankings to show the reordering. Hint: $d_A=\sqrt{\sum_j a_j (x_j-x'_j)^2}$; set the informative feature's $a_j$ large.
11. (Coding) NDCG from scratch: write dcg(rels) = $\sum_i \text{rels}_i / \log_2(i+1)$ and ndcg_at_k(rels, k) that sorts relevances descending for the ideal DCG; test it on [3, 3, 2, 1, 0] (should give 1.0) and [1, 3, 0, 2, 3] at k=3. Hint: normalize by dcg(sorted(rels, reverse=True)).
12. (Coding) Ranking comparison: for two orderings [1, 3, 0, 2, 3] and [3, 1, 0, 2, 3], compute NDCG@3 for each with your function from Exercise 11 and print which is better. Hint: the second ordering lifts a high-relevance item to the top, so it should score higher.
13. (Coding) Low-rank reconstruction (factorization spirit): build a small 4×5 ratings matrix with some np.nan holes, fill NaNs with 0, compute the SVD, truncate to k=2 components, reconstruct, and print the predicted values at the originally-missing positions. Hint: U, s, Vt = np.linalg.svd(R_filled); reconstruct U[:,:k] @ diag(s[:k]) @ Vt[:k,:].
14. (Coding) Skip-gram pair generation: given sentence = "the cat sat on the mat".split() and window size 2, generate all (center, context) training pairs and print them. Hint: for each center index i, loop over offsets in [-2,-1,1,2] that stay in bounds; skip out-of-range indices.

# Exercise 9: metric learning via LDA + 5-NN
import numpy as np
from sklearn.datasets import make_classification
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=300, n_features=2, n_informative=1,
                           n_redundant=0, n_clusters_per_class=1, random_state=0)
X[:, 1] *= 8  # stretch feature 2 -- make it noisy/wide
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)

# Baseline 5-NN on raw features
raw_acc = KNeighborsClassifier(n_neighbors=5).fit(Xtr, ytr).score(Xte, yte)

# TODO: fit LinearDiscriminantAnalysis() on Xtr, transform Xtr/Xte, then fit 5-NN on the transformed data
lda = None  # placeholder
lda_acc = 0.0  # placeholder

print("5-NN on raw features   :", raw_acc)
print("5-NN on LDA-projected  :", lda_acc)

# Exercise 10: plain Euclidean vs weighted distance
import numpy as np

query = np.array([1.0, 1.0])
points = np.array([[1.1, 9.0], [2.0, 1.5], [0.9, 8.0], [5.0, 1.2]])
# Feature 0 is informative; feature 1 is noise.
A = np.array([1.0, 1.0])  # placeholder: try [1.0, 0.01] to down-weight the noisy feature

# TODO: euclidean[i] = np.linalg.norm(query - points[i])
# TODO: weighted[i]  = np.sqrt(np.sum(A * (query - points[i])**2))
euclidean = np.zeros(len(points))  # placeholder
weighted = np.zeros(len(points))    # placeholder

print("euclidean order:", np.argsort(euclidean))
print("weighted order  :", np.argsort(weighted))

# Exercise 11: NDCG from scratch
import numpy as np

def dcg(rels):
    # TODO: sum(rels[i] / log2(i + 2)) for i in range(len(rels))  (rank i+1 -> log2(i+2))
    return 0.0  # placeholder

def ndcg_at_k(rels, k):
    # TODO: DCG of rels[:k] divided by DCG of sorted(rels, reverse=True)[:k]
    return 0.0  # placeholder

print("perfect order NDCG@5:", ndcg_at_k([3, 3, 2, 1, 0], 5))      # expected 1.0
print("mixed order NDCG@3  :", ndcg_at_k([1, 3, 0, 2, 3], 3))

# Exercise 12: compare two rankings with NDCG@3
# Reuse your dcg/ndcg_at_k from Exercise 11 (pasted below)
import numpy as np

def dcg(rels):
    return 0.0  # placeholder -- paste your implementation

def ndcg_at_k(rels, k):
    return 0.0  # placeholder -- paste your implementation

order_a = [1, 3, 0, 2, 3]
order_b = [3, 1, 0, 2, 3]

# TODO: print ndcg_at_k(order_a, 3) and ndcg_at_k(order_b, 3), and say which is better

# Exercise 13: low-rank SVD reconstruction of a sparse ratings matrix
import numpy as np

R = np.array([
    [5, 4, np.nan, 1, np.nan],
    [5, 5, np.nan, np.nan, np.nan],
    [np.nan, np.nan, 5, 4, 5],
    [np.nan, 1, 4, 5, 4],
])
missing = np.isnan(R)
R_filled = np.nan_to_num(R, nan=0.0)

# TODO: SVD, truncate to k=2, reconstruct
k = 2
# U, s, Vt = np.linalg.svd(R_filled, full_matrices=False)
# R_hat = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]
R_hat = np.zeros_like(R)  # placeholder

print("predicted values at missing positions:")
print(R_hat[missing])

# Exercise 14: generate skip-gram (center, context) pairs
sentence = "the cat sat on the mat".split()
window = 2

pairs = []
for i, center in enumerate(sentence):
    # TODO: for offset in range(-window, window+1): skip 0 and out-of-bounds;
    #       append (center, sentence[i + offset])
    pass

print("skip-gram pairs:")
for center, context in pairs:
    print(f"  ({center} -> {context})")