Scalable
Machine Learning

Split the WORK, or split the MODEL — these are the two genuinely different axes of "distributed" machine learning, and CityCourier's tiny linear model only ever needs one of them.

A weight and a bias — two numbers — fit on any machine ever built. CityCourier's regression only ever needs data parallelism; model parallelism becomes relevant at a scale (billion-parameter models) this course doesn't otherwise touch.

Why the Closed-Form Formula Doesn't Just "Scale Up"

Linear regression has an exact, one-step formula (ordinary least squares, solved via matrix inversion) that a statistics course teaches first. It needs the entire dataset assembled into one matrix before a single operation can run. Gradient descent needs something much weaker at each step: a sum and a count, computable independently on each machine's own slice and combined afterward.

Worked Example · Same Answer, Two Very Different Appetites for Data Access

Practice

1. Computing the MEAN delivery time across all 15 clean orders, split across 3 machines: is this data parallelism, model parallelism, both, or neither?
   Solution

   Data parallelism — there's no "model" here at all, just an aggregation (sum and count) computed locally per machine and combined. Same shape as Section 3.3's combiner, not machine learning in the model-fitting sense, but the same underlying pattern.

2. A recommendation model has one billion parameters, too large for any single machine's memory, trained on a modest, single-machine-sized dataset. Which kind of parallelism does this scenario need?
   Solution

   Model parallelism — the data fits fine on one machine; it's the MODEL that doesn't fit anywhere. Different machines would hold different slices of the billion parameters, needing to coordinate during each forward/backward pass, the opposite bottleneck from CityCourier's tiny-model, split-data scenario.

3. Why can't an exact median (not mean) be computed the same aggregate-and-combine way as a sum or count across partitions?
   Solution

   A median needs the actual relative ORDER of every value against every other value to find the true middle one; two machines' local medians don't combine into the global median through any simple arithmetic the way two local sums add into a global sum. (Approximate streaming median algorithms exist, but they trade exactness for exactly this reason.)

4. Section 3.4 showed that a data-skewed key can't be fixed just by adding more reducers. Does adding more machines fix a poorly-parallelizable ML algorithm the same way it fails to fix skew?
   Solution

   Similar failure shape — more machines only help the parts of a computation that genuinely decompose into independent, combinable pieces. An algorithm whose core step needs global information (a closed-form matrix inversion, an exact sort) doesn't get any easier to distribute just because more machines are available, the same way more reducers didn't split Curry Point's single hot key.

