Linear Regression
simonwardjones.co.uk
simonwardjones.co.uk
A good article on linear regression, in my opinion, would break it down into three steps:
1. Spend a bit of time looking at cost functions. In principle linear regression is finding the "best" line, where by "best" we consider all possible lines (yes, all uncountably infinite of them), compute the cost function for each one, and pick the one where the cost comes out lowest. You want to show a few example lines on top of some example points and label their costs. Start with absolute deviation (i.e. l1 norm) to start with - let's face it, that's really the most obvious cost function if you don't already know what comes next - then contrast with least squares (i.e. l2 norm). For example, note that least squares cost function "cares" more about points that are a particularly long way away.
2. Admit that, OK, we do want an algorithm more sensible than "try every possible line, labourously computing the cost of each one". Now you can talk about gradient descent - and I mean WHY you use gradient descent, not the computation. And now you can mention that least squares is differentiable, so solves nicely for gradient descent, which is the real reason we tend to prefer it over absolute deviation.
3. Finally, after both of those you can solve the gradient descent equations and show some associated code.
I wanted to give the ideas in the simplest way with friendly emojis and then go onto the more complex derivation with the cost function etc. I haven't explained the idea of the cost function enough. I think your idea for stating with the cost function (as a concept - not a formula) and absolute error may have been nicer to be fair. I can see a nice d3 visual where you can slide the gradient and see the total error change!
I could always add the line of best fit approach and more intuition for the cost function after I introduce training data (and before the brutal leap)?
It seems to me that you're trying to condense a few weeks of intro linear algebra into a single blog post. In my experience that only works as a refresher, not for someone starting from zero.
You use gradient descent, but do not introduce the normal equations. This is problematic for at least two reasons.
Case 1: Design matrix has full rank
Omitting the normal equations obfuscates what is really going on. You are inverting a matrix to solve the first order condition of a strictly convex objective, which therefore has a unique optimum.
Case 2: Design matrix does not have full rank
Omitting the normal equations hides the fact that there are multiple solutions to the first order condition. Gradient descent will find one of them, but you need a principled method for selecting among them. The Moore-Penrose pseudo-inverse method gives you the solution with the smallest L2 norm.
Omitting these details is setting learners up for failure.
You may amused to learn that "How would you program a solver for a system of linear equations?" was an informal interview question for a top machine learning PhD program, and applicants were not looked upon favorably if they mindlessly gave gradient descent as an answer.
1. I appreciate the rigour that went into the math notation. I need to see equations to start to make sense of something. And if you're a beginner, this at least provides an intuition for starting to grok these visuals.
2. It's visually very clear, and structured clearly. Sounds trivial, but this kind of visual organization helps a lot to break down complex topics.
3. Intro -> Math theory -> Python breakdown. The best way to teach math.
4. No memes. I feel like there's a huge temptation in articles for beginners to litter the post with moving gifs and memes which are distracting and annoying.
To me Deming regression is the most obvious. It actually took me a long time to realize that x~y and y~x are in most cases different lines.
For others that, like me, don't already know it (at least by name): the Deming cost function is the sum of perpendicular distances to the points from the line, as opposed to measuring only the vertical component.
Edit: Actually it looks like Deming regression is a bit more subtle and statistical than just sum of perpendicular distances. A treatment of linear regression from a statistical perspective of trying untangle some random noise is very worthy, but I'd save it for a second lesson, following a first lessons that's just an unmotivated "let's choose the line that's somehow closest to all the points".
This may be less of an issue for the machine leaner who's only interested in point predictions, but it's a serious concern for us old fashioned statisticians who are more interested in inference.
Edit: this is also not just true for ridge, but lasso as well
1) I know this article isn't aimed at me, but I do truly hate the excessive emojis.
2) More substantively: not once does the word "statistics" enter here. There is not a single illustration of the idea behind linear regression, which is staggeringly simple: it is just finding the best linear fit. Anyone who looks at a 2D scatterplot can do an approximate linear regression with their brains by visualizing a line that sorta fits the data. While the gradient descent stuff is useful for extending a machine learning algorithm, introducing linear regression this way obscures the actual concept - and indeed, obscures what machine learning actually is.
In my experience there are a huge number of data scientists who are ignorant of statistics and don't understand their models and algorithms. Although this is unfair, it is my impression that the author himself does not understand linear regression, even if they are able to write formulas using vectors. This article does a disservice to learners.
I am more in the camp of actually always finding them excessive. Especially in more serious, and possibly, interesting posts.
I think they're never going to go away, but at least we can try to eradicate them from professional discourse and education.
I do use smileys here on HN, on facebook, and chatting, to signal I'm being friendly and non-confrontational, to preempt and defuse situations which could escalate into anger if someone misreads the tone.
I bet somebody could write an article much like this and gloss over most (maybe all?) of the math:
1) Here's a 2D scatterplot, and we want a line that kind of follows the dots.
2) If the data were on a line, this function (sum of the y values subtracted from a linear prediction) would be 0.
2a) Maybe introduce squaring here, but it might seem a little magical and unnecessary, so perhaps wait to introduce pathologies or other reasons till after an implementation of some kind.
3) The scatterplot obviously doesn't fall on a line, but let's try to get as close to 0 as we can. Picking random parameters seems good enough for an introduction to linear regression -- certainly not as efficient in the limit as gradient descent, but it requires next to no code or math to explain what we're doing to a new student.
Future directions and blog posts) Other optimization algorithms, closed forms, why we care about squaring, other functions that work in addition to squaring, and now that we have a good idea of how linear regression might work let's add some statistical reasoning.
The linear projection, assuming finite second moments and a positive definite expectation of the design matrix, is the best linear predictor in the sense of MSE. Its error is by construction (not by assumption) uncorrelated with the regressands.
The linear regression comes in when one additionally assumes that the conditional expectation of the error given the explanatory variables is zero. This then gives unbiased estimates. No distributions required.
To characterize the distributions and do testing/intervals, one usually employs large sample theory. This also then shows when the probability limit of the estimator converges to the true value (consistency) and at which speed.
The idea of requiring Gaussian noise is, except for edge cases, depreciated. Textbooks that build on this should not be used anymore. It is misleading and it leads to the wide spread misconception that normality of the error term is in some sense essential for linear regression.
It's fine to come from the CS angle of algorithms and optimizations, as opposed to theoretical distributions and all that, but semi-parametric statistics in quite useful to understand why and when linear regression can do really well.
One can, for example, find a chapter on linear regression in most machine learning textbooks, without reference to statistics.
I've been on both sides of the fence, but it's always the statisticians who take the perspective of, "yeah, well you didn't study model diagnostics, ANOVA, QQ plots, ... so you don't know linear regression".
Linear regression as described in this post (which is pretty much what you find in Andrew Ng's famed machine learning course) can be used as an introductory stepping stone to logistic regression, neural networks, etc.
Something of a nitpick, but one thing that both Simon Ward-Jones and Joel Grus miss is that linear regression is typically not implemented using gradient descent at all, there's an analytical solution and you can get the beta coefficients with straightforward matrix algebra. It's much harder to explain than gradient descent so I get why they don't bother, but on the other hand without that background it's hard to see why everybody talks about linear regression all the time when with gradient descent or any other numerical optimizer there's really no limit to what f(x) can look like.
Even though there is no limit to what f can look like (except being differentiable), the kind of models that you can reasonably fit and obtain good performance from is still very much limited by how much data you have, and of which quality. And data is indeed the bottleneck in the vast majority of cases.
Fair point about the gradient descent Vs normal equations closed form solution. I am planning on working through a few algorithms so thought it would be better to introduce gradient descent with something simple before talking about gradient boosted decision trees and Neural Networks. Also I would have to explain more complex matrix stuff like invertibility issues and linear dependance like you said.
I guess I just dodged that bullet and went for gradient descent. Maybe another post for the linear algebra fans! Thanks for reading though!
My main criticism on the article would be that the nitty gritty section only makes sense to a reader that has already done a linear algebra / multivariate calculus course. In which case they've likely already covered least squares in greater depth (including the exact solutions) than this article. So I don't really see the purpose of the math section, except maybe to signal that the writer has a descent understanding of the algorithmic detail.
https://github.com/melling/data-science-from-scratch-swift
Of the last 5, only the Linear Regression chapter is finished:
https://github.com/melling/data-science-from-scratch-swift/b...
For my current project I had to really understand the closed-form solution for linear regression and even it looks straightforward on paper it really took a while to sink in.
Feels like some mix of SEO-farming/resume-building-blogspam.
e.g.
https://en.m.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%...
https://docs.scipy.org/doc/scipy/reference/generated/scipy.o...
What'll that give you compared to a simple gradient descent? It'll attempt to accelerate convergence by estimating an approximation of the Hessian matrix - all the second order partial derivatives, and use a line search algorithm to figure out a good step size for each step instead of using an arbitrary constant step size aka "learning rate". The "L-" variation of the algorithm will use a limited amount of memory when approximating the Hessian matrix, which might help if your cost function has a larger number of parameters. The "-B" variations of the algorithm will also let you set upper and/or lower bounds on each variable that will be respected during the search.
Huh? Doesn't this apply to literally every piece of writing ever produced? The reader is always free to leave.
Also, there's no concrete examples of this algorithm in place for students to go through and built intuition and a working understanding. Even the most dense math text books I've read have problems for the reader to work through.
I get that the author is writing for a certain audience, but this is a gross over-simplification.
You may say it's only regression if it fits your favorite framework, like giving confidence values or goodness of fit etc, but that's not true in general. There so many variants, like Bayesian probabilistic regression, nonparametrics, neural nets, random forests etc.
Either use is ok, but e.g. a tree model predicting if an animal is a dog or a cat is not regression by any definition.
You're right that regression is a type of task, not a type of solution. The conceptual difference is important to understand if someone does not yet know it. But it's not an all or nothing set-in-stone thing. It implies there is a waterfall design to these ideas, as if some oracle posed these tasks to us and then we started finding solutions to each of them separately. But actually in many cases one and the same algorithm with small tweaks can tackle multiple tasks. Sometimes we have the hammer (algorithm) first and then the nails (task).
How you build your taxonomy and how you categorize one approach or another is not the same as learning and understanding. I always had an issue with this at university, where some lecturers would confuse learning lists like "what are the 3 areas of field X" or what are "the 4 principles of approach Y" etc.
The world is not structured according to subjects, fields, subfields etc. It's not a single hierarchy, but a big mess of similarities, like a graph or a multidimensional space. The map is not the territory and so on.
Terminology is necessary of course for communication and structuring books etc, but I like to see it merely as a utilitarian thing. The categories provide a scaffolding so that learning can happen. Studying the vocabulary and various outlines and nested hierarchies is a useful part of the journey but should not be confused with actually learning the thing itself. You could in principle learn all about regression without ever learning the word "regression".
The name actually originates from statistics, named after the "regression towards the mean" phenomenon, where they observed how the adult height of people is closer to the average compared to the height of their parents. So a tall person will have tall children but less extremely tall (in tendency, some will of course be even taller). So confusingly, regression literally means "going back".
Statistics :)
As a subfield in computer science, of course the concern has often been on algorithmic complexity and similar. But that is nascency exposed, in my view, and likely not representative of a fully mature field.
Armchair thought (not a historian of economics): I think Econometrics followed (and continues to follow) a similar evolution -- start with the goals (identification of model parameters, identifiability, KPIs), improve statistical validity and relevance, annotate dead ends or less common routes, continue on trucking.
Whenever I look at generic information (news, newspapers, generic articles), someone is taking a cloud of points and, bam!, draws a straight line through them. I actually reached to some authors to ask why they did that.
Answers (if any) were varied, I had I think one person who actually said that the data is expected to be linear. Many could not see the point, up to "if it looks like a line, then we put a line".
[1] https://en.wikipedia.org/wiki/Ordinary_least_squares#Matrix/...
Any advice on what I need to learn to even begin to understand what's written in section 2?
The intro video for linear regression of one variable is free (I think the whole course is free) and gives a good taste of what's in the course:
https://www.coursera.org/lecture/machine-learning/model-repr...