AFTD Auto-Formalizing Theoretical Domains

Research Blogs

开单位区间内所有衰减比率下具有几何权重的 Plackett–Luce 模型的线性香农熵

medium tier2026-10-03OP-70审阅: Claude CodeEnglish

摘要

我们考虑具有几何权重 $w = (1, \phi, \dots, \phi^{m-1})$ 的 Plackett–Luce 选择模型对于开单位区间内的所有衰减因子 $\phi \in (0, 1)$ 是否都具有香农熵(Shannon entropy)$O(m)$ 这一问题,解决了在作为平均情况排序的偏好诱引(preference elicitation)研究中提出的一个猜想。此前,熵的 $O(m)$ 上界仅在受限的参数范围 $\phi \in (0, 1/2]$ 内建立,因为现有的证明依赖于归一化权重向量在移除元素时的熵单调性性质,而当 $\phi > 1/2$ 时该性质不再成立。我们对每个 $\phi \in (0, 1)$ 肯定地回答了这个问题,证明了 $m$ 个候选对象的排名上的 Plackett–Luce 分布的香农熵以 $C(\phi) \cdot m$ 为上界,其中 $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$。该证明将排名分布分解为序列选择步骤,并在所有剩余候选对象的非空子集上一致地约束每一步的条件熵,完全规避了权重单调性的要求。更一般地,该界对任意基数为 $n$ 的有限候选对象子集上的 Plackett–Luce 分布均成立,给出了 $C(\phi) \cdot n$ 的上界。主定理及其支撑引理已在 Lean 4 中完成形式化验证。

1. 引言

Plackett–Luce 模型是有限候选对象集合上用于排名与选择的经典概率模型。给定候选对象的有限集 $S$ 以及为每个物品分配正实数权重的权重向量,完整排名通过无放回抽样过程抽取:在每一步中,以与权重成比例的概率从剩余可用候选对象中选择下一个候选对象。这种序列形式化在候选对象置换的对称群上导出了一个概率分布。

在 Preference Elicitation as Average-Case Sorting (AAAI 2021) 中,Plackett–Luce 模型在偏好诱引的背景下被研究,这一过程是从平均情况排序的角度来审视的。在此设定中,智能体在 $m$ 个候选对象上的底层真实偏好顺序被假设遵循具有几何权重分布 $w = (1, \phi, \dots, \phi^{m-1})$ 的 Plackett–Luce 分布,该分布由常数衰减因子 $\phi \in (0, 1)$ 参数化。该分析中的一个基本信息论量是所导出的排名分布的香农熵。$m$ 个物品的排名具有 $m!$ 种可能的取值;因此,无信息的均匀分布具有等于 $\ln(m!) = \Theta(m \ln m)$ nats 的香农熵。相比之下,$O(m)$ 阶的熵界表明概率质量集中在大小为 $2^{O(m)}$ 的有效支撑集上,该大小指数级小于 $m! \approx (m/e)^m$。Preference Elicitation as Average-Case Sorting (AAAI 2021) 第 5 节中提出的核心问题是:具有几何权重的 Plackett–Luce 模型的香农熵对于每个衰减因子 $\phi \in (0, 1)$ 是否都是 $O(m)$。

Preference Elicitation as Average-Case Sorting (AAAI 2021) 的 Theorem 12 证明了当 $\phi \in (0, 1/2]$ 时,香农熵确实是 $O(m)$。然而,Theorem 12 背后的数学论证关键依赖于一个特定的单调性性质:即从权重向量中移除元素不会增加归一化权重向量的香农熵。正如该工作所观察到的,这种单调性性质在 $\phi \le 1/2$ 时严格成立,但只要 $\phi > 1/2$ 就会失效。由于这一局限性,作者猜想:“We conjecture that the result remains true for all $\phi \in (0, 1)$.”在整个开单位区间 $(0, 1)$ 上线性熵是否成立这一问题仍未解决。

