Choose λ with a validation set

λ is a hyperparameter: it is chosen by trying several values and comparing them on data the model did not train on.

What to build

A program that fits a ridge line for each candidate λ and picks the best one by validation error.

Requirements

  • For each λ, in the given order, fit w = Sxy / (Sxx + λ), b = ȳ − w x̄ on the training points.
  • Print lambda L: w W, validation MSE V, with L written as in the input and W and V with 4 decimal places.
  • Finally print best lambda L for the smallest validation MSE (the earlier one on a tie).

Input

Line 1: the λ values. Line 2: n, then n training lines x y. Then m, then m validation lines x y.

Output

One line per λ, then the best.

Constraints

1 to 20 values of λ ≥ 0; 2 ≤ n ≤ 500, 1 ≤ m ≤ 500; if some λ is 0, not all training x are equal.

Example

Input:

0 1 10
4
1 1.0
2 2.6
3 2.4
4 4.9
3
0 0
5 5
6 6

Output:

lambda 0: w 1.1500, validation MSE 0.3150
lambda 1: w 0.9583, validation MSE 0.0431
lambda 10: w 0.3833, validation MSE 2.8642
best lambda 1

Why it works

Training error always favours λ = 0, the line closest to the training points; only data the model did not see can show whether shrinking the weight helps it generalize.

Examples

Example 1 · Input
0 1 10
4
1 1.0
2 2.6
3 2.4
4 4.9
3
0 0
5 5
6 6
Expected output
lambda 0: w 1.1500, validation MSE 0.3150
lambda 1: w 0.9583, validation MSE 0.0431
lambda 10: w 0.3833, validation MSE 2.8642
best lambda 1
Example 2 · Input
0 100
2
1 2
2 4
1
3 6
Expected output
lambda 0: w 2.0000, validation MSE 0.0000
lambda 100: w 0.0100, validation MSE 8.9107
best lambda 0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Fit the ridge line on the training points only, once per λ.

Hint 2

Measure each line's mean squared error on the validation points.

Hint 3

Keep the first λ with the smallest validation error.

Solution

Show one correct solution (try it yourself first)
lams = input().split()
n = int(input())
train = [tuple(map(float, input().split())) for _ in range(n)]
m = int(input())
valid = [tuple(map(float, input().split())) for _ in range(m)]
mx = sum(x for x, _ in train) / n
my = sum(y for _, y in train) / n
sxy = sum((x - mx) * (y - my) for x, y in train)
sxx = sum((x - mx) ** 2 for x, _ in train)
best = None
for lam in lams:
    w = sxy / (sxx + float(lam))
    b = my - w * mx
    error = sum((w * x + b - y) ** 2 for x, y in valid) / m
    print(f"lambda {lam}: w {w:.4f}, validation MSE {error:.4f}")
    if best is None or error < best[1]:
        best = (lam, error)
print(f"best lambda {best[0]}")

Lesson: Regularization: ridge, lasso and early stopping →