解题思路

• 将每条样本的“特征序列”看成由大写字母 A~G 组成的集合。按固定顺序 A B C D E F G 做 one-hot 编码：只要某个字母在序列中出现（次数不计），对应位置记为 1，否则为 0，得到长度为 7 的特征向量。
• 训练一个单层逻辑回归（Logistic Regression） 分类器： 预测值 p = sigmoid(w·x + b)；损失函数采用交叉熵；用**梯度下降（SGD，batch=1）**更新参数。题面给定超参：学习率 0.1，训练轮数 20，初始 w、b 全为 0。
• 预测阶段：对测试数据计算 p，阈值 0.5 二值化，p>0.5 输出 1，否则输出 0。
• 读入格式：第一行 N M；接着 N 行为训练样本（“字符串 标签”）；之后 M 行为仅含字符串的测试样本；输出 M 行预测标签。

复杂度分析

• 设训练样本数为 N、特征维度为 d=7、轮数为 E=20。

  • 时间复杂度：O(E * N * d)，题目范围下极小。
  • 空间复杂度：O(d)，仅存放权重与一个样本向量。

代码实现

Python

# -*- coding: utf-8 -*-
# 逻辑回归 + one-hot(A~G) 的ACM风格实现
import sys, math

# 将字母串编码为长度7的one-hot（出现即1，不计次数）
def encode(seq):
    x = [0.0] * 7
    seen = set(seq.strip())
    for ch in seen:
        idx = ord(ch) - ord('A')
        if 0 <= idx < 7:
            x[idx] = 1.0
    return x

# 训练：SGD，交叉熵损失，学习率0.1，轮数20
def train(X, y, lr=0.1, epochs=20):
    w = [0.0] * 7
    b = 0.0
    for _ in range(epochs):
        for xi, yi in zip(X, y):
            z = sum(w[j] * xi[j] for j in range(7)) + b
            p = 1.0 / (1.0 + math.exp(-z))
            dz = p - yi  # 交叉熵对z的导数
            # 参数更新（batch=1）
            for j in range(7):
                w[j] -= lr * dz * xi[j]
            b -= lr * dz
    return w, b

# 预测：p>0.5 -> 1，否则0
def predict(w, b, xi):
    z = sum(w[j] * xi[j] for j in range(7)) + b
    p = 1.0 / (1.0 + math.exp(-z))
    return 1 if p > 0.5 else 0

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it)); M = int(next(it))

    X, y = [], []
    # 读取N条训练数据
    for _ in range(N):
        seq = next(it)
        label = int(next(it))
        X.append(encode(seq))
        y.append(label)

    # 训练
    w, b = train(X, y, lr=0.1, epochs=20)

    # 读取并预测M条测试数据
    outs = []
    for _ in range(M):
        seq = next(it)
        xi = encode(seq)
        outs.append(str(predict(w, b, xi)))

    print("\n".join(outs))

if __name__ == "__main__":
    main()

Java

// 逻辑回归 + one-hot(A~G) 的ACM风格实现
import java.util.*;

public class Main {

    // 全局参数
    static double[] w = new double[7]; // 权重
    static double b = 0.0;             // 偏置

    // 将字母串编码为长度7的one-hot（出现即1，不计次数）
    static double[] encode(String s) {
        double[] x = new double[7];
        boolean[] seen = new boolean[7];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'A';
            if (0 <= idx && idx < 7) seen[idx] = true;
        }
        for (int i = 0; i < 7; i++) x[i] = seen[i] ? 1.0 : 0.0;
        return x;
    }

    // 训练：SGD，交叉熵损失，学习率0.1，轮数20
    static void train(ArrayList<double[]> X, ArrayList<Integer> Y) {
        double lr = 0.1;
        int epochs = 20;
        Arrays.fill(w, 0.0);
        b = 0.0;
        for (int ep = 0; ep < epochs; ep++) {
            for (int i = 0; i < X.size(); i++) {
                double[] xi = X.get(i);
                int yi = Y.get(i);
                double z = b;
                for (int j = 0; j < 7; j++) z += w[j] * xi[j];
                double p = 1.0 / (1.0 + Math.exp(-z));
                double dz = p - yi; // 交叉熵对z的导数
                for (int j = 0; j < 7; j++) {
                    w[j] -= lr * dz * xi[j];
                }
                b -= lr * dz;
            }
        }
    }

    // 预测：p>0.5 -> 1，否则0
    static int predict(double[] xi) {
        double z = b;
        for (int j = 0; j < 7; j++) z += w[j] * xi[j];
        double p = 1.0 / (1.0 + Math.exp(-z));
        return p > 0.5 ? 1 : 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNext()) return;
        int N = sc.nextInt();
        int M = sc.nextInt();

        ArrayList<double[]> X = new ArrayList<>();
        ArrayList<Integer> Y = new ArrayList<>();

        // 读取N条训练数据
        for (int i = 0; i < N; i++) {
            String seq = sc.next();
            int label = sc.nextInt();
            X.add(encode(seq));
            Y.add(label);
        }

        // 训练
        train(X, Y);

        // 读取并预测M条测试数据
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            String seq = sc.next();
            int pred = predict(encode(seq));
            sb.append(pred).append('\n');
        }
        System.out.print(sb.toString());
        sc.close();
    }
}

