Perceptron learning rule for classification

Question

That's the problem

$$y=(x,w,\rho) = \begin{cases} 1 & \sum_{i=1}^3 w_ix_i >\rho\\ 0 & \text{otherwise} \end{cases},$$

where $x=\{x_1,x_2,x_3\}$ are inputs, $w=\{w_1,w_2,w_3\}$ are weights and $\rho$ is the threshold value.

The problem asks to find an opportune set of weights that can classify these inputs.

$$A = \{(1, 2, 0), (−1, 3, 0), (−2, −3, 0)\},$$ $$B = \{(0,1,2),(9,0,1),(−3,−3,3)\}.$$

The first step is to assign a random weights to all inputs

$w_1= 0.5$, $w_2= 0.7$, $w_3=0.3$.

For the first example $(1,2,0)$ that I know is part of the A class

$\sum_{i=1}^3 w_ix_i=1.9 < \rho~ \Rightarrow y=0$ is the result.

I need to update the weights but I can't understand how.

The formula is

$w_i'=w_i*n*x(t-y)$.

Correct?

Answer 1

The biggest problem is your equation is wrong for how to update the weights. Your response that $t$ is the target value is correct. Furthermore, the $n$ should almost certainly be the greek letter eta, $\eta$. Anyway, sticking as close to your notation and example as possible, say we have some input/output pair $(x, t) \in \mathbb{R}^3 \times \{0,1\}$ and $y$ is the output of the perceptron on input $x$. Then the weight update should be

$$ w_i^\prime = w_i + \eta x_i (t - y), \; i = 1,2,3. $$

Answer 2

The first thing to do is to treat the bias ($\rho$) as a weight on an extra input whose activity is always 1 so that you won't need a separate learning rule for the bias and then the decision for your binary threshold outputs a 1 iff $\sum\limits_{i=1}^{3} w_i x_i \geq 0$

To learn the weights of perceptrons, you are right to start with random weights. The remainder of the procedure is to do the following: if for an input your weights correctly classify an output, you leave the weights alone. If, however, you incorrectly output a zero, add the input vector to the weight vector. And on the other hand, if you incorrectly output a 1, subtract the input vector from the weight vector. I would be able to show you an example run with your inputs and random weights above but you're missing the outputs which map to the inputs in order to correct the weights.

Also, note that the above procedure gives you a correct set of weights iff one exists. Otherwise, the learning procedure will fail and you will eventually find it impossible to classify one of the inputs.

EDIT: Here's another example to try and explain things. Let's use initial weights where $w = (w_1, w_2, w_3) = (1, 0, -2)$, letting $\rho = 0$, with:

Target: $t_1 = 1$, $t_2 = 1$, $t_3 = 0$, $t_4 = 1$, $t_5 = 0$

Input: $x_1 = (1,0,1)$, $x_2 = (0,1,1)$, $x_3 = (1, 0, 0)$, $x_4 = (1,0,1)$, $x_5 = (1, 0, 0)$

$y_1 = wx_1 = 1\times 1 + 0\times 0 + -2\times1 =-1 \leq \rho$ --> outputs a 0, which does not equal $t_1$. In this case, we add the input to the weight vector so $w\prime = w + x_1 = (1+1,0+0,-2+1) = (2,0,-1)$, $w = w\prime$

$y_2 = wx_2 = 0\times 2 + 1 \times 0 + 1\times -1 = -1 \leq \rho $ --> outputs a 0, which does not equal $t_2$. In this case, we add the input to the weight vector so $w\prime = w + x_2 = (2,1,0)$, $w = w\prime$

$y_3 = wx_3 = 1\times 2 + 0\times 1 + 0\times 0 = 2 > \rho$ --> outputs a 1, which does not equal $t_3$. In this case, we subtract the input from the weight vector so $w\prime = w - x_3 = (2-1,1-0,0-0) = (1,1,0)$, $w = w\prime$

$y_4 = wx_4 = 1\times 1 + 0\times 1 + 1\times 0 = 1 > \rho$ --> outputs a 1, which equals $t_4$ so the weight vector remains unchanged.

$y_5 = wx_5 = 1\times 1 + 0\times 1 + 0\times 0 = 1 > \rho$ --> outputs a 1, which does not equal $t_5$. In this case, we subtract the input from the weight vector so $w\prime = w - x_5 = (1-1,1-0,0-0) = (0,1,0)$, $w = w\prime$

Final weight vector $w= (0,1,0)$