如何理解Bregman divergence？

12-29

我也來稍微說下這個Bregman divergence。默認題主（和一般人）應該都是在機器學習的一些paper里首先看到這個東西的。我之前也是，research用到mirror descent的時候接觸了這套定義和theory。

我就講點簡單的intuition（一般人不太注意的）。通俗來說，什麼是Bregman divergence，就是如果你抽象地定義一種在特定空間里兩個點之間的「距離」，然後在這些點滿足任意的概率分布的情況下，這些點的平均值點（mean point）一定是空間中距離這些點的平均距離最小的點（這是一個很正常的我們希望對「距離」的定義吧）。

令人吃驚的是，這個條件是當且僅當的，也就是說，反過來說，給定一個 $mathbb{R}^n imes mathbb{R}^n ightarrow mathbb{R}$ 上的divergence函數 $d(x,y)$ ，如果滿足對所有 $mathbb{R}^n$ 上的隨機變數(random variable) $X$ , $mathbb{E}[X]$ 都是 $y ightarrow mathbb{E}[d(X,y)]$ 唯一的minimizer，那麼d一定是一個Bregman divergence。我們一般所以也說Bregman divergence是exhastive（窮盡）的，即它包含了一切對「正常距離」的定義。

這在理論上是一個很深刻的結果，尤其是一會當我介紹Bregman divergence定義的時候，它形式上看起來其實並沒有那麼exhastive，然而實際上這件事情卻確確實實發生了。

這個結果最早出現於這篇paper：[1] Banerjee, Arindam, Xin Guo, and Hui Wang. On the optimality of conditional expectation as a Bregman predictor. IEEE Transactions on Information Theory 51.7 (2005): 2664-2669. , 有一定數學水平的童鞋可以自行參看證明；或者結合appendix看這篇：[2] Banerjee, Arindam, et al. Clustering with Bregman divergences. Journal of machine learning research 6.Oct (2005): 1705-1749. 我這個回答不涉及理論推導，只稍微講講intuition。

因為這個divergence function是個抽象的概念，我們就從最具體的形式入手開始介紹。就拿最常見的均方歐式距離（squared Euclidean distance）來舉例子，即任給 $mathbb{R}^n$ 中的兩個點 $x,y$ ，定義

$d^2(x,y):=sum_{i=1}^n(x_i-y_i)^2$

這是個最常見的「距離」定義，大家應該沒有異議吧。注意到，如果我們定義內積 $left< x,y ight>:=sum_{i=1}^n x_iy_i$

和歐式模 $| x | := sqrt{left< x,x ight>}$ 那麼 $d^2$ 也可以寫成 $d^2(x,y)=|x-y|^2= left< x-y,x-y ight> = |x| ^2 - |y|^2-left<2y,x-y ight>$ 。

接下來我們注意到 $2y$ 是 $|y|^2$ 的導數，因此，後面一項

$|y|^2+left<2y,x-y ight>$ 的值便是函數 $f(x)=|x|^2$ 在 $y$ 點切線在 $x$ 處的取值！所以均方歐式距離的幾何描述便是歐式模函數在x點和其在y點切線在x點估計的差！用一張圖（n=1）表示則如下，藍色部分就是 $d^2(x,y)$ 。

那麼這之後，一個很自然的想法就是把這個定義拓展，即對任意 $mathbb{R}^n$ 上的函數 $f$ ，我們顯然都可以定義「距離」 $d(x,y): = f(x)-( f(y)+left< abla f(y), x-y ight> )$ 。當然，為了讓這個定義well-defined,我們至少需要確保 $d(x,y)$ 永遠是非負的，從幾何上來說那就是 $f$ 永遠在其切線的上方，因為 $d(x,y)geq 0, forall~ x,yin mathbb{R}^n$ 等價於 $f(x)geq f(y)+left< abla f(y), x-y ight> , forall~ x,yin mathbb{R}^n$ 。而我們從凸分析知道這等價於（對適當光滑的函數來說） $f$ 是凸（convex）的。由此，我們便得到了Bregman divergence函數 $d(x,y)$ 的一般定義。

*歷史淵源：這是Bregman最早提出定義的paper：[3] Bregman, Lev M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics 7.3 (1967): 200-217. 第一次被叫Bregman divergence這名字是在這篇paper：[4] Censor, Yair, and Arnold Lent. An iterative row-action method for interval convex programming. Journal of Optimization theory and Applications 34.3 (1981): 321-353.

既然我們先前已經提到Bregman divergence實際上是窮盡的，所以也不意外我們一般見到的「距離」都可以是Bregman divergence。下圖提供了常見距離的生成方式（圖片來自[2]）,比如我們熟知的KL divergence可以通過令 $f(x)$ 為Shannon entrpy function來生成。

好了，最後再講一點high-level的idea。我看到有些答主已經講了一些Bregman divergence的應用，這主要是因為我們在做一些一階演算法收斂性分析的時候往往是iterative method，中間式子的項直接會可以用到Bregman divergence的性質（有位匿名答主已經提了不少，不過他沒有提及對一個凸集做Bregman projection是唯一的）。這些演算法往往和常見的一階演算法稍微有一些區別，因為它們往往用了更特殊的投影迭代方式因此常規的一階演算法收斂性分析不適用（一個經典的例子，simplex ${xin mathbb{R}^n: sum_{i=1}^n x_i=1, xgeq 0 }$ 上的凸函數優化問題，用KL-divergence可以setup成一個無約束一階演算法問題，因為中間的projection步驟有顯式解，這也叫做mirror descent，詳見著名paper: [5] Ben-Tal, Aharon, Tamar Margalit, and Arkadi Nemirovski. The ordered subsets mirror descent optimization method with applications to tomography. SIAM Journal on Optimization 12.1 (2001): 79-108.）。因為這個回答談如何理解所以我就不再提更多application了。

