题目内容

某电商平台要根据用户的行为特征预测其是否会购买某类商品。

已知一批用户的历史行为数据：日均浏览时长、近 $30$ 天登录次数、平均加购次数等特征，以及最终是否购买（$0$ 表示未购买，$1$ 表示购买）。

请实现一个逻辑回归模型，用批量梯度下降完成训练，再对新用户给出购买预测。

1. sigmoid 函数

2. 逻辑回归模型

其中 $x=[1,x_1,x_2,\ldots,x_d]^T$ 为补上偏置项 $x_0=1$ 的特征向量，$\theta=[\theta_0,\theta_1,\ldots,\theta_d]^T$ 为参数向量。

3. 批量梯度下降

学习率 $\alpha=0.01$，固定迭代 $1000$ 轮，$m$ 为训练样本数。

4. 预测

对每个测试样本计算 $h_\theta(x)$：概率 $\ge 0.5$ 时预测为 $1$（购买），否则预测为 $0$（未购买）。

实现约定

• 训练前 $\theta$ 的全部 $d+1$ 个分量（含 $\theta_0$）都置为 $0$。
• 训练样本与测试样本都补上 $x_0=1$。
• 每一轮先用本轮开始时的参数算出所有训练样本的概率，求出各分量的平均梯度后再同时更新全部参数；不能逐样本更新，也不能让本轮后算的分量用到本轮已更新的分量。
• 完整执行 $1000$ 轮，不提前停止；不做正则化，也不做特征标准化。
• 使用双精度浮点数。为避免指数溢出，$z\ge 0$ 时用 $\sigma(z)=\dfrac{1}{1+e^{-z}}$，$z<0$ 时用 $\sigma(z)=\dfrac{e^{z}}{1+e^{z}}$，两式数学上等价。

输入描述

第一行两个整数 $N_{\mathrm{train}}$ 和 $N_{\mathrm{test}}$，表示训练样本数与测试样本数。

接下来 $N_{\mathrm{train}}$ 行，每行若干个浮点数：前 $d$ 个是特征值，最后一个是标签（$0$ 或 $1$）。特征维度 $d$ 不单独给出，等于每行数值个数减 $1$，所有训练行的 $d$ 相同。

接下来 $N_{\mathrm{test}}$ 行，每行 $d$ 个浮点数，表示一个测试样本的特征值（不含标签）。

输出描述

输出 $N_{\mathrm{test}}$ 行，每行一个整数 $0$ 或 $1$，依次为各测试样本的预测类别。

补充说明

数据范围

• $1\le N_{\mathrm{train}}\le 1000$
• $1\le N_{\mathrm{test}}\le 500$
• $1\le d\le 10$
• 特征值绝对值不超过 $10^4$
• 标签只会是 $0$ 或 $1$

解答要求

• 时间限制：C/C++ 1000ms，其他语言 2000ms。
• 内存限制：C/C++ 512MB，其他语言 1024MB。

样例1

输入

5 3
1 0
2 0
3 0
6 1
7 1
0
4
8

输出

0
1
1

说明

$d=1$。训练 $1000$ 轮后 $\theta\approx(-1.687,\,0.491)$。

测试样本 $0$：$h_\theta\approx0.156$，预测 $0$。

测试样本 $4$：$h_\theta\approx0.568$，预测 $1$（虽小于两类中点 $4.5$）。

测试样本 $8$：$h_\theta\approx0.904$，预测 $1$。

样例2

输入

6 2
0 1 0
1 0 0
1 1 0
3 4 1
4 3 1
4 4 1
1 2
3 3

输出

1
1

说明

$d=2$。训练后 $\theta\approx(-1.577,\,0.564,\,0.564)$。

测试样本 $(1,2)$：$h_\theta\approx0.529$，预测 $1$。

测试样本 $(3,3)$：$h_\theta\approx0.859$，预测 $1$。

样例3

输入

5 3
0.6 1.5 1.0 0
1.2 1.8 0.7 0
2.6 3.1 2.4 1
3.0 2.7 2.9 1
2.2 3.3 2.6 1
0.9 1.4 0.8
2.8 3.0 2.5
1.5 2.0 1.2

输出

0
1
1

说明

$d=3$。训练后 $\theta\approx(-1.085,\,0.690,\,-0.342,\,0.869)$。

三个测试样本的 $h_\theta$ 依次约为 $0.438$、$0.880$、$0.577$，按阈值 $0.5$ 得到 $0$、$1$、$1$。