<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Linear Least Squares
This is the most common form of linear regression. Let's look at a concrete example...
Let us assume we would like to fit a line to the following three points
$${(x_i,y_i)} = {(1,2), (2,1), (2.5,2)}$$
Step1:  Another way to express this problem is to say, I would like to find the equation of a line that satisfies all of the above points. Take the following general equation of a line...
$$ \alpha x_i + \beta = y_i $$
We would like to find the parameters $\alpha$ and $\beta$ such that the equality is satisfied for all of the points $(x_i, y_i)$. This can be expressed as a system of equations.
$$\begin{array}{lcl} \alpha (1)+\beta & = & 2 \ \alpha(2)+ \beta & = & 1 \ \alpha(2.5)+ \beta & = & 2 \end{array}$$
Now because each equation in the system is linear, which I will define in a bit, this system of equations can be expressed in matrix form using Linear Algebra!
$$\begin{bmatrix} 1 & 1 \ 2 & 1 \ 2.5 & 1 \end{bmatrix} \begin{bmatrix} \alpha \ \beta \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
The ideal objective for this overdetermined system is to find the values of $\alpha$ and $\beta$ that make the two columns of the matrix add up to the right hand side, i.e.
$$\alpha\begin{bmatrix} 1 \ 2 \ 2.5 \end{bmatrix} + \beta\begin{bmatrix} 1 \ 1 \ 1 \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
In linear algebra notation we express this problem more succinctly as follows
$$A\vec{x} = \vec{b}$$ 
where
$$A = \begin{bmatrix} 1 & 1 \ 2 & 1 \ 2.5 & 1 \end{bmatrix} \hspace{10pt} \vec{x} = \begin{bmatrix} \alpha \ \beta \end{bmatrix} \hspace{10pt} \vec{b} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
We know however, via our impressive powers of logic, that there does not exist an equation of a line that can pass through all of the points above, because the points do not lie along a line. In otherwords, there are not such $\alpha$ and $\beta$ that satisfy all of the equations simultaneously. In linear algebra lingo, we say that $\vec{b}$ does not lie in the column space of $A$. Since there is no exact solution, given a value of $\vec{x}$ we can express how far it is from the ideal solution as follows.
$$||\vec{r}|| = ||A\vec{x} - \vec{b}||$$
Given this definition of error we seek to find the "best" solution, $\hat{x}$. We define the best solution to be the values of $\alpha$ and $\beta$ that minimize the magnitude of $||\vec{r}||$, i.e. the error.
$$\hat{x} = \min{||\vec{r}||} = \min_{\vec{x}}{||A\vec{x} - \vec{b}}||$$
As far as theory is concerned, this is an extremely well posed problem. It can be shown that the parameter space is a convex parabola with one global minimum. Even more, because this is posed in the linear world we can solve this
problem directly in one formula
$$\hat{x} = (A^TA)^{-1}A^T\vec{b}$$
For those interested, since $\vec{b}$ is not in the columnspace of $A$, this formula says the "best" solution is the projection of $\vec{b}$ onto the columnspace. Interestingly this is equivalent to solving the above minimization problem. In practice however, it is not very stable or efficient to solve it directly like this. We now plot the line to see how close it is to the points.
Step2:  NOW, let's assume that instead of fitting a line we wanted to fit a parabola. This is still a linear least squares problem. That's because linear least squares only requires that the function being fit is linear in its parameters. We will look more at what that means below. Let's take a general quadratic equation.
$$\alpha x_i^2 + \beta x_i + \gamma = y_i$$
Now we have three degrees of freedom and must fit all 3 parameters. We pose this problem the same way as above. We want the quadratic equation to satisfy all of the points $(x_i,y_i)$ simultaneously. We want $\alpha$, $\beta$, and $\gamma$ such that all of the below equations are true.
$$\begin{array}{lcl} \alpha (1)^2+\beta(1)+\gamma & = & 2 \ \alpha(2)^2+ \beta(2) + \gamma & = & 1 \ \alpha(2.5)^2+ \beta(2.5) + \gamma & = & 2 \end{array}$$
In matrix form...
$$\begin{bmatrix} 1 & 1 & 1 \ 4 & 2 & 1 \ 6.25 & 2.5 & 1 \end{bmatrix} \begin{bmatrix} \alpha \ \beta \ \gamma \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
This time, there does exist a unique solution. A quadratic equation has 3 degrees of freedom and there are 3 constraints posed. Our good friend Gauss proved that $n$ distinct points uniquely define a polynomial of degree $n-1$. So we will find the "best" solution using the above technique and show that the error is zero.
Step3:  Now we look at the resulting parabola and see that it passes through all 3 points.
<ASSISTANT_TASK:>
Python Code:
#%matplotlib inline
import matplotlib.pyplot as plt
plt.scatter((1,2,2.5), (2,1,2)); plt.xlim((0,3)); plt.ylim((0,3));
Explanation: Linear Least Squares
This is the most common form of linear regression. Let's look at a concrete example...
Let us assume we would like to fit a line to the following three points
$${(x_i,y_i)} = {(1,2), (2,1), (2.5,2)}$$
End of explanation
import numpy as np
A = np.array(((1,1),(2,1),(2.5,1))); b = np.array((2,1,2)) # Create A and b
x = np.dot(np.dot(np.linalg.inv(np.dot(A.T, A)), A.T), b) # Project b onto Col(A)
xvals = np.linspace(0,3,100) # Create a set of x values 
yvals = x[0]*xvals + x[1] # All y values for the equation of the line
plt.scatter((1,2,2.5), (2,1,2)); plt.plot(xvals,yvals); plt.xlim((0,3)); plt.ylim((0,3));
Explanation: Another way to express this problem is to say, I would like to find the equation of a line that satisfies all of the above points. Take the following general equation of a line...
$$ \alpha x_i + \beta = y_i $$
We would like to find the parameters $\alpha$ and $\beta$ such that the equality is satisfied for all of the points $(x_i, y_i)$. This can be expressed as a system of equations.
$$\begin{array}{lcl} \alpha (1)+\beta & = & 2 \ \alpha(2)+ \beta & = & 1 \ \alpha(2.5)+ \beta & = & 2 \end{array}$$
Now because each equation in the system is linear, which I will define in a bit, this system of equations can be expressed in matrix form using Linear Algebra!
$$\begin{bmatrix} 1 & 1 \ 2 & 1 \ 2.5 & 1 \end{bmatrix} \begin{bmatrix} \alpha \ \beta \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
The ideal objective for this overdetermined system is to find the values of $\alpha$ and $\beta$ that make the two columns of the matrix add up to the right hand side, i.e.
$$\alpha\begin{bmatrix} 1 \ 2 \ 2.5 \end{bmatrix} + \beta\begin{bmatrix} 1 \ 1 \ 1 \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
In linear algebra notation we express this problem more succinctly as follows
$$A\vec{x} = \vec{b}$$ 
where
$$A = \begin{bmatrix} 1 & 1 \ 2 & 1 \ 2.5 & 1 \end{bmatrix} \hspace{10pt} \vec{x} = \begin{bmatrix} \alpha \ \beta \end{bmatrix} \hspace{10pt} \vec{b} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
We know however, via our impressive powers of logic, that there does not exist an equation of a line that can pass through all of the points above, because the points do not lie along a line. In otherwords, there are not such $\alpha$ and $\beta$ that satisfy all of the equations simultaneously. In linear algebra lingo, we say that $\vec{b}$ does not lie in the column space of $A$. Since there is no exact solution, given a value of $\vec{x}$ we can express how far it is from the ideal solution as follows.
$$||\vec{r}|| = ||A\vec{x} - \vec{b}||$$
Given this definition of error we seek to find the "best" solution, $\hat{x}$. We define the best solution to be the values of $\alpha$ and $\beta$ that minimize the magnitude of $||\vec{r}||$, i.e. the error.
$$\hat{x} = \min{||\vec{r}||} = \min_{\vec{x}}{||A\vec{x} - \vec{b}}||$$
As far as theory is concerned, this is an extremely well posed problem. It can be shown that the parameter space is a convex parabola with one global minimum. Even more, because this is posed in the linear world we can solve this
problem directly in one formula
$$\hat{x} = (A^TA)^{-1}A^T\vec{b}$$
For those interested, since $\vec{b}$ is not in the columnspace of $A$, this formula says the "best" solution is the projection of $\vec{b}$ onto the columnspace. Interestingly this is equivalent to solving the above minimization problem. In practice however, it is not very stable or efficient to solve it directly like this. We now plot the line to see how close it is to the points.
End of explanation
A = np.array(((1,1,1),(4,2,1),(6.25,2.5,1))) # The matrix for our new 3x3 system of equations.
x = np.dot(np.dot(np.linalg.inv(np.dot(A.T, A)), A.T), b) # Project b onto Col(A)
error = np.linalg.norm( np.dot(A,x) - b )
print "Error = ", error
Explanation: NOW, let's assume that instead of fitting a line we wanted to fit a parabola. This is still a linear least squares problem. That's because linear least squares only requires that the function being fit is linear in its parameters. We will look more at what that means below. Let's take a general quadratic equation.
$$\alpha x_i^2 + \beta x_i + \gamma = y_i$$
Now we have three degrees of freedom and must fit all 3 parameters. We pose this problem the same way as above. We want the quadratic equation to satisfy all of the points $(x_i,y_i)$ simultaneously. We want $\alpha$, $\beta$, and $\gamma$ such that all of the below equations are true.
$$\begin{array}{lcl} \alpha (1)^2+\beta(1)+\gamma & = & 2 \ \alpha(2)^2+ \beta(2) + \gamma & = & 1 \ \alpha(2.5)^2+ \beta(2.5) + \gamma & = & 2 \end{array}$$
In matrix form...
$$\begin{bmatrix} 1 & 1 & 1 \ 4 & 2 & 1 \ 6.25 & 2.5 & 1 \end{bmatrix} \begin{bmatrix} \alpha \ \beta \ \gamma \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 2 \end{bmatrix}$$
This time, there does exist a unique solution. A quadratic equation has 3 degrees of freedom and there are 3 constraints posed. Our good friend Gauss proved that $n$ distinct points uniquely define a polynomial of degree $n-1$. So we will find the "best" solution using the above technique and show that the error is zero.
End of explanation
yvals = x[0]*xvals*xvals + x[1]*xvals + x[2] # All y values for the equation of the line
plt.scatter((1,2,2.5), (2,1,2)); plt.plot(xvals,yvals); plt.xlim((0,3)); plt.ylim((0,3));
Explanation: Now we look at the resulting parabola and see that it passes through all 3 points.
End of explanation
<END_TASK>