题目内容

某银行计划利用简单的线性分类器对贷款申请人进行二分类，根据两个特征（例如年收入与负债率）将客户标记为“通过”或“拒绝”。现在给定一个训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$，其中 $x_i = (x_i^1,x_i^2)$ 是二维特征向量，$y_i \in \{1,-1\}$ 表示二分类标签。分类器采用线性函数 $f(x)=w\cdot x+b$，最终预测为 $\operatorname{sign}(f(x))$。

定义损失函数为所有被误分类的样本点到决策超平面 $w\cdot x+b=0$ 的总距离。对于误分类的样本 $(x_i,y_i)$，满足 $y_i(w\cdot x_i+b)\le 0$。此时该点到超平面的距离可表示为 $\frac{1}{\|w\|}|w\cdot x_i+b|$，且成立 $-y_i(w\cdot x_i+b)>0$。忽略常数系数后，取损失函数为 $L(w,b)=-\sum y_i(w\cdot x_i+b)$，其中求和仅对当前所有误分类样本进行。

为了最小化该损失，采用随机梯度下降法。对 $w$ 和 $b$ 求梯度可得：

因此参数更新规则为：

其中 $\eta$ 为学习率。初始时 $w$ 和 $b$ 均设为 $0$。训练时需要进行多轮迭代，每轮遍历全部样本，只对当前被误分类的样本累加梯度，一轮结束后统一更新参数。最终输出保留至多三位小数的权重 $(w_1,w_2)$ 和偏置 $b$。

约束条件：训练样本数目 $N$ 不超过 $10^4$，所有特征值与标签的绝对值不超过 $10^5$，迭代次数为正整数且不超过 $10^3$，学习率为正实数且不超过 $1$。

输入描述

通过标准输入读取数据。输入包含两行：第一行是一个列表，其中每个元素也是一个列表，包含一个由两个实数组成的特征向量（如元组 (x1,x2)）和一个标签（1 或 -1），形式为 [[(x1,x2),y], ...]；第二行是一个列表，包含两个数值，依次表示训练轮数（整数）和学习率（浮点数），形式为 [epoch, learning_rate]。

输出描述

向标准输出打印一个列表，包含三个保留三位小数的浮点数，依次为学习到的权重 $w_1$、$w_2$ 和偏置 $b$。输出格式为 [w1, w2, b]。

样例1

输入

[[(1,0),1],[(0,1),-1]]
[2,0.1]

输出

[0.1, -0.1, 0.0]

说明

初始 $w=(0,0)$, $b=0$，学习率 $\eta=0.1$。第 1 轮两个样本得分均为 $0$，满足 $y_i(w \cdot x_i + b) \le 0$，均被误分类。

累加梯度：$\sum y_i x_i = 1 \times (1,0) + (-1) \times (0,1) = (1,-1)$，$\sum y_i = 1 + (-1) = 0$。更新后 $w=(0.1,-0.1)$, $b=0$。

第 2 轮：样本 $(1,0)$ 得分 $0.1 > 0$，分类正确；样本 $(0,1)$ 得分 $-0.1$，$y \cdot score = 0.1 > 0$，分类正确。无误分类样本，参数不再更新。最终输出 $[0.1, -0.1, 0.0]$。

样例2

输入

[[(1,2),1],[(3,4),-1],[(2,1),1]]
[2,0.1]

输出

[0.3, 0.2, 0.3]

说明

初始 $w=(0,0)$, $b=0$，学习率 $\eta=0.1$。第 1 轮全部三个样本被误分类。累加梯度：$\sum y_i x_i = (1,2) + (-1)\times(3,4) + (2,1) = (0,-1)$，$\sum y_i = 1-1+1=1$。更新后 $w=(0,-0.1)$, $b=0.1$。

第 2 轮：样本 1 $(1,2)$ 得分 $-0.1 \le 0$，误分类；样本 2 $(3,4)$ 得分 $-0.3$，标签为 $-1$，$y \cdot score = 0.3 > 0$，正确；样本 3 $(2,1)$ 得分 $0.0 \le 0$，误分类。

误分类样本为 1 和 3，梯度累加：$\sum y_i x_i = (1,2)+(2,1)=(3,3)$，$\sum y_i = 2$。更新后 $w=(0.3,0.2)$, $b=0.3$。两轮结束，输出最终权重与偏置。

样例3

输入

[[(0,0),1]]
[5,0.5]

输出

[0.0, 0.0, 0.5]

说明

仅有一个样本，特征为 $(0,0)$，标签为 1。初始 $w=(0,0)$, $b=0$，学习率 $\eta=0.5$。

第 1 轮：得分 $0$，$y \cdot score = 0 \le 0$，误分类。梯度 $\sum y_i x_i = (0,0)$，$\sum y_i = 1$。更新后 $b = 0.5$，$w$ 保持 $(0,0)$。

后续轮次该样本得分 $0.5 > 0$，分类正确，不再更新。因此最终参数为 $w_1=0.0$, $w_2=0.0$, $b=0.5$，体现了单样本边界情形。