Linear classifiers and surrogate losses

The regularization note finished the linear regression section with a model that predicts a number and does not chase the noise. Many targets are not numbers but classes: spam or not, default or repayment, malignant or benign. The tempting shortcut is to code the two classes as $-1$ and $+1$, fit least squares with a ridge penalty, and predict the sign of the fitted value. This note shows why least squares with a linear model does that job badly, what a linear classifier should minimize instead, and how the oldest learning algorithm, the perceptron, fits into the picture. The losses it introduces return in every remaining note of the section: the logistic loss in logistic regression, the hinge in support vector machines.

Notation. The training set is $(x_1, y_1), \dots, (x_n, y_n)$ with $x_i \in \mathbb R^d$ and labels $y_i \in \{-1, +1\}$. A linear classifier has weights $w \in \mathbb R^d$ and a bias $b$; its score is $f(x) = \langle w, x\rangle + b$ and its prediction $a(x) = \operatorname{sign} f(x)$. The margin of example $i$ is $M_i = y_i f(x_i)$. $[\,\cdot\,]$ is 1 when the condition inside holds and 0 otherwise, and $\lVert w\rVert$ is the Euclidean norm. $\eta(x) = P(y = +1 \mid x)$ is the probability of the positive class at $x$.

Why not least squares on the labels?#

Take six points on a line: negatives at $-3, -2, -1$ and positives at $1, 2, 3$. Least squares on the labels $\pm 1$ fits $f(x) = 3x/7$, and the boundary $f(x) = 0$ sits at $x = 0$, exactly between the classes. Now add three more positives at $20, 21, 22$, so clearly positive that no sensible rule should move. The least-squares fit becomes $f(x) = (27x - 37)/456$, the boundary moves to $x = 37/27 \approx 1.37$, and the positive at $x = 1$ is now misclassified. Logistic regression, the subject of the next note, keeps the boundary at $0$ with no errors on the same nine points.

The reason is visible once the loss is written in terms of the margin. Since $y^2 = 1$,

$$(y - f)^2 = y^2 (1 - y f)^2 = (1 - M)^2 .$$

Squared error is a function of the margin that is smallest at $M = 1$ and grows on both sides. The three far points have scores around $1.1$ to $1.2$ under the new fit, margins above 1, and squared error charges them for being too right: lowering their scores towards 1 means flattening the line, which drags the boundary to the right. For a linear classifier, a loss that punishes large positive margins lets easy points move the boundary; the losses below never punish them.

A hyperplane splits the space#

The set $\{x : \langle w, x\rangle + b = 0\}$ is a hyperplane: a line in the plane, a plane in three dimensions. The classifier sends one side of it to $+1$ and the other to $-1$. For two points $x, x'$ on the hyperplane, $\langle w, x - x'\rangle = 0$, so $w$ is perpendicular to every direction within it: $w$ is the normal vector, and it points towards the positive side.

Distance to the boundary. Write any point as $x = x_\perp + r\, w/\lVert w\rVert$, where $x_\perp$ is its projection on the hyperplane and $r$ the signed distance along the unit normal. Since $\langle w, x_\perp\rangle + b = 0$,

$$f(x) = \langle w, x_\perp\rangle + b + r \frac{\langle w, w\rangle}{\lVert w\rVert} = r \lVert w\rVert, \qquad r = \frac{\langle w, x\rangle + b}{\lVert w\rVert} .$$

The score is the signed distance to the boundary, measured in units of $1/\lVert w\rVert$. Multiplying $w$ and $b$ by the same positive constant changes the scores but neither the boundary nor the predictions, so a linear classifier has one redundant degree of freedom; regularization will remove it. The bias can be absorbed by appending a constant feature $1$ to every $x$ and $b$ to $w$, which is how the code below handles it.

