브레그만 발산

수학, 특히 통계학 및 정보 기하학에서, Bregman difference 또는 Bregman distance는 두 점 사이의 차이를 측정하는 척도로, 엄격히 볼록한 함수의 관점에서 정의된다. 그것들은 분기의 중요한 부류를 형성한다.점이 확률 분포(특히 모수 모형의 모수 값 또는 관측된 값의 데이터 집합)로 해석되는 경우, 결과 거리는 통계적 거리가 된다.가장 기본적인 브레그먼의 차이는 유클리드 거리 제곱이다.null

브레그만 분수는 측정 기준과 유사하지만 삼각 불평등(언제나)과 대칭(일반적으로)을 모두 만족시키지 못한다.그러나 그들은 피타고라스 정리의 일반화를 만족시키고, 정보 기하학에서 해당 통계 다지관은 (다지) 평판 다지관으로 해석된다.이를 통해 최소 제곱의 일반화로서 기하학적으로 Bregman 다이버전스에 최적화 이론의 많은 기법이 일반화될 수 있다.null

브레그만 다이버전스는 1967년 이 개념을 도입한 레프 M. 브레그만의 이름을 따서 명명되었다.null

정의

${\displaystyle F\mathbb{}}$ :${\displaystyle \mathrm{\Omega }}$→ R ${\$$\Oomega \to \mathb {R}$}은(는) 닫힌 볼록 세트 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$에 정의된 연속적으로 구별 가능하고 엄격히 볼록한 함수임$.$

포인트 $p{\displaystyle }$ ,${\displaystyle q}$ ${\displaystyle \in }$ ${\displaystyle \mathrm{\Omega }}$ ${\displaystyle p,q\in \Oomega }$에 대한 F와 관련된 Bregman 거리는 포인트 p에서의 F 값과 포인트 p:에서 평가한 포인트 q 주변의 F의 1차 확장 Taylor의 값 사이의 차이다$$.

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

특성.

• 비부정성: $모든{\displaystyle {}_{}}$ p, q에 대해$$ D ${\displaystyle F_{}p}$ ,${\displaystyle q}$) ${\displaystyle 0}${\$displaystyle D_{F}(p,q)\geq 0}$이것은 F의 대류도의 결과물이다.
• 볼록함: ${\displaystyle {}_{}}$ ${\displaystyle F_{}}$( ${\displaystyle p}$ ,${\displaystyle q}$) ${\displaystyle D_{F}(p,q)}}$은(는) 첫 번째 인수에서는 볼록하지만$$ 두 번째 인수에서는 반드시 볼록하지 않다( 참조).
• 선형성:Bregman 거리를 함수 F의 연산자로 생각하면 음이 아닌 계수에 대해 선형이다.즉${\displaystyle {}_{}}$ $F{\displaystyle {}_{}}$ ${\displaystyle 1_{}}$에 대해서는 ${\displaystyle {F\mathrm{}}_{}}$ 2 ${\$}} 엄격히$$ 볼록하고 구별이 가능하며,${\displaystyle }and{\displaystyle }$ ${\displaystyle \lambda \geq$ 0$\},$

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

