I understand the intuition of polynomial regression with higher degree are able to fit the data better, as it is able to decrease your bias but increases the variance. However, I am unable to proof them mathematically. Can anyone help to explain to me why this might be true, i.e it decreases $|| Y - X \beta ||^2 $ ? Thank you!
3
-
$\begingroup$ maybe we come from an intuitive point before goint into mathematics: a better fit reduces mean squared error! Is that clear or not yet? $\endgroup$– pythonic833Commented Apr 29, 2018 at 9:46
-
$\begingroup$ Hi pythonic833! After watching youtube.com/watch?v=fDQkUN9yw44, I understand that intuitively! However, I still could not justify it mathematically. $\endgroup$– JackCommented Apr 29, 2018 at 9:50
-
$\begingroup$ Why do you need a proof? When you set some coefficients to zero, the higher degree models turn into a simpler model. $\endgroup$– SmallChessCommented Apr 29, 2018 at 10:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Consider your matrix $X$ consists of one column vector $x_1$. That is, a single feature.
In linear regression, $\beta=(X^TX)^{-1}X^Ty=(x_1^Tx_1)^{-1}x_1^Ty$.
If you add a new variable $x_2$ of degree 2, obtaining $X_2$, then $$ y-X_2(X_2^TX_2)^{-1}X_2^Ty = y-x_1(x_1^Tx_1)^{-1}x_1^Ty -x_2(x_2^Tx_2)^{-1}x_2^T\tilde y_1 $$ where $\tilde y_1 = y-x_1(x_1^Tx_1)^{-1}x_1^Ty$.
For any matrix $X$, $\pi_X(y)=X(X^TX)^{-1}X^Ty$ is the orthogonal projection of $y$ onto the space spanned by the columns of $X$, which means that $|\pi_X(y)_i| \leq |y_i|$ for every $i$, where $y_i$ denotes the $i$-th entry of vector $y$.
This means that $$ \|y-X_2(X_2^TX_2)^{-1}X_2^Ty\|_2^2 \leq \|y-X(X^TX)^{-1}X^Ty \|_2^2 $$ Equality happens only when $x_1(x_1^Tx_1)^{-1}x_1^Tx_2=x_2$, that is, when the addition of column $x_2$ does not increase the rank of $X$.
More generally, if $X_n$ denotes the matrix resulting from adding polynomial variables up to degree $n$, then $$ y-X_n(X_n^TX_n)^{-1}X_n^Ty = y-X_{n-1}(X_{n-1}^TX_{n-1})^{-1}X_{n-1}^Ty -x_n(x_n^Tx_n)^{-1}x_n^T\tilde y_{n-1} $$ and the same reasoning applies.
If the inverse does not exist, one can replace $(X^TX)^{-1}X^T$ the Moore-Penrose pseudoinverse, $X^+$.
-
$\begingroup$ sorry, one more comment: there should be norms around your inequality. Otherwise it's not true in the general case $\endgroup$ Commented Apr 29, 2018 at 10:58
-
$\begingroup$ well I was not quite clear. you want to compare errors, so we are talking about scalars but in the general case you wrote this as a vector equation $\endgroup$ Commented Apr 29, 2018 at 11:11
-
$\begingroup$ Sorry, you were actually quite clear. I just read your comment wrong and was looking at an equality, rather than the inequality. $\endgroup$– cangrejoCommented Apr 29, 2018 at 11:13
-
$\begingroup$ now everything is fine! Nice answer! $\endgroup$ Commented Apr 29, 2018 at 11:16
$\begingroup$
$\endgroup$
Let's start with the connection of linear and polynomial regression
In linear regression you want to approximate $y$ with $X\beta$, meaning you take a linear comination of features:
$y = \beta_{0} + x_{1} \beta_{1} + \ldots + x_{n}\beta_{n}$.
In multinomial regression you take into account higher orders of $x_{k}$, thus $y = \beta_{0} + x_{1}\beta_{1} + x_{1}^{2}\beta_{12} + \ldots $.
So if we choose $\beta_{12}=0$ (and all other $\beta_{kj}$ which connect to higher orders of any$x_{k}$) then we end up with the linear regression.
What the regression does is to minimize the mean squared error: $L = \lVert y - \bar{y} \rVert$. Let's consider an multinomial regression. If the linear terms approximate $y$ the best and any nonlinear coefficient makes the fit worse (makes the total mean squared error higher) then this coefficient is set to zero and we end up with the linear regression. The other way round if nonlinearity is needed to approximate $y$, $\beta$ which minimizes MSE has terms like, e.g. $\beta_{12}$ which are not equal to zero.
This is not a mathematical proof but you could deduce one easily from what I wrote
