CF2181L.LLM Training

You are given a text dataset. Your task is to train LLM (Large Language Model) and find the minimal possible loss. No kidding.

A text dataset is an array of texts $t_1, t_2, \ldots, t_n$. Each text $t_i$ is a sequence of tokens. We define the set of tokens $T$ as the set of all tokens that appear in at least one text $t_i$. Additionally, for each text $t_i$, there is a set of positions $L_i \subseteq {1, 2, \ldots, |t_i|}$. The token $t_i[j]$ is generated by LLM if $j \in L_i$ and is written by the user if $j \notin L_i$.

Let us define LLM with context size $k$ as a probabilistic model $P_k$, such that it defines the probability distribution of the next token of the sequence, depending on a context $w$ — a sequence of length between $0$ and $k$ (inclusive) whose elements are from $T$. Thus the probabilistic model $P_k$ is a large table of probabilities $P_k(\text{next} | w)$, defined for any context $w \in T^{*}$, $0 \leq |w| \leq k$ and any token $\text{next} \in T$. Conditions $0 \leq P_k(\text{next} | w) \leq 1$ and $\sum\limits_{\text{next} \in T} P_k(\text{next} | w) = 1$ should be satisfied.

The loss function of LLM with the context size $k$ is the following function defined for $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{next token}} \\ \\middle|\\ \\underbrace{t\_i\[\\max(1,j-k)\\,..\\,j-1\]}\_{\\text{context}} \\right)

Here $t_i[l\,..\,r] = t_i[l] t_i[l+1] \ldots t_i[r]$ is the substring from $l$-th to $r$-th token, $t_i[1\,..\,0]$ is an empty string. So, for each text and for each token that is generated by LLM, we add to the loss the negative logarithm (base 2) of the probability that this token will be generated, depending on the substring of previous $k$ tokens (or the whole prefix, if it has length less than $k$). If the probability is zero, we assume that the negative logarithm is $+\infty$. This loss function is known as the (base 2) Cross Entropy Loss over the LLM-generated positions. The smaller the loss function value $\mathcal{L}_k(P_k)$, the better LLM $P_k$ is.

For each $0 \leq k \lt \max\limits_{i=1..n} |t_i|$, calculate the minimum possible loss $\mathcal{L}_k(P_k)$ that could be obtained for some $P_k$ — LLM with context size $k$. It can be proved that this minimum is reachable and is not infinite.

你将获得一个文本数据集。你的任务是训练一个大语言模型（LLM），并找到可能的最小损失值。这可不是开玩笑。

一个文本数据集是一个文本序列 $t_1, t_2, \ldots, t_n$。每个文本 $t_i$ 是一个词元（token）序列。我们将词元集合 $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} \mid w)$，其定义域为任意上下文 $w \in T^{*}$（满足 $0 \leq |w| \leq k$）以及任意词元 $\text{next} \in T$。需满足条件：$0 \leq P_k(\text{next} \mid w) \leq 1$，且 $\sum\limits_{\text{next} \in T} P_k(\text{next} \mid 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 生成的词元，我们将该词元在以此前最多 $k$ 个词元（若前缀长度不足 $k$，则取整个前缀）为上下文条件下被生成的概率的负以 2 为底的对数加入损失值中。若该概率为零，则约定其负对数值为 $+\infty$。该损失函数被称为（以 2 为底的）交叉熵损失（Cross Entropy Loss），仅在 LLM 生成的位置上计算。损失函数值 $\mathcal{L}_k(P_k)$ 越小，说明 LLM $P_k$ 的性能越优。

对每个满足 $0 \leq k < \max\limits_{i=1..n} |t_i|$ 的整数 $k$，计算在某个上下文长度为 $k$ 的 LLM $P_k$ 上所能达到的最小可能损失 $\mathcal{L}_k(P_k)$。可以证明，该最小值一定可达，且不为无穷大。

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of texts in the dataset. Text descriptions follow.

The first line of the $i$-th text description contains a single integer $m_i$ ($1 \leq m_i \leq 3 \cdot 10^5$) — the length of $t_i$ ($m_i = |t_i|$).

The next line contains $m_i$ strings $t_{i}[1]$, $t_{i}[2]$, $\ldots$, $t_{i}[m_i]$ ($1 \leq |t_{i}[j]| \leq 5$) — tokens of the text $t_i$. Each token consists of symbols with ASCII codes from $33$ to $126$ (printable characters).

The next line contains a string $\ell_i$ of $m_i$ letters U and L, which encodes the set $L_i$. All positions with the letter L are generated by LLM, and all positions with the letter U are written by the user. So $L_i = {j\,|\,\ell_{i}[j] = \texttt{L}}$. It is guaranteed that the last token is generated by LLM, so $\ell_{i}[m_i] = \texttt{L}$.

It is guaranteed that the sum of $m_i$ for all $i$ ($1 \le i \le n$) does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $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$ 的各个词元（token）。每个词元均由 ASCII 码在 $33$ 到 $126$ 范围内的字符（即可打印字符）组成。

再下一行包含一个由 $m_i$ 个字母 U 和 L 组成的字符串 $\ell_i$，用于编码集合 $L_i$：所有对应位置为字母 L 的下标属于 $L_i$（即该位置词元由大语言模型生成），所有对应位置为字母 U 的下标则属于用户撰写部分。因此 $L_i = \{j \mid \ell_{i}[j] = \texttt{L}\}$。题目保证最后一个词元一定由大语言模型生成，即 $\ell_{i}[m_i] = \texttt{L}$。

题目保证对所有 $i$（$1 \le i \le n$）的 $m_i$ 之和不超过 $3 \cdot 10^5$。

Print $M = \max\limits_{i=1..n} m_i$ real numbers: for each $k = 0, 1, \ldots, M-1$ print the minimum possible loss $\mathcal{L}_k(P_k)$ for all possible $P_k$ — LLM with context size $k$.

Your answers will be accepted if their absolute or relative errors do not exceed $10^{-6}$; formally, if $p$ is your answer, and $q$ is the jury's answer, this should hold: $\frac{|p - q|}{\max{1, |q|}} \le 10^{-6}$.

输出 $M = \max\limits_{i=1..n} m_i$ 个实数：对每个 $k = 0, 1, \ldots, M-1$，输出所有可能的 $P_k$（即上下文长度为 $k$ 的大语言模型）所能达到的最小损失 $\mathcal{L}_k(P_k)$。

若您的答案绝对误差或相对误差不超过 $10^{-6}$，则视为正确；形式化地，若 $p$ 是您的答案，$q$ 是出题方的答案，则需满足：$\frac{|p - q|}{\max{1, |q|}} \le 10^{-6}$。