C++

// 逻辑回归 + one-hot(A~G) 的ACM风格实现
#include <bits/stdc++.h>
using namespace std;

vector<double> wgt(7, 0.0); // 权重
double bias = 0.0;          // 偏置

// 将字母串编码为长度7的one-hot（出现即1，不计次数）
vector<double> encode(const string& s) {
    vector<double> x(7, 0.0);
    vector<int> seen(7, 0);
    for (char c : s) {
        int idx = c - 'A';
        if (0 <= idx && idx < 7) seen[idx] = 1;
    }
    for (int i = 0; i < 7; ++i) x[i] = seen[i] ? 1.0 : 0.0;
    return x;
}

// 训练：SGD，交叉熵损失，学习率0.1，轮数20
void train(const vector<vector<double>>& X, const vector<int>& y) {
    double lr = 0.1;
    int epochs = 20;
    fill(wgt.begin(), wgt.end(), 0.0);
    bias = 0.0;
    for (int ep = 0; ep < epochs; ++ep) {
        for (int i = 0; i < (int)X.size(); ++i) {
            const vector<double>& xi = X[i];
            int yi = y[i];
            double z = bias;
            for (int j = 0; j < 7; ++j) z += wgt[j] * xi[j];
            double p = 1.0 / (1.0 + exp(-z));
            double dz = p - yi; // 交叉熵对z的导数
            for (int j = 0; j < 7; ++j) wgt[j] -= lr * dz * xi[j];
            bias -= lr * dz;
        }
    }
}

// 预测：p>0.5 -> 1，否则0
int predict(const vector<double>& xi) {
    double z = bias;
    for (int j = 0; j < 7; ++j) z += wgt[j] * xi[j];
    double p = 1.0 / (1.0 + exp(-z));
    return (p > 0.5) ? 1 : 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<vector<double>> X;
    vector<int> Y;

    // 读取N条训练数据
    for (int i = 0; i < N; ++i) {
        string seq; int label;
        cin >> seq >> label;
        X.push_back(encode(seq));
        Y.push_back(label);
    }

    // 训练
    train(X, Y);

    // 读取并预测M条测试数据
    for (int i = 0; i < M; ++i) {
        string seq; cin >> seq;
        cout << predict(encode(seq)) << "\n";
    }
    return 0;
}

题目内容

意图分类是一种常见的 $NLP$ 任多，现在需要实现一个基于逻辑回归的意图分类系统(二分类)。本系统的输入是一个已处理的特征序列，输出是意图标签 ( $0$ 或 $1$ )。请根据以下步骤实现该分类器：

1、数据预处理：对输入(特征序列，即仅包含大写字母 $ABCDEFG$ 的序列)进行 $one-hot$ 编码，编码时的特征顺序是 $ABCDEFG$；某个特征存在取 $1$ ，不存在取 $0$ ;

2、模型初始化：构造一个单层的训练网络，初始化权重 $w$ 和偏置 $b$ 初始化的值全部设为 $0$ ;

3、模型训练：使用 $Sigmoid$ 函数计算预测值，使用交叉熵损失函数训练，使用梯度下降算法更新参数；训练过程中使用训练数据进行训练，相关超参数为：学习率 $0.1$，训练轮数 $20$ ，$batch$ 大小为 $1$ ;

（1）$Sigmoid$ 函数公式:

$σ(z)=\frac{1}{1+e^{-z}}$ ，其中 $z=w·x+b$ （ $x$ 为输入特征向量）。

4.模型预测：对测试数据进行预测，首先使用 $sigmoid$ 函数计算预测值，然后做二值化处理(大于 $0.5$ 认为是类别 $1$ ，否则是类别 $0$ )

输入描述

第一行输入 $N$ 和 $M，N(10<=N<=100)$ 表示训练数据条数，$M(2<=M<=10)$ 表示测试数据条数；

接下来 $N$ 行是训练数据，每行包含两部分内容(空格隔开)，即代表输入的特征序列(由大写字母 $ABCDEFG$ 构成的字符串，长度范围是 $[3,7]$ )和该条数据的意图标签(使用数字 $0$ 或 $1$ 表示)；

在接下来 $M$ 行是测试数据的特征序列。

输出描述

输出有 $M$ 行，每行是测试输出，即用数字 $0$ 或 $1$ 表示的意图标签。

样例1

输入

10 2
CBG 0
AFE 0
FGD 1
BFG 0
BBA 0
BDD 0
BEG 1
EGE 0
CAF 0
DGD 1
DBA
DAD

输出

0
0

说明

该样例有 $10$ 条训练数据，$2$ 条测试数据，$2$ 个测试输出均 $0$

样例2

输入

10 3
GDEE 0
BDFEA 1
BDFE 0
GECD 0
DDCEE 1
ADA 0
EECBC 0
BACBC 1
DDD 1
FEEEE 0
AADC
BBAE
ECEC

输出

1
0
0

说明

该样例有 $10$ 条训练数据，$3$ 条测试数据，测试输出分别为 $1、0、0$ 。