一元线性回归的梯度下降算法

博主： tony102
发布时间：2023 年 08 月 05 日
981 次浏览
暂无评论
4395字数
分类：机器学习

## 前言

第一次学习机器学习，比较 naive，希望大家多多指出我的问题。

机器学习的学习进度完成了 Week1，除了因为之前要带麓山的竞赛、每天要上五个小时日语课的原因，还有一个导致进度比较慢的原因是 Python 不太会用，所以学习了一个星期的 Python 后才重新开始学习这个课程。

## 一元线性回归

这个是比较基础的内容，简单记录一下。

高中的时候已经学会了用最小二乘法来估计 $\hat{y}$ 及其参数(parameter) $\hat{a}, \hat{b}$ 。简单来说就是要求一些一个点集的最佳拟合的直线（我的理解，表述不一定规范）。最佳拟合的定义是，我们有一个计算偏差值 (Error) 的函数，我们记为 $J$，那么 $J$ 满足：

$$
J(w,b) = \frac{1}{2n}\sum_{i=1}^n(\hat{y_i} - y_i)^2

其中 $(w,b)$ 是我们拟合的回归直线 $\hat{y} = wx+b$ 的两个参数。

不难发现，在一元线性回归的情况下，该式将会是一个开口向上的二次函数。

比较令人迷惑的地方是前面 $\frac{1}{2n}$ 的系数，不过等下子就能见识到它的含义。

我们的目的就是要求出一组 $(w,b)$ 使得 $\min_{J} J(w,b)$

## 梯度下降算法

### 我的理解

牛顿迭代机器学习版。

### 过程

以一元线性回归为例。

我们现在要求的是最小的 $J(w,b)$ ，而我们已经知道这是一个**开口向上的二次函数**，那么**实质上我们就是要求其导函数的零点**。这就是个牛顿迭代的过程。

具体地，我们每一次梯度下降实质上是更新两个参数 $(w,b)$

对于 $w$，有：

$$
w' = w - \alpha \frac{\partial{}}{\partial{w}} J(w,b)

对于 $b$，同理有：

$$
b' = b - \alpha \frac{\partial{}}{\partial{b}} J(w,b)

上述两式就是牛顿迭代的式子的形式。

#### 微分

$\frac{\partial{}}{\partial{w}} J(w,b)$ 我们管这一坨微分的式子来控制这一次我们更新参数的方向，也就是在 $(w,b)$ 这一点的导数。

假如把这个过程比作下山的话，这一坨式子就是控制方向的。

#### 学习率 $\alpha$

首先是，$\alpha \in (0,1)$

$\alpha$ 的大小决定了我们这一次下降的大小，如果 $\alpha$ 比较大，那么减号后面的式子对参数更新结果的影响也同样比较大。

假如把这个过程比作下山的话，这一个参数就控制了我们下山步伐的大小。

最终，我们重复用上面的式子对结果进行更新，直到某一定次数以后结果收敛 (converge) 为止。

P.S. 这个地方的收敛不是极限里面的收敛。这个地方大概是指，当我们更新到一个更加接近答案的位置的时候，我们微分那一块会减小，因为导数将接近 $0$，同时我们的 $\alpha$ 也会减小。所以这样保证我们一定会有一个答案，可能这就是这里收敛的含义。但是你也许会问，诶呀呀，那我这个是个多峰函数怎么办。我还没有尝试，但是应该可以更改我们下降的起点来控制。有待后续研究。

接下来我们来探讨一些细节。

### 梯度下降函数的实现

#### 公式推导

首先我们要来求这两个式子应该怎么计算。以 $w$ 的为例：

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{\partial{}}{\partial{w}} \frac{1}{2n} \sum_{i=1}^{n} (f_{w,b} (x^{(i)} ) - y^{(i)})^2

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{\partial{}}{\partial{w}} \frac{1}{2n} \sum_{i=1}^{n} (wx^{(i)} + b - y^{(i)})^2

把括号内的式子展开可以得到：

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{1}{2n} \sum_{i=1}^{n} ((2x^{(i)})^2 + 2x^{(i)} b - 2 x^{(i)}y^{(i)})

这个时候这个“莫名其妙的系数” $\frac{1}{2n}$ 而不是 $\frac{1}{n}$ 的妙处就展现出来了——每一项都可以消掉一个 $2$ 的系数。这样一来减少了不少次的乘法。考虑到 Python 的乘法使用 FFT 实现的，对常数的优化应该是不错的。（没有实测，理论推测）

