ludu-vorton

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

Variable Selection For Causal Inference | Causal Inference: what if, Chapter 18

This is a personal note for my study. There might be some errors, so if you notice them, I'd be happy to let me know.

The notation here follows Causal Inference: What if.

Here is a link to this book.

www.hsph.harvard.edu

Also, the figures shown in the note come from Hernán MA, Robins JM (2020). Causal Inference: What If. Boca Raton: Chapman & Hall/CRC.


There are several methods to estimate the causal effect of a treatment A on an outcome Y. For example,

  • stratification
  • outcome regression
  • standardization
  • parametric g-formula
  • g-estimation

All of these methods above need to adjust covariates L to achieve conditional exchangeability though in different ways. How do we select such covariates?

A means to select covariates to be used to predict an outcome Y cannot be applied to the selection of covariates for causal analyses. Hence, this chapter summarizes the ways to select variables for the adjustment.

18.1 The different goals of variable selection

Prediction tasks do not have to consider confounding variables while causal inference tasks do have to consider confounding ones. So, applying an automatic selection of variables for predictive models to causal inference models introduces some bias.

Here are methods for the selection of variables for predictive purposes.

Selection of variables for predictive purposes

Brute force

Try all possible combinations of variables available to measure predictive power using some pre-defined criterion (e.g. Akaike's information criterion). This approach becomes infeasible as the number of covariates increases.

Forward selection

Start with no variables. In each step, add the variable that leads to the greatest improvement. Stop when no further improvement.

Backward elimination

Start with all variables available. In each step, eliminate the variable that leads to the greatest improvement. Stop when no further improvement.

Stepwise selection

a combination of forward selection and backward elimination.

Shrinkage

Use LASSO regression. If parameter estimates are nearly 0, then eliminate these variables. Again, fit some regression model.

18.2 Variables that induce or amplify bias

Imagine you have the unlimited computational power and a dataset with a quasi-infinite number of individuals and many variables measured for each individual including a treatment A, an outcome Y, a large number of variables X. Some of X might be confounders of the effect of A on Y.

Then, Shouldn't we adjust for all measured variables X using stratification/outcome regression, standardization/g-formula, IP weighting, or g-estimation? The answer is NO! Let's see some examples where adjustment introduces biases.

Selection bias under the null

Consider the figure shown below.

f:id:gmorishita:20200306184537p:plain

There is no effect of A on Y, so the average causal effect is zero. That is,


\mathrm{E}[Y^{a=1}] - \mathrm{E}[Y^{a=0}] = 0

There is no confounding by L. Hence, we can unbiasedly estimate the causal effect by


\mathrm{E}[Y|A=1] - \mathrm{E}[Y|A=0].

See what happens if we adjust for L. We estimate the causal effect via g-formula:


\sum_l \mathrm{E}[Y | A=1, L = l]\Pr(L=l) - \sum_l \mathrm{E}[Y|A=1, L=l]\Pr(L=l).

In the above DAG, L is associated with A, so


\Pr(L = l|A) \neq \Pr(L=l).

Therefore, generally, the estimate of g-formula is not equal to  E[Y|A=1] - E[Y|A=0], thus is biased. When A-Y association adjusted for L is expected to be non-null even though the causal effect of treatment A on the outcome Y is null, we say that there is selection bias under the null.

Selection bias under the alternative or off the null

Consider another DAG.

f:id:gmorishita:20200306184628p:plain

There is no confounding by L, so


\mathrm{E}[Y^{a=1}] - \mathrm{E}[Y^{a=0}]  = \mathrm{E}[Y|A=1] - \mathrm{E}[Y|A=0].

Adjusting for L via g-formula, the average causal effect is


\sum_l \mathrm{E}[Y | A=1, L = l]\Pr(L=l) - \sum_l \mathrm{E}[Y|A=1, L=l]\Pr(L=l).

For the same reason,


\Pr(L = l|A) \neq \Pr(L=l).

Therefore, the estimate of g-formula is biased. If A-Y causation was null, A and Y would be independent whether we adjust for L or not. Only when there is a causation between A and Y, there is a bias. That is why we call this kind of bias selection bias off the null.

Overadjustment for mediators

f:id:gmorishita:20200306184654p:plain

Next, consider the DAG. An adjustment variable that is affected by A and affects Y is called a mediator. If we adjust for a mediator, that blocks the effect of A on Y that goes through L, introducing biases.

Common feature of adjustment variables that introduce bias

The adjustment variables mentioned above have the same feature. They are affected by treatment A, and thus are post-treatment variables. So, you might come up with the rule of thumb that adjustment for post-treatment variables are prohibited.

However, there is an exception where post-treatment variable can be used to block the backdoor path between treatment A and the outcome Y as shown in the figure below.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/92f42288-a72c-46f9-9b1d-b515723b49e2/Untitled.png

So, we cannot decide whether to adjust for L or not from the data but from information outside the data (e.g. experts' advice)

The myth of selection of adjustment variables

Next, we consider the question of adjustment for variables L. Assume that the temporal order is L A Y. It is said that an estimator that adjusts for all variables L minimizes the bias, which is a false belief. Consider the following DAG.

f:id:gmorishita:20200306184753p:plain

L is a collider, so adjustment for L introduces the bias. There is another reason to avoid the myth of adjustment for all variables.

Think about the following DAG.

f:id:gmorishita:20200306184816p:plain

If we adjusted for U, we could estimate the average causal effect unbiasedly. However, U is an unmeasured confounder, so the bias cannot be removed. Even if we adjust Z, we cannot eliminate the bias introduced by U. Rather, adjustment for Z may amplify the bias. That is, the A-Y association adjusted for Z may be larger than the A-Y association not adjusted for Z. This kind of bias is called Z-bias.

18.3 Causal Inference and Machine Learning

Putting the problems discussed previously aside, we assume that X includes o variables that may induce or amplify bias. Also, X has all confounders L of the average causal effect of A on Y. The next problem is when X is very high-dimensional.

When using the plug-in g-formula, we will estimate the mean outcome Y conditional on the variables X b(X).


b(X) = \mathrm{E}[Y|X. ]

When using IP weighting, we will estimate the probability of assigning the treatment conditional on the variable X π(X).


\pi(X) = \Pr(A|X).

Traditionally, we use a parametric model such as linear or logistic regression to estimate b(X) and π(X). But, when X is high-dimensional, for example, the number of samples is much smaller than the dimension of X, the traditional parametric models do not work. Therefore, we have to come up with solutions.

LASSO

Use lasso to eliminate the variables automatically.

Machine learning algorithms

Use machine learning algorithms originally used for predictive purposes.

However, there are two major problems.

  • No guarantee that the selected variables will eliminate confounding (DR estimator can mitigate the problem because it has resistance to biases)
  • statistical black boxes with largely unknown statistical properties (variance may not be wrong, thus the confidence intervals will lose their frequentist interpretation.

In the next section, we discuss how to solve these two problems with DR estimators.

18.4 Doubly Robust Machine Learning Estimators

In this book, there is no accounting for why sampling splitting and cross-fitting, which we describe below. Under certain conditions, applying these two methods enables us to construct a consistent doubly robust estimator that will asymptotically follow a normal distribution with mean at the true value of the causa parameter.

sampling splitting

  1. Split the dataset into an estimation sample and training sample.
  2. Estimate b(x) and π(x) using training sample
  3. Compute the DR estimator using estimation sample

Cross-fitting

  1. Split the dataset into two halves.
  2. do sampling splitting
  3. Swap the roles of the estimation and training halves
  4. Average the DR estimates

18.5 Variable selection is a difficult problem

Doubly Robust Machine Learning (DRML) does not solve all our problems for at least four reasons.

  • It is not possible to identify all important confounders or to rule out variables that induce or amplify bias
  • The choice of machine learning algorithms depends on the causal structure that is usually unknown.
  • The implementation is very hard
  • The variance might be too big to be useful,

The last problem could be solved by removing the variables that is strongly associated with the treatment A. But the removed variables might be potential confounders to eliminate the bias.

The best way is to carry out multiple sensitivity analyses and look at all the results. If we get similar results, we are confident in the results. If not, let's try to understand why?

Reference

Hernán MA, Robins JM (2020). Causal Inference: What If. Boca Raton: Chapman & Hall/CRC.

Instrumental Variable Estimation | Causal Inference: What if, Chapter 16

This is a personal note for my study. There might be some errors, so if you notice them, I'd be happy to let me know.

The notation here follows Causal Inference: What if.

Here is a link to this book.

www.hsph.harvard.edu

16.1 The three instrumental conditions

If Z meets the following three conditions, we say that Z is an instrumental variable (IV).

  1. Z is associated with A (relevance condition)
  2. Z does not affect Y except through its potential effect on A (exclusion restriction)
  3. Z and Y do not share causes

Condition (2) can be written as:


Y_i^{z, a} = Y_i^{z', a} = Y_i^{a} \quad \forall z, z'.

Precisely, condition (3) can be expressed as:


Y^{a, z}\perp  Z \quad \forall a, z.

Empirically, condition (1) can be verified while condition (2) and (3) cannot.

The three conditions are not sufficient to identify the causal effect in the population. One more condition is required. It will be described in 16.3.

Example of instrumental variables

  • A: Smoking, Y: Weights, Z: the price of cigarette
  • A: Intake of alcohol, Y: the risk of alcohol, Z: the genetic factor associated with alcohol metabolism
  • A: COX-2 selective versus non-selective non-steroidal anti-inflammatory drugs, Y: the outcome on gastrointestinal bleeding, U_z: physician's preference for treatments, Z: last prescription issued by the physician before the current prescription
  • Z: access to the treatment, for example, physical distance or travel time to a facility

16.2 The usual IV estimand

When the three conditions above and the additional condition hold, the causal effect is identified as follows:


\mathrm{E}[Y^{a=1}] - \mathrm{E}[Y^{a=0}]= \frac{\mathrm{E}[Y|Z=1] - \mathrm{E}[Y|Z=0]}{\mathrm{E}[A|Z=1] - \mathrm{E}[A|Z=0]}

, which is called the usual IV estimand.

How to compute the IV estimand?

You can estimate each of the four expectations above. That means you fit two saturated linear models such as:


\mathrm{E}[A|Z] = \alpha_0 + \alpha_1Z, \\ \mathrm{E}[Y|Z] = \beta_0 + \beta_1Z.

There is another means to estimate the usual IV estimand. It is a two-stage least squares.

two-stage-least-squares estimator

  • Fit the first-stage treatment model

\mathrm{E}[A|Z] = \alpha_0 + \alpha_1Z.
  • Fit the second-stage outcome mode

\mathrm{E}[Y|Z] = \beta_0 + \beta_1\widehat{\mathrm{E}}[A|Z].

 β_1 will always be numerically equivalent to the standard IV estimate.

However, the confidence interval is usually so wide when A and Z are weakly associated. A commonly used rule of thumb is to declare an instrument as weak if the F-statistic from the first-stage model is less than 10.

structural mean model

The two-stage-least-squares model requires investigators to make strong parametric assumptions. Therefore, sometimes structural mean model can be used and estimated via g-estimation.

16.3 A fourth identifying condition: homogeneity

There are four homogeneity conditions.

  • constant effect of treatment A on outcome Y across individuals (A is dichotomous)

Y_i^{a=1} - Y_i^{a=0} = const \quad \forall i.
  • equality of the average causal effect of A on Y across levels of Z both in the treated and in the untreated. (Z, A are dichotomous)

\mathrm{E}[Y^{a=1} - Y^{a=0}|Z=1, A=a] = \mathrm{E}[Y^{a=1} - Y^{a=0}|Z=0, A=a]\quad \forall a =0,1
  • U is not an additive effect modifier (A is dichotomous)

\mathrm{E}[Y^{a=1}|U] - \mathrm{E}[Y^{a=0}|U] = \mathrm{E}[Y^{a=1}] - \mathrm{E}[Y^{a=0}].
  • Z-A association on the additive scale is constant across levels of the confounders U (no restriction on A)

\mathrm{E}[A | Z = 1, U] - \mathrm{E}[A | Z=0, U] = \mathrm{E}[A|Z=1] - \mathrm{E}[A|Z=0].

The fourth condition has some testable implication. For a dichotomous A, if some of the confounders are measured, it must be the case that the difference is the same across levels of the measured confounders.

For a continuous A, if we are willing to make additional assumptions about linearity, the variance of the treatment A must be constant across levels of the instrument Z.

Homogeneity seems implausible to some people.

16.4 An alternative fourth condition: monotonicity

We investigate an alternative assumption to homogeneity. We define some counterfactual variables to describe a new condition named monotonicity.


A^{z=1}: \text{indicator of the treatment if assigned to no treatment} \\A^{z=0}: \text{indicator of the treatment if assigned to treatment}

Monotonicity is described as follows:


A^{z=1} \geq A^{z=0}.

Assuming this monotonicity property, the usual IV estimand equals


\mathrm{E}[Y^{a=1} - Y^{a=0}|A^{z=1} =1,  A^{z=0} = 0].

Which is the causal effect in the complier. What complier means is Z and A are compatible: A=Z.

Monotonicity seems plausible, but there are some issues discussed below.

Relevance issue

The proportion of the compliers can be small, so if you know the causal effect in the compliers, it would be hard to make a decision to assign the treatment to the overall population.

Observational data

There are likely to be defiers ( A ^ \{ z=1 \} < A ^ \{ z=0 \} ).

ill-defined Partitioning

See Causal Inference: What if.

16.5 The three instrumental conditions revisited

What if the conditions fail to hold?

Condition (1): What if a Z-A association is weak?

  • Wide 95% confidence interval
  • Amplify the bias caused by violations of condition (2) and (3)
  • weak instrumental variable itself causes a bias

Condition (2): What if the absence of a direct effect of the instrument on the outcome does not hold?


\mathrm{E}[Y|Z=1] - \mathrm{E}[Y|Z=0]

If there is a direct effect of the instrument on the outcome, the numerator in the usual IV estimator just above will be incorrectly inflated by the denominator  E[A|Z=1] - E[A|Z=0] as if it were part of the effect of treatment A.

There is another possibility that there is a direct effect of the instrument on the outcome. For example, continuous treatment A is replaced in the analysis by a coarser version A*. A still exists through which Z affects Y. So, there is a direct effect Z → Y.

Condition (3): What if there is confounding for the effect of the instrument on the outcome

The same inflation happens as condition (2).

16.6 Instrumental variable estimation versus other methods

  • Unlike other methods, IV estimation requires modeling assumptions even if infinite data were available.
  • Relatively minor violations of the conditions for IV estimation might result in large biases.
  • The situation is more restrictive, e.g. a truly dichotomous and time-fixed treatment A, a strong and causal proposed instrument Z and homogeneity or monotonicity.

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

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

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

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

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

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

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

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

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

 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は, 以下のような定理である.

補助定理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つの単調増加な関数の差で表せるという証明において, 単調増加な関数を実際に構成していたので, それを採用する.

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

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

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


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も容易に証明できる.

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

Probabilistic State Translation in Extensive Games with Large Actions Sets

不完全情報ゲームの代表例と言えるポーカーで初めてプロに勝った人工知能 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の解の近似解を得る方法です.

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

2つ目は, 抽象化によって取りうる行動や起きうる状態が減ることです. 抽象化したからといって, 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の要素を1つ1つ見ていきます.

  •  N : プレイヤーの有限集合. 5人のポーカーなら  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は履歴の集合の要素です. 次に, プレイヤー1が最初に行動をします. 可能な行動は,  L, R, U, Dなので, それらも履歴の集合になります. 次に, もしプレイヤー1が L, Rをとった場合, プレイヤー2は,  a,  bのどちらかの行動を取ることができます. またプレイヤー1が Uを取った時, プレイヤー2は \alpha, \beta, \gammaのどれかの行動をとることができます. またプレイヤー1が Dを取った時, プレイヤー2は 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)について考えてみると, ゲームの最初はプレイヤー1が L, R, U, Dのどれかを取るので,  A(\phi) =  \{L, R, U, D\}となります.

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

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

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

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

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

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

Game Abstraction

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

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

例えば, ポーカーであればチャンスは最初のカードの手にあたります. テキサスホールデムというポーカーのゲームでは, 最初2枚のカードが配られます. 通常であれば,  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のナッシュ均衡から乖離すると思われるが, 実際はそうでないということです.

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

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

抽象化したゲーム
抽象化したゲーム

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

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

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

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

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

プレイヤー2の抽象したゲームの情報分割は,  \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は, 1つの履歴を出力するのではなく, 履歴に実数の値がついたペアとなる要素の集合を返すことです. この実数はその行動のとる確率と結びついています*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:関数の出力の実数部分だけの和をとったら1になるような要請はされていないのでこのような表現をしました.

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

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

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

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

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

確率のバウンドの基本

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

期待値  \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}.

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

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

後半も全く同じように証明できます*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が2つ登場する. 片方を Zと全く同じ分布に従う別の確率変数とみなしても特に問題はない.

よって, 2つめに登場する 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に敬意を払ってドイツ読みにしています