"""
第 01 章配套代码：感知机（Perceptron）从零实现
Runnable with: numpy only.  python3 01_perceptron.py

复现 Rosenblatt 1958 在线学习规则 + Novikoff 1962 收敛性的经验验证。
演示：感知机能学线性可分（AND/OR），不能学 XOR（Minsky-Papert 1969）。
"""
import numpy as np

rng = np.random.default_rng(0)


def perceptron_train(X, y, lr=1.0, max_epochs=100):
    """Rosenblatt 在线感知机。y in {0,1}。
    更新规则:  w <- w + lr * (y_i - y_hat_i) * x_i ;  b <- b + lr*(y_i - y_hat_i)
    返回 (w, b, epochs_to_converge, mistake_count)。
    """
    n, d = X.shape
    w = np.zeros(d)
    b = 0.0
    mistakes = 0
    for epoch in range(max_epochs):
        errors = 0
        for i in range(n):
            y_hat = 1 if (X[i] @ w + b) >= 0 else 0
            update = lr * (y[i] - y_hat)
            if update != 0:
                w += update * X[i]
                b += update
                errors += 1
                mistakes += 1
        if errors == 0:
            return w, b, epoch + 1, mistakes
    return w, b, max_epochs, mistakes


def novikoff_bound(X, y):
    """Novikoff 1962 错误上界 (R/gamma)^2 的经验估计。
    用 {-1,+1} 标签找一个分隔超平面的 margin 下界（这里用已收敛的 w 近似）。
    """
    Xpm = X
    R = np.max(np.linalg.norm(Xpm, axis=1))
    return R


if __name__ == "__main__":
    # 线性可分: 逻辑 AND
    X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], dtype=float)
    y_and = np.array([0, 0, 0, 1])
    w, b, ep, mis = perceptron_train(X, y_and)
    print(f"[AND ] 收敛于 {ep} epoch, 共 {mis} 次错误更新, w={w}, b={b:.1f}")

    # 线性可分: 逻辑 OR
    y_or = np.array([0, 1, 1, 1])
    w, b, ep, mis = perceptron_train(X, y_or)
    print(f"[OR  ] 收敛于 {ep} epoch, 共 {mis} 次错误更新, w={w}, b={b:.1f}")

    # 线性不可分: XOR —— 不会收敛（Minsky-Papert 1969）
    y_xor = np.array([0, 1, 1, 0])
    w, b, ep, mis = perceptron_train(X, y_xor, max_epochs=100)
    print(f"[XOR ] 100 epoch 仍未收敛 (ep={ep}), 错误更新累计 {mis} 次 —— 线性不可分，感知机无解")

    # Novikoff 边界示意（R = 最大数据范数）
    R = novikoff_bound(X, y_and)
    print(f"[Novikoff] 数据最大范数 R={R:.3f}; 错误界 (R/gamma)^2 随 margin gamma 减小而增大")