3
$\begingroup$

A post gives a formula for perceptron to update weights

enter image description here

I understand almost all the parts of it, except for the part $(y_i - \hat y_i)x_i$ where does it come from? Is it the gradient of some kind of loss function? If yes, what is the definition of the loss function?

The OP seems doesn't give the hypothesis, so that $\hat y_i = h(x_i)$

However, this hypothesis seems prevalent

\begin{align} \hat{y} &= sign(\mathbf{w} \cdot \mathbf{x} + b) \tag{1}\\ &= sign({w}_{1}{x}_{1}+{w}_{2}{x}_{2} + ... + w_nx_n + b) \\ \end{align}

where

$$ sign(z) = \begin{cases} 1, & z \ge 0 \\ -1, & z < 0 \end{cases} $$

How do I get $(y_i - \hat y_i)x_i$ from function (1)

$\endgroup$
1
  • $\begingroup$ I'm only adding this comment because you asked, "Is it the gradient of some kind of loss function?" The direct answer is "No... It is, in itself, a simple loss function." I just want to make sure that you recognize that the author seems to be presenting a simplified approach and not what we tend to use in a deep learning neural network. More typically we will be performing backpropagation with partial differentials to determine how the weights and biases are adjusted. Andrew Ng has a very, very good video explaining this that simplifies the math significantly if you search around. $\endgroup$ Jul 24, 2021 at 23:28

2 Answers 2

0
$\begingroup$

It depends on your hypothesis $h$. The author of the original article compares the dot product with a threshold:

enter image description here

So for a binary classification problem $h$ can be defined as follows:

$$ h = \begin{cases} 1 & \text{if $f>z$}\\ 0 & \text{otherwise} \end{cases} $$

That is, $\hat y_i$ is your prediction and $\hat y_i = h(x_i)$, $y_i$ is a real label and $x_i$ is a sample.

Finally, you can update your weghts $w_n = w_n + \eta(y_i - \hat y_i)x_i$, where $n$ is a number of the weight and $i$ denotes a number of the label/sample pair.

Depending on how you define your hypothesis you will have a different optimization algorithm. Take a look at this answer for more details.

$\endgroup$
2
  • $\begingroup$ Thank you. How do I get $(y_i - \hat y_i)x_i$ from this hypothesis \begin{align} \hat{y} &= sign(\mathbf{w} \cdot \mathbf{x} + b) \\ &= sign({w}_{1}{x}_{1}+{w}_{2}{x}_{2} + ... + w_nx_n + b) \\ \end{align} $\endgroup$
    – JJJohn
    Jun 23, 2021 at 22:38
  • $\begingroup$ sign extracts a sign of a number. According to the article, it is defined exactly as I described: $sign(\mathbf{w} \cdot \mathbf{x} + b) = \begin{cases} 1 & \text{if $\mathbf{w} \cdot \mathbf{x} + b>0$}\\ 0 & \text{otherwise} \end{cases}$ $\endgroup$ Jun 24, 2021 at 1:40
0
$\begingroup$

Your reference's training algo is called error correction rule or simply perceptron 0-1 rule which doesn't have the usual mean squared error (MSE) or cross entropy (CE) loss function associated with LMS/delta training rules leveraging various forms of gradient descent (GD) methods because its activation function is the non-differentiable Heaviside sign function breaking any GD applicability via chain rule to update each weight. Yet instead it could be approximately viewed as having MSE loss function optimized with stochastic gradient descent (SGD) method iterating over every training sample to update each weight incrementally following your referenced perceptron rule.

This can be intuited from simply replacing your sign activation function with a very similarly shaped differentiable function such as sigmoid, then your concerned 0-1 training rule can be derived just as the usual delta rule reflected in the Widrow-Hoff SGD version algo or the popular MLP backpropagation's SGD version algo to update any weight parameter, and better yet in your case, the derivative of activation function is approximately 1 since the activation function is assumed to be very like the sign function as intuited above.

Of course this is just some intuition, even for linearly separable dataset we cannot assure your concerned rule would converge at all. Fortunately there was Perceptron convergence theorem proved by Rosenblatt et al to affirm such convergence in the cases data is linearly separable. Even in non-separable cases there is no way for a single perceptron to converge, however, we still have Perceptron cycling theorem to give some upper bound estimate for the weight vector norm.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .