ブレグマンダイバージェンス

数学、特に統計学と情報幾何学 において、ブレグマン ダイバージェンスまたはブレグマン距離は、厳密に凸関数で定義される 2 点間の差の尺度であり、重要なダイバージェンスクラスを形成します。点が確率分布として解釈される場合(特にパラメトリック モデルのパラメーターの値または観測値のデータ セットとして)、結果として得られる距離は統計距離です。最も基本的なブレグマン ダイバージェンスは、ユークリッド距離の 2 乗です。

ブレグマン ダイバージェンスは、計量に似ていますが、三角不等式(常に) も対称性 (一般に) も満たしません。ただし、ピタゴラスの定理の一般化は満たしており、情報幾何学では、対応する統計多様体は(双対)平坦多様体として解釈されます。これにより、最適化理論の多くの手法を、幾何学的には最小二乗法の一般化として、ブレグマン ダイバージェンスに一般化できます。

ブレグマン ダイバージェンスは、1967 年にこの概念を導入した ロシアの数学者Lev M. Bregmanにちなんで名付けられました。

を凸集合上で定義された連続的に微分可能な厳密に凸な関数とします 。 ${\displaystyle F\colon \Omega \to \mathbb {R} }$ ${\displaystyle \オメガ}$

点に対するFに関連付けられたブレグマン距離は、点pにおけるFの値と、点pで評価された点qの周りのFの1次テイラー展開の値との差です。 ${\displaystyle p,q\in \Omega }$

${\displaystyle D_{F}(p,q)=F(p)-F(q)-\langle \nabla F(q),pq\rangle .}$

• 非負性:すべての に対して、。これは の凸性の結果です。${\displaystyle D_{F}(p,q)\geq 0}$${\displaystyle p}$${\displaystyle q}$${\displaystyle F}$
• 正性:が厳密に凸である場合、そのときに限ります。${\displaystyle F}$${\displaystyle D_{F}(p,q)=0}$${\displaystyle p=q}$
• アフィン差までの一意性: iffはアフィン関数です。${\displaystyle D_{F}=D_{G}}$${\displaystyle FG}$
• 凸性:最初の引数では凸ですが、2 番目の引数では必ずしも凸ではありません。 F が厳密に凸である場合、最初の引数では厳密に凸です。 ${\displaystyle D_{F}(p,q)}$${\displaystyle D_{F}(p,q)}$
  • たとえば、f(x) = |x| をとり、0 で平滑化し、 を取り、 とします。${\displaystyle y=1,x_{1}=0.1,x_{2}=-0.9,x_{3}=0.9x_{1}+0.1x_{2}}$${\displaystyle D_{f}(y,x_{3})\approx 1>0.9D_{f}(y,x_{1})+0.1D_{f}(y,x_{2})\approx 0.2}$
• 線形性: ブレグマン距離を関数F上の演算子として考えると、非負の係数に関して線形になります。言い換えると、厳密に凸で微分可能な場合、およびの場合、${\displaystyle F_{1},F_{2}}$${\displaystyle \lambda \geq 0}$

${\displaystyle D_{F_{1}+\lambda F_{2}}(p,q)=D_{F_{1}}(p,q)+\lambda D_{F_{2}}(p,q)}$

• 双対性: F が厳密に凸ならば、関数 F は凸共役を 持ち、これもまた厳密に凸であり、ある凸集合上で連続的に微分可能である。 に関して定義されるブレグマン距離はと双対であり、${\displaystyle F^{*}}$${\displaystyle \Omega^{*}}$${\displaystyle F^{*}}$${\displaystyle D_{F}(p,q)}$

${\displaystyle D_{F^{*}}(p^{*},q^{*})=D_{F}(q,p)}$

ここで、およびはp と q に対応する双対点です。${\displaystyle p^{*}=\nabla F(p)}$${\displaystyle q^{*}=\nabla F(q)}$

さらに、同じ表記法を使用すると、

${\displaystyle D_{F}(p,q)=F(p)+F^{*}(q^{*})-\langle p,q^{*}\rangle }$

• 積分形式:テイラーの定理の積分剰余形式により、ブレグマン ダイバージェンスは、ブレグマン ダイバージェンスの引数間の線分に沿ったヘッセ行列の積分として表すことができます。${\displaystyle F}$

• 最小化としての平均: ブレグマン ダイバージェンスに関する重要な結果は、ランダム ベクトルが与えられた場合、平均ベクトルはランダム ベクトルからの期待されるブレグマン ダイバージェンスを最小化するということです。この結果は、セットの平均がセット内の要素に対する総二乗誤差を最小化するという教科書的な結果を一般化したものです。この結果は、ベクトルの場合 (Banerjee 他 2005) によって証明され、関数/分布の場合 (Frigyik 他 2008) に拡張されました。この結果は、特にベイズ推定において、ランダム セットの代表として平均を使用することをさらに正当化するため重要です。
• ブレグマン球は有界であり、 X が閉じている場合にコンパクトです。 によって、 x を中心とし、半径 r を持つブレグマン球を定義します。が有限次元のとき、が の相対的内部にある場合、または がで局所的に閉じている場合（つまり、を中心とし、 が閉じている閉球が存在する場合）、 はすべての に対して有界です。が閉じている場合、 はすべての に対してコンパクトです。${\displaystyle B_{f}(x,r):=\left\{y\in X:D_{f}(y,x)\leq r\right\}}$${\displaystyle X\subset \mathbb {R} ^{n}}$${\displaystyle \forall x\in X}$${\displaystyle x}$${\displaystyle X}$${\displaystyle X}$${\displaystyle x}$${\displaystyle B(x,r)}$${\displaystyle x}$${\displaystyle B(x,r)\cap X}$${\displaystyle B_{f}(x,r)}$${\displaystyle r}$${\displaystyle X}$${\displaystyle B_{f}(x,r)}$${\displaystyle r}$
• 余弦定理：^[1]

いかなる${\displaystyle p,q,z}$

${\displaystyle D_{F}(p,q)=D_{F}(p,z)+D_{F}(z,q)-(pz)^{T}(\nabla F(q)-\nabla F(z))}$

• 平行四辺形の法則：任意のに対して、${\displaystyle \theta ,\theta _{1},\theta _{2}}$

${\displaystyle B_{F}\left(\theta _{1}:\theta \right)+B_{F}\left(\theta _{2}:\theta \right)=B_{F}\left(\theta _{1}:{\frac {\theta _{1}+\theta _{2}}{2}}\right)+B_{F}\left(\theta _{2}:{\frac {\theta _{1}+\theta _{2}}{2}}\right)+2B_{F}\left({\frac {\theta _{1}+\theta _{2}}{2}}:\theta \right)}$

• ブレグマン射影: 任意の に対して、の への「ブレグマン射影」を定義します。${\displaystyle W\subset \Omega }$${\displaystyle q}$${\displaystyle W}$

${\displaystyle P_{W}(q)={\text{argmin}}_{\omega \in W}D_{F}(\omega ,q)}$。 それから

• • が凸である場合、投影は存在する場合に一意です。${\displaystyle W}$
  • が空でなく、閉じていて、凸であり、有限次元である場合、射影は存在し、一意である。^[3]${\displaystyle W}$${\displaystyle \Omega \subset \mathbb {R} ^{n}}$
• 一般化されたピタゴラスの定理：^[1]

いずれの場合も、 ${\displaystyle v\in \Omega ,a\in W}$

${\displaystyle D_{F}(a,v)\geq D_{F}(a,P_{W}(v))+D_{F}(P_{W}(v),v).}$

これは、 が の相対内部にある場合の等式です。 ${\displaystyle P_{W}(v)}$${\displaystyle W}$

特に、がアフィン集合である場合、これは常に発生します。 ${\displaystyle W}$

• 三角不等式の欠如: ブレグマン ダイバージェンスは本質的にユークリッド距離の二乗の一般化であるため、三角不等式は存在しません。実際、は正または負の可能性があります。${\displaystyle D_{F}(z,x)-D_{F}(z,y)-D_{F}(y,x)=\langle \nabla f(y)-\nabla f(x),zy \rangle }$

• 非負性と正性: Jensen の不等式を使用します。
• アフィン差分までの一意性: いくつかの を固定すると、他の任意の に対して、定義により が成り立ちます。${\displaystyle x\in \Omega }$${\displaystyle y\in \Omega }$${\displaystyle F(y)-G(y)=F(x)-G(x)+\langle \nabla F(x)-\nabla G(x),yx\rangle }$
• 最初の引数の凸性: 定義により、F の凸性を使用します。厳密な凸性の場合も同様です。
• F における線形性、余弦定理、平行四辺形の法則: 定義による。
• 二重性：図1を参照。^[4]
• ブレグマン球は有界であり、X が閉じている場合はコンパクトです。

を修正します。 をアフィン変換して、 となるようにします。 ${\displaystyle x\in X}$${\displaystyle f}$${\displaystyle \nabla f(x)=0}$

