0
$\begingroup$

I was reading the convergence proof for the perceptron algorithm. It says under the assumption that there are some $R$, $\theta^*$ with $|\theta^*| = 1$ and $\gamma > 0$, such that $y_t(x_t\cdot \theta^*) \geq \gamma$ and $|x_t|\leq R$ for $t = 1, 2, \dots n$, the perceptron algorithm makes at most $\frac{R^2}{\gamma^2}$ errors.

What I didn't fully understand how $\theta^*$ was related to $x_t$ and how it affected the convergence of PLA. If I scale down all $x_t$ by a factor $k$, then I have $|x_t| \leq \frac{1}{k}R$, but what happens to $\theta^*$ and $\gamma$? Does scaling down $x_t$ gives a smaller upper bound and thus PLA converges faster? I personally believe how fast PLA converges is decided by how data is distributed rather than $|x_i|$, is it correct? Any hint or answer is appreciated, thanks in advance.

$\endgroup$
0
$\begingroup$

If we scale $x_t$ by a factor $m$ (not using $k$ to prevent any confusion with the number of steps), the inequality becomes $$y_t((x_t/m) \cdot \theta^*)\geq \gamma/m\rightarrow y_t(x_t'\cdot\theta^*)\geq\gamma'$$ $\gamma$ acts like a margin of the boundary, i.e. how far the samples are off. If we scale the samples, the margin is also scaled. The boundary weights are always normalized, i.e. $||\theta^*||=1$, and isn't affected by scale changes in input, e.g. $x+2y=5$ and $2x+4y=10$ are the same line. Therefore, both $R$ and $\gamma$ are scaled the same way and we have $$k\leq \frac{(R/m)^2}{(\gamma/m)^2}=\frac{R^2}{\gamma^2}$$ So, it doesn't converge faster.

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