• 이중성:F함수는 볼록결합 $∗{\$ F$^{*}}}.$$F{\displaystyle {}^{}}$has ${\$ F$^{*}$에 대해 $정의$된 Bregman 거리는 $D{\displaystyle {}_{}}$ F${\displaystyle {}_{}{p}_{}}$ ,${\displaystyle q}$) ${\displaystyle D_{F}(p,q)$와 흥미로운 관계를$$ 갖는다.

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

여기서 $p{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$= ${\displaystyle \mathrm{\nabla }}$ ${\displaystyle F}$( p${\displaystyle }$) ${\displaystyle$ $^{*}=\nabla F(p)},$ $q{\displaystyle {}^{}}$ =${\displaystyle {}^{}\mathrm{\nabla }}$ F (${\displaystyle q)}$ ${\displaystyle q^{*}=\nabla F(q)}$는 p와 q에 해당하는 이중점이다$$.

• 미니마이저로서의 평균: Bregman 분리에 대한 주요 결과는 랜덤 벡터가 주어진 경우, 평균 벡터는 무작위 벡터로부터 예상되는 Bregman 분산을 최소화하는 것이다.이 결과는 집합의 평균이 집합의 원소에 대한 총 제곱 오차를 최소화하는 교과서 결과를 일반화한다.이 결과는 (Banerjee et al. 2005)에 의해 벡터 케이스에 대해 입증되었고 (Frigyik et al. 2008)에 의해 기능/분산의 케이스로 확장되었다.이 결과는 특히 베이지안 추정에서 랜덤 집합의 대표로서 평균을 사용하는 것을 더욱 정당화하기 때문에 중요하다.

• 코사인 법칙:^[2]

$모든{\displaystyle }$p ,${\displaystyle q}$ , ${\displaystyle z}${\$displaystyle p,q,z}$에 대해

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

• 일반화된 피타고라스 정리:^[3]

Consider the "Bregman projection" of ${\displaystyle q}$ onto a convex set ${\displaystyle \Omega }$: ${\displaystyle P_{\Omega }(q)={\text{argmin}}_{\omega \in \Omega }D_{F}(\omega ,q)}$. The Bregman divergence is an obtuse triangle in the sense

${\displaystyle D_{F}(p,q)\geq D_{F}(p,P_{\Oomega }(q))+D_{F}(P_{\Oomega }(q),q).}$

예

• Squared Euclidean distance ${\displaystyle D_{F}(x,y)=\ x-y\ ^{2}}$ is the canonical example of a Bregman distance, generated by the convex function ${\displaystyle F(x)=\ x\ ^{2}}$
• The squared Mahalanobis distance, ${\displaystyle D_{F}(x,y)={\tfrac {1}{2}}(x-y)^{T}Q(x-y)}$ which is generated by the convex function ${\displaystyle F(x)={\tfrac {1}{2}}x^{$$T}Qx$ 이것은 위 제곱 유클리드 거리의 일반화라고 생각할 수 있다.
• 일반화된 Kullback-Leibler의 차이

${\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)}$

• 이타쿠라-사이토 거리,

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

볼록함수에 의해 생성된다.

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

투영 이중성 일반화

컴퓨터 기하학의 핵심 도구는 투영적 이중성의 개념으로, 발생률과 신뢰도 이상의 관계를 유지하면서 하이퍼플레인과 그 반대의 경우를 가리킨다.There are numerous analytical forms of the projective dual: one common form maps the point ${\displaystyle p=(p_{1},\ldots p_{d})}$ to the hyperplane ${\displaystyle x_{d+1}=\sum _{1}^{d}2p_{i}x_{i}}$.This mapping can be interpreted (identifying the hyperplane with its normal) as the convex conjugate mapping that takes the point p to its dual point ${\displaystyle p^{*}=\nabla F(p)}$, where F defines the d-dimensional paraboloid ${\displaystyle x_{d+1}=\sum x_{i}^{2}}$.

이제 임의 볼록함수로 파라볼로이드를 대체하면 표준 투영 이중의 발생률과 상층 특성을 유지하는 다른 이중 매핑을 얻는다.이는 보로노이 다이어그램과 델라오나이 삼각측량 같은 계산 기하학에서 자연적인 이중 개념들이 임의의 브레그만 분리에 의해 정의된 거리 공간에서 그 의미를 간직하고 있음을 암시한다.따라서 "정상" 기하학의 알고리즘은 이러한 공간에 직접 확장된다(Boissonnat, Nielsen 및 Nock, 2010).

브레그만 다이버전스 일반화

브레그먼 다이버전스는 옌센 다이버전스의 제한된 사례로 해석할 수 있다(닐슨과 볼츠, 2011 참조).젠센 다이버전스는 비교 볼록도를 사용하여 일반화할 수 있으며, 이러한 왜곡된 젠센 다이버전의 제한적인 경우는 일반화된 브레그만 다이버전스를 산출한다(닐슨과 녹, 2017 참조).브레그만 화음 분비는^[4] 접선 대신 화음을 취함으로써 얻는다.null

다른 물체에 대한 Bregman 발산

브레그만 분리는 행렬, 함수 사이, 조치 간(분산)에도 정의될 수 있다.브레그먼이 매트릭스 사이에 분리한 것은 스타인의 상실과 폰 노이만 엔트로피를 포함한다.함수 간 브레그만 분리는 총 제곱 오차, 상대 엔트로피 및 편향 제곱을 포함한다. 정의와 속성은 아래 Frigyik 등.의 참조를 참조한다.마찬가지로 Bregman 다이버전스도 볼록함수의 이산 아날로그로 알려진 하위모듈러 집합함수를 통해 집합에 걸쳐 정의되었다.서브모듈라 Bregman 다이버전스는 해밍 거리, 정밀도 및 리콜, 상호 정보 및 기타 설정 기반 거리 측정과 같은 여러 이산 거리 측정값을 소급한다(Iyer & Bilmes, 2012 참조).null

일반 행렬 Bregman 다이버전스 목록은 표 15.1 in을 참조하십시오.^[5]null

적용들

머신러닝에서 Bregman 다이버전스는 데이터세트가 소음이 많은 소프트맥스 기능보다 더 뛰어난 성능을 발휘하며, 바이성 로지스틱 손실을 계산하는 데 사용된다.^[6]null

참조