1
$\begingroup$

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

The question and solution is as follows:

enter image description here

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.

$\endgroup$
1
$\begingroup$

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 $$

$\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.