最小二乘法的概率解释
对于多元高斯分布，假设协方差矩阵\(\Sigma = \sigma^2 I\)，概率密度为 \[ p(y|\mu, \sigma^2) = \frac{1}{(2\pi \sigma^2)^{\frac{n}{2}}}\exp\left(-\frac{1}{2\sigma^2}(y-\mu)^\mathsf{T}(y-\mu)\right) \] 假设\(\mu = Xw\)，求解\(w\)的最大似然，会得到什么？实际上还是求解 \[ \hat{w}_{\rm ML} = \mathop{\rm arg}\max_w - \frac{1}{2\sigma^2} |\!|y-Xw|\!|^2 \] 即最小二乘和最大似然的解是一样的
最大似然隐含的意思在于，误差\(\epsilon_i = y_i - x_i^\mathsf{T}w\)是独立的高斯噪声，等价于以下三种说法：
- \(y_i = x_i^\mathsf{T}w + \epsilon_i,\ \ \epsilon_i \mathop{\sim}^{iid}N(0,\sigma^2), i = 1,\ldots,n\)
- \(y_i \mathop{\sim}^{ind} N(x_i^\mathsf{T}w, \sigma^2), i = 1, \ldots, n\)
- \(y \sim N(Xw, \sigma^2I)\)
如果我们假设了有\(y \sim N(Xw, \sigma^2I)\)，根据此分布，我们可以计算最大似然解的期望，有 \[\begin{align*} \mathbb{E}[w_{\rm ML}] &= \mathbb{E}[(X^\mathsf{T}X)^{-1}X^\mathsf{T}y]\ \ （最小二乘中w的解析解） \\ &= \int [(X^\mathsf{T}X)^{-1}X^\mathsf{T}y]p(y|X,w)dy\ \ （连续随机变量的期望E[g(X)] = \int_{-\infty}^{\infty} g(x)f_X(x)dx）\\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}\int yp(y|X,w)dy \\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}\mathbb{E}[y] \\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}Xw \ \ (y \sim N(Xw, \sigma^2I)) \\ &= w \end{align*}\]
即最大似然估计\(w_{\rm ML}\)是\(w\)的一个无偏估计。但是要考虑到还有方差的存在，如果方差很大的话，即便期望是无偏的，也很可能会看到比较奇怪的值，因此需要对方差做一个判断。
如果有\(y \sim N(\mu, \Sigma)\)，则 \[ {\rm var}[y] = \mathbb{E}[(y-\mathbb{E}[y])(y-\mathbb{E}[y])^\mathsf{T}] = \Sigma \] 代入\(\mathbb{E}[y] = \mu\)，有 \[\begin{align*} {\rm var}[y] &= \mathbb{E}[(y-\mu)(y-\mu)^\mathsf{T}] \\ &= \mathbb{E}[yy^\mathsf{T} - y\mu^\mathsf{T} - \mu y^\mathsf{T} + \mu\mu^\mathsf{T}] \\ &= \mathbb{E}[yy^\mathsf{T}] - \mathbb{E}[y]\mu^\mathsf{T} - \mu \mathbb{E}[y^\mathsf{T}] + \mu\mu^\mathsf{T} \\ &= \mathbb{E}[yy^\mathsf{T}] - \mu\mu^\mathsf{T} - \mu \mu^\mathsf{T} + \mu\mu^\mathsf{T} \\ &= \mathbb{E}[yy^\mathsf{T}] - \mu\mu^\mathsf{T} \end{align*}\]
即\(\mathbb{E}[yy^\mathsf{T}] = \Sigma + \mu\mu^\mathsf{T}\)
因此可以计算\(w\)的方差，即 \[\begin{align*} {\rm var}[w_{\rm ML}] &= \mathbb{E}[(w_{\rm ML}-\mathbb{E}[w_{\rm ML}])(w_{\rm ML}-\mathbb{E}[w_{\rm ML}])^\mathsf{T}] \\ &= \mathbb{E}[w_{\rm ML}w_{\rm ML}^\mathsf{T}] - \mathbb{E}[w_{\rm ML}]\mathbb{E}[w_{\rm ML}]^\mathsf{T} \end{align*}\]
由于\(w = (X^\mathsf{T}X)^{-1}X^\mathsf{T}y\)且\(\mathbb{E}[w_{\rm ML}] = w\)，而且\((X^\mathsf{T}X)\)是对称矩阵，其逆也是对称矩阵，因此\(((X^\mathsf{T}X)^{-1})^\mathsf{T} = (X^\mathsf{T}X)^{-1}\)。带入到上面可知 \[\begin{align*} {\rm var}[w_{\rm ML}] &= \mathbb{E}[(X^\mathsf{T}X)^{-1}X^\mathsf{T}yy^\mathsf{T}X(X^\mathsf{T}X)^{-1}]-ww^\mathsf{T} \\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}\mathbb{E}[yy^\mathsf{T}]X(X^\mathsf{T}X)^{-1} - ww^\mathsf{T} \end{align*}\]
由于\(\mathbb{E}[yy^\mathsf{T}] = \Sigma + \mu\mu^\mathsf{T}\)且\(y \sim N(Xw, \sigma^2I)\)，即\(\mu = Xw, \Sigma = \sigma^2 I\)，因此
\[\begin{align*} {\rm var}[w_{\rm ML}] &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}\mathbb{E}[yy^\mathsf{T}]X(X^\mathsf{T}X)^{-1} - ww^\mathsf{T} \\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T} (\Sigma + \mu\mu^\mathsf{T}) X(X^\mathsf{T}X)^{-1} - ww^\mathsf{T} \\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T} (\sigma^2I + Xww^\mathsf{T}X^\mathsf{T}) X(X^\mathsf{T}X)^{-1} - ww^\mathsf{T} \\ &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}\sigma^2IX(X^\mathsf{T}X)^{-1} + (X^\mathsf{T}X)^{-1}X^\mathsf{T}Xww^\mathsf{T}X^\mathsf{T}X(X^\mathsf{T}X)^{-1}- ww^\mathsf{T} \end{align*}\] 由于\(\sigma^2\)是标量可以提出来，因此上式可以化简为 \[ {\rm var}[w_{\rm ML}] = \sigma^2(X^\mathsf{T}X)^{-1} \]
因此在如果我们假设\(y\)满足高斯分布，即\(y \sim N(Xw, \sigma^2I)\)，就有 \[ \mathbb{E}[w_{\rm ML}] = w,\ \ {\rm var}[w_{\rm ML}] = \sigma^2(X^\mathsf{T}X)^{-1} \] 如果\(\sigma^2(X^\mathsf{T}X)^{-1}\)太大，那么\(w_{\rm ML}\)就会敏感于\(y\)的值，不利于用其做预测
岭回归
由于方差的存在，\(w\)可能会变得很大，而这是我们所不希望看到的。因此可以在目标函数上加一个正则项来控制\(w\)的大小，即类似下式这样的形式： \[ w_{\rm OPT} = {\rm arg}\min_w |\!|y-Xw|\!|^2 + \lambda g(w) \] 其中\(\lambda > 0\)是正则化参数，\(g(w) > 0\)是惩罚函数，将\(w\)引向所希望的性质。具体地，对于岭回归，有 \[ w_{\rm RR} = {\rm arg}\min_w |\!|y-Xw|\!|^2 + \lambda |\!|w|\!|^2 \] 其中\(g(w) = |\!|w|\!|^2\)对大的\(w\)进行了惩罚。注意到目标函数的第二项和第一项之间存在着平衡关系，由\(\lambda\)控制。如果\(\lambda \rightarrow 0\)，则\(w_{\rm RR} \rightarrow w_{\rm LS}\)；如果\(\lambda \rightarrow \infty\)，则\(w_{\rm RR} \rightarrow 0\)
求解析解可得 \[\begin{align*} \mathcal{L} &= |\!|y-Xw|\!|^2 + \lambda |\!|w|\!|^2 \\ &= (y - Xw)^\mathsf{T}(y-Xw) + \lambda w^\mathsf{T}w \\ \nabla_w \mathcal{L} &= -2X^\mathsf{T}y + 2X^\mathsf{T}Xw + 2\lambda w = 0 \\ \Rightarrow w_{\rm RR} &= (\lambda I + X^\mathsf{T}X)^{-1}X^\mathsf{T}y \end{align*}\]
使用岭回归之前需要对数据先做预处理： \[\begin{align*} y &\leftarrow y - \frac{1}{n}\sum_{i=1}^n y_i \\ x_{ij} &\leftarrow \frac{x_{ij} - \bar{x}_{.j}}{\hat{\sigma}_j} \\ \hat{\sigma}_j & = \sqrt{\frac{1}{n} \sum_{i=1}^n (x_{ij} - \bar{x}_{.j})^2} \end{align*}\]
对岭回归的进一步分析
可以通过奇异值分解SVD来进一步探索最小二乘法和岭回归之间的关系。SVD的核心理论是对于任何\(n\times d\)矩阵\(X\)（假设\(n>d\)），都可以将其分解为\(X=USV^\mathsf{T}\)，其中
- \(U: n \times d\)正交矩阵，即\(U^\mathsf{T}U=I\)
- \(S: d \times d\)非负对角矩阵，即\(S_{ii}\ge 0\)且对\(i \not= j\)有\(S_{ij} = 0\)
- \(V: d \times d\)正交矩阵，即\(V^\mathsf{T}V = VV^\mathsf{T} = I\)
因此可以得出以下等式 \[ X^\mathsf{T}X = (USV^\mathsf{T})^\mathsf{T}(USV^\mathsf{T}) = VS^2V^\mathsf{T}, XX^\mathsf{T} = US^2U^\mathsf{T} \\ (X^\mathsf{T}X)^{-1} = (VS^2V^\mathsf{T})^{-1} = VS^{-2}V^\mathsf{T} \]
因此\(w\)的方差可以重写为 \[ {\rm var}[w_{\rm LS}] = \sigma^2(X^\mathsf{T}X)^{-1} = \sigma^2VS^{-2}V^\mathsf{T} \] 如果对某个\(i\)，\(S_{ii}\)特别小，那么其逆会特别大，导致方差变大（这说明\(X\)中的一些列有很高的相关性） 同时，对新的数据进行最小平方预测，结果为 \[ y_{\rm new} = x_{\rm new}^\mathsf{T}w_{\rm LS} = x_{\rm new}^\mathsf{T}(X^\mathsf{T}X)^{-1}X^\mathsf{T}y = x_{\rm new}^\mathsf{T}VS^{-1}U^\mathsf{T}y \] 也可以看出来如果\(S^{-1}\)很大，则预测结果会不稳定
可以推导出最小二乘得出的权重和岭回归得出的权重之间的关系： \[\begin{align*} w_{\rm RR} &= (\lambda I + X^\mathsf{T}X)^{-1}X^\mathsf{T}y \\ &= (\lambda I + X^\mathsf{T}X)^{-1}(X^\mathsf{T}X)(X^\mathsf{T}X)^{-1}X^\mathsf{T}y \\ &= (\lambda I + X^\mathsf{T}X)^{-1}(X^\mathsf{T}X)w_{\rm LS} \\ &= [(X^\mathsf{T}X)(\lambda(X^\mathsf{T}X)^{-1} + I)]^{-1}(X^\mathsf{T}X)w_{\rm LS} \end{align*}\] 由于对于两个对称矩阵有\((AB)^{-1} = B^{-1}A^{-1}\)，因此 \[\begin{align*} w_{\rm RR} &= [(X^\mathsf{T}X)(\lambda(X^\mathsf{T}X)^{-1} + I)]^{-1}(X^\mathsf{T}X)w_{\rm LS} \\ &= (\lambda(X^\mathsf{T}X)^{-1} + I)^{-1}(X^\mathsf{T}X)^{-1}(X^\mathsf{T}X)w_{\rm LS} \\ &= (\lambda(X^\mathsf{T}X)^{-1} + I)^{-1}w_{\rm LS} \end{align*}\]
代入奇异值分解的结果，且考虑\(VV^\mathsf{T}=I\)，有
\[\begin{align*} w_{\rm RR} &= (\lambda(X^\mathsf{T}X)^{-1} + I)^{-1}w_{\rm LS} \\ &= (\lambda VS^{-2}V^\mathsf{T} + I)^{-1}w_{\rm LS} \\ &= (V(\lambda S^{-2}V^\mathsf{T}+V^\mathsf{T}))^{-1}w_{\rm LS} \\ &= (V(\lambda S^{-2} + I)V^\mathsf{T})^{-1}w_{\rm LS} \\ &= V(\lambda S^{-2} + I)^{-1}V^\mathsf{T}w_{\rm LS} \\ &:= VMV^\mathsf{T}w_{\rm LS} \end{align*}\]
其中\(M_{ii} = \frac{S_{ii}^2}{\lambda + S_{ii}^2}\)
也可以把奇异值分解的结果带入到\(w_{\rm LS}\)的求解中
\[\begin{align*} w_{\rm LS} &= (X^\mathsf{T}X)^{-1}X^\mathsf{T}y \\ &= VS^{-2}V^\mathsf{T}VS^\mathsf{T}U^\mathsf{T}y \\ &= VS^{-2}SU^\mathsf{T}y \\ &= VS^{-1}U^\mathsf{T}y \end{align*}\]
代入到上式，有 \[ w_{\rm RR} = VS_{\lambda}^{-1}U^\mathsf{T}y,\ \ S_{\lambda}^{-1} = \left[\!\begin{array}{rrr} \frac{S_{11}}{\lambda+S_{11}^2}&&0\\ &\ddots&\\ 0&&\frac{S_{dd}}{\lambda+S_{dd}^2} \end{array}\!\right] \]
岭回归也可以看作是最小二乘的一个特例情况。如果如下定义\(\hat{y} \approx \hat{X}w\)，即 \[ \left[\begin{array}{c} y \\ 0 \\ \vdots \\ 0 \end{array}\right] \approx \left[\begin{array}{ccc} - & X & - \\ \sqrt{\lambda} & & 0 \\ & \ddots & \\ 0 & & \sqrt{\lambda} \end{array}\right] \left[\begin{array}{c} w_1 \\ \vdots \\ w_d \end{array}\right] \] 如果对这个回归问题求解\(w_{\rm LS}\)，则找到了原始回归问题的\(w_{\rm RR}\) \[\begin{align*} (\hat{y} - \hat{X}w)^\mathsf{T}(\hat{y} - \hat{X}w) &= (y-Xw)^\mathsf{T}(y-Xw) + (\sqrt{\lambda}w)^\mathsf{T}(\sqrt{\lambda}w) \\ &= |\!|y-Xw|\!|^2 + \lambda |\!|w|\!|^2 \end{align*}\]
