Linear Regression and Gradient Descent Optimization

Base（想跳可以跳

How does a model learn?

1. Supervised learning (监督学习):
   Given examples of data, learn a model that can estimate the value of label variables from feature variables.
2. Unsupervised learning (非监督学习):
   The given data is not labeled. And the model searches for patterns, but cannot assign meanings.

Goal for Supervised Learning:

1. Classification: predict a discrete label.
2. Regression: predict a ordered quantitative value.
   => So to optimize the model, we should solve 2 problems:
   1. Structure/Class ?
   2. Parameters ?

Funcion Classes

• Linear: $y = mx + b$
• Polynomial: $y = m_0 + m_1x + m_2x^2 + ... + m_nx^n$
• Exponential: $y = m(k)^x$
• Logarithmic: $y = log_k(x)$
• Logistic: $y = \frac{1}{1 + e^{-k(x - x_0)}}$

  • How to pick Class?

    1. Search the function space (搜索函数空间):
       逐一搜索每种函数形式以找到最优的模型【但这在计算上是不可行的..
    2. Domain knowledge (领域知识):
       比如经济学可能时对数，物理问题可能是指数函数..【但这太limited
    3. Visual inspection of data （数据可视化检查）:
       【高维数据不直观
    4. Occam's Razor (奥卡姆剃刀原则): 在所有可能的模型中，选择最简单的那个，最小化模型复杂度 -> 减少过拟合风险【但太简单可能不足以捕捉数据的复杂关系

  • How to pick Parameters?

    最小化预测值 y_pred 和真实值 y 的误差。常用的目标函数（Objective Function）:

    1. SAE (Sum of Absolute Errors)（绝对误差和）:
    $$SAE = \sum_{i=1}^{n} |y_{pred} - y|$$
    2. MSE (Mean Squared Error)（均方误差）:
    $$MSE = \frac{1}{n} \sum_{i=1}^{n} (y_{pred} - y)^2$$

一、Gradient Descent

For a linear univariate regression model:

$$y = mx + b$$

The MSE loss function:

$$L(m, b) = \frac{1}{n} \sum_{i=1}^{n} (y_{pred} - y)^2$$

Do partial derivatives for m / b independently:

$$\frac{\partial L}{\partial m} = \frac{1}{n} \sum_{i=1}^{n} -2x_i(y_i - (mx_i + b))$$ $$\frac{\partial L}{\partial b} = \frac{1}{n} \sum_{i=1}^{n} -2(y_i - (mx_i + b))$$

Then update the parameters (in which $\alpha$ is the learning rate):

$$m = m - \alpha \frac{\partial L}{\partial m}$$ $$b = b - \alpha \frac{\partial L}{\partial b}$$

Dynamic $\alpha$

Some options:

1. ↓ over time: $\alpha = \frac{1}{t}$
2. Increase while improving, decrease with error: $$\alpha_t = \begin{cases} 1.01 \alpha_t & \text{if } l(m_{t+1}) \leq l(m_t), \\ 0.5 \alpha_t & \text{if } l(m_{t+1}) > l(m_t). \end{cases}$$
3. Search for the best $\alpha$: $\alpha_{t+1} = \underset{\alpha}{\operatorname{argmin}} \ l(m_{t+1})$

Stochastic Gradient Descent (SGD)

Too many samples?
Use one or a subset of the data to calculate the gradient:

$$m_{new} = m_{old} - \frac{\alpha} {n} \sum_{i=1}^{n} -2x_i(y_i - (mx_i + b))$$

Overfitting

可能原因：

1. Too many parameters.(recording noise)
2. Too less data.
3. Lack of regularization.

Regularization

Cross Validation

Randomly divide the data into:

• Training set: Used to train the model.
• Validation set: Used to test whether the model can correctly predict the data, during the training process.

So that we can adjust the model parameters to minimize the error on the validation set during training.

But this cannot prevent overfitting. So we need Regularization.

L1 Regularization (Lasso)

$$J = MSE + \lambda \sum_{i=1}^{n} |m_i|$$

In which:

• $J$ is the new objective function.
• $\lambda$ is the regularization parameter, to control the importance of the regularization term.

