4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Neal Young Mar 19 '13 at 18:17
  • $\begingroup$ 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. $\endgroup$ – Mike Izbicki Mar 19 '13 at 19:10
  • 1
    $\begingroup$ 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 $\endgroup$ – Yonatan N Mar 19 '13 at 23:52
  • $\begingroup$ 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. $\endgroup$ – vzn Mar 21 '13 at 5:01
1
$\begingroup$

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.

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