{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Linear Regression\n",
"\n",
"To start off, we will introduce the problem of regression.\n",
"This is the task of predicting a *real valued target* $y$\n",
"given a data point $\\mathbf{x}$.\n",
"Regression problems are common in practice, arising\n",
"whenever we want to predict a continuous numerical value. \n",
"Some examples of regression problems include\n",
"predicting house prices, stock prices, \n",
"length of stay (for patients in the hospital),\n",
"tomorrow's temperature, demand forecasting (for retail sales), and many more. \n",
"Note that not every prediction problem is a regression problem.\n",
"In subsequent sections we will discuss classification problems,\n",
"where our predictions are discrete categories.\n",
"\n",
"## Basic Elements of Linear Regression\n",
"\n",
"Linear regression, which dates to Gauss and Legendre, \n",
"is perhaps the simplest, and by far the most popular approach\n",
"to solving regression problems. \n",
"What makes linear regression *linear* is that \n",
"we assume that the output truly can be expressed \n",
"as a *linear* combination of the input features.\n",
"\n",
"\n",
"### Linear Model\n",
"\n",
"To keep things simple, we will start with running example\n",
"in which we consider the problem \n",
"of estimating the price of a house (e.g. in dollars) \n",
"based on area (e.g. in square feet) and age (e.g. in years). \n",
"More formally, the assumption of linearity suggests \n",
"that our model can be expressed in the following form:\n",
"\n",
"$$\\mathrm{price} = w_{\\mathrm{area}} \\cdot \\mathrm{area} + w_{\\mathrm{age}} \\cdot \\mathrm{age} + b$$\n",
"\n",
"In economics papers, it is common for authors to write out linear models in this format with a gigantic equation that spans multiple lines containing terms for every single feature. \n",
"For the high-dimensional data that we often address in machine learning,\n",
"writing out the entire model can be tedious. \n",
"In these cases, we will find it more convenient to use linear algebra notation.\n",
"In the case of $d$ variables, we could express our prediction $\\hat{y}$ as follows:\n",
"\n",
"$$\\hat{y} = w_1 \\cdot x_1 + ... + w_d \\cdot x_d + b$$\n",
"\n",
"or alternatively, collecting all features into a single vector $\\mathbf{x}$ and all parameters into a vector $\\mathbf{w}$, we can express our linear model as $\\hat{y} = \\mathbf{w}^T \\mathbf{x} + b$.\n",
"\n",
"Above, the vector $\\mathbf{x}$ corresponds to a single data point.\n",
"Commonly, we will want notation to refer to \n",
"the entire dataset of all input data points.\n",
"This matrix, often denoted using a capital letter $X$,\n",
"is called the *design matrix* and contrains one row for every example,\n",
"and one column for every feature.\n",
"\n",
"Given a collection of data points $X$ and a vector\n",
"containing the corresponding target values $\\mathbf{y}$,\n",
"the goal of linear regression is to find \n",
"the *weight* vector $w$ and bias term $b$\n",
"(also called an *offset* or *intercept*)\n",
"that associates each data point $\\mathbf{x}_i$ \n",
"with an approximation $\\hat{y}_i$ of its corresponding label $y_i$.\n",
"\n",
"Expressed in terms of a single data point, \n",
"this gives us the expression (same as above) \n",
"$\\hat{y} = \\mathbf{w}^\\top \\mathbf{x} + b$. \n",
"\n",
"Finally, for a collection of data points $\\mathbf{X}$, \n",
"the predictions $\\hat{\\mathbf{y}}$ can be expressed via the matrix-vector product:\n",
"\n",
"$${\\hat{\\mathbf{y}}} = X \\mathbf{w} + b$$\n",
"\n",
"Even if we believe that the best model \n",
"to relate $\\mathbf{x}$ and $y$ is linear,\n",
"it's unlikely that we'd find data where $y$ \n",
"lines up exactly as a linear function of $\\mathbf{x}$.\n",
"For example, both the target values $y$ and the features $X$\n",
"might be subject to some amount of measurement error.\n",
"Thus even when we believe that the linearity assumption holds,\n",
"we will typically incorporate a noise term to account for such errors.\n",
"\n",
"Before we can go about solving for the best setting of the parameters $w$ and $b$, we will need two more things: \n",
"(i) some way to measure the quality of the current model \n",
"and (ii) some way to manipulate the model to improve its quality.\n",
"\n",
"### Training Data\n",
"\n",
"The first thing that we need is training data. \n",
"Sticking with our running example, we'll need some collection of examples \n",
"for which we know both the actual selling price of each house \n",
"as well as their corresponding area and age. \n",
"Our goal is to identify model parameters \n",
"that minimize the error between the predicted price and the real price. \n",
"In the terminology of machine learning, the data set is called a ‘training data’ or ‘training set’, a house (often a house and its price) here comprises one ‘sample’, and its actual selling price is called a ‘label’. \n",
"The two factors used to predict the label \n",
"are called ‘features’ or 'covariates'. \n",
"\n",
"Typically, we will use $n$ to denote the number of samples in our dataset. \n",
"We index the samples by $i$, denoting each input data point as $x^{(i)} = [x_1^{(i)}, x_2^{(i)}]$ and the corresponding label as $y^{(i)}$.\n",
"\n",
"### Loss Function\n",
"\n",
"In model training, we need to measure the error \n",
"between the predicted value and the real value of the price. \n",
"Usually, we will choose a non-negative number as the error. \n",
"The smaller the value, the smaller the error. \n",
"A common choice is the square function. \n",
"For given parameters $\\mathbf{w}$ and $b$,\n",
"we can express the error of our prediction on a given a sample as follows:\n",
"\n",
"$$l^{(i)}(\\mathbf{w}, b) = \\frac{1}{2} \\left(\\hat{y}^{(i)} - y^{(i)}\\right)^2,$$\n",
"\n",
"The constant $1/2$ is just for mathematical convenience,\n",
"ensuring that after we take the derivative of the loss,\n",
"the constant coefficient will be $1$. \n",
"The smaller the error, the closer the predicted price is to the actual price, and when the two are equal, the error will be zero. \n",
"\n",
"Since the training dataset is given to us, and thus out of our control,\n",
"the error is only a function of the model parameters. \n",
"In machine learning, we call the function that measures the error the ‘loss function’. \n",
"The squared error function used here is commonly referred to as ‘square loss’.\n",
"\n",
"To make things a bit more concrete, consider the example below where we plot a regression problem for a one-dimensional case, e.g. for a model where house prices depend only on area.\n",
"\n",
"![Linear regression is a single-layer neural network. ](../img/linearregression.svg)\n",
"\n",
"As you can see, large differences between estimates $\\hat{y}^{(i)}$ and observations $y^{(i)}$ lead to even larger contributions in terms of the loss, due to the quadratic dependence. To measure the quality of a model on the entire dataset, we can simply average the losses on the training set.\n",
"\n",
"$$L(\\mathbf{w}, b) =\\frac{1}{n}\\sum_{i=1}^n l^{(i)}(\\mathbf{w}, b) =\\frac{1}{n} \\sum_{i=1}^n \\frac{1}{2}\\left(\\mathbf{w}^\\top \\mathbf{x}^{(i)} + b - y^{(i)}\\right)^2.$$\n",
"\n",
"When training the model, we want to find parameters ($\\mathbf{w}^*, b^*$) that minimize the average loss across all training samples:\n",
"\n",
"$$\\mathbf{w}^*, b^* = \\operatorname*{argmin}_{\\mathbf{w}, b}\\ L(\\mathbf{w}, b).$$\n",
"\n",
"\n",
"### Analytic Solution\n",
"\n",
"Linear regression happens to be an unusually simple optimization problem.\n",
"Unlike nearly every other model that we will encounter in this book,\n",
"linear regression can be solved easily with a simple formula,\n",
"yielding a global optimum. \n",
"To start we can subsume the bias $b$ into the parameter $\\mathbf{w}$\n",
"by appending a column to the design matrix consisting of all $1s$.\n",
"Then our prediction problem is to minimize $||\\mathbf{y} - X\\mathbf{w}||$. \n",
"Because this expression has a quadratic form it is clearly convex,\n",
"and so long as the problem is not degenerate\n",
"(our features are linearly independent), it is strictly convex.\n",
"\n",
"Thus there is just one global critical point on the loss surface \n",
"corresponding to the global minimum.\n",
"Taking the derivative of the loss with respect to $\\mathbf{w}$ \n",
"and setting it equal to 0 gives the analytic solution:\n",
"\n",
"$$\\mathbf{w}^* = (X^T X)^{-1}X^T y$$\n",
"\n",
"While simple problems like linear regression may admit analytic solutions,\n",
"you should not get used to such good fortune. \n",
"Although analytic solutions allow for nice mathematical analysis,\n",
"the requirement of an analytic solution confines one to \n",
"an restrictive set of models that would exclude all of deep learning.\n",
"\n",
"### Gradient descent\n",
"\n",
"Even in cases where we cannot solve the models analytically,\n",
"and even when the loss surfaces are high-dimensional and nonconvex,\n",
"it turns out that we can still make progress.\n",
"Moreover, when those difficult-to-optimize models are sufficiently superior for the task at hand, figuring out how to train them is well worth the trouble.\n",
"\n",
"The key trick behind nearly all of deep learning \n",
"and that we will repeatedly throughout this book\n",
"is to reduce the error gradually by iteratively updating the parameters,\n",
"each step moving the parameters in the direction \n",
"that incrementally lowers the loss function.\n",
"This algorithm is called gradient descent.\n",
"On convex loss surfaces it will eventually converge to a global minimum,\n",
"and while the same can't be said for nonconvex surfaces, \n",
"it will at least lead towards a (hopefully good) local minimum.\n",
"\n",
"The most naive application of gradient descent consists of taking the derivative of the true loss, which is an average of the losses computed on every single example in the dataset. In practice, this can be extremely slow. We must pass over the entire dataset before making a single update. \n",
"Thus, we'll often settle for sampling a random mini-batch\n",
"of examples every time we need to computer the update, \n",
"a variant called *stochastic gradient descent*.\n",
"\n",
"In each iteration, we first randomly and uniformly sample a mini-batch $\\mathcal{B}$ consisting of a fixed number of training data examples. \n",
"We then compute the derivative (gradient) of the average loss on the mini batch with regard to the model parameters. \n",
"Finally, the product of this result and a predetermined step size $\\eta > 0$ are used to update the parameters in the direction that lowers the loss. \n",
"\n",
"We can express the update mathematically as follows ($\\partial$ denotes the partial derivative):\n",
"\n",
"$$(\\mathbf{w},b) \\leftarrow (\\mathbf{w},b) - \\frac{\\eta}{|\\mathcal{B}|} \\sum_{i \\in \\mathcal{B}} \\partial_{(\\mathbf{w},b)} l^{(i)}(\\mathbf{w},b)$$\n",
"\n",
"\n",
"To summarize, steps of the algorithm are the following: \n",
"(i) we initialize the values of the model parameters, typically at random;\n",
"(ii) we iterate over the data many times, \n",
"updating the parameters in each by moving the parameters in the direction of the negative gradient, as calculated on a random minibatch of data. \n",
"\n",
"\n",
"For quadratic losses and linear functions we can write this out explicitly as follows. Note that $\\mathbf{w}$ and $\\mathbf{x}$ are vectors. Here the more elegant vector notation makes the math much more readable than expressing things in terms of coefficients, say $w_1, w_2, \\ldots w_d$.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\mathbf{w} &\\leftarrow \\mathbf{w} - \\frac{\\eta}{|\\mathcal{B}|} \\sum_{i \\in \\mathcal{B}} \\partial_{\\mathbf{w}} l^{(i)}(\\mathbf{w}, b) && =\n",
"w - \\frac{\\eta}{|\\mathcal{B}|} \\sum_{i \\in \\mathcal{B}} \\mathbf{x}^{(i)} \\left(\\mathbf{w}^\\top \\mathbf{x}^{(i)} + b - y^{(i)}\\right),\\\\\n",
"b &\\leftarrow b - \\frac{\\eta}{|\\mathcal{B}|} \\sum_{i \\in \\mathcal{B}} \\partial_b l^{(i)}(\\mathbf{w}, b) && =\n",
"b - \\frac{\\eta}{|\\mathcal{B}|} \\sum_{i \\in \\mathcal{B}} \\left(\\mathbf{w}^\\top \\mathbf{x}^{(i)} + b - y^{(i)}\\right).\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"In the above equation $|\\mathcal{B}|$ represents the number of samples (batch size) in each mini-batch, $\\eta$ is referred to as ‘learning rate’ and takes a positive number. It should be emphasized that the values of the batch size and learning rate are set somewhat manually and are typically not learned through model training. Therefore, they are referred to as *hyper-parameters*. What we usually call *tuning hyper-parameters* refers to the adjustment of these terms. In the worst case this is performed through repeated trial and error until the appropriate hyper-parameters are found. A better approach is to learn these as parts of model training. This is an advanced topic and we do not cover them here for the sake of simplicity.\n",
"\n",
"### Model Prediction\n",
"\n",
"After completing the training process, we record the estimated model parameters, denoted $\\hat{\\mathbf{w}}, \\hat{b}$ \n",
"(in general the \"hat\" symbol denotes estimates).\n",
"Note that the parameters that we learn via gradient descent \n",
"are not exactly equal to the true minimizers of the loss on the training set,\n",
"that's be cause gradient descent converges slowly to a local minimum but does not achieve it exactly. \n",
"Moreover if the problem has multiple local minimum, we may not necessarily achieve the lowest minimum. \n",
"Fortunately, for deep neural networks, finding parameters that minimize the loss *on training data* is seldom a significant problem. The more formidable task is to find parameters that will achieve low loss on data that we have not seen before, a challenge called *generalization*. We return to these topics throughout the book.\n",
"\n",
"Given the learned learned linear regression model $\\hat{\\mathbf{w}}^\\top x + \\hat{b}$, we can now estimate the price of any house outside the training data set with area (square feet) as $x_1$ and house age (year) as $x_2$. Here, estimation also referred to as ‘model prediction’ or ‘model inference’.\n",
"\n",
"Note that calling this step 'inference' is a misnomer, \n",
"but has become standard jargon in deep learning. \n",
"In statistics, 'inference' means estimating parameters \n",
"and outcomes based on other data. \n",
"This misuse of terminology in deep learning \n",
"can be a source of confusion when talking to statisticians. \n",
"\n",
"\n",
"## From Linear Regression to Deep Networks\n",
"\n",
"So far we only talked about linear functions. While neural networks cover a much richer family of models, we can begin thinking of the linear model as a neural network by expressing it the language of neural networks. To begin, let's start by rewriting things in a 'layer' notation.\n",
"\n",
"### Neural Network Diagram\n",
"\n",
"Commonly, deep learning practitioners represent models visually using neural network diagrams. In Figure 3.1, we represent linear regression with a neural network diagram. The diagram shows the connectivity among the inputs and output, but does not depict the weights or biases (which are given implicitly).\n",
"\n",
"![Linear regression is a single-layer neural network. ](../img/singleneuron.svg)\n",
"\n",
"In the above network, the inputs are $x_1, x_2, \\ldots x_d$. \n",
"Sometimes the number of inputs are referred to as the feature dimension. \n",
"For linear regression models, we act upon $d$ inputs and output $1$ value. \n",
"Because there is just a single computed neuron (node) in the graph,\n",
"we can think of linear models as neural networks consisting of just a single neuron. Since all inputs are connected to all outputs (in this case it's just one), this layer can also be regarded as an instance of a *fully-connected layer*, also commonly called a *dense layer*.\n",
"\n",
"### Biology\n",
"\n",
"Neural networks derive their name from their inspirations in neuroscience. \n",
"Although linear regression predates computation neuroscience,\n",
"many of the models we subsequently discuss truly owe to neural inspiration.\n",
"To understand the neural inspiration for artificial neural networks \n",
"it is worth while considering the basic structure of a neuron. \n",
"For the purpose of the analogy it is sufficient to consider the *dendrites* \n",
"(input terminals), the *nucleus* (CPU), the *axon* (output wire), \n",
"and the *axon terminals* (output terminals) \n",
"which connect to other neurons via *synapses*.\n",
"\n",
"![The real neuron](../img/Neuron.svg)\n",
"\n",
"Information $x_i$ arriving from other neurons (or environmental sensors such as the retina) is received in the dendrites. In particular, that information is weighted by *synaptic weights* $w_i$ which determine how to respond to the inputs (e.g. activation or inhibition via $x_i w_i$). All this is aggregated in the nucleus $y = \\sum_i x_i w_i + b$, and this information is then sent for further processing in the axon $y$, typically after some nonlinear processing via $\\sigma(y)$. From there it either reaches its destination (e.g. a muscle) or is fed into another neuron via its dendrites.\n",
"\n",
"Brain *structures* vary significantly. Some look (to us) rather arbitrary whereas others have a regular structure. For example, the visual system of many insects is consistent across members of a species. The analysis of such structures has often inspired neuroscientists to propose new architectures, and in some cases, this has been successful. However, much research in artificial neural networks has little to do with any direct inspiration in neuroscience, just as although airplanes are *inspired* by birds, the study of orninthology hasn't been the primary driver of aeronautics innovaton in the last century. Equal amounts of inspiration these days comes from mathematics, statistics, and computer science.\n",
"\n",
"### Vectorization for Speed\n",
"\n",
"In model training or prediction, we often use vector calculations and process multiple observations at the same time. To illustrate why this matters, consider two methods of adding vectors. We begin by creating two 1000 dimensional ones first."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"attributes": {
"classes": [],
"id": "",
"n": "1"
}
},
"outputs": [],
"source": [
"from mxnet import nd\n",
"from time import time\n",
"\n",
"a = nd.ones(shape=10000)\n",
"b = nd.ones(shape=10000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One way to add vectors is to add them one coordinate at a time using a for loop."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"attributes": {
"classes": [],
"id": "",
"n": "2"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1.6884946823120117"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"start = time()\n",
"c = nd.zeros(shape=10000)\n",
"for i in range(10000):\n",
" c[i] = a[i] + b[i]\n",
"time() - start"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Another way to add vectors is to add the vectors directly:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"attributes": {
"classes": [],
"id": "",
"n": "3"
}
},
"outputs": [
{
"data": {
"text/plain": [
"0.00031828880310058594"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"start = time()\n",
"d = a + b\n",
"time() - start"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Obviously, the latter is vastly faster than the former. Vectorizing code is a good way of getting order of magnitude speedups. Likewise, as we saw above, it also greatly simplifies the mathematics and with it, it reduces the potential for errors in the notation.\n",
"\n",
"## The Normal Distribution and Squared Loss\n",
"\n",
"The following is optional and can be skipped but it will greatly help with understanding some of the design choices in building deep learning models. As we saw above, using the squared loss $l(y, \\hat{y}) = \\frac{1}{2} (y - \\hat{y})^2$ has many nice properties, such as having a particularly simple derivative $\\partial_{\\hat{y}} l(y, \\hat{y}) = (\\hat{y} - y)$. That is, the gradient is given by the difference between estimate and observation. You might reasonably point out that linear regression is a [classical](https://en.wikipedia.org/wiki/Regression_analysis#History) statistical model. Legendre first developed the method of least squares regression in 1805, which was shortly thereafter rediscovered by Gauss in 1809. To understand this a bit better, recall the normal distribution with mean $\\mu$ and variance $\\sigma^2$.\n",
"\n",
"$$p(x) = \\frac{1}{\\sqrt{2 \\pi \\sigma^2}} \\exp\\left(-\\frac{1}{2 \\sigma^2} (x - \\mu)^2\\right)$$\n",
"\n",
"It can be visualized as follows:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"attributes": {
"classes": [],
"id": "",
"n": "2"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"