# Are there perceptrons that maximize the average margin, rather than the minimum?

A perceptron is a linear classifier. The standard method for training a perceptron involves maximizing the minimum margin. That is, we are trying to find:

$x^* = \text{argmax}_{x\in \text{unit vectors}} \min_{i \in 1..n} A_i x$

where $x$ is a normal vector to the separating hyperplane, $A$ is the $n\times d$ matrix of input values, $n$ is the number of input data points, $d$ is their diminsion, and $A_i x$ is the dot product between $x$ and the $i$th data point.

My question is: has there been any work on perceptrons whose hyperplane maximizes the average margin? That is,

$x'^* = \text{argmax}_{x\in \text{unit vectors}} \sum_{i \in 1..n} A_i x$

This is a much easier quantity to calculate because it does not require gradient descent. The problem is that it is not guaranteed to find separating hyperplanes even when they do exist---the points with low margin aren't given enough weight to do this.

• Mike, wouldn't this $x'^*$ just be the unit vector in the direction of the vector sum $\sum_i A_i$? (Maybe you want instead to maximize something like $\sum_i\max(0,A_i x)$? Disclaimer: I don't know much about linear classifiers.) – Neal Young Mar 19 '13 at 18:17
• Yeah, the unit vector in that direction was what I was going for. I imagine it's not a particularly effective classifier in most cases, it's just really fast to calculate in practice. – Mike Izbicki Mar 19 '13 at 19:10
• This is a bit of an aside, but AdaBoost can be viewed as an algorithm that repeatedly projects the training vectors onto a one-dimensional subspace and attempts to minimize a certain convex combination of the margins. Perhaps you can extract some insights from this connection for your work. See the discussion in section 6 of the "Boosting The Margin" paper by Schapire, Freund, Bartlett, and Lee for more detail. cs.nyu.edu/~cil217/ML/BoostingMargin.pdf – Yonatan N Mar 19 '13 at 23:52
• many problems on perceptrons can be translated into linear algebra eqns/problems. suggest reformulating the problem in that form. it is already close but maybe it can be reduced further to a basic linear algebra problem. – vzn Mar 21 '13 at 5:01

This is what a soft-margin SVM is already doing, except that the average has a min on the inside: $\sum_i min(h,d(x_i,c_i,w))$ where $d(x_i,c_i,w)$ is the distance of the point $x_i$ from the classification hyperplane, signed with a positive sign if it is on the correct side as determined by the target $c_i$, and $h$ is the maximum distance on the correct side you're willing to give "credit" for. If you set $h$ to a large enough value, this is what you have above. And, this is precisely a soft-margin linear SVM.