Grid search over a hyperparameter grid

The problem, from first principles

03-bias-variance-tradeoff shows that a model's complexity — its hyperparameters — controls where it lands on the bias/variance tradeoff, and that neither extreme wins. But nothing so far in this curriculum has picked those hyperparameters systematically; learning_rate, max_depth, n_trees, lam have all been chosen by hand, by the person writing the training call, not discovered from the data.

The most literal fix: define a small set of candidate values for each hyperparameter, actually try every combination of them by training and validating a real model for each one, and keep whichever combination scored best. No cleverness, no assumptions about which hyperparameters matter more — just brute-force coverage of a defined search space.

From theory to code

Implement generate_param_combinations(param_grid) to enumerate every combination, then grid_search(param_grid, fit_and_score_fn) to score each one and track the winner. fit_and_score_fn is a black box supplied by the caller — it trains a model with one specific set of hyperparameters and returns a validation score, higher is better; this question doesn't care what model it is, just how to search over its hyperparameters.

Constraints

• param_grid: a dict mapping each hyperparameter name to a list of candidate values.
• generate_param_combinations returns a list of dicts, one per combination — the Cartesian product of every hyperparameter's candidate values, e.g. {"lr": [0.01, 0.1], "depth": [2, 3]} produces 4 combinations.
• The number of combinations returned must equal the product of each hyperparameter's candidate-list length.
• grid_search returns a dict with "best_params" (the params dict that scored highest), "best_score" (that score), and "all_scores" (a list of (params, score) for every combination tried, in the order tried).
• Ties aside, the combination with the strictly highest score wins — never the lowest.
• fit_and_score_fn is called exactly once per combination.

Hints

Open one at a time. Each gives away a little more than the last.