What is the intuition behind the idea that for linear regression, the number of observations should exceed the number of parameters?

Question

If a population model has k independent variables and 1 intercept, why are k+1 observations required to perform OLS estimates?

What is the intuition behind this?

Answer 1

Consider the simple case of drawing a straight line through two data points

Have a think about the case where you have only two data points (with different explanatory variables let us say). As you're no doubt aware, if you draw two data points on a plane, that is enough to draw a straight line through both points --- i.e., it fully defines a line-of-best-fit. This means that with two data points you can fit a simple linear regression model with an intercept and slope term (two parameters) and the line will go exactly through the data points. The drawback of this is that because there is no third data point, you cannot get any measure of how far from this line-of-best-fit the data will tend to deviate. Now, if you were to add a third data point then the line-of-best fit probably would not go exactly through all three of them, and so you would now be able to measure how far the data points fall from the line, giving you an idea not only of where the line-of-best-fit might fall, but also how far the data points tend to fall from this line.

Now extend this reasoning to the general case for $k=0,1,2,...$. If you have $k+1$ data points and $k+1$ parameters in your linear regression model (i.e., $k$ slope parameters plus an intercept term) then you can draw the line-of-best-fit$^\dagger$ exactly through the data and therefore there is no measure of variability around the regression line. With $k+2$ data points (i.e., one extra data point beyond what is needed for OLS estimation) you can begin to estimate the variability (very badly) and as you get more and more data points beyond this, you can estimate the line-of-best-fit and the variability around this line better and better. We refer to the excess of the number of data points above the number of model parameters as the "degrees-of-freedom" of the linear regression. More degrees-of-freedom allows better estimation of the regression line (representing the conditional expected value of the response) and better estimation of the regression standard error (representing the conditional standard deviation of the response).

---

$^\dagger$ Actually a plane for $k=2$ and a hyperplane for $k \geqslant 3$.

Answer 2

Welcome to CrossValidated. One way to think about the problem is to consider the case where the only predictor variable is categorical with $k$ levels. The typical coding used to fit this ANOVA-type model has an intercept and $k-1$ indicator variables, the latter corresponding to all but the first category. The $i$th indicator variable is 1 if $x=i+1$, 0 otherwise. Estimation of the intercept requires at least one observation in the first category, and estimation of the regression coefficients requires at least one observation in the category corresponding to each coefficient. This adds up to $k$ observations minimum.

Answer 3

Linear regression consists of trying to find $\beta_0, \beta_1, \beta_2 ... \beta_n$ such that $y = \beta_0+\beta_1x_1+\beta_2x_2+...+\beta_nx_n$. That's $n+1$ different $\beta$, so we need at least $n+1$ observations to find them.

Suppose there's a grocery store that charges you a base amount every time you make a purchase, plus the prices of what you bought. But they won't tell you what that base amount is, or what the prices of the food are. If you want to find out what the base amount and the prices are, you could go there once and buy nothing, go another time and buy just apples, then buy just oranges, etc. After going there $n+1$ times, where $n$ is the number of items available, you'd know what all the prices are.

Answer 4

First, you need k+1 observations for the regression to work at all, but you need a lot more than that to avoid overfitting. There are various rules of thumb. One is that you need 10 observations for every independent variable.

Why? Well, a regression line is a line through a space. If you have as many observations as you have dimensions, then the line can be fit perfectly, even with random data. This is easiest to see with 2 observations, where a straight line fits perfectly. (I'm not sure how to make a picture of this, but you can draw it on paper easily).

Or you can run this R code:

set.seed(1234)

x1 <- rnorm(4)
x2 <- rnorm(4)
x3<- rnorm(4)
y <- rnorm(4)

m1 <- lm(y~x1 + x2 + x3)
summary(m1)

and, while it does produce parameter estimates, the full output is a warning:

R version 4.2.0 (2022-04-22 ucrt) -- "Vigorous Calisthenics"
Copyright (C) 2022 The R Foundation for Statistical Computing
Platform: x86_64-w64-mingw32/x64 (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

[Workspace loaded from ~/.RData]

> ?t.test
> set.seed(1234)
> 
> sleep2 <- reshape(sleep, direction = "wide", 
+                   idvar = "ID", timevar = "group")
> t.test(Pair(extra.1, extra.2) ~ 1, data = sleep2)

    Paired t-test

data:  Pair(extra.1, extra.2)
t = -4.0621, df = 9, p-value = 0.002833
alternative hypothesis: true mean difference is not equal to 0
95 percent confidence interval:
 -2.4598858 -0.7001142
sample estimates:
mean difference 
          -1.58 

> head(sleep2)
  ID extra.1 extra.2
1  1     0.7     1.9
2  2    -1.6     0.8
3  3    -0.2     1.1
4  4    -1.2     0.1
5  5    -0.1    -0.1
6  6     3.4     4.4
> t.test(extra.1, extra.2)
Error in t.test(extra.1, extra.2) : object 'extra.1' not found
> t.test(extra.1, extra.2, data = sleep2)
Error in t.test(extra.1, extra.2, data = sleep2) : 
  object 'extra.1' not found
> t.test(extra~group, data = sleep)

    Welch Two Sample t-test

data:  extra by group
t = -1.8608, df = 17.776, p-value = 0.07939
alternative hypothesis: true difference in means between group 1 and group 2 is not equal to 0
95 percent confidence interval:
 -3.3654832  0.2054832
sample estimates:
mean in group 1 mean in group 2 
           0.75            2.33 

> ?Wilcoxon
> wilcox.test(extra~group, paired = true)
Error in eval(predvars, data, env) : object 'extra' not found
> wilcox.test(extra~group, paired = true, data = sleep)
Error in wilcox.test.default(x = DATA[[1L]], y = DATA[[2L]], ...) : 
  object 'true' not found
> wilcox.test(extra~group, paired = "true", data = sleep)
Error in paired || !is.null(y) : invalid 'x' type in 'x || y'
In addition: Warning messages:
1: In wilcox.test.default(x = DATA[[1L]], y = DATA[[2L]], ...) :
  cannot compute exact p-value with ties
2: In wilcox.test.default(x = DATA[[1L]], y = DATA[[2L]], ...) :
  cannot compute exact p-value with zeroes
> wilcox.test(Pair(extra.1, extra.2) ~ 1, data = sleep2)

    Wilcoxon signed rank test with continuity correction

data:  Pair(extra.1, extra.2)
V = 0, p-value = 0.009091
alternative hypothesis: true location shift is not equal to 0

Warning messages:
1: In wilcox.test.default(x = respVar[, 1L], y = respVar[, 2L], paired = TRUE,  :
  cannot compute exact p-value with ties
2: In wilcox.test.default(x = respVar[, 1L], y = respVar[, 2L], paired = TRUE,  :
  cannot compute exact p-value with zeroes
> set.seed(1234)
> 
> x1 <- rnorm(4)
> x2 <- rnorm(4)
> x3<- rnorm(4)
> x4<- rnorm(4)
> y <- rnorm(4)
> 
> m1 <- lm(y~z1 + x2 + x3)
Error in eval(predvars, data, env) : object 'z1' not found
> m1 <- lm(y~x1 + x2 + x3)
> m1

Call:
lm(formula = y ~ x1 + x2 + x3)

Coefficients:
(Intercept)           x1           x2           x3  
    -0.3677       0.4294      -0.8199      -0.8179  

> summary(m1)

Call:
lm(formula = y ~ x1 + x2 + x3)

Residuals:
ALL 4 residuals are 0: no residual degrees of freedom!

    Coefficients:
                Estimate Std. Error t value Pr(>|t|)
    (Intercept)  -0.3677        NaN     NaN      NaN
    x1            0.4294        NaN     NaN      NaN
    x2           -0.8199        NaN     NaN      NaN
    x3           -0.8179        NaN     NaN      NaN
    
    Residual standard error: NaN on 0 degrees of freedom
    Multiple R-squared:      1, Adjusted R-squared:    NaN 
    F-statistic:   NaN on 3 and 0 DF,  p-value: NA

And if we use 4 IVs, then we get similar output but with the additional warning that one coefficient cannot be estimated because of singularities.

Answer 5

Maybe a more algebraic answer next to all the excellent intuitive ones.

Recall that if we want the OLS estimator to be uniquely defined, we must be able to express it as $$ \hat\beta=(X'X)^{-1}X'y $$ Now, we then must of course have that the $(k\times k)$ matrix $(X'X)^{-1}$ exists. This requires $X'X$ to have rank $k$. Now, $$\text{rank}(X'X)=\text{rank}(X),$$ but, for any matrix, neither column and row rank can exceed the number of columns or rows, respectively, so that the rank cannot exceed the minimum of the number of rows and columns.

Hence, when $n<k$, $\text{rank}(X)\leq n<k$, so that the standard inverse of $X'X$ does not exist.

Copying my answer from Why is $n < p$ a problem for OLS regression?:

Suppose you want to fit a regression of $y_i$ on $x_i$, $x_i^2$ and a constant, i.e. $$ y_i = a x_i + b x_i^2 + c + u_i $$ or, in matrix notation, \begin{align*} \mathbf{y} = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}, \quad \mathbf{X} = \begin{pmatrix} 1 & x_1 & x_1^2 \\ \vdots & \vdots & \vdots \\ 1 & x_n & x_n^2 \end{pmatrix}, \quad \boldsymbol{\beta} = \begin{pmatrix} c \\ a \\ b \end{pmatrix}, \quad \mathbf{u} = \begin{pmatrix} u_1 \\ \vdots \\ u_n \end{pmatrix} \end{align*}

Suppose you observe $\mathbf{y}^T=(0,1)$ and $\mathbf{x}^T=(0,1)$, i.e., $n=2<k=3$.

Then, the OLS estimator would be

\begin{align*} \widehat{\boldsymbol{\beta}} =& \, (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} \\ =& \, \left[ \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix}^T \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix} \right]^{-1} \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix}^T \begin{pmatrix} 0 \\ 1 \end{pmatrix} \\ =& \, \left[\underbrace{\begin{pmatrix} 2 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}}_{\text{not invertible, as $\mathrm{rk}()=2\neq 3$}} \right]^{-1} \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \end{align*}

There are infinitely many solutions to the problem: setting up a system of equations and inserting the observations gives

\begin{align*} 0 =& \, a \cdot 0 + b \cdot 0^2 + c \ \ \Rightarrow c=0 \\ 1 =& \, a \cdot 1 + b \cdot 1^2 + c \ \ \Rightarrow 1 = a + b \end{align*} Hence, all $a=1-b$, $b \in \mathbb{R}$ satisfy the regression equation.

Answer 6

The simple answer is that regression is just another way of saying curve-fitting, and presuming that the fitting is to be done to a polynomial, then there needs to be the same number of data points as coefficients (or terms) of the fitted polynomial for there to be an exact fitting (or interpolation), and that it is impossible to so such an exact fitting if there are more data points (at least for a non-degenerate case).

Think of trying to fit a line to data points. If there are 2 points, then there is an exact line containing them - but for 3 points, unless there is the degenerate case of the points being collinear, there can only be a "best fit" regression to the points in which the sum of the squares of the error (i.e., the difference between the data point and where the fitting function is for the input variable) is minimized (and which has an elegant solution using critical values for a multivariate function for the coefficients).

Answer 7

A related question is Why are the residuals in $R^{n−p}$?.

A geometric interpretation of OLS is that the model space is the linear span of vectors and contains all the potential fitted values.

We need that each point in that space has a unique coordinate in terms of the model parameters (otherwise a prediction can be explained by multiple different sets of parameter values).

This means that the columns in the design matrix, that represents the predictors in the OLS model, are linearly independent. This requires that there are at least as many observations as parameters.

It is necessary condition but not a sufficient condition. A counterexample is when we have an intercept $x_0 =(1,1,1,1)$ and two predictors $x_1 = (1,1,0,0)$ and $x_2 = (0,0,1,1)$ with a model $y = a + b x_1 + c x_2$ then we can have multiple model values with the same solution. For example $a=1,b=1,c=1$ gives $y = (2,2,2,2)$ but also $a=2,b=0,c=0$ will give that $y = (2,2,2,2)$ answer.

The problem in that counterexample is that there is a linear dependence and we can write $x_0-x_1-x_2=0$.

---

Another complicating issue is that the observations need to be in a space that has sufficiently high dimensions. With OLS we often imagine independent normal distributed variables, but this may not need to be the case. The observations can be for instance discrete values and it might be possible that all the observed outcome values are equal to zero. Then we can have more than $k+1$ observations and a model space without dependent columns, and the fitting still doesn't work.

Answer 8

Let us complicate things a bit and take a look at another regression, the logistic regression, in an ML model that predicts a binary class. You might say that this is quite far-fetched, but you may get an intuition as well from this as this can show that your question is not just a problem of the linear regression, but can show up elsewhere in new guises, as discussed on meta at If someone asks "What is the intuition behind the idea that for linear regression, ...", does the answer have to be only about the linear regression?.

Linear regression

• OLS, from Ordinary least squares:

In statistics, ordinary least squares (OLS) is a type of linear least squares method for choosing the unknown parameters in a linear regression model (with fixed level-one effects of a linear function of a set of explanatory variables) by the principle of least squares: minimizing the sum of the squares of the differences between the observed dependent variable (values of the variable being observed) in the input dataset and the output of the (linear) function of the independent variable.

MLE as a tool to minimize the loss function of an ML model of a logistic regression

• loss function of a 0/1 classification, from logistic regression:

In machine learning applications where logistic regression is used for binary classification, the MLE minimises the cross-entropy loss function.

• MLE, from Maximum likelihood estimation:

The maximum likelihood estimator selects the parameter value which gives the observed data the largest possible probability (or probability density, in the continuous case). If the parameter consists of a number of components, then we define their separate maximum likelihood estimators, as the corresponding component of the MLE of the complete parameter.

Logistic regression is an important machine learning algorithm. The goal is to model the probability of a random variable Y being 0 or 1 given experimental data.

Wrap up

Wrapping this up, OLS is like MLE, the latter is just to make the best prediction so that the model's loss function hits its lowest value. You have to find the parameters that predict the best separation from one class to the other, and you will have a problem when rare features are needed to hit the rare observations (rare features crosses), since then, you can drop all of the other features and the model overfits since the MLE can become infinite (unconstrained).

In a linear regression, you just need to hit the best curve through the observations.

The weakness of the logistic regression is also its strength

In other words, the logistic regression makes a 0/1 decision from an asymptotic probabity function and therefore can fully hit any needed prediction as long as you give it enough parameters. Yet training with rare features does not always mean that it is well-trained for other observations yet to come.

This weakness of the logistic regression to overfit a model can be fought with regularization (sort of punishing), but it is better, if you have less features that do not set up these rare feature crosses and still predict rare observations with the right class. The weakness of the logistic regression is then also a strength! If you have unbalanced data, for example if you predict rare diseases of just 1 in a 10000, the logistic regression tries to overfit such rare features on rare observations, but this it also means the strength that it does not forget about these rare observations since it can gain up to "infinite points" for the MLE. If you manage to have so few features that you do not build up rare feature crosses but still have many enough that the maximization of the MLE is rewarded well enough for a rare disease, you do not need to unbalance your data. See Case-control sampling:

Logistic regression is unique in that it may be estimated on unbalanced data, rather than randomly sampled data, and still yield correct coefficient estimates of the effects of each independent variable on the outcome.

See for example Rare Feature Selection in High Dimensions:

It is common in modern prediction problems for many predictor variables to be counts of rarely occurring events. This leads to design matrices in which many columns are highly sparse.

Thus, the weakness is also a strength of the logistic regression.

Example

disease: 1 out of 10000

• features: 10 -> leads to a too broad prediction, the disease observations are not classified since the power of the rest is too big.
• features: 20 -> leads to a healthy balance between broad and narrow "multi-dimensional feature-observation clouds".
• features: 100 -> leads to some rare feature crosses, you overfit (~ sort of overtrain) the model only on the given disease observations and risk missing some disease observations of the future if the disease still comes also from some broad features (that might mirror some yet unknown rare feature or that might just be needed as well).

The first and the last bullets should be avoided in a good model unless you begin exploring the data and want to put the mainstream against the rare features, but you will gladly see that in the loss function that helps you find the best outcome with regularization and/or a new run with a lower or higher in dimensionality (less or more features).

Linking back to your question: avoid overfitting with feature reduction

If you know what you are doing, this is good to go. But if you just guess the number of features, try avoiding rare feature crosses, which are more likely the more features you add. Linking back to your question on the linear regression, if you add as many features as you have observations in a logistic regression of an ML model, you will get a matrix of some highly sparse columns, which is an overfit of the model so that it can tell you all and up to 100 % about the given observations but that cannot do so for the unknown future.

See Cross Validated Why is logistic regression particularly prone to overfitting in high dimensions?, for example the highest voted answer:

Perfect separation is more likely with more dimensions

... the model tries to predict as close to 0 and 1 as possible, by predicting values of μ that are as low and high as possible. To do this, it must set the regression weights, β as large as possible.

(but then leads to overfitting if β can become very large for rare feature crosses)

As a result, regularisation becomes more important when you have many predictors.

And here from my own answer - and I warn you that I am still not sure whether I understood this right (and by the way, this whole answer is on shaky grounds since I am not a professional):

In the usual case and in small dimensionality, a constrained MLE exists for each observation, it is calculated over a given number of observations that face a smaller number of features - thus it needs to be calculated by using constraints. With higher dimensionality, rare feature crosses arise where an unconstrained MLE exists, because parameters and observations become 1:1 cases then: one unique feature (~ parameter) = one isolated class assignment (~ observation). In these cases, those observations that are not mapped to just one feature lose their impact and need to be recovered by regularisation.

(Which would then tell us why we need to regularize such ML models during training to avoid overfitting.)

---

PS: Mind that "more features" does not just mean "new features of whatever", like "intelligence" and "weight" and "foot size", but it can also just mean higher dimensionalities of the same, already given features, like x1², x1³ and so forth from an x1="intelligence". Those higher dimensions will all have the role as stand-alone features even if they are mathematically correlated since they can strongly change the model accuracy.