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.

Improve this question
$\endgroup$
4
  • $\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, 2013 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, 2013 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, 2013 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, 2013 at 5:01

1 Answer 1

Reset to default
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.

Improve this answer
$\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.