Ch05_Linear_Neural_Networks/Softmax_Regression.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Softmax Regression\n",
    "\n",
    "\n",
    "In the last two chapters, we worked through implementations\n",
    "linear regression, building everything from scratch and again using Gluon to automate the most repetitive work.\n",
    "\n",
    "Regression is the hammer we reach for\n",
    "when we want to answer *how much?* or *how many?* questions.\n",
    "If you want to predict the number of dollars (the *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're probably looking for a regression model.\n",
    "\n",
    "In practice, we're more often interested in classification:\n",
    "asking not *how much* but *which one*.\n",
    "\n",
    "* Does this email belong in the spam folder or the inbox?\n",
    "* Is this customer more likely *to sign up* 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 user most likely to watch next?\n",
    "\n",
    "Colloquially, we use the word *classification* to describe two subtly different problems: (i) those where we are interested only in *hard* assignments of examples to categories, and (ii) those where we wish to make *soft assignments*, i.e., to assess the *probability* that each category applies. One reason why the distinction between these tasks gets blurred is because most often, even when we only care about hard assignments, we still use models that make soft assignments.\n",
    "\n",
    "\n",
    "## Classification Problems\n",
    "\n",
    "To get our feet wet, let's start off with a somewhat contrived image classification problem. Here, each input will be a grayscale 2-by-2 image. We can represent each pixel location as a single scalar, representing each image with four features $x_1, x_2, x_3, x_4$. Further, let's assume that each image belongs to one among the categories \"cat\", \"chicken\" and \"dog\".\n",
    "\n",
    "First, we have to choose how to represent the labels. We have two obvious choices. Perhaps the most natural impulse would be to choose $y \\in \\{1, 2, 3\\}$, where the integers represent {dog, cat, chicken} respectively. This is a great way of *storing* such information on a computer.\n",
    "If the categories had some natural ordering among them, say if we were trying to predict {baby, child, adolescent, adult}, then it might even make sense to cast this problem as a regression and keep the labels in this format.\n",
    "\n",
    "But general classification problems do not come with natural orderings among the classes. To deal with problems like this, statisticians invented an alternative way to represent categorical data: the one hot encoding. Here we have a vector with one component for every possible category. For a given instance, we set the component corresponding to *its category* to 1, and set all other components to 0.\n",
    "\n",
    "$$y \\in \\{(1, 0, 0), (0, 1, 0), (0, 0, 1)\\}$$\n",
    "\n",
    "In our case, $y$ would be a three-dimensional vector, with $(1,0,0)$ corresponding to \"cat\", $(0,1,0)$ to \"chicken\" and $(0,0,1)$ to \"dog\".\n",
    "\n",
    "### Network Architecture\n",
    "\n",
    "In order to estimate multiple classes, we need a model with multiple outputs, one per category. This is one of the main differences between classification and regression models. To address classification with linear models, we will need as many linear functions as we have outputs. Each output will correspond to its own linear function. In our case, since we have 4 features and 3 possible output categories, we will need 12 scalars to represent the weights,  ($w$ with subscripts) and 3 scalars to represent the biases ($b$ with subscripts). We compute these three outputs, $o_1, o_2$, and $o_3$, for each input:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "o_1 &= x_1 w_{11} + x_2 w_{21} + x_3 w_{31} + x_4 w_{41} + b_1,\\\\\n",
    "o_2 &= x_1 w_{12} + x_2 w_{22} + x_3 w_{32} + x_4 w_{42} + b_2,\\\\\n",
    "o_3 &= x_1 w_{13} + x_2 w_{23} + x_3 w_{33} + x_4 w_{43} + b_3.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "We can depict this calculation with the neural network diagram below. Just as in linear regression, softmax regression is also a single-layer neural network. And since the calculation of each output, $o_1, o_2$, and $o_3$, depends on all inputs, $x_1$, $x_2$, $x_3$, and $x_4$, the output layer of softmax regression can also be described as fully connected layer.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg height=\"88pt\" version=\"1.1\" viewBox=\"0 0 263 88\" width=\"263pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol id=\"glyph0-0\" overflow=\"visible\">\n",
       "<path d=\"M 1.125 0 L 1.125 -5.625 L 5.625 -5.625 L 5.625 0 Z M 1.265625 -0.140625 L 5.484375 -0.140625 L 5.484375 -5.484375 L 1.265625 -5.484375 Z M 1.265625 -0.140625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-1\" overflow=\"visible\">\n",
       "<path d=\"M -0.015625 0 L 2.015625 -2.375 L 0.859375 -4.671875 L 1.734375 -4.671875 L 2.125 -3.84375 C 2.269531 -3.53125 2.398438 -3.226562 2.515625 -2.9375 L 3.875 -4.671875 L 4.84375 -4.671875 L 2.875 -2.3125 L 4.0625 0 L 3.171875 0 L 2.71875 -0.953125 C 2.613281 -1.148438 2.5 -1.398438 2.375 -1.703125 L 0.984375 0 Z M -0.015625 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-2\" overflow=\"visible\">\n",
       "<path d=\"M 0.4375 -1.765625 C 0.4375 -2.679688 0.707031 -3.4375 1.25 -4.03125 C 1.6875 -4.519531 2.265625 -4.765625 2.984375 -4.765625 C 3.546875 -4.765625 4 -4.585938 4.34375 -4.234375 C 4.6875 -3.890625 4.859375 -3.421875 4.859375 -2.828125 C 4.859375 -2.285156 4.75 -1.785156 4.53125 -1.328125 C 4.3125 -0.867188 4.003906 -0.515625 3.609375 -0.265625 C 3.210938 -0.015625 2.789062 0.109375 2.34375 0.109375 C 1.976562 0.109375 1.644531 0.03125 1.34375 -0.125 C 1.050781 -0.28125 0.828125 -0.5 0.671875 -0.78125 C 0.515625 -1.070312 0.4375 -1.398438 0.4375 -1.765625 Z M 1.234375 -1.84375 C 1.234375 -1.40625 1.335938 -1.070312 1.546875 -0.84375 C 1.765625 -0.625 2.035156 -0.515625 2.359375 -0.515625 C 2.523438 -0.515625 2.691406 -0.546875 2.859375 -0.609375 C 3.023438 -0.679688 3.179688 -0.785156 3.328125 -0.921875 C 3.472656 -1.066406 3.59375 -1.226562 3.6875 -1.40625 C 3.789062 -1.582031 3.875 -1.773438 3.9375 -1.984375 C 4.03125 -2.273438 4.078125 -2.554688 4.078125 -2.828125 C 4.078125 -3.242188 3.96875 -3.566406 3.75 -3.796875 C 3.539062 -4.035156 3.273438 -4.15625 2.953125 -4.15625 C 2.703125 -4.15625 2.472656 -4.09375 2.265625 -3.96875 C 2.066406 -3.851562 1.882812 -3.679688 1.71875 -3.453125 C 1.550781 -3.222656 1.425781 -2.957031 1.34375 -2.65625 C 1.269531 -2.351562 1.234375 -2.082031 1.234375 -1.84375 Z M 1.234375 -1.84375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-0\" overflow=\"visible\">\n",
       "<path d=\"M 0.875 0 L 0.875 -4.375 L 4.375 -4.375 L 4.375 0 Z M 0.984375 -0.109375 L 4.265625 -0.109375 L 4.265625 -4.265625 L 0.984375 -4.265625 Z M 0.984375 -0.109375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-1\" overflow=\"visible\">\n",
       "<path d=\"M 1.6875 0 L 2.484375 -3.78125 C 2.140625 -3.507812 1.65625 -3.296875 1.03125 -3.140625 L 1.15625 -3.703125 C 1.457031 -3.828125 1.757812 -3.988281 2.0625 -4.1875 C 2.363281 -4.382812 2.585938 -4.554688 2.734375 -4.703125 C 2.828125 -4.796875 2.914062 -4.90625 3 -5.03125 L 3.359375 -5.03125 L 2.3125 0 Z M 1.6875 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-2\" overflow=\"visible\">\n",
       "<path d=\"M 0.40625 0 C 0.46875 -0.300781 0.554688 -0.550781 0.671875 -0.75 C 0.785156 -0.945312 0.9375 -1.132812 1.125 -1.3125 C 1.3125 -1.5 1.671875 -1.804688 2.203125 -2.234375 C 2.523438 -2.492188 2.75 -2.6875 2.875 -2.8125 C 3.039062 -2.988281 3.160156 -3.160156 3.234375 -3.328125 C 3.285156 -3.441406 3.3125 -3.566406 3.3125 -3.703125 C 3.3125 -3.929688 3.226562 -4.125 3.0625 -4.28125 C 2.90625 -4.445312 2.707031 -4.53125 2.46875 -4.53125 C 2.238281 -4.53125 2.035156 -4.445312 1.859375 -4.28125 C 1.679688 -4.125 1.554688 -3.863281 1.484375 -3.5 L 0.875 -3.59375 C 0.9375 -4.039062 1.109375 -4.390625 1.390625 -4.640625 C 1.679688 -4.898438 2.039062 -5.03125 2.46875 -5.03125 C 2.75 -5.03125 3.003906 -4.96875 3.234375 -4.84375 C 3.460938 -4.726562 3.632812 -4.5625 3.75 -4.34375 C 3.875 -4.132812 3.9375 -3.914062 3.9375 -3.6875 C 3.9375 -3.351562 3.816406 -3.035156 3.578125 -2.734375 C 3.429688 -2.535156 3.003906 -2.15625 2.296875 -1.59375 C 1.984375 -1.351562 1.753906 -1.15625 1.609375 -1 C 1.460938 -0.84375 1.351562 -0.695312 1.28125 -0.5625 L 3.515625 -0.5625 L 3.390625 0 Z M 0.40625 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-3\" overflow=\"visible\">\n",
       "<path d=\"M 0.390625 -1.3125 L 0.984375 -1.390625 C 1.023438 -1.035156 1.125 -0.78125 1.28125 -0.625 C 1.4375 -0.476562 1.644531 -0.40625 1.90625 -0.40625 C 2.207031 -0.40625 2.46875 -0.515625 2.6875 -0.734375 C 2.914062 -0.953125 3.03125 -1.203125 3.03125 -1.484375 C 3.03125 -1.734375 2.945312 -1.9375 2.78125 -2.09375 C 2.613281 -2.257812 2.390625 -2.34375 2.109375 -2.34375 C 2.078125 -2.34375 2.007812 -2.335938 1.90625 -2.328125 L 2.015625 -2.84375 C 2.078125 -2.832031 2.132812 -2.828125 2.1875 -2.828125 C 2.539062 -2.828125 2.8125 -2.910156 3 -3.078125 C 3.1875 -3.253906 3.28125 -3.46875 3.28125 -3.71875 C 3.28125 -3.945312 3.203125 -4.140625 3.046875 -4.296875 C 2.890625 -4.453125 2.703125 -4.53125 2.484375 -4.53125 C 2.253906 -4.53125 2.050781 -4.445312 1.875 -4.28125 C 1.695312 -4.125 1.585938 -3.898438 1.546875 -3.609375 L 0.9375 -3.734375 C 1.03125 -4.148438 1.21875 -4.46875 1.5 -4.6875 C 1.789062 -4.914062 2.128906 -5.03125 2.515625 -5.03125 C 2.929688 -5.03125 3.265625 -4.90625 3.515625 -4.65625 C 3.773438 -4.40625 3.90625 -4.101562 3.90625 -3.75 C 3.90625 -3.476562 3.832031 -3.242188 3.6875 -3.046875 C 3.550781 -2.847656 3.347656 -2.6875 3.078125 -2.5625 C 3.265625 -2.445312 3.40625 -2.304688 3.5 -2.140625 C 3.601562 -1.972656 3.65625 -1.785156 3.65625 -1.578125 C 3.65625 -1.128906 3.488281 -0.738281 3.15625 -0.40625 C 2.820312 -0.0820312 2.421875 0.078125 1.953125 0.078125 C 1.492188 0.078125 1.125 -0.046875 0.84375 -0.296875 C 0.570312 -0.546875 0.421875 -0.882812 0.390625 -1.3125 Z M 0.390625 -1.3125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-4\" overflow=\"visible\">\n",
       "<path d=\"M 2.09375 0 L 2.359375 -1.28125 L 0.3125 -1.28125 L 0.453125 -1.890625 L 3.25 -5.015625 L 3.765625 -5.015625 L 3.09375 -1.828125 L 3.796875 -1.828125 L 3.6875 -1.28125 L 2.984375 -1.28125 L 2.703125 0 Z M 2.46875 -1.828125 L 2.90625 -3.921875 L 1.046875 -1.828125 Z M 2.46875 -1.828125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-0\" overflow=\"visible\">\n",
       "<path d=\"M 1.125 0 L 1.125 -5.625 L 5.625 -5.625 L 5.625 0 Z M 1.265625 -0.140625 L 5.484375 -0.140625 L 5.484375 -5.484375 L 1.265625 -5.484375 Z M 1.265625 -0.140625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-1\" overflow=\"visible\">\n",
       "<path d=\"M 0.84375 0 L 0.84375 -6.4375 L 1.6875 -6.4375 L 1.6875 0 Z M 0.84375 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-2\" overflow=\"visible\">\n",
       "<path d=\"M 0.59375 0 L 0.59375 -4.671875 L 1.3125 -4.671875 L 1.3125 -4 C 1.644531 -4.507812 2.140625 -4.765625 2.796875 -4.765625 C 3.078125 -4.765625 3.332031 -4.710938 3.5625 -4.609375 C 3.800781 -4.515625 3.976562 -4.382812 4.09375 -4.21875 C 4.207031 -4.0625 4.289062 -3.867188 4.34375 -3.640625 C 4.375 -3.492188 4.390625 -3.238281 4.390625 -2.875 L 4.390625 0 L 3.59375 0 L 3.59375 -2.84375 C 3.59375 -3.164062 3.5625 -3.40625 3.5 -3.5625 C 3.4375 -3.71875 3.328125 -3.84375 3.171875 -3.9375 C 3.015625 -4.039062 2.832031 -4.09375 2.625 -4.09375 C 2.289062 -4.09375 2 -3.984375 1.75 -3.765625 C 1.507812 -3.554688 1.390625 -3.148438 1.390625 -2.546875 L 1.390625 0 Z M 0.59375 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-3\" overflow=\"visible\">\n",
       "<path d=\"M 0.59375 1.78125 L 0.59375 -4.671875 L 1.3125 -4.671875 L 1.3125 -4.0625 C 1.476562 -4.300781 1.664062 -4.476562 1.875 -4.59375 C 2.09375 -4.707031 2.359375 -4.765625 2.671875 -4.765625 C 3.066406 -4.765625 3.414062 -4.660156 3.71875 -4.453125 C 4.019531 -4.253906 4.25 -3.96875 4.40625 -3.59375 C 4.5625 -3.21875 4.640625 -2.8125 4.640625 -2.375 C 4.640625 -1.894531 4.550781 -1.460938 4.375 -1.078125 C 4.207031 -0.691406 3.960938 -0.394531 3.640625 -0.1875 C 3.316406 0.0078125 2.972656 0.109375 2.609375 0.109375 C 2.347656 0.109375 2.113281 0.0507812 1.90625 -0.0625 C 1.695312 -0.175781 1.523438 -0.316406 1.390625 -0.484375 L 1.390625 1.78125 Z M 1.3125 -2.3125 C 1.3125 -1.707031 1.429688 -1.257812 1.671875 -0.96875 C 1.921875 -0.6875 2.21875 -0.546875 2.5625 -0.546875 C 2.90625 -0.546875 3.203125 -0.691406 3.453125 -0.984375 C 3.710938 -1.285156 3.84375 -1.75 3.84375 -2.375 C 3.84375 -2.96875 3.71875 -3.410156 3.46875 -3.703125 C 3.226562 -4.003906 2.9375 -4.15625 2.59375 -4.15625 C 2.257812 -4.15625 1.960938 -3.992188 1.703125 -3.671875 C 1.441406 -3.359375 1.3125 -2.90625 1.3125 -2.3125 Z M 1.3125 -2.3125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-4\" overflow=\"visible\">\n",
       "<path d=\"M 3.65625 0 L 3.65625 -0.6875 C 3.289062 -0.15625 2.796875 0.109375 2.171875 0.109375 C 1.898438 0.109375 1.644531 0.0546875 1.40625 -0.046875 C 1.164062 -0.160156 0.984375 -0.296875 0.859375 -0.453125 C 0.742188 -0.609375 0.664062 -0.800781 0.625 -1.03125 C 0.59375 -1.1875 0.578125 -1.4375 0.578125 -1.78125 L 0.578125 -4.671875 L 1.359375 -4.671875 L 1.359375 -2.078125 C 1.359375 -1.660156 1.378906 -1.382812 1.421875 -1.25 C 1.460938 -1.039062 1.5625 -0.875 1.71875 -0.75 C 1.882812 -0.632812 2.085938 -0.578125 2.328125 -0.578125 C 2.566406 -0.578125 2.789062 -0.632812 3 -0.75 C 3.207031 -0.875 3.351562 -1.039062 3.4375 -1.25 C 3.519531 -1.457031 3.5625 -1.765625 3.5625 -2.171875 L 3.5625 -4.671875 L 4.359375 -4.671875 L 4.359375 0 Z M 3.65625 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-5\" overflow=\"visible\">\n",
       "<path d=\"M 2.328125 -0.703125 L 2.4375 -0.015625 C 2.207031 0.0351562 2.007812 0.0625 1.84375 0.0625 C 1.550781 0.0625 1.328125 0.015625 1.171875 -0.078125 C 1.015625 -0.171875 0.898438 -0.289062 0.828125 -0.4375 C 0.765625 -0.582031 0.734375 -0.890625 0.734375 -1.359375 L 0.734375 -4.046875 L 0.15625 -4.046875 L 0.15625 -4.671875 L 0.734375 -4.671875 L 0.734375 -5.828125 L 1.53125 -6.296875 L 1.53125 -4.671875 L 2.328125 -4.671875 L 2.328125 -4.046875 L 1.53125 -4.046875 L 1.53125 -1.328125 C 1.53125 -1.097656 1.539062 -0.953125 1.5625 -0.890625 C 1.59375 -0.828125 1.640625 -0.773438 1.703125 -0.734375 C 1.765625 -0.691406 1.851562 -0.671875 1.96875 -0.671875 C 2.0625 -0.671875 2.179688 -0.679688 2.328125 -0.703125 Z M 2.328125 -0.703125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-6\" overflow=\"visible\">\n",
       "<path d=\"\" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-7\" overflow=\"visible\">\n",
       "<path d=\"M 0.578125 0 L 0.578125 -6.4375 L 1.359375 -6.4375 L 1.359375 0 Z M 0.578125 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-8\" overflow=\"visible\">\n",
       "<path d=\"M 3.640625 -0.578125 C 3.347656 -0.328125 3.066406 -0.148438 2.796875 -0.046875 C 2.523438 0.0546875 2.234375 0.109375 1.921875 0.109375 C 1.410156 0.109375 1.015625 -0.015625 0.734375 -0.265625 C 0.460938 -0.515625 0.328125 -0.835938 0.328125 -1.234375 C 0.328125 -1.460938 0.378906 -1.671875 0.484375 -1.859375 C 0.585938 -2.046875 0.722656 -2.195312 0.890625 -2.3125 C 1.054688 -2.425781 1.242188 -2.515625 1.453125 -2.578125 C 1.609375 -2.609375 1.84375 -2.644531 2.15625 -2.6875 C 2.800781 -2.757812 3.273438 -2.851562 3.578125 -2.96875 C 3.578125 -3.070312 3.578125 -3.140625 3.578125 -3.171875 C 3.578125 -3.492188 3.503906 -3.71875 3.359375 -3.84375 C 3.148438 -4.03125 2.847656 -4.125 2.453125 -4.125 C 2.078125 -4.125 1.800781 -4.054688 1.625 -3.921875 C 1.445312 -3.796875 1.316406 -3.566406 1.234375 -3.234375 L 0.46875 -3.328125 C 0.53125 -3.660156 0.640625 -3.925781 0.796875 -4.125 C 0.960938 -4.332031 1.195312 -4.488281 1.5 -4.59375 C 1.8125 -4.707031 2.164062 -4.765625 2.5625 -4.765625 C 2.96875 -4.765625 3.289062 -4.71875 3.53125 -4.625 C 3.78125 -4.53125 3.960938 -4.410156 4.078125 -4.265625 C 4.203125 -4.128906 4.285156 -3.953125 4.328125 -3.734375 C 4.359375 -3.597656 4.375 -3.359375 4.375 -3.015625 L 4.375 -1.953125 C 4.375 -1.222656 4.390625 -0.757812 4.421875 -0.5625 C 4.453125 -0.363281 4.519531 -0.175781 4.625 0 L 3.796875 0 C 3.710938 -0.164062 3.660156 -0.359375 3.640625 -0.578125 Z M 3.578125 -2.34375 C 3.285156 -2.226562 2.851562 -2.128906 2.28125 -2.046875 C 1.957031 -1.992188 1.726562 -1.9375 1.59375 -1.875 C 1.457031 -1.820312 1.351562 -1.738281 1.28125 -1.625 C 1.207031 -1.507812 1.171875 -1.382812 1.171875 -1.25 C 1.171875 -1.039062 1.25 -0.863281 1.40625 -0.71875 C 1.5625 -0.582031 1.796875 -0.515625 2.109375 -0.515625 C 2.410156 -0.515625 2.679688 -0.582031 2.921875 -0.71875 C 3.160156 -0.851562 3.335938 -1.035156 3.453125 -1.265625 C 3.535156 -1.441406 3.578125 -1.703125 3.578125 -2.046875 Z M 3.578125 -2.34375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-9\" overflow=\"visible\">\n",
       "<path d=\"M 0.5625 1.796875 L 0.46875 1.0625 C 0.644531 1.101562 0.796875 1.125 0.921875 1.125 C 1.097656 1.125 1.238281 1.09375 1.34375 1.03125 C 1.445312 0.976562 1.535156 0.898438 1.609375 0.796875 C 1.648438 0.710938 1.726562 0.515625 1.84375 0.203125 C 1.863281 0.160156 1.890625 0.0976562 1.921875 0.015625 L 0.140625 -4.671875 L 1 -4.671875 L 1.96875 -1.96875 C 2.09375 -1.625 2.207031 -1.265625 2.3125 -0.890625 C 2.394531 -1.242188 2.5 -1.597656 2.625 -1.953125 L 3.625 -4.671875 L 4.421875 -4.671875 L 2.640625 0.078125 C 2.453125 0.585938 2.304688 0.941406 2.203125 1.140625 C 2.054688 1.398438 1.894531 1.585938 1.71875 1.703125 C 1.539062 1.828125 1.320312 1.890625 1.0625 1.890625 C 0.914062 1.890625 0.75 1.859375 0.5625 1.796875 Z M 0.5625 1.796875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-10\" overflow=\"visible\">\n",
       "<path d=\"M 3.78125 -1.5 L 4.609375 -1.40625 C 4.472656 -0.925781 4.226562 -0.550781 3.875 -0.28125 C 3.53125 -0.0195312 3.085938 0.109375 2.546875 0.109375 C 1.867188 0.109375 1.328125 -0.0976562 0.921875 -0.515625 C 0.523438 -0.941406 0.328125 -1.535156 0.328125 -2.296875 C 0.328125 -3.078125 0.53125 -3.679688 0.9375 -4.109375 C 1.34375 -4.546875 1.867188 -4.765625 2.515625 -4.765625 C 3.140625 -4.765625 3.644531 -4.550781 4.03125 -4.125 C 4.425781 -3.707031 4.625 -3.113281 4.625 -2.34375 C 4.625 -2.289062 4.625 -2.21875 4.625 -2.125 L 1.140625 -2.125 C 1.171875 -1.613281 1.316406 -1.222656 1.578125 -0.953125 C 1.835938 -0.679688 2.164062 -0.546875 2.5625 -0.546875 C 2.851562 -0.546875 3.097656 -0.617188 3.296875 -0.765625 C 3.503906 -0.921875 3.664062 -1.164062 3.78125 -1.5 Z M 1.1875 -2.78125 L 3.796875 -2.78125 C 3.765625 -3.175781 3.664062 -3.472656 3.5 -3.671875 C 3.25 -3.972656 2.921875 -4.125 2.515625 -4.125 C 2.148438 -4.125 1.84375 -4 1.59375 -3.75 C 1.351562 -3.507812 1.21875 -3.1875 1.1875 -2.78125 Z M 1.1875 -2.78125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-11\" overflow=\"visible\">\n",
       "<path d=\"M 0.578125 0 L 0.578125 -4.671875 L 1.296875 -4.671875 L 1.296875 -3.953125 C 1.472656 -4.285156 1.640625 -4.503906 1.796875 -4.609375 C 1.953125 -4.710938 2.125 -4.765625 2.3125 -4.765625 C 2.570312 -4.765625 2.84375 -4.679688 3.125 -4.515625 L 2.84375 -3.78125 C 2.65625 -3.894531 2.460938 -3.953125 2.265625 -3.953125 C 2.097656 -3.953125 1.941406 -3.898438 1.796875 -3.796875 C 1.660156 -3.691406 1.5625 -3.546875 1.5 -3.359375 C 1.414062 -3.078125 1.375 -2.769531 1.375 -2.4375 L 1.375 0 Z M 0.578125 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph2-12\" overflow=\"visible\">\n",
       "<path d=\"M 0.4375 -3.140625 C 0.4375 -4.203125 0.722656 -5.035156 1.296875 -5.640625 C 1.867188 -6.253906 2.609375 -6.5625 3.515625 -6.5625 C 4.109375 -6.5625 4.644531 -6.414062 5.125 -6.125 C 5.601562 -5.84375 5.96875 -5.445312 6.21875 -4.9375 C 6.46875 -4.425781 6.59375 -3.851562 6.59375 -3.21875 C 6.59375 -2.5625 6.460938 -1.972656 6.203125 -1.453125 C 5.941406 -0.941406 5.566406 -0.550781 5.078125 -0.28125 C 4.597656 -0.0195312 4.078125 0.109375 3.515625 0.109375 C 2.910156 0.109375 2.367188 -0.0351562 1.890625 -0.328125 C 1.410156 -0.617188 1.046875 -1.019531 0.796875 -1.53125 C 0.554688 -2.039062 0.4375 -2.578125 0.4375 -3.140625 Z M 1.3125 -3.125 C 1.3125 -2.34375 1.519531 -1.726562 1.9375 -1.28125 C 2.351562 -0.84375 2.878906 -0.625 3.515625 -0.625 C 4.148438 -0.625 4.675781 -0.847656 5.09375 -1.296875 C 5.507812 -1.742188 5.71875 -2.382812 5.71875 -3.21875 C 5.71875 -3.738281 5.628906 -4.191406 5.453125 -4.578125 C 5.273438 -4.972656 5.015625 -5.28125 4.671875 -5.5 C 4.328125 -5.71875 3.945312 -5.828125 3.53125 -5.828125 C 2.925781 -5.828125 2.40625 -5.617188 1.96875 -5.203125 C 1.53125 -4.785156 1.3125 -4.09375 1.3125 -3.125 Z M 1.3125 -3.125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<path d=\"M 107.015625 77.734375 C 111.996094 82.714844 111.996094 90.785156 107.015625 95.765625 C 102.035156 100.746094 93.964844 100.746094 88.984375 95.765625 C 84.003906 90.785156 84.003906 82.714844 88.984375 77.734375 C 93.964844 72.753906 102.035156 72.753906 107.015625 77.734375 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"86.803467\" xlink:href=\"#glyph0-1\" y=\"77.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"91.303467\" xlink:href=\"#glyph1-1\" y=\"79.135498\"/>\n",
       "</g>\n",
       "<path d=\"M 159.890625 77.734375 C 164.871094 82.714844 164.871094 90.785156 159.890625 95.765625 C 154.910156 100.746094 146.839844 100.746094 141.859375 95.765625 C 136.878906 90.785156 136.878906 82.714844 141.859375 77.734375 C 146.839844 72.753906 154.910156 72.753906 159.890625 77.734375 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"139.678467\" xlink:href=\"#glyph0-1\" y=\"77.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"144.178467\" xlink:href=\"#glyph1-2\" y=\"79.135498\"/>\n",
       "</g>\n",
       "<path d=\"M 140.015625 16.734375 C 144.996094 21.714844 144.996094 29.785156 140.015625 34.765625 C 135.035156 39.746094 126.964844 39.746094 121.984375 34.765625 C 117.003906 29.785156 117.003906 21.714844 121.984375 16.734375 C 126.964844 11.753906 135.035156 11.753906 140.015625 16.734375 \" style=\"fill-rule:nonzero;fill:rgb(39.99939%,74.900818%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"119.550781\" xlink:href=\"#glyph0-2\" y=\"16.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"124.556152\" xlink:href=\"#glyph1-1\" y=\"18.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"8.98755\" xlink:href=\"#glyph2-1\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"11.48775\" xlink:href=\"#glyph2-2\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"16.49355\" xlink:href=\"#glyph2-3\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"21.49935\" xlink:href=\"#glyph2-4\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"26.50515\" xlink:href=\"#glyph2-5\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"29.00535\" xlink:href=\"#glyph2-6\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"31.50555\" xlink:href=\"#glyph2-7\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"33.50535\" xlink:href=\"#glyph2-8\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"38.51115\" xlink:href=\"#glyph2-9\" y=\"76.852783\"/>\n",
       "  <use x=\"43.01115\" xlink:href=\"#glyph2-10\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"48.01695\" xlink:href=\"#glyph2-11\" y=\"76.852783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"5.4873\" xlink:href=\"#glyph2-12\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"12.4875\" xlink:href=\"#glyph2-4\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"17.4933\" xlink:href=\"#glyph2-5\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"19.9935\" xlink:href=\"#glyph2-3\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"24.9993\" xlink:href=\"#glyph2-4\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"30.0051\" xlink:href=\"#glyph2-5\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"32.5053\" xlink:href=\"#glyph2-6\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"35.0055\" xlink:href=\"#glyph2-7\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"37.0053\" xlink:href=\"#glyph2-8\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"42.0111\" xlink:href=\"#glyph2-9\" y=\"16.602783\"/>\n",
       "  <use x=\"46.5111\" xlink:href=\"#glyph2-10\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"51.5169\" xlink:href=\"#glyph2-11\" y=\"16.602783\"/>\n",
       "</g>\n",
       "<path d=\"M 212.765625 77.734375 C 217.746094 82.714844 217.746094 90.785156 212.765625 95.765625 C 207.785156 100.746094 199.714844 100.746094 194.734375 95.765625 C 189.753906 90.785156 189.753906 82.714844 194.734375 77.734375 C 199.714844 72.753906 207.785156 72.753906 212.765625 77.734375 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"192.553467\" xlink:href=\"#glyph0-1\" y=\"77.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"197.053467\" xlink:href=\"#glyph1-3\" y=\"79.135498\"/>\n",
       "</g>\n",
       "<path d=\"M 265.640625 76.984375 C 270.621094 81.964844 270.621094 90.035156 265.640625 95.015625 C 260.660156 99.996094 252.589844 99.996094 247.609375 95.015625 C 242.628906 90.035156 242.628906 81.964844 247.609375 76.984375 C 252.589844 72.003906 260.660156 72.003906 265.640625 76.984375 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"245.428467\" xlink:href=\"#glyph0-1\" y=\"76.385498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"249.928467\" xlink:href=\"#glyph1-4\" y=\"78.385498\"/>\n",
       "</g>\n",
       "<path d=\"M 231.265625 16.734375 C 236.246094 21.714844 236.246094 29.785156 231.265625 34.765625 C 226.285156 39.746094 218.214844 39.746094 213.234375 34.765625 C 208.253906 29.785156 208.253906 21.714844 213.234375 16.734375 C 218.214844 11.753906 226.285156 11.753906 231.265625 16.734375 \" style=\"fill-rule:nonzero;fill:rgb(39.99939%,74.900818%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"210.800781\" xlink:href=\"#glyph0-2\" y=\"16.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"215.806152\" xlink:href=\"#glyph1-3\" y=\"18.135498\"/>\n",
       "</g>\n",
       "<path d=\"M 185.640625 16.734375 C 190.621094 21.714844 190.621094 29.785156 185.640625 34.765625 C 180.660156 39.746094 172.589844 39.746094 167.609375 34.765625 C 162.628906 29.785156 162.628906 21.714844 167.609375 16.734375 C 172.589844 11.753906 180.660156 11.753906 185.640625 16.734375 \" style=\"fill-rule:nonzero;fill:rgb(39.99939%,74.900818%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"165.175781\" xlink:href=\"#glyph0-2\" y=\"16.135498\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"170.181152\" xlink:href=\"#glyph1-2\" y=\"18.135498\"/>\n",
       "</g>\n",
       "<path d=\"M 104.066406 75.53125 L 122.125 42.15625 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 124.027344 38.636719 L 122.125 42.15625 M 120.804688 41.441406 L 124.027344 38.636719 L 123.445312 42.871094 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 108.074219 78.933594 L 161.890625 37.183594 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 165.050781 34.730469 L 161.890625 37.183594 M 160.96875 35.996094 L 165.050781 34.730469 L 162.808594 38.367188 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 109.449219 81.128906 L 205.503906 33.96875 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 209.097656 32.207031 L 205.503906 33.96875 M 204.84375 32.625 L 209.097656 32.207031 L 206.167969 35.316406 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 146.925781 74.625 L 136.777344 43.484375 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 135.539062 39.683594 L 136.777344 43.484375 M 135.351562 43.949219 L 135.539062 39.683594 L 138.203125 43.019531 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 155.835938 75 L 169.371094 42.933594 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 170.925781 39.25 L 169.371094 42.933594 M 167.988281 42.351562 L 170.925781 39.25 L 170.753906 43.519531 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 160.566406 78.464844 L 208.070312 37.867188 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 211.113281 35.269531 L 208.070312 37.867188 M 207.097656 36.726562 L 211.113281 35.269531 L 209.046875 39.007812 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 193.980469 78.558594 L 145.292969 37.734375 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 142.226562 35.164062 L 145.292969 37.734375 M 144.328125 38.882812 L 142.226562 35.164062 L 146.253906 36.582031 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 198.566406 75.097656 L 184.203125 42.792969 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 182.578125 39.140625 L 184.203125 42.792969 M 182.832031 43.402344 L 182.578125 39.140625 L 185.574219 42.183594 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 207.449219 74.546875 L 216.835938 43.601562 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 217.996094 39.773438 L 216.835938 43.601562 M 215.402344 43.164062 L 217.996094 39.773438 L 218.273438 44.035156 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 245.125 80.484375 L 147.820312 33.816406 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 144.210938 32.085938 L 147.820312 33.816406 M 147.171875 35.167969 L 144.210938 32.085938 L 148.46875 32.464844 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 246.4375 78.328125 L 191.523438 36.972656 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 188.328125 34.5625 L 191.523438 36.972656 M 190.621094 38.167969 L 188.328125 34.5625 L 192.425781 35.773438 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 250.304688 74.921875 L 231.492188 41.953125 \" style=\"fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "<path d=\"M 229.511719 38.476562 L 231.492188 41.953125 M 230.191406 42.695312 L 229.511719 38.476562 L 232.796875 41.207031 \" style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-7,-12)\"/>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import SVG\n",
    "SVG(filename='../img/softmaxreg.svg')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Softmax regression is a single-layer neural network.  \n",
    "\n",
    "\n",
    "### Softmax Operation\n",
    "\n",
    "To express the model more compactly, we can use linear algebra notation. In vector form, we arrive at $\\mathbf{o} = \\mathbf{W} \\mathbf{x} + \\mathbf{b}$, a form better suited both for mathematics, and for writing code. Note that we have gathered all of our weights into a $3\\times4$ matrix and that for a given example $\\mathbf{x}$ our outputs are given by a matrix vector product of our weights by our inputs plus our biases $\\mathbf{b}$.\n",
    "\n",
    "\n",
    "If we are interested in hard classifications, we need to convert these outputs into a discrete prediction. One straightforward way to do this is to treat the output values $o_i$ as the relative confidence levels that the item belongs to each category $i$. Then we can choose the class with the largest output value as our prediction $\\operatorname*{argmax}_i o_i$. For example, if $o_1$, $o_2$, and $o_3$ are 0.1, 10, and 0.1, respectively, then we predict category 2, which represents \"chicken\".\n",
    "\n",
    "However, there are a few problems with using the output from the output layer directly. First, because the range of output values from the output layer is uncertain, it is difficult to judge the meaning of these values. For instance, the output value 10 from the previous example appears to indicate that we are *very confident* that the image category is *chicken*. But just how confident? Is it 100 times more likely to be a chicken than a dog or are we less confident?\n",
    "\n",
    "Moreover how do we train this model. If the argmax matches the label, then we have no error at all! And if if the argmax is not equal to the label, then no infinitesimal change in our weights will decrease our error. That takes gradient-based learning off the table.\n",
    "\n",
    "We might like for our outputs to correspond to probabilities, but then we would need a way to guarantee that on new (unseen) data the probabilities would be nonnegative and sum up to 1. Moreover, we would need a training objective that encouraged the model to actually estimate *probabilities*.\n",
    "Fortunately, statisticians have conveniently invented a model\n",
    "called softmax logistic regression that does precisely this.\n",
    "\n",
    "In order to ensure that our outputs are nonnegative and sum to 1,\n",
    "while requiring that our model remains differentiable,\n",
    "we subject the outputs of the linear portion of our model\n",
    "to a nonlinear *softmax* function:\n",
    "\n",
    "$$\n",
    "\\hat{\\mathbf{y}} = \\mathrm{softmax}(\\mathbf{o}) \\text{ where }\n",
    "\\hat{y}_i = \\frac{\\exp(o_i)}{\\sum_j \\exp(o_j)}\n",
    "$$\n",
    "\n",
    "It is easy to see $\\hat{y}_1 + \\hat{y}_2 + \\hat{y}_3 = 1$ with $0 \\leq \\hat{y}_i \\leq 1$ for all $i$. Thus, $\\hat{y}$ is a proper probability distribution and the values of $o$ now assume an easily quantifiable meaning. Note that we can still find the most likely class by\n",
    "\n",
    "$$\n",
    "\\hat{\\imath}(\\mathbf{o}) = \\operatorname*{argmax}_i o_i = \\operatorname*{argmax}_i \\hat y_i\n",
    "$$\n",
    "\n",
    "In short, the softmax operation preserves the orderings of its inputs, and thus does not alter the predicted category vs our simpler *argmax* model. However, it gives the outputs $\\mathbf{o}$ proper meaning: they are the pre-softmax values determining the probabilities assigned to each category. Summarizing it all in vector notation we get ${\\mathbf{o}}^{(i)} = \\mathbf{W} {\\mathbf{x}}^{(i)} + {\\mathbf{b}}$ where ${\\hat{\\mathbf{y}}}^{(i)} = \\mathrm{softmax}({\\mathbf{o}}^{(i)})$.\n",
    "\n",
    "\n",
    "### Vectorization for Minibatches\n",
    "\n",
    "Again, to improve computational efficiency and take advantage of GPUs, we will typically carry out vector calculations for mini-batches of data. Assume that we are given a mini-batch $\\mathbf{X}$ of examples with dimensionality $d$ and batch size $n$. Moreover, assume that we have $q$ categories (outputs). Then the minibatch features $\\mathbf{X}$ are in $\\mathbb{R}^{n \\times d}$, weights $\\mathbf{W} \\in \\mathbb{R}^{d \\times q}$ and the bias satisfies $\\mathbf{b} \\in \\mathbb{R}^q$.\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbf{O} &= \\mathbf{X} \\mathbf{W} + \\mathbf{b} \\\\\n",
    "\\hat{\\mathbf{Y}} & = \\mathrm{softmax}(\\mathbf{O})\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "This accelerates the dominant operation into a matrix-matrix product $\\mathbf{W} \\mathbf{X}$ vs the matrix-vector products we would be executing if we processed one example at a time. The softmax itself can be computed by exponentiating all entries in $\\mathbf{O}$ and then normalizing them by the sum appropriately.\n",
    "\n",
    "## Loss Function\n",
    "\n",
    "Now that we have some mechanism for outputting probabilities, we need to transform this into a measure of how accurate things are, i.e. we need a *loss function*. For this, we use the same concept that we already encountered in linear regression, namely likelihood maximization.\n",
    "\n",
    "### Log-Likelihood\n",
    "\n",
    "The softmax function maps $\\mathbf{o}$ into a vector of probabilities corresponding to various outcomes, such as $p(y=\\mathrm{cat}|\\mathbf{x})$. This allows us to compare the estimates with reality, simply by checking how well it predicted what we observe.\n",
    "\n",
    "$$\n",
    "p(Y|X) = \\prod_{i=1}^n p(y^{(i)}|x^{(i)})\n",
    "\\text{ and thus }\n",
    "-\\log p(Y|X) = \\sum_{i=1}^n -\\log p(y^{(i)}|x^{(i)})\n",
    "$$\n",
    "\n",
    "\n",
    "Maximizing $p(Y|X)$ (and thus equivalently minimizing $-\\log p(Y|X)$)\n",
    "corresponds to predicting the label well.\n",
    "This yields the loss function (we dropped the superscript $(i)$ to avoid notation clutter):\n",
    "\n",
    "$$\n",
    "l = -\\log p(y|x) = - \\sum_j y_j \\log \\hat{y}_j\n",
    "$$\n",
    "\n",
    "Here we used that by construction $\\hat{y} = \\mathrm{softmax}(\\mathbf{o})$ and moreover, that the vector $\\mathbf{y}$ consists of all zeroes but for the correct label, such as $(1, 0, 0)$. Hence the sum over all coordinates $j$ vanishes for all but one term. Since all $\\hat{y}_j$ are probabilities, their logarithm is never larger than $0$. Consequently, the loss function is minimized if we correctly predict $y$ with *certainty*, i.e. if $p(y|x) = 1$ for the correct label.\n",
    "\n",
    "### Softmax and Derivatives\n",
    "\n",
    "Since the Softmax and the corresponding loss are so common, it is worth while understanding a bit better how it is computed. Plugging $o$ into the definition of the loss $l$ and using the definition of the softmax we obtain:\n",
    "\n",
    "$$\n",
    "l = -\\sum_j y_j \\log \\hat{y}_j = \\sum_j y_j \\log \\sum_k \\exp(o_k) - \\sum_j y_j o_j\n",
    "= \\log \\sum_k \\exp(o_k) - \\sum_j y_j o_j\n",
    "$$\n",
    "\n",
    "To understand a bit better what is going on, consider the derivative with respect to $o$. We get\n",
    "\n",
    "$$\n",
    "\\partial_{o_j} l = \\frac{\\exp(o_j)}{\\sum_k \\exp(o_k)} - y_j = \\mathrm{softmax}(\\mathbf{o})_j - y_j = \\Pr(y = j|x) - y_j\n",
    "$$\n",
    "\n",
    "In other words, the gradient is the difference between the probability assigned to the true class by our model, as expressed by the probability $p(y|x)$, and what actually happened, as expressed by $y$. In this sense, it is very similar to what we saw in regression, where the gradient was the difference between the observation $y$ and estimate $\\hat{y}$. This is not coincidence. In any [exponential family](https://en.wikipedia.org/wiki/Exponential_family) model, the gradients of the log-likelihood are given by precisely this term. This fact makes computing gradients easy in practice.\n",
    "\n",
    "### Cross-Entropy Loss\n",
    "\n",
    "Now consider the case where we don't just observe a single outcome but maybe, an entire distribution over outcomes. We can use the same representation as before for $y$. The only difference is that rather than a vector containing only binary entries, say $(0, 0, 1)$, we now have a generic probability vector, say $(0.1, 0.2, 0.7)$. The math that we used previously to define the loss $l$ still works out fine, just that the interpretation is slightly more general. It is the expected value of the loss for a distribution over labels.\n",
    "\n",
    "$$\n",
    "l(\\mathbf{y}, \\hat{\\mathbf{y}}) = - \\sum_j y_j \\log \\hat{y}_j\n",
    "$$\n",
    "\n",
    "This loss is called the cross-entropy loss and it is one of the most commonly used losses for multiclass classification. To demystify its name we need some information theory. The following section can be skipped if needed.\n",
    "\n",
    "## Information Theory Basics\n",
    "\n",
    "Information theory deals with the problem of encoding, decoding, transmitting and manipulating information (aka data), preferentially in as concise form as possible.\n",
    "\n",
    "### Entropy\n",
    "\n",
    "A key concept is how many bits of information (or randomness) are contained in data. It can be measured as the [entropy](https://en.wikipedia.org/wiki/Entropy) of a distribution $p$ via\n",
    "\n",
    "$$\n",
    "H[p] = \\sum_j - p(j) \\log p(j)\n",
    "$$\n",
    "\n",
    "One of the fundamental theorems of information theory states that in order to encode data drawn randomly from the distribution $p$ we need at least $H[p]$ 'nats' to encode it. If you wonder what a 'nat' is, it is the equivalent of bit but when using a code with base $e$ rather than one with base 2. One nat is $\\frac{1}{\\log(2)} \\approx 1.44$ bit. $H[p] / \\log 2$ is often also called the binary entropy.\n",
    "\n",
    "To make this all a bit more theoretical consider the following: $p(1) = \\frac{1}{2}$ whereas $p(2) = p(3) = \\frac{1}{4}$. In this case we can easily design an optimal code for data drawn from this distribution, by using `0` to encode 1, `10` for 2 and `11` for 3. The expected number of bit is $1.5 = 0.5 * 1 + 0.25 * 2 + 0.25 * 2$. It is easy to check that this is the same as the binary entropy $H[p] / \\log 2$.\n",
    "\n",
    "### Kullback Leibler Divergence\n",
    "\n",
    "One way of measuring the difference between two distributions arises directly from the entropy. Since $H[p]$ is the minimum number of bits that we need to encode data drawn from $p$, we could ask how well it is encoded if we pick the 'wrong' distribution $q$. The amount of extra bits that we need to encode $q$ gives us some idea of how different these two distributions are. Let us compute this directly - recall that to encode $j$ using an optimal code for $q$ would cost $-\\log q(j)$ nats, and we need to use this in $p(j)$ of all cases. Hence we have\n",
    "\n",
    "$$\n",
    "D(p\\|q) = -\\sum_j p(j) \\log q(j) - H[p] = \\sum_j p(j) \\log \\frac{p(j)}{q(j)}\n",
    "$$\n",
    "\n",
    "Note that minimizing $D(p\\|q)$ with respect to $q$ is equivalent to minimizing the cross-entropy loss. This can be seen directly by dropping $H[p]$ which doesn't depend on $q$. We thus showed that softmax regression tries the minimize the surprise (and thus the number of bits) we experience when seeing the true label $y$ rather than our prediction $\\hat{y}$.\n",
    "\n",
    "## Model Prediction and Evaluation\n",
    "\n",
    "After training the softmax regression model, given any example features, we can predict the probability of each output category. Normally, we use the category with the highest predicted probability as the output category. The prediction is correct if it is consistent with the actual category (label). In the next part of the experiment, we will use accuracy to evaluate the model’s performance. This is equal to the ratio between the number of correct predictions and the total number of predictions.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* We introduced the softmax operation which takes a vector maps it into probabilities.\n",
    "* Softmax regression applies to classification problems. It uses the probability distribution of the output category in the softmax operation.\n",
    "* Cross entropy is a good measure of the difference between two probability distributions. It measures the number of bits needed to encode the data given our model.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Show that the Kullback-Leibler divergence $D(p\\|q)$ is nonnegative for all distributions $p$ and $q$. Hint - use Jensen's inequality, i.e. use the fact that $-\\log x$ is a convex function.\n",
    "1. Show that $\\log \\sum_j \\exp(o_j)$ is a convex function in $o$.\n",
    "1. We can explore the connection between exponential families and the softmax in some more depth\n",
    "    * Compute the second derivative of the cross entropy loss $l(y,\\hat{y})$ for the softmax.\n",
    "    * Compute the variance of the distribution given by $\\mathrm{softmax}(o)$ and show that it matches the second derivative computed above.\n",
    "1. Assume that we three classes which occur with equal probability, i.e. the probability vector is $(\\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3})$.\n",
    "    * What is the problem if we try to design a binary code for it? Can we match the entropy lower bound on the number of bits?\n",
    "    * 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. Softmax is a misnomer for the mapping introduced above (but everyone in deep learning uses it). The real softmax is defined as $\\mathrm{RealSoftMax}(a,b) = \\log (\\exp(a) + \\exp(b))$.\n",
    "    * Prove that $\\mathrm{RealSoftMax}(a,b) > \\mathrm{max}(a,b)$.\n",
    "    * Prove that this holds for $\\lambda^{-1} \\mathrm{RealSoftMax}(\\lambda a, \\lambda b)$, provided that $\\lambda > 0$.\n",
    "    * Show that for $\\lambda \\to \\infty$ we have $\\lambda^{-1} \\mathrm{RealSoftMax}(\\lambda a, \\lambda b) \\to \\mathrm{max}(a,b)$.\n",
    "    * What does the soft-min look like?\n",
    "    * Extend this to more than two numbers."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}