为您提供了一个文本数据集。你的任务是训练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}$$$。
示例
输入复制
451 + 1 = 2UUUUL51 + 2 = 3UUUUL52 + 1 = 3UUUUL52 + 2 = 4UUUUL
输出复制
6.000000000000 6.000000000000 4.000000000000 4.000000000000 0.000000000000
输入复制
44N E F <EOS>LLLL5N E R C <EOS>LLLLL6N E E R C <EOS>LLLLLL5I C P C <EOS>LLLLL
输出复制
55.683674395584 12.490224995673 8.000000000000 8.000000000000 8.000000000000 8.000000000000
输入复制
116a b a c a b a d b a b d a b a cULLULLLLLLULLLLL
输出复制
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
输入复制
24WA WA WA ACLULL4AC AC WA ACLLUL
输出复制
5.509775004327 4.754887502163 4.000000000000 2.000000000000