2023阿里巴巴全球数学竞赛预选赛题/决赛部分题个人解 (五)

应用与计算数学题 2. LLM Reward Collapse

给定一个特定的 prompt，让 LLM 生成  个回答。标注者将这  个回答从最好到最差排序。设  在  上强凹且单调递增，我们想训练一个 reward model，为第  个回答分配一个  的分数。奖励  应为如下优化问题的解：

(a) 证明

是凹的，并证明上述优化问题有唯一解 。

(b) 证明上述解满足：(1) ；(2) 对任意 ，。

(c) 设当  时， 的经验分布收敛于区间  上的概率测度 。此时优化问题即为

若  在一个概率测度  上取得最大值，证明： 不依赖于 。

(a) 与 (b)：该优化问题的解记为 。直接由定义得

因此  是凹的。特别地，上述不等式取等当且仅当对任意  都有 。由于  是递增的，因此 ，这说明优化问题的解是唯一的（若有两个不同的解 ，则  使得  更大）。

下面再证明最优解满足 。若不然，则存在  使得  但 。但此时考察

此时

这与  的最优性矛盾。

最后，令 ，则 ，故 。根据解的唯一性可知 ，因此 。

(c)  为最优解  在  时所收敛的概率测度，设其对应的概率密度为 ，其中  为常数。令

则

由于  在紧集  上连续，那么  也是连续的。因此，如果  不是常数，那么我们可以考虑  使得 ，，此时 ，矛盾。

下面的题赛时并没有选，只是出于个人喜好和某人一起做的。

组合与概率题 5. 证明：对任意 ，存在  使得任取 ，所有边数不少于  的  阶简单图包含一个圈  满足：其至少有  条弦。这里  是集合的势。（圈 中弦是一条边，其连接  中两个顶点但不属于  的边集 。）

先来吐槽这个题，一方面是因为专栏公式又要插不下了，另一方面是这是个 open problem，直到开赛前 3 天有一篇文章挂在 arxiv 上解决了这个问题（https://arxiv.org/abs/2306.09157)，就很离谱。