最终，我们将这个式子化为

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{1}{n} \sum_{i=1}^{n} x^{(i)} (f_{w,b}(x^{(i)}) - y^{(i)})

同理可以得到 $\frac{\partial{}}{\partial{b}} J(w,b)$ ，此处不再赘述。

#### 实现

```python
import math
import copy
import numpy as np

x_train = np.array([])
y_train = np.array([])

def calcCost(x, y, w, b):
    n = x.shape[0]
    print(n)
    cost = 0
    for i in range(n):
        f = w * x[i] + b
        cost += (f - y[i]) ** 2
    return 1.00 / (2.00 * n) * cost

def calcGradient(x, y, w, b):
    n = x.shape[0]
    dw = 0.00
    db = 0.00
    for i in range(n):
        f = w * x[i] + b
        tmp_dw = (f - y[i]) * x[i]
        tmp_db = f - y[i]
        dw = dw + tmp_dw
        db = db + tmp_db
    dw = dw / n
    db = db / n
    return dw, db

def gradientDescent(x, y, w_in, b_in, alpha, calcGradient):
    w = copy.deepcopy(w_in)
    b = b_in; w = w_in
    for t in range(1000000):
        dw, db = calcGradient(x, y, w, b)
        b = b - alpha * db
        w = w - alpha * dw
    return w, b

with open('my_data_x.txt', 'r') as f:
    siz = list(map(int, f.read().split()))
x_train.resize(int(siz[0]))
for i in range(1, int(siz[0]) + 1):
    x_train[i - 1] = int(siz[i])
print(x_train)

with open('my_data_y.txt', 'r') as f:
    siz = list(map(int, f.read().split()))
y_train.resize(int(siz[0]))
for i in range(1, int(siz[0]) + 1):
    y_train[i - 1] = int(siz[i])
print(y_train)

res_w, res_b = gradientDescent(x_train, y_train, 0.00, 0.00, 1.0e-2, calcGradient)
print(f"{res_w:8.4f} {res_b:8.4f}")
```

## 实践中遇到的若干问题

实践中，只要多尝试几组参数，那么肯定可以遇到这样的情况

```
RuntimeWarning: invalid value encountered in scalar subtract
  w = w - alpha * dw
     nan      nan
```

这个地方是 `RuntimeWarning` 而不是 `Error` 的原因是，使用了 NumPy 与原生数据类型运算后导致的。

实际问题是出现了分母为 $0$ 的情况。

想一想问题出现在了哪里。假如初始的 $(w,b)$ 不变的情况下，微分部分的结果由函数本身决定，唯一可以控制的变量在于 $\alpha$ 学习率。一番尝试发现是，学习率过大导致的。比较稳妥的学习率要调到 $10^{-2}$ 级别左右。样本点比较均匀分布在直线两侧的情况下，迭代次数不应该少于 $10^5$

## 感想

实现了人生第一个机器学习算法，虽然大部分东西也是以前接触过的东西，但是还是很兴奋。

发现自己微积分的知识还没有被高考摧残掉。想起组里面其他同学是没有搞微积分这一块内容的。高一是被 Karry5307 逼着卷多项式内容，虽然后面学会出了大纲直接给多项式判了死刑。但是学习多项式的同时附带解决了很多数学问题是令人受益匪浅的。其中就有微积分的内容。

至于偏微分为什么还记得？高考的时候做基本不等式基本不会，只能用拉格朗日乘数法来代替求解。

最后修改：2023 年 08 月 05 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了
Yanws
牢师求更新

一元线性回归的梯度下降算法

tony102 • 2023 年 08 月 05 日

## 前言

第一次学习机器学习，比较 naive，希望大家多多指出我的问题。

## 一元线性回归

这个是比较基础的内容，简单记录一下。

$$
J(w,b) = \frac{1}{2n}\sum_{i=1}^n(\hat{y_i} - y_i)^2

其中 $(w,b)$ 是我们拟合的回归直线 $\hat{y} = wx+b$ 的两个参数。

不难发现，在一元线性回归的情况下，该式将会是一个开口向上的二次函数。

比较令人迷惑的地方是前面 $\frac{1}{2n}$ 的系数，不过等下子就能见识到它的含义。

我们的目的就是要求出一组 $(w,b)$ 使得 $\min_{J} J(w,b)$

## 梯度下降算法

### 我的理解

牛顿迭代机器学习版。

### 过程

以一元线性回归为例。

具体地，我们每一次梯度下降实质上是更新两个参数 $(w,b)$

对于 $w$，有：

$$
w' = w - \alpha \frac{\partial{}}{\partial{w}} J(w,b)

对于 $b$，同理有：

$$
b' = b - \alpha \frac{\partial{}}{\partial{b}} J(w,b)

上述两式就是牛顿迭代的式子的形式。

#### 微分

$\frac{\partial{}}{\partial{w}} J(w,b)$ 我们管这一坨微分的式子来控制这一次我们更新参数的方向，也就是在 $(w,b)$ 这一点的导数。

假如把这个过程比作下山的话，这一坨式子就是控制方向的。

#### 学习率 $\alpha$

首先是，$\alpha \in (0,1)$

$\alpha$ 的大小决定了我们这一次下降的大小，如果 $\alpha$ 比较大，那么减号后面的式子对参数更新结果的影响也同样比较大。

假如把这个过程比作下山的话，这一个参数就控制了我们下山步伐的大小。

最终，我们重复用上面的式子对结果进行更新，直到某一定次数以后结果收敛 (converge) 为止。

接下来我们来探讨一些细节。

### 梯度下降函数的实现

#### 公式推导

首先我们要来求这两个式子应该怎么计算。以 $w$ 的为例：

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{\partial{}}{\partial{w}} \frac{1}{2n} \sum_{i=1}^{n} (f_{w,b} (x^{(i)} ) - y^{(i)})^2

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{\partial{}}{\partial{w}} \frac{1}{2n} \sum_{i=1}^{n} (wx^{(i)} + b - y^{(i)})^2

把括号内的式子展开可以得到：

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{1}{2n} \sum_{i=1}^{n} ((2x^{(i)})^2 + 2x^{(i)} b - 2 x^{(i)}y^{(i)})

最终，我们将这个式子化为

$$
\frac{\partial{}}{\partial{w}} J(w,b) = \frac{1}{n} \sum_{i=1}^{n} x^{(i)} (f_{w,b}(x^{(i)}) - y^{(i)})

同理可以得到 $\frac{\partial{}}{\partial{b}} J(w,b)$ ，此处不再赘述。

#### 实现

```python
import math
import copy
import numpy as np

x_train = np.array([])
y_train = np.array([])

def calcCost(x, y, w, b):
    n = x.shape[0]
    print(n)
    cost = 0
    for i in range(n):
        f = w * x[i] + b
        cost += (f - y[i]) ** 2
    return 1.00 / (2.00 * n) * cost

with open('my_data_x.txt', 'r') as f:
    siz = list(map(int, f.read().split()))
x_train.resize(int(siz[0]))
for i in range(1, int(siz[0]) + 1):
    x_train[i - 1] = int(siz[i])
print(x_train)

with open('my_data_y.txt', 'r') as f:
    siz = list(map(int, f.read().split()))
y_train.resize(int(siz[0]))
for i in range(1, int(siz[0]) + 1):
    y_train[i - 1] = int(siz[i])
print(y_train)

res_w, res_b = gradientDescent(x_train, y_train, 0.00, 0.00, 1.0e-2, calcGradient)
print(f"{res_w:8.4f} {res_b:8.4f}")
```

## 实践中遇到的若干问题

实践中，只要多尝试几组参数，那么肯定可以遇到这样的情况

```
RuntimeWarning: invalid value encountered in scalar subtract
  w = w - alpha * dw
     nan      nan
```

这个地方是 `RuntimeWarning` 而不是 `Error` 的原因是，使用了 NumPy 与原生数据类型运算后导致的。

实际问题是出现了分母为 $0$ 的情况。

## 感想

实现了人生第一个机器学习算法，虽然大部分东西也是以前接触过的东西，但是还是很兴奋。

至于偏微分为什么还记得？高考的时候做基本不等式基本不会，只能用拉格朗日乘数法来代替求解。

一元线性回归的梯度下降算法

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Universal Few-Shot Learning of Dense Prediction Tasks with Visual Token Matching

CCPC2023（深圳）游记

CF1278F Cards

Discretization process for State Space Model of Mamba

Contest: AtCoder Beginner Contest 223(ABC223)

一元线性回归的梯度下降算法

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

一元线性回归的梯度下降算法

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款