← 返回题目列表

Codeforces · 2181/L

L. 法学硕士培训

中文机器翻译题面 查看原题

为您提供了一个文本数据集。你的任务是训练LLM(大型语言模型)并找到最小可能的损失。不开玩笑。

文本数据集是文本数组 $$$t_1, t_2, \ldots, t_n$$$。每个文本 $$$t_i$$$ 都是一个标记序列。我们将标记集 $$$T$$$ 定义为至少一个文本 $$$t_i$$$ 中出现的所有标记的集合。此外,对于每个文本 $$$t_i$$$,有一组位置 $$$L_i \subseteq \{1, 2, \ldots, |t_i|\}$$$。如果 $$$j \in L_i$$$,则令牌 $$$t_i[j]$$$ 由 LLM 生成;如果 $$$j \notin L_i$$$,则由用户写入。

让我们将上下文大小 $$$k$$$ 的 LLM 定义为概率模型 $$$P_k$$$,这样它就可以根据上下文 $$$w$$$ 定义序列的下一个标记的概率分布 - 长度在 $$$0$$$ 和 $$$k$$$(含)之间的序列,其元素来自 $$$T$$$。因此,概率模型 $$$P_k$$$ 是一个大型概率表 $$$P_k(\text{next} | w)$$$,为任何上下文 $$$w \in T^{*}$$$, $$$0 \leq |w| 定义\leq k$$$ 和任何标记 $$$\text{next} \in T$$$。应满足条件 $$$0 \leq P_k(\text{next} | w) \leq 1$$$ 和 $$$\sum\limits_{\text{next} \in T} P_k(\text{next} | w) = 1$$$。

上下文大小$$$k$$$的LLM损失函数是为$$$P_k$$$定义的以下函数:

$$\mathcal{L}_k(P_k) \,\, = \,\, \sum_{i=1}^{n} \,\, \sum_{j\in L_i} \, -\log_2 P_k\!\left( \underbrace{t_i[j]}_{\text{下一个标记}} \ \middle|\ \underbrace{t_i[\max(1,j-k)\,..\,j-1]}_{\text{上下文}} \right)$$

这里 $$$t_i[l\,..\,r] = t_i[l] t_i[l+1] \ldots t_i[r]$$$ 是从 $$$l$$$ 到第 $$$r$$$ 的子串,$$$t_i[1\,..\,0]$$$ 是一个空字符串。因此,对于每个文本和 LLM 生成的每个标记,我们将生成该标记的概率的负对数(以 2 为底)添加到损失中,具体取决于先前 $$$k$$$ 标记的子字符串(或整个前缀,如果其长度小于 $$$k$$$)。如果概率为零,我们假设负对数为 $$$+\infty$$$。该损失函数称为 LLM 生成位置的(以 2 为底)交叉熵损失。损失函数值$$$\mathcal{L}_k(P_k)$$$越小,LLM $$$P_k$$$越好。

对于每个 $$$0 \leq k \lt \max\limits_{i=1..n} |t_i|$$$,计算对于某些 $$$P_k$$$ — 具有上下文大小 $$$k$$$ 的 LLM 可以获得的最小可能损失 $$$\mathcal{L}_k(P_k)$$$。可以证明这个最小值是可达的,并且不是无限的。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数据集中的文本数量。文字说明如下。

第 $$$i$$$ 文本描述的第一行包含一个整数 $$$m_i$$$ ($$$1 \leq m_i \leq 3 \cdot 10^5$$$) — $$$t_i$$$ 的长度 ($$$m_i = |t_i|$$$)。

下一行包含 $$$m_i$$$ 字符串 $$$t_{i}[1]$$$, $$$t_{i}[2]$$$, $$$\ldots$$$, $$$t_{i}[m_i]$$$ ($$$1 \leq |t_{i}[j]| \leq 5$$$) — 文本的标记$$$t_i$$$。每个标记均由 ASCII 代码从 $$$33$$$ 到 $$$126$$$(可打印字符)的符号组成。

下一行包含 $$$\ell_i$$$ 个 $$$m_i$$$ 字母的字符串 U 和 L,对集合 $$$L_i$$$ 进行编码。所有带有字母的职位 L 由LLM生成,所有带有字母的职位 U 由用户写入。所以$$$L_i = \{j\,|\,\ell_{i}[j] = \texttt{L}\}$$$。保证最后一个token是由LLM生成的,所以$$$\ell_{i}[m_i] = \texttt{L}$$$。

保证所有 $$$i$$$ ($$$1 \le i \le n$$$) 的 $$$m_i$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

打印 $$$M = \max\limits_{i=1..n} m_i$$$ 实数:对于每个 $$$k = 0, 1, \ldots, M-1$$$ 打印所有可能的 $$$P_k$$$ 的最小可能损失 $$$\mathcal{L}_k(P_k)$$$ - 上下文大小 $$$k$$$ 的 LLM。

如果您的答案的绝对或相对误差不超过$$$10^{-6}$$$,则您的答案将被接受;正式地,如果 $$$p$$$ 是你的答案,$$$q$$$ 是陪审团的答案,则应成立:$$$\frac{|p - q|}{\max\{1, |q|\}} \le 10^{-6}$$$。

示例

输入
复制

4
5
1 + 1 = 2
UUUUL
5
1 + 2 = 3
UUUUL
5
2 + 1 = 3
UUUUL
5
2 + 2 = 4
UUUUL

输出
复制

6.000000000000
6.000000000000
4.000000000000
4.000000000000
0.000000000000

输入
复制

4
4
N E F <EOS>
LLLL
5
N E R C <EOS>
LLLLL
6
N E E R C <EOS>
LLLLLL
5
I C P C <EOS>
LLLLL

输出
复制

55.683674395584
12.490224995673
8.000000000000
8.000000000000
8.000000000000
8.000000000000

输入
复制

1
16
a b a c a b a d b a b d a b a c
ULLULLLLLLULLLLL

输出
复制

22.595941331507
12.464393446710
5.245112497837
2.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000

输入
复制

2
4
WA WA WA AC
LULL
4
AC AC WA AC
LLUL

输出
复制

5.509775004327
4.754887502163
4.000000000000
2.000000000000