How to resolve the perceptron dilemma for binary classification?

Question

I have a following thought problem involving perceptron and binary classification that I wonder if anyone has thought about before. This is not from any textbook or reference, although I doubt I'm the first one to observe the following.

---

Suppose you wish to do binary linear classification on a separable dataset.

From the famous perceptron convergence theorem (I am referring to the last equation in this document: http://www.cs.columbia.edu/~mcollins/courses/6998-2012/notes/perc.converge.pdf)

The number of iterations $(k)$ is upper bounded by ,

$$k \leq R^2/\gamma^2$$

Where $R$ is the largest magnitude of your data and $\gamma$ is the margin to the optimal/separating hyperplane.

Now if I wished to increase the rate of convergence of perceptron for finding this optimal hyperplane. This means, I would either increase $\gamma$ or lower $R$.

Since $\gamma$ is an unknown, prior to calculating the optimal hyperplane. Then I can only lower $R$.

I use standardscaler or whatever else technology to normalize my data around the mean and divide by the standard deviation. Great, now $R$ is smaller.

But a problem now arises: the normalized dataset appears to be more "squished" together. This means that my $\gamma$ has also gotten smaller. Hence the bound is now bigger.

Thenceforth, the perceptron dilemma: should you normalize your data or not?

Answer 1

Your idea of trying to reduce $R$ to reduce the bound is interesting, but I do not see a dilemma.

First, lets define each concept precisely. Given a data set $(x_i, y_i)_{i=1}^n$, $x_i \, \in \, \mathbb{R}^k$, $y_i\,\in\,\{-1,1\}$, define $R = \underset{i\,\in\,[n]}{max} ||x_i||$. The theorem states that the perceptron converges for any constant $\gamma > 0$ such that

$$ y_i(x_i\cdot\theta^*) \geq \gamma \quad\forall i\,\in\,[n]\quad,$$

where $\theta^*$ is the optimal hyperplane normalized vector. To have optimal bound, you take $\gamma$ as the largest constant satisfying the inequalities above. Hence, you take $\gamma = \underset{i\,\in\,[n]}{min}||x_i \cdot \theta^*||$, which is called the margin.

Okay, with everything defined, lets tackle the question.

(Normalization) First, normalization does not necessarily reduces $R$. Take $x = (x_1, x_2) = (-1/2,1/2)$. That is, $x$ is a sample of size $2$ of a one dimensional vector. The normalized $X$ is either $(-1, 1)$ or $(-\sqrt{2}, \sqrt{2})$, depending on how you compute the standard deviation. Nevertheless, $R$ is smaller for the original $X$ than in the transformed set.

(A second attempt) Not wanting to give up, you come up with a simple idea! Just divide the data $x_i$ (all entries of all vectors) by some constant a, arriving at $x_i' = \frac{1}{a}x_i$! This way, the new bound will be $R'= R/a$. Hence, you can make the bound as low as you wish. What happens to $\gamma$, though? Well, the normalized hyperplan vector still is $\theta^*$. hence

$$\gamma' = \underset{i\,\in\,[n]}{min}||x_i'\cdot\theta^*|| = \frac{\gamma}{a} \quad.$$

The upperbound is then

$$ \frac{R'^2}{\gamma'^2} = \frac{R^2}{\gamma^2} \quad,$$

so this idea did not work too.

(A final thrust) You decide to bring all your mathematical collection of functions to the table. You think on linear and non linear operators that reduce $R$ greatly but reduces $\gamma$ only slightly. Will you succeed? Maybe. But there is a second tough problem: the original data set $X$ is linearly separable. You have to find a transformation that, for any linearly separable data set, the transformed data set always will be linearly separable. If you do not, then the algorithm will not even converge. It is not an easy task to find a transformation satisfying both.