3
$\begingroup$

Every perceptron convergence proof i've looked at implicitly uses a learning rate = 1.

However, the book I'm using ("Machine learning with Python") suggests to use a small learning rate for convergence reason, without giving a proof.

Can someone explain how the learning rate influences the perceptron convergence and what value of learning rate should be used in practice?

$\endgroup$
1
$\begingroup$

(My answer is with regard to the well known variant of the single-layered perceptron, very similar to the first version described in wikipedia, except that for convenience, here the classes are $1$ and $-1$.)

Let's denote:

  • $d$ is the dimension of a feature vector, including the dummy component for the bias (which is the constant $1$).
  • $x^r\in\mathbb R^d$ and $y^r\in\{-1,1\}$ are the feature vector (including the dummy component) and class of the $r$ example in the training set, respectively.
  • $\eta _1,\eta _2>0$ are training steps, and let there be two perceptrons, each trained with one of these training steps, while the iteration over the examples in the training of both is in the same order.
  • $w_0\in\mathbb R^d$ is the initial weights vector (including a bias) in each training.
  • for $i\in\{1,2\}$: let $w_k^i\in\mathbb R^d$ be the weights vector after $k$ mistakes by the perceptron trained with training step $\eta _i$.
  • for $i\in\{1,2\}$: with regard to the $k$-th mistake by the perceptron trained with training step $\eta _i$, let $j_k^i$ be the number of the example that was misclassified.

If $w_0=\bar 0$, then we can prove by induction that for every mistake number $k$, it holds that $j_k^1=j_k^2$ and also $w_k^1=\frac{\eta_1}{\eta_2}w_k^2$:

  • base ($k=1$):
    $w_0^1=w_0=w_0^2$, so both perceptrons would predict the same class for each example until and including the first mistake, so $j_1^1=j_1^2$.
    Now: $$w_1^2=w_0+\eta_2y^{j_1^2}x^{j_1^2}=\eta_2y^{j_1^2}x^{j_1^2}=\eta_2y^{j_1^1}x^{j_1^1}$$ and thus:$$w_1^1=w_0+\eta_1y^{j_1^1}x^{j_1^1}=\eta_1y^{j_1^1}x^{j_1^1}=\frac{\eta_1}{\eta_2}\eta_2y^{j_1^1}x^{j_1^1}=\frac{\eta_1}{\eta_2}w_1^2$$
  • step (let $k$ be a mistake number such that the claim holds for $k$, and for every natural smaller than $k$):
    After the $k$-th mistake, perceptron $1$ would predict that an example $r$ is positive iff $(w_k^1)^Tx^r>0$. According to the induction hypothesis, this is true iff $(\frac{\eta_1}{\eta_2}w_k^2)^Tx^r>0$, but we can divide both sides by $\frac{\eta_1}{\eta_2}$, as it is a strictly positive scalar, and thus we get: $$(w_k^1)^Tx^r>0\leftrightarrow (w_k^2)^Tx^r>0$$ i.e. after the $k$-th mistake, both perceptrons would predict the same class for each example. According to the induction hypothesis, $j_k^1=j_k^2$, and so both perceptrons would iterate over the same examples in the same order after the $k$-th mistake. Therefore, $j_{k+1}^1=j_{k+1}^2$.
    Now: $$w_{k+1}^2=w_k^2+\eta_2y^{j_{k+1}^2}x^{j_{k+1}^2}=w_k^2+\eta_2y^{j_{k+1}^1}x^{j_{k+1}^1}$$ and thus (according to the induction hypothesis):$$w_{k+1}^1=w_k^1+\eta_1y^{j_{k+1}^1}x^{j_{k+1}^1}=\frac{\eta_1}{\eta_2}w_k^2+\eta_1y^{j_{k+1}^1}x^{j_{k+1}^1}=\frac{\eta_1}{\eta_2}(w_k^2+\eta_2y^{j_{k+1}^1}x^{j_{k+1}^1})=\frac{\eta_1}{\eta_2}w_{k+1}^2$$

We showed that the perceptrons do exactly the same mistakes, so it must be that the amount of mistakes until convergence is the same in both. (You could also deduce from this proof that the hyperplanes defined by $w_k^1$ and $w_k^2$ are equal, for any mistake number $k$.)
Thus, the learning rate doesn't matter in case $w_0=\bar 0$.


In case $w_0\not=\bar 0$, you could prove (in a very similar manner to the proof above) that in case $\frac{w_0^1}{\eta_1}=\frac{w_0^2}{\eta_2}$, both perceptrons would do exactly the same mistakes (assuming that $\eta _1,\eta _2>0$, and the iteration over the examples in the training of both is in the same order).
Thus, for any $w_0^1\in\mathbb R^d$ and $\eta_1>0$, you could instead use $w_0^2=\frac{w_0^1}{\eta_1}$ and $\eta_2=1$, and the learning would be the same.
In other words, even in case $w_0\not=\bar 0$, the learning rate doesn't matter, except for the fact that it determines where in $\mathbb R^d$ the perceptron starts looking for an appropriate $w$.


Finally, I wrote a perceptron for $d=3$ with an animation that shows the hyperplane defined by the current $w$. I think that visualizing the way it learns from different examples and with different parameters might be illuminating.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import itertools
import time

EXAMPLES1 = np.array([[9, 0], [8, 0]], dtype='float')
EXAMPLES2 = np.array([[5, 0], [6, 0]], dtype='float') # closer to the origin
EXAMPLES_CLASSES1_2 = np.array([1, -1])

