エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

ブレグマン距離の定義について考える

本記事は以下の過去記事の内容を用います.

フレシェ微分が勾配に一致するための条件と,勾配は双対空間の要素であることについて考える - エンジニアを目指す浪人のブログ


以下の過去記事も参考になります.

内部と相対的内部の違いについて考える - エンジニアを目指す浪人のブログ

可分距離空間についてすこし考える - エンジニアを目指す浪人のブログ


勉強を進めていて,ブレグマン距離(Bregman divergence)(ブレグマンダイバージェンス)をバナッハ空間上で用いるときとヒルベルト空間上で用いるときとで,同じ式を用いていることにモヤモヤしてしまいました.具体的には,バナッハ空間では内積を定義していないにも関わらず,見かけ上は通常の内積を用いているように思えることに疑問を感じました.そこで,それぞれの定義について調べて,自分なりに再構成しておくことにしました.


本記事の目的に進みます.はじめに,様々な応用がききやすいように抽象的な定義を構成します.文献[1][2][3]を参考にしています.

'--------------------------------------------------------------------------------------------------------------------------------------------
定義1.

可分で回帰的なバナッハ空間 {\displaystyle ( \mathcal{B} , \left\| \cdot \right\|_{\mathcal{B}} ) } 上の,狭義凸かつ二回連続フレシェ微分可能な関数 {\displaystyle \phi : \mathcal{B} \to \mathbb{R} } についてのブレグマン距離 {\displaystyle d_\phi : \mathcal{B} \times \mathcal{B} \to [0,\infty ) } を以下とする.{\displaystyle D_{y}\phi(\cdot) }{\displaystyle \phi }{\displaystyle y } でのフレシェ微分である.

(1.1){\displaystyle \;\;\; d_\phi(x,y) = \phi(x) - \phi(y) - D_{y}\phi(x-y) }

'--------------------------------------------------------------------------------------------------------------------------------------------


つぎに,応用上重要な場合として {\displaystyle \mathcal{B} = \mathbb{R}^n } のときの定義を構成します.凸(文献[4]にあります)な部分集合を {\displaystyle \mathcal{C} \subset \mathbb{R}^n } とし,その相対的内部(relative interior)(冒頭の過去過去(記事内部と相対的内部)にあります)を {\displaystyle \mathrm{ri} (\mathcal{C}) } とします.{\displaystyle \mathbb{R}^n } は可分(separable)であり(文献[5]にあります),あらゆる有限次元ノルム空間は回帰的(reflexive)です(文献[6]にあります).定義1.(1.1)第三項のフレシェ微分を勾配(gradient)に置き換えることができます.

'--------------------------------------------------------------------------------------------------------------------------------------------
定義2.

バナッハ空間 {\displaystyle (\mathbb{R}^n, \left\| \cdot \right\|_{\mathbb{R}^n} ) } 上の,狭義凸かつ二回連続微分可能な関数 {\displaystyle \phi : \mathcal{C} \to \mathbb{R} } についてのブレグマン距離 {\displaystyle d_\phi : \mathcal{C} \times \mathrm{ri} (\mathcal{C}) \to [0,\infty ) } を以下とする.{\displaystyle \nabla \phi(\cdot) }{\displaystyle \phi } の勾配である.

(1.2){\displaystyle \;\;\; d_\phi(x,y) = \phi(x) - \phi(y) - \nabla \phi(y)^T (x-y) }


注意.

先ほどの過去記事(フレシェ微分が勾配に一致するための条件)事実.と(1.9)を用いると,{\displaystyle \phi : \mathcal{C} \to \mathbb{R} }{\displaystyle y \in \mathrm{ri} (\mathcal{C}) } でのフレシェ微分 {\displaystyle D_{y}\phi(\cdot) = A_y : \mathbb{R}^n \to \mathbb{R} } として以下を得る.

(1.3) {\displaystyle \;\;\; D_{y}\phi(\cdot) = A_y(\cdot)  }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \nabla \phi(y)(\cdot) }

したがって以下を得る.

(1.4){\displaystyle \;\;\; d_\phi(x,y) = \phi(x) - \phi(y) - \; D_{y}\phi(x-y) \;\;\;\; \because } (1.1)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \phi(x) - \phi(y) - \nabla \phi(y) (x-y) \;\;\; \because } (1.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \phi(x) - \phi(y) - \nabla \phi(y) \cdot (x-y) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \phi(x) - \phi(y) - \nabla \phi(y)^T (x-y) }

'--------------------------------------------------------------------------------------------------------------------------------------------


バナッハ空間 {\displaystyle \mathcal{B} } の特別な場合として,ヒルベルト空間 {\displaystyle \mathcal{H} } を考えます.内積 {\displaystyle \langle \cdot,\cdot \rangle_{ \mathcal{H} } } を導入し誘導ノルムを {\displaystyle \left\| \cdot \right\|_{\mathcal H} } とします.{\displaystyle \mathcal{H} } の双対空間(dual space)(文献[7]にあります)を {\displaystyle \mathcal{H}^* } とします.あらゆるヒルベルト空間は回帰的です(文献[6]にあります).先ほどの過去記事(フレシェ微分が勾配に一致するための条件)(1.12)(1.13)を一般化したものを利用し、定義1.(1.1)のフレシェ微分内積に置き換えることができます.

'--------------------------------------------------------------------------------------------------------------------------------------------
命題1.

可分なヒルベルト空間 {\displaystyle ( \mathcal{H}, \left\| \cdot \right\|_{ \mathcal{H} } ) } 上の,狭義凸かつ二回連続フレシェ微分可能な関数 {\displaystyle \phi : \mathcal{H} \to \mathbb{R} } についてのブレグマン距離 {\displaystyle d_\phi : \mathcal{H} \times \mathcal{H} \to [0,\infty ) } について,以下をみたすようなただ一つの {\displaystyle g \in \mathcal{H}} が存在する.

(1.5){\displaystyle \;\;\; d_\phi(x,y) = \phi(x) - \phi(y) - \langle g, x - y \rangle_{\mathcal{H}} }


証明.

先ほどの定義1.{\displaystyle \mathcal{H} } 上で考える.フレシェ微分 {\displaystyle D_{y}\phi(\cdot) = A_y : \mathcal{H} \to \mathbb{R} }有界線形汎関数とみなすこともできるので,リースの表現定理(Riesz representation theorem)(文献[8]にあります)より,以下をみたすようなただ一つの {\displaystyle g_{A_y} \in \mathcal{H}} が存在する.

(1.6){\displaystyle \;\;\; A_y (h) = \langle g_{A_y} \ , \ h \rangle_{\mathcal{H}}  \;\;\;\; \mathrm{for \ all} \;\; h \in \mathcal{H} }

(1.7){\displaystyle \;\;\; \left\| g_{A_y}  \right\|_{ \mathcal{H} } = \left\| A_y \right\|_{ \mathcal{H}^* }  }

{\displaystyle \phi : \mathcal{H} \to \mathbb{R} }{\displaystyle y } でのフレシェ微分 {\displaystyle D_{y}\phi(\cdot) = A_y : \mathcal{H} \to \mathbb{R} } として以下を得る.

(1.8){\displaystyle \;\;\; D_{y}\phi(\cdot) = A_y(\cdot) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \langle g_{A_y} \ , \ \cdot \ \rangle_{\mathcal{H}} \;\;\; \because } (1.6)

したがって以下を得る.

(1.9){\displaystyle \;\;\; d_\phi(x,y) = \phi(x) - \phi(y) - D_{y}\phi(x-y) \;\;\;\;\;\; \because } (1.1)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  = \phi(x) - \phi(y) - \langle g_{A_y} \ , \ x - y \rangle_{\mathcal{H}} \;\;\;\; \because } (1.8)

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


最後に,応用上重要な場合として {\displaystyle \mathcal{H} = \mathbb{R}^n } のときを考えます.このとき誘導ノルムはユークリッドノルム {\displaystyle \left\| \cdot \right\|_2 } です.定義2.命題1.より,以下のように構成すればよさそうです.結局これは定義2.と同じものです.

'--------------------------------------------------------------------------------------------------------------------------------------------
定義3.

ヒルベルト空間 {\displaystyle (\mathbb{R}^n, \left\| \cdot \right\|_2 ) } 上の,狭義凸かつ二回連続微分可能な関数 {\displaystyle \phi : \mathcal{C} \to \mathbb{R} } についてのブレグマン距離 {\displaystyle d_\phi : \mathcal{C} \times \mathrm{ri} (\mathcal{C}) \to [0,\infty ) } を以下とする.

(1.10){\displaystyle \;\;\; d_\phi(x,y) = \phi(x) - \phi(y) - \langle \nabla \phi(y), x-y \rangle }

'--------------------------------------------------------------------------------------------------------------------------------------------


以上,ブレグマン距離の定義について考えてみました.



参考文献
[1] Fischer, A. (2010), Journal of Multivariate Analysis, Vol.101, Issue.9, pp.2207-2221.
[2] Frigyik, B.A., Srivastava, S., and Gupta, M.R. (2008), Functional Bregman Divergence and Bayesian Estimation of Distributions, IEEE Transactions on Infomartion Theory, Vol.54, No.11, pp.5130-5139.
[3] Banerjee, A., Merugu, S., Dhillon, I.S., Ghosh, J.,(2005), Clustering with Bregman Divergences, Journal of Machine Learning Research, Vol.6, pp.1705-1749.
[4] Wikipedia Convex set のページ https://en.wikipedia.org/wiki/Convex_set
[5] Wikipedia Separable space のページ https://en.wikipedia.org/wiki/Separable_space
[6] Wikipedia Reflexive space のページ https://en.wikipedia.org/wiki/Reflexive_space
[7] Wikipedia Dual space のページ https://en.wikipedia.org/wiki/Dual_space
[8] Wikipedia Riesz representation theorem のページ https://en.wikipedia.org/wiki/Riesz_representation_theorem

おまけ
[1] へのリンク
https://www.lpsm.paris/dw/lib/exe/fetch.php?media=users:fischer:quantization_and_clustering_with_bregman_divergences.pdf
[2] へのリンク
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.323.8330&rep=rep1&type=pdf
[3] へのリンク
https://www.jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf