Algorithm

model: f(x) = sign(w*x + b)
input: training_set = {(x1, y1), (x2, y2), ..., (xn, yn)}
xi∈Rn, yi ∈{-1, +1}, i=1,2,...,n;
learning rate: 0 < η ≤ 1;
output: w, b

1. initialize w and b;
2. select one (x, y) in the training set
3. if y * (w*x +b) ≤ 0
   w ← w + η * yi * xi
   b ← b + η * yi
4. Go to step 2 until there is no more mistakes in the training set

Code

Note:

• use python 3.x
• pip install matplotlib

import copy
from matplotlib import pyplot as plt
from matplotlib import animation


def update(x, y, w, b, rate):
    for i in range(len(w)):
        w[i] += rate * y * x[i]
    b += rate * y
    return w, b


def compute(x, y, w, b):
    wx = 0
    for i in range(len(w)):
        wx += w[i] * x[i]
    return y * (wx + b)


def learning(training_set, w, b, rate):
    flag = True
    for item in training_set:
        x = item[0]
        y = item[1]
        if compute(x, y, w, b) <= 0:
            flag = False
            w, b = update(x, y, w, b, rate)
    return flag, w, b


def train(training_set, w, b):
    training_process = []
    learning_rate = 1
    iterations = 1000
    for index in range(iterations):
        completed, w, b = learning(training_set, w, b, learning_rate)
        training_process.append([copy.copy(w), b])
        if completed > 0:
            print("RESULT: w:", w, "b:", b)
            return training_process


def display(training_set, training_process):
    def init():
        line.set_data([], [])
        x, y, x_, y_ = [], [], [], []
        for p in training_set:
            if p[1] > 0:
                x.append(p[0][0])
                y.append(p[0][1])
            else:
                x_.append(p[0][0])
                y_.append(p[0][1])

        plt.plot(x, y, 'bo', x_, y_, 'rx')
        plt.axis([-6, 6, -6, 6])
        plt.grid(True)
        plt.xlabel('x(1)')
        plt.ylabel('x(2)')
        plt.title('Perceptron')
        return line, label

    def frame_update(frame_index):
        w = training_process[frame_index][0]
        b = training_process[frame_index][1]
        if w[1] == 0:
            return line, label
        x1 = -7
        y1 = -(b + w[0] * x1) / w[1]
        x2 = 7
        y2 = -(b + w[0] * x2) / w[1]
        line.set_data([x1, x2], [y1, y2])
        x1 = 0
        y1 = -(b + w[0] * x1) / w[1]
        label.set_text(training_process[frame_index])
        label.set_position([x1, y1])
        return line, label

    fig = plt.figure()
    ax = plt.axes(xlim=(0, 2), ylim=(-2, 2))
    line, = ax.plot([], [], 'g', lw=2)
    label = ax.text([], [], '')

    anim = animation.FuncAnimation(fig, frame_update, init_func=init,
                                   frames=len(training_process), interval=1000,
                                   repeat=False,
                                   blit=True)
    plt.show()


def main():
    training_set = [[(3, 3), 1], [(4, 3), 1], [(1, 1), -1]]
    w = [0, 0]
    b = 0
    training_process = train(training_set, w, b)
    print(training_process)
    display(training_set, training_process)


if __name__ == "__main__":
    main()