Train a logistic regression

Train the lesson's model yourself: logistic regression on one feature, with batch gradient descent on the log loss.

What to build

A program that trains a one-feature logistic regression and gives probabilities for new values.

Requirements

  • Run steps steps of batch gradient descent from w = 0, b = 0, without centring the feature.
  • Print w W b B with 4 decimal places.
  • Then for each query print X -> P, with X as in the input and P = σ(w x + b) with 3 decimal places.

Input

Line 1: n, rate and steps. Then n lines x y with y 0 or 1. Then q and q lines with one x each.

Output

The parameters, then one line per query.

Constraints

1 ≤ n ≤ 200, 1 ≤ steps ≤ 500, 1 ≤ q ≤ 20.

Example

Input:

2 1 1
1 1
-1 0
2
2
0

Output:

w 0.5000 b 0.0000
2 -> 0.731
0 -> 0.500

Why it works

For the log loss, the gradient with respect to w is the mean of (p − y) x, so each step moves the boundary towards the examples the model gets wrong, in proportion to how wrong they are.

Examples

Example 1 · Input
2 1 1
1 1
-1 0
2
2
0
Expected output
w 0.5000 b 0.0000
2 -> 0.731
0 -> 0.500
Example 2 · Input
1 0.5 2
0 1
1
0
Expected output
w 0.0000 b 0.4689
0 -> 0.615

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

Hints

Hint 1

Start at w = 0, b = 0. Each step: p = σ(w x + b) for every point, using the current w and b.

Hint 2

dw = mean of (p − y) x, db = mean of (p − y); then w ← w − rate × dw and b ← b − rate × db.

Solution

Show one correct solution (try it yourself first)
import math

n, rate, steps = input().split()
rate = float(rate)
points = [tuple(map(float, input().split())) for _ in range(int(n))]
q = int(input())
queries = [input().strip() for _ in range(q)]


def sigmoid(z):
    return 1 / (1 + math.exp(-z))


w = b = 0.0
for _ in range(int(steps)):
    dw = db = 0.0
    for x, y in points:
        p = sigmoid(w * x + b)
        dw += (p - y) * x / len(points)
        db += (p - y) / len(points)
    w, b = w - rate * dw, b - rate * db
print(f"w {w:.4f} b {b:.4f}")
for token in queries:
    print(f"{token} -> {sigmoid(w * float(token) + b):.3f}")

Lesson: Logistic regression →