Worked example. With $w = (3, 4)$ and $b = -5$, the boundary is the line $3x_1 + 4x_2 = 5$ and $\lVert w\rVert = 5$. The point $x = (3, 1)$ has score $9 + 4 - 5 = 8$, so it is on the positive side at distance $8/5 = 1.6$. Its projection on the line is $x - (8/25)\, w = (2.04, -0.28)$, and indeed $3 \cdot 2.04 + 4 \cdot (-0.28) = 5$.

Figure

A linear classifier: boundary, normal and margin

The margin#

The margin $M_i = y_i(\langle w, x_i\rangle + b)$ combines the label and the score into one number. Its sign says whether the example is classified correctly; its size, divided by $\lVert w\rVert$, is the distance to the boundary, so it measures how confidently. In the figure the point closest to the boundary among the correct ones has $M = 0.9$, while a point of class $-1$ deep on the positive side has $M = -5.5$. The training error rate is the share of non-positive margins,

$$\frac1n \sum_{i=1}^n [M_i \le 0] ,$$

where $M_i = 0$, a point exactly on the boundary, is counted as an error. The function $[M \le 0]$ is the 0–1 loss written as a function of the margin.

Why the error count cannot be minimized directly#

The error rate is the natural objective, and it is unusable for two reasons.

• No gradient. As a function of $(w, b)$ it is piecewise constant: a small change of the weights either changes nothing or flips one point across the boundary. Its gradient is zero almost everywhere and undefined at the jumps, so gradient descent has nothing to follow.
• Computational hardness. Finding the hyperplane with the fewest training errors is NP-hard when the classes overlap (Höffgen, Simon and Van Horn, 1995), and even finding one whose error count is within a constant factor of the best is hard (Ben-David, Eiron and Long, 2003). Only the separable case is easy: a hyperplane with $y_i(\langle w, x_i\rangle + b) \ge 1$ for all $i$ is a feasible point of a linear program, found in polynomial time.

What the error rate estimates is still the right target. Its population version, the expected 0–1 loss, is minimized by the Bayes classifier, which predicts the more probable class, $\operatorname{sign}(2\eta(x) - 1)$, as the table of other losses, other targets records. The question is how to reach it by a computation that works.

Surrogate losses: upper bounds that can be minimized#

If $\tilde L(M) \ge [M \le 0]$ for every $M$, then

$$\frac1n \sum_{i=1}^n [M_i \le 0] \;\le\; \frac1n \sum_{i=1}^n \tilde L(M_i) .$$

The common choices are

$$\begin{aligned} \text{logistic:} \quad & \tilde L(M) = \log_2\big(1 + e^{-M}\big), \\ \text{hinge:} \quad & \tilde L(M) = \max(0,\, 1 - M), \\ \text{exponential:} \quad & \tilde L(M) = e^{-M}, \\ \text{squared hinge:} \quad & \tilde L(M) = \max(0,\, 1 - M)^2 . \end{aligned}$$

The logistic loss is usually written with the natural logarithm, $\log(1 + e^{-M})$. That version equals $\log 2 \approx 0.69$ at $M = 0$ and is not an upper bound near zero; dividing by $\log 2$, as above, makes it one and changes nothing about the minimizer.

The bound caps the error rate; it does not track it. With this loss, the margins $(-0.1, 3)$ have average surrogate loss $0.57$ and one error in two, while the margins $(0.1, 0.5)$ have $0.81$ and no error.

Figure

The 0–1 loss and its convex upper bounds

At $M = -1$, one unit on the wrong side, the four losses are $1.89$, $2$, $2.72$ and $4$; at $M = 2$, comfortably correct, they are $0.18$, $0$, $0.14$ and $0$. The squared error $(1 - M)^2$ of the opening example is also an upper bound on the step, but it is the only curve in the figure that rises again on the right. The other differences matter in practice:

Loss	Convex	Smooth	Zero for confident correct answers	Growth for $M \to -\infty$	Used by
logistic	yes	yes	no, only tends to 0	linear	logistic regression
hinge	yes	no, kink at $M = 1$	yes, for $M \ge 1$	linear	support vector machines
exponential	yes	yes	no	exponential	AdaBoost
squared hinge	yes	once differentiable	yes, for $M \ge 1$	quadratic	scikit-learn’s LinearSVC (its default loss)
squared error	yes	yes	no, rises again for $M > 1$	quadratic	least squares on $\pm 1$ labels

