What is the equation to update the weights in the perceptron algorithm?

Question

I'm trying to understand the solution to question 4 of this midterm paper.

The question and solution is as follows:

I thought that the process for updating weights was:

error = target - guess
new_weight = current_weight + (error)(input)

I do not understand for example, for number 2 below, how that sum is determined. For example, I want to understand whether to update the weight or not. The calculation is:

x1(w1) + x2(w2)
(10)(1) + (10)(1) = 20
20 > 0, therefore update.

But the equation to obtain the same answer in the solution is:

1(10 + 10) 20
20 > 0, therefore update.

I understand that these two equations are essentially the same, but written differently. But for example, in step 5, what do the elements in g5 mean. What do the -8, -16 and -2 represent?

p.s. I know in a previous (now deleted) post of mine, I asked a question related to the use of LaTeX instead for maths equations. If someone can show me a simple way to convert these equations online, I'm more than happy to use it. However, I'm unfamiliar with this software, so I need some sort of converter.

Answer 1

I will tell you my knowledge, correct me if I am wrong.

Perceptron Learning Algorithm (PLA) is a simple method to solve the binary classification problem.

Define a function:

$$ f_w(x) = w^Tx + b $$

where $x \in \mathbb{R}^n$ is an input vector that contains data points and $w$ is a vector with the same dimension as $x$ which present for the parameters of our model.

Call $y=label(x)=\{1,-1\}$ where $1$ and $-1$ are the label of each $x$ vector.

The PLA will predict a class like this:

$$ y=label(x)=sgn(f_w(x))=sgn(w^Tx+b) $$

(The definition of sgn function can be found in this wiki)

We can understand that PLA tries to define a line (in 2D, or a plane in 3D, and hyperplane in more than 3 dimensions coordinate, I will assume it in 2D from now on) which separate our data into two areas. So how can we find that line? Just like every other machine learning problems, define a cost function, then optimize the parameters to have the smallest cost value.

Now, let define the cost function first, you can see that if a data point lies in the correct area, $y$ and $f(x)$ have the same sign, which means $y(w^Tx+b) > 0$ and otherwise. Similar to your example, I will define: $$ g(x)=y(w^Tx+b) $$

We ignore all the points in the safe zone ($g(x)>0$), only update to rotate or move the line to adapt with the misclassified points ($g(x)\le 0$), here, you can understand why we only update if $g(x)\le0$.

We need to define a cost function to minimize it, so our cost function will become: $$ L(w)=\displaystyle\sum_{x_i\in U}(-y_i(w^Tx_i+b)) $$ where

• $U$is the set of the misclassified points
• $y_i$ is the label of data point $i$-th
• $x_i$ is the $i$-th data vector
• $w$ and $b$ is parameters of our model

For each data point, we have the derivative is $$ \frac{\partial L}{\partial w} = -y_ix_i \\ \frac{\partial L}{\partial b} = -y_i $$

Finally, update them by Stochastic gradient descent (SGD), we get: $$ w = w - \frac{\partial L}{\partial w} = w + y_ix_i \\ b = b - \frac{\partial L}{\partial b} = b + y_i $$

For your last question, notice that the weight and bias changed from $4$-th updated, so we have: $$ y_5 = 1, x_5 = (4,8), w = (-2,-2), b = -2 \\ \Rightarrow g_5 = +1 \times (4\times(-2) + 8\times(-2)+ (-2)) = -8 -16 -2 $$