In the Previous Post...

The previous post introduced image classification, one of the most representative tasks in computer vision, as well as the simple KNN (k-Nearest Neighbor) classifier. It described several challenges in image classification and explained why we use data-driven algorithms to address them. Classification based only on comparing a distance metric between samples, however, has two problems:

1. The classifier must retain all training data as a reference for test data. Keeping that data in memory is inefficient.
2. Classifying a single item requires comparing it with every training example, making computation expensive.

KNN offers limited generalization and uses memory inefficiently. Image classification therefore needed a more efficient approach: learning with a neural network. Everything covered up to that point was not really about deep learning, but about how to define a task such as computer vision, what a data-driven algorithm means, and why we choose that methodology.

Neural Network Circuits

The neural-network circuit approach imitates the operating principles of the human nervous system.

To represent how a neuron receives and transmits information, an input $X$ interacts with weights $W$ and produces an output through an activation function $f$. This is called a perceptron. A perceptron cannot fully reproduce a neuron, so it is misleading to map dendrites, the soma, axons, and other biological parts directly onto perceptron components. Instead, think of it as defining information transmission by an affine transform $X\cdot W+b$ of input $X$ and then applying a nonlinear function $f$ to increase logical complexity. More concretely, when an input $X$ enters the computation, predefined parameters $W$ and $b$ produce an output; applying a nonlinear function yields a score or some indicator of the result.

$$output = f(X \cdot W + b)$$

If the defined parameters $W$ and $b$ behave as intended on the input dataset, the difference between the output and label (ground truth) will converge to $0$.

$$\rho(output,~label)$$

We must therefore define a distance metric $\rho$ that meaningfully measures the difference between output and label. The neural-network parameters will be adjusted incrementally according to this metric.

Score function / Loss function / Cost function

Choosing the distance metric $\rho$ appropriately is important, as is the task represented by the ground-truth labels. If $\rho$ is unsuitable, it may fail to capture the difference between ground truth and output, or training may be unable to converge. When viewed as a function, this metric $\rho$ is called a loss function or cost function. Both terms imply how far something falls short of a criterion. To preview a later point, unsupervised, semi-supervised, and supervised learning all ultimately need a reference point that can play the role of ground truth. Returning to the topic, neural-network optimization requires a loss or cost function.
Since this post is about linear classification, let us make the explanation specific to that task. In addition to loss, we need the concept of a score function. A score function maps raw data to a score for each class, while the loss function uses those scores to quantify the difference between a prediction and its label. Here, raw data means the input $X$ supplied to the neural network.
Let us formulate exactly how an image is mapped to scores. Suppose there are $N$ image samples, each corresponding to one of $K$ classes.

$$x_i~(i = 1,~2,~3,~\cdots,~N) \rightarrow y_j~(j = 1,~2,~\cdots,~K)$$

Interpreting these in matrix dimensions, a CIFAR-10 input image, for example, has size $32 \times 32 \times 3$, so

$$x_i \in \mathbb{R}^D,~D = 32 \times 32 \times 3 = 3072$$

The image sample $x_i$ can be flattened into a one-dimensional vector whose length is the product of all three dimensions of the image tensor. As its name suggests, CIFAR-10 contains 10 classes, so it corresponds to $K=10$ in the expression above.

$$\begin{aligned} W &\in \mathbb{R}^{D \times K}, \newline X &\in \mathbb{R}^{1 \times D}, \newline b &\in \mathbb{R}^{1 \times K} \end{aligned}$$ $$f(X \cdot W + b) = f(Y),~Y \in \mathbb{R}^{1 \times K}$$

Because activation function $f$ operates element-wise on the vector, the output retains the dimensions of the affine-mapped $Y$. The neural-network circuit can therefore replace an input image with $3072$ dimensions with scores for $10$ classes. As introduced earlier, the learnable parameters $W$ and $b$ are called the weight and bias. The discussion so far can be summarized in four points.