となるような をとります。次に、ユークリッド球面上の の「放射方向」微分を考えます。 ${\displaystyle \epsilon >0}$${\displaystyle \partial B(x,\epsilon )\subset X}$${\displaystyle f}$${\displaystyle \partial B(x,\epsilon )}$

${\displaystyle \langle \nabla f(y),(y-x)\rangle }$すべてに対して。 ${\displaystyle y\in \partial B(x,\epsilon )}$

はコンパクトなので、ある で最小値を達成します。 ${\displaystyle \partial B(x,\epsilon )\subset \mathbb {R} ^{n}}$${\displaystyle \delta }$${\displaystyle y_{0}\in \partial B(x,\epsilon )}$

は厳密に凸なので、です。 ${\displaystyle f}$${\displaystyle \delta >0}$${\displaystyle B_{f}(x,r)\subset B(x,r/\delta )\cap X}$

は内にあるので、は 内で連続しており、したがって である場合は は閉じています。 ${\displaystyle D_{f}(y,x)}$${\displaystyle C^{1}}$${\displaystyle y}$${\displaystyle D_{f}}$${\displaystyle y}$${\displaystyle B_{f}(x,r)}$${\displaystyle X}$

• が閉じていて凸状のとき、投影は明確に定義されます。${\displaystyle P_{W}}$${\displaystyle W}$

を固定します。 をいくつか取り、 とします。次に、ブレグマン球 を描きます。これは閉じていて有界であるため、コンパクトです。 は連続かつ厳密に凸であり、 の下では有界であるため、 は 上で一意の最小値を実現します。 ${\displaystyle v\in X}$${\displaystyle w\in W}$${\displaystyle r:=D_{f}(w,v)}$${\displaystyle B_{f}(v,r)\cap W}$${\displaystyle D_{f}(\cdot ,v)}$${\displaystyle 0}$

• ピタゴラスの不等式。

余弦定理により、はで最小化し、凸であるため、でなければなりません。 ${\displaystyle D_{f}(w,v)-D_{f}(w,P_{W}(v))-D_{f}(P_{W}(v),v)=\langle \nabla _{y}D_{f}(y,v)|_{y=P_{W}(v)},w-P_{W}(v)\rangle }$${\displaystyle \geq 0}$${\displaystyle P_{W}(v)}$${\displaystyle D_{f}(\cdot ,v)}$${\displaystyle W}$${\displaystyle W}$

• が の相対内部にある場合のピタゴラスの等式。${\displaystyle P_{W}(v)}$${\displaystyle X}$

の場合、 は相対的内部にあるため、から の反対方向に移動して を減少させることができますが、矛盾があります。 ${\displaystyle \langle \nabla _{y}D_{f}(y,v)|_{y=P_{W}(v)},w-P_{W}(v)\rangle >0}$${\displaystyle w}$${\displaystyle P_{W}(v)}$${\displaystyle w}$${\displaystyle D_{f}(y,v)}$

したがって。 ${\displaystyle \langle \nabla _{y}D_{f}(y,v)|_{y=P_{W}(v)},w-P_{W}(v)\rangle =0}$

• における唯一の対称的なブレグマンダイバージェンスは、一般化ユークリッド距離の二乗（マハラノビス距離）であり、つまり、ある正定値に対してである。^[5]${\displaystyle X\subset \mathbb {R} ^{n}}$${\displaystyle D_{f}(y,x)=(y-x)^{T}A(y-x)}$ ${\displaystyle A}$

証拠

任意の に対して、を定義します。 とします。 ${\displaystyle x\neq y\in X}$${\displaystyle r=\|y-x\|,v=(y-x)/r,g(t)=f(x+tv)}$${\displaystyle t\in [0,r]}$${\displaystyle z(t)=x+tv}$

するとに対して となり、 は連続なので に対しても となります。 ${\displaystyle g'(t)=\langle \nabla f(z(t)),v\rangle }$${\displaystyle t\in (0,r)}$${\displaystyle \nabla f}$${\displaystyle t=0,r}$

次に、図から、すべての に対して が上で線形でなければならないことがわかります。 ${\displaystyle D_{f}(x;z(t))=D_{f}(z(t);x)}$${\displaystyle t\in [0,r]}$${\displaystyle g'(t)}$${\displaystyle t\in [0,r]}$

したがって、 は任意の方向に沿って線形に変化することがわかります。次の補題により、は 2 次関数です。 も厳密に凸であるため、 の形になります。ここで です。 ${\displaystyle \nabla f}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f(x)+x^{T}Ax+B^{T}x+C}$${\displaystyle A\succ 0}$

補題:が の開部分集合であり、連続導関数を持ち、任意の線分 が与えられた場合、関数 はにおいて線形であり、 は二次関数である。 ${\displaystyle S}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle f:S\to \mathbb {R} }$${\displaystyle [x,x+v]\subset S}$${\displaystyle h(t):=\langle \nabla f(x+tv),v\rangle }$${\displaystyle t}$${\displaystyle f}$

