Least-squares regression is a methodology for finding the equation of a best fit line through a set of data points. It also provides a means of describing how well the data correlates to a linear relationship. An example of data with a general linear trend is seen in the above graph. First, we will go over the derivation of the formulas from theory and then I have also appended at the end of this post Scilab code for implementation of the algorithm.
The equation of a line through a data point can be written as:
The value of any data points that are not directly on the line but are in the proximity of the line can be given by:
Where e is the vertical error between the y-value given by the line and the actual y-value of the data. The goal would be to come up with a line which minimizes this error. In least-squares regression, this is accomplished by minimizing the sum of the squares of the errors. The sum of the squares of the errors is given by:
In order to minimize this value, the minimum finding techniques of differential calculus will be used. First take the derivative with respect to the slope.
Then with respect to the y-intercept yields:
Which can be substituted in the previous equation to solve for the slope.
The y-intercept is then:
It can be seen that these last two formulas only require knowledge about the data point coordinates and the number of points and the equation for the least squares linear regression line can be found.
Finally, below is the Scilab code implementation.
//the linear regression function takes x-values and //y-values of data in the column vectors 'X' and 'Y' and finds //the best fit line through the data points. It returns //the slope and y-intercept of the line as well as the //coefficient of determination ('r_sq'). //the function call for this should be of the form: //'[m,b,r2]=Linear_Regression(x,y)' function [slope, y_int, r_sq]=Linear_Regression(X, Y) //determine the number of data points n=size(X,'r'); //initialize each summation sum_x=0; sum_y=0; sum_xy=0; sum_x_sq=0; sum_y_sq=0; //calculate each sum required to find the slope, y-intercept and r_sq for i=1:n sum_x=sum_x+X(i); sum_y=sum_y+Y(i); sum_xy=sum_xy+X(i)*Y(i); sum_x_sq=sum_x_sq+X(i)*X(i); sum_y_sq=sum_y_sq+Y(i)*Y(i); end //determine the average x and y values for the //y-intercept calculation x_bar=sum_x/n; y_bar=sum_y/n; //calculate the slope, y-intercept and r_sq and return the results slope=(n*sum_xy-sum_x*sum_y)/(n*sum_x_sq-sum_x^2); y_int=y_bar-slope*x_bar; r_sq=((n*sum_xy-sum_x*sum_y)/(sqrt(n*sum_x_sq-sum_x^2)*sqrt(n*sum_y_sq-sum_y^2)))^2; //determine the appropriate axes size for plotting the data and //linear regression line axes_size=[min(X)-0.1*(max(X)-min(X)),min(Y)-0.1*(max(Y)-min(Y)),max(X)+0.1*(max(X)-min(X)),max(Y)+0.1*(max(Y)-min(Y))]; //plot the provided data plot2d(X,Y,style=-4,rect=axes_size); //plot the calculated regression line plot2d(X,(slope*X+y_int)); endfunction
I hope this proves helpful. Let me know in the comments if you have any questions.
Suppose you are in the can manufacturing industry. Your job is to create cans according to the specifications of canned goods suppliers who will put their products in your cans and distribute them for sale. Now suppose one of those canned good suppliers comes to you and says, “We need a can that can contain a 300 mL volume of our product. Joe Shmoe says he can provide us these cans for $X. What can you do?” If you want the canned good suppliers business you will have to underbid Joe. (Provided you can’t sale them on some other facet of your company, i.e. service, quality, etc.) How will you do it? Where can you cut cost? What is the most inexpensive can you can make to satisfy the spec? In the real world this is a very complex question because it involves labor, facility, process, and material expenses along with several others. For the sake of this exercise however, we will use the principle of the derivative to optimize our can design in order to minimize material cost.
Now let’s assume you are set up to produce a standard cylindrical can with a top and a botttom. (I realize the canned goods supplier will have to add their product before the top is sealed and I realize that actual cans have a small lip on the top and bottom, but for the sake of simplicity…) To minimize the cost of the cans we want to minimize the amount of material used. But what shape cylinder will contain the required 300 mL but use minimal material? A short fat can or a tall thin can? How “tall” or how “short”?
First, realize the total material for the can can be determined by finding the area of the metal. For a cylinder this is the area of the bottom plus the area of the top plus the area of the side.
We can rewrite the area of the top and bottom as:
If you imagine removing the top and bottom, cutting the side along a vertical line, and laying it out flat you can see that the area of the side is the area of a rectangle with the length of one side equal to the height of the can and the length of the other side equal to the circumference of the top or bottom. So its area is:
Putting this all together, the total area of a can is given by:
Now the volume of the cylinder is given by:
If we rearrange this expression for the height, h we get:
Now we substitute this into our expression for the area to eliminate the h and make the whole thing in terms of 1 variable. (r – because the volume is given to us in the spec)
This equation tells us how much area a can has of a particular volume with any radius. With this in hand we can now use the derivative to optimize (maximize or minimize) the can design and find out which radius will give us the smallest area and thus the most inexpensive (as far as material costs go) cylindrical can that can contain the prescribed volume. Taking the derivative of the area equation using the power rule we have:
Now we set this equal to zero to find the minimum area. Solving for r we get:
Knowing that the volume is 300 mL our radius is:
Putting this back in our equation for h we get a height of:
These are the dimensions for our can of minimum material. Below I have tabulated and graphed some other values for the radius and associated heights that yield the necessary volume and show that the resulting surface area is larger than our optimized design.
One other beautiful thing about this technique is that I have a general formula for an optimized cylindrical can for any volume. I can just put in whatever the specification says and get my design.
Although this is greatly simplified, I hope this provides another demonstration of the real world applicability of these techniques.
Previously we have discussed how a derivative is found using the limit, why the derivative is useful, and how to find it. Now to attempt to simplify or shortcut the derivative finding process, we will look at some general rules that can be used instead of going through the entire limit step-by-step every time.
The first derivative we will look at is the derivative of a linear function in slope-intercept form.
Where m is the slope and b is the y-intercept. Using the limit definition for the derivative we have:
Therefore the derivative of any linear function is, as we would expect, equal to the slope of that line. The next derivative we will look at is a special case of the linear function. If the slope is zero then the linear function is a constant function.
As above, the derivative of a linear function is its slope therefore the derivative of a constant function is also equal to the slope which is zero.
The next rule we can look at is a single independent variable raised to any power. Hence this rule is often called the Power Rule.
Applying the limit process we obtain:
Notice how we used the Binomial Theorem to expand the first term in the numerator. At this point I want us to notice a certain pattern in the coefficients that can be seen in Pascal’s Triangle. The first coefficient will always be 1 (c1=1). This can be seen by looking at the left edge of the triangle. Every first number is 1. Secondly if you look at the diagonal row parallel to, directly adjacent to, and to the right of this first row of 1’s, you notice that the numbers count sequentially as you descend the horizontal rows of the triangle: 1, 2,3,4,5,..etc. These numbers correspond to the second coefficient in the binomial expansion. If we label the horizontal row of the very first 1 at the top of Pascal’s Triangle zero and then incrementally as we go down the triangle, the second row will provide the coefficients for the binomial squared, the third row for the binomial cubed, the forth row for the binomial to the fourth power, and so on such that the nth row gives the coefficients for the binomial to the nth power and the second coefficient will be n also (c2=n). From here we have:
So you can see that the derivative of any variable to an exponent is equal to that same variable times the original exponent to the power of one less than the original exponent. For example:
In summary we can use the following rules to make our lives easier with regard to finding derivatives.
The first post in this series discussed the idea of the limit. And we tried to present it in a fairly simple, intuitive manner. We also discussed how a lot of the difficulty people ascribe to to calculus is due to the symbology. Above in the header you will see 4 different ways of writing the first derivative. However don’t be dismayed, just stick with me and we’ll see the derivative is not really that bad. Now with reference to the limit you might ask, what does getting really close to some point of anomaly have to do with derivatives? And what is a derivative anyway? And why should I care about all this math-ese? I suppose to motivate you to read on, I will first speak toward the usefulness of this concept.
The derivative allows us to consider the way one quantity or variable responds with regard to another quantity or variable. For instance, consider distance and speed. The more distance I cover in a period of time, the greater my speed. (For more on the relationship between distance, time, speed and acceleration see this post.) Or how about manufacturing: the less material I waste, the less my costs. Or maybe fuel economy: at a low speed I consume a lot of fuel. At a really high speed I consume a lot of fuel. But at some optimum intermediary speed, I maximize my fuel economy. Or maybe designing a structure for maximum strength with minimum weight. Or an electrical system that delivers adequate power with minimum infrastructure. All of these problems and many more utilize the concept of the derivative to arrive at their solutions.
Now with the hope that you are sufficiently convinced of its usefulness, let’s look at what exactly and derivative is. Again, I want to present it in such a way that you can intuitively grasp the idea. Take a look at the following graph.
Now the red line represents the function or the relationship between the input or independent variable, x, and the output or dependent variable, y. There are two of these key points that we want to look at. First at x=a, the function value is y=f(a). We use generic symbols so it will work for any function at any point. We will take a look at a particular function shortly to try and see this less abstractly, but for now let’s continue on. The second point is at x=a+h we get y=f(a+h). Now suppose we are curious to find the slope of the function curve (red line) at the point (a,f(a)) (the line labeled T). A rough approximation could be made by finding the slope of the line between the two points we mentioned. Recall that the slope of a line is equal to the rise divided by the run. The rise then will be equal to the difference in the two y-values, in particular f(a+h) – f(a). The run will be the difference in the x-values, in particular a+h-a which is equal to h. Therefore the approximate slope could be written as:
Now look at the graph and imagine that the point (a+h, f(a+h)) moved closer and closer and closer to the point (a,f(a)). Wouldn’t this give us a better approximation of the slope at (a, f(a))? I bet you have already noticed what concept I’m alluding to. That’s right, the limit. If we use the limit to bring the two points closer and closer together (in fact we will bring them so close together that the distance between them approaches nothing) we will have the exact slope at the first point. This is how we write that:
Now I promised an example so let’s look at a simple one. Let’s use:
Using the definition above we have:
So just like that we have found the slope or derivative of the function x squared which is 2x (“a” was just used above for a particular point, but it could really be any point “x”). In this same fashion we can find the derivative or slope of any function (provided it’s continuous – more on that later.)
But now you might say, “What does finding slope have to do with all the useful stuff you talked about at first?” We will dig into that next time.