570 lines
30 KiB
Plaintext
570 lines
30 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "2a074b4b",
|
|
"metadata": {
|
|
"origin_pos": 0
|
|
},
|
|
"source": [
|
|
"# Softmax Regression\n",
|
|
":label:`sec_softmax`\n",
|
|
"\n",
|
|
"In :numref:`sec_linear_regression`, we introduced linear regression,\n",
|
|
"working through implementations from scratch in :numref:`sec_linear_scratch`\n",
|
|
"and again using high-level APIs of a deep learning framework\n",
|
|
"in :numref:`sec_linear_concise` to do the heavy lifting.\n",
|
|
"\n",
|
|
"Regression is the hammer we reach for when\n",
|
|
"we want to answer *how much?* or *how many?* questions.\n",
|
|
"If you want to predict the number of dollars (price)\n",
|
|
"at which a house will be sold,\n",
|
|
"or the number of wins a baseball team might have,\n",
|
|
"or the number of days that a patient\n",
|
|
"will remain hospitalized before being discharged,\n",
|
|
"then you are probably looking for a regression model.\n",
|
|
"However, even within regression models,\n",
|
|
"there are important distinctions.\n",
|
|
"For instance, the price of a house\n",
|
|
"will never be negative and changes might often be *relative* to its baseline price.\n",
|
|
"As such, it might be more effective to regress\n",
|
|
"on the logarithm of the price.\n",
|
|
"Likewise, the number of days a patient spends in hospital\n",
|
|
"is a *discrete nonnegative* random variable.\n",
|
|
"As such, least mean squares might not be an ideal approach either.\n",
|
|
"This sort of time-to-event modeling\n",
|
|
"comes with a host of other complications that are dealt with\n",
|
|
"in a specialized subfield called *survival modeling*.\n",
|
|
"\n",
|
|
"The point here is not to overwhelm you but just\n",
|
|
"to let you know that there is a lot more to estimation\n",
|
|
"than simply minimizing squared errors.\n",
|
|
"And more broadly, there is a lot more to supervised learning than regression.\n",
|
|
"In this section, we focus on *classification* problems\n",
|
|
"where we put aside *how much?* questions\n",
|
|
"and instead focus on *which category?* questions.\n",
|
|
"\n",
|
|
"\n",
|
|
"\n",
|
|
"* Does this email belong in the spam folder or the inbox?\n",
|
|
"* Is this customer more likely to sign up\n",
|
|
" or not to sign up for a subscription service?\n",
|
|
"* Does this image depict a donkey, a dog, a cat, or a rooster?\n",
|
|
"* Which movie is Aston most likely to watch next?\n",
|
|
"* Which section of the book are you going to read next?\n",
|
|
"\n",
|
|
"Colloquially, machine learning practitioners\n",
|
|
"overload the word *classification*\n",
|
|
"to describe two subtly different problems:\n",
|
|
"(i) those where we are interested only in\n",
|
|
"hard assignments of examples to categories (classes);\n",
|
|
"and (ii) those where we wish to make soft assignments,\n",
|
|
"i.e., to assess the probability that each category applies.\n",
|
|
"The distinction tends to get blurred, in part,\n",
|
|
"because often, even when we only care about hard assignments,\n",
|
|
"we still use models that make soft assignments.\n",
|
|
"\n",
|
|
"Even more, there are cases where more than one label might be true.\n",
|
|
"For instance, a news article might simultaneously cover\n",
|
|
"the topics of entertainment, business, and space flight,\n",
|
|
"but not the topics of medicine or sports.\n",
|
|
"Thus, categorizing it into one of the above categories\n",
|
|
"on their own would not be very useful.\n",
|
|
"This problem is commonly known as [multi-label classification](https://en.wikipedia.org/wiki/Multi-label_classification).\n",
|
|
"See :citet:`Tsoumakas.Katakis.2007` for an overview\n",
|
|
"and :citet:`Huang.Xu.Yu.2015`\n",
|
|
"for an effective algorithm when tagging images.\n",
|
|
"\n",
|
|
"## Classification\n",
|
|
":label:`subsec_classification-problem`\n",
|
|
"\n",
|
|
"To get our feet wet, let's start with\n",
|
|
"a simple image classification problem.\n",
|
|
"Here, each input consists of a $2\\times2$ grayscale image.\n",
|
|
"We can represent each pixel value with a single scalar,\n",
|
|
"giving us four features $x_1, x_2, x_3, x_4$.\n",
|
|
"Further, let's assume that each image belongs to one\n",
|
|
"among the categories \"cat\", \"chicken\", and \"dog\".\n",
|
|
"\n",
|
|
"Next, we have to choose how to represent the labels.\n",
|
|
"We have two obvious choices.\n",
|
|
"Perhaps the most natural impulse would be\n",
|
|
"to choose $y \\in \\{1, 2, 3\\}$,\n",
|
|
"where the integers represent\n",
|
|
"$\\{\\textrm{dog}, \\textrm{cat}, \\textrm{chicken}\\}$ respectively.\n",
|
|
"This is a great way of *storing* such information on a computer.\n",
|
|
"If the categories had some natural ordering among them,\n",
|
|
"say if we were trying to predict\n",
|
|
"$\\{\\textrm{baby}, \\textrm{toddler}, \\textrm{adolescent}, \\textrm{young adult}, \\textrm{adult}, \\textrm{geriatric}\\}$,\n",
|
|
"then it might even make sense to cast this as\n",
|
|
"an [ordinal regression](https://en.wikipedia.org/wiki/Ordinal_regression) problem\n",
|
|
"and keep the labels in this format.\n",
|
|
"See :citet:`Moon.Smola.Chang.ea.2010` for an overview\n",
|
|
"of different types of ranking loss functions\n",
|
|
"and :citet:`Beutel.Murray.Faloutsos.ea.2014` for a Bayesian approach\n",
|
|
"that addresses responses with more than one mode.\n",
|
|
"\n",
|
|
"In general, classification problems do not come\n",
|
|
"with natural orderings among the classes.\n",
|
|
"Fortunately, statisticians long ago invented a simple way\n",
|
|
"to represent categorical data: the *one-hot encoding*.\n",
|
|
"A one-hot encoding is a vector\n",
|
|
"with as many components as we have categories.\n",
|
|
"The component corresponding to a particular instance's category is set to 1\n",
|
|
"and all other components are set to 0.\n",
|
|
"In our case, a label $y$ would be a three-dimensional vector,\n",
|
|
"with $(1, 0, 0)$ corresponding to \"cat\", $(0, 1, 0)$ to \"chicken\",\n",
|
|
"and $(0, 0, 1)$ to \"dog\":\n",
|
|
"\n",
|
|
"$$y \\in \\{(1, 0, 0), (0, 1, 0), (0, 0, 1)\\}.$$\n",
|
|
"\n",
|
|
"### Linear Model\n",
|
|
"\n",
|
|
"In order to estimate the conditional probabilities\n",
|
|
"associated with all the possible classes,\n",
|
|
"we need a model with multiple outputs, one per class.\n",
|
|
"To address classification with linear models,\n",
|
|
"we will need as many affine functions as we have outputs.\n",
|
|
"Strictly speaking, we only need one fewer,\n",
|
|
"since the final category has to be the difference\n",
|
|
"between $1$ and the sum of the other categories,\n",
|
|
"but for reasons of symmetry\n",
|
|
"we use a slightly redundant parametrization.\n",
|
|
"Each output corresponds to its own affine function.\n",
|
|
"In our case, since we have 4 features and 3 possible output categories,\n",
|
|
"we need 12 scalars to represent the weights ($w$ with subscripts),\n",
|
|
"and 3 scalars to represent the biases ($b$ with subscripts). This yields:\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\begin{aligned}\n",
|
|
"o_1 &= x_1 w_{11} + x_2 w_{12} + x_3 w_{13} + x_4 w_{14} + b_1,\\\\\n",
|
|
"o_2 &= x_1 w_{21} + x_2 w_{22} + x_3 w_{23} + x_4 w_{24} + b_2,\\\\\n",
|
|
"o_3 &= x_1 w_{31} + x_2 w_{32} + x_3 w_{33} + x_4 w_{34} + b_3.\n",
|
|
"\\end{aligned}\n",
|
|
"$$\n",
|
|
"\n",
|
|
"The corresponding neural network diagram\n",
|
|
"is shown in :numref:`fig_softmaxreg`.\n",
|
|
"Just as in linear regression,\n",
|
|
"we use a single-layer neural network.\n",
|
|
"And since the calculation of each output, $o_1, o_2$, and $o_3$,\n",
|
|
"depends on every input, $x_1$, $x_2$, $x_3$, and $x_4$,\n",
|
|
"the output layer can also be described as a *fully connected layer*.\n",
|
|
"\n",
|
|
"\n",
|
|
":label:`fig_softmaxreg`\n",
|
|
"\n",
|
|
"For a more concise notation we use vectors and matrices:\n",
|
|
"$\\mathbf{o} = \\mathbf{W} \\mathbf{x} + \\mathbf{b}$ is\n",
|
|
"much better suited for mathematics and code.\n",
|
|
"Note that we have gathered all of our weights into a $3 \\times 4$ matrix and all biases\n",
|
|
"$\\mathbf{b} \\in \\mathbb{R}^3$ in a vector.\n",
|
|
"\n",
|
|
"### The Softmax\n",
|
|
":label:`subsec_softmax_operation`\n",
|
|
"\n",
|
|
"Assuming a suitable loss function,\n",
|
|
"we could try, directly, to minimize the difference\n",
|
|
"between $\\mathbf{o}$ and the labels $\\mathbf{y}$.\n",
|
|
"While it turns out that treating classification\n",
|
|
"as a vector-valued regression problem works surprisingly well,\n",
|
|
"it is nonetheless unsatisfactory in the following ways:\n",
|
|
"\n",
|
|
"* There is no guarantee that the outputs $o_i$ sum up to $1$ in the way we expect probabilities to behave.\n",
|
|
"* There is no guarantee that the outputs $o_i$ are even nonnegative, even if their outputs sum up to $1$, or that they do not exceed $1$.\n",
|
|
"\n",
|
|
"Both aspects render the estimation problem difficult to solve\n",
|
|
"and the solution very brittle to outliers.\n",
|
|
"For instance, if we assume that there\n",
|
|
"is a positive linear dependency\n",
|
|
"between the number of bedrooms and the likelihood\n",
|
|
"that someone will buy a house,\n",
|
|
"the probability might exceed $1$\n",
|
|
"when it comes to buying a mansion!\n",
|
|
"As such, we need a mechanism to \"squish\" the outputs.\n",
|
|
"\n",
|
|
"There are many ways we might accomplish this goal.\n",
|
|
"For instance, we could assume that the outputs\n",
|
|
"$\\mathbf{o}$ are corrupted versions of $\\mathbf{y}$,\n",
|
|
"where the corruption occurs by means of adding noise $\\boldsymbol{\\epsilon}$\n",
|
|
"drawn from a normal distribution.\n",
|
|
"In other words, $\\mathbf{y} = \\mathbf{o} + \\boldsymbol{\\epsilon}$,\n",
|
|
"where $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma^2)$.\n",
|
|
"This is the so-called [probit model](https://en.wikipedia.org/wiki/Probit_model),\n",
|
|
"first introduced by :citet:`Fechner.1860`.\n",
|
|
"While appealing, it does not work quite as well\n",
|
|
"nor lead to a particularly nice optimization problem,\n",
|
|
"when compared to the softmax.\n",
|
|
"\n",
|
|
"Another way to accomplish this goal\n",
|
|
"(and to ensure nonnegativity) is to use\n",
|
|
"an exponential function $P(y = i) \\propto \\exp o_i$.\n",
|
|
"This does indeed satisfy the requirement\n",
|
|
"that the conditional class probability\n",
|
|
"increases with increasing $o_i$, it is monotonic,\n",
|
|
"and all probabilities are nonnegative.\n",
|
|
"We can then transform these values so that they add up to $1$\n",
|
|
"by dividing each by their sum.\n",
|
|
"This process is called *normalization*.\n",
|
|
"Putting these two pieces together\n",
|
|
"gives us the *softmax* function:\n",
|
|
"\n",
|
|
"$$\\hat{\\mathbf{y}} = \\mathrm{softmax}(\\mathbf{o}) \\quad \\textrm{where}\\quad \\hat{y}_i = \\frac{\\exp(o_i)}{\\sum_j \\exp(o_j)}.$$\n",
|
|
":eqlabel:`eq_softmax_y_and_o`\n",
|
|
"\n",
|
|
"Note that the largest coordinate of $\\mathbf{o}$\n",
|
|
"corresponds to the most likely class according to $\\hat{\\mathbf{y}}$.\n",
|
|
"Moreover, because the softmax operation\n",
|
|
"preserves the ordering among its arguments,\n",
|
|
"we do not need to compute the softmax\n",
|
|
"to determine which class has been assigned the highest probability. Thus,\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\operatorname*{argmax}_j \\hat y_j = \\operatorname*{argmax}_j o_j.\n",
|
|
"$$\n",
|
|
"\n",
|
|
"\n",
|
|
"The idea of a softmax dates back to :citet:`Gibbs.1902`,\n",
|
|
"who adapted ideas from physics.\n",
|
|
"Dating even further back, Boltzmann,\n",
|
|
"the father of modern statistical physics,\n",
|
|
"used this trick to model a distribution\n",
|
|
"over energy states in gas molecules.\n",
|
|
"In particular, he discovered that the prevalence\n",
|
|
"of a state of energy in a thermodynamic ensemble,\n",
|
|
"such as the molecules in a gas,\n",
|
|
"is proportional to $\\exp(-E/kT)$.\n",
|
|
"Here, $E$ is the energy of a state,\n",
|
|
"$T$ is the temperature, and $k$ is the Boltzmann constant.\n",
|
|
"When statisticians talk about increasing or decreasing\n",
|
|
"the \"temperature\" of a statistical system,\n",
|
|
"they refer to changing $T$\n",
|
|
"in order to favor lower or higher energy states.\n",
|
|
"Following Gibbs' idea, energy equates to error.\n",
|
|
"Energy-based models :cite:`Ranzato.Boureau.Chopra.ea.2007`\n",
|
|
"use this point of view when describing\n",
|
|
"problems in deep learning.\n",
|
|
"\n",
|
|
"### Vectorization\n",
|
|
":label:`subsec_softmax_vectorization`\n",
|
|
"\n",
|
|
"To improve computational efficiency,\n",
|
|
"we vectorize calculations in minibatches of data.\n",
|
|
"Assume that we are given a minibatch $\\mathbf{X} \\in \\mathbb{R}^{n \\times d}$\n",
|
|
"of $n$ examples with dimensionality (number of inputs) $d$.\n",
|
|
"Moreover, assume that we have $q$ categories in the output.\n",
|
|
"Then the weights satisfy $\\mathbf{W} \\in \\mathbb{R}^{d \\times q}$\n",
|
|
"and the bias satisfies $\\mathbf{b} \\in \\mathbb{R}^{1\\times q}$.\n",
|
|
"\n",
|
|
"$$ \\begin{aligned} \\mathbf{O} &= \\mathbf{X} \\mathbf{W} + \\mathbf{b}, \\\\ \\hat{\\mathbf{Y}} & = \\mathrm{softmax}(\\mathbf{O}). \\end{aligned} $$\n",
|
|
":eqlabel:`eq_minibatch_softmax_reg`\n",
|
|
"\n",
|
|
"This accelerates the dominant operation into\n",
|
|
"a matrix--matrix product $\\mathbf{X} \\mathbf{W}$.\n",
|
|
"Moreover, since each row in $\\mathbf{X}$ represents a data example,\n",
|
|
"the softmax operation itself can be computed *rowwise*:\n",
|
|
"for each row of $\\mathbf{O}$, exponentiate all entries\n",
|
|
"and then normalize them by the sum.\n",
|
|
"Note, though, that care must be taken\n",
|
|
"to avoid exponentiating and taking logarithms of large numbers,\n",
|
|
"since this can cause numerical overflow or underflow.\n",
|
|
"Deep learning frameworks take care of this automatically.\n",
|
|
"\n",
|
|
"## Loss Function\n",
|
|
":label:`subsec_softmax-regression-loss-func`\n",
|
|
"\n",
|
|
"Now that we have a mapping from features $\\mathbf{x}$\n",
|
|
"to probabilities $\\mathbf{\\hat{y}}$,\n",
|
|
"we need a way to optimize the accuracy of this mapping.\n",
|
|
"We will rely on maximum likelihood estimation,\n",
|
|
"the very same method that we encountered\n",
|
|
"when providing a probabilistic justification\n",
|
|
"for the mean squared error loss in\n",
|
|
":numref:`subsec_normal_distribution_and_squared_loss`.\n",
|
|
"\n",
|
|
"### Log-Likelihood\n",
|
|
"\n",
|
|
"The softmax function gives us a vector $\\hat{\\mathbf{y}}$,\n",
|
|
"which we can interpret as the (estimated) conditional probabilities\n",
|
|
"of each class, given any input $\\mathbf{x}$,\n",
|
|
"such as $\\hat{y}_1$ = $P(y=\\textrm{cat} \\mid \\mathbf{x})$.\n",
|
|
"In the following we assume that for a dataset\n",
|
|
"with features $\\mathbf{X}$ the labels $\\mathbf{Y}$\n",
|
|
"are represented using a one-hot encoding label vector.\n",
|
|
"We can compare the estimates with reality\n",
|
|
"by checking how probable the actual classes are\n",
|
|
"according to our model, given the features:\n",
|
|
"\n",
|
|
"$$\n",
|
|
"P(\\mathbf{Y} \\mid \\mathbf{X}) = \\prod_{i=1}^n P(\\mathbf{y}^{(i)} \\mid \\mathbf{x}^{(i)}).\n",
|
|
"$$\n",
|
|
"\n",
|
|
"We are allowed to use the factorization\n",
|
|
"since we assume that each label is drawn independently\n",
|
|
"from its respective distribution $P(\\mathbf{y}\\mid\\mathbf{x}^{(i)})$.\n",
|
|
"Since maximizing the product of terms is awkward,\n",
|
|
"we take the negative logarithm to obtain the equivalent problem\n",
|
|
"of minimizing the negative log-likelihood:\n",
|
|
"\n",
|
|
"$$\n",
|
|
"-\\log P(\\mathbf{Y} \\mid \\mathbf{X}) = \\sum_{i=1}^n -\\log P(\\mathbf{y}^{(i)} \\mid \\mathbf{x}^{(i)})\n",
|
|
"= \\sum_{i=1}^n l(\\mathbf{y}^{(i)}, \\hat{\\mathbf{y}}^{(i)}),\n",
|
|
"$$\n",
|
|
"\n",
|
|
"where for any pair of label $\\mathbf{y}$\n",
|
|
"and model prediction $\\hat{\\mathbf{y}}$\n",
|
|
"over $q$ classes, the loss function $l$ is\n",
|
|
"\n",
|
|
"$$ l(\\mathbf{y}, \\hat{\\mathbf{y}}) = - \\sum_{j=1}^q y_j \\log \\hat{y}_j. $$\n",
|
|
":eqlabel:`eq_l_cross_entropy`\n",
|
|
"\n",
|
|
"For reasons explained later on,\n",
|
|
"the loss function in :eqref:`eq_l_cross_entropy`\n",
|
|
"is commonly called the *cross-entropy loss*.\n",
|
|
"Since $\\mathbf{y}$ is a one-hot vector of length $q$,\n",
|
|
"the sum over all its coordinates $j$ vanishes for all but one term.\n",
|
|
"Note that the loss $l(\\mathbf{y}, \\hat{\\mathbf{y}})$\n",
|
|
"is bounded from below by $0$\n",
|
|
"whenever $\\hat{\\mathbf{y}}$ is a probability vector:\n",
|
|
"no single entry is larger than $1$,\n",
|
|
"hence their negative logarithm cannot be lower than $0$;\n",
|
|
"$l(\\mathbf{y}, \\hat{\\mathbf{y}}) = 0$ only if we predict\n",
|
|
"the actual label with *certainty*.\n",
|
|
"This can never happen for any finite setting of the weights\n",
|
|
"because taking a softmax output towards $1$\n",
|
|
"requires taking the corresponding input $o_i$ to infinity\n",
|
|
"(or all other outputs $o_j$ for $j \\neq i$ to negative infinity).\n",
|
|
"Even if our model could assign an output probability of $0$,\n",
|
|
"any error made when assigning such high confidence\n",
|
|
"would incur infinite loss ($-\\log 0 = \\infty$).\n",
|
|
"\n",
|
|
"\n",
|
|
"### Softmax and Cross-Entropy Loss\n",
|
|
":label:`subsec_softmax_and_derivatives`\n",
|
|
"\n",
|
|
"Since the softmax function\n",
|
|
"and the corresponding cross-entropy loss are so common,\n",
|
|
"it is worth understanding a bit better how they are computed.\n",
|
|
"Plugging :eqref:`eq_softmax_y_and_o` into the definition of the loss\n",
|
|
"in :eqref:`eq_l_cross_entropy`\n",
|
|
"and using the definition of the softmax we obtain\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\begin{aligned}\n",
|
|
"l(\\mathbf{y}, \\hat{\\mathbf{y}}) &= - \\sum_{j=1}^q y_j \\log \\frac{\\exp(o_j)}{\\sum_{k=1}^q \\exp(o_k)} \\\\\n",
|
|
"&= \\sum_{j=1}^q y_j \\log \\sum_{k=1}^q \\exp(o_k) - \\sum_{j=1}^q y_j o_j \\\\\n",
|
|
"&= \\log \\sum_{k=1}^q \\exp(o_k) - \\sum_{j=1}^q y_j o_j.\n",
|
|
"\\end{aligned}\n",
|
|
"$$\n",
|
|
"\n",
|
|
"To understand a bit better what is going on,\n",
|
|
"consider the derivative with respect to any logit $o_j$. We get\n",
|
|
"\n",
|
|
"$$\n",
|
|
"\\partial_{o_j} l(\\mathbf{y}, \\hat{\\mathbf{y}}) = \\frac{\\exp(o_j)}{\\sum_{k=1}^q \\exp(o_k)} - y_j = \\mathrm{softmax}(\\mathbf{o})_j - y_j.\n",
|
|
"$$\n",
|
|
"\n",
|
|
"In other words, the derivative is the difference\n",
|
|
"between the probability assigned by our model,\n",
|
|
"as expressed by the softmax operation,\n",
|
|
"and what actually happened, as expressed\n",
|
|
"by elements in the one-hot label vector.\n",
|
|
"In this sense, it is very similar\n",
|
|
"to what we saw in regression,\n",
|
|
"where the gradient was the difference\n",
|
|
"between the observation $y$ and estimate $\\hat{y}$.\n",
|
|
"This is not a coincidence.\n",
|
|
"In any exponential family model,\n",
|
|
"the gradients of the log-likelihood are given by precisely this term.\n",
|
|
"This fact makes computing gradients easy in practice.\n",
|
|
"\n",
|
|
"Now consider the case where we observe not just a single outcome\n",
|
|
"but an entire distribution over outcomes.\n",
|
|
"We can use the same representation as before for the label $\\mathbf{y}$.\n",
|
|
"The only difference is that rather\n",
|
|
"than a vector containing only binary entries,\n",
|
|
"say $(0, 0, 1)$, we now have a generic probability vector,\n",
|
|
"say $(0.1, 0.2, 0.7)$.\n",
|
|
"The math that we used previously to define the loss $l$\n",
|
|
"in :eqref:`eq_l_cross_entropy`\n",
|
|
"still works well,\n",
|
|
"just that the interpretation is slightly more general.\n",
|
|
"It is the expected value of the loss for a distribution over labels.\n",
|
|
"This loss is called the *cross-entropy loss* and it is\n",
|
|
"one of the most commonly used losses for classification problems.\n",
|
|
"We can demystify the name by introducing just the basics of information theory.\n",
|
|
"In a nutshell, it measures the number of bits needed to encode what we see, $\\mathbf{y}$,\n",
|
|
"relative to what we predict that should happen, $\\hat{\\mathbf{y}}$.\n",
|
|
"We provide a very basic explanation in the following. For further\n",
|
|
"details on information theory see\n",
|
|
":citet:`Cover.Thomas.1999` or :citet:`mackay2003information`.\n",
|
|
"\n",
|
|
"\n",
|
|
"\n",
|
|
"## Information Theory Basics\n",
|
|
":label:`subsec_info_theory_basics`\n",
|
|
"\n",
|
|
"Many deep learning papers use intuition and terms from information theory.\n",
|
|
"To make sense of them, we need some common language.\n",
|
|
"This is a survival guide.\n",
|
|
"*Information theory* deals with the problem\n",
|
|
"of encoding, decoding, transmitting,\n",
|
|
"and manipulating information (also known as data).\n",
|
|
"\n",
|
|
"### Entropy\n",
|
|
"\n",
|
|
"The central idea in information theory is to quantify the\n",
|
|
"amount of information contained in data.\n",
|
|
"This places a limit on our ability to compress data.\n",
|
|
"For a distribution $P$ its *entropy*, $H[P]$, is defined as:\n",
|
|
"\n",
|
|
"$$H[P] = \\sum_j - P(j) \\log P(j).$$\n",
|
|
":eqlabel:`eq_softmax_reg_entropy`\n",
|
|
"\n",
|
|
"One of the fundamental theorems of information theory states\n",
|
|
"that in order to encode data drawn randomly from the distribution $P$,\n",
|
|
"we need at least $H[P]$ \"nats\" to encode it :cite:`Shannon.1948`.\n",
|
|
"If you wonder what a \"nat\" is, it is the equivalent of bit\n",
|
|
"but when using a code with base $e$ rather than one with base 2.\n",
|
|
"Thus, one nat is $\\frac{1}{\\log(2)} \\approx 1.44$ bit.\n",
|
|
"\n",
|
|
"\n",
|
|
"### Surprisal\n",
|
|
"\n",
|
|
"You might be wondering what compression has to do with prediction.\n",
|
|
"Imagine that we have a stream of data that we want to compress.\n",
|
|
"If it is always easy for us to predict the next token,\n",
|
|
"then this data is easy to compress.\n",
|
|
"Take the extreme example where every token in the stream\n",
|
|
"always takes the same value.\n",
|
|
"That is a very boring data stream!\n",
|
|
"And not only it is boring, but it is also easy to predict.\n",
|
|
"Because the tokens are always the same,\n",
|
|
"we do not have to transmit any information\n",
|
|
"to communicate the contents of the stream.\n",
|
|
"Easy to predict, easy to compress.\n",
|
|
"\n",
|
|
"However if we cannot perfectly predict every event,\n",
|
|
"then we might sometimes be surprised.\n",
|
|
"Our surprise is greater when an event is assigned lower probability.\n",
|
|
"Claude Shannon settled on $\\log \\frac{1}{P(j)} = -\\log P(j)$\n",
|
|
"to quantify one's *surprisal* at observing an event $j$\n",
|
|
"having assigned it a (subjective) probability $P(j)$.\n",
|
|
"The entropy defined in :eqref:`eq_softmax_reg_entropy`\n",
|
|
"is then the *expected surprisal*\n",
|
|
"when one assigned the correct probabilities\n",
|
|
"that truly match the data-generating process.\n",
|
|
"\n",
|
|
"\n",
|
|
"### Cross-Entropy Revisited\n",
|
|
"\n",
|
|
"So if entropy is the level of surprise experienced\n",
|
|
"by someone who knows the true probability,\n",
|
|
"then you might be wondering, what is cross-entropy?\n",
|
|
"The cross-entropy *from* $P$ *to* $Q$, denoted $H(P, Q)$,\n",
|
|
"is the expected surprisal of an observer with subjective probabilities $Q$\n",
|
|
"upon seeing data that was actually generated according to probabilities $P$.\n",
|
|
"This is given by $H(P, Q) \\stackrel{\\textrm{def}}{=} \\sum_j - P(j) \\log Q(j)$.\n",
|
|
"The lowest possible cross-entropy is achieved when $P=Q$.\n",
|
|
"In this case, the cross-entropy from $P$ to $Q$ is $H(P, P)= H(P)$.\n",
|
|
"\n",
|
|
"In short, we can think of the cross-entropy classification objective\n",
|
|
"in two ways: (i) as maximizing the likelihood of the observed data;\n",
|
|
"and (ii) as minimizing our surprisal (and thus the number of bits)\n",
|
|
"required to communicate the labels.\n",
|
|
"\n",
|
|
"## Summary and Discussion\n",
|
|
"\n",
|
|
"In this section, we encountered the first nontrivial loss function,\n",
|
|
"allowing us to optimize over *discrete* output spaces.\n",
|
|
"Key in its design was that we took a probabilistic approach,\n",
|
|
"treating discrete categories as instances of draws from a probability distribution.\n",
|
|
"As a side effect, we encountered the softmax,\n",
|
|
"a convenient activation function that transforms\n",
|
|
"outputs of an ordinary neural network layer\n",
|
|
"into valid discrete probability distributions.\n",
|
|
"We saw that the derivative of the cross-entropy loss\n",
|
|
"when combined with softmax\n",
|
|
"behaves very similarly\n",
|
|
"to the derivative of squared error;\n",
|
|
"namely by taking the difference between\n",
|
|
"the expected behavior and its prediction.\n",
|
|
"And, while we were only able to\n",
|
|
"scratch the very surface of it,\n",
|
|
"we encountered exciting connections\n",
|
|
"to statistical physics and information theory.\n",
|
|
"\n",
|
|
"While this is enough to get you on your way,\n",
|
|
"and hopefully enough to whet your appetite,\n",
|
|
"we hardly dived deep here.\n",
|
|
"Among other things, we skipped over computational considerations.\n",
|
|
"Specifically, for any fully connected layer with $d$ inputs and $q$ outputs,\n",
|
|
"the parametrization and computational cost is $\\mathcal{O}(dq)$,\n",
|
|
"which can be prohibitively high in practice.\n",
|
|
"Fortunately, this cost of transforming $d$ inputs into $q$ outputs\n",
|
|
"can be reduced through approximation and compression.\n",
|
|
"For instance Deep Fried Convnets :cite:`Yang.Moczulski.Denil.ea.2015`\n",
|
|
"uses a combination of permutations,\n",
|
|
"Fourier transforms, and scaling\n",
|
|
"to reduce the cost from quadratic to log-linear.\n",
|
|
"Similar techniques work for more advanced\n",
|
|
"structural matrix approximations :cite:`sindhwani2015structured`.\n",
|
|
"Lastly, we can use quaternion-like decompositions\n",
|
|
"to reduce the cost to $\\mathcal{O}(\\frac{dq}{n})$,\n",
|
|
"again if we are willing to trade off a small amount of accuracy\n",
|
|
"for computational and storage cost :cite:`Zhang.Tay.Zhang.ea.2021`\n",
|
|
"based on a compression factor $n$.\n",
|
|
"This is an active area of research.\n",
|
|
"What makes it challenging is that\n",
|
|
"we do not necessarily strive\n",
|
|
"for the most compact representation\n",
|
|
"or the smallest number of floating point operations\n",
|
|
"but rather for the solution\n",
|
|
"that can be executed most efficiently on modern GPUs.\n",
|
|
"\n",
|
|
"## Exercises\n",
|
|
"\n",
|
|
"1. We can explore the connection between exponential families and softmax in some more depth.\n",
|
|
" 1. Compute the second derivative of the cross-entropy loss $l(\\mathbf{y},\\hat{\\mathbf{y}})$ for softmax.\n",
|
|
" 1. Compute the variance of the distribution given by $\\mathrm{softmax}(\\mathbf{o})$ and show that it matches the second derivative computed above.\n",
|
|
"1. Assume that we have three classes which occur with equal probability, i.e., the probability vector is $(\\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3})$.\n",
|
|
" 1. What is the problem if we try to design a binary code for it?\n",
|
|
" 1. Can you design a better code? Hint: what happens if we try to encode two independent observations? What if we encode $n$ observations jointly?\n",
|
|
"1. When encoding signals transmitted over a physical wire, engineers do not always use binary codes. For instance, [PAM-3](https://en.wikipedia.org/wiki/Ternary_signal) uses three signal levels $\\{-1, 0, 1\\}$ as opposed to two levels $\\{0, 1\\}$. How many ternary units do you need to transmit an integer in the range $\\{0, \\ldots, 7\\}$? Why might this be a better idea in terms of electronics?\n",
|
|
"1. The [Bradley--Terry model](https://en.wikipedia.org/wiki/Bradley%E2%80%93Terry_model) uses\n",
|
|
"a logistic model to capture preferences. For a user to choose between apples and oranges one\n",
|
|
"assumes scores $o_{\\textrm{apple}}$ and $o_{\\textrm{orange}}$. Our requirements are that larger scores should lead to a higher likelihood in choosing the associated item and that\n",
|
|
"the item with the largest score is the most likely one to be chosen :cite:`Bradley.Terry.1952`.\n",
|
|
" 1. Prove that softmax satisfies this requirement.\n",
|
|
" 1. What happens if you want to allow for a default option of choosing neither apples nor oranges? Hint: now the user has three choices.\n",
|
|
"1. Softmax gets its name from the following mapping: $\\textrm{RealSoftMax}(a, b) = \\log (\\exp(a) + \\exp(b))$.\n",
|
|
" 1. Prove that $\\textrm{RealSoftMax}(a, b) > \\mathrm{max}(a, b)$.\n",
|
|
" 1. How small can you make the difference between both functions? Hint: without loss of\n",
|
|
" generality you can set $b = 0$ and $a \\geq b$.\n",
|
|
" 1. Prove that this holds for $\\lambda^{-1} \\textrm{RealSoftMax}(\\lambda a, \\lambda b)$, provided that $\\lambda > 0$.\n",
|
|
" 1. Show that for $\\lambda \\to \\infty$ we have $\\lambda^{-1} \\textrm{RealSoftMax}(\\lambda a, \\lambda b) \\to \\mathrm{max}(a, b)$.\n",
|
|
" 1. Construct an analogous softmin function.\n",
|
|
" 1. Extend this to more than two numbers.\n",
|
|
"1. The function $g(\\mathbf{x}) \\stackrel{\\textrm{def}}{=} \\log \\sum_i \\exp x_i$ is sometimes also referred to as the [log-partition function](https://en.wikipedia.org/wiki/Partition_function_(mathematics)).\n",
|
|
" 1. Prove that the function is convex. Hint: to do so, use the fact that the first derivative amounts to the probabilities from the softmax function and show that the second derivative is the variance.\n",
|
|
" 1. Show that $g$ is translation invariant, i.e., $g(\\mathbf{x} + b) = g(\\mathbf{x})$.\n",
|
|
" 1. What happens if some of the coordinates $x_i$ are very large? What happens if they're all very small?\n",
|
|
" 1. Show that if we choose $b = \\mathrm{max}_i x_i$ we end up with a numerically stable implementation.\n",
|
|
"1. Assume that we have some probability distribution $P$. Suppose we pick another distribution $Q$ with $Q(i) \\propto P(i)^\\alpha$ for $\\alpha > 0$.\n",
|
|
" 1. Which choice of $\\alpha$ corresponds to doubling the temperature? Which choice corresponds to halving it?\n",
|
|
" 1. What happens if we let the temperature approach $0$?\n",
|
|
" 1. What happens if we let the temperature approach $\\infty$?\n",
|
|
"\n",
|
|
"[Discussions](https://discuss.d2l.ai/t/46)\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
},
|
|
"required_libs": []
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
} |