1. The single matrix product $X \cdot W$ can be computed efficiently. Here, efficient means parallelizable: each label score in $X \cdot W$ is computed from a row vector of $W$. Although there are 10 classes, their computations can run in parallel.

2. The data $(x_i,y_i)$ is fixed, but the function parameters $W$ and $b$ can be adjusted.

3. The goal is to pass training data $(x,y)$ through the network and find $W$ and $b$ that predict the dataset well. We therefore no longer need to keep the training data in memory after training.

4. This is much faster than comparing a test image with every training image, as KNN does.

The computation can be illustrated as above. Strictly speaking, the diagram behaves differently from the activation function $f$ previously described. In this example, treat $f$ as simply the affine function $X \cdot W+b$. The result on the far right contains the predicted scores used for classification. Since the dog score is highest, the model will probably predict “dog”—an obviously incorrect answer here.

Once expanded into a high-dimensional vector, an image can be interpreted as a point in a coordinate system with 3,072 axes. Linear classification maps the entire image dataset $X$ directly into this 3,072-dimensional space. The figure above reduces those dimensions to two for ease of understanding.
As explained earlier, each row vector of $W$ classifies one label. Geometrically, changing a row vector is like rotating the classifier in another direction, while bias $b$ shifts the classifier relative to the origin.
A linear classifier can also be interpreted as template matching, like KNN. Every $X \cdot W$ computation is the inner product between a row vector of $W$ and $X$ (a column vector). This lets $W$ learn a template or prototype and find the closest value in vector space. The problem can ultimately be interpreted like KNN, which treats samples as prototypes and predicts from the nearest $K$ samples. This may not be intuitive at first, but an inner product itself acts as a distance metric, much like calculating an $L_1$ or $L_2$ distance.
For example, the learned horse template might show two horses facing each other. A car classifier should distinguish many colors and types of cars, yet red features biased by the dataset may dominate. The figure below shows the weights learned for each class.

A simple linear classifier trained on the dataset produces a weight prototype for each class, as shown above. When a new sample is projected onto a prototype, greater similarity produces a larger value. This mechanism does not provide especially good generalization. To overcome these problems, deep neural architectures later introduce hidden layers and move beyond prototype-style learning.

Weight and bias

If bias and weight are learned and computed separately, the parallelization of row-vector operations described above cannot be applied to the bias. But adding bias is simply an element-wise sum with each element of the linear projection of $X$ and $W$, so it can be incorporated by adding a dimension instead of being learned separately.

Append an element $1$ to the input and extend the row vector with the bias on its right. The two operations can then be optimized together rather than processed separately.

Loss functions

Everything described so far concerns making a neural network predict one score for each desired class. When the network gives a wrong or ambiguous answer for an input, we need a criterion that quantifies the error and supports optimization. We will therefore examine basic forms of the objective $\rho$ introduced earlier, beginning with a brief introduction to the support vector machine.

Support Vector Machine (SVM)

The basic principle of an SVM is to give the score of the correct answer for each image a margin ($\Delta$) above the scores of other classes. In a linear classification model, it maximizes the score at the correct class index while minimizing those at the remaining class indices. For a variable $j$ indexing classes from 1 through $K$, the score of sample $i$ ($x_i$) is

$$s_j = f(x_i,~W)_j$$

Because SVM loss requires the correct class score to exceed every other class score by at least a margin $\Delta$, the SVM loss for sample $i$ is

$$L_i = \sum\_{j \neq y_i} \max (0, s_j - s_{y_i} + \Delta)$$

Suppose the correct answer for sample $i$ is $y_i$, mapped to one of $K$ classes. $s_{y_i}$ is the score assigning sample $i$ to its correct class $y_i$, while each $s_j$ is the score assigning sample $i$ to an incorrect class $j$. If the score for class $j$ is not at least the margin below the score of the correct class $y_i$, the argument to $\max$ is positive and the loss increases. Loss definitions vary by task, but in general they grow as a result moves farther from the desired criterion. Here, loss increases unless all incorrect-class scores lie at least the margin below the correct-class score.

