0
$\begingroup$

I'm wondering if anybody can explain how Rosenblatt reached his formula for updating the weights of his Perceptron:

$\textbf{w}_{t+1} = \textbf{w}_{t} +\eta ( y_j - \hat{y}_j ) \textbf{x}_j$

It seems to me that the step function $h ( \textbf x^T \textbf w) )$ is disregarded in what looks to be (apart from the missing step function) a Stochastic Gradient Descent update formula. I know the step function cannot be differentiated, I'm just curious about the motivation and if I'm thinking about this correctly?

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that $(y_j−\hat{y}_j)$ is 0 if the sample is at the correct side of the decision boundary. So there are only updates when the estimate is wrong.

Otherwise, let's assume $y_j=1$ and and we estimate the wrong label: $\hat{y}_j = -1$

The update becomes $\textbf{w}_{t+1} = \textbf{w}_{t} +\eta \textbf{x}_j$. That is, we move the direction of the vector $\textbf{w}$, which is perpendicular to the decision boundary, slightly towards the misclassified data point.

Note that $\textbf{w}_{t+1} \cdot \textbf{x}_j = (\textbf{w}_{t} + \eta \textbf{x}_j) \cdot \textbf{x}_j = \textbf{w}_{t} \cdot \textbf{x}_j + \eta \textbf{x}_j \cdot \textbf{x}_j = \textbf{w}_{t} \cdot \textbf{x}_j + \eta \Vert\textbf{x}_j \Vert > \textbf{w}_{t} \cdot \textbf{x}_j$ since $\eta \Vert\textbf{x}_j \Vert$ is positive (unless $\textbf{x}_j=\textbf{0}$).

Since the length of all samples is constant, every update is a finite update, although relative to the size of $\textbf{w}$ they will become smaller, and hence the angles will update with smaller steps eventually.

A symmetrical argument holds for $-1$ samples.

Since $\hat{y}_j = sign(\textbf{w} \cdot \textbf{x}_j)$, this means ultimately all estimates are correct when the data is linearly separable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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