証明のアイデア: 任意の 2 次関数 に対して、 は依然としてそのような導関数線形性を持つので、いくつかの 2 次関数を減算して がゼロになることを示します。 ${\displaystyle q:S\to \mathbb {R} }$${\displaystyle f-q}$${\displaystyle f}$

証明のアイデアは の場合に完全に説明できるため、この場合にはそれを証明します。 ${\displaystyle S=\mathbb {R} ^{2}}$

導関数の線形性により、は 内の任意の線分上の 2 次関数です。 がx 軸、y 軸、および直線上で常に 0 になるような 4 つの 2 次関数を減算します。 ${\displaystyle f}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle g:=f-q_{0}-q_{1}-q_{2}-q_{3}}$${\displaystyle \{x=y\}}$

適切に選択された について、とします。ここで、 を使用して線形項を除去し、 を使用して3 本の線に沿った二次項を除去します。 ${\displaystyle q_{0}(x,y)=f(0,0)+\nabla f(0,0)\cdot (x,y),q_{1}(x,y)=A_{1}x^{2},q_{2}(x,y)=A_{2}y^{2},q_{3}(x,y)=A_{3}xy}$${\displaystyle A_{1},A_{2},A_{3}}$${\displaystyle q_{0}}$${\displaystyle q_{1},q_{2},q_{3}}$

${\displaystyle \forall (x,y)\in \mathbb {R} ^{2}}$原点上にはありませんが、を横切る直線が存在します。この直線はx 軸、y 軸、直線と 3 つの異なる点で交差します。は 上で 2 次関数であり、 は 3 つの異なる点で 0 であるため、は 上でも 0 であり、したがって になります。したがって は2 次関数です。 ${\displaystyle l}$${\displaystyle (x,y)}$${\displaystyle \{x=y\}}$${\displaystyle g}$${\displaystyle l}$${\displaystyle g}$${\displaystyle l}$${\displaystyle g(x,y)=0}$${\displaystyle f=q_{0}+q_{1}+q_{2}+q_{3}}$

次の 2 つの特徴付けは、 （ 上のすべての確率測度の集合、 ）上の発散に対するものです。 ${\displaystyle \Gamma _{n}}$${\displaystyle \{1,2,...,n\}}$${\displaystyle n\geq 2}$

上の発散を型の任意の関数として定義し、すべての に対して次の式が成り立つようにします。 ${\displaystyle \Gamma _{n}}$${\displaystyle D:\Gamma _{n}\times \Gamma _{n}\to [0,\infty ]}$${\displaystyle D(x,x)=0}$${\displaystyle x\in \Gamma _{n}}$

• ブレグマンダイバージェンスとfダイバージェンスの両方である唯一のダイバージェンスは、カルバック・ライブラーダイバージェンスです。^[6]${\displaystyle \Gamma _{n}}$
• の場合、データ処理不等式を満たす 上の任意のブレグマンダイバージェンスは、カルバック・ライブラーダイバージェンスでなければならない。（実際、より弱い「十分性」の仮定で十分である。） の場合には反例が存在する。^[6]${\displaystyle n\geq 3}$${\displaystyle \Gamma _{n}}$${\displaystyle n=2}$

ブレグマン ダイバージェンス が与えられた場合、 によって定義されるその「反対」は、一般にブレグマン ダイバージェンスではありません。たとえば、カルバック ライバー ダイバージェンスは、ブレグマン ダイバージェンスと f-ダイバージェンスの両方です。その逆も f-ダイバージェンスですが、上記の特徴により、逆 KL ダイバージェンスはブレグマン ダイバージェンスにはなり得ません。 ${\displaystyle D_{F}}$${\displaystyle D_{F}^{*}(v,w)=D_{F}(w,v)}$

