Least Square Method (LSM) with L2 Regularization and Maximum A Posteriori (MAP) Estimation

Jul. 07, 2022

LSM with L2 regularization

对于具有$N$个样本点的最小二乘拟合问题，最小二乘损失函数的形式为1：

\[L(w)=\sum_{i=1}^N|w^Tx_i-y_i|^2\label{1-1}\]

并具有解析解，

\[\hat{w}=(X^TX)^{-1}X^TY\label{1-2}\]

其中，数据点$D={(x_1,y_1), (x_2, y_2), \cdots, (x_N, y_N)}$，且$x_i\in\mathbb{R}^p$，$y_i\in\mathbb{R}$，$i=1,2,\cdots, N$，拟合函数为$f(w)=w^Tx$。

但在实践中，当（1）样本点的数量$N$没有那么大，或者（2）$N$小于$x$的维度$p$时，式$\eqref{1-2}$就可能没有解析解。从数学的角度看，是因为式$\eqref{1-2}$中的矩阵$X^TX$不可逆；从机器学习实践的角度看，这种情况易造成过拟合现象。

为了解决最小二乘法的问题，通常会引入“正则化”的框架：在式$\eqref{1-1}$表示的损失函数中添加惩罚项（Penalty） $\lambda P(w)$，得到带正则化项的最小二乘法（Regularized LSE）：

\[\arg\max \limits_w \big[L(w)+ {\lambda P(w)}\big]\]

我们最常使用的是$L_1$惩罚项和$L_2$惩罚项：

\[\begin{align*} &L_1:P(w)=||w||_1\\ &L_2:P(w)=||w||_2^2=w^Tw\\ \end{align*}\]
  • $L_1$ 正则化的模型，即Lasso回归；
  • $L_2$ 正则化的模型，即Ridge回归（岭回归，亦称为权值衰减）。

在LSE的损失函数中引入$L_2$正则项后：

\[\begin{aligned} J(w)&=\sum_{i=1}^N||w^Tx_i-y_i||_2^2+\lambda w^Tw\\ &=(w^TX^TXw-2w^TX^TY+Y^TY)+\lambda w^Tw\\ &=w^T(X^TX+\lambda I)w-2w^TX^TY+Y^TY \end{aligned}\]

于是优化损失函数

\[\begin{align} \hat{w}&=\arg\min\limits_{w} J(w)\notag \\ &=\arg\min\limits_{w}\Big[\sum_{i=1}^N||w^Tx_i-y_i||^2_2+\lambda w^Tw\Big]\notag \\ &=\arg\min\limits_{w}\Big[ w^T(X^TX+\lambda I)w-2w^TX^TY+Y^TY\Big] \label{1-3} \end{align}\]

可以得到

\[\begin{aligned} &\dfrac{\partial J(w)}{\partial w}=2(X^TX+\lambda I)-2X^TY=0\\ \Rightarrow&\hat{w} = (X^TX+\lambda I)^{-1}X^TY \end{aligned}\label{1-4}\]

对于公式$\eqref{1-4}$中的矩阵$X^TX+\lambda I$：$X^TX$是半正定矩阵，$\lambda I$是对角阵，因此矩阵$X^TX+\lambda I$一定是正定的，$X^TX+\lambda I$一定可逆。因此，$L_2$正则化手段就解决了式$\eqref{1-2}$中的矩阵$X^TX$不可逆的问题，并且在实践中可以达到抑制过拟合现象的效果。


The relation between L2 regularized LSM and MAP

从参数估计的角度看，当噪声为服从零均值的正态分布时，极大似然估计法等价于最小二乘法1。

贝叶斯派对于参数估计的观点2

对于极大似然估计而言，未知参数（待估计参数）$\theta$ 就是一个简单的未知数，在抽样之前，我们对$\theta$没有任何了解，所有的信息都来自于样本。而贝叶斯派则不然，他们的出发点是：在进行抽样之前，我们已经对$\theta$有了一定的知识，叫做先验知识。并且，贝叶斯学派进一步要求：这种先验知识必须用$\theta$的某种概率分布表达出来。

仍然假设有拟合曲线$y=f(w)+\varepsilon=w^Tx+\varepsilon$，并且噪声服从分布$\varepsilon\sim N(0, \sigma^2)$；在此基础上，根据贝叶斯学派的观点假设对于待估参数$w$有一个先验估计$w\sim N(0,\sigma_0^2)$，则在已知$y$的情况下，可以得到后验估计$p(w\vert y)$：

\[p(w|y)=\dfrac{p(y|w)p(w)}{p(y)}\]

根据最大后验估计法（Maximum a posteriori estimation, MAP），有： \(\begin{align*} \hat{w}_{\mathrm{MAP}}&=\arg\max\limits_{w}\log \prod_{i=1}^Np(w|y_i)\\ &=\arg\max\limits_{w}\log \prod_{i=1}^N p(y_i|w)p(w)\\ &=\arg\max\limits_{w}\log \prod_{i=1}^N\Big[\dfrac1{\sqrt{2\pi}\sigma}\exp\{-\dfrac{(y_i-w^Tx_i)^2}{2\sigma^2}\}\dfrac1{\sqrt{2\pi}\sigma_0}\exp\{-\dfrac{w^2}{2\sigma_0^2}\}\Big]\\ &=\arg\min\limits_{w}\sum_{i=1}^N \Bigl[(y_i-w^Tx_i)^2+\dfrac{\sigma^2}{\sigma_0^2}||w||_2^2\Bigr]\\ (\mathrm{Let}:\lambda=\sigma^2/\sigma_0^2)&=\arg\min\limits_{w}\sum_{i=1}^N\Big[(y_i-w^Tx_i)^2+\lambda||w||_2^2\Big]\\ \end{align*}\)

即

\[\hat{w}_{\mathrm{MAP}}=\arg\min\limits_{w}\sum_{i=1}^N\Big[(y_i-w^Tx_i)^2+\lambda||w||_2^2\Big]\label{1-5}\]

式$\eqref{1-5}$与带有$L_2$正则项最小二乘法的形式$\eqref{1-3}$是一致的。


In closing

  1. 当（1）噪声为服从零均值的正态分布时$\varepsilon\sim N(0, \sigma^2)$，极大似然估计法等价于最小二乘法；
  2. 当（1）噪声为服从零均值的正态分布时$\varepsilon\sim N(0, \sigma^2)$，且（2）待估参数$w$的先验估计也服从零均值的正态分布时$w\sim N(0,\sigma_0^2)$，最大后验估计等价于带$L_2$正则化项的最小二乘法。


Reference

  1. View Least Square Method from Perspectives of Curve Fitting, Parameter Estimation, and Geometry Meaning of Solving Over-determined Equations. ˄ ˄2

  2. 陈希孺. 概率论与数理统计. 合肥: 中国科学技术大学出版社, 2009.2(2019.8重印). ˄