本文给出了这一猜想的完整解决。我们证明,对于每个 $\phi \in (0, 1)$,具有几何权重 $(1, \phi, \dots, \phi^{m-1})$ 的 $m$ 个候选对象上的 Plackett–Luce 分布的香农熵以 $C(\phi) \cdot m$ 为上界,其中 $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$。该证明通过直接分析每个序列选择步骤的条件熵,克服了以往的障碍。我们没有要求在移除物品下的单调性,而是确立了在权重 $i \mapsto \phi^i$ 下从任何非空子集 $R \subset \mathbb{N}$ 中选择一个物品的熵以 $C(\phi)$ 为上界,且该界在所有子集 $R$ 上是一致的。在所有步骤中对这一一致界求和,立即可得出大小为 $n$ 的任意候选对象子集的上界 $C(\phi) \cdot n$,从而对所有 $\phi \in (0, 1)$ 确立了线性界 $O(m)$。

这里描述的结果已在 Lean 4 证明助手中进行了机械化形式化和验证。主定理在标识符 plackett_luce_geometric_entropy_linear 下解决了这一公开猜想,并借助了支撑引理 plackett_luce_entropy_geometric_le。接下来的各节详细介绍了形式化定义、精确陈述、逐步数学证明,以及对边界情况和进一步问题的讨论。

2. 预备知识

Definition 1: Plackett–Luce Distribution on Finite Sets 设 $S \subset \mathbb{N}$ 是基数为 $|S| = n$ 的候选对象的非空有限集,设 $w : \mathbb{N} \to \mathbb{R}$ 为权重函数,为每个候选对象 $i \in S$ 分配正实数权重 $w(i) > 0$。$S$ 的一个排名是 $S$ 中元素的双射序列 $l = (\sigma_1, \sigma_2, \dots, \sigma_n)$,表示一个全序关系,其中 $\sigma_1$ 优于 $\sigma_2$,依此类推。在 Plackett–Luce 模型中,获得排名 $l$ 的概率由每个阶段的选择概率的乘积给出: $$P_w(l) = \prod_{k=1}^n \frac{w(\sigma_k)}{\sum_{j=k}^n w(\sigma_j)}.$$ 在形式化展开中,$S$ 的所有有效排名的有限集记作 $\text{rankings\_of}(S)$,在权重函数 $w$ 下排名 $l \in \text{rankings\_of}(S)$ 的概率记作 $\text{plackett\_luce\_prob}(w, l)$。 Remark 1: Lean 形式化将候选对象建模为 $\mathbb{N}$ 中的自然数,候选对象集合建模为有限集 $\text{Finset } \mathbb{N}$。排名表示为不含重复元素且支撑集等于 $S$ 的有序列表。当 $S$ 为空时,$\text{rankings\_of}(S)$ 仅包含空列表,其概率为 1。

Definition 2: Shannon Entropy of the Plackett–Luce Model (plackett_luce_entropy) 设 $w : \mathbb{N} \to \mathbb{R}$ 为权重函数,设 $S \subset \mathbb{N}$ 为候选对象的有限集。在 $S$ 的排名上的 Plackett–Luce 分布的香农熵记作 plackett_luce_entropy,是排名分布的期望信息内容: $$\text{`plackett\_luce\_entropy`} (w, S) = \sum_{l \in \text{rankings\_of}(S)} - P_w(l) \ln P_w(l).$$ 在 Lean 形式化中,这被非可计算地定义为: $$\text{`plackett\_luce\_entropy`} (w, S) = \sum_{l \in \text{rankings\_of}(S)} \text{Real.negMulLog}(\text{plackett\_luce\_prob}(w, l)),$$ 其中当 $p > 0$ 时 $\text{Real.negMulLog}(p) = -p \ln p$,且 $\text{Real.negMulLog}(0) = 0$。 Remark 2: 熵以 nats 为单位,采用自然对数 $\ln$(通过 $\text{Real.log}$ 形式化)进行度量。该定义采用 $\text{Real.negMulLog}$,它强制执行标准约定 $0 \ln 0 = 0$,确保在零概率处的连续性。该定义接受任何权重函数 $w : \mathbb{N} \to \mathbb{R}$ 和任何有限集 $S : \text{Finset } \mathbb{N}$,而不要求 $S$ 是整数的初始段。

