题目内容

路由器在执行数据转发任务时，其资源利用率与多项运行特征密切相关，这些特征包括协议连接数、转发数据包速率以及内存占用率。为了在不同负载条件下准确预测路由器的资源利用率，保障网络稳定运行，需要基于批量梯度下降法（BGD）训练一个用于资源预测的线性回归模型。

预测值由线性模型给出：

其中 $w_0$ 为偏置项，$w_1$、$w_2$、$w_3$ 为三个特征对应的权重。

训练目标是最小化均方误差（MSE）损失：

其中 $m$ 表示样本数量。

参数更新采用批量梯度下降。对于任意参数 $w_j$，更新规则为：

为了方便统一处理偏置项，令 $x_{i0}=1$。这里 $\alpha$ 表示学习率。

初始时所有参数（含偏置项）均设为 $0$，固定迭代 $N$ 次后停止，不进行收敛判断。

为了加快收敛速度，训练前需要对特征进行 Min-Max 归一化。对于特征维度 $x_j$（$j=1,2,3$），归一化后的值为：

其中 $\min(x_j)$ 和 $\max(x_j)$ 分别是该特征在所有样本中的最小值和最大值。若 $\max(x_j)=\min(x_j)$，则该特征归一化后的值取 $0$。

训练完成后，需要将归一化空间中的参数还原到原始特征空间。对于 $j=1,2,3$，如果 $\max(x_j)-\min(x_j)\neq 0$，则还原后的特征权重为：

否则 $w_j$ 取 $0$。最后还原偏置项：

约束条件：

• 样本数量 $m$ 为 $1$ 到 $10000$ 的整数。
• 迭代次数 $N$ 为 $1$ 到 $1000$ 的整数。
• 学习率 $\alpha$ 为 $0$ 到 $1$ 之间的浮点数，且保留 $2$ 位小数。
• 每个样本包含四个整数，依次为：协议连接数 $x_1$ 范围 $0$ 到 $1000$，转发数据包速率 $x_2$ 范围 $0$ 到 $10000$，内存占用率 $x_3$ 范围 $0$ 到 $100$，资源用量 $y$ 范围 $0$ 到 $10000$。

输入描述

第一行包含一个整数 $m$，表示样本数量。

第二行包含一个整数 $N$，表示 BGD 的迭代次数。

第三行包含一个浮点数 $\alpha$，表示学习率。

接下来 $m$ 行，每行包含四个整数，依次表示协议连接数 $x_1$、转发数据包速率 $x_2$、内存占用率 $x_3$ 和资源用量 $y$。

输出描述

输出一行，包含四个浮点数，依次为还原后的偏置项 $w_0$ 以及特征权重 $w_1$、$w_2$、$w_3$。所有数值保留 $2$ 位小数，采用银行家舍入，数字之间用一个空格分隔，行首和行尾不要有多余空格。

样例1

输入

1
1
0.50
10 20 30 8

输出

4.00 0.00 0.00 0.00

说明

样本数为 $1$，因此每个特征在所有样本中的最大值等于最小值。 按照归一化规则，三个特征归一化后的值都取 $0$。

初始参数全为 $0$，一次迭代中预测值为 $0$，误差为 $0-8=-8$。 偏置更新为 $w_0=0-0.50\times(-8)=4.00$。 由于归一化后特征恒为 $0$，三个特征权重的梯度均为 $0$，保持为 $0$。

还原时三个特征的极差均为 $0$，所以原始空间特征权重保持 $0$，偏置仍为 $4.00$。

样例2

输入

2
2
0.25
0 0 0 0
1 1 1 3

输出

0.52 0.56 0.56 0.56

说明

样本数为 $2$，三个特征在样本中的取值都为 $0$ 或 $1$，极差均为 $1$。 因此归一化后的两个样本为 $(0,0,0)$ 和 $(1,1,1)$。

第一次迭代开始时预测值均为 $0$。 两个样本的误差分别为 $0$ 和 $-3$，平均误差为 $-1.5$。 偏置更新为 $w_0 = 0 - 0.25\times(-1.5)=0.375$。 三个特征的平均梯度也均为 $-1.5$，所以归一化空间中的三个权重都更新为 $0.375$。

第二次迭代时，两个预测值分别为 $0.375$ 和 $0.375+3\times0.375=1.5$。 误差分别为 $0.375-0=0.375$ 和 $1.5-3=-1.5$。 偏置的平均误差为 $(0.375-1.5)/2=-0.5625$，更新为 $w_0=0.375-0.25\times(-0.5625)=0.515625$。 每个特征的平均梯度为 $-1.5/2=-0.75$，权重更新为 $0.375-0.25\times(-0.75)=0.5625$。

还原时极差均为 $1$，最小值均为 $0$，因此原始空间三个权重仍为 $0.5625$，偏置仍为 $0.515625$。 保留两位小数后得到 $0.52\ 0.56\ 0.56\ 0.56$。

样例3

输入

3
1
0.10
0 0 0 0
10 20 5 35
10 0 5 15

输出

1.67 0.17 0.06 0.33

说明

样本数为 $3$，三个特征的最小值都是 $0$，最大值分别为 $10$、$20$、$5$。 因此归一化后的三个样本为 $(0,0,0)$、$(1,1,1)$、$(1,0,1)$。

初始预测均为 $0$。 样本误差分别为 $0-0=0$、$0-35=-35$、$0-15=-15$，平均误差为 $-\frac{50}{3}$。 偏置更新为 $w_0=0-0.10\times(-\frac{50}{3})=\frac{5}{3}\approx1.67$。

特征 $x_1$ 的归一化取值为 $0,1,1$，加权误差和为 $0\times0+1\times(-35)+1\times(-15)=-50$，平均梯度为 $-\frac{50}{3}$，更新后归一化权重为 $\frac{5}{3}$，还原后除以极差 $10$ 得 $w_1=\frac{1}{6}\approx0.17$。

特征 $x_2$ 的归一化取值为 $0,1,0$，加权误差和为 $-35$，更新后归一化权重为 $0-0.10\times(-\frac{35}{3})=\frac{7}{6}$，除以极差 $20$ 得 $w_2=\frac{7}{120}\approx0.06$。

特征 $x_3$ 的归一化取值与 $x_1$ 相同，更新后归一化权重为 $\frac{5}{3}$，除以极差 $5$ 得 $w_3=\frac{1}{3}\approx0.33$。

所有特征最小值为 $0$，因此偏置还原后仍为 $\frac{5}{3}\approx1.67$。

样例4

输入

2
1
0.10
10 100 20 0
20 115 50 30

输出

-11.00 0.15 0.10 0.05

说明

样本数为 $2$，三个特征的最小值分别为 $10$、$100$、$20$，最大值分别为 $20$、$115$、$50$。 因此极差分别为 $10$、$15$、$30$。 归一化后的两个样本为 $(0,0,0)$ 和 $(1,1,1)$。

初始预测均为 $0$，两个样本的误差分别为 $0$ 和 $-30$。 平均误差为 $-15$，偏置更新为 $w_0=0-0.10\times(-15)=1.50$。 每个特征的平均梯度也为 $-15$，因此归一化空间中三个特征权重均更新为 $1.50$。

还原特征权重时分别除以极差： $w_1=1.50/10=0.15$， $w_2=1.50/15=0.10$， $w_3=1.50/30=0.05$。

偏置还原为 $w_0=1.50-(0.15\times10+0.10\times100+0.05\times20)=1.50-12.50=-11.00$。