为了减少过拟合，也就是为了让 $J$ 尽可能小，我们需要同时减小 $MSE$ 和 $\lambda \sum_{i=1}^{n} |m_i|$。
而MSE的减少是通过前面的梯度下降来实现的，所以我们只需要考虑如何减小 $\lambda \sum_{i=1}^{n} |m_i|$。

这就是L1(Lasso)正则化的Sparsity特性：

• 通过调整 $\lambda$ 的大小，可以将一些不重要的特征的权重变为0，从而减少特征的数量，提高模型的泛化能力。

HW3

作业中有提到LASSO在淘汰参数时的的参考：

1. F-Statisitc: 越大越显著
2. P-Value: 越小越显著
3. 方差：大不一定说明贡献大，但是小的话->取值范围窄->贡献有限 【3不一定准确，还是以其他判断方式为准】

L2 Regularization (Ridge)

$$J = MSE + \lambda \sum_{i=1}^{n} m_i^2$$

相比于L1, L2正则化的特性为Smoothness：

• 鼓励参数的权重尽可能小，但不会变为0。

二、Closed Form Solution（闭式解）

1. Ordinary Least Squares (OLS)

梯度下降的优化思路是：
为了优化 MSE --> 对MSE的参数求偏导 --> 重复直到收敛。

而闭式解：
为了优化 MSE = $\frac{1}{n} \sum_{i=1}^{n} (y_{pred} - y)^2$
--> 简单来说就是要优化残差平方和 RSS(Residual Sum of Squares) = $\sum_{i=1}^{n} (y_{pred} - y)^2$
--> 对于给定的数据集：

• X 为输入特征矩阵，包含m个样本，每个样本有n个特征 ($m \times n$)
• y 为输出目标变量 ($m \times 1$)
• $\beta$ 为特征权重向量 ($n \times 1$)
• $\epsilon$ 为误差项

线性回归模型可以表示为：

$$y = X\beta + \epsilon$$

--> 于是RSS可以表示为：

$$RSS = (y - X\beta)^T(y - X\beta)$$ $$= y^Ty - y^TX\beta - \beta^TX^Ty + \beta^TX^TX\beta$$

$y$ ($m \times 1$), 而$X^T\beta$ ($m \times 1$)，所以$y^TX\beta$是一个标量。标量的转置等于自身，所以：

$$y^TX\beta = (y^TX\beta)^T = \beta^TX^Ty$$

得：

$$RSS = y^Ty - 2y^TX\beta + \beta^TX^TX\beta$$

--> 为了minimize RSS，对$\beta$求导：

$$\frac{\partial RSS}{\partial \beta} = -2X^Ty + 2X^TX\beta$$

而：

正定矩阵什么的以后再说吧，总之就是这样喵..

所以令导数为0，得：

$$X^TX\beta = X^Ty$$ $$\beta = (X^TX)^{-1}X^Ty$$

然鹅，目前的问题是：

1. $X^TX$ 可能不可逆
2. 过拟合

2. Ridge Regression

原理差不多，只是在RSS后面加上了L2正则化项。就不过多推导了：

$$\beta = (X^TX + \lambda I)^{-1}X^Ty$$

在OLS的基础上，加上了$\lambda I$，in which $I$ 是单位（对角）矩阵

$X^TX + \lambda I$ 是正定矩阵，所以一定是可逆的。

Why we still use Gradient Descent?

计算量太大：
Closed Form Solution 光计算一个 $(X^TX)^{-1}$ 就需要 $O(n^3)$ 的时间复杂度，并且，还要求矩阵可逆（虽然已经在Ridge中解决了这个问题）。

反观GD，作为一个迭代的方法：

1. 适用于大数据集 - 不需要存储整个数据矩阵
2. 延展性 - 机器学习哪都能用，可不止regression

Evaluation

1. Objective Function: e.g. MSE

2. Variance Explained, aka $R^2$:

   $$R^2 = 1 - \frac{RSS}{TSS}$$

   所以呢，$R^2$ 也可以被称为 VE(Variance Explained)：

   $$VE = 1 - \frac{MSE[f(x)]}{Variance[y]}$$

   其中，$RSS = \sum_{i=1}^{n} (y_{pred} - y)^2$，$TSS = \sum_{i=1}^{n} (y - \bar{y})^2$，$\bar{y}$ 是y的均值。

   $R^2$ 越接近1，说明模型越好。