Perceptron

Properties#

• Boundary points are always updated ($w \cdot x - b = 0$ counts as wrong), in the direction that moves the prediction towards the correct side (exam WS 15/16, Task 4). Without this rule the start $w = 0, b = 0$ would never change.
• Effect of one update: after $w' = w + y x$, $b' = b - y$: $y(w' \cdot x - b') = y(w \cdot x - b) + \|x\|^2 + 1$, so the score of $x$ moves by $\|x\|^2 + 1 > 0$ towards the correct sign (it may need several updates to cross).
• Label symmetry: swapping all labels yields exactly $(-w, -b)$ after every step. Proof by induction over the steps: if $\bar w_i = -w_i$, $\bar b_i = -b_i$, then the swapped condition $(-y)(\bar w_i \cdot x - \bar b_i) \le 0$ equals the original $y(w_i \cdot x - b_i) \le 0$, and the updates give $\bar w_{i+1} = -w_i - y x = -w_{i+1}$, $\bar b_{i+1} = -b_i + y = -b_{i+1}$ (exam WS 15/16, Task 4.3).
• Result depends on the order of the training points and on the number of rounds; the final hyperplane is some separating one, not a particular “best” one.

Example#

def perceptron():
    w, b = 0, 0
    for _ in range(50):
        for x in range(1, 9):
            y = 1 if x >= 5 else -1
            if y * (w * x - b) <= 0:
                w, b = w + y * x, b - y
    return w, b

Sources#

• Not covered by a WS 25/26 lecture. Source: the former Information Retrieval exams.
• Exam WS 15/16, Task 4 (not published) (one round, implementation, label symmetry)