A ridge regression line

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 B with 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}")

Lesson: Regularization: ridge, lasso and early stopping →