The figure above visualizes this idea. Training continues until every other class score has been reduced enough to differ by the margin. In neural-network matrix notation,

$$L_i = \sum\_{j \neq y_i} \max (0, W_j^\top x_i - W_{y_i}^\top x_i + \Delta)$$

If $k$ is the class index whose score we want, the required element is row vector $k$ of matrix $W$, which is combined with sample $x_i$ by an inner product. A loss defined around a threshold in this way is called hinge loss. To penalize predictions more heavily or make the loss differentiable, we can instead use

$$\max (0,~-)^2$$

SVM loss has a major problem. If a trained $W$ can make a particular class score larger by the desired margin $\Delta$, every scalar multiple of $W$ can do the same. For every $\lambda$ with $\lambda>1$, for example, the scores produced by $\lambda W$ are also scaled above 1 and satisfy the same condition. From an optimization perspective, having multiple global minima violates the conditions for convex optimization. Without a constraint in the problem, training may slow down or diverge. We therefore add a regularization penalty to restrict the search to a more feasible region—that is, a meaningful manifold that can actually be explored.

$$R(W) = \sum\_k \sum\_l W\_{k,~l}^2$$

The $L_2$ norm of a two-dimensional matrix $W$ is defined as above. Among the many possible values of $W$, it encourages the ideal optimum to be the one closest to the origin on an $n$-dimensional hypersphere. The loss we minimize therefore combines the hinge loss introduced earlier with the $L_2$ regularization loss above.

$$\begin{aligned} L =& \frac{1}{N} \sum\_i L_i + \lambda R(W) \newline L =& \frac{1}{N} \sum\_i \sum\_{j \neq y_i} \max \left( 0, W_j^\top x_i - W_{y_i}^\top x_i + \Delta \right) + \lambda \sum\_k \sum\_l W\_{k,~l}^2 \end{aligned}$$

When optimizing multiple loss functions, the user typically chooses hyperparameter $\lambda$ through cross-validation. From an optimization perspective, the regularization term makes the problem closer to convex optimization, as explained above. From the perspective of post-training performance, larger weight parameters make the network more sensitive to changes in the input and can cause overfitting. Explanations of regularization losses and methods therefore often say they are used to prevent overfitting. That is correct, but it is not the whole reason for regularization.

Hyperparameters in SVM

We introduced $\lambda$ as an adjustable hyperparameter, but $\Delta$ in the hinge loss must also be chosen by the user. Since $\lambda$ controls the scale of the weights, adjusting $\lambda$ would require a corresponding adjustment to $\Delta$. The two hyperparameters are related rather than acting independently on performance, so we can leave $\Delta$ fixed and consider only $\lambda$, which controls weight magnitude, as the hyperparameter. The SVM classifier described so far applies regardless of the number of classes. For binary classification with two classes, fixing the margin at $1$ gives

$$L_i = C \max \left(0,~1-y_iw^\top x_i \right) + R(W)$$

Here, constant $C$ is a hyperparameter inversely proportional to $\lambda$. In a binary support vector machine, $y_i$ takes the values $-1,~1$ rather than representing a class index.

Softmax

The SVM introduced above is one type of classifier. Another representative choice is the softmax classifier. I have rarely used an SVM in recent projects or deep-learning assignments, while softmax appears frequently when applying energy-based functions, so it may be the more important concept in practice. Softmax can be summarized as extending binary logistic regression to a multiclass classifier. Binary logistic regression begins with two categories, $0$ and $1$, whose classification probabilities sum to 1. It differs from ordinary linear regression because it uses a linear model in a special way, constraining the target $y$ to lie between $0$ and $1$. Consider a model that predicts a dependent variable $y$ taking the values $0$ or $1$ from an independent variable $x$. An ordinary linear model would be $y=Wx+b$. Linear regression finds the slope (weight) and intercept (bias) of a line that represents multiple data points, but this linear formulation is not very helpful for classification with only two possible dependent-variable values.

