<p>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.</p>

CC BY-SA 3.0
2013-06-03T15:48:12.020Z
2013-06-03T15:48:12.020Z
Barak A. Pearlmutter
<p>A <a href="https://en.wikipedia.org/wiki/Perceptron" rel="nofollow">perceptron</a> is a linear classifier.    The standard method for training a perceptron involves maximizing the minimum <a href="https://en.wikipedia.org/wiki/Margin_%28machine_learning%29" rel="nofollow">margin</a>.  That is, we are trying to find:</p>

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

<p>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.</p>

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

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

<p>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.</p>

CC BY-SA 3.0
2013-03-19T18:17:28.167Z
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
CC BY-SA 3.0
2013-03-19T19:10:34.657Z
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
CC BY-SA 3.0
2013-03-19T23:52:28.363Z
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. http://cs.nyu.edu/~cil217/ML/BoostingMargin.pdf
Yonatan N
CC BY-SA 3.0
2013-03-21T05:01:06.430Z
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
<reference-request><machine-learning>
Are there perceptrons that maximize the average margin, rather than the minimum?
Mike Izbicki
# Are there perceptrons that maximize the average margin, rather than the minimum?

(Asked by: username_0 on 2013-03-19)

A [perceptron](https://en.wikipedia.org/wiki/Perceptron) is a linear classifier. The standard method for training a perceptron involves maximizing the minimum [margin](https://en.wikipedia.org/wiki/Margin_%28machine_learning%29). 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.

**Tags:** reference-request, machine-learning

> **Comments:**
> **username_1**: 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.)  
> **username_0**: 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.  
> **username_2**: 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. http://cs.nyu.edu/~cil217/ML/BoostingMargin.pdf  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2013-06-03. Score: 1

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.


---