Convexity makes them minimizable. Each margin $M_i = y_i(\langle w, x_i\rangle + b)$ is linear in $(w, b)$, and a convex function of a linear function is convex. The average of convex functions is convex, so every local minimum of the empirical surrogate risk is global and gradient methods converge to it. Smoothness decides which methods apply: gradient descent and Newton’s method for the logistic loss, subgradients or a reformulation for the hinge.

Growth on the left decides robustness. A mislabelled point sits at a large negative margin. The linear losses charge it in proportion to how wrong it is, the exponential loss exponentially, so one bad label can dominate the sum; this is the known weakness of AdaBoost on noisy labels (Hastie, Tibshirani and Friedman, 2009, Section 10.6). Exponential loss returns in the gradient boosting note.

What each surrogate estimates#

At a single point $x$ with $\eta = \eta(x)$, a score $f$ incurs the expected surrogate loss $\eta \tilde L(f) + (1 - \eta) \tilde L(-f)$, because the label is $+1$ with probability $\eta$. Minimizing it over $f$ gives the score that a perfectly flexible model trained on unlimited data would output. For the logistic loss with the natural logarithm, $\frac{d}{df}\log(1 + e^{-f}) = -(1 - \sigma(f))$ with $\sigma(f) = 1/(1 + e^{-f})$, so the derivative of the expected loss is

$$-\eta\,\big(1 - \sigma(f)\big) + (1 - \eta)\, \sigma(f) = \sigma(f) - \eta = 0 \quad\Longrightarrow\quad f^* = \log\frac{\eta}{1 - \eta} .$$

The other rows follow the same way (Hastie, Tibshirani and Friedman, 2009, Table 12.1); the support vector machines note derives the hinge row.

Loss	Minimizer $f^*(\eta)$	At $\eta = 0.8$	Recovers $\eta$?
logistic	$\log\frac{\eta}{1-\eta}$, the log-odds	$1.386$	yes
exponential	$\frac12 \log\frac{\eta}{1-\eta}$	$0.693$	yes
hinge	$\operatorname{sign}(2\eta - 1)$	$1$	no
squared hinge, squared error	$2\eta - 1$	$0.6$	yes, on $[-1, 1]$

Every row has the sign of $2\eta - 1$, so each surrogate, minimized over all functions, gives the Bayes classifier. This property is called classification calibration, and for a convex surrogate it holds exactly when the loss is differentiable at $0$ with a negative derivative there (Bartlett, Jordan and McAuliffe, 2006; Zhang, 2004). The rows differ in what else they keep. The hinge minimizer is $\pm 1$ whatever $\eta$ is, so a hinge-trained score says on which side a point falls and nothing about how likely the side is; the logistic minimizer is the log-odds itself, from which $\eta = \sigma(f^*)$. The exponential and squared rows invert too, through other links: $\eta = \sigma(2f^*)$ and $\eta = (f^* + 1)/2$, both $0.8$ at the scores of the table.

The squared-error row also explains the opening example. Over all functions, squared error on $\pm 1$ labels is classification-calibrated and even recovers $\eta$. What failed there was the linear fit: a line cannot follow $2\eta - 1$ everywhere, and squared error spends its slope on far points that are already correct. The logistic loss is the starting point of the next note.

The perceptron: stochastic gradient descent at zero margin#

The perceptron of Rosenblatt (1958) is the oldest training rule for a linear classifier. It visits the examples one by one and corrects the weights only after a mistake:

$$\text{if } y_i(\langle w, x_i\rangle + b) \le 0: \qquad w \leftarrow w + y_i x_i, \quad b \leftarrow b + y_i .$$

