Ridge regression is least squares with a penalty λw² on the weight. For one feature it has a formula.
What to build
A program that fits a ridge regression line for a given λ.
Requirements
- Minimize Σ (w x + b − y)² + λ w².
- Print
w W b Bwith 4 decimal places.
Input
Line 1: λ. Line 2: n. Then n lines x y.
Output
One line.
Constraints
2 ≤ n ≤ 1000; λ ≥ 0; if λ is 0, not all x are equal.
Example
Input:
0
3
1 2
2 4
3 6
Output:
w 2.0000 b 0.0000
Why it works
Setting the derivatives to zero gives b = ȳ − w x̄ as before, and the penalty adds λ to the denominator of w, shrinking it towards 0.
Examples
Example 1 · Input
0 3 1 2 2 4 3 6
Expected output
w 2.0000 b 0.0000
Example 2 · Input
2 3 1 2 2 4 3 6
Expected output
w 1.0000 b 2.0000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Compute x̄, ȳ, Sxy = Σ (x − x̄)(y − ȳ) and Sxx = Σ (x − x̄)².
Hint 2
w = Sxy / (Sxx + λ) and b = ȳ − w x̄; the bias is not penalized.
Solution
Show one correct solution (try it yourself first)
lam = float(input())
n = int(input())
points = [tuple(map(float, input().split())) for _ in range(n)]
mx = sum(x for x, _ in points) / n
my = sum(y for _, y in points) / n
sxy = sum((x - mx) * (y - my) for x, y in points)
sxx = sum((x - mx) ** 2 for x, _ in points)
w = sxy / (sxx + lam)
b = my - w * mx
print(f"w {w:.4f} b {b:.4f}")