Is there a Good Illustrative Example where the Hinge Loss (SVM) Gives a Higher Accuracy than the Logistic Loss

Question

Vladimir Vapnik wrote:

“When solving a problem of interest, do not solve a more general problem as an intermediate step. Try to get the answer that you really need but not a more general one.”

Vapnik wrote this in the context of transductive learning, but the principle could also be applied to statistical pattern recognition tasks. If we just need to perform a hard classification, then we should aim to determine the decision boundary directly, rather than estimating the posterior probability of class membership and then threshold that at 0.5 (or some other threshold depending on the misclassification costs). In principle, we may be able to get better generalisation in terms of accuracy by following this principle as it focusses on the needs of the application, and avoids modelling compromises that benefit modelling of aspects of the data that are not relevant to the application at the expense of other aspects that are.

The performance of the SVM on real-world problems suggest that there may be some merit in this, but it is not easy to find a clear example where this is demonstrably the case. Can anyone suggest an example where a SVM will give better performance than an equivalent logistic regression model (i.e. kernels and regularisation should be available for the logistic regression model, so we are just comparing the loss used, rather than the other aspects of the models)? Preferably the example should demonstrate why this is the case.

Obviously the no-free lunch theorem suggests that no classifier system is going to be superior for all datasets, and the theoretical justification for the SVM is largely a worst-case analysis, so the SVM may be better in pathologically difficult problems, but not necessarily the average case.

Personally I prefer kernel logistic regression over the support vector machine, largely because the hyper-parameter tuning is much easier, and I think they are likely to give broadly similar results. However, I have an open mind where the needs of the application mean that the limitations of the SVM (e.g. having to know misclassification costs a-priori) are not a problem.

Please can we avoid discussions of whether accuracy is a good performance metric. It has issues, but there are some applications where accuracy is the relevant statistic of interest, and there have already been good discussions of this topic.

Note the answer here is the sort of thing I am looking for, but unfortunately it isn't correct (see my comment on the answer).

Answer 1

The example attributed to Olivier Bousquet doesn't work as clearly as depicted in the blog post mentioned in an answer to a related question, but I have been able to make it work to some extent in a more realistic setting, so I'll post it here in case it stimulates further (hopefully simpler or more informative) examples.

The (of course) adversarial learning task is shown below. The probability of membership of the positive class is given by

$$p(\mathcal{C}_+|x) = \frac{0.5}{(1 + \exp(-100*x))} + 0.25 + 0.24*\sin(20*x)$$

Note there are features of the true probability of class membership that do not affect the decision boundary, so any model may be distracted by modelling those irrelevant undulations at the expense of accurately determining the optimal decision boundary. To demonstrate that Bousqet's example builds a series of logistic regression-style models, of increasing complexity, based on Legendre polynomials (for numerical considerations). Here are the first seven basis functions:

The blog example is implemented in Mathmatica, which is a language I don't know, but I have been able to replicate their results in MATLAB tolerably well. What I think they have done is to fit these Legendre polynomial models firstly using the cross-entropy metric, and then using the hinge loss, but rather strangely they have fitted it directly to the true (sampled) probability of class membership, i.e. the response values lie between 0 and 1. Using the cross-entropy, I get this result:

Which is broadly the same as the Mathmatica implementation. Note that in the attempt to model the undulations in the probability of class membership, the model has overshot on occasion and so the accuracy is lower than we would get by simply placing a threshold at $x = 0$.

It wasn't completely clear how to implement the model with the hinge loss, as the logistic function clips the output to lie in the range of 0 to 1, so instead I used the hinge loss on the weighted sum of the Legendre basis functions and then afterwards applied the logistic function. This is the result:

All the models now achieve the optimal accuracy, although the estimates of the posterior probability of class membership are clearly inferior (if not actually plain wrong!).

HOWEVER this is not what we actually do when we have a classification task. If we knew the optimal posterior probability of class membership to determine the targets for the training data, we probably wouldn't need to build a classifier in the first place! So I then modified the code so that instead of the response values being the sampled true probability, I generated random x values (uniform distribution from -1 to +1) and then generated binary responses according to the probability of class membership.

This is the result for the cross-entropy error metric, which is pretty much the same as before.

Here is the result for the hinge loss, which is very different.

So why the difference? Well in the blog version, if we set the weight "linear" term to a very high value, then the weighted sum will be less than -1 for all of the data to the left of $x = 0$ and a value greater than +1 for all of the data on the right. In which case, the hinge loss will be zero, and we will get a classifier with minimal error regardless of model complexity. The hinge loss cannot be negative. However, if we sample the labels from a conditional Bernoulli distribution, we will have data on both sides of $x=0$ that are both positively and negatively labelled, and if they are the wrong side of $x=0$ they will have a non-zero hinge loss, and hence we will start penalising models with a large linear term increasingly harshly. It does have some excess error caused by trying to model the right-most undulation, but it does see to be more robust in terms of accuracy than the cross-entropy loss. So it is an example of how trying to classify the data directly, rather than estimate probability and then threshold, it just isn't as clear cut as the example in the blog suggests.

