# Maximum Relative Margin and Data-Dependent Regularization

Pannagadatta K. Shivaswamy, Tony Jebara.

Year: 2010, Volume: 11, Issue: 25, Pages: 747−788

#### Abstract

Leading classification methods such as support vector machines
(SVMs) and their counterparts achieve strong generalization
performance by maximizing the margin of separation between data
classes. While the maximum margin approach has achieved promising
performance, this article identifies its sensitivity to affine
transformations of the data and to directions with large data
spread. Maximum margin solutions may be misled by the spread of data
and preferentially separate classes along large spread directions.
This article corrects these weaknesses by measuring margin not in
the absolute sense but rather only relative to the spread of data in
any projection direction. Maximum relative margin corresponds to a
data-dependent regularization on the classification function while
maximum absolute margin corresponds to an *l _{2}* norm constraint
on the classification function. Interestingly, the proposed
improvements only require simple extensions to existing maximum
margin formulations and preserve the computational efficiency of
SVMs. Through the maximization of relative margin, surprising
performance gains are achieved on real-world problems such as digit,
text classification and on several other benchmark data sets. In addition,
risk bounds are derived for the new formulation based on Rademacher averages.