It is stochastic gradient descent on the perceptron loss $\max(0, -M)$ with step size 1. The gradient of $\max(0, -y_i(\langle w, x_i\rangle + b))$ with respect to $w$ is $-y_i x_i$ for a misclassified example and $0$ for a correct one; at $M_i = 0$ the loss has a kink, and the rule takes the subgradient $-y_i x_i$. The step size does not matter when the weights start at zero: every iterate is then a sum of $\pm x_i$, and a different step only rescales it, which does not change any prediction. The perceptron loss is convex but not an upper bound on the 0–1 loss (it is $0$ at $M = 0$). The hinge differs from it by the shift to $1 - M$, which also charges correct points with margins below 1 and, as the SVM note shows, pushes the boundary away from the data.

Worked example. Four points, with the bias as a third coordinate: $x_1 = (2, 1)$ and $x_2 = (1, 3)$ positive, $x_3 = (-1, 1)$ and $x_4 = (0, -2)$ negative. Start from $w = (0, 0)$, $b = 0$ and visit the points in order:

Step	Point	Margin before	Update	$w$ after	$b$ after
1	$x_1$, $y = +1$	$0$	add $x_1$	$(2, 1)$	$1$
2	$x_2$, $y = +1$	$2 + 3 + 1 = 6$	none	$(2, 1)$	$1$
3	$x_3$, $y = -1$	$-(-2 + 1 + 1) = 0$	subtract $x_3$	$(3, 0)$	$0$
4	$x_4$, $y = -1$	$-(0 + 0 + 0) = 0$	subtract $x_4$	$(3, 2)$	$-1$

On the second pass the margins under $3x_1 + 2x_2 - 1$ are $7, 8, 2, 5$, all positive, and the algorithm stops after three updates.

Why it stops on separable data. Suppose some unit vector $u$ separates the data with margin $\gamma > 0$, that is $y_i \langle u, x_i\rangle \ge \gamma$ for all $i$, and $\lVert x_i\rVert \le R$ (the bias is absorbed into $x$, so both hold in the augmented space). Start from $w_0 = 0$ and let $w_k$ be the weights after $k$ updates. Each update is triggered by a point with $y\langle w_k, x\rangle \le 0$, so

$$\langle w_{k+1}, u\rangle = \langle w_k, u\rangle + y\langle x, u\rangle \ge \langle w_k, u\rangle + \gamma, \qquad \lVert w_{k+1}\rVert^2 = \lVert w_k\rVert^2 + 2y\langle w_k, x\rangle + \lVert x\rVert^2 \le \lVert w_k\rVert^2 + R^2 .$$

After $k$ updates $\langle w_k, u\rangle \ge k\gamma$ and $\lVert w_k\rVert \le \sqrt k\, R$, and by the Cauchy–Schwarz inequality $k\gamma \le \langle w_k, u\rangle \le \lVert w_k\rVert \le \sqrt k R$. Hence

$$k \le \Big(\frac{R}{\gamma}\Big)^2 ,$$

the bound of Novikoff (1962). It depends on neither the number of points nor the dimension, only on how wide the gap between the classes is relative to the spread of the data. It is a worst case: on 200 random points in the plane with a gap of at least $0.1$ on each side of a line through the origin, the bound is $253$ updates and the perceptron needs 4 (Code section).

When the classes overlap, some point is always misclassified, the updates never stop, and the final weights depend on where the run is cut off. Averaging the weight vectors over all steps, or letting them vote, gives a stable classifier with similar guarantees (Freund and Schapire, 1999), but the standard answer is to minimize a convex surrogate with a regularizer.

Linear separability#

A training set is linearly separable if some hyperplane classifies all of it correctly. The XOR pattern, positives at $(0, 0)$ and $(1, 1)$ and negatives at $(1, 0)$ and $(0, 1)$, is not: any line that puts both positives on one side puts a negative there too. Minsky and Papert (1969) made this limitation of the single perceptron famous. A new feature fixes it: with $x_1 x_2$ added, the four points become separable in three dimensions. Adding features by hand, implicitly through kernels, or by learning them in a neural network are the three ways the course goes beyond lines.