Update #1: Here are the results with a larger dataset (so sampling noise is less likely to be a factor). For the previous results I used 1024 training patterns, and for these I used 65536 (I work in a computer science department ;o). It seems to improve things a bit for the hinge loss, but the cross-entropy results look broadly similar.

Cross-entropy loss:

Hinge loss:

It is interesting (i.e. worrying) that for some of the simpler models, the output does not go through $(0, 1/2)$...

FWIW, this is the most complex of the hinge-loss models without the logistic transformation (but with an offset of 0.5 to make it easier to compare with the probabilities).

Answer 2

The results you shared are fascinating. Here's some more exploration in a similar direction.

The idea behind the Bousquet example is to create a situation where optimizing the logistic loss prioritizes fitting the underlying probability distribution at the expense of accuracy. But, it's not clear to me that accuracy and fit to the distribution would have to be opposed here. For example, it seems like a model that exactly matches the underlying distribution should yield both optimal accuracy and optimal logistic loss (at least in expectation).

I'll build a similar example that tries to simplify things, with only two models in the hypothesis space. One gives better accuracy but worse fit to the underlying distribution, and the other does the opposite. The tension between these two objectives is explicitly baked into the problem. I'll work directly with expected losses, so issues related to finite samples and/or optimization won't play any role.

True distribution

Suppose each point $x$ is drawn i.i.d. from the uniform distribution on $[-1, 1]$ and its class label $y \in \{-1, +1\}$ is drawn from a Bernoulli distribution $p(y \mid x)$. Similar to the Bousquet example, the conditional probability of the positive class is a 'wavy step function' (see plot below):

$$p(y=1 \mid x) = .598 \ \sigma(100 x) - .201 + .2 \sin(20 x)$$

where $\sigma$ is the logistic sigmoid function.

Models

Suppose our hypothesis space contains only two models (with no free parameters so 'fitting' means choosing one or the other):

The first model is a step function:

$$\hat{p}_1(y=1 \mid x) = \begin{cases} \sigma(1) & x \ge 0 \\ \sigma(-1) & x < 0 \\ \end{cases}$$

The second is a wavy step function, similar to the true distribution, but with slightly different parameters:

$$\hat{p}_2(y=1 \mid x) = .398 \ \sigma(100 x) - .301 + .3 \sin(20 x)$$

Where needed (e.g. for computing the hinge loss), 'raw' classifier outputs are computed as $f(x) = \operatorname{logit}(\hat{p}(y=1 \mid x))$. Since we're interested in accuracy, point predictions are computed as the mode of the predicted distribution over class labels (equivalent to the sign of the 'raw' output), which is the optimal decision under the 0-1 loss.

Note that the hypothesis space doesn't contain the true distribution. We're forced to choose between two approximations that make different tradeoffs. The first model (step function) is designed to make more accurate point predictions, at the expense of fit to the underlying distribution. In contrast, the second model (wavy step) is designed to match the underlying distribution better, at the expense of accuracy. To confirm that these tradeoffs are indeed present, the table below shows the expected 0-1 loss (better for model 1) and expected KL divergence from the true distribution to the model (better for model 2).

Hinge vs. logistic loss

Here are the expected losses for each model, where the expectation is taken w.r.t. the true data generating process (calculated by numerical integration). The best model according to each loss function is shown in bold+parentheses:

$$\begin{array}{rc} & \text{Model 1 (step)} & \text{Model 2 (wavy step)} \\ \text{0-1} & \mathbf{(.208)} & .269 \\ \text{KL} & .113 & \mathbf{(.044)} \\ \text{Hinge} & \mathbf{(.416)} & .580 \\ \text{Logistic} & .521 & \mathbf{(.474)} \\ \end{array}$$

Suppose we choose a model from our hypothesis space by minimizing the expected loss (i.e. what empirical risk minimization tries to do by proxy). As the table shows, minimizing the hinge loss gives the first model (prioritizing accuracy), whereas minimizing the logistic loss gives the second model (prioritizing fit to the underlying distribution).

Notes

Contrary to this example, accuracy and fit to the underlying distribution aren't always opposed. Even when such a conflict exists, the hinge and logistic losses may not necessarily behave as shown above.

For example, the amplitude of model 1's step function matters. It doesn't affect the accuracy (which only depends on the sign), but it does affect the hinge loss. Increasing the amplitude too far (overconfidence) incurs increasing penalties for misclassified points. And, shrinking it too far (underconfidence) penalizes correct predictions, which increasingly fall inside the margin. In both cases, the hinge loss will eventually favor the second model, thereby accepting a decrease in accuracy. This emphasizes that: 1) the hinge loss doesn't always agree with the 0-1 loss (it's only a convex surrogate) and 2) the effects in question depend on the hypothesis space.

In practice, I'd bet that regularization plays an important role too, together with the model selection algorithm. For example, regularization strength is often chosen to maximize validation set accuracy. Even if the logistic loss is used to fit the parameters, using the 0-1 loss for model selection might sacrifice fit to the underlying distribution in favor of accuracy.