IS CS-2021S-04

题目来源：Problem 4 日期：2024-08-04 题目主题：CS-机器学习-线性回归

解题思路

我们要解决的主要问题是通过给定的数据集找到一个线性预测器 $f(\mathbf{x})={\mathbf{w}}^{\mathbf{T}}\mathbf{x}$，使得预测误差的平方和最小化。给定了数据生成过程和噪声的假设，我们需要推导出最优权重向量 $\hat{\mathbf{w}}$，并分析在有噪声的情况下损失函数的期望。

Solution

Question 1: Express $\hat{\mathbf{w}}$ using $\mathbf{X},\mathbf{Y},\mathbf{\Phi }$, and $n$

To find the optimal weight vector $\hat{\mathbf{w}}$, we minimize the loss function $L(\mathbf{w})$ defined as:

$$L(\mathbf{w})=\frac{1}{2n}\sum _{i=1}^n(y_i-{\mathbf{w}}^{\mathbf{T}}{\mathbf{x}}_i{)}^2=\frac{1}{2n}\Vert \mathbf{Y}-\mathbf{Xw}{\Vert }_2^2.$$

To minimize $L(\mathbf{w})$, we take the derivative of $L(\mathbf{w})$ with respect to $\mathbf{w}$ and set it to zero:

$$\nabla L(\mathbf{w})=-\frac{1}{n}{\mathbf{X}}^{\mathbf{T}}(\mathbf{Y}-\mathbf{Xw})=0.$$

Solving for $\mathbf{w}$ gives:

$${\mathbf{X}}^{\mathbf{T}}\mathbf{Y}={\mathbf{X}}^{\mathbf{T}}\mathbf{Xw}.$$

Thus, the optimal weight vector $\hat{\mathbf{w}}$ is:

$$\hat{\mathbf{w}}=({\mathbf{X}}^{\mathbf{T}}\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathbf{T}}\mathbf{Y}={\mathbf{\Phi }}^{-1}\left(\frac{1}{n}{\mathbf{X}}^{\mathbf{T}}\mathbf{Y}\right).$$

Question 2: Express ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]$ in the form of $\frac{1}{2}\Vert \mathbf{w}-{\mathbf{w}}^{\ast }{\Vert }_{\mathbf{A}}^2+b$

To express ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]$, we first express $L(\mathbf{w})$:

$$L(\mathbf{w})=\frac{1}{2n}(\mathbf{Y}-\mathbf{Xw}{)}^{\mathbf{T}}(\mathbf{Y}-\mathbf{Xw}).$$

Using the data generation model $y_i={\mathbf{w}}^{\ast \mathbf{T}}{\mathbf{x}}_i+{ϵ}_i$, we can write $\mathbf{Y}=\mathbf{X}{\mathbf{w}}^{\ast }+\mathbf{e}$. Then:

$${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]=\frac{1}{2n}{\mathbb{E}}_{\mathbf{e}}\left[(\mathbf{X}{\mathbf{w}}^{\ast }+\mathbf{e}-\mathbf{Xw}{)}^{\mathbf{T}}(\mathbf{X}{\mathbf{w}}^{\ast }+\mathbf{e}-\mathbf{Xw})\right].$$

Expanding and using the properties of expectation:

$${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]=\frac{1}{2n}\left[(\mathbf{w}-{\mathbf{w}}^{\ast }{)}^{\mathbf{T}}{\mathbf{X}}^{\mathbf{T}}\mathbf{X}(\mathbf{w}-{\mathbf{w}}^{\ast })+{\mathbb{E}}_{\mathbf{e}}[{\mathbf{e}}^{\mathbf{T}}\mathbf{e}]\right].$$

Since $\mathbb{E}[\mathbf{e}]=0$ and $\mathbb{E}[\mathbf{e}{\mathbf{e}}^{\mathbf{T}}]={\sigma }^2\mathbf{I}$, we have:

$${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]=\frac{1}{2}\Vert \mathbf{w}-{\mathbf{w}}^{\ast }{\Vert }_{\mathbf{\Phi }}^2+\frac{{\sigma }^2}{2}.$$

Here, the matrix $\mathbf{A}$ is $\mathbf{\Phi }$ and the scalar $b$ is $\frac{{\sigma }^2}{2}$.

Question 3: Express ${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]-{\mathbb{E}}_{\mathbf{e}}[L(\hat{\mathbf{w}})]$ in the form of $\frac{{\sigma }^2}{2n}\mathbf{tr}(\mathbf{B})$

We have:

$${\mathbb{E}}_{\mathbf{e}}[L(\hat{\mathbf{w}})]=\frac{{\sigma }^2}{2n}.$$

Thus:

$${\mathbb{E}}_{\mathbf{e}}[L(\mathbf{w})]-{\mathbb{E}}_{\mathbf{e}}[L(\hat{\mathbf{w}})]=\frac{1}{2}(\mathbf{w}-{\mathbf{w}}^{\ast }{)}^{\mathbf{T}}\mathbf{\Phi }(\mathbf{w}-{\mathbf{w}}^{\ast })+\frac{{\sigma }^2}{2}-\frac{{\sigma }^2}{2n}.$$

Therefore, the matrix $\mathbf{B}$ is $\mathbf{\Phi }$.

Question 4: Explain what problem arises when $\mathbf{\Phi }$ is not a regular matrix and suggest a way to remedy the problem

When $\mathbf{\Phi }$ is not a regular matrix, it is singular and cannot be inverted. This usually happens when the features are linearly dependent, leading to multicollinearity. This makes the computation of $\hat{\mathbf{w}}$ unstable or impossible.

A common remedy is to add a regularization term to the loss function, which is known as Ridge Regression. The modified loss function becomes:

$$L(\mathbf{w})=\frac{1}{2n}\Vert \mathbf{Y}-\mathbf{Xw}{\Vert }_2^2+\frac{\lambda }{2}\Vert \mathbf{w}{\Vert }_2^2,$$

where $\lambda >0$ is a regularization parameter. The solution then becomes:

$$\hat{\mathbf{w}}=(\mathbf{\Phi }+\lambda \mathbf{I}{)}^{-1}\left(\frac{1}{n}{\mathbf{X}}^{\mathbf{T}}\mathbf{Y}\right).$$

知识点

机器学习线性回归最小二乘法岭回归

解题技巧和信息

在回归问题中，当自变量之间存在共线性问题时，使用岭回归可以增加模型的稳定性并避免参数过大。理解最小二乘法的优化问题如何转化为矩阵求解问题是非常重要的。此外，加入正则化项可以有效地解决过拟合问题。

重点词汇

• trace (迹) - 矩阵对角线元素之和
• regular matrix (正规矩阵) - 具有满秩的矩阵，即矩阵的行列式非零
• regularization (正则化) - 添加到损失函数的额外项，以约束模型复杂度并提高泛化能力

参考资料

1. The Elements of Statistical Learning, Trevor Hastie, Robert Tibshirani, and Jerome Friedman, Chap. 3
2. Pattern Recognition and Machine Learning, Christopher Bishop, Chap. 4