In high dimensions the opposite problem appears: almost everything is separable. Cover (1965) counted the labellings of $n$ points in general position in $\mathbb R^d$ that an affine hyperplane can realize. If the labels are random coin flips, the probability that they are linearly separable is

$$P(n, d) = \frac{1}{2^{n-1}} \sum_{k=0}^{d} \binom{n-1}{k} .$$

For $n \le d + 1$ it is 1, every labelling; for $n = 2(d + 1)$ it is exactly $1/2$; beyond that it falls quickly. In $d = 5$ dimensions the formula gives $1$, $0.5$ and $0.072$ for 6, 12 and 18 points, and 400 random labellings per size give $1$, $0.48$ and $0.065$ (Code section). Since $P(n, d)$ decreases as $n$ grows, a classifier with at least half as many parameters as examples ($d + 1$ with the bias, so $n \le 2(d + 1)$) separates random labels with probability at least $1/2$, and with $n \le d + 1$ it always does. Zero training error therefore proves nothing, since pure-noise labels reach it too; a bag-of-words model with tens of thousands of features is in exactly this regime. It is the classification face of the overfitting of the validation note.

What a regularizer adds#

On separable data the surrogate losses misbehave in two different ways. The logistic and exponential losses keep decreasing as $w$ is scaled up along any separating direction, so they have no minimizer and the weights run away; the hinge and squared hinge reach zero as soon as every margin exceeds 1, and then every larger multiple of $w$ is an equally good solution. Adding the ridge penalty of the regularization note,

$$\frac1n \sum_{i=1}^n \tilde L\big(y_i(\langle w, x_i\rangle + b)\big) + \lambda \lVert w\rVert^2 ,$$

fixes both. The objective is now strictly convex in $w$ and grows without bound as $\lVert w\rVert \to \infty$, so it has exactly one minimizer in $w$, and it is finite. The penalty also has a geometric meaning: with the margin condition $M_i \ge 1$, the distance from the boundary to the nearest point is at least $1/\lVert w\rVert$, so making $\lVert w\rVert$ small while keeping margins at least 1 maximizes the gap between the classes. That trade is the support vector machine. For the logistic loss the penalty has a third reading, a Gaussian prior on the weights, which the next note develops; the lasso penalty works as well and, as in regression, sets weights to zero.

What changed#

	Least squares on $\pm 1$ labels	Linear classifier with a surrogate loss
Loss of one example	$(1 - M)^2$	a convex upper bound on $[M \le 0]$: logistic, hinge, exponential
Confident correct answers	punished for $M > 1$	free or nearly free
What the score estimates	$2\eta - 1$, through a loss that also chases far points	log-odds (logistic), only the side (hinge)
Separable data	a unique fit that may misclassify	zero loss in the limit (logistic, exponential) or exactly (hinge); a regularizer picks one solution
Training	normal equations	gradient methods; the perceptron as SGD at zero margin

Limitations#

• The boundary is a hyperplane. Interactions such as XOR are invisible without new features.
• The surrogate is not the metric. Minimizing the logistic or hinge loss bounds the error rate, but the quantity that matters may be recall at a fixed false-alarm rate or the cost of errors; the classification metrics note separates the two.
• Scores are not probabilities. A score optimum turns into a probability only through a known link: $\sigma(f^*)$ for the logistic loss, $\sigma(2f^*)$ for the exponential loss, $(f^* + 1)/2$ for the squared losses; the hinge has none. Even then the probabilities are approximate with a finite sample and a linear model, which may not contain $f^*$.
• Outliers still pull. Linear growth is gentler than exponential, but a mislabelled point far on the wrong side still contributes the largest term of the sum.
• The guarantees are for the training set. Zero training error and a small surrogate loss say little when the number of features approaches the number of examples, as Cover’s count shows.

What you should remember#

