λ 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 Lfor 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
0 1 10 4 1 1.0 2 2.6 3 2.4 4 4.9 3 0 0 5 5 6 6
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
0 100 2 1 2 2 4 1 3 6
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]}")