# Do we actually take random line in first step of linear regression?

This is the screenshot I took from a video on linear regression made by Luis Serrano. He explained linear regression step by step (scratch version). The first step was to start with a random line.

The question is do we actually draw a random line, or instead do we perform some calculation like taking an average of y values and initially draw a line. Because if we take any random line it might not fall near any points at all. Maybe it will fall on the 3rd quadrant of the coordinate system where there are no points in this case.

• Linear regression when using sum of squared errors as the optimality criterion has a closed form solution. There is no trial and error. Commented Dec 14, 2021 at 15:13
• FWIW, It's plausible that the instructor is introducing the concept in this way so that when students arrive at advanced models like neural networks, the mechanics of gradient descent are familiar. But, this particular slide seems like a poor way to do so because it’s very far removed from a reasonable algorithm.
– Sycorax
Commented Dec 14, 2021 at 16:03
• As a practical matter, solvers often use heuristics to find reasonable starting guesses. For instance, we might split the points into three roughly equal vertical strips (by count). Drop the middle strip. In each of the left and right strips, compute the median $x$ value and median $y$ value, thereby producing a "median point" within each strip. Connecting those points gives a very reasonable estimate. (It is a simple form of "robust regression.") The illustrated regression algorithm, BTW, is extremely poor: it must be considered as a conceptual explanation only.
– whuber
Commented Dec 14, 2021 at 18:08
• The algorithm actually doesn't work. Consider what happens when all the points happen to lie to the right of the y-axis and above the initial line. The slope and intercept will increase on average until half the points lie above it and half lie below it. From that point on, only small fluctuations in the line will happen, because changes to slope and intercept tend to be balanced out. If the slope of the initial guess was far off, its estimate can never reach a reasonable value. One lesson: the proposer of an algorithm has a duty to show (a) it converges (b) to reasonable values.
– whuber
Commented Dec 14, 2021 at 21:24
• @f-c-akhi There are a number of suitable but simple approaches (starting from 'naive' ways to fit a line), to motivate ordinary linear regression but this one seems to be flawed. Given the issues that arose in your previous question, which related to the same video (or at least the same presenter), I'd urge you to consider that you may be served by some other resource. Commented Dec 15, 2021 at 2:25

NO

What we want to find are the parameters that result in the least amount of error, and OLS defines error as the squared differences between observed values $$y_i$$ and predicted values $$\hat y_i$$. Error often gets denoted by an $$L$$ for "loss".

$$L(y, \hat y) = \sum_{i = 1}^N \bigg(y_i - \hat y_i\bigg)^2$$

We have our regression model, $$\hat y_i =\hat\beta_0 + \hat\beta_1x$$, so the $$\hat y$$ is a function of $$\hat\beta_0$$ and $$\hat\beta_1$$.

$$L(y, \hat\beta_0, \hat\beta_1) = \sum_{i = 1}^N \bigg(y_i - (\hat\beta_0 + \hat\beta_1x)\bigg)^2$$

We want to find the $$\hat\beta_0$$ and $$\hat\beta_1$$ that minimize $$L$$.

