Minix lower bound 이광민 My 08 ottion 모수공간 : Θ Action spce : A Loss function : L : Θ A [0, Sple spce : Dt : θ (robbility esure on sple spce Decision rule : D : A Minix isk : inix := inf D sup θ Θ E θ L(θ, D( ottion for syptotic Sple spce : n Dt : (n n θ Decision rule : D (n : n A (robbility esure on sple spce Minix isk : (n inix := inf D sup θ Θ E θ L(θ, D( (n 목표 특정추정량 (D 이 inix 관점에서최적인추정량임을보장하기위해다음을만족해야함. sup E θ L(θ, D ( = inix θ Θ
따라서 inix 값을 계산할 필요가 있음. 그런데, 정확한 inix 를 구하기 힘들기 때문에 inix관점에서 최적인 추정량을 다음과 같이 재정의한다. (n sup Eθ L(θ, D (n ( inix θ Θ 즉 Minix risk가 최적의 수렴속도와 syptotic하게 일치하는 것으로 만족. (n 따라서 inix 를 계산해야 하고, 이를 정확하게 계산하는 것이 아닌 syptotic한 계산만으로 충분하다. 그리고 해당 발표의 주제는 일반적인 setting에서 inix 를 계산하기 위해 사용되는 방법들에 대해 다룬다. 즉 for soe, b > 0 다음 식을 만족하는 n 을 구하면 된다. (n inix n (n inix b n 이를 다시 표현하면, Upper bound에 대해서는 적당한 D (n 를 잡아서, supθ Θ Eθ L(θ, D (n ( 의 upper bound를 계산한다. (이를 un 이라 함. 그리고 lower bound에 대해서는 inf D supθ Θ Eθ L(θ, D( (n 의 lower bound를 계산한다. (이를 b ln 이라 함. 이때 un = ln 이 될때까지 최대한 upper, lower bound를 tight하게 만든다. lower bound를 계산하기 위해서 모든 조합들 다 고려해 봐야하는데, 이는 실질적으로 불가능하 고, 베이즈 위험에 바탕해 둔 lower bound 계산 기술들에 대해 다룬다. 3 베이즈 위험을 이용한 bound Definiton nd nottion Byes risk for prior w : Byes (w := inf D Θ Eθ L(θ, D(w(dθ B(w,L (x : inf A B(w,L (x
(x := B(w,L Θ L(θ, pθ (xw(dθ Since inix Byes (w, w Assuing the condition for interchnging of order of integrtion Z Eθ L(θ, D(w(dθ inix Θ Z Z = L(θ, D(xpθ (xw(dθµ(dx Z Θ Bw,L (xµ(dx inix에 대한 lower bound는 적당한 사전분포를 잘 잡아서 베이즈리스크 구하는 것으로 환원된다. 4 Stndrd Technique 앞장에서 사전분포 w를 잡을 때, 전체 모수공간에 대한 esure를 고려하는 것이 아닌, Finite set F Θ에 대해 사전분포를 부여하는 방식으로 베이즈 isk를 제시한다. 4. ottion d(θ, θ := inf{l(θ, + L(θ, : A} for θ, θ Θ d(θ, Θ := inf{d(θ, θ : θ Θ, θ Θ } for subsets Θ, Θ Θ finite set F Θ는 η-seperted if d(θ, θ η for ll θ, θ F θ 6= θ For esure on,..., on nd weights ρi Z r ρ (,..., := x [ρi pi (x]µ(dx, where pi := di /dµ i 3
(이는 lower bound를 표현하는 단위로서 중요한 역할을함 Hing distnce on hyper cube {0, } Γ(τ, τ 0 = {τi 6= τi0 } i= 4. Multiple Hypothesis Testing Assue Θ = A = {,..., } nd L(θ, = {θ 6= }. Then, inix r ρ (,..., for every prob ρ roof 정의에 의해 Bρ,L (x = { 6= i}pi (xρi = i= pi (xρi p (xρ i= Bρ,L (x = pi (xρi x pj (xρj i= j 이 성립하고 베이즈 리스크에 의한 bound를 그대로 적용하면 됨. 4.3 Generl Testing Bound 앞의 ultiple hypotesis testing은 일반적인 loss function에 적용가능한 것이 아니기에 실 질적으로는 의미 없는 정리이다. 하지만 이를 적용하여 다음 정리를 유도할 수 있다. For every η-seprted finite subset F of Θ we hve η ρθ = inix r ρ (θ, θ F for ll ρθ 0, θ F with θ F roof Since L(θ, (η/{l(θ, η/}, η ρθ pθ (x ρθ pθ (x{l(θ, < η/} θ F θ F η Bw,L (x ρθ pθ (x x[ρθ pθ (x] since F is η seprted θ F θ F Bw,L (x 4
4.4 Assoud s ethod Generl Hypothesis를 이용하였을때의 lower bound는 여전히 일반적인 상황에서 계산하기 용이하지 않다. 좀더 계산용이한 lower bound version하나 제시함. Suppose Θ, A = {0, }, L(θ, = Γ(θ, = i= {θi 6= i } Then, in θ θ0 Γ(θ,θ0 = inix roof Let prior w s unifor then Bw,Γ = i= Bw,Γ (x = in i= {θi 6= i }pθ (x θ {0,} θ:θi =0 pθ (x, θ:θi = pθ (x 따라서 그대로 대입하게되면, inix ( ( θ θ i= θ:θi =0 θ:θi =0 in θ θ0 Γ(θ,θ0 = 마지막 부등식은 다음 이유때문에 성립한다. i /d Qi /d = (i Qi /d T V i Qi /d x i Qi = in i Qi 4.5 Generl Assoud 마찬가지로 Assoud에서 정의한 loss function은 일반적으로 사용되기 힘든 loss이다. Consider ψ : {0, } Θ nd suppose ξ is positive rel nuber such tht d(ψ(τ, ψ(τ 0 ξγ(τ, τ 0 Then, inix ξ 4 in ψ(τ ψ(τ 0 Γ(θ,θ0 = roof Let τ := rginτ L(ψ(τ,, L(ψ(τ, L(ψ(τ, + L(ψ(τ, ξ Γ(τ, τ 5
이 되므로, 다음 이 성립한다. (x Bw,L ξ Γ(τ, τ pψ(τ (x θ {0,} ssoud에서와 같은 방법으로 증명 할수 있음 Finite한 공간에서의 probbility esure간의 거리는 비교적 쉽게 계산할 수있다. 4.6 Le C Θ, Θ 를 Θ의 subset이라 하고, 각각에 대해 prior w, w 라 한다. 그리고 i (x := Θi pθ (xwi (dθ라 할때, inix d(θ, Θ roof Let w = (w + w / Bw,L (x + Bw,L (x (x inf L(θ, + (x inf L(θ, θ Θ θ Θ in( (x, (xd(θ, Θ Bw,L (x = 마지막 부등식은 inf θ Θ L(θ, + inf θ Θ L(θ, inf θi Θi [L(θ, + L(θ, ] inf θi Θi d(θ, θ = d(θ, Θ 이므로 성립. 4.7 Fno inequlity F Θ 의 crdinlity가 이고 η-seprted 일 경우에 다음이 성립한다. log + θ F D (θ η inix log where := θ F θ /. Le 4. non negtive nuber,..., 에 대해 다음 부등식이 성립한다. (log x i i i= where := ( + + / 6 i log i
roof WLOG i =, = x i i then, (log x i i i log i= ( i ā = = 0 i= i= ( ā ( ā i log + log i ( ( i log + log i roof generl testing bound 에의해 5 Bounds vi f-divergences 5. f-divergence 의정의 inix (η/ r( θ, θ F pi / log p i p log log + θ F D ( θ log Definition 5. Let f : (0, convex function with f( = 0, f(0 := li x 0+ f(x, f( := li x f(x/x D f ( Q := Qf(p/q + f ( {q = 0} Exple 5. f(x = x / 인경우 D f ( Q = Q T V power divergence D α ( Q := D fα ( Q x α for α / [0, ] x α for α (0, f α (x = x log x for α = log x for α = 0 α = 인경우, D ( Q = KL( Q α = /인경우, D /( Q = pqdµ (Hellinger distnce 7
Theore 5. f 가 convex on (0, 이고, f ( = 0인 경우 다음 부등식이 성립한다. Df (i Q g(r i= where g( := f ( ( + ( f ( roof 먼저 임의의 non negtive,..., 에 대해 다음 부등식이 성립한다. i= 왜냐하면 x i i i= i f (i f (x i + ( f i i= f (i = f ( +( i (f (i /( f ( +( f pi (x i 이 성립(by Jensen 그리고,..., n << Q인 경우 가정(아닌 경우는 생략, 비슷한 아이디어 pi := di /dq라 할때, 다음 부등식이 성립한다. i= p x p i i i= i f (pi f (x pi + ( f i 이때 각 변을 Q로 적분한다면, Z Z f (pi dq i= Z f (x pi dq + ( i p x p i i i= i f dq 좌변은 정의에 의해 i= Df (i Q가 되고, f (xi pi dq f ( xi pi dq = f ( ( r i= pi xi pi i= pi xi pi r f dq f ( dq = f ( erk 위 정리의 사용 r 은 [0, / ]사이의 값을 갖고 g는 [0, / ]에서 감소하기 때문에 g에 역함수통해 r 의 lower bound를 구할 수 있고, 이에 따라 inix lower bound계산가능 Exple 5. Totl vrition의 경우 f (x = x /이고 g(x = r 이 된다. 따라서 i Q T V r i= 8
Liner pproxition for g g는 convex이고 non-incresing이기때문에 (0, /] 에대해, g( r g( + g L(( r 따라서 D f ( i Q g( + g L(( r i= Df ( i Q g( r + g L ( 9