The range of a linear function extends to infinity regardless of how the data and parameters are chosen, rather than remaining between $0$ and $1$. Since this is unrelated to the result we want, functions were designed to map onto the desired values $0$ and $1$ of the dependent variable $y$: the logistic model $g(x)=\frac{e^x}{1+e^x}$ and the Gumbel model $g(x)=e^{-e^x}$. Because the nested exponentials make the Gumbel model expensive to compute, the simpler logistic model came into use.

As the form of the logistic function shows, its dependent-variable output is always between 0 and 1 for a continuous independent variable $x$. Two concepts used in the computation are odds and logit. Odds are the ratio of the probability of success to the probability of failure. If the probability that the dependent variable belongs to class $1$ for a given independent variable is the probability of success, then

$$\text{Odds} = \frac{p(y = 1 \vert x)}{1-p(y = 1 \vert x)}$$

Because probability $p$ ranges from 0 to 1, taking its logarithmic odds gives the logit

$$\text{Logit} = \log(\text{Odds}) = \log \left( \frac{p}{1-p} \right)$$

which spans the entire real line. We now have a function defining the relationship between dependent variable $p$ and independent variable $x$, so linear regression can be applied.

$$\log \left( \frac{p}{1-p} \right) = Wx+b$$

This expression is not defined directly in terms of $y$. Solving it for dependent variable $p$ turns it into a logistic-regression problem.

$$p = \frac{e^{b+Wx}}{1+e^{b+Wx}}$$

This demonstrates that classification with softmax is possible in a neural network. We have considered only the binary case so far, but the idea can be extended to multiple classes. The logistic function used in logistic regression converts an input score into an estimated class probability. Whereas an SVM classifier uses scores directly, this approach uses probabilities obtained through logistic mapping.

$$p_i = \frac{e^{z_i}}{ \sum_{j = 1}^k e^{z_j}},~\text{for }i = 1,~2,~\cdots,~k$$

This is called the softmax function. Here, $i$ is the class index and $z_i$ is its score. To return probabilities for $k$ classes, softmax transforms $k$ scores into a vector of values in the range $0~1$—a normalized probability distribution. The loss aims to make the probability at the correct class index approach $1$, and is computed by taking the negative logarithm of the softmax result.

$$L_i = -\log \left( \frac{e^{f_{y_i}}}{\sum_j e^{f_j}} \right) = -f_{y_i} + \log \sum\_j e^{f_j}$$

Minimizing this expression increases the target-class score $f_{y_i}$ and decreases the remaining scores, so SVM and softmax ultimately share the same direction. The resulting loss is called cross-entropy loss.

Cross-Entropy Loss and Information Theory

We commonly say entropy is high when a situation is confusing or uncertain. In probabilistic terms, entropy is large when we cannot be confident about a piece of information. Given possible outcomes (results or information) $x_1,\sim x_n$ and their respective probabilities $p(x_1),\sim p(x_n)$, Shannon entropy is

$$H(X) = -\sum_{i = 1}^n p(x_i) \log p(x_i)$$

This expression can be interpreted as the amount of information that probability distribution $p(x)$ preserves about $p(x)$ itself. If we are uncertain about every outcome, $p(x_i)$ is distributed uniformly, and preserving all possible outcomes requires more information, increasing entropy. Conversely, if $p(x_i)$ is uneven enough that we can be confident about the outcome, the result can be represented without preserving every possibility, reducing entropy. Now consider how much information a predicted distribution $p(x)$ preserves about $q(x)$. Assume we know the target distribution and treat it as ground truth $q(x)$.

$$H(p,~q) = -\sum_{i = 1}^n q(x_i) \log p(x_i)$$

From a classification perspective, for each $x_i$ the ideal distribution assigns probability $1$ to the correct class index and $0$ to all other classes. The softmax term $\frac{e^{f_{y_i}}}{\sum_j e^{f_j}}$ is the predicted probability $p(x_i)$. Decomposing cross-entropy gives

$$H(p,~q) = -\sum_{i = 1}^n q(x_i) \log \left( \frac{p(x_i)}{q(x_i)} \right) + q(x_i) \log q(x_i)$$