• マハラノビス距離の 二乗は凸二次形式によって生成されます。${\displaystyle D_{F}(x,y)={\tfrac {1}{2}}(x-y)^{T}Q(x-y)}$ ${\displaystyle F(x)={\tfrac {1}{2}}x^{T}Qx}$
• ブレグマン距離の標準的な例は、ユークリッド距離の二乗 です。これは、が恒等式であるとき、つまり に対して となる、上記の の特殊なケースとして生じます 。前述のように、アフィン差分、つまり に追加された低次の階数は とは無関係です。${\displaystyle D_{F}(x,y)=\|x-y\|^{2}}$${\displaystyle Q}$${\displaystyle F(x)=\|x\|^{2}}$${\displaystyle F}$${\displaystyle D_{F}}$
• 一般化されたカルバック・ライブラー距離

${\displaystyle D_{F}(p,q)=\sum _{i}p(i)\log {\frac {p(i)}{q(i)}}-\sum p(i)+\sum q(i)}$

負のエントロピー関数 によって生成される

${\displaystyle F(p)=\sum _{i}p(i)\log p(i)}$

単体に制限すると、最後の2つの項が打ち消され、分布の通常のカルバック・ライブラー分布が得られます。

• 板倉－斉藤間距離

${\displaystyle D_{F}(p,q)=\sum _{i}\left({\frac {p(i)}{q(i)}}-\log {\frac {p(i)}{q(i)}}-1\right)}$

凸関数によって生成される

${\displaystyle F(p)=-\sum _{i}\log p(i)}$

計算幾何学における重要なツールは、射影双対性という考え方です。これは、入射と上下関係を維持しながら、点を超平面に、またその逆へマッピングするものです。射影双対には数多くの解析形式がありますが、一般的な形式の 1 つは、点を超平面にマッピングします。このマッピングは、(超平面をその法線と同一視して) 点 p をその双対点 に取る凸共役マッピングとして解釈できます。ここで、F はd次元放物面を定義します。 ${\displaystyle p=(p_{1},\ldots p_{d})}$${\displaystyle x_{d+1}=\sum _{1}^{d}2p_{i}x_{i}}$${\displaystyle p^{*}=\nabla F(p)}$${\displaystyle x_{d+1}=\sum x_{i}^{2}}$

ここで、放物面を任意の凸関数に置き換えると、標準的な射影双対の入射と上下の特性を保持する異なる双対写像が得られます。これは、ボロノイ図やドロネー三角形分割などの計算幾何学における自然な双対概念が、任意のブレグマン ダイバージェンスによって定義される距離空間でその意味を保持することを意味します。したがって、「通常の」幾何学からのアルゴリズムは、これらの空間に直接拡張されます (Boissonnat、Nielsen、および Nock、2010)

ブレグマン ダイバージェンスは、歪んだジェンセン ダイバージェンスの極限ケースとして解釈できます(Nielsen and Boltz, 2011 を参照)。ジェンセン ダイバージェンスは比較凸性を使用して一般化でき、これらの歪んだジェンセン ダイバージェンスの一般化の極限ケースは、一般化されたブレグマン ダイバージェンスをもたらします (Nielsen and Nock, 2017 を参照)。ブレグマン コード ダイバージェンス^[7]は、接線の代わりにコードを取ることで得られます。

ブレグマン ダイバージェンスは、行列間、関数間、および測度 (分布) 間でも定義できます。行列間のブレグマン ダイバージェンスには、スタイン損失とフォン ノイマン エントロピーが含まれます。関数間のブレグマン ダイバージェンスには、全二乗誤差、相対エントロピー、および二乗バイアスが含まれます。定義とプロパティについては、以下の Frigyik らによる参考文献を参照してください。同様に、ブレグマン ダイバージェンスは、凸関数の離散アナログとして知られるサブモジュラー セット関数を通じて、セットに対しても定義されています。サブモジュラー ブレグマン ダイバージェンスには、ハミング距離、精度と再現率、相互情報量、およびその他のセット ベースの距離尺度など、いくつかの離散距離尺度が含まれます (サブモジュラー ブレグマンの詳細とプロパティについては、Iyer & Bilmes、2012 を参照してください)。

一般的な行列ブレグマンダイバージェンスのリストについては、^{[8]の表15.1を参照。}

機械学習では、ブレグマンダイバージェンスはバイテンパーロジスティック損失を計算するために使用され、ノイズの多いデータセットではソフトマックス関数よりも優れたパフォーマンスを発揮します。^[9]

ブレグマン ダイバージェンスは、勾配降下法やヘッジ アルゴリズムなどの機械学習で使用される最適化アルゴリズムを含むミラー降下法の定式化に使用されます。