2020-02-01

伊藤清三のルベーグ積分入門 | 直線上の有界変動関数の全変動がWell-Defineでない問題!

study note

この記事では, 伊藤清三先生のルベーグ積分入門の139ページで, 有界変動関数の全変動を定義がWell Defineにならない問題について解決する.

ルベーグ積分入門(新装版) (数学選書)

作者:清三, 伊藤
発売日: 2017/04/06
メディア: 単行本

直線上の有界変動関数の全変動がWell-Defineでない問題!

伊藤清三先生のルベーグ積分入門の139ページで, 有界変動関数の全変動を定義している.

しかし, この定義では, Well Defineにならない.

それゆえに, 補助定理1が成り立たない(反例が見つかる).

このノートでは, まず, Well-Defineにならないことと, 補助定理１の反例をあげて, その解決策を提示する.

$F(x)$ は, $[a, b]$ で定義された有界な実数値関数とする.

全変動の定義

ルベーグ積分入門では, 以下のように, 有界変動関数の全変動を定義している.

次に $F(x)$ を $[a, b]$ で有界変動で右連続な任意の函数 (絶対連続とはかぎらない) とすると, $F(x)$ はで $[a, b]$ で右連続な二つの単調増加函数, 差として表わされる:
$F(x) = F_1(x) - F_2(x)$
そして,
$V_F(x) = F_1(x) + F_2(x)$
は, $V_F(x)$ の全変動と呼ばれる.

問題点

定義の問題点

上の定義の問題は, 一言で言うと, Well-Defineにならない.

例えば, 有界変動で右連続な任意の函数として, $F(x) \equiv 0$ を取る.

すると, $F_1(x)$ と $F_2(x)$ の選び方として, 無限個ある.

例えば, $F_1(x) = F_2(x) = x$ とか, $F_1(x) = F_2(x) = 2x$ とか.

すると, $F(x)$ の全変動は, 前者は, $2x$ で, 後者は, $4x$ である.

つまり, $F(x)$ を $F_1(x)$ と $F_2(x)$ で表す方法によって, 全変動の値が変わってしまう.

補助定理1が成り立たない問題

また, 定義がうまくいかないので, 定理がうまくいかないだろうと予測はつく.

一応, 補助定理１の反例をあげる.

まず, 補助定理1は, 以下のような定理である.

補助定理1 | 次の三つの条件は同等である：

$F_1(x)$ が絶対連続である.

$F_1(x)$ , $F_2(x)$ がともに絶対連続である.

$V_F(x)$ が絶対連続である.

同じように $F(x) \equiv 0$ とすると, $F_1(x) = F_2(x)$ である限り, あらゆる右連続な単調増加な関数が

$F(x) = F_1(x) - F_2(x)$

を満たす.

$F_1(x)$ , $F_2(x)$ として, 不連続な関数を, 取ってきても上の式が成り立つ.

不連続ならば, 絶対連続でないから, 定理に矛盾.

解決方法

定義を変える

伊藤先生も, , $F_1(x)$ , $F_2(x)$ を自由に選んで, 定義しているわけではなさそう.

だから, 選び方を”うまく”一つに固定すればよい.

固定の仕方として,

杉浦光夫先生の解析入門Ⅰの351ページで, 有界変動関数が, ２つの単調増加な関数の差で表せるという証明において, 単調増加な関数を実際に構成していたので, それを採用する.

解析入門 Ⅰ(基礎数学2)

作者:杉浦光夫
発売日: 1980/03/31
メディア: 単行本

２つの単調増加な関数は, 以下のように構成されていた.

$V(a, x, F) = \sup \sum_{j=1}^{N}\big|F(x_j) - F(x_{j-1})\big| \quad (a, x]\text{のあらゆる分割で}\sup\text{をとったもの}.$

とおくと,

$F_1(x) = V(a, x, F) \\ F_2(x) = F(x) - F_1(x)$

とすると, どちらも単調増加な関数になる.

なぜならば, $F_1(x)$ は, $x$ が増加すると, 区間 $(a, x]$ が大きくなる.

よって, 足し合わせる領域が大きくなるので, $F_1(x)$ が増加する.

$F_2(x)$ は, $y > x$ として,

$F_2(y) - F_2(x) = V(a, y, F) - V(a, x, F) - F(y) + F(x) \\ F_2(y) - F_2(x) = V(x, y, F) - (F(y) - F(x)) \geq 0$

最後の不等式は, $V(x, y, F)$ は, 区間 $(x, y]$ のあらゆる分割の $\sup$ なので, $V(x, y, F) \geq (F(y) -F(x))$ .

この $F_1(x)$ と $F_2(x)$ を定義に採用すれば, 補助定理1も容易に証明できる.

以後, これを踏まえてルベーグ積分入門の残りの章を読むことにする.

2019-07-04

Probabilistic State Translation in Extensive Games with Large Actions Sets

論文メモ game theory

不完全情報ゲームの代表例と言えるポーカーで初めてプロに勝った人工知能 Libratus*1の論文を理解するために, 最近, 大規模な展開形ゲームのナッシュ均衡を求めるための手法に関する論文を読んでいます. それの一環として, タイトルにもあるProbabilistic State Translation in Extensive Games with Large Actions Setsを読んだのでそれをまとめます.

この論文を選んだ理由としては, 定式化が非常にしっかりしていたからです. Libratusの論文Safe and Nested Subgame Solving for Imperfect-Information Gamesも数学的に書かれているので, それを読み解くには, 記号に慣れる必要があり, 良い訓練になると考えました.