The first term on the right is the KL divergence, which expresses the distance between distributions $p(x)$ and $q(x)$. Since this distance is nonnegative, the following inequality holds.

$$H(p,~q) = D_{KL}(q \parallel p) + H(q) \ge H(q)$$

Cross-entropy must therefore be greater than or equal to entropy. The original distribution's $H(q)$ is treated as a constant, so its derivative is $0$ and it does not affect training. Optimizing cross-entropy is consequently equivalent to optimizing KL divergence.
The model predicts unnormalized scores, which softmax—with its exponential function—converts into normalized probabilities. Maximizing the probability that an image belongs to a particular class is equivalent to maximizing likelihood and can be interpreted as MLE through Bayes' rule below.

$$p(x_i \vert y_i) = \frac{p(y_i \vert x_i)p(x_i)}{p(y_i)}$$

This form cannot account for the input prior. In a neural network, however, matrix $W$ can take its place. If $y_i$ is interpreted as a transformation of input $x_i$ through parameter $W$, the prior can be rewritten as

$$p(x_i \vert W) = \frac{p(y_i \vert W)p(W)}{p(y_i)}$$

Thus, while optimizing classification likelihood, $W$ can simultaneously serve as the prior, allowing the process to be interpreted as MAP (maximum a posteriori) estimation.

Normalization trick

Computing the exponentials above and applying log-likelihood can make the sum of exponentials in the denominator ($\sum_j e^{f_j}$) extremely large. Because the scores are unnormalized, values may overflow or lose precision during computation. We therefore use the following trick to reduce their magnitude.

$$\frac{e^{f_{y_i}}}{\sum_j e^{f_j}} = \frac{e^{f_{y_i} - \delta}}{\sum_j e^{f_j - \delta}}$$

Dividing both numerator and denominator by the same value $e^{-\delta}$ leaves the result unchanged. Let the largest original score be $f_{j^*}=\max(f_j)$. Then

$$\frac{e^{f_{y_i} - f_{j^*}}}{\sum_j e^{f_j - f_{j^*}}}$$

Rescaling relative to this maximum makes every exponent nonpositive, keeping the exponential values in the range $0\sim1$.

SVM vs. Softmax: Which Is Better?

We have examined two classifiers for linear classification: the support vector machine (SVM) and softmax.

An SVM applies hinge loss to the score function produced by a neural network. Softmax converts the network's score function into normalized probabilities and uses cross-entropy loss to perform MLE or MAP optimization.

Regularization in SVM—and in Softmax?

We noted that an SVM can have multiple values of $W$ producing the same loss. The following example shows why softmax nevertheless also uses $L_2$ regularization.

$$(1, -2, 0) \rightarrow (e^1, e^{-2}, e^0) = (2.71, 0.14, 1) \rightarrow (0.7, 0.04, 0.26)$$

Suppose a neural-network computation with some $W$ produces the values above. A softmax classifier converts scores $(1,-2,0)$ into normalized probabilities $(0.7,0.04,0.26)$. If regularization makes every element of this $W$ half as large, the probabilities become

$$(0.5, -1, 0) \rightarrow (e^{0.5}, e^{-1}, e^0) = (1.65, 0.37, 1) \rightarrow (0.55, 0.12, 0.33)$$

The result is more diffuse—a denser probability distribution. In other words, as weight parameters become smaller, the output probabilities become more uniform. Unlike the raw SVM score table, the ordering of probabilities remains the same while their confidence changes, rather than preserving absolute values or differences.

Conclusion

The performance difference between SVM and softmax is not very large, so there is no universal answer about which classifier is better for every task or practitioner. An SVM is described as having a more local objective—it focuses only where necessary—because it can ignore score differences larger than the margin. Softmax does not satisfy this condition because its loss never becomes zero, no matter how far apart the scores are. In summary, an SVM stops learning once its condition is met, whereas softmax continues updating parameters in pursuit of higher performance.