勉強を進めていて,確率論における概念である集中不等式(concentration inequality)を知りました.これは確率変数がある値(例えば期待値)からどのくらい確率的に乖離するかを評価する不等式のことです.

本記事では,統計的学習理論あるいは機械学習に応用される Hoeffdings Inequality を最終目標にして,いくつかの集中不等式を証明します.文献[1]をベースにしてまとめます.


はじめに本記事であつかう集中不等式の基礎となる Markovs inequality を証明します.

命題1. (Markovs inequality)
{displaystyle mathbb{R} } 上の(可積分な)非負確率変数 {displaystyle U } とすべての {displaystyle t gt 0 } について以下が成り立つ.
{displaystyle ;;; P(U ge t ) le frac{1}{t} E [ U ] }

証明.
{displaystyle ;;; P(U ge t ) = E [ mathbf{1}_{ { U ge t } } ] le E left[ frac{U}{t} mathbf{1}_{ { U ge t } } 
ight] = frac{1}{t} E [ U mathbf{1}_{ { U ge t } } ] le frac{1}{t} E [ U ] }

ここで2つの不等号には {displaystyle U } が非負であることを用いている.(証明終わり)

 

Markovs Inequality の系として Chebyshevs inequality を得ます.

系1. (Chebyshevs inequality)
{displaystyle mathbb{R} } 上の(二乗可積分な)確率変数 {displaystyle Z } の平均 {displaystyle E [ Z ] = mu }, 分散 {displaystyle E [ ( Z - E [ Z ] )^2 ] = sigma^2 } であるとする.すべての {displaystyle t gt 0 } について以下が成り立つ.
{displaystyle ;;; P( | Z - mu | ge sigma t ) le frac{1}{t^2} }

証明.
確率変数 {displaystyle (Z-mu)^2 } に Markovs Inequality を適用して
{displaystyle ;;; P( | Z - mu | ge sigma t ) = P left( (Z-mu)^2 le sigma^2 t^2 
ight)  le frac{1}{sigma^2 t^2} E [ (Z-mu)^2 ] = frac{1}{sigma^2 t^2} sigma^2 = frac{1}{t^2} }
を得る.(証明終わり)

 

Markovs Inequality の系として Chernoff bound を得ます.これは次の Hoeffdings inequality の証明に使用します.

系2. (Chernoff bound)
{displaystyle mathbb{R} } 上の確率変数 {displaystyle Z } とすべての {displaystyle t gt 0 } について以下が成り立つ.{displaystyle M_Z (s) } はモーメント母関数である.
{displaystyle ;;; P(Z ge t) = inf_{s gt 0 } left( e^{-st} E [ e^{sZ} ] 
ight) }

{displaystyle ;;;;;;;;;;;;;;;;; = inf_{s gt 0 } left( e^{-st} E left[ 1 + sZ + frac{1}{2}s^2 Z^2 + cdots  
ight] 
ight) }

{displaystyle ;;;;;;;;;;;;;;;;; = inf_{s gt 0 } left( e^{-st} sum_{i=1}^infty frac{1}{i!} s^i E [ Z^i ] 
ight)  ;;; ecause }  自明ではないが成り立つ(証明なしで認める)

{displaystyle ;;;;;;;;;;;;;;;;; = inf_{s gt 0 }  e^{-st} M_Z (s) }

証明.
任意の {displaystyle s gt 0 } について, Markovs Inequality を適用して
{displaystyle ;;; P(Z ge t) = P(sZ ge st ) = P( e^{sZ} ge e^{st} ) le e^{-st} E [ e^{sZ} ] = e^{-st} M_Z (s) }
が成り立つ.(証明終わり)

 

 補題1. (Hoeffdings lemma)
{displaystyle V }{displaystyle E [ V ] =0 } を満たす {displaystyle mathbb{R} } 上の確率変数とし,{displaystyle a le V le b } が確率1で成り立つとする( {displaystyle a lt 0 lt b } である).このときすべての {displaystyle s gt 0 } について以下が成り立つ.

{displaystyle ;;; E [ e^{sV} ] le e^{s^2 (b-a)^2 /8 } }


証明.
{displaystyle x in [ a,b ] } のとき関数 {displaystyle x 	o e^{sx} } が凸関数であることと {displaystyle E [ V ] =0 } より以下を得る.

{displaystyle ;;; e^{sx} le frac{x-a}{b-a}e^{sb} + frac{b-x}{b-a}e^{sa} }
{displaystyle ;;; E [ e^{sV} ] le frac{b}{b-a}e^{sa} - frac{a}{b-a}e^{sb} }

{displaystyle p=b/(b-a),  u=(b-a)s } として以下の関数を導入する.

{displaystyle ;;; phi(u)= log (ps^{sa} + (1-p)e^{sb} ) }
{displaystyle ;;;;;;;;;; = log s^{sa} ( p + (1-p)e^{s(b-a)} ) }
{displaystyle ;;;;;;;;;; = sa + log ( p + (1-p)e^{s(b-a)} ) }
{displaystyle ;;;;;;;;;; = sb - u + log ( p + (1-p)e^{u} ) }
{displaystyle ;;;;;;;;;; = sp(b-a) - u + log ( p + (1-p)e^{u} ) }
{displaystyle ;;;;;;;;;; = pu - u + log ( p + (1-p)e^{u} ) }
{displaystyle ;;;;;;;;;; = (p-1)u + log ( p + (1-p)e^{u} ) }

この関数は滑らかであるのでテイラーの定理(文献[4]にあります)より任意の {displaystyle u in mathbb{R} } について以下を満たす {displaystyle xi = xi (u) in mathbb{R} } が存在する.

{displaystyle ;;; phi(u) = phi(0) + phi'(0)u + frac{1}{2}phi'' (xi) u^2 }

すぐにわかるように {displaystyle xi (0) = 0 } である.また

{displaystyle ;;; phi'(u)= (p-1) + frac{ (1-p)e^{u} }{p + (1-p)e^{u}} }
{displaystyle ;;;;;;;;;;; = (p-1) + frac{- p+p+(1-p)e^{u} }{p + (1-p)e^{u}} }
{displaystyle ;;;;;;;;;;; = (p-1) + 1 - frac{p}{p + (1-p)e^{u}} }

から {displaystyle xi' (0) = 0 } である.つぎに {displaystyle phi''(u) } の最大値を求める.

{displaystyle ;;; phi''(u)= frac{p(1-p)e^{u} }{ (p + (1-p)e^{u})^2 } }

{displaystyle ;;; phi''' (u)= frac{p(1-p) e^u ( p+(1-p) e^{u})^2 - p(1-p)e^u 2(p+(1-p)e^u )(1-p) e^u }{ (p + (1-p)e^{u})^4 } }
{displaystyle ;;;;;;;;;;; = frac{p(1-p) e^u }{ (p + (1-p)e^{u})^2 }- frac{ 2 p(1-p)^2 e^{2u} }{ (p + (1-p)e^{u})^3 } }
{displaystyle ;;;;;;;;;;; = frac{ p(1-p)e^u}{ (p + (1-p)e^{u})^3 } left( (p + (1-p)e^{u}) -2(1-p)e^u 
ight) }
{displaystyle ;;;;;;;;;;; = frac{ p(1-p)e^u}{ (p + (1-p)e^{u})^3 } left( p -(1-p)e^u 
ight) }

であり,{displaystyle xi''' (0) = 0 } とすると

{displaystyle ;;; e^u = frac{p}{1-p} ; left( = frac{b/(b-a)}{1 - b/(b-a)} = - frac{b}{a} gt 0 
ight) }

であり,このとき最大値

{displaystyle ;;; phi''(u)= frac{p(1-p) p/(1-p) }{ (p + (1-p) p/(1-p) )^2 } = frac{p^2 }{ ( 2p )^2 } = frac{1}{4} }

をとる(たしかに {displaystyle e^u 	o 0, infty } とするとどちらも {displaystyle phi'' (u) 	o 0 } である).以上をあわせると

{displaystyle ;;; E [ e^{sV} ] le frac{b}{b-a}e^{sa} - frac{a}{b-a}e^{sb} }
{displaystyle ;;;;;;;;;;; = e^{ phi(u) } }
{displaystyle ;;;;;;;;;;; = e^{ phi(0) + phi'(0)u + (1/2)phi'' (xi) u^2 } }
{displaystyle ;;;;;;;;;;; le e^{ (1/2)(1/4) u^2 } }
{displaystyle ;;;;;;;;;;; = e^{ s^2 (b-a)^2 / 8 } }

を得る.(証明終わり)

 

互いに独立な確率変数列の総和に対する不等式として Hoeffdings inequality が成り立ちます.

定理1. (Hoeffdings inequality)
{displaystyle Z_1,ldots,Z_n }{displaystyle mathbb{R} } 上の互いに独立な確率変数とし,確率 {displaystyle 1 }{displaystyle a_i le Z_i le b_i } を満たすとする.{displaystyle S_n = sum_{i=1}^n Z_i } とする.すべての {displaystyle t gt 0 } について以下が成り立つ.

{displaystyle ;;; P(S_n - E [ S_n ] ge t) le e^{-2 t^2 / sum_{i=1}^n (b_i - a_i) } }

{displaystyle ;;; P(S_n - E [ S_n ] le -t) le e^{-2 t^2 / sum_{i=1}^n (b_i - a_i) } }

注意.
2つをあわせて以下を得る.

{displaystyle ;;; P( | S_n - E [ S_n ] | ge t) le 2 e^{-2 t^2 / sum_{i=1}^n (b_i - a_i) } }


証明.
確率変数 {displaystyle S_n - E [ S_n ] } に Chernoff bound と補題1.を適用して以下を得る.

{displaystyle ;;; P( S_n - E [ S_n ] ge t ) = min_{s gt 0}  e^{-st} E [ e^{s (S_n - E [ S_n ]) } ] ;;;;;;;;;; ecause } Chernoff bound
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st} E [ e^{s ( sum_{i=1}^n Z_i - E left[ sum_{i=1}^n Z_i 
ight]) } ] }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st} E [ e^{s ( sum_{i=1}^n Z_i - sum_{i=1}^n E left[ Z_i 
ight]) } ] }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st} E [ e^{ s sum_{i=1}^n ( Z_i - E left[ Z_i 
ight]) } ] }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st} E left[ prod_{i=1}^n e^{ s ( Z_i - E left[ Z_i 
ight]) } 
ight] }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st} prod_{i=1}^n E left[ e^{ s ( Z_i - E left[ Z_i 
ight]) } 
ight] ;;; ecause } {displaystyle Z_i } は互いに独立
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; le min_{s gt 0}  e^{-st} prod_{i=1}^n e^{ s^2 (b_i - a_i)^2 /8 } ;;;;;;;;; ecause } 補題1.
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st} e^{ sum_{i=1}^n s^2 (b_i - a_i)^2 /8 } }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{-st+ s^2 /8 sum_{i=1}^n (b_i - a_i)^2 } }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{ ( sum_{i=1}^n (b_i - a_i)^2 /8 ) s^2 - t s } }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{ left( sum_{i=1}^n (b_i - a_i)^2 /8 
ight) left( s^2 - ( 8/ sum_{i=1}^n (b_i - a_i)^2 )t s 
ight) } }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = min_{s gt 0}  e^{ left( sum_{i=1}^n (b_i - a_i)^2 /8 
ight) left[ left( s - 4 t/ sum_{i=1}^n (b_i - a_i)^2 
ight)^2 - left( 4t / sum_{i=1}^n (b_i - a_i)^2 
ight)^2 
ight] } }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = e^{ left( sum_{i=1}^n (b_i - a_i)^2 /8 
ight) left[ - left( 4t / sum_{i=1}^n (b_i - a_i)^2 
ight)^2 
ight] } ;;;;; ecause t gt 0 }
{displaystyle ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; = e^{ - 2 t^2 / sum_{i=1}^n (b_i - a_i)^2 } }

これは1つ目の不等式である.ここで {displaystyle Z_1 = - Z_1,ldots,Z_n = - Z_n } とおきかえると,{displaystyle -b_i le - Z_i le - a_i,  - a_i - (- b _i) = b_i - a_i } であるので2つ目の不等式を得る.(証明終わり)

 

 以上,いくつかの集中不等式を証明しました.

 

参考文献
[1] University of Michigan  Clayton Scott先生のノート http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf
[2] Massachusetts Institute of Technology  Michel Goemans先生のノート http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf
[3] Cornell University  Karthik Sridharan先生のノート https://www.cs.cornell.edu/~sridharan/concentration.pdf
[4] Wikipedia  Taylors theorem のページ https://en.wikipedia.org/wiki/Taylor%27s_theorem
[5] Wikipedia  Concentration inequality のページ https://en.wikipedia.org/wiki/Concentration_inequality