Personal study notes written in my own words from publicly available lectures and course pages. Not affiliated with or endorsed by Stanford University. No assignment solutions are published here.
What the course is about
Most machine learning courses assume the data fits in memory and that you can afford several passes over it. CS246 asks what happens when neither is true. The data is a web crawl, a click log, a social graph with billions of edges, or a stream that never stops. The recurring answer is to trade exactness for something you can actually compute: a hash instead of a comparison, a sketch instead of a count, a sample instead of a scan, a low-rank matrix instead of the full one. The course is about knowing which trade to make and what guarantee you keep.
You should be comfortable with basic probability (expectations, independence, the union bound), linear algebra (eigenvectors, matrix rank), and enough programming to write a MapReduce or Spark job. Prior machine learning helps for the recommender and SVM material but is not required. The course sits between systems and algorithms: it cares about disk reads and shuffles as much as about big-O.
The lectures group into three arcs. The first is infrastructure and pass-counting: MapReduce, frequent itemsets, similarity search with hashing. The second is linear algebra at scale: clustering, dimensionality reduction, recommenders, PageRank. The third is graphs, streams, and online decisions: community detection, streaming sketches, advertising, submodular optimization. Each arc ends with the same question: what did the approximation cost, and how would you know?
Lecture notes
01 · MapReduce and Spark
MapReduce writes a large computation as two functions. A map function reads one record and emits key-value pairs. The system groups all pairs by key and hands each group to a reduce function. Splitting the input across machines, retrying failed tasks, and moving intermediate data belong to the framework. Fault tolerance comes from a distributed file system that keeps several replicas of each chunk, so a dead machine costs a rerun rather than a restart.
The expensive step is the shuffle: the group-by-key phase where every mapper’s output is sorted and sent across the network to the right reducer. Word count is cheap because the shuffle is small relative to the input. A join between two large tables is expensive because the shuffle is the size of both tables. Combiners run a partial reduce on each mapper before the shuffle and help only when the reduce is associative and commutative.
Spark keeps the model but removes the disk round trip between stages. Data lives in resilient distributed datasets, transformations are lazy, and a lineage graph records how each partition was computed so lost partitions can be rebuilt. Narrow dependencies (map, filter) stay on one machine; wide dependencies (groupByKey, join) force a shuffle. Iterative algorithms such as PageRank and k-means gain the most, because the working set stays cached across iterations.
What goes wrong: a single hot key sends most of the data to one reducer, and a job that looks parallel becomes serial. Skewed joins need salting or a broadcast of the small side. The rest of the course assumes this substrate.
02 · Frequent itemsets: A-Priori and PCY
Market-basket analysis asks which sets of items appear together in many baskets. An itemset is frequent if its support (the number of baskets containing it) is at least a threshold $s$. Frequent itemsets yield association rules $I \to j$ with confidence $\text{conf}(I \to j) = \text{supp}(I \cup \{j\}) / \text{supp}(I)$. Confidence is misleading when $j$ is popular on its own, so interest is defined as $\text{conf}(I \to j) - \Pr[j]$; a rule matters when interest is far from zero in either direction.
The bottleneck is memory: counting all pairs of $n$ items needs roughly $n^2 / 2$ counters. A-Priori uses monotonicity: if a set is frequent, every subset is frequent. Pass one counts single items. Pass two counts only pairs whose two items were both frequent, which shrinks the candidate space enormously. Triples and beyond take one more pass each.
PCY (Park-Chen-Yu) uses the memory that A-Priori leaves idle in pass one. While counting items, hash every pair in each basket to a bucket and increment the bucket’s count. After the pass, buckets with count below $s$ become zeros in a bitmap. In pass two a pair is a candidate only if both items are frequent and the pair hashes to a frequent bucket.
| Method | Pass 1 memory | Pass 2 candidates |
|---|---|---|
| A-Priori | item counts | pairs of frequent items |
| PCY | item counts + bucket counts | frequent pairs in frequent buckets |
Typical mistake: setting $s$ too low, so the pair count explodes and pass two no longer fits. Frequent itemsets find related things; the next lecture finds similar things without enumerating pairs.
03 · Finding similar items: shingling, minhashing, LSH
Near-duplicate detection over $N$ documents cannot compare all $N^2 / 2$ pairs. Shingling turns each document into the set of its $k$-character substrings, so similar text becomes overlapping sets. Similarity is Jaccard:
Minhashing compresses each set to a short signature while preserving Jaccard similarity in expectation. Pick a random permutation of the universe of shingles and record, for each set, the first element under that permutation. The key property is
because the first element of $A \cup B$ under the permutation lands in $A \cap B$ with exactly that probability. With $n$ permutations (in practice, $n$ random hash functions), the fraction of matching signature rows estimates $J$.
Locality-sensitive hashing avoids comparing all signature pairs. Split the signature into $b$ bands of $r$ rows and hash each band to a bucket. Two documents become a candidate pair if they share a bucket in at least one band. The probability that a pair with similarity $s$ becomes a candidate is
an S-curve with threshold near $(1/b)^{1/r}$. Choosing $b$ and $r$ trades false positives (checked and discarded) against false negatives (never checked).
import numpy as np
def minhash(sets, n_hash, universe, seed=0):
rng = np.random.default_rng(seed)
sig = np.full((n_hash, len(sets)), np.iinfo(np.int64).max)
for i in range(n_hash):
perm = rng.permutation(universe)
for j, s in enumerate(sets):
sig[i, j] = min(perm[x] for x in s)
return sig
Common failure: shingles too short, so every document looks similar. The next lecture asks why banding works and what to hash for other distances.
04 · LSH theory and families for other distances
Banding is a special case of a general recipe. A family of hash functions is $(d_1, d_2, p_1, p_2)$-sensitive for a distance $d$ if any two points within distance $d_1$ collide with probability at least $p_1$, and any two points farther than $d_2$ collide with probability at most $p_2$. Minhash is such a family for Jaccard distance $1 - J$, with $p_1 = 1 - d_1$ and $p_2 = 1 - d_2$.
Two constructions sharpen any family. AND-construction takes $r$ independent functions and declares a match only if all agree, so collision probability becomes $p^r$, pushing low probabilities toward zero. OR-construction takes $b$ functions and declares a match if any agrees, giving $1 - (1 - p)^b$, pushing high probabilities toward one. Banding is AND within a band, then OR across bands. Stacking constructions steepens the S-curve at the cost of more hash evaluations.
Other distances have their own families. For cosine distance, pick a random vector $v$ and hash $x$ to the sign of $v \cdot x$; two vectors at angle $\theta$ collide with probability $1 - \theta / \pi$. For Euclidean distance, project onto a random line cut into buckets of width $a$. For Hamming distance, sample one bit position.
| Distance | Family | Collision probability |
|---|---|---|
| Jaccard | minhash | $J(A, B)$ |
| Cosine | random hyperplane sign | $1 - \theta / \pi$ |
| Euclidean | random projection, width $a$ | decreasing in $d / a$ |
| Hamming | bit sampling | $1 - d / n$ |
What goes wrong: the distance you hash for is not the distance you care about. The next lecture uses distance to group points rather than to find pairs.
05 · Clustering at scale
Clustering groups points so that intra-cluster distances are small. Hierarchical agglomerative clustering starts with every point as its own cluster and repeatedly merges the closest pair under some linkage. It produces a full tree but costs at least $O(n^2)$, which limits it to samples.
k-means fixes $k$, assigns each point to its nearest centroid, recomputes centroids as means, and repeats. Each pass reads the data once, so it fits MapReduce. Initialization matters: picking initial centroids far apart or from a hierarchical clustering of a sample avoids many bad local optima. The value of $k$ is usually chosen by watching average distance to centroid fall sharply and then flatten.
BFR (Bradley-Fayyad-Reina) is k-means for data that arrives in memory-sized chunks. It assumes clusters are roughly Gaussian and axis-aligned. Each cluster is summarized by the count $N$, the per-dimension sum, and the per-dimension sum of squares, which recover mean and variance. Points near a centroid by Mahalanobis distance are absorbed into that summary (the discard set). Points that cluster among themselves but not with any main cluster form a compression set. Isolated points wait in a retained set. Only summaries persist between chunks.
CURE drops the Gaussian assumption. It clusters a sample, keeps a handful of representative points per cluster, and shrinks them a fixed fraction toward the centroid. Remaining points join the cluster with the nearest representative, so non-spherical clusters survive.
What goes wrong: BFR on elongated or ring-shaped clusters, or k-means on data whose scale differs across dimensions. Reducing dimensions first, next, often helps.
06 · Dimensionality reduction: SVD and CUR
High-dimensional data often lies near a low-dimensional subspace, and singular value decomposition finds it. Any $m \times n$ matrix factors as $A = U \Sigma V^T$, where $U$ and $V$ have orthonormal columns and $\Sigma$ is diagonal with non-negative singular values in decreasing order. Keeping the top $k$ singular values gives the best rank-$k$ approximation in Frobenius norm:
The columns of $V$ are the directions of greatest variance, the columns of $U$ say how each row projects onto them, and the singular values say how much each direction matters. A common rule keeps enough singular values that their squared sum retains most of the total, often 80 to 90 percent.
SVD has two practical drawbacks. $U$ and $V$ are dense even when $A$ is sparse, so the factors can take more space than the original. And each latent direction mixes every column, which makes it hard to explain. CUR decomposition chooses actual rows and columns of $A$ instead. Sample $r$ columns with probability proportional to squared norm to form $C$, sample rows the same way for $R$, and build a small middle matrix $U$ from the intersection with a pseudo-inverse. Then $A \approx C U R$, with factors as sparse and interpretable as the data and error provably close to the SVD error for modest oversampling.
| Property | SVD | CUR |
|---|---|---|
| Optimality | best rank-$k$ | near-optimal with more samples |
| Sparsity of factors | dense | as sparse as $A$ |
| Interpretability | latent directions | real rows and columns |
Typical mistake: computing the full SVD when only the top few components are needed. Recommender systems, next, are the main application.
07 · Recommender systems
The setting is a utility matrix: rows are users, columns are items, most entries unknown. Content-based methods build an item profile from features, a user profile as a weighted average of the profiles of liked items, and recommend by cosine similarity. They need no other users and can explain their choices, but cannot suggest anything outside a user’s existing taste.
Collaborative filtering uses only the ratings. User-user CF finds users with similar rating vectors (Pearson correlation after centering) and predicts a rating as the similarity-weighted average of neighbors’ ratings. Item-item CF does the same with item vectors and usually works better because item similarity is more stable.
Latent factor models treat the matrix as approximately low rank and learn it directly. Represent user $u$ by $p_u$ and item $i$ by $q_i$ in $\mathbb{R}^k$, and predict $\hat{r}_{ui} = q_i^T p_u$. Fit only on known ratings with regularization:
Stochastic gradient descent updates one rating at a time: with error $e_{ui} = r_{ui} - q_i^T p_u$, set $p_u \leftarrow p_u + \eta (e_{ui} q_i - \lambda p_u)$ and symmetrically for $q_i$. Adding a global mean plus user and item biases helps noticeably.
Cold start is the standing problem. A new item has no ratings, so CF cannot place it, but content features can. A new user has no history, so neither works until a few interactions arrive. Hybrids and onboarding questions are the usual answers.
What goes wrong: evaluating on RMSE alone when the product cares about the top few recommendations, and running SVD on the full matrix so every missing entry counts as a zero. The next lecture applies low-rank thinking to a graph.
08 · PageRank and link analysis
A page is important if important pages link to it. Each page divides its rank equally among its out-links, and a page’s rank is the sum of what flows in. This is the stationary distribution of a random walk on the link graph, $r = M r$ for the column-stochastic matrix $M$. Power iteration computes it: start uniform, repeatedly multiply by $M$, stop when the change is small. Each step is one pass over the edges.
Two structures break the plain walk. Dead ends (pages with no out-links) leak rank out of the system. Spider traps (groups that link only among themselves) absorb all of it. Teleportation fixes both: at each step, with probability $\beta$ follow a random link, otherwise jump to a uniformly random page.
Here $d_i$ is the out-degree of $i$ and $N$ the number of pages; $\beta$ is typically 0.8 to 0.9. Dead ends are handled by redistributing their leaked mass uniformly.
Topic-sensitive PageRank replaces the uniform teleport with a jump into a chosen set $S$ of pages on a topic, producing a rank vector biased toward that topic. With $S$ a single node, the same vector serves as a proximity measure on any graph.
Link spam attacks the model directly: a spam farm points many controlled pages at one target and harvests the teleport mass they receive. TrustRank runs topic-sensitive PageRank from a set of trusted pages; the gap between a page’s PageRank and its TrustRank, called spam mass, flags likely spam.
Typical mistake: iterating without renormalizing after dead ends, so the vector drifts. The next lecture asks about the graph’s clusters rather than its ranking.
09 · Community detection in graphs
A community is a set of nodes with many edges inside and few leaving. Girvan-Newman finds communities top-down. It computes edge betweenness, the number of shortest paths between all node pairs that pass through each edge, removes the edge with the highest betweenness, and recomputes. Bridges between communities carry many shortest paths and go first. Betweenness needs a breadth-first search from every node, which makes the method expensive on large graphs.
Deciding where to stop, or how good any partition is, needs a score. Modularity compares the edges inside communities with what a random graph of the same degree sequence would have:
where $m$ is the edge count, $k_i$ is the degree of node $i$, and $\delta$ is one when $i$ and $j$ share a community. Values above roughly 0.3 indicate meaningful structure. The Louvain method greedily moves nodes to increase $Q$, collapses communities into super-nodes, and repeats, which scales to very large graphs.
Spectral clustering takes a different route. Build the Laplacian $L = D - A$ with $D$ the diagonal degree matrix. Its smallest eigenvalue is zero with the all-ones eigenvector. The eigenvector for the second-smallest eigenvalue (the Fiedler vector) gives a relaxed minimum balanced cut, and splitting nodes by its sign yields two communities. For $k$ communities, use the first $k$ eigenvectors as coordinates and run k-means.
| Method | Style | Scales to |
|---|---|---|
| Girvan-Newman | divisive, betweenness | thousands of edges |
| Louvain | greedy modularity | hundreds of millions of edges |
| Spectral | Laplacian eigenvectors | limited by the eigensolver |
What goes wrong: overlapping communities, which none of these handle directly. The next lecture leaves static graphs for data that arrives faster than it can be stored.
10 · Mining data streams
A stream arrives too fast and too long to store, so queries must be answered with memory far smaller than the stream.
Sampling: to keep a fixed fraction of a stream and still answer per-user questions, hash the user id and keep every element whose hash falls in a chosen range. Sampling by element instead of by key gives wrong answers to questions like “how many queries were repeated.”
Sliding windows: counting ones in the last $N$ bits exactly needs $N$ bits. DGIM (Datar-Gionis-Indyk-Motwani) uses $O(\log^2 N)$ bits by grouping ones into buckets whose sizes are powers of two, with at most one or two buckets of each size. The estimate sums all bucket sizes except half of the oldest, with error at most about 50 percent; allowing $r$ buckets per size cuts the error to about $1 / r$.
Membership: a Bloom filter uses $m$ bits and $k$ hash functions. Insert by setting the $k$ bits; test by checking them. There are no false negatives. After $n$ insertions the false positive rate is approximately
minimized at $k \approx (m / n) \ln 2$.
Distinct counting: Flajolet-Martin hashes each element and records $R$, the maximum number of trailing zeros seen. The estimate is
because a hash with $r$ trailing zeros appears with probability $2^{-r}$. One estimate is noisy; the fix is the mean within groups of hash functions and the median across groups.
Frequency: a count-min sketch keeps one small counter array per hash function, increments one counter per row on each arrival, and answers with the minimum over rows. It never underestimates.
Typical mistake: reusing one hash function for sampling and for a sketch, which correlates their errors. The next lecture must make decisions on a stream rather than estimates.
11 · Computational advertising and online algorithms
Search advertising matches queries to ads as queries arrive. Each advertiser has a bid per query and a daily budget. The AdWords problem asks which ad to show for each query, without knowing future queries, to maximize revenue. Decisions are irreversible and the input is revealed one item at a time.
Online algorithms are judged by the competitive ratio: the worst-case ratio of the online algorithm’s value to the value of the best offline algorithm that saw the whole sequence. The warm-up is online bipartite matching, where greedy is $1 / 2$-competitive and no deterministic algorithm does better.
For AdWords, greedy (pick any advertiser with remaining budget) also has ratio $1 / 2$: an adversary can spend one advertiser’s budget on queries another could have served, then send queries only the exhausted one wanted. BALANCE assigns each query to the eligible advertiser with the most remaining budget. With two advertisers and equal budgets it achieves $3 / 4$; with many advertisers it achieves $1 - 1 / e \approx 0.63$, the best possible for a deterministic algorithm here.
When bids and budgets differ, generalized BALANCE scores each advertiser by bid times $1 - e^{-(1 - f_i)}$, where $f_i$ is the fraction of budget already spent, and picks the highest. The same $1 - 1 / e$ ratio holds.
| Algorithm | Competitive ratio |
|---|---|
| Greedy | $1 / 2$ |
| BALANCE, two equal advertisers | $3 / 4$ |
| BALANCE, many advertisers | $1 - 1 / e$ |
What goes wrong: reading the ratio as typical-case performance. It is a worst case that rarely occurs, but nothing rules it out. The next lecture returns to supervised learning at scale.
12 · Learning from large data
A support vector machine finds the hyperplane $w \cdot x + b = 0$ that separates classes with the largest margin. Allowing violations through slack gives the soft-margin objective
where $C$ trades margin against training error. The hinge loss is convex, so stochastic gradient descent works: sample one example, step on the regularizer, and add a step on the hinge term if the example is inside the margin. One pass over a very large dataset often beats many passes over a subsample. Batch gradient descent needs a full scan per step, one MapReduce job per iteration; SGD needs a single sequential read. Kernels are usually avoided at scale because the kernel matrix is $n^2$.
Decision trees are harder to distribute because each split depends on the previous ones. The practical approach builds the tree level by level: each job scans the data once and computes, for every candidate split at every current leaf, an aggregate such as variance reduction or Gini impurity, and the driver picks the best split per leaf. Candidate thresholds come from approximate quantiles. Once a leaf’s data fits in memory, its subtree finishes locally.
| Model | Distributed cost per step | Notes |
|---|---|---|
| Linear SVM with SGD | sequential read | one machine often suffices |
| Batch gradient | full scan | one job per iteration |
| Decision tree | full scan per level | histogram aggregation |
Typical mistakes: not shuffling the data before SGD, and comparing a tuned nonlinear model on a sample against a linear model on everything. The next lecture asks when greedy is provably good.
13 · Optimizing submodular functions
Many “pick the best $k$ things” problems share a diminishing-returns structure: which $k$ people to seed with a product, which $k$ blogs to read to catch most stories early, which $k$ sensors to place. A set function $f$ is submodular if for all $A \subseteq B$ and any $x \notin B$,
Influence maximization is the canonical example. Under the independent cascade model each newly activated node gets one chance to activate each neighbor with an edge probability. The expected number of nodes eventually activated is monotone and submodular in the seed set, and finding the best seed set of size $k$ is NP-hard.
The greedy algorithm adds, at each of $k$ steps, the item with the largest marginal gain. For any monotone submodular function it guarantees
where $S^*$ is the optimal set of size $k$. The proof shows that each step closes at least a $1 / k$ fraction of the remaining gap to optimal, and $(1 - 1 / k)^k \leq 1 / e$. Without submodularity greedy can be arbitrarily bad.
Evaluating $f$ for influence means simulating cascades, which is slow. Lazy greedy uses submodularity again: an item’s marginal gain can only fall as the set grows, so a priority queue of stale gains lets you skip re-evaluating items whose old gain is already below the current best, with no loss in guarantee.
What goes wrong: applying greedy to a non-submodular objective and quoting the bound anyway. The next lecture points to where graph learning went after these methods.
14 · Graph neural networks pointer
Every graph lecture so far builds features by hand: PageRank scores, community labels, spectral coordinates. Graph neural networks learn them. Each node starts with an input vector, and a layer updates it by aggregating messages from the node’s neighbors and combining the result with its own state. Stacking $L$ layers gives each node a receptive field of its $L$-hop neighborhood. The aggregation must be permutation-invariant (mean, sum, max), and parameters are shared across nodes, so the model applies to nodes and graphs it has not seen.
Two ideas connect back to this course. First, scaling: a full-graph forward pass over billions of edges does not fit, so practical systems sample a fixed number of neighbors per node per layer and train on mini-batches of target nodes. Second, the spectral view: a mean-aggregation layer is one step of the same normalized adjacency propagation that appears in PageRank and spectral clustering, so a GNN with no nonlinearity reduces to smoothed feature propagation.
Where they help: node classification when features and structure both carry signal, link prediction, and recommendation on user-item graphs where a two-hop message pass reconstructs collaborative filtering. Where they struggle: deep stacks oversmooth representations toward one vector, and graphs where neighbors tend to differ break the assumption aggregation encodes.
Typical mistake: comparing a GNN against a weak baseline; a linear model on structural features is often competitive. A full treatment belongs to CS224W. The last lecture steps back to the trade the whole course makes.
15 · Choosing approximations honestly
Every method here replaces an exact computation with a cheaper one that is right in expectation, right within a bound, or right most of the time. Choosing well means being explicit about which of these you get and what it costs.
Some approximations guarantee something about a single answer: minhash is unbiased for Jaccard, a Bloom filter has no false negatives, count-min never underestimates, greedy on a submodular function is within $1 - 1 / e$ of optimal. Others hold only over a distribution: the LSH S-curve gives a probability per pair, not a promise about any pair; Flajolet-Martin is noisy until averaged; BALANCE’s ratio is a worst case. Others have no guarantee and simply work on typical data: k-means, Louvain, item-item CF. The rung a method sits on should appear in any description of its results.
Cost has more than one axis. Passes over the data matter more than arithmetic when the data lives on disk. Shuffle volume matters more than passes in a cluster. Memory bounds decide whether a streaming sketch is possible at all. Query-time latency is separate from build cost: LSH and PageRank pay once and then answer by lookup. Reporting one axis while ignoring the one that binds is the usual way to make an approximation look better than it is.
A working procedure: compute the exact answer on a sample small enough to afford it, run the approximation on the same sample, and report the gap next to the speedup. Then probe the known failure modes: skewed keys, short shingles, elongated clusters, popular items, dead ends, correlated hash functions. A claim that cannot be traced to a bound, a distributional assumption, or a measured comparison is an anecdote. That habit, more than any single algorithm, is what the course leaves you with.
Key equations at a glance
| Concept | Equation | When it applies |
|---|---|---|
| Jaccard similarity | $J(A, B) = \lvert A \cap B \rvert / \lvert A \cup B \rvert$ | comparing sets such as shingled documents |
| Minhash property | $\Pr[h_\pi(A) = h_\pi(B)] = J(A, B)$ | estimating Jaccard from short signatures |
| LSH S-curve | $P(s) = 1 - (1 - s^r)^b$ | chance a pair with similarity $s$ is a candidate under $b$ bands of $r$ rows |
| Confidence and interest | $\text{conf}(I \to j) = \text{supp}(I \cup \{j\}) / \text{supp}(I)$, interest $= \text{conf} - \Pr[j]$ | ranking association rules |
| PageRank with teleport | $r_j = \sum_{i \to j} \beta r_i / d_i + (1 - \beta) / N$ | ranking nodes in a graph with dead ends or spider traps |
| SVD reconstruction | $A \approx U_k \Sigma_k V_k^T$ | best rank-$k$ approximation in Frobenius norm |
| Latent factor loss | $\sum_{(u, i)} (r_{ui} - q_i^T p_u)^2 + \lambda (\sum_u \lVert p_u \rVert^2 + \sum_i \lVert q_i \rVert^2)$ | fitting a recommender on known ratings only |
| Modularity | $Q = \frac{1}{2m} \sum_{i, j} (A_{ij} - k_i k_j / 2m) \delta(c_i, c_j)$ | scoring a community partition |
| Bloom filter false positive rate | $(1 - e^{-kn / m})^k$ | $m$ bits, $k$ hashes, $n$ inserted items |
| Flajolet-Martin estimate | $\hat{n} = 2^R$, $R$ the max trailing zeros | counting distinct stream elements in $O(\log n)$ bits |
| Soft-margin SVM | $\frac{1}{2} \lVert w \rVert^2 + C \sum_i \max(0, 1 - y_i (w \cdot x_i + b))$ | linear classification with SGD at scale |
| Greedy submodular bound | $f(S_{\text{greedy}}) \geq (1 - 1 / e) f(S^*)$ | monotone submodular maximization under a size constraint |
Common mistakes
- Emitting a hot key from the mapper so one reducer receives most of the data. Fix: salt the key or broadcast the small side of a join.
- Using shingles that are too short, so almost every pair looks similar. Fix: choose $k$ so the space of possible shingles far exceeds the shingles in any one document; 5 to 9 characters is typical for text.
- Picking $b$ and $r$ for LSH without checking the S-curve threshold. Fix: compute $(1 / b)^{1/r}$ and compare it with the similarity you want to catch.
- Running SVD on a ratings matrix with missing entries filled as zero. Fix: fit a latent factor model on known entries only, with regularization.
- Iterating PageRank without handling dead ends, so total rank shrinks each step. Fix: renormalize or redistribute leaked mass uniformly.
- Assuming BFR will find clusters that are not roughly Gaussian and axis-aligned. Fix: use CURE or reduce dimensions first.
- Reading a Bloom filter or count-min answer as exact. Fix: report the false positive rate or overestimate bound alongside it.
- Quoting the $1 - 1 / e$ greedy bound for an objective that is not submodular. Fix: verify diminishing returns before claiming the guarantee.
Related courses
- CS224W continues the graph arc: PageRank, community detection, and the GNN pointer here become the main subject there.
- CS229 gives the statistical foundation for the SVM, latent factor, and k-means material.
- CS230 covers the deep learning side of recommenders and large-scale training that this course only touches.
- CS224N uses text representations and similarity search in a language setting.
- CS336 treats the systems side of training at scale, where the shuffle and pass-counting instincts from MapReduce reappear.