回過頭來再說說為什麼我覺得一開頭我所指出的當且僅當條件很深刻，我們知道那個結果是對所有一般的概率分布都成立的，而Bregman divergence其實限定了必須是由凸函數來生成的，而這竟然就足夠了。總之我不知道你們怎麼看，我第一次看到這個結果是很驚訝的，後來想想可能和Jensen"s inequality有關，畢竟凸函數隱含了一部分對於期望的度量（但這也不能說明問題，總之這是convexity一個很深刻的體現），具體證明有興趣的請參閱[1]或[2]，主要是利用最小化性質分析導函數。

不開心強答此題泄泄憤

Bregman divergence的一個主要用途：複合非光滑凸優化（composite nonsmooth convex minimization）的一階演算法設計和複雜度分析。

設計思路：將一階演算法看作是MM（Majorization-Minimization）演算法, 單步迭代都是最小化目標函數的一個凸的上界函數, 在當前迭代點處目標函數與上界函數有相同函數值，這樣能保證目標函數序列單調下降。Bregman類演算法就是將這個上界函數設計為：一階梯度項 + L*Bregman distance，這裡L是待設計參數，Bregman distance是由Bregman divergence生成的距離函數。

複雜度分析難點：根據現有經驗，可以猜到通常一階演算法具有O(1/t)的收斂速度。然而上述設計思路無法從理論上保證這一點，也沒有理論依據來確定參數L的最佳數值。分析光滑目標函數的梯度下降演算法的證明可以發現，梯度下降演算法採用的距離函數是L2範數函數，參數L是目標函數的梯度與這個範數有關的Lipschitz常數，關鍵引理是與此距離函數和Lipschitz常數有關的一個descent lemma。關於Lipschitz條件的介紹，請讀 @王哲的專欄文章非凸優化基石：Lipschitz Condition。

因此，要理解Bregman divergence及對應的一階Bregman類演算法，關鍵點就是確認對應的descent lemma和類似的Lipschitz常數是什麼？這個問題同時在[1]和[2]給出了統一而清晰的回答。對於只有單純形約束的凸優化問題，熟悉Mirror descent演算法[3]的朋友知道，用到的是L1範數及其對應的Lipschitz常數，這是Bregman演算法的一個直接案例。

[1] Bolte J, Bauschke H, Teboulle M. A descent Lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[J]. Mathematics of Operations Research, 2016.

[2] Lu H, Freund R M, Nesterov Y. Relatively-Smooth Convex Optimization by First-Order Methods, and Applications[J]. arXiv preprint arXiv:1610.05708, 2016.

[3]Amir Beck, Marc Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization[J]. Operations Research Letters, Volume 31, Issue 3, Pages 167-175, 2003.

Bregman 散度（Bregman divergence or divergence distance）是一種類似於距離度量的方式，用于衡量兩者之間的差異大小。

定義

可以認為，Bregman散度是損失或者失真函數。考慮如下情況：設點 p 是點 q 的失真或者近似的點，也就是說可能 p 是由 q 添加了一些雜訊形成的，損失函數的目的是度量 p 近似 q 導致的失真或者損失，因而Bregman散度可以用作相異性函數。

更為形式化地，定義函數 F:Ω→R 。其中Ω是一個凸集，F是一個嚴格凸二次可微函數。
由該函數F生成的Bregman散度通過下面的公式給出：

DF(p.q)=F(p)?F(q)???F(q),(p?q)?

其中?F(q)表示函數F在q處的梯度，(p?q)表示兩個向量的差，??F(q),(p?q)?是?F(q)和(p?q)的內積。

以上公式的後半部分L(p,q)=F(q)+??F(q),(p?q)?表示了函數F在q點附近的線性部分，而Bregman散度是一個函數與該函數的線性近似（一階Taylor展開）之間的差，選取不同的函數F可以得到不同的Bregman散度。

性質

1.不滿足三角不等式，即對任意的x、y、z，以下不等式不一定成立：

DF(x,z)≤DF(x,ｙ)＋DF(ｙ,z)

2.不滿足對稱性，即對任意ｘ和ｙ，下式不一定成立：

DF(x,y)=DF(y,x)

3. 非負性：對於所有的p和q，滿足DF(p,q)≥0,這一點是由函數F的凸性決定的；

4. 凸性：DF(p,q)在第一個參數上是凸的,但是在第二個參數上不一定是；

5. 線性：如果我們將Bregman散度考慮為函F的操作符，那麼它對於非負的係數是線性的。即對於嚴格凸且可微的函數F1和F2，以及係數λ≥0，滿足：

DF1+λF2(p,q)=DF1(p,q)+λDF2(p,q)

6. 對偶性：函數F具有凸的共軛F?，則F?的Bregman散度與DF(p,q)存在著如下的聯繫：

D?F(p?,q?)=DF(q,p)

其中，p?=?F(p)， q?=?F(q)是p和q的對偶點。

舉例

選擇不同的函數F，就可以得到不同的Bregman散度形式：

歐式距離平方

DF(x,y)=||x?y||2

是令F(x)=||x||2得到的。

馬氏距離平方

DF(x,y)=12(x?y)TQ(x?y)

是令F(x)=12xTQx得到的，這可以看作是以上歐式距離平方的推廣。

KL散度

DF(p,q)=∑p(i)logp(i)q(i)?∑p(i)+∑q(i)

是令F(p)=∑p(i)logp(i)?∑p(i)得到的。

IS距離

DF(p,q)=∑i(p(i)q(i)?logp(i)q(i)?1)

是令F(p)=?∑p(i)得到的。

見：Bregman divergence