Definition 3: Geometric Weights and the Range of Alternatives 对于满足 $0 < \phi < 1$ 的固定参数 $\phi \in \mathbb{R}$,几何权重函数 $w_\phi : \mathbb{N} \to \mathbb{R}$ 定义为 $$w_\phi(i) = \phi^i \quad \text{for each } i \in \mathbb{N}.$$ 对于自然数 $m \in \mathbb{N}$,$m$ 个候选对象的标准集合是初始段 $\{0, 1, \dots, m-1\}$,在 Lean 中形式化为 $\text{Finset.range}(m)$。在此集合上,候选对象的权重为 $(1, \phi, \phi^2, \dots, \phi^{m-1})$。 Remark 3: 参数 $\phi$ 严格限制在开区间 $(0, 1)$ 内,这意味着不等式 $0 < \phi$ 和 $\phi < 1$ 都是严格的。候选对象采用 0-indexed,因此初始候选对象 0 获得权重 $\phi^0 = 1$,随后的候选对象具有几何衰减的权重。

Definition 4: The Geometric Rate Constant $C(\phi)$ 对于任何参数 $\phi \in (0, 1)$,几何速率常数 $C(\phi) \in \mathbb{R}$ 定义为 $$C(\phi) = \ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2} = \ln\left(\frac{1}{1 - \phi}\right) + \ln\left(\frac{1}{\phi}\right) \frac{\phi}{(1 - \phi)^2}.$$ 在 Lean 中,此表达式出现在 plackett_luce_entropy_geometric_le 的界中,形式为 $\text{Real.log}(1 - \phi)^{-1} + (-\text{Real.log } \phi) \cdot (\phi / (1 - \phi)^2)$。 Remark 4: 由于 $0 < \phi < 1$,$1 - \phi$ 和 $\phi$ 都位于 $(0, 1)$ 内。因此,$(1 - \phi)^{-1} > 1$,这意味着 $\ln((1 - \phi)^{-1}) > 0$。类似地,$-\ln \phi = \ln(1/\phi) > 0$。由于 $\phi / (1 - \phi)^2 > 0$,常数 $C(\phi)$ 对所有 $\phi \in (0, 1)$ 都是严格正的。函数 $\phi \mapsto C(\phi)$ 在 $(0, 1)$ 上是连续且单调递增的,满足 $\lim_{\phi \to 0^+} C(\phi) = 0$ 和 $\lim_{\phi \to 1^-} C(\phi) = \infty$。

3. 主要结果

Theorem 1 (Linear Shannon Entropy for Geometric Plackett–Luce Models): 设 $\phi \in \mathbb{R}$ 满足 $0 < \phi < 1$。则存在实常数 $C \in \mathbb{R}$ 使得对每个自然数 $m \in \mathbb{N}$,几何权重 $i \mapsto \phi^i$ 在 $m$ 个候选对象的初始段 $\{0, 1, \dots, m-1\}$ 上的 Plackett–Luce 分布的香农熵满足 $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, \{0, 1, \dots, m-1\}) \le C \cdot m.$$

Lean 陈述 theorem plackett_luce_geometric_entropy_linear (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) : ∃ C : ℝ, ∀ m : ℕ, plackett_luce_entropy (fun i => φ ^ i) (Finset.range m) ≤ C * m 对应英文陈述:通过对满足假设 $0 < \phi$ 和 $\phi < 1$ 的实参数 $\phi$ 进行量化,并断言存在实常数 $C$ 使得对所有自然数 $m$,$m$ 个候选对象的范围上的香农熵均以 $C \cdot m$ 为上界。

形式化展开包含第二个基础性结果,该结果强化并推广了 Theorem 1:

