Representation learning: why depth learns hierarchical features, not one big lookup

The problem, from first principles

[01-universal-approximation] showed that a single wide hidden layer CAN, in principle, approximate any function. But "can, in principle" and "is a good idea in practice" are very different claims, and this question is about the gap between them. Imagine trying to classify images by a simple lookup table: store the correct label for every possible image you might ever see. This fails catastrophically for a completely obvious reason: the number of possible images (even small ones) is astronomically, exponentially large, so a lookup table would need to be unimaginably huge, and would have learned NOTHING about any image it hadn't seen during "training" (it's not really learning at all, just memorizing).

Real neural networks avoid this trap through SHARING: a feature detected at one layer (a low-level pattern, like "this looks like an edge going diagonally") can be REUSED by every combination of higher-level features that happens to depend on it, instead of that edge-detection logic being re-derived, or separately memorized, for every possible image that happens to contain a diagonal edge somewhere. This is the core intuition behind why depth (stacking layers, each building on features the previous layer already extracted) tends to work far better in practice than one enormous, un-shared lookup table: a shared feature layer's PARAMETER COUNT grows only proportionally to the number of underlying features, while the number of possible COMBINATIONS of those features (what a lookup table would need to separately store) grows exponentially.

From theory to code

Implement lookup_table_size(num_features) (the number of entries a pure lookup table needs, one per possible combination of num_features binary features: 2^num_features), shared_feature_layer_size(num_features, num_hidden) (the number of parameters a single shared (num_features -> num_hidden) linear layer needs, reusable across every combination), and capacity_ratio(num_features, num_hidden) (how many times larger the lookup table is than the shared layer).

Constraints

• lookup_table_size must compute 2 ** num_features exactly (one entry per distinct binary combination of num_features features).
• shared_feature_layer_size must compute the SAME parameter count [02-layers/01-linear-forward]'s linear_forward would need for a (num_features -> num_hidden) layer: weight has num_features * num_hidden entries, bias has num_hidden entries.
• capacity_ratio must be lookup_table_size(num_features) / shared_feature_layer_size(num_features, num_hidden), reusing both functions above.

Hints