Bregman 散度

定义与非负性 ​

设 $C$ 是内积空间中的凸集，$\psi :C\to \mathbb{R}$ 在所讨论点可微且凸。对 $x,y$（其中 $\mathrm{\nabla }\psi (y)$ 存在），定义

$$D_{\psi }(x,y)=\psi (x)-\psi (y)-⟨\mathrm{\nabla }\psi (y),x-y⟩.$$

凸函数公理库凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。的一阶条件给出

$$\psi (x)\ge \psi (y)+⟨\mathrm{\nabla }\psi (y),x-y⟩,$$

所以 $D_{\psi }(x,y)\ge 0$。它描绘函数图像在 $x$ 处比从 $y$ 出发的切平面高出多少；改变生成函数 $\psi$，也就改变了“偏离”的几何。

若 $\psi$ 关于范数 $\Vert \cdot \Vert$ 是 $\alpha$-强凸的，则

$$D_{\psi }(x,y)\ge \frac{\alpha }{2}\Vert x-y{\Vert }^2.$$

严格凸通常保证 $x\ne y$ 时散度为正，但这并未使它成为距离。

三点恒等式 ​

直接展开定义可得

$$D_{\psi }(x,z)-D_{\psi }(x,y)-D_{\psi }(y,z)=⟨\mathrm{\nabla }\psi (y)-\mathrm{\nabla }\psi (z),x-y⟩.$$

欧氏平方距离的勾股关系在非欧几里得优化中由这个恒等式取代。镜像下降证明会把一次更新的线性损失，与两个相邻 Bregman 散度之差相连；对时间求和后，大部分项望远镜消去。

两种几何 ​

取 $\psi (x)=\frac{1}{2}\Vert x{\Vert }_2^2$，便有

$$D_{\psi }(x,y)=\frac{1}{2}\Vert x-y{\Vert }_2^2.$$

因此欧氏投影梯度可以看成 Bregman 几何的特例。对概率单纯形内部取负熵 $\psi (p)=\sum _i{p}_i\log p_i$，则

$$D_{\psi }(p,q)=\sum _i{p}_i\log \frac{p_i}{q_i}=D_{\mathrm{KL}}(p\Vert q).$$

这说明 KL 散度公理库KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。是特定方向、特定定义域上的 Bregman 散度。负熵的镜像更新自然产生乘法权重，而非欧氏加法步；这不是换一种记号，而是几何与约束集合相匹配的结果。

为什么它不是度量 ​

一般有 $D_{\psi }(x,y)\ne D_{\psi }(y,x)$。例如在正实数上取 $\psi (u)=u\log u$，$D_{\psi }(1,2)=1-\log 2$，而 $D_{\psi }(2,1)=2\log 2-1$。它也通常不满足三角不等式；即使平方欧氏例子也不满足普通三角不等式。因而“散度”只承诺非负及同点为零，不承诺度量空间公理库度量空间Metric space配备非负、对称、正定并满足三角不等式的距离函数的集合。结构。

另一个边界来自定义域。负熵在单纯形边界可连续延拓函数值，但梯度含 $\log p_i$，在 $p_i=0$ 处并非有限。书写更新与三点恒等式时，应把第二个参数限制在相对内部，或显式采用次梯度与广义 Bregman 散度；不能默认任意凸函数处处可微。

Bregman 投影也揭示参数方向的重要性。给定凸集 $C$，常定义 ${\mathrm{\Pi }}_C^{\psi }(y)=\arg \underset{x\in C}{min}{D}_{\psi }(x,y)$：优化变量在第一个槽位，梯度锚点是旧点 $y$。交换成 $D_{\psi }(y,x)$ 一般得到另一问题；只有平方欧氏生成函数的对称特例看不出差别。

取一维 $\psi (u)=\frac{1}{2}{u}^2$，三点恒等式退化为平方展开；取负熵并在单纯形上最小化“线性损失 $\eta ⟨g,p⟩$ 加 $D_{KL}(p\Vert q)$”，一阶条件给 $p_i\propto q_i{e}^{-\eta g_i}$。这条乘法更新具体展示了生成函数如何把同一线性信号转成不同几何中的一步，而不是把 KL 仅当作评价预测分布的统计量。

参考资料

• Lev M. Bregman, “The Relaxation Method of Finding the Common Point of Convex Sets,” USSR Computational Mathematics and Mathematical Physics, 1967.
• Amir Beck, Marc Teboulle, “Mirror Descent and Nonlinear Projected Subgradient Methods,” Operations Research Letters, 2003.