Lemma 1 (plackett_luce_entropy_geometric_le): 设 $\phi \in \mathbb{R}$ 满足 $0 < \phi < 1$。对于每个自然数 $n \in \mathbb{N}$ 和每个基数为 $|S| = n$ 的候选对象有限集 $S \subset \mathbb{N}$,香农熵满足 $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, S) \le \left(\ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2}\right) \cdot n.$$

Lemma plackett_luce_entropy_geometric_le 为 Theorem 1 增加了三项关键优势:

1. Closed-Form Constant: 该引理不仅非构造性地断言某个常数 $C$ 的存在,还给出了显式的速率常数 $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$,对于任何给定的参数 $\phi$ 均可直接计算其数值。

2. Arbitrary Finite Subsets: 该界不局限于连续的初始段 $\{0, 1, \dots, m-1\}$。它对每个有限子集 $S \subset \mathbb{N}$ 均成立,无论 $S$ 中出现的指标之间的间隙如何。因此,即便对手删除了任意一组候选对象,剩余候选对象上的 Plackett–Luce 模型的熵仍以 $C(\phi) \cdot |S|$ 为上界。

3. Full Parameter Coverage: Preference Elicitation as Average-Case Sorting (AAAI 2021) 的 Theorem 12 仅针对半区间 $\phi \in (0, 1/2]$ 建立了 $O(m)$ 界。Lemma plackett_luce_entropy_geometric_le 将这一线性界推广到了整个开区间 $\phi \in (0, 1)$,解决了该论文中提出的猜想。

定理 plackett_luce_geometric_entropy_linear (Lean 4 已验证)
theorem plackett_luce_geometric_entropy_linear (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) :
    ∃ C : ℝ, ∀ m : ℕ, plackett_luce_entropy (fun i => φ ^ i) (Finset.range m) ≤ C * m

4. 证明

我们按照 Lean 形式化的结构展开证明。我们首先概述核心数学思想,然后给出 Lemma 1(plackett_luce_entropy_geometric_le)及其解析证明,接着给出主定理(plackett_luce_geometric_entropy_linear)的证明,最后对具体实例进行详细的数值计算。

在候选对象集合 $S$(满足 $|S| = n$)上 Plackett–Luce 模型下的排名 $l = (\sigma_1, \dots, \sigma_n)$ 是通过由 $n$ 个选择阶段构成的序列过程生成的。在 stage 1,根据与权重成比例的分类分布选择一个候选对象 $\sigma_1 \in S$。在任何后续 stage $k \in \{2, \dots, n\}$ 中,在给定先前选择序列 $(\sigma_1, \dots, \sigma_{k-1})$ 的条件下,剩余可用候选对象的集合为 $R_k = S \setminus \{\sigma_1, \dots, \sigma_{k-1}\}$,它是 $S$ 的基数为 $n - k + 1$ 的非空子集。下一个候选对象 $\sigma_k$ 从 $R_k$ 中抽取的概率为 $$P(\sigma_k = x \mid R_k) = \frac{\phi^x}{\sum_{y \in R_k} \phi^y}.$$ 根据香农熵的链式法则,排名的联合熵是所有 $n$ 个阶段的条件熵之和: $$H(\sigma_1, \dots, \sigma_n) = \sum_{k=1}^n H(\sigma_k \mid \sigma_1, \dots, \sigma_{k-1}).$$ stage $k$ 的条件熵是 $R_k$ 上的分类分布的熵的平均值。如果我们能证明对于每个非空有限集 $R \subset \mathbb{N}$,以与 $\phi^i$ 成比例的概率从 $R$ 中选择一个元素的熵均以一致常数 $C(\phi)$ 为上界,那么和式中的每一项都以 $C(\phi)$ 为上界。对所有 $n$ 个阶段求和便得到上界 $C(\phi) \cdot n$。

关键在于,该方法没有比较移除物品前后权重向量的熵,而这正是 Preference Elicitation as Average-Case Sorting (AAAI 2021) 的 Theorem 12 中 $\phi \le 1/2$ 限制的根源。相反,它确立了单阶段选择熵的绝对上界,该上界在所有非空子集 $R$ 上普适成立。

Lemma 1 (plackett_luce_entropy_geometric_le): 设 $\phi \in \mathbb{R}$ 满足 $0 < \phi < 1$。对于任意自然数 $n \in \mathbb{N}$ 及满足 $|S| = n$ 的任意有限集 $S \subset \mathbb{N}$, $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, S) \le \left(\ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2}\right) \cdot n.$$

Proof of Lemma 1: 设 $R \subset \mathbb{N}$ 为自然数的任意非空有限子集。设 $i_0 = \min(R)$ 表示 $R$ 的最小元素。$R$ 上的选择分布的归一化配分函数为 $$Z = \sum_{i \in R} \phi^i.$$ 由于对所有 $i \in R$ 都有 $i \ge i_0$,我们可以提出 $\phi^{i_0}$: $$Z = \phi^{i_0} \sum_{i \in R} \phi^{i - i_0} = \phi^{i_0} D,$$ 其中 $D = \sum_{i \in R} \phi^{i - i_0}$。 因为 $i_0 \in R$,对应于 $i = i_0$ 的项为 $\phi^0 = 1$。由于所有剩余项 $\phi^{i - i_0}$ 均严格为正,我们有下界 $$D \ge 1.$$ 另一方面,平移后的指标集 $\{i - i_0 : i \in R\}$ 由包含 0 的互异非负整数组成。因此,该有限和以完整几何级数为上界: $$D = \sum_{i \in R} \phi^{i - i_0} \le \sum_{j=0}^\infty \phi^j = \frac{1}{1 - \phi}.$$ 现在考虑 $R$ 上由 $p_i = \phi^i / Z$ 定义的概率分布。该分布的香农熵为 $$H_R = \sum_{i \in R} - p_i \ln p_i = \sum_{i \in R} - \frac{\phi^i}{Z} \ln\left(\frac{\phi^i}{Z}\right).$$ 利用恒等式 $\ln(\phi^i / Z) = i \ln \phi - \ln Z$,我们展开该求和式: $$H_R = \sum_{i \in R} \frac{\phi^i}{Z} (\ln Z - i \ln \phi) = \ln Z - (\ln \phi) \sum_{i \in R} i \frac{\phi^i}{Z}.$$ 代入 $Z = \phi^{i_0} D$ 得出 $\ln Z = i_0 \ln \phi + \ln D$。因此: $$H_R = i_0 \ln \phi + \ln D - (\ln \phi) \sum_{i \in R} i \frac{\phi^i}{Z} = \ln D - (\ln \phi) \sum_{i \in R} (i - i_0) \frac{\phi^i}{Z}.$$ 由于 $\phi^i / Z = \phi^{i - i_0} / D$,我们将第二项重写为: $$H_R = \ln D + (-\ln \phi) \frac{\sum_{i \in R} (i - i_0) \phi^{i - i_0}}{D}.$$ 由于 $0 < \phi < 1$,我们有 $-\ln \phi = \ln(1/\phi) > 0$。我们分别对这两项建立上界:

1. Term 1: 由于 $D \le 1 / (1 - \phi)$ 且对数函数是严格递增的, $$\ln D \le \ln\left(\frac{1}{1 - \phi}\right).$$

2. Term 2: 由于 $D \ge 1$,分母满足 $1 / D \le 1$。对于分子,平移后的指标 $i - i_0$ 是互异的非负整数,因此 $$\sum_{i \in R} (i - i_0) \phi^{i - i_0} \le \sum_{j=0}^\infty j \phi^j.$$ 利用几何级数导数的恒等式, $$\sum_{j=0}^\infty j \phi^j = \phi \frac{d}{d\phi}\left(\sum_{j=0}^\infty \phi^j\right) = \phi \frac{d}{d\phi}\left(\frac{1}{1 - \phi}\right) = \frac{\phi}{(1 - \phi)^2}.$$ 因为 $-\ln \phi > 0$ 且 $1/D \le 1$,所以有 $$(-\ln \phi) \frac{\sum_{i \in R} (i - i_0) \phi^{i - i_0}}{D} \le (-\ln \phi) \frac{\phi}{(1 - \phi)^2}.$$ 对两项的界求和,我们得到: $$H_R \le \ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2} = C(\phi).$$ 这个一致界对自然数的每个非空子集 $R \subset \mathbb{N}$ 都成立,无论其大小、元素或间隙如何。 在 $S$ 上的序列过程的 stage $k$,剩余集合 $R_k$ 的基数为 $n - k + 1 \ge 1$。因此,stage $k$ 的条件熵满足 $H(\sigma_k \mid \sigma_1, \dots, \sigma_{k-1}) \le C(\phi)$。 在最终 stage $k = n$,剩余集合满足 $|R_n| = 1$,其熵为 $0 \le C(\phi)$。 对所有 $n$ 个阶段求和得到: $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, S) \le \sum_{k=1}^n C(\phi) = C(\phi) \cdot n.$$ 这完成了 Lemma 1 的证明。

Proof of Theorem 1 (plackett_luce_geometric_entropy_linear): 给定 $\phi \in \mathbb{R}$ 满足 $0 < \phi$ 和 $\phi < 1$,我们用速率常数 $$C = \ln\left(\frac{1}{1 - \phi}\right) + (-\ln \phi) \frac{\phi}{(1 - \phi)^2}.$$ 实例化存在量词 $\exists C : \mathbb{R}$。 在 Lean 中,此见证通过匿名构造子 ⟨_, ...⟩ 提供。 对于任意自然数 $m : \mathbb{N}$,我们考虑候选对象集合 $S = \text{Finset.range}(m)$。 根据库引理 $\text{Finset.card\_range}(m)$,该集合的基数恰好为 $|S| = m$。 将 plackett_luce_entropy_geometric_le 应用于参数 $\phi$、假设 $h_0 : 0 < \phi$ 与 $h_1 : \phi < 1$、基数 $m$、集合 $\text{Finset.range}(m)$ 以及基数等式,可得出不等式: $$\text{plackett\_luce\_entropy}(i \mapsto \phi^i, \text{Finset.range}(m)) \le C \cdot m.$$ 策略 simpa 化简该表达式并在 Lean 中完成了证明。

为了支持手动验证,我们在两个具体实例上评估该界。

Instance 1: $\phi = 1/2$,$m = 3$ 个候选对象($S = \{0, 1, 2\}$)。 此实例位于先前已分析过的参数范围 $\phi \le 1/2$ 内。 我们首先计算常数 $C(1/2)$: - $1 - \phi = 1/2 \implies (1 - \phi)^{-1} = 2$,因此 $\ln(1/(1 - \phi)) = \ln 2 \approx 0.693147$ nats。 - $-\ln \phi = -\ln(1/2) = \ln 2 \approx 0.693147$ nats。 - $\phi / (1 - \phi)^2 = (1/2) / (1/4) = 2$。 - $C(1/2) = \ln 2 + 2 \ln 2 = 3 \ln 2 = \ln 8 \approx 2.079442$ nats。 对于 $m = 3$,线性上界为: $$C(1/2) \cdot 3 = 9 \ln 2 \approx 6.238325 \text{ nats}.$$ 我们现在手动计算精确的分布和熵。 权重为 $w(0) = 1$、$w(1) = 1/2$ 和 $w(2) = 1/4$。乘以 4 得到和为 7 的整数权重 $(4, 2, 1)$。 存在 $3! = 6$ 种可能的排名 $l = (\sigma_1, \sigma_2, \sigma_3)$: 1. 排名 $(0, 1, 2)$:概率 $p_1 = (4/7) \cdot (2/3) \cdot 1 = 8/21 \approx 0.380952$。 2. 排名 $(0, 2, 1)$:概率 $p_2 = (4/7) \cdot (1/3) \cdot 1 = 4/21 \approx 0.190476$。 3. 排名 $(1, 0, 2)$:概率 $p_3 = (2/7) \cdot (4/5) \cdot 1 = 8/35 \approx 0.228571$。 4. 排名 $(1, 2, 0)$:概率 $p_4 = (2/7) \cdot (1/5) \cdot 1 = 2/35 \approx 0.057143$。 5. 排名 $(2, 0, 1)$:概率 $p_5 = (1/7) \cdot (4/6) \cdot 1 = 2/21 \approx 0.095238$。 6. 排名 $(2, 1, 0)$:概率 $p_6 = (1/7) \cdot (2/6) \cdot 1 = 1/21 \approx 0.047619$。 验证总概率: $$p_1 + p_2 + p_5 + p_6 = \frac{8 + 4 + 2 + 1}{21} = \frac{15}{21} = \frac{5}{7}.$$ $$p_3 + p_4 = \frac{8 + 2}{35} = \frac{10}{35} = \frac{2}{7}.$$ 求和:$5/7 + 2/7 = 1$。 各个熵分量 $-p_i \ln p_i$ 分别为: - $-p_1 \ln p_1 \approx -(0.380952)(-0.965081) \approx 0.367645$ - $-p_2 \ln p_2 \approx -(0.190476)(-1.658228) \approx 0.315808$ - $-p_3 \ln p_3 \approx -(0.228571)(-1.475907) \approx 0.337349$ - $-p_4 \ln p_4 \approx -(0.057143)(-2.862201) \approx 0.163539$ - $-p_5 \ln p_5 \approx -(0.095238)(-2.351375) \approx 0.224016$ - $-p_6 \ln p_6 \approx -(0.047619)(-3.044522) \approx 0.144976$ 对这些值求和得到精确的香农熵: $$H \approx 0.367645 + 0.315808 + 0.337349 + 0.163539 + 0.224016 + 0.144976 \approx 1.553333 \text{ nats}.$$ 与理论界进行比较: $$1.553333 \le 6.238325.$$ 该界以充裕的余量成立。

Instance 2: $\phi = 3/4$,位于先前未解决的区间 $(1/2, 1)$ 内。 因为 $\phi = 3/4 > 1/2$,Preference Elicitation as Average-Case Sorting (AAAI 2021) 的 Theorem 12 并不适用。 我们计算常数 $C(3/4)$: - $1 - \phi = 1/4 \implies (1 - \phi)^{-1} = 4$,因此 $\ln(1/(1 - \phi)) = \ln 4 = 2 \ln 2 \approx 1.386294$ nats。 - $-\ln \phi = -\ln(3/4) = \ln(4/3) \approx 0.287682$ nats。 - $\phi / (1 - \phi)^2 = (3/4) / (1/16) = 12$。 - $C(3/4) = \ln 4 + 12 \ln(4/3) \approx 1.386294 + 12 \cdot 0.287682 \approx 4.838479$ nats。 对于 $m = 2$ 个候选对象($S = \{0, 1\}$),权重为 $w(0) = 1$ 且 $w(1) = 3/4$。 两种可能的排名是概率为 $4/7$ 的 $(0, 1)$ 以及概率为 $3/7$ 的 $(1, 0)$。 精确的香农熵为: $$H = -\frac{4}{7} \ln\left(\frac{4}{7}\right) - \frac{3}{7} \ln\left(\frac{3}{7}\right) \approx 0.319799 + 0.363131 \approx 0.682930 \text{ nats}.$$ 理论界给出: $$C(3/4) \cdot 2 \approx 4.838479 \cdot 2 = 9.676958 \text{ nats}.$$ 不等式 $0.682930 \le 9.676958$ 得到验证。

5. 讨论

我们讨论该结果的意涵、它所涵盖与未涵盖的内容,以及该设定所突出的其余问题。

该结果完全普遍地解决了 Preference Elicitation as Average-Case Sorting (AAAI 2021) 第 5 节中提出的猜想。原文证明了具有权重 $(1, \phi, \dots, \phi^{m-1})$ 的 Plackett–Luce 模型的香农熵对于 $\phi \in (0, 1/2]$ 是 $O(m)$,并猜想该线性界可推广到所有 $\phi \in (0, 1)$。定理 plackett_luce_geometric_entropy_linear 肯定地解决了这个猜想。此外,引理 plackett_luce_entropy_geometric_le 提供了一个显式的闭形式常数 $C(\phi)$,并表明线性界对基数为 $n$ 的任意子集 $S \subset \mathbb{N}$ 均成立,而不仅限于连续的初始段。

该定理专门针对开单位区间 $\phi \in (0, 1)$。考察此结果的边界与局限性是有启发性的:

1. 边界 $\phi = 1$:当 $\phi = 1$ 时,权重是均匀的,$w = (1, 1, \dots, 1)$。在均匀权重下,每个排名都是等可能的,产生 $m!$ 个置换上的均匀分布。该分布的香农熵为 $\ln(m!) = \sum_{k=1}^m \ln k = m \ln m - m + O(\ln m)$,这是严格超线性的($\Theta(m \ln m)$ nats)。因此,线性熵在 $\phi = 1$ 时不成立。这种奇点反映在速率常数 $C(\phi)$ 中:当 $\phi \to 1^-$ 时,我们有 $(1 - \phi)^{-1} \to \infty$ 且 $\phi / (1 - \phi)^2 \to \infty$,从而 $C(\phi) \to \infty$。$C(\phi)$ 当 $\phi \to 1^-$ 时的发散准确地反映了从线性熵到超线性熵的转变。

2. 区域 $\phi > 1$:当 $\phi > 1$ 时,权重随指标几何递增。在 $m$ 个候选对象的有限集合上,可以通过双射 $i \mapsto m - 1 - i$ 反转对象的标号,这将权重向量转换为参数为 $\psi = 1/\phi \in (0, 1)$ 的几何权重。反转标号是排名上的双射并保持熵不变;因此,对于任何固定的 $\phi > 1$,在范围 $\{0, \dots, m-1\}$ 上的熵仍然是 $O(m)$。然而,在无限基础集 $\mathbb{N}$ 上,权重发散到无穷大,并且在无限子集上的配分函数不收敛。

3. 一般权重分布:该结果特定于几何权重 $w(i) = \phi^i$。在平均情况排序和偏好诱引中,其他参数化权重族通常也具有相关性,例如调和权重 $w_i = (i + 1)^{-1}$ 或多项式衰减权重 $w_i = (i + 1)^{-\alpha}$(其中 $\alpha > 0$)。对于调和权重,配分函数对数发散,熵的行为介于均匀和几何设定之间。确定一般权重序列 $w : \mathbb{N} \to \mathbb{R}_{>0}$ 保障线性香农熵的充要条件仍然是一个开放问题,本工作未予涉及。

4. 常数的渐近紧致性:虽然 $C(\phi)$ 为所有 $n$ 提供了显式上界,但它不是紧的。例如,当 $\phi \to 0^+$ 时,$C(\phi) \sim \phi \ln(1/\phi)$,而精确的渐近熵率 $\lim_{m \to \infty} \frac{1}{m} \text{plackett\_luce\_entropy}(w_\phi, \text{range}(m))$ 可能有所不同。确定该渐近极限的精确值是未来研究的一个自然问题。

为什么是研究级成果

  • settles OP-70 (Linear entropy of geometric Plackett–Luce models)

Lean 声明

  • plackett_luce_geometric_entropy_linearConjecture of Preference Elicitation as Average-Case Sorting (AAAI 2021): for every phi in (0,1) the Plackett-Luce model with weights (1,…
  • plackett_luce_entropy_geometric_leFor geometric weights phi^a with 0 < phi < 1, the Plackett-Luce entropy on any set of n alternatives is at most C(phi) * n with C(phi) =…
  • plackett_luce_entropyShannon entropy (natural logarithm) of the Plackett-Luce distribution over the rankings of S.

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。