形式陈述
样本均值只保留一个数。如果关心整份频率表异常,哪种函数取代 Cramér 定理的均值速率?Sanov 定理的答案是相对熵。
设 X 1 , X 2 , … 为Polish 空间 理路 Polish 空间 Polish space 可分且可完全度量化的拓扑空间;用换度量、可数乘积和子空间例子区分拓扑性质与指定度量的完备性。 E 上服从 P 的IID 样本 理路 独立同分布样本 IID sample · Independent and identically distributed sample 以乘积分布描述来自同一总体的独立重复观测。 ,经验测度 理路 经验测度 Empirical measure · Empirical distribution 把有限观测的重复频数编码为原子概率测度。 为 L n = n − 1 ∑ i δ X i 。在概率测度空间的弱拓扑 理路 测度的弱收敛 Weak convergence of measures · Weak convergence of probability measures 以所有有界连续测试函数的积分收敛来定义有限 Borel 测度的拓扑收敛。 下,L n 以速度 n 满足LDP 理路 大偏差原理 Large deviation principle · LDP 用开集下界和闭集上界刻画概率的指数衰减,区分速率函数、拓扑与精确概率。 ,良速率为
否 则 I ( Q ) = D ( Q ‖ P ) = { ∫ log d Q d P d Q , Q ≪ P , + ∞ , 否则 . 这里的 D 是采用自然对数的KL 散度 理路 KL 散度 Kullback–Leibler divergence · Relative entropy 同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。 ,方向是异常经验律 Q 相对于真实抽样律 P 。若用比特单位 D 2 ,则 I = D = ( ln 2 ) D 2 ,概率指数相应为 e − n D = 2 − n D 2 。弱拓扑意味着用有界连续函数的积分检验接近,而不是用总变差检验。
有限字母表 { 1 , … , r } (r ≥ 1 )上,若 P = ( p 1 , … , p r ) ,则 I ( q ) = ∑ j q j log ( q j / p j ) 。任何 q j = 0 的项都取零,包括 p j = q j = 0 的情形;若 p j = 0 < q j ,该项为无穷,因为原模型不可能产生这个类别。
直觉
一种频率表的概率有两部分:拥有这张表的排列有多少,以及每个排列在原模型下有多大概率。熵计算排列数量,交叉熵计算单个排列的概率,两者相减后恰好留下相对熵。
有限表上,若 n q j 都是非负整数,多项式系数 理路 多项式系数 Multinomial coefficient 把 n 个可区分对象分入若干有标号组时的计数系数 n!/(n1!⋯nk!)。 计数相同频率表的有序样本,因此
P ( L n = q ) = n ! ∏ j ( n q j ) ! ∏ j p j n q j . 类型计数给出 ( n + 1 ) − r e − n D ( q ‖ p ) ≤ P ( L n = q ) ≤ e − n D ( q ‖ p ) ,而类型总数至多 ( n + 1 ) r 。可以不使用渐近阶乘公式来核验前一个界:在抽样律恰为 q 时,该类型的概率是所有类型中的最大值,所以介于 ( n + 1 ) − r 与 1 之间;换回抽样律 p ,同类型的每条样本序列恰多出因子 e − n D ( q ‖ p ) 。最大值性质也可逐项验证:写 k j = n q j ,当总计数为 n 时,只需比较 ∏ j k j m j / m j ! ,每个正整数 k j 对应的因子在 m j = k j 处达到最大;k j = 0 则只允许 m j = 0 。这些多项式因子在对数除以 n 后消失。对闭集汇总各类型得上界,对开集选一串逼近目标分布的可实现类型得下界。一般 Polish 空间还需要弱拓扑、相对熵的变分式和指数紧性;下面直接给出这一层证明。
证明:一般 Polish 空间
经验映射 E n → P ( E ) 在弱拓扑下连续,因为对每个 g ∈ C b ( E ) ,其积分是连续函数 n − 1 ∑ i g ( X i ) 。特别地,经验测度确实定义了可测随机元素。
相对熵的连续测试变分式。 先允许有界 Borel 函数 g 。若 Q ≪̸ P ,取 P ( A ) = 0 < Q ( A ) ,令 g = t 1 A 并使 t ↑ ∞ 。若 Q ≪ P ,由Radon–Nikodym 定理 理路 Radon–Nikodym 定理 Radon–Nikodym theorem 在标准 σ-有限条件下,把绝对连续测度表示为参考测度的积分密度。 写 r = d Q / d P 。将 P 倾斜成 e g P / ( P e g ) ,KL 非负性给出 Q g − log P e g ≤ D ( Q ‖ P ) ;当右侧无穷时这个上界自动成立。反向用 g m = max { − m , min { m , log r } } ,在 r = 0 处取 − m 。由于 r ( log r ) − ≤ 1 / e ,负部可积;正部用单调收敛定理 理路 单调收敛定理 Monotone convergence theorem 非负可测函数单调递增时,积分极限等于极限函数积分。 ,负部用控制收敛定理 理路 控制收敛定理 Dominated convergence theorem 几乎处处收敛且被同一可积函数控制时,可以交换极限与积分。 ,得 Q g m → D ( Q ‖ P ) 。又有 e g m ≤ r + 1 且 e g m → r ,故 P e g m → 1 。
可将有界 Borel 测试函数替换为有界连续函数。由于 E 是 Polish 空间,有限 Borel 测度 P + Q 是正则测度 理路 正则 Borel 测度 Regular Borel measure · 正则博雷尔测度 能从外部用开集、从内部用紧集逼近每个 Borel 集质量的 Borel 测度。 ,可用紧集作内逼近、开集作外逼近:指标函数可先在闭集 F ⊂ A ⊂ G (G 开)之间逼近,使 ( P + Q ) ( G ∖ F ) 任意小,再用连续截断
u ( z ) = d ( z , G c ) d ( z , F ) + d ( z , G c ) 代替 1 A ;非空 F , G c 时分母处处正,空集边界情形用常数函数处理。有限简单函数逼近并截回原有界值域,使 Q g 与 P e g 都收敛,后者用指数函数在有界区间上的 Lipschitz 性。于是
D ( Q ‖ P ) = sup g ∈ C b ( E ) { Q g − log P e g } . 这立即说明熵对弱拓扑下半连续。还可由有界 Borel 测试 g = t 1 K c 得到:若 P ( K c ) ≤ e − t ,则
Q ( K c ) ≤ D ( Q ‖ P ) + log 2 t . Polish 空间上的每个概率测度紧,故可为任意 t 选择这样的紧集 K 。因此每个熵子水平集一致紧;由Prokhorov 定理 理路 Prokhorov 定理 Prokhorov theorem · Prokhorov's theorem · 普罗霍罗夫定理 在 Polish 空间上把概率测度族的一致紧性等价为弱拓扑中的相对紧性。 和上述闭性,它是弱紧集,证明了速率的良性。
局部上界与指数紧性。 IID 结构给出 E exp ( n L n g ) = ( P e g ) n 。若 b < D ( Q ‖ P ) ,由变分式选 g ∈ C b ( E ) 使 Q g − log P e g > b ;在 Q 的一个弱邻域内这个严格不等式仍成立,指数 Markov 不等式即给出该邻域概率至多 e − n b 。紧集有限覆盖得到紧集上界。
为把它提升为闭集上界,固定 L > 0 ,对 j ≥ 1 令 t j = j ( L + j + log 2 ) ,选紧集 K j 使 P ( K j c ) ≤ e − t j 。集合
对 所 有 K L = { Q : Q ( K j c ) ≤ 1 / j 对所有 j ≥ 1 } 一致紧,且是弱闭集。具体地,对非空补集的开集 U ,连续函数 u k ( z ) = min { 1 , k d ( z , U c ) } 单调趋于 1 U ,单调收敛给出 Q ( U ) = sup k Q u k ;U = E 时直接用常数一。因此开集质量是弱下半连续函数,每个约束 Q ( K j c ) ≤ 1 / j 都闭。由 Prokhorov 定理,K L 为紧集。对每个 j 用指标函数的指数矩,再取可数并,得到
P ( L n ∉ K L ) ≤ ∑ j ≥ 1 exp { − n ( t j / j − log 2 ) } = ∑ j ≥ 1 e − n ( L + j ) . 其对数除以 n 的上极限至多 − L − 1 ,这证明指数紧性 理路 指数紧性 Exponential tightness 以任意强度的指数尾控制质量逃向无穷,将紧集上界升级为所有闭集上界。 ,并将紧集上界升级为完整闭集上界。
下界。 固定开集 G 内一个 D ( Q ‖ P ) < ∞ 的 Q ,并在 Q ⊗ n 下抽样。弱邻域可由有限个有界连续测试积分约束,因此大数定律 理路 强大数定律 Law of large numbers · Strong law of large numbers · SLLN 独立同分布且可积时,样本均值沿几乎每条无限样本路径收敛到共同期望。 给出 Q ⊗ n ( L n ∈ G ) → 1 。同样,log r 在 Q 下可积且均值为 D ( Q ‖ P ) ,故其样本平均也收敛。对事件
A n = { L n ∈ G , n − 1 ∑ i log r ( X i ) ≤ D ( Q ‖ P ) + δ } 有 Q ⊗ n ( A n ) → 1 ,而换测度给出
P ⊗ n ( L n ∈ G ) ≥ E Q ⊗ n [ 1 A n e − ∑ i log r ( X i ) ] ≥ e − n ( D ( Q ‖ P ) + δ ) Q ⊗ n ( A n ) . 第一个不等式只用 Q ≪ P ,并未假设反向绝对连续:积分只计算 P ⊗ n 在 r ( X i ) > 0 上的部分。令 δ ↓ 0 并在 G 内优化 Q ,即得开集下界。这证明完整的一般 Polish 版本。
例子与边界
三种结果的真实概率为 p = ( 1 / 2 , 1 / 4 , 1 / 4 ) ,研究第一类经验比例不超过 1 / 4 。固定 q 1 = x 后,剩余质量 1 − x 分给第二、三类的最小成本方案保持原比例 1 : 1 ,即 q 2 = q 3 = ( 1 − x ) / 2 。
代入后,优化降为二元相对熵 D ( x ‖ 1 / 2 ) 。它在 x < 1 / 2 时随 x 增大而减小,所以约束下的最小点是
q ∗ = ( 1 / 4 , 3 / 8 , 3 / 8 ) , I ( q ∗ ) = 1 4 log 1 2 + 3 4 log 3 2 . 闭约束与内部 q 1 < 1 / 4 可逼近同一最小点,因此事件概率的对数除以 n 趋于 − I ( q ∗ ) 。定理不仅给出成本,也指出异常样本最可能怎样把少掉的第一类质量重新分配。
若 P 连续,有限样本经验测度对 P 奇异,故每个实现的 D ( L n ‖ P ) 都为无穷。这不与 Sanov 矛盾:定理计算的是经验测度落入一个固定弱邻域的概率,不是把每个随机原子测度代入速率后当成其点概率。弱邻域可包含相对熵有限的连续分布。
换成依赖样本时,通常不能保留 D ( Q ‖ P ) 作为完整速率。相同的一维边缘不代表相同的频率表概率,转移结构可能改变成本。