What the video does is simulate pieces of the entire "loss function". For $$\hat\beta_0 = 1$$ and $$\hat\beta_1 = 7$$, you get a certain loss value. For $$\hat\beta_0 = 1$$ and $$\hat\beta_1 = 8$$, you get another loss value. One approach to finding the minimum is to pick random values until you find one that results in a loss value that seems low enough (or you're tired of waiting). Much of the deep learning work uses variations of this, with tricks like stochastic gradient descent to make the algorithm get (close to) the right answer in a short amount of time.

In OLS linear regression, however, calculus gives us a solution to the minimization problem, and we do not have to play such games.

$$\hat\beta_1=\frac{cov(x,y)}{var(x)}\\ \hat\beta_0=\bar y-\hat\beta_1\bar x$$

• When there are a very large number of parameters or the problem is truncated, and a closed form solution is not tractable or useful, then the answer is actually YES! You start from a random line, then you use optimisation like SGD to improve the line by a small amount each iteration. A recent paper uses this approach for solving a truncated linear regression that fails with OLS for an example of when SGD would be used for linear regression: proceedings.neurips.cc/paper/2020/hash/… Commented Dec 15, 2021 at 15:30
• @JStrahl more than just truncation, just about any nontrivial modification to linear regression will leave us without a closed form solution. So from the perspective of generality, I agree, it's quite useful to understand why gradient-based methods with random init works. Commented Dec 16, 2021 at 0:06

We, sort of, do something like this effectively, especially in Gradient descent algorithms. A random line is simply a set of random parameters $$\beta_0,\beta_1$$. The gradient descent algorithm has to start somewhere looking for the optimal parameters, and the random set of parameters is one place to start.

So, in a way, we do start with a line, though we don’t draw it. Also, the algorithm itself is not exactly the one presented, of course. The instructor was probably trying to explain it without the notion of a gradient, and it’s tough. So, I’d give him a pass on a sloppy attempt.

Sometimes it is more intuitive to show things graphically, mostly for beginners. You can do it this way, of course, but in practice this is not how it is done, as there is a closed form solution, as Frank Harrel mentioned in the comment. If you have a single independent variable, as in simple linear regression, $$\hat y_i = \hat\beta_0 + \hat\beta_1x$$, you solve it analytically, through the equations below:

$$\hat\beta_1=\frac{cov(x,y)}{var(x)}$$

and

$$\hat\beta_0=\bar y-\beta_1\bar x$$

By the way, it is possible that this question (Why is a regression coefficient covariance/variance?) is of your interest.

• Thank you for your answer. I have confusion here. Did you mean we don't take a random line but we do some calculations on X and Y values like taking covariance and variance? And finding the value of slope and intercept? Then draw the first line which is not actually random. We then do some more calculations on the slope and intercept and try to find the best-fit line. I know practically it is not that easy, But, all I want to know is whether we take a random line or not initially. Commented Dec 14, 2021 at 15:29
• We get the best fit (the expected fit with OLS, and giving your data does not violate linear regression assumptions) by solving the two equations. We do it once, and it's the best. Things will go crazy if you're violating the assumptions, as it would also go if you tried to do it with the algorithm in the picture (like unequal variance among residuals, heteroscedasticity). What I mean is: If simple linear regression is the right approach for your case, the calculation of b_0 and b_1 one time will give you the best fit. Commented Dec 14, 2021 at 15:48

That example is definitely NOT the way linear regression is typically done, but I suppose it is an algorithm to find a regression line. As other answers have correctly stated, there is a closed form solution for finding the Least Squares Regression equation for a set of points.

That being said, what's being shown in the snippet is a method for algorithmically finding a line that gets close to the points by trial and error (i.e. iterations).

As a simple analogy to show the difference between a closed form solution and an algorithm: if I were to give you a mathematical equation, say $$10 = 2x+4$$, and asked you to solve for $$x$$, we know that you can solve this exactly using algebra.

$$10 = 2x+4$$

$$\implies 2x=6$$

$$\implies x=3$$ ** Exact solution **

Alternatively, an algorithmic approach to this could be used to solve this same equation by guessing a solution (e.g. start with a random guess: $$x=0$$) and systematically adjusting $$x$$ until your condition (statement of equality) is met, or approximately met.

$$x = 0 \implies 10=4$$ ** too low, adjust up **

$$x = 1 \implies 10=6$$ ** too low, adjust up **

$$x = 2 \implies 10=8$$ ** too low, adjust up **

$$x = 3 \implies 10=10$$ ** condition met, stop **

As this crude example shows, algorithms can sometimes approximate the answers returned by closed form solutions, but this isn't guaranteed to happen for all types of equations.

Personally, I don't find the snippet in the question to be pedagogically helpful to showing how regression lines work, and I think there are better examples of how algorithms can be used to find approximate solutions to mathematical equations.

This clearly looks like an attempt by an instructor to introduce some intuition behind linear regression and iterative optimisation to computer science students not familiar with derivatives or without a mathematical background in general.

If it was up to me I would do it in a slightly different way - start with some "goodness of fit" measure, then, since this is a simple linear regression with one covariate, perform a grid search over the intercept and slope, and calculate the selected goodness of fit measures for every point on a grid computationally using a loop.

This would give students some intuition and they would even feel being able to get an approximate answer themselves. After this step we then can mention that for some goodness of fit measures such problem can be solved precisely without the need to perform any iterations, but that doesn't change the goal or intuition behind looking for the best-fitting solution and minimising residuals.

Sticking with the iterative procedure, however, does require a starting point with a random line. This is similar to how some neural network optimisations start with initiation of random weights. Still, I feel, that calculating the goodness of fit to every subsequent iteration would help to clarify things further. Without it it might seem unclear why the line needs to move at all, and how is it getting any better by moving towards the points.

To be clear, there's a closed form solution for linear regression that is almost always used to find the fit, so there's no need for a "guess" to start with at all. This example is more of illustrative example of how Stochastic Algorithms work rather than how to best fit a linear regression model.

However, linear regression really is the exception to the rule in this case. For fitting most models, we do not have a closed form solution and we do need to start with an initial set of parameters and then iteratively improve them.

In such cases, it is often the case that choosing a good starting point, as you have suggested, will help the algorithm to converge faster. For some problems, choosing a good starting point is crucial for acceptable performance (both in terms of speed of convergence and probability that algorithm will converge to an acceptable answer), while for other model/algorithm combinations, the improvement may be so minor that it is not worth the extra effort to find a good starting values and initializing with random values is fine.

Some methods for robust regression, notably RANSAC (Random sample consensus) are actually built around fitting random lines. But this is, of course, far from what is happening here - I agree with those who say that

• it is a pedagogical tool
• the problem can be solved exactly (optimal least squares)
• it is reminiscent of the gradient descent

In the above mentioned robust methods one actually uses exact regression for fitting a line to a random subset of datapoints, thus diminishing the influence of the outliers (to which the exact solution to linear least squares regression is extremely sensitive).