• A linear classifier predicts $\operatorname{sign}(\langle w, x\rangle + b)$; $w$ is normal to the boundary, and $(\langle w, x\rangle + b)/\lVert w\rVert$ is the signed distance to it.
• The margin $M = y(\langle w, x\rangle + b)$ is positive for a correct answer and measures confidence. Squared error on $\pm 1$ labels is $(1 - M)^2$ and punishes large margins.
• The 0–1 loss has no useful gradient and minimizing it is NP-hard; convex upper bounds (logistic, hinge, exponential, squared hinge) bound the error rate and can be minimized.
• All of these surrogates lead to the Bayes classifier. The logistic loss also recovers the log-odds, the exponential and squared losses recover $\eta$ through other links, the hinge only the side.
• The perceptron is SGD on $\max(0, -M)$; on separable data it makes at most $(R/\gamma)^2$ mistakes, and on overlapping data it never settles.
• Separability is common in high dimensions ($P = 1/2$ at $n = 2(d + 1)$ random labels); a regularizer makes the solution unique and finite and, with the hinge, maximizes the margin.

Code#

Least squares against a classification loss, the surrogate losses and their minimizers, the perceptron and its bound, and Cover’s count:

import numpy as np
from math import comb
from scipy.optimize import linprog, minimize_scalar
from sklearn.linear_model import LogisticRegression

rng = np.random.default_rng(0)

# 1. least squares on ±1 labels: three far, clearly positive points move the boundary
x = np.array([-3, -2, -1, 1, 2, 3, 20, 21, 22.])
y = np.r_[-np.ones(3), np.ones(6)]
b, w = np.linalg.lstsq(np.c_[np.ones_like(x), x], y, rcond=None)[0]
print(round(-b / w, 4), int((np.sign(b + w * x) != y).sum()))            # 1.3704 1: the positive at x = 1 is lost
lr = LogisticRegression().fit(x[:, None], y)
print(round(-lr.intercept_[0] / lr.coef_[0, 0], 4), int((lr.predict(x[:, None]) != y).sum()))   # -0.0002 0

# 2. the surrogate losses at margins -1, 0 and 2
M = np.array([-1, 0, 2.])
losses = {'logistic': np.log2(1 + np.exp(-M)), 'hinge': np.maximum(0, 1 - M), 'exponential': np.exp(-M),
          'squared hinge': np.maximum(0, 1 - M) ** 2, 'squared error': (1 - M) ** 2}
for name, v in losses.items():
    print(name, v.round(3))
# logistic [1.895 1. 0.183] | hinge [2. 1. 0.] | exponential [2.718 1. 0.135]
# squared hinge [4. 1. 0.] | squared error [4. 1. 1.]
# a smaller surrogate need not mean fewer errors: mean logistic loss and error rate of two pairs of margins
for pair in ([-0.1, 3], [0.1, 0.5]):
    print(np.log2(1 + np.exp(-np.array(pair))).mean().round(2), np.mean(np.array(pair) <= 0))   # 0.57 0.5 | 0.81 0.0

# 3. what each surrogate estimates: the minimizer of eta L(f) + (1 - eta) L(-f) at eta = 0.8
eta = 0.8
for name, L in [('logistic', lambda m: np.log2(1 + np.exp(-m))), ('hinge', lambda m: max(0, 1 - m)),
                ('exponential', lambda m: np.exp(-m)), ('squared hinge', lambda m: max(0, 1 - m) ** 2)]:
    f = minimize_scalar(lambda f: eta * L(f) + (1 - eta) * L(-f), bounds=(-5, 5), method='bounded', options={'xatol': 1e-9}).x
    print(name, round(f, 3))
# logistic 1.386 (log 4) | hinge 1.0 | exponential 0.693 (log 2) | squared hinge 0.6

# 4. the perceptron on the four points of the worked example, then on a separable cloud against Novikoff's bound
def perceptron(X, y, max_epochs=1000):
    Xb = np.c_[X, np.ones(len(X))]
    w, updates = np.zeros(Xb.shape[1]), 0
    for _ in range(max_epochs):
        mistakes = 0
        for xi, yi in zip(Xb, y):
            if yi * (w @ xi) <= 0:
                w, updates, mistakes = w + yi * xi, updates + 1, mistakes + 1
        if mistakes == 0:
            return w, updates
    return w, updates