EXAMPLES3 = np.array([[20, 26], [16, -11], [21, 2], [18, 25],
                    [26, -19], [11, 6], [20, -10], [17, 17]], dtype='float')
EXAMPLES4 = EXAMPLES3 - 11 * np.ones(EXAMPLES3.shape) # closer to the origin
EXAMPLES5 = np.array([[20, 26], [16, 27], [21, 24], [15, 25],
                    [22, 23], [14, 27], [20, 20], [13, 24]], dtype='float')
EXAMPLES_CLASSES3_4_5 = np.array([1, -1, 1, -1, 1, -1, 1, -1])


W0_0 = np.zeros(3)
W0_1 = np.array([1., 0, -2])
LEARNING_RATE_1 = 0.00156
W0_2 = np.array([1., 0, -2]) / 0.00156
LEARNING_RATE_2 = 1

EXAMPLES = EXAMPLES1
EXAMPLES_CLASSES = EXAMPLES_CLASSES1_2
LEARNING_RATE = LEARNING_RATE_2
W0 = W0_2
INTERVAL = 3e2
INTERVAL = 1
INTERVAL = 3e1



N = len(EXAMPLES)
assert(EXAMPLES.shape[1] == 2)
assert(N == len(EXAMPLES_CLASSES))
assert(LEARNING_RATE > 0)
assert(len(W0) == 3)


fig, ax = plt.subplots()
XS = EXAMPLES[:, 0]
YS = EXAMPLES[:, 1]
max_abs_x = max(max(XS), abs(min(XS)), 1)
max_abs_y = max(max(YS), abs(min(YS)), 1)
bottom_limit = -2 * max_abs_y
top_limit = 2 * max_abs_y
left_limit = -2 * max_abs_x
right_limit = 2 * max_abs_x
plt.xlim(left_limit, right_limit)
plt.ylim(bottom_limit, top_limit)
x_range_size = right_limit - left_limit
y_range_size = top_limit - bottom_limit

# plot the examples
for x, y in zip(EXAMPLES, EXAMPLES_CLASSES):
    if y == 1:
        plt.plot(x[0], x[1], marker='o', markersize=4, color="green")
    else:
        plt.plot(x[0], x[1], marker='o', markersize=4, color="red")

# add a dummy column of ones for the bias.
EXAMPLES = np.hstack((EXAMPLES, np.ones((N, 1))))

hyperplane, = plt.plot([], [], color='blue')
hyperplane.set_visible(False)
k_text = plt.text(ax.get_xlim()[0] + x_range_size / 70,
                  ax.get_ylim()[1] - y_range_size / 25, 'mistakes: 0')
next_example_idx = 0
k = 0
w = W0

def get_hyperplane(w):
    w_x, w_y, bias = w
    if w_x == w_y == 0:
        print(f'No hyperplane is defined by w')
        return None
    if w_y == 0:
        x1 = x2 = -bias / w_x
        y1 = bottom_limit
        y2 = top_limit
        if not left_limit <= x1 <= right_limit:
            print(f'The hyperplane is out of range of our graph')
            return None
        else:
            print(f'The hyperplane defined by w is `x = {x1}`')
    else:
        # find the hyperplane representation as y = m * x + b.
        m = -w_x / w_y # m = -1 / (w_y / w_x)
        b = -bias / w_y
        # b = -bias / np.linalg.norm(np.array([w_x, w_y]))
        print(f'The hyperplane defined by w is `y = {m} * x + {b}`')

        if m == 0:
            y1 = y2 = m * left_limit + b
            x1 = left_limit
            x2 = bottom_limit
        else:
            potential_points_on_limits = {
                (left_limit, m * left_limit + b),
                (right_limit, m * right_limit + b),
                ((bottom_limit - b) / m, bottom_limit),
                ((top_limit - b) / m, top_limit)}
            for x, y in set(potential_points_on_limits):
                if not left_limit <= x <= right_limit:
                    potential_points_on_limits.remove((x, y))
                elif not bottom_limit <= y <= top_limit:
                    potential_points_on_limits.remove((x, y))
            if len(potential_points_on_limits) < 2:
                print(f'The hyperplane is out of range of our graph')
                return None
            x1, y1 = potential_points_on_limits.pop()
            x2, y2 = potential_points_on_limits.pop()

    return (x1, x2), (y1, y2)

def update(frame):
    global k, w, next_example_idx

    for j in itertools.chain(range(next_example_idx, N),
                             range(next_example_idx)):
        x = EXAMPLES[j]
        y = EXAMPLES_CLASSES[j]
        perdicted_y = 1 if np.dot(w, x) > 0 else -1
        if perdicted_y != y:
            print(f'\nMisclassification of example {x}')
            w += LEARNING_RATE * y * x
            k += 1
            k_text.set_text(f'mistakes: {k}')
            print(f'This is mistake number {k}')
            print(f'Update w to {w}')

            hyperplane_xs_and_ys = get_hyperplane(w)
            if hyperplane_xs_and_ys:
                hyperplane.set_data(hyperplane_xs_and_ys)
                hyperplane.set_visible(True)
            else:
                hyperplane.set_visible(False)

            next_example_idx = j + 1
            return hyperplane, k_text

    # The perceptron successfully predicted all of the examples.
    time.sleep(3)
    exit()

ani = FuncAnimation(fig, update, blit=True, repeat=False, interval=INTERVAL)
plt.show()
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.