この記事は, 論文の流れに添いつつも, 自分の考えや調べたことなどが含まれています.

Introduction

複数のエージェントが存在する複雑な問題の多くは, ゲーム理論の展開形ゲームと呼ばれる木の構造を持つ形式で定式化することができます. しかし, 木のサイズが大きくなると, 実際にナッシュ均衡と呼ばれるゲームにおける解を計算することが, 事実上不可能になります. そこで, 抽象化(abstraction)と呼ばれる方法を使います. 本来解きたいゲーム(real game)を抽象化(具体的には, 取りうる行動を減らすなど)して, 木のサイズを計算できるレベルまで小さくする. そして, 抽象化したゲーム(abstraction game)を解くことで, real gameの解の近似解を得る方法です.

この方法には, ２つの問題があります. １つ目は, 抽象化によってreal gameに持っていた情報を失うことです. 抽象化によって, abstration gameのナッシュ均衡は, real gameのナッシュ均衡と大きく乖離してしまう場合があります.

２つ目は, 抽象化によって取りうる行動や起きうる状態が減ることです. 抽象化したからといって, real gameにおいて, その行動や状態が起こらないとは限りません. もし仮に, abstradtion gameでは起きない行動や状態が起きた場合, abstraction gameのナッシュ均衡の戦略は使うことができなくなってしまいます. そのため, real gameの状態からabstraction gameの状態を変換するマッピングが必要になります.

この論文では, real gameにおける状態とabstract gameにおける状態のマッピングであるstate translationを数学的にきちんと定式化します. またより柔軟にエージェントを作り出すため, 抽象化とtranslationを分けて考えることができることを示します. また既存のtranslationの方法もきちんと定式化しています. 新しい提案手法と比較実験を行い, 抽象化の特性を利用してプレイしてくるエージェントに対して, exploitability*2が減ることを示しました.

この記事では, 実際にポーカーに適用した部分や実験結果は紹介していません. 基本的に定式化の部分のみの紹介になります.

Background

Extensive Game

展開形ゲーム(Extensive Game)は, プレイヤー(player)とチャンス(chance)*3が取り得る行動の組み合わせによって構築されます. 例えば, 将棋であればプレイヤーの行動は, どの駒を動かすかなどです. チャンスとは, プレイヤーとは独立した存在で, プレイヤーに及ばない部分の行動を表現する際に使われます. 将棋であれば先行後攻を決めるのは, プレイヤーではなく振り駒によって確率的に決まります. この先行後攻を決める部分も行動とみなすためにチャンスと呼ばれる特別なプレイヤーを導入します.

将棋や囲碁のように全ての行動がどのプレイヤーにも観察可能なゲームもあれば, ポーカーのように相手のカードが見えないといったある行動が観測可能でないゲームも存在します. そのようなすべての行動が観測可能とは限らないゲームのことを不完全情報ゲーム(imperfect information game)と呼びます. どの行動が観察できないのかを定式化するには, 情報分割(information partition)といった概念を考える必要があります. 情報分割は履歴(history)*4の集合をプレイヤーにとっては判別できない履歴は同じ集合に属するように分割した集合の集合です.

まずこういった概念を数式で定式化するために, まず展開形ゲームを定義します.

不完全情報ゲームの有限展開形ゲーム不完全情報ゲームにおける有限な展開形ゲームは $\Gamma = (N, H, A, P, f_c, \{\mathbf{I}_i\}_i, \{u_i\}_i, \{\sigma_i\}_i)$ で表される.

$\Gamma$ の要素を１つ１つ見ていきます.

$N$ : プレイヤーの有限集合. ５人のポーカーなら $N = \{1,2,3,4,5\}$ . またチャンス $c$ を含めて, 全プレイヤーを $N \cup \{c\}$ と表す.
$H$ : 履歴(history)の集合. 末端の履歴*5のことを, $Z$ で表す.
$A(h) = \{a: (h,a) \in H \}$ : 末端でない履歴 $h \in H/Z$ において取り得る行動の集合
$P: H/Z \rightarrow N \cup \{c\}$ : プレイヤー関数(player function). その履歴において, 次行動をとるプレイヤーを出力する関数
$f_c$ : チャンスの行動の確率分布
$\mathbf{I}_i$ : プレイヤー $i \in N$ の情報分割. $P(h) = i$ となる履歴, つまり, プレイヤー $i$ が次に行動する履歴の集合を $H_i$ とおけば, 情報分割は, $H_i$ の分割になる. 情報分割の要素を情報集合(information set)と呼ぶ. 同じ情報集合にいる履歴は, そのプレイヤーからはどっちの履歴なのか判断がつかないことを表す. 区別がつかないので, 取り得る行動は同じでなければならないので

\begin{align} A(h) = A(h') \quad \forall h, h' \in I_i \in \mathbf{I}_i \end{align}

が必要になる.

$u_i$ : プレイヤー $i$ の効用関数. 末端の履歴から実数(効用)を返す.
$\sigma_i$ :プレイヤー $i$ の戦略.

数式でドバッとゲームを表現されるとわかりづらいと思うので, 以下の図のようなゲームを使って具体的に, 上の要素を書き下してみます.

まずプレイヤーの集合を考えると, 図からプレイヤーは二人なので, $N=\{1, 2\}$ となります. そして, 次に履歴の集合です. まず最初の何も行動が起きていない状態は, 空集合で表します. なので, $\phi$ は履歴の集合の要素です. 次に, プレイヤー１が最初に行動をします. 可能な行動は, $L, R, U, D$ なので, それらも履歴の集合になります. 次に, もしプレイヤー１が $L, R$ をとった場合, プレイヤー２は, $a, b$ のどちらかの行動を取ることができます. またプレイヤー１が $U$ を取った時, プレイヤー２は $\alpha, \beta, \gamma$ のどれかの行動をとることができます. またプレイヤー１が $D$ を取った時, プレイヤー２は $r, l$ のどれかの行動をとることができます. したがって, 履歴の集合 $H$ は,

\begin{align} H = \{L, C, R, O, (L, a), (L, b), (R,a), (R,b), (U, \alpha), (U, \beta), (U, \gamma), (D, l), (D, r)\}. \end{align}

次に $A(h)$ について考えてみると, ゲームの最初はプレイヤー１が $L, R, U, D$ のどれかを取るので, $A(\phi) = \{L, R, U, D\}$ となります.

次に, プレイヤー１が $L, R$ をとった場合は, プレイヤー２の手番で, $a, b$ のどちらかの行動をとることができるので, $A(L) = A(C) = A(R) = A(O) = \{a,b\}$ となる. もし, プレイヤー１が $U$ をとった場合, プレイヤー２の手番で, $\alpha, \beta, \gamma$ のどれかの行動をとることができるので, $A(U) = \{\alpha, \beta, \gamma\}$ となります. 同じように, プレイヤー１が $D$ を取った場合, プレイヤー２の手番で, $r, l$ のどれかの行動をとることができるので, $A(D) = \{l, r\}$ となります.

$P(h)$ について考えてみると, ゲームの最初は, プレイヤー１が行動するので, $P(\phi) = 1$ . そのあとはプレイヤー１がどの行動を取ろうとも, プレイヤー２が行動するので, $P(L) = P(R) = P(U) = P(D) = 2$ . そのあとは, 末端に行くので, $P(h)$ は考えない.

$f_c$ は, 今回はチャンスを考えていないので無視する.

抽象化を考える上で一番重要になる情報分割について考えてみます. 上の図をみると, 青い丸で囲まれたところは, 情報集合を表していて, プレイヤー２は青い丸のどのノード*6にいるかわからない状態を表しています. まずプレイヤー２が次に行動する履歴の集合 $H_2$ は, $H_2 = \{L, R, U, D\}$ である. 青い丸の履歴の部分は, プレイヤー２にとって区別できないので, プレイヤー２の情報分割は, $\mathbf{I}_2 = \{\{L, R\}, \{U\}, \{D\}\}$ となる. プレイヤー１の情報分割は, トリビアルな例なので, 省略します(全ての情報集合の要素が１).

効用関数と戦略の部分も基礎的なものなので, 具体例は省略.

これで展開形ゲームの基礎的な内容は終わりで, 次に本題である抽象化についてです.

Game Abstraction

抽象化には以下の２つのテクニックがあります.

チャンスの行動をいくつかのバケットにするテクニック

例えば, ポーカーであればチャンスは最初のカードの手にあたります. テキサスホールデムというポーカーのゲームでは, 最初２枚のカードが配られます. 通常であれば, $52 \times 51$ の組み合わせがありますが, これでは大きすぎます. 手の強さを計算して, ある程度同じ強さのものはひとまとめにして同じ手とみなすような抽象化はこれにあたります.

プレイヤーがとることのできる行動を制限するテクニック

ポーカーであれば, 掛け金の上限を設定するといった抽象化はこのテクニックにあたります.

こういった抽象化を数学的に定義します.

Abstraction プレイヤー $i \in N$ の抽象化とは, $\alpha_i = \langle \alpha_i^{\mathbf{I}}, \alpha_i^{A}\rangle$ である. ここで,
$\alpha_i^{\mathbf{I}}$ は $H_i$ の抽象化したゲームの情報分割で, 元のゲームの情報集合よりcoarse*7である.
$\alpha_i^{A}$ は, 抽象化行動集合(abstract action set)と呼び, 履歴から行動を返す関数で, $\alpha_i^{A}(h) \subset A(h)$ であり, 抽象化したゲームの同じ情報集合に属する履歴 $h, h'$ に対して, $\alpha_i^{A}(h) = \alpha_i^{A}(h')$ を満たす.

プレイヤー全体の抽象化を, $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_n)$ で表します. この $\alpha$ を使ったabstract gameを $\Gamma^{\alpha}$ で表します.

実際に抽象化の影響については[Waugh et al., 2009]が研究していて, 抽象化の度合いとabstract gameのナッシュ均衡とreal gameのナッシュ均衡の乖離は関係がないことを証明しています. 直感的には, 抽象度が上がれば, 情報は失われていくので, abstract gameのナッシュ均衡はreal gameのナッシュ均衡から乖離すると思われるが, 実際はそうでないということです.

さて, 理解を深めるためにこの定義を使って, ゲームの抽象化をしてみます.

再び, 先ほどの図を用いて考えてみましょう.

上の図は, プレイヤー１の行動 $D$ は $U$ とみなすという抽象化をしているということを表しています.

これを上で定義した抽象化 $\alpha$ で表してみます.

まずプレイヤー１の抽象化について. プレイヤー１の情報分割は, 変わらないのでそのまま $\alpha_1^{\mathbf{I}} = \mathbf{I}_1$ .

次に, 抽象行動集合は, $\alpha_1^{A}(\phi) = \{L, R, U\}$ となります. $D$ という行動は抽象化されたからです.

次にプレイヤー２の抽象化を考えます.

プレイヤー２の抽象したゲームの情報分割は, $\alpha_2^{\mathbf{I}} = \{\{L, R\}, \{ U, D\}\}$ . 抽象化する前は, $\{U\}$ と $\{D\}$ が別れていたが, 抽象化によって $U$ は $D$ とみなしたので, 区別がつかなくなったことを表しています.

次に抽象行動集合は, $\alpha_2^{A}(L) = \alpha_2^{A}(R) = \{a, b\}$ となります. 次に, $D$ は抽象化されて, $U$ とみなすので, $\alpha_2^{A}(U) = \alpha_2^{A}(D) = \{\alpha, \beta, \gamma \}$ となります.

ある程度, 抽象化のイメージがついたところで, 抽象化の問題を解決するためのtranslationについて話を進めます. 実際の論文では, 抽象化について別の定義(Loose abstraction)を用いています. 具体的な情報分割を明示しなくても抽象化できるような工夫がされています. 詳しくは本論文を読んでみるといいと思います.

Translation Method

Introductionでも述べたように, abstract gameの解を使うためには, real gameの行動や状態をabstract gameに変換するマッピングが必要になります. それが, translationと呼ばれるものです. translationの方法は色々ありますが, real gameにおける行動をabstract gameにおいて有効な行動に逐一変換する方法が簡単です.

Hard translation

この論文が出る前の既存のtranslationの手法は, [Gilpin et al., 2008]が提案したもので, hard translationと呼びます. これはreal gameの履歴をabstract gameの履歴に変換するものです. 数式で定式化すると, 以下のようになります.

hard translation function hard translation $T(h)$ とは, real gameの履歴からabstract gameの履歴の関数である. つまり, $T: H \rightarrow H'$ である.

これは履歴に対する関数なので, 行動を変換する関数は別で定義する必要がある. これをhard translation in-step functionと呼ぶ.

hard translation in-step function hard translation in-step functionとは, $h \in H$ , $a \in A(h)$ に対して, $t_{in}(h, a) \in A'(T(h))$ となる関数である.

$'$ がついているのは, abstract gameを表します. 言葉で説明すると, hard translation in-step functionとは, real gameの履歴 $h \in H$ とその時の行動 $a \in A(h)$ から, abstract gameで有効な行動に変換する関数です. real gameの行動を即時にabstract gameの行動に変換する関数です.

逆に, abstract gameからreal gameに変換するtranslationも定義できて, それをhard translation out-step functionと呼ぶ.

hard translation out-step function hard translation out-step functionとは, $h \in H$ , $a' \in A'(T(h))$ から $t_{in}(h, a') \in A(h)$ となる関数である

言葉で説明すると, abstract gameの行動をreal gameの行動に変換してくれる関数です. out-step functionは, abstract gameの解に従っている場合でも, real gameの行動をしたいときに使うことができます.

さて, 数学的にtranslationを定義しましたが, translationを具体的に定義することでabstract gameが構築されます. 実際に上で見た例がその実例となります( $D$ を $U$ とみなすことを $T(D) = U$ とかける).

実際に適当に抽象化するだけではreal gameに近いabstract gameを作ることができません. ここで, $T$ を実際に作る方法を考えます. まずtranslation in-step functionを用いて $T$ を再帰的に書けることを利用します.

\begin{align} T( (h,a) ) = (T(h), t_{in}(h, a)) \end{align}

これは, 履歴 $(h, a)$ をabstract gameに変換した履歴は, 一個前の履歴 $h$ をabstract gameの履歴に変換したものとreal gameでの行動 $a$ をabstract gameの行動に変換したものを付け加えたものということです. これは直感的に正しそうです. これを用いれば, $t_in$ が既知ならば, $T$ は決まります.

そうすると, 続く問題は $t_in$ の決め方になります. このin-step functionを決めるために行動の類似度を測るための概念を導入します. これをsimilarity metricsと呼ぶ.

$S(h, a, a')$ と書いて, 履歴 $h$ の時点でのreal gameの行動 $a$ とabstract gameの行動 $a'$ の類似度を表します. これを使って, hard translation in-step functionを定義します. 単純に一番real gameの行動に近いabstract gameの行動に変換するだけです. 数式で表すと, 以下のようになります.

\begin{align} t_{in}(h, a) = \operatorname{\rm arg~max} S(h, a, a') \end{align}

out-step functionの役割もありますが, この記事では省略します.

この論文では新しいtranslationの方法を提案していますが, hard translationには何が問題になるのでしょうか. それは, 相手が抽象化していることを知られていて, なおかつ, どうやって抽象化しているのか知られている時, それを利用されてしまう可能性が高くなることです. ポーカーでいえば, ベット額を$1から$10は$1とみなすような抽象化をした時, 相手は自分の手札が強い時は$10ベットして, 弱い時は, $1ベットすれば, どちらも$1と見なされるので, 自分の情報はバレずに勝った時の利得を上げて, 負けた時のリスクを下げることができてしまう. よって, 抽象化のやり方がバレないようにする必要があるのですが, hard translationだと抽象化は決定的なので, 何回かゲームをすることで, 抽象化の仕方を推定される可能性がある. そこで, この論文では, translationを確率的にしたsoft translationというものを提案しました.

Soft translation

いきなりですが, soft translationを数学的に定義します.

soft translation function soft translation function $T^p(h)$ とは, $T^p(h) \subset \mathbb{R} \times H'$ となる関数である.

soft translation functionは, １つの履歴を出力するのではなく, 履歴に実数の値がついたペアとなる要素の集合を返すことです. この実数はその行動のとる確率と結びついています*8. よって, hard translation functionと違って, soft translationはどの履歴にtranslateされるかは確率的に変動するような仕組みを提供してくれます.

同じようにin-step functionも定義しましょう.

soft translation in-step function soft translation in-step functionとは, $h \in H$ , $a \in A(h)$ に対して, $t_{in}(h, a) \in \mathbb{R} \times A'(T(h))$ となる関数である.

これによって, 行動の変換が確率的になるので, 先ほど指摘した抽象化の方法がばれるという問題は緩和します.

ただこのやり方だとhard translationと違って, translationの結果が履歴と実数のペアの集合であるため, real gameを毎回, translationすると, その履歴の数は指数関数的に増加してしまう. そのため, translationするごとに集合をそのまま保持するのではなく, その集合から一つの履歴をサンプリングすることで指数的な増加を抑える.

実際の論文では, このsoft translationとhard translationを使ったエージェントを様々な敵と戦わせた結果を解析していますのでそちらを知りたい方はぜひ論文を読んでみてください.

最後になりますが, もし間違いなどあればぜひコメントくれると嬉しいです.

reference

Extensive-form game - Wikipedia

Schnizlein, David & H. Bowling, Michael & Szafron, Duane. "Probabilistic State Translation in Extensive Games with Large Action Sets." IJCAI (2009)

Waugh, Kevin, David Schnizlein, Michael H. Bowling and Duane Szafron. “Abstraction pathologies in extensive games.” AAMAS (2009).

Gilpin, Andrew, Tuomas Sandholm and Troels Bjerre Lund. “A heads-up no-limit Texas Hold'em poker player: discretized betting models and automatically generated equilibrium-finding programs.” AAMAS (2008).

*1:不完全情報ゲームのポーカーで人間を倒したAI「Libratus」が採っていた戦略が論文で公開される

*2:ゼロサムゲームにおいて, 相手にどれだけ利得が取られるかの指標. 小さければ小さいほど良い

*3:経済学のゲーム理論では, 自然(Nature)と表現することが多いと思う

*4:どういう行動を取ったかの履歴

*5:そこでゲームが終わるところ

*6:履歴によって決まる地点

*7:分割 $A$ が分割 $B$ よりcoarseであるとは, $B$ に属する任意の集合が $A$ に属する集合の部分集合になっているということ.

*8:関数の出力の実数部分だけの和をとったら１になるような要請はされていないのでこのような表現をしました.

2019-06-06

ヘフディングの不等式(Hoeffding's inequality)と諸々の確率の評価の不等式

今回はバンディットアルゴリズムや統計的学習理論で, 確率の評価で用いられる不等式について解説します.

最後に, 学習理論で最も重要な不等式の一つであるヘフディングの不等式まで証明します.

証明の中で, 確率論, 学習理論で用いられるテクニックがたくさんつまっているので, 証明も追うとよいと思います.

この解説記事は, スタンフォード大学のコンピューターサイエンスの授業の一つであるCS229:Machine learningのレクチャーノートを参考にしています.

確率のバウンドの基本
- マルコフの不等式(Markov's inequality)
- チェビシェフの不等式(Chebyshev’s inequality)
モーメント母関数(Moment generating functions)
- チェルノフ上界(Chernoff bounds)
  - チェルノフ上界の具体例
ヘフディングの補題とヘフディングの不等式(Hoeffding’s lemma and Hoeffding’s inequality)
参考文献

確率のバウンドの基本

確率論, 統計学, 機械学習などで基本的な疑問は以下のような問題です.

期待値 $\mathbb{E}[Z]$ の確率変数 $Z$ が与えられたとき, $Z$ はその期待値 $\mathbb{E}[Z]$ 近くの値になる確率はどの程度か.

この問いに答えるために, この記事では以下のような確率の上限を計算するいくつかの道具を紹介する.

$\mathbb{P}(Z \geq \mathbb{E}[Z] + t)$

$\mathbb{P}(Z \leq \mathbb{E}[Z] - t)$

ただし, $t$ は正の実数.

マルコフの不等式(Markov's inequality)

最初に紹介する不等式は, マルコフの不等式です

証明は簡単であるが, 全ての基本となる不等式なので, きちんと覚えておきたい.

$Z \geq 0$ を確率変数とする. 任意の $t \geq 0$ に対して

マルコフの不等式 $\mathbb{P}(Z \geq t) \leq \frac{\mathbb{E}[Z]}{t}$

証明 $\mathbb{P}(Z \geq t) = \mathbb{E}[\textbf{1}\{Z \geq t\}]$ であることに注意する.

$Z \geq t$ のとき, $t \gt 0$ より $t$ で割ると $\frac{Z}{t} \geq 1 = \textbf{1}\{Z \geq t\}$ .

一方で, $Z \leq t$ のとき, $\textbf{1}{Z \geq t} = 0$ であるから, $\frac{Z}{t} \geq 0 = \textbf{1}\{Z \geq t\}$ .

以上より, $Z$ と $t$ と大小関係に寄らず,

$\frac{Z}{t} \geq \textbf{1}\{Z \geq t\}$ .

両辺で期待値を取ればマルコフの不等式が成り立つことがわかる.

チェビシェフの不等式(Chebyshev’s inequality)

次にマルコフの不等式の発展系を紹介する.

この不等式は, 期待値で抑えるのではなく, 分散で抑えるものです.

$Z$ は任意の確率変数とする(正である必要はない). また, $\mathrm{Var}(Z) \lt \infty$ とします

任意の実数 $t \gt 0$ に対して

チェビシェフの不等式 $\mathbb{P}(Z \geq \mathbb{E}[Z] + t \text{ or } Z \leq \mathbb{E}[Z] - t) \leq \frac{\mathrm{Var}(Z)}{t^2}$

証明:

以下が同値であることを利用する.

$Z \geq \mathbb{E}[Z] + t$ または $Z \leq \mathbb{E}[Z] - t$ $\Leftrightarrow$ $(Z - \mathbb{E}[Z] )^{2} \geq t^{2}$ .

すると,

$\mathbb{P}(Z \geq \mathbb{E}[Z] + t \text{ or } Z \leq \mathbb{E}[Z] - t) = \mathbb{P}\big( (Z - \mathbb{E}[Z])^{2} \geq t^{2}\big)$

マルコフの不等式において, $Z$ を, $(Z - \mathbb{E}[Z])^{2}$ , $t$ を $t^{2}$ とみなして, 適用すると

$\mathbb{P}\big( (Z - \mathbb{E}[Z])^{2} \geq t^{2}\big) \leq \frac{\mathbb{E}[(Z - \mathbb{E}[Z])^{2}]}{t^{2}} = \frac{\mathrm{Var}(Z)}{t^2}$

マルコフの不等式を使うことですぐにチェビシェフの不等式が示せました.

初めてチェビシェフの不等式を証明したときはもっと苦労した覚えがあったので, この証明法は鮮やかだったです.

よく見るチェビシェフの不等式と違う方もいるかもしれないです.

Wikipediaのチェビシェフの不等式では,

$\mathbb{P}(|Z - \mathbb{E}[Z]| \geq k\sigma ) \leq \frac{1}{k^{2}}$

ただし, $\sigma$ は, $Z$ の分散の平方根をとったもの.

これは同じもので, $t$ を $k\sigma$ とおけばよい.

チェビシェフの不等式の応用の一つとして, 標本平均の分散が有限であれば, 真の平均に近くことが証明できます.

ここでは証明は省略するが, 元のレクチャーノートでは証明もされているので, 気になる方はチェックしてみてください.

モーメント母関数(Moment generating functions)

確率変数の実現値が期待値からズレる確率をもっと厳しい不等式で評価したい場合, 分散が有限である条件より強い条件が必要になります.

そのひとつがモーメント母関数です*1.

あとで紹介するヘフディングの不等式にexponentialが出るのが不思議だったが, モーメント母関数がそれに一役買っていたことがわかってなるほどなとなりました.

任意の確率変数 $Z$ のモーメント母関数 $M_{Z}(\lambda)$ は,

$M_{Z}(\lambda) = \mathbb{E}(e^{\lambda Z})$

次にこのモーメント母関数を用いた確率の評価の不等式を紹介します.

チェルノフ上界(Chernoff bounds)

任意の確率変数 $Z$ と任意の正の実数 $t \geq 0$ に対して,

チェルノフ上界 $\mathbb{P}(Z \geq \mathbb{E}[Z] + t) \leq \min_{\lambda \geq 0} M_{Z - \mathbb{E}[Z]}(\lambda)e^{-\lambda t} \\ \mathbb{P}(Z \leq \mathbb{E}[Z] - t) \leq \min_{\lambda \geq 0} M_{\mathbb{E}[Z] - Z}(\lambda)e^{-\lambda t}.$

この証明もマルコフの不等式を使えば一瞬で解ける.

証明は１つ目の不等式だけ与えます.

後半も全く同じように証明できます*2

証明: 任意の $\lambda \geq 0$ を一つ取る.

このとき,

$Z \geq \mathbb{E}[Z] + t \Leftrightarrow e^{\lambda Z} \geq e^{\lambda \mathbb{E}[Z] + \lambda t}$

が成り立つ.

これは正の実数 $\lambda$ をかけても不等式の向きは変わらず, また $e$ は増加関数であるからである.

最後に両辺を $e^{\lambda \mathbb{E}[Z]} \geq 0$ で割る操作をすると,

$Z \geq \mathbb{E}[Z] + t \Leftrightarrow e^{\lambda Z - \lambda \mathbb{E}[Z]} \geq e^{\lambda t}$

よって,

$\mathbb{P}\big(Z \geq \mathbb{E}[Z] + t \big) = \mathbb{P}\big(e^{\lambda Z - \lambda \mathbb{E}[Z]} \geq e^{\lambda t} \big) \leq \mathbb{E}[ e^{\lambda(Z -\mathbb{E}[Z]}])e^{-\lambda t}$

最後の不等号はマルコフの不等式を適用した.

$\lambda$ は任意だったので, 右辺が最小になる $\lambda$ に対しても成り立つので, チェルノフ上界は示された.　

チェルノフ上界は, $\lambda$ で最小化させる前の段階を指す場合もあります.

その場合もチェルノフ上界と呼ぶことにします.

チェルノフ上界の嬉しいのは, 和の操作について"きれいに振る舞ってくれる"点です.

これはモーメント母関数がもたらす作用である.

きれいに振る舞ってくれるのいみは以下の例でわかると思います.

例えば, 確率変数の列 $\{Z\}_{i=1}^n$ があり, 各々が独立であるとします.

このとき, 確率変数の和 $\sum_{i=1}^n Z_i$ のモーメント母関数は各々のモーメント母関数の積となります.

つまり

$M_{Z_1 + Z_2 + \cdots + Z_n}(\lambda) = \Pi_{i=1}^n M_{Z_i}(\lambda)$

$Z_i$ がi.i.d.*3だとして, また平均が0*4の場合, チェルノフ上界から

$\mathbb{P}(\sum_{i=1}^nZ_i \geq t) \leq \frac{\Pi_{i=1}^n M_{Z_i}(\lambda)}{e^{\lambda t}} = \frac{(M_{Z_1}(\lambda))^{n}}{e^{\lambda t}}$

となります.

よって一つのモーメント母関数さえ計算すれば上界が得られます.

チェルノフ上界の具体例

次は, チェルノフ上界を使って示される面白い評価式を見てみる

ラーデマッハー*5確率変数を用いた例です.

ラーデマッハー変数とは仰々しいですが, 要は確率1/2で1で, 確率1/2で-1を取る変数のことです.

まずラーデマッハー変数 $S$ のモーメント母関数を抑える式を証明します.

それが次式です.

$\mathbb{E}[e^{\lambda S}] \leq e^{\frac{\lambda^{2}}{2}}$

これの証明は少々厄介で, 指数関数のテイラー展開を用いて証明します.

証明: 指数関数のテイラー展開は, $e^{x} = \sum_{k=0}^{\infty} \frac{x^{k}}{k!}$ である.

これを用いると, ラーデマッハー変数 $S$ のモーメント母関数は,

$\mathbb{E}[e^{\lambda S}] = \mathbb{E}\Big[\sum_{k=0}^{\infty} \frac{(\lambda S)^{k}}{k!} \Big]$

期待値は積分なので, 無限級数の和が入れ替えられるかなど気になる方もいらっしゃると思いますが, 詳細な議論は目をつぶります.

そして, $k$ が奇数の場合, $\mathbb{E}[S^{k}] = 0$ で, $k$ が偶数の場合, $\mathbb{E}[S^{k}] = 1$ となることを利用すると

$\mathbb{E}\Big[\sum_{k=0}^{\infty} \frac{(\lambda S)^{k}}{k!} \Big] = \sum_{k=0, 2, 4, \dots} \frac{\lambda^{k}}{k!} = \sum_{k=0}^{\infty} \frac{\lambda^{2k}}{(2k)!}$

また $(2k)! \geq 2^{k} \cdot k!$ であるから,

$\sum_{k=0}^{\infty} \frac{\lambda^{2k}}{(2k)!} \leq \sum_{k=0}^{\infty} (\frac{\lambda^{2}}{2})^{k} \frac{1}{k!} = e^{\frac{\lambda^{2}}{2}}$

よって, ラーデマッハー確率変数のモーメント母関数は $e^{\frac{\lambda^{2}}{2}}$ で抑えられることがわかった.

次にラーデマッハー確率変数 $S_i$ の和を考えます. $S_i$ は, i.i.d.とします

$Z = \sum_{i=1}^{n} S_i$ とおきます.

すると, $\mathbb{E}[S_i] = 0$ であるから, もちろん $\mathbb{E}[Z] = 0$ である.

よって, チェルノフ上界と先ほど証明したラーデマッハー確率変数のモーメント母関数を抑える不等式より

$\mathbb{P}(Z \geq t) \leq \mathbb{E}[e^{\lambda Z} ] e^{-\lambda t} = \mathbb{E}[e^{\lambda S_1}]^{n}e^{-\lambda t} \leq e^{\frac{n\lambda^ {2} - \lambda t}{2}}$

ここで, チェルノフ上界は $\lambda$ を最小になる部分は具体的に書けなかったが, 今回は $e$ の指数部分が下に凸な二次関数なので, 具体的に書くことができて,

$\lambda^{*} = \frac{t}{n}$

のとき, 最小になる.

したがって,

$\mathbb{P}(Z \geq t) \leq e^{- \frac{t^2}{2n}}$

右辺の式が, きれいになるように $t = \sqrt{2n \log \frac{1}{\delta}} \geq 0$ とおけば,

$\mathbb{P}(Z \geq \sqrt{2n \log \frac{1}{\delta}}) \leq \delta$

変形して,

$\mathbb{P}(Z \lt \sqrt{2n \log \frac{1}{\delta}}) \geq 1- \delta$ .

この不等式を読むと, $\delta$ を小さく取ったとき, ほとんどの確率で, ラーデマッハー確率変数の $n$ 個の和 $O(\sqrt{n})$ より小さくなるということを表しています.

ヘフディングの補題とヘフディングの不等式(Hoeffding’s lemma and Hoeffding’s inequality)

ヘフディングの不等式は, 学習理論においてもっとも大事な不等式の一つです.

確率変数の和が大きくなりすぎたり, 小さくなりすぎたりする確率を評価する際に使います.

$Z_1, Z_2, \dots, Z_n$ を有限で独立な確率変数とする. 任意の $i$ で, $Z_i \in [a, b]$ とする. ここで, $a, b$ は有限.

このとき, 任意の正の実数 $t$ に対して,

ヘフディングの不等式 $\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq t \Big) \leq e^{-\frac{2nt^{2}}{(b-a)^{2}}} \\ \mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \leq -t \Big) \leq e^{-\frac{2nt^{2}}{(b-a)^{2}}}$

これを証明するためには, ヘフディングの補題という命題を証明しないといけません.

$Z$ を $[a, b]$ の範囲にある有限な確率変数とする.

このとき, 任意の実数 $\lambda$ に対して,

ヘフディングの補題 $\mathbb{E}[e^{\lambda(Z-\mathbb{E}[Z])}] \leq e^{\frac{\lambda^{2}(b-a)^{2}}{8}}$

この補題の少し弱い不等式を証明します.

分母の8を2にしたバージョンです.

定数の部分なので, 本質的にはそこまで影響はないと言えます.

この証明ではたくさんテクニックがつまっているので, 丁寧に追うとよいと思います.

たとえば,

イェンセンの不等式(Jensen's inequality)
同一の確率変数を別の確率変数とみなす対称化(symmetrization)
$0$ で対称な確率変数は, ラーデマッハー確率変数をかけても分布が変わらない
複数の確率変数で, 期待値を取るとき, 他の確率変数は固定してみることができる

などです.

証明: 証明で使うイェンセンの不等式をまず紹介する.

イェンセンの不等式は, 以下の不等式のことです. 詳細はここでは説明しません.

関数 $f$ が凸関数であるとき,

イェンセンの不等式 $f(\mathbb{E}[Z]) \leq \mathbb{E}[f(Z)].$

今回は, 指数関数 $e^{-x}$ が凸関数であるので, イェンセンの不等式が使えることを用いる.

次に, 補題の不等式の左辺には, $Z$ が２つ登場する. 片方を $Z$ と全く同じ分布に従う別の確率変数とみなしても特に問題はない.

よって, ２つめに登場する $Z$ を $Z'$ のようにすると(symmetrization),

$\mathbb{E}[e^{\lambda(Z-\mathbb{E}[Z])}] = \mathbb{E}_{Z}[e^{\lambda(Z-\mathbb{E}_{Z'}[Z'])}] \leq \mathbb{E}_{Z}\mathbb{E}_{Z'}[e^{\lambda(Z-Z')}]$ .

最後の不等式はイェンセンの不等式を用いた.

よって,

$\mathbb{E}[e^{\lambda(Z-\mathbb{E}[Z])}] \leq \mathbb{E}_{Z, Z'}[e^{\lambda(Z-Z')}]$ .

$Z - Z'$ は, $0$ に関して対称な確率変数なので, ラーデマッハー確率変数 $S$ をかけても分布は変わらない.

つまり, $Z - Z'$ は $S(Z - Z')$ と全く同じ分布に従う.

したがって,

$\mathbb{E}_{Z, Z'}[e^{\lambda(Z-Z')}] = \mathbb{E}_{Z, Z', S}[e^{\lambda S(Z-Z')}] = \mathbb{E}_{Z, Z'}\mathbb{E}_{S}[e^{\lambda S(Z-Z')}| Z, Z']$ .

チェルノフ上界の具体例で示したラーデマッハー確率変数のモーメント母関数を評価する式を用いて,

$\mathbb{E}_{S}[e^{\lambda S(Z-Z')}| Z, Z'] \leq e^{\frac{\lambda^{2}(Z-Z')^{2}}{2}}$ .

$Z, Z'$ は, $[a, b]$ であるから, $(Z-Z')^{2} \leq (b-a)^{2}$ .

したがって,

$\mathbb{E}_{Z, Z'}[e^{\lambda(Z-Z')}] \leq e^{\frac{\lambda^{2}(b-a)^{2}}{2}}$ .

以上から, ヘフディングの補題は示された.

この補題を用いて, ヘフディングの不等式の上の式だけ証明する.

ヘフディングの不等式の上から抑える式(再掲) $\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq t \Big) \leq e^{-\frac{2nt^{2}}{(b-a)^{2}}}$

証明: チェルノフ上界より,

$\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq t \Big) = \mathbb{P}\Big(\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq nt \Big) \\ \leq \mathbb{E}\big[ e^{\lambda \sum (Z_{i} - \mathbb{E}[Z_{i}])}\big] e^{-\lambda n t} \\ = \Big(\Pi_{i=1}^{n} \mathbb{E}\big[ e^{\lambda (Z_i - \mathbb{E}[Z_i]}\big]\Big)e^{-\lambda n t} \leq e^{\frac{n\lambda^{2}(b-a)^{2}}{8} - \lambda n t}$

最後の不等式は, ヘフディングの補題を用いた.

最後に, $\lambda$ で右辺を最小化すれば, 望む式が得られる.

参考文献

CS229 Supplemental Lecture notes Hoeffding’s inequality

Wikipedia: Moment-generating function

ウィキペディア: ラーデマッハー

*1:期待値や分散は, モーメントによって表現されるので, モーメント母関数が存在することは分散が有限であることより強い条件になる.

*2:数学書によくある同様に証明できる詐欺ではないです

*3:Independent and identically distributed

*4:簡単のため

*5:Rademacher 読み方はHans Rademacherに敬意を払ってドイツ読みにしています

ludu-vorton

Machine learning, Causal Inference, Algorithmic game theoryなどに興味があります。

伊藤清三のルベーグ積分入門 | 直線上の有界変動関数の全変動がWell-Defineでない問題!

直線上の有界変動関数の全変動がWell-Defineでない問題!

全変動の定義

問題点

定義の問題点

補助定理1が成り立たない問題

解決方法

定義を変える

Probabilistic State Translation in Extensive Games with Large Actions Sets

Introduction

Background

Extensive Game

Game Abstraction

Translation Method

Hard translation

Soft translation

reference

ヘフディングの不等式(Hoeffding's inequality)と諸々の確率の評価の不等式

確率のバウンドの基本

マルコフの不等式(Markov's inequality)

チェビシェフの不等式(Chebyshev’s inequality)

モーメント母関数(Moment generating functions)

チェルノフ上界(Chernoff bounds)

チェルノフ上界の具体例

ヘフディングの補題とヘフディングの不等式(Hoeffding’s lemma and Hoeffding’s inequality)

参考文献