Linear Regression
Introduction
Linear regression is a typical method among linear models.
Basic Principles
Given a data set $D = \{(x_1,y_1),...,(x_m,y_m) \}$ of inputs $x$ and outputs $y$, where $y_{i}\in \mathbb{R}$. A linear regression model assumes that the data are linearly distributed, so the goal is to learn a linear model that minimizes the error between the predicted values and the true values. Assume that the output and the input in linear regression are related by
$$ y = wx_i+b $$Least squares minimizes the mean squared error:
$$ \begin{aligned} (w^*,b^*)=\arg\min\sum_{i=1}^{m}(y-y_i)^2=\arg\min\sum_{i=1}^{m}(wx_i+b-y_i)^2 \end{aligned}\tag{1}\label{eq1} $$The closed-form solutions for the parameters $w^*$ and $b^*$ can be obtained from $\eqref{eq1}$.
$$ \begin{aligned} \frac{\partial L(w, b)}{\partial w} & =\frac{\partial}{\partial w}\left[\sum_{i=1}^{m}\left(w x_{i}+b-y_{i}\right)^{2}\right] =\sum_{i=1}^{m} \frac{\partial}{\partial w}\left[\left(y_{i}-w x_{i}-b\right)^{2}\right] \\ & =\sum_{i=1}^{m}\left[2 \cdot\left(y_{i}-w x_{i}-b\right) \cdot\left(-x_{i}\right)\right] =\sum_{i=1}^{m}\left[2 \cdot\left(w x_{i}^{2}-y_{i} x_{i}+b x_{i}\right)\right] \\ & =2 \cdot\left(w \sum_{i=1}^{m} x_{i}^{2}-\sum_{i=1}^{m} y_{i} x_{i}+b \sum_{i=1}^{m} x_{i}\right) \end{aligned} $$$$ \begin{aligned} \frac{\partial L(w, b)}{\partial b} & =\frac{\partial}{\partial b}\left[\sum_{i=1}^{m}\left(w x_{i}+b-y_{i}\right)^{2}\right] =\sum_{i=1}^{m} \frac{\partial}{\partial b}\left[\left(y_{i}-w x_{i}-b\right)^{2}\right] \\ & =\sum_{i=1}^{m}\left[2 \cdot\left(y_{i}-w x_{i}-b\right) \cdot(-1)\right] =\sum_{i=1}^{m}\left[2 \cdot\left(-y_{i}+w x_{i}+b\right)\right] \\ & =2 \cdot\left(-\sum_{i=1}^{m} y_{i}+\sum_{i=1}^{m} w x_{i}+\sum_{i=1}^{m} b\right) =2 \cdot\left(m b-\sum_{i=1}^{m}\left(y_{i}-w x_{i}\right)\right) \end{aligned} $$This yields the following expressions for the weight $w^*$ and the bias $b^*$:
$$ \begin{aligned} w^{*}&=\frac{\sum_{i=1}^{m} y_{i}\left(x_{i}-\bar{x}\right)}{\sum_{i=1}^{m} x_{i}^{2}-\frac{1}{m}\left(\sum_{i=1}^{m} x_{i}\right)^{2}} \\ b^{*}&=\frac{1}{m} \sum_{i=1}^{m}\left(y_{i}-w x_{i}\right) \end{aligned} $$Equation $\eqref{eq1}$ is the vector form of linear regression. In practice, linear regression is usually written in matrix form. First, the inputs $x$ are concatenated into a matrix:
$$ \boldsymbol{X}=\left(\begin{array}{ccccc} x_{11} & x_{12} & \cdots & x_{1 d} & 1 \\ x_{21} & x_{22} & \cdots & x_{2 d} & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{m 1} & x_{m 2} & \cdots & x_{m d} & 1 \end{array}\right)=\left(\begin{array}{cc} x_{1}^{\mathrm{T}} & 1 \\ \vdots & \vdots \\ x_{m}^{\mathrm{T}} & 1 \end{array}\right) $$The output vector $y$ is stacked accordingly as $\mathbf{y}=(y_1;y_2;...;y_m)$. The optimization objective then takes the following matrix form:
$$ w^*=\arg\min(\mathbf{y}-\mathbf{X}\hat{w}^T)(\mathbf{y}-\mathbf{X}\hat{w}) $$Differentiating with respect to the weight matrix and the bias matrix yields:
$$ \begin{aligned} \frac{\partial L}{\partial w}&=-\mathbf{X}^T\mathbf{y}-\mathbf{X}^T\mathbf{y}+(\mathbf{X^TX}+\mathbf{X^TX})\hat{w}\\ \frac{\partial L}{\partial b}&=2\mathbf{X}^T(\mathbf{X}\hat{w}-\mathbf{y}) \end{aligned} $$The analytical solution, the normal equation, follows directly from the gradient:
$$ \hat{w}=(\mathbf{X^{T}X})^{-1} \mathbf{X}^{T}\mathbf{y} $$Implementation
NumPy Implementation
| |
Linear Regression with scikit-learn
| |
