Linear regression with two features

With two features the best plane ŷ = w₁x₁ + w₂x₂ + b still has a formula: the normal equations, here small enough to solve by hand.

What to build

A program that fits a least-squares plane to points with two features and predicts new ones.

Requirements

  • Use the least-squares solution (the one with the smallest mean squared error).
  • Print w1 A w2 B b C with 4 decimal places each.
  • Then one prediction per query with 2 decimal places.

Input

Line 1: n. Then n lines x1 x2 y. Then q and q lines x1 x2.

Output

The parameters, then the predictions.

Constraints

3 ≤ n ≤ 200; the features are not all on one line, so the system has one solution; 1 ≤ q ≤ 20.

Example

Input:

4
0 0 1
1 0 3
0 1 4
1 1 6
1
2 2

Output:

w1 2.0000 w2 3.0000 b 1.0000
11.00

Why it works

Setting the derivative of the squared error with respect to each weight to zero gives one linear equation per weight; after centring, the bias drops out and two equations in w₁ and w₂ remain.

Examples

Example 1 · Input
4
0 0 1
1 0 3
0 1 4
1 1 6
1
2 2
Expected output
w1 2.0000 w2 3.0000 b 1.0000
11.00
Example 2 · Input
4
1 1 4
2 1 5
1 2 7
2 2 9
2
0 0
3 1
Expected output
w1 1.5000 w2 3.5000 b -1.2500
-1.25
6.75

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

Hints

Hint 1

Centre everything: subtract the means of x₁, x₂ and y.

Hint 2

With S₁₁ = Σ c₁², S₂₂ = Σ c₂², S₁₂ = Σ c₁c₂, S₁y = Σ c₁c_y and S₂y = Σ c₂c_y, the weights solve a 2 × 2 system.

Hint 3

d = S₁₁S₂₂ − S₁₂², w₁ = (S₁y S₂₂ − S₂y S₁₂) / d, w₂ = (S₂y S₁₁ − S₁y S₁₂) / d, b = ȳ − w₁x̄₁ − w₂x̄₂.

Solution

Show one correct solution (try it yourself first)
n = int(input())
rows = [list(map(float, input().split())) for _ in range(n)]
q = int(input())
queries = [list(map(float, input().split())) for _ in range(q)]
m1 = sum(r[0] for r in rows) / n
m2 = sum(r[1] for r in rows) / n
my = sum(r[2] for r in rows) / n
s11 = sum((r[0] - m1) ** 2 for r in rows)
s22 = sum((r[1] - m2) ** 2 for r in rows)
s12 = sum((r[0] - m1) * (r[1] - m2) for r in rows)
s1y = sum((r[0] - m1) * (r[2] - my) for r in rows)
s2y = sum((r[1] - m2) * (r[2] - my) for r in rows)
d = s11 * s22 - s12 * s12
w1 = (s1y * s22 - s2y * s12) / d
w2 = (s2y * s11 - s1y * s12) / d
b = my - w1 * m1 - w2 * m2
print(f"w1 {w1:.4f} w2 {w2:.4f} b {b:.4f}")
for x1, x2 in queries:
    print(f"{w1 * x1 + w2 * x2 + b:.2f}")

Lesson: Linear regression →