Predicting delivery time from order amount (correlation 0.74 on the 15 veracity-clean orders — order #10 stays excluded, exactly as training on a known-impossible label would corrupt the fit before it starts) is a one-weight, one-bias linear model. Gradient descent nudges both numbers, repeatedly, in the direction that reduces squared error — and each nudge only needs a sum over whatever rows are locally available.

Worked Example · Fitting the Line, Centrally

Starting from w=0, b=0, learning rate 0.01, on amount scaled to hundreds of rupees:

Worked Example · The Same First Step, Split Across Two Machines

Split the 15 rows unevenly — 11 rows on one machine, 4 on the other, an imbalance no worse than Section 1.5's 11-vs-5 node split — and compute epoch 1's gradient on each machine separately, at the starting point w=0,b=0.

See the Gap

Practice

1. If the split were even (7 vs 8 rows instead of 11 vs 4), would naive averaging still produce an error?
   Solution

   Yes, generally — naive averaging is only guaranteed correct when the partition sizes are EXACTLY equal (7 vs 8 still differ). The error would likely be smaller than the 11-vs-4 case's 6.7%, since the imbalance is milder, but "smaller" isn't "zero" unless the split is perfectly even.

2. Three machines hold 5, 5, and 5 rows respectively. Does naive (unweighted) averaging give the correct combined gradient here?
   Solution

   Yes — with equal partition sizes, the weighted average and the naive average are the same calculation (each weight is 5/15 = 1/3 either way). Naive averaging is a special case of weighted averaging that happens to be correct only when every partition is the same size.

3. Section 3.1's ApplicationMaster tracked task completion for one job. In distributed gradient descent, what would need to be tracked before the driver can safely combine that epoch's gradients?
   Solution

   That every machine's local gradient for the current epoch has actually arrived, and how many rows each one was computed over. Combining early — using only 2 of 3 machines' results because the third hasn't reported yet — would silently produce a partial, biased gradient, structurally identical to this section's weighting bug even though the cause is different (missing data rather than wrong arithmetic).

4. Connect this to Section 5.6: is an unweighted-average bug a "delivery" problem the way duplicate message processing was, or something else?
   Solution

   Something else entirely — nothing was delivered twice or lost. Every machine's gradient arrived exactly once and was used exactly once; the bug is purely in the COMBINING FORMULA applied to correctly-delivered data. Section 5.6's fixes (idempotency, exactly-once semantics) wouldn't touch this bug at all, since the problem isn't in how many times data arrived but in the arithmetic once it did.

K-means repeats two steps until nothing changes: assign every point to its nearest of K centroids, then move each centroid to the mean of the points assigned to it. Lloyd's algorithm, and both steps distribute cleanly — assignment only needs a point and the current centroids (no cross-machine communication), and recomputing a centroid is exactly Section 3.3's sum-and-count combiner pattern.

Worked Example · Clustering by Order Amount, K=2

Starting centroids ₹150 and ₹560 (deliberately far apart, no special meaning), on the 15 veracity-clean orders:

Step Through the Iteration

Practice

1. If Block 2's contribution to cluster 1 (sum=780, count=3) were lost due to a machine failure before the driver combined the round, what would the resulting centroid be, and is this the same kind of problem Section 3.6 addressed?
   Solution

   Cluster 1's centroid would be computed from only 1,870÷7 = ₹267.1 instead of the correct ₹265.0 — close, but silently wrong, using 7 of the true 10 points. Yes, structurally the same problem as Section 3.6: a lost partial result needs to be detected and either retried or recomputed from lineage, not silently omitted from the combination.

2. With K=3 instead of K=2, would the assign step's cost per point change?
   Solution

   Slightly — each point now compares against 3 centroids instead of 2, a small constant-factor increase, not a fundamental change. The assign step remains purely local and embarrassingly parallel regardless of K.

3. Two different machines, run independently with different random seeds for initial centroids, produce different final clusterings for the same 15 orders. Does this mean K-means is broken?
   Solution

   No — this section's pitfall box already flagged it: K-means can converge to different local answers depending on starting centroids. It's a known property of the algorithm (not a distributed-computing bug), which is why production use runs multiple initializations and picks the best-scoring result rather than trusting any single run.

4. Section 6.1 distinguished algorithms that decompose into aggregable statistics from those that don't. Does K-means's ASSIGN step (finding each point's nearest centroid) require any aggregation at all?
   Solution

   No — assignment is a pure per-point computation against the current (already-known) centroids, needing no aggregation and no cross-machine communication whatsoever. Only the RECOMPUTE step aggregates. K-means is actually two different kinds of step glued together, one trivially parallel and one requiring combination, which is worth noticing precisely because they're so often described as a single undifferentiated "iteration."

Predict "high rating" (4–5 stars) versus "low" (1–3) from which hub an order came from. Sections 1.1's three missing-rating orders (#3, #7, #11) can't train or be predicted against a label they don't have — 13 of 16 orders remain.

Every quantity above is a count, or a ratio of counts. "Training" a Naive Bayes classifier isn't an iterative search like Section 6.2's gradient descent — it's tallying, once, and dividing.

Worked Example · Counting in Parallel

Identical shape to Section 3.2's restaurant-count MapReduce job — each block counts locally, a global sum combines them, and the "model" is nothing but this table plus the equally simple low-rating version of it.

Practice

1. Using this section's counts, compute P(Hub S | high) and P(Hub S | low) with Laplace smoothing.
   Solution

   P(Hub S|high) = (2+1)/(10+3) = 3/13 ≈ 0.231. P(Hub S|low) = (2+1)/(3+3) = 3/6 = 0.5 — matching the worked example's stated values exactly.

2. Classify a new Hub S order using this section's priors and the Hub S probabilities above. Which class wins?
   Solution

   score(high) = 0.769 × 0.231 ≈ 0.178. score(low) = 0.231 × 0.5 ≈ 0.116. High still wins, but by a much smaller margin than the Hub E case (normalized confidence ≈ 60.6% instead of 88.5%) — Hub S's orders are relatively more associated with low ratings than Hub E's, and the model's confidence reflects that.

3. If Block 2 had actually gone offline before reporting its local counts (1 high at Hub N, 1 high at Hub E, 1 low at Hub S), how would that change the global counts, and is the resulting model simply "less accurate" or something worse?
   Solution

   Global high counts would read N=3,S=1,E=3 instead of N=4,S=2,E=4 — not just less accurate, systematically biased toward whichever blocks DID report, since the missing block's specific rows are silently absent rather than randomly sampled out. This is the same "missing partition contribution" failure mode flagged in Section 6.3's practice, now applied to Naive Bayes counting instead of K-means recomputation.

4. Section 6.1 asked whether an algorithm's inner step reduces to aggregable statistics. Does Naive Bayes's PREDICTION step (classifying one new order) need any cross-machine aggregation at all?
   Solution

   No — once the counts (the "model") are computed and available, classifying a single new order is a handful of multiplications against already-known probabilities, needing no further access to the training data or any other machine. Training aggregates; prediction, given a trained model, doesn't.

A train/test split needs to behave like a fair, random sample of the whole dataset. The easiest thing to actually implement — each machine holding out its own last 20% — isn't that, and the difference is exactly Chapter 5's ordering problem wearing a different hat.

Worked Example · Two Ways to Get "80/20"

On these 15 rows the two test sets happen to look similarly balanced by hub — small-sample luck, not a guarantee. The real risk isn't visible in fifteen rows at all: at citywide volume, if order characteristics genuinely drift over the course of a rush (later orders skewing toward different hubs, larger group orders, whatever pattern actually holds), a contiguous tail-as-test-set inherits that drift wholesale, and a model evaluated against it gets judged on a systematically unrepresentative slice.

The Same Problem, K Times: Cross-Validation

K-fold cross-validation repeats the split K times, holding out a different fold each round and training on the rest, then averages the K evaluation scores. It's not a different problem from the single 80/20 split — it's the identical distributed-shuffle requirement, paid K times instead of once, specifically so a model's evaluation doesn't depend on the luck of one particular split.

Practice

1. Would a train/test split based on HUB (all of Hub N's orders as test, everyone else as train) share the naive time-ordered split's core problem?
   Solution

   Yes, the identical shape of problem — the test set is defined by a characteristic (hub) that might itself correlate with the thing being predicted, rather than being an unbiased random sample. Any split correlated with a real attribute of the data risks this, not just time.

2. In 5-fold cross-validation on these 15 rows, roughly how many rows would each fold hold out?
   Solution

   15÷5 = 3 rows per fold — five rounds, each training on the other 12 and testing on a different 3, cycling through until every row has been in exactly one test fold.

3. Section 2.3 showed consistent hashing distributing keys without regard to any business meaning. Could a hash-of-order-id assignment be used to build a fair random train/test split?
   Solution

   Yes, cleanly — hash each order id, and route it to "train" or "test" based on the hash value (say, below some threshold goes to test). Since the hash has no relationship to arrival order, hub, or any other real attribute (Section 2.3's whole point), this produces exactly the "any 20% with equal probability" property this section's pitfall box asked for, and can be computed independently on each partition with no coordination beyond agreeing on the hash function and threshold.

4. A model trained with Section 6.2's gradient descent is evaluated only on the naive tail-of-stream test set (orders #14–16). Its MSE looks great. Should that result be trusted?
   Solution

   Not fully — a good score on a non-representative test set only tells you the model fits that particular slice, which this section already flagged as potentially unlike the data as a whole. The fix isn't necessarily distrust of the model itself, but re-evaluating on a properly shuffled (or cross-validated) split before trusting the number enough to act on it.

1. Two machines hold 8 and 8 rows. Does averaging their local gradients without weighting give the correct combined gradient?
   Solution

   Yes — with equal partition sizes, unweighted and weighted averaging compute the same result. The bug only appears when partitions differ in size.

2. Which K-means step needs no communication between machines at all: assign or recompute?
   Solution

   Assign — each point only needs comparison against the already-known current centroids, entirely local. Recompute needs every machine's partial sums combined.

3. A Naive Bayes model has zero training examples of "low-rated Hub E orders." Without smoothing, what happens to any future Hub E order's probability of being classified low?
   Solution

   It becomes exactly zero, permanently, regardless of any other evidence — an unsmoothed zero count makes an outcome flatly impossible rather than merely unlikely. Laplace smoothing exists specifically to prevent this.

4. Why does a closed-form (matrix-inversion) solution to linear regression resist data-parallel distribution better than gradient descent does?
   Solution

   It needs the entire dataset assembled into one matrix before any single operation can proceed, unlike gradient descent's per-step reliance on locally-computable, aggregable partial sums.

5. A train/test split is built by hashing order id and routing below a threshold to test. Is this split's fairness affected by which hub, restaurant, or arrival time each order has?
   Solution

   No — a well-chosen hash has no relationship to any of those attributes, which is exactly the property that makes it a fair substitute for a true random shuffle.

6. A billion-parameter model needs to be split across machines because no single machine's memory can hold it. Is this data parallelism or model parallelism?
   Solution

   Model parallelism — the constraint is the model's size, not the data's, the opposite bottleneck from Chapter 6's CityCourier examples.

7. In distributed K-means, Block 3 reports its partial sum and count for cluster 2 twice due to a retried message. What happens to the resulting centroid if the driver isn't careful?
   Solution

   Cluster 2's centroid would be computed with Block 3's contribution counted twice, pulling the mean toward Block 3's points more than it should — a double-counting problem structurally identical to Section 5.6's duplicate-message issue, just occurring in a training aggregation instead of a revenue count.

8. Does 5-fold cross-validation require 5× as much raw data as a single 80/20 split?
   Solution

   No — it reuses the same dataset five times, each round holding out a different fold. It costs roughly 5× the TRAINING compute (fitting five separate models), not five times the data.

• Mining of Massive Datasets — Leskovec, Rajaraman & Ullman. Its machine learning chapters cover distributed K-means, Naive Bayes, and gradient-based methods (Sections 6.2–6.4) with the same MapReduce-flavoured lens this chapter used throughout.
• Spark: The Definitive Guide — Chambers & Zaharia. MLlib's actual implementations of everything in this chapter, including how partition-size weighting (Section 6.2) and cross-validation (Section 6.5) are handled in production code.
• Designing Data-Intensive Applications — Martin Kleppmann. Not ML-specific, but its treatment of what makes a computation decomposable (Section 6.1's core question) underlies why some algorithms distribute cleanly and others resist it.