print(perceptron(np.array([[2., 1], [1, 3], [-1, 1], [0, -2]]), np.array([1, 1, -1, -1])))   # (array([ 3.,  2., -1.]), 3)
u = np.array([0.6, 0.8])                       # the separating direction, through the origin
X = rng.uniform(-1, 1, (2000, 2))
X = X[np.abs(X @ u) >= 0.1][:200]              # keep a gap of at least 0.1 on each side of the line
y = np.sign(X @ u)
Xb = np.c_[X, np.ones(len(X))]                 # the perceptron learns a bias too: work in the augmented space
R, gamma = np.linalg.norm(Xb, axis=1).max(), (y * (Xb @ np.r_[u, 0])).min()
print(perceptron(X, y)[1], round((R / gamma) ** 2, 1))                   # 4 253.4: four updates, bound 253

# 5. Cover: the chance that random labels on n points in general position in R^5 are linearly separable
def separable(X, y):
    A = -y[:, None] * np.c_[X, np.ones(len(X))]     # y_i (w·x_i + b) >= 1 as A [w, b] <= -1
    return linprog(np.zeros(X.shape[1] + 1), A_ub=A, b_ub=-np.ones(len(X)), bounds=(None, None)).status == 0
d = 5
for n in (6, 12, 18):
    share = np.mean([separable(rng.normal(size=(n, d)), rng.choice([-1., 1.], n)) for _ in range(400)])
    exact = sum(comb(n - 1, k) for k in range(d + 1)) / 2 ** (n - 1)
    print(n, share, round(exact, 4))
# 6 1.0 1.0 | 12 0.48 0.5 | 18 0.065 0.0717

Next#

The surrogate losses turn classification into an optimization problem, and among them the logistic loss stands out: its minimizer is the log-odds, so its scores can be read as probabilities. A probability is often what the application needs, to compare a click’s chance with its price or a patient’s risk with the cost of a test. The next note derives logistic regression from a probability model of the label, shows that the logistic loss is its negative log-likelihood, and asks when its probabilities can be trusted.

References#

• F. Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408, 1958.
• A. B. J. Novikoff. On convergence proofs on perceptrons. Proceedings of the Symposium on the Mathematical Theory of Automata, 12, 615–622. Polytechnic Institute of Brooklyn, 1962.
• M. Minsky, S. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969.
• T. M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, EC-14(3), 326–334, 1965.
• K.-U. Höffgen, H. U. Simon, K. S. Van Horn. Robust trainability of single neurons. Journal of Computer and System Sciences, 50(1), 114–125, 1995.
• S. Ben-David, N. Eiron, P. M. Long. On the difficulty of approximately maximizing agreements. Journal of Computer and System Sciences, 66(3), 496–514, 2003.
• P. L. Bartlett, M. I. Jordan, J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473), 138–156, 2006.
• T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1), 56–85, 2004.
• Y. Freund, R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3), 277–296, 1999.
• C. Cortes, V. Vapnik. Support-vector networks. Machine Learning, 20(3), 273–297, 1995.
• J. Friedman, T. Hastie, R. Tibshirani. Additive logistic regression: a statistical view of boosting. The Annals of Statistics, 28(2), 337–407, 2000. (AdaBoost as minimization of the exponential loss.)
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Section 4.5 (separating hyperplanes and the perceptron), Section 10.6 (loss functions and robustness), Section 12.3.2 and Table 12.1 (losses and their population minimizers).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Chapter 9 (halfspaces and the perceptron), Section 12.3 (surrogate loss functions).
• E. Sokolov et al. Машинное обучение (HSE), lecture notes: lecture 4: linear classification (margins and upper bounds on the error rate), lecture 5 (the logistic and hinge losses).