The duo Bregman and Fenchel-Young divergences
Frank Nielsen
cs.IT
2022-02-22
把不同指数族之间的KL写成一对凸函数的Fenchel-Young缺口;支撑一嵌套就非负,截断正态和指数对拉普拉斯都能闭式算。
同一指数族里两条密度的 KL 散度,早就能写成 Bregman 散度,也能写成 Fenchel-Young 散度。Amari 在对偶平坦空间里给过这条公式,Azoury 和 Warmuth 在 2001 年的在线密度估计里把它写成对偶 Bregman。麻烦出在两边不是同一族:一条密度撑在半轴上,另一条撑在全轴上;一条是截断正态,一条是完整正态。支撑集不同,log 配分函数不同,「KL = BF(θ2:θ1)」这条经典等式直接失效。
Frank Nielsen(Sony CSL)把这件事收成一对凸生成元。两个严格凸函数 F1、F2,只要 F1 在公共定义域上点点不小于 F2,就能定义始终非负的 duo Fenchel-Young 散度,并证明嵌套指数族之间的 KL 恰好等于它。期刊版发在 Entropy 2022 第 24 卷第 3 期。
普通 Fenchel-Young 散度是 Y{F,F}(θ,η') = F(θ)+F(η')−θᵀη'。非负来自 Fenchel-Young 不等式,等号当且仅当 η'=∇F(θ)。duo 版本把两个生成元拆开:
Y{F1,F2}(θ,η') = F1(θ) + F2(η') − θᵀη'
非负条件是 F1(θ)≥F2(θ) 对每个公共点都成立。Legendre-Fenchel 变换会把优势反过来:F1 更大,则共轭 F1 更小,于是这个缺口至少和普通 Fenchel-Young 一样大,因此非负。
换到同一套自然参数,就是 duo Bregman 散度:
B{F1,F2}(θ:θ') = F1(θ) − F2(θ') − (θ−θ')ᵀ∇F2(θ')
几何图像是「高的那条曲线」减去「矮的那条在 θ' 处的切线」。F1=F2 时退回普通 Bregman。二次例子最清楚:F1=(a/2)θ²、F2=(1/2)θ²,只有 a≥1 才处处非负;a=1 时就是半平方欧氏距离,a=1/2 时函数会掉到零以下。
嵌套指数族是主应用。大支撑 X2 上的族 E2,小支撑 X1⊂X2 上的截断族 E1,共用充分统计量和自然参数。配分函数满足 F2(θ)≥F1(θ),因为积分域更大,自然参数空间反过来是 Θ2⊆Θ1。定理 1 给出截断密度对更大支撑密度的 KL:
DKL[p{θ1}:q{θ2}] = B{F2,F1}(θ2:θ1) = Y{F2,F1}(θ2:η1)
参数顺序是对调的。反向 KL 是无穷,因为大支撑密度并不绝对连续于小支撑密度。
Bhattacharyya 的 α 偏斜距离走同一条路,变成 duo Jensen 散度(定理 2):
J{F1,F2,α}(θ1:θ2) = α F1(θ1) + (1−α) F2(θ2) − F1(αθ1+(1−α)θ2)
α→1 时把这个量除以 1−α,极限就是上面的 KL,和同一族里 Jensen 逼近 Bregman 的经典极限平行。
不强制 F1≥F2 时,duo Bregman 可以变负,论文叫它 signed 伪散度。差凸规划里的 DCA(也叫 CCCP)迭代,恰好是固定右参数、最小化这个伪散度。
没有深度学习榜单,能带走的是几条闭式。
| 配对 | KL | 和同族公式的差别 |
| 指数 λ1 对拉普拉斯 λ2 | log(λ1/λ2)+λ2/λ1+log 2−1 | 多一项 log 2,其余是 Itakura-Saito DIS[λ2:λ1] |
| 半正态 σ1 对正态 σ2 | ½(log(σ2²/σ1²)+σ1²/σ2²+log 4−1) | 同族 KL 少 log 2;½log 4 正好是 log 2 |
| 截断正态,支撑 [a1,b1]⊆[a2,b2] | 配分函数用 Φ 差写出,再减矩参数内积 | 支撑不嵌套则 +∞;两边都回到全直线时退回标准一维正态 KL |
| Poisson λ 对几何 p | −log p + λ log(λ/(1-p)) − λ − Eλ[log x!] | 含一个对阶乘对数的泊松期望,没有更简的闭式 |
截断正态的均值和二阶矩用 φ、Φ 的 mills 比修正:μ = m − s(φ(β)−φ(α))/(Φ(β)−Φ(α))。全支撑极限下 μ=m、σ²=s²,KL 缩成 ½(log(s2²/s1²)+s1²/s2²+(m2−m1)²/s2²−1)。Nielsen 提供了 Java 实现。
质心:左质心 θL=(∇F1)^{−1}((1/n)Σ ∇F2(θi));右质心永远是算术平均 θ̄。后一条把 Banerjee 等人 2005 年 Bregman 聚类的「右心即质心」推到双生成元。
概率模型里会撞上截断高斯、半正态、指数对拉普拉斯这类「同一充分统计量、不同支撑」的配对。以前要么数值积分,要么每对分布手推一遍。配分函数能写出来,这篇就把 KL 收成同一条 duo Bregman。
对训练损失,这是渐进推广。Blondel 等人已经把普通 Fenchel-Young loss 做成结构化预测的标准件;duo 版本只是允许两个凸生成元不同。Khan 和 Swaroop 的 knowledge-adaptation prior 用过 duo Fenchel-Young 做持续学习里的 change regularizer,这篇只引用、没有自己的下游实验。
DC 规划那一节给 CCCP 一个几何读法,没有新的收敛速率。
论文自己写,嵌套指数族很少被单独拿出来研究,duo 散度在「算嵌套族统计距离」之外的用法还薄。F1 严格压过 F2 时,即使自然参数相同,duo 散度也严格大于 0,所以它是伪散度:不能当度量,也不能无脑替换普通 Bregman 聚类里的损失。
截断指数族可以是 non-steep 的。Del Castillo 对单边截断正态的经典结果就是例子,矩映射不一定把自然参数空间映满,对偶坐标换算会卡住。反向 KL 在支撑不嵌套时是无穷,实现里必须先检查支撑关系。
全文没有「闭式对蒙特卡洛 KL」的数值对照。截断正态公式里 Φ(β)−Φ(α) 在尾部会下溢,数值稳定性没讨论。