Skip to content

定理Theorem

Sanov 定理

施工中 · 内容逐步修订

Sanov theorem

以相对熵刻画 IID 经验测度偏离总体分布的指数成本,有限字母表下可由类型计数推导。

形式陈述 ​

样本均值只保留一个数。如果关心整份频率表异常,哪种函数取代 Cramér 定理的均值速率?Sanov 定理的答案是相对熵。

设 X1,X2,… 为Polish 空间 E 上服从 P 的IID 样本,经验测度为 Ln=n−1∑iδXi。在概率测度空间的弱拓扑下,Ln 以速度 n 满足LDP,良速率为

I(Q)=D(Q‖P)={∫log⁡dQdPdQ,Q≪P,+∞,否则.

这里的 D 是采用自然对数的KL 散度,方向是异常经验律 Q 相对于真实抽样律 P。若用比特单位 D2,则 I=D=(ln⁡2)D2,概率指数相应为 e−nD=2−nD2。弱拓扑意味着用有界连续函数的积分检验接近,而不是用总变差检验。

有限字母表 {1,…,r}(r≥1)上,若 P=(p1,…,pr),则 I(q)=∑jqjlog⁡(qj/pj)。任何 qj=0 的项都取零,包括 pj=qj=0 的情形;若 pj=0<qj,该项为无穷,因为原模型不可能产生这个类别。

直觉

一种频率表的概率有两部分:拥有这张表的排列有多少,以及每个排列在原模型下有多大概率。熵计算排列数量,交叉熵计算单个排列的概率,两者相减后恰好留下相对熵。

有限表上,若 nqj 都是非负整数,多项式系数计数相同频率表的有序样本,因此

P(Ln=q)=n!∏j(nqj)!∏jpjnqj.

类型计数给出 (n+1)−re−nD(q‖p)≤P(Ln=q)≤e−nD(q‖p),而类型总数至多 (n+1)r。可以不使用渐近阶乘公式来核验前一个界:在抽样律恰为 q 时,该类型的概率是所有类型中的最大值,所以介于 (n+1)−r 与 1 之间;换回抽样律 p,同类型的每条样本序列恰多出因子 e−nD(q‖p)。最大值性质也可逐项验证:写 kj=nqj,当总计数为 n 时,只需比较 ∏jkjmj/mj!,每个正整数 kj 对应的因子在 mj=kj 处达到最大;kj=0 则只允许 mj=0。这些多项式因子在对数除以 n 后消失。对闭集汇总各类型得上界,对开集选一串逼近目标分布的可实现类型得下界。一般 Polish 空间还需要弱拓扑、相对熵的变分式和指数紧性;下面直接给出这一层证明。

证明:一般 Polish 空间 ​

经验映射 En→P(E) 在弱拓扑下连续,因为对每个 g∈Cb(E),其积分是连续函数 n−1∑ig(Xi)。特别地,经验测度确实定义了可测随机元素。

相对熵的连续测试变分式。 先允许有界 Borel 函数 g。若 Q≪̸P,取 P(A)=0<Q(A),令 g=t1A 并使 t↑∞。若 Q≪P,由Radon–Nikodym 定理写 r=dQ/dP。将 P 倾斜成 egP/(Peg),KL 非负性给出 Qg−log⁡Peg≤D(Q‖P);当右侧无穷时这个上界自动成立。反向用 gm=max{−m,min{m,log⁡r}},在 r=0 处取 −m。由于 r(log⁡r)−≤1/e,负部可积;正部用单调收敛定理,负部用控制收敛定理,得 Qgm→D(Q‖P)。又有 egm≤r+1 且 egm→r,故 Pegm→1。

可将有界 Borel 测试函数替换为有界连续函数。由于 E 是 Polish 空间,有限 Borel 测度 P+Q 是正则测度,可用紧集作内逼近、开集作外逼近:指标函数可先在闭集 F⊂A⊂G(G 开)之间逼近,使 (P+Q)(G∖F) 任意小,再用连续截断

u(z)=d(z,Gc)d(z,F)+d(z,Gc)

代替 1A;非空 F,Gc 时分母处处正,空集边界情形用常数函数处理。有限简单函数逼近并截回原有界值域,使 Qg 与 Peg 都收敛,后者用指数函数在有界区间上的 Lipschitz 性。于是

D(Q‖P)=supg∈Cb(E){Qg−log⁡Peg}.

这立即说明熵对弱拓扑下半连续。还可由有界 Borel 测试 g=t1Kc 得到:若 P(Kc)≤e−t,则

Q(Kc)≤D(Q‖P)+log⁡2t.

Polish 空间上的每个概率测度紧,故可为任意 t 选择这样的紧集 K。因此每个熵子水平集一致紧;由Prokhorov 定理和上述闭性,它是弱紧集,证明了速率的良性。

局部上界与指数紧性。 IID 结构给出 Eexp⁡(nLng)=(Peg)n。若 b<D(Q‖P),由变分式选 g∈Cb(E) 使 Qg−log⁡Peg>b;在 Q 的一个弱邻域内这个严格不等式仍成立,指数 Markov 不等式即给出该邻域概率至多 e−nb。紧集有限覆盖得到紧集上界。

为把它提升为闭集上界,固定 L>0,对 j≥1 令 tj=j(L+j+log⁡2),选紧集 Kj 使 P(Kjc)≤e−tj。集合

KL={Q:Q(Kjc)≤1/j 对所有 j≥1}

一致紧,且是弱闭集。具体地,对非空补集的开集 U,连续函数 uk(z)=min{1,kd(z,Uc)} 单调趋于 1U,单调收敛给出 Q(U)=supkQuk;U=E 时直接用常数一。因此开集质量是弱下半连续函数,每个约束 Q(Kjc)≤1/j 都闭。由 Prokhorov 定理,KL 为紧集。对每个 j 用指标函数的指数矩,再取可数并,得到

P(Ln∉KL)≤∑j≥1exp⁡{−n(tj/j−log⁡2)}=∑j≥1e−n(L+j).

其对数除以 n 的上极限至多 −L−1,这证明指数紧性,并将紧集上界升级为完整闭集上界。

下界。 固定开集 G 内一个 D(Q‖P)<∞ 的 Q,并在 Q⊗n 下抽样。弱邻域可由有限个有界连续测试积分约束,因此大数定律给出 Q⊗n(Ln∈G)→1。同样,log⁡r 在 Q 下可积且均值为 D(Q‖P),故其样本平均也收敛。对事件

An={Ln∈G, n−1∑ilog⁡r(Xi)≤D(Q‖P)+δ}

有 Q⊗n(An)→1,而换测度给出

P⊗n(Ln∈G)≥EQ⊗n[1Ane−∑ilog⁡r(Xi)]≥e−n(D(Q‖P)+δ)Q⊗n(An).

第一个不等式只用 Q≪P,并未假设反向绝对连续:积分只计算 P⊗n 在 r(Xi)>0 上的部分。令 δ↓0 并在 G 内优化 Q,即得开集下界。这证明完整的一般 Polish 版本。

例子与边界

三种结果的真实概率为 p=(1/2,1/4,1/4),研究第一类经验比例不超过 1/4。固定 q1=x 后,剩余质量 1−x 分给第二、三类的最小成本方案保持原比例 1:1,即 q2=q3=(1−x)/2。

代入后,优化降为二元相对熵 D(x‖1/2)。它在 x<1/2 时随 x 增大而减小,所以约束下的最小点是

q∗=(1/4,3/8,3/8),I(q∗)=14log⁡12+34log⁡32.

闭约束与内部 q1<1/4 可逼近同一最小点,因此事件概率的对数除以 n 趋于 −I(q∗)。定理不仅给出成本,也指出异常样本最可能怎样把少掉的第一类质量重新分配。

若 P 连续,有限样本经验测度对 P 奇异,故每个实现的 D(Ln‖P) 都为无穷。这不与 Sanov 矛盾:定理计算的是经验测度落入一个固定弱邻域的概率,不是把每个随机原子测度代入速率后当成其点概率。弱邻域可包含相对熵有限的连续分布。

换成依赖样本时,通常不能保留 D(Q‖P) 作为完整速率。相同的一维边缘不代表相同的频率表概率,转移结构可能改变成本。

推论与应用

在有限字母表上,把 Q 映到 ∑jg(j)qj 连续,收缩原理给出统计量速率 infQ:EQg=xD(Q‖P)。若再条件于稀有频率约束,最小相对熵分布将成为Gibbs 条件化原理的核心对象。

参考资料
关系图谱46 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系