解题思路

核心思路

按输入顺序做 $T$ 轮在线更新。对每条样本先算线性得分 $z=b+w\cdot x$，再过 $p=\dfrac{1}{1+e^{-z}}$（$|z|$ 过大时直接取 $0$ 或 $1$）。权重按 $w \leftarrow w-\eta\big((p-y)x+\lambda w\big)$ 更新，偏置只按 $b\leftarrow b-\eta(p-y)$ 更新，正则项不加在 $b$ 上。判定时把 $p$ 向下截断到 $k$ 位小数，再与 $\theta$ 比较。

实现方法

用双精度保存 $w,b$。每一条样本的梯度必须用更新前的 $w,b$ 计算后再写回。截断实现为 $\lfloor p\cdot 10^k\rfloor/10^k$。新请求逐条输出 $0$ 或 $1$。

题目内容

某推理服务为在线请求维护 KV 缓存页。已记录 $n$ 条历史请求，每条含 $d$ 维特征 $x_{i,1},\ldots,x_{i,d}$ 以及溢出标记 $y_i$（$1$ 表示本次导致缓存溢出，$0$ 表示命中已有页）。需要对 $m$ 条新请求判定溢出或命中。

权重 $w_1,\ldots,w_d$ 与偏置 $b$ 初值均为 $0$，按输入顺序做 $T$ 轮更新。每一轮扫完所有历史请求；每条先用更新前的 $w,b$ 计算 $p$，再写回：

• $z = b + \sum_{j=1}^{d} w_j x_{i,j}$
• $p = \dfrac{1}{1+e^{-z}}$。若 $z \ge 20$，取 $p=1$；若 $z \le -20$，取 $p=0$
• $w_j \leftarrow w_j - \eta\big((p-y_i)x_{i,j} + \lambda w_j\big)$，$j=1,\ldots,d$
• $b \leftarrow b - \eta(p-y_i)$

对每条新请求用最终 $w,b$ 同样计算 $p$，再令 $p' = \left\lfloor p \times 10^k \right\rfloor / 10^k$。若 $p' \ge \theta$ 则输出 $1$，否则输出 $0$。

输入描述

第一行四个整数 $n,m,d,T$。

第二行四个数 $\eta,\lambda,\theta,k$，其中 $k$ 为整数。

接下来 $n$ 行，第 $i$ 行 $d+1$ 个数：$x_{i,1},\ldots,x_{i,d},y_i$。

接下来 $m$ 行，每行 $d$ 个整数，为一条新请求的特征。

约束

$1 \le n,m \le 80$

$1 \le d \le 5$

$1 \le T \le 15$

$0 < \eta \le 1$

$0 \le \lambda \le 1$

$0 < \theta < 1$

$1 \le k \le 4$

特征为整数，绝对值不超过 $20$

$y_i \in \{0,1\}$

$\eta,\lambda,\theta$ 最多三位小数

输出描述

一行 $m$ 个整数，用空格分隔，依次为各新请求的判定结果。

样例1

输入

2 2 1 1
0.5 0 0.5 2
2 1
-1 0
2
-2

输出

1 0

说明

初始 $w_1=0$，$b=0$。

第 $1$ 轮第 $1$ 条：$z=0$，$p=0.5$。 $w_1 \leftarrow 0-0.5\times((0.5-1)\times 2)=0.5$，$b \leftarrow 0-0.5\times(0.5-1)=0.25$。

第 $1$ 轮第 $2$ 条：$z=0.25+0.5\times(-1)=-0.25$，$p\approx 0.437823$。 $w_1 \leftarrow 0.5-0.5\times(0.437823\times(-1))\approx 0.718912$，$b \leftarrow 0.25-0.5\times 0.437823\approx 0.031088$。

新请求 $2$：$z\approx 1.468912$，$p\approx 0.812892$，$p'=0.81\ge 0.5$，输出 $1$。

新请求 $-2$：$z\approx -1.406735$，$p\approx 0.196750$，$p'=0.19<0.5$，输出 $0$。

样例2

输入

2 3 1 2
0.2 0.1 0.6 2
1 0
0 1
-2
1
-3

输出

0 0 1

说明

第 $1$ 轮第 $1$ 条：$z=0$，$p=0.5$，更新后 $w_1=-0.1$，$b=-0.1$。

第 $1$ 轮第 $2$ 条 $x_1=0$：$z=-0.1$，$p\approx 0.475021$。 $w_1 \leftarrow -0.1-0.2\times(0.1\times(-0.1))=-0.098$，$b \leftarrow -0.1-0.2\times(0.475021-1)\approx 0.004996$。

第 $2$ 轮第 $1$ 条：$z\approx -0.093004$，$p\approx 0.476766$，更新后 $w_1\approx -0.191393$，$b\approx -0.090357$。

第 $2$ 轮第 $2$ 条：$z\approx -0.090357$，$p\approx 0.477426$，更新后 $w_1\approx -0.187565$，$b\approx 0.014157$。

新请求 $-2$：$p\approx 0.596111$，$p'=0.59<0.6$，输出 $0$。

新请求 $1$：$p\approx 0.456756$，$p'=0.45$，输出 $0$。

新请求 $-3$：$p\approx 0.640343$，$p'=0.64\ge 0.6$，输出 $1$。