Ispr Bhattacharyya Bound

Bhattacharyya Bound song

Outline • Bhattacharyya Boundの定義 • Bhattacharyya距離の性質 • 三つの例題についてのBhattacharyya BoundとBayes errorの結果 • 他のbound

Keywords • • • •

Bhattacharyya Bound Bhattacharyya distance Bayes error Asymptotic nearest neighbor error

Bhattacharyya Boundの定義 • 定義式は

ε = P P ∫ p (X)p (X )dX = P P e u

1

2

1

2

1

− µ (1 / 2 )

2

( 3.151 )

そしては µ(1 / 2)Bhattacharyya距離と呼ばれる。二つの 分布はともに正規分布であるとき。この距離は以下 の式のようになる： Σ +Σ | 1 1 Σ + Σ  2 µ(1 / 2) = (M − M )  ( M − M ) + In 8 2 | Σ || Σ |  2  |

− 1

T

2

1

1

1

2

2

2

1

1

2

( 3.152 )

Bhattacharyya Boundの性質 • 正規分布Bhattacharyya距離について – 二つの正規分布の共分散行列は同じの時のChernoff距離(sの関 数とするとき)の最大値である。

1 µ(1 / 2) = (M − M ) 8 2

1

T

Σ 

Σ +Σ | +Σ  1 2 ( M − M ) + In 2  2 | Σ || Σ | |

− 1

1

1

2

2

2

1

1

( 3.152 )

2

– 式3.151において、二つの部分に分けてみると、前の部分はM1=M2 のとき消える、そして後ろの部分は Σ = Σ のとき無くなる。言い換 えれば、前の部分は二つの正規分布のmeanの違いを表す、後ろ の部分は共分散の違いを表している。 1

2

三つの例題 • 例題12 – まずChernoff距離は

s(1 − s) 1 | sΣ + (1 − s)Σ | µ(s) = ( M − M ) [sΣ + (1 − s)Σ ] ( M − M ) + In 2 2 | Σ1 | | Σ 2 | − 1

1

T

2

1

1

2

2

1

2

s

1 − s

( 3.150 )

– DATA I − Λにおいて、Chernoff距離の最大値を計算す るとS0=0.58になる。（P1=P2=0.5）それに対応したChernoff boundは0.046になる。この数値はBhattacharyya bound の0.048に近い。一方Bayes errorは0.019になる。

三つの例題 • 例題13 – Nx(0,I),Nx(0, Λ)についてBhattacharyya距離を計算する。 Σ +Σ | 1 2 µ(1 / 2) = In 2 | Σ || Σ | |

1

2

1

– そして以下になる

2

1 1 + λi µ(1 / 2) = Σ In 2 2 λi n

i = 1

もしnは + ∞ そして λi ≠ 0 の時、距離は無限大のなって、 boundは0に接近。当然Bayes errorも接近。

三つの例題 • 例題14 – Xi(i=1…n)はIID。 一様分布である。

ω,ω 1

クラスは[0.4,0.6]そして[0,1]区間上の

2

ε = P P ∫ p (X)p (X)dX u

1

2

= PP ∫ 1

2

+∞

−∞ n

= PPΠ ∫ 1

2

1

p (X)p (X)dX 1

2

0.6

5dX

i

i = 1 0.4

= P P 0.477 1

2

n

2

– Boundはnにつれて小さくなる。たとえば、n=1,P1=P2=0.5の時 0.224となる、一方Bayes errorは0.1である。

他のbound • たとえばAsymptotic nearest neighbor error • 定義式：

P p (X)P p (X) ε <= 2 ∫ dX <= ∫ P p (X )P p (X )dX p( X) 1

1

2

2

1

1

2

2

( 3.157 )

• Bayes errorとBhattacharyya boundの中間。 • Bayes errorを計算するとき,各クラスで積分して和をとる。一 方Bhattacharyya boundそしてAsymptotic nearest neighbor errorはP1p1(X)とP2p2(X)の積についての関数を積分している。 Asymptotic nearest neighbor errorは7章にまた詳しく説明され る。