jyanjayakaの日記

はやめのリリース、しょっちゅうリリース

モンテカルロ木探索について

手をランダムに選択させて1ゲームをプレイさせる。(もちろんルール上許される手に限る。)

囲碁と将棋が違うのは、このようにプレイさせると囲碁はゲームがすぐに終わるが、将棋の場合はそうはいかないというところ。囲碁は単純に盤上に石が増えていって、それ以上置けなくなる。一方将棋はルール上可能な手を繰り返していつまでもゲームを続けることができる。

ランダムに手を選ばせるだけなら、1ゲームはすぐに終わる。互いに100手打つなら全部で200手がプレイされるが、ランダムに手を選ぶだけなら1秒以下で終わるだろう。

こうしてたくさんのゲーム数をこなさせる。こうすると、数あるゲームの中で、特定のある手を選択した時に白が負けやすいといったことが起こりうる。そうすると、どうもその手は白にとって勝率が低い「悪い手」であるということが言えそうだ。

こうして、各局面でランダムにプレイさせて、その中で最も勝率の高かった手を選択するという戦略が立てられる。

この戦略は強いだろうか?

まず原理的な問題として、ランダムなプレイでちゃんとゲームが終了することが必要だ。人間同士の場合は、ゲームが終了するように手を選択するのが普通だが、それを完全にランダムに選ぶとなるとゲームがちゃんと終わるかどうか保証されない。

実際、囲碁は終わるが将棋は終わらない。

なのでこの戦略はそもそも囲碁のようにランダムな手を選択しても終わるゲームにだけ有効。ここではそれを前提として話を進めよう。

まず考えられるのは、ランダムで選ぶのは適当過ぎるんじゃないか? ということ。これは確かにそうで、勝率が高いとか低いとかいうのはお互いがランダムにプレイした結果であって、もし人間が相手なら(ランダムな方法では「運悪く」選ばれなかった)上手い手があって簡単に負けるかもしれない。

「運が悪い」というのはプレイ数を十分多く取れば防げる問題のような気がする。ただこの「十分多く」というのが問題で、これはそもそも論として、囲碁のようなゲームはルール上許される局面の数が非常に多いから解析が難しいのだった。そのように十分大きなプレイ数を確保できるのであれば、そもそもAIを工夫する必要性があまりない。

 そこでいかに効率よく手を絞ってゆくかといういつもの問題に行き着く。

 

Google検索エンジンにみる線型代数の応用

参考サイト

How Google Finds Your Needle in the Web's Haystack

 

Google検索エンジンの基本的なアイデアは、

他のページからリンクをされていればいるほど、そのページのランキングが高くなる

というもの。要はリンクを行うことが一種の投票行為となっているのだ。我々はリンクを張ることで、ネット上の人気投票に知らず知らずのうちに参加していることになる。

ただし、一つ一つのリンクが全て同じ価値を与えるのではなくて、ランキングの高いページからのリンクは、より大きな価値を与えると考える。

このような条件を数式的に、定量的に表現する。

j番目のページ P_jはリンクを張っている他のページに対して、自身の価値 I(P_j)を均等に分配すると考える。例えば100のリンクを張っているページは、自身の価値を100等分してリンク先のページへ渡す。

このことを分配される側の P_iから見ると次のようになる:

 I(P_i) = a_{i1} I(P_1) + a_{i2} I(P_2) + \cdots + a_{in} I(P_N)

ここで I(P_i)はページ P_iPageRankを表す。 a_{ij}は重みであり、jからiへリンクが貼られているなら l_jをページjの張っているリンク総数として

 \displaystyle{\frac{1}{l_j}}

であり、jからiへリンクが無いなら0である。(自分自身から自分自身へのリンクは存在しないと考える。自分から自分への投票は出来ない!)

Nは世界に存在するwebページの総数であり、数千億とか、そういうレベルの数である。

このようなランキングの決定方法は、よくよく考えると再帰的である。実際、ページAのランキングを計算するためにはページBのランキングを知らなければならず、そのためにはページAのランキングを知らなければならない!

そこでこのように逐次的に考えるのではなく、巧妙な数学的テクニックを使おう。それは答えが既に分かっていると仮定し、それを文字で表すというものだ。

いま、全てのページのランキングが計算できたと仮定する。そしてこれを v_1, v_2 , \cdots v_Nと文字で表す。するとこれらの数は、上の数式に従い、連立方程式
\begin{align}
a_{11} I(P_1) + a_{12} I(P_2) + \cdots + a_{1N} I(P_N) &=P(I_1)\\
a_{21} I(P_1) + a_{22} I(P_2) + \cdots + a_{2N} I(P_N) &= P(I_2)\\
&\cdots\\
a_{N1} I(P_1) + a_{N2} I(P_2) + \cdots + a_{NN} I(P_N) &= P(I_N)
\end{align}

を満たす。

ところで連立方程式を解くための洗練された手法として、線型代数が使える。行列Aを

\begin{bmatrix}
a_{11} & \cdots & a_{1N}\\
\vdots & & \vdots \\
a_{N1} & \cdots & a_{NN}
\end{bmatrix}

と定義して、ベクトルvを

 \begin{bmatrix}
v_1\\
\vdots\\
v_N
\end{bmatrix}

で定義すれば、元の連立方程式

  Av = v

と表せる。行列Aを乗じても変化しないことが、その再帰性を表現している。また、この式はベクトルvが行列Aの固有値1の固有ベクトルであることを意味している。従って、次のことが分かった

ページのランクを求めたければ、行列Aの固有値1の固有ベクトルを求めればよい。

問題はこの行列がN x Nというとんでもない大きさの行列であることである。

 

誤差論(中心極限定理)から推定への流れ

前の記事で述べたように、中心極限定理は誤差論の基本定理と見なせる。そこで我々が理解したのは、誤差というものが持つ一般的性質、その分布の仕方であった。このことが分かると、次に統計学で言うところの推定へと進むことが出来る。

 

ある測定(例えば世論調査)を行った時に、その結果が真の値とどれだけ離れているのかを調べることは、測定の誤差を評価する問題に帰着される。そして中心極限定理によれば、十分大きなサンプル数で測定を行えば、誤差値の分布は正規分布に従う。だから、測定で得た値と真の値とのずれを確率的に調べることが出来る。

中心極限定理は誤差論の基本定理と見るべきだ

誤差の共通性質としての中心極限定理

例えばある測定を行うとしよう。

測定を正確に行えるよう、最新の注意を払うが、測定には誤差がつきものだ。

誤差には二種類ある。それは人為的誤差と、本質的誤差である。実験装置の設定不良などの、測定者の注意不足によって生じるものが人為的誤差である。一方、どのように注意深く実験状況を整えても拭うことのできない誤差が本質的誤差である。例えば望遠鏡で星を観測するとき、地球大気のゆらぎによる測定誤差が生じるが、これは観測者には制御できない誤差である。他にも様々な誤差の要因を考えることができる。一般に、誤差というのは様々な要因から生じたものが幾重にも重なって生じているのである。

こうしてどんな測定についても結果には(本質的)誤差が生じるが、その誤差にはどうやら共通性があるように見える。我々は多数の測定の結果を平均したものを、実験の結果として結論するから、測定の平均値と真の値との差を誤差と定義して、グラフ化してみると、だいたいこのようなグラフになる:

 

f:id:ziguzaku:20171015121328p:plain

 

誤差0が最も多く、誤差が大きくなればなるほどその数は少なくなってゆく。

世の中には様々な実験や測定があり、結果は種々のグラフにまとめられる。が、そこに生じる誤差に注目すると、上に示したような似通ったグラフが得られる。つまり誤差には様々な種類があるのではなく、ある単一の法則性に従っているように見えるのだ。誤差の法則性! 誤差とは我々には制御できないものなのに、そこに法則性があるとは。なんとも矛盾した物言いに聞こえるが、正確に予言できないものを予言する道具があった。それは確率論だ。そして実際、誤差を統治するいわゆる中心極限定理は、確率論によって定式化される。

 

中心極限定理

 X_1, X_2, \cdots, X_nを同じ確率分布に従う独立な確率変数とする。(要はある測定をn回繰り返すということだ。)この時新しい確率変数 Y_n

 \displaystyle{Y_n = \frac{X_1+ X_2 + \cdots + X_n}{n}}

で定義する。 Y_nはn回測定の平均値である。これが上で言うところの測定結果である。

次に確率変数 Z_n

 Z_n = Y_n - E[X]

で定義する。 Z_nは測定値 Y_nと真の値 E[X]との差であるから、測定の誤差を表している。このまま進んでも良いのだが、我々の目標は誤差の性質を明らかにすることであるから、ここにもう一工夫する。測定回数nを増やせば誤差の幅は小さくなる。これは誤差の性質の一つではあるのだが、このこと自体は大数の法則で既に示されている。今注目している誤差の性質とは関係ない。1万回の測定と100万回の測定を比べれば、確かに誤差の幅は小さくなるが、そのことはもう分かっていて、ある意味で当たり前で、今興味があるのは幅の大きさではなく、その分布である。

そこで、誤差の幅という目障りな因子を排除し、純粋に今見たい誤差の性質だけを取り出すため、 Z_n

 Z_n = \sqrt{n} (Y_n - E[X] )  

で定義し直そう。 \sqrt{n}倍したことで回数を増やしても誤差の幅が変わらなくなった。

中心極限定理とは

 Z_nはnを増大させた極限で正規分布 N(0, \sigma^2)に収束する。

という定理である。(ただしここで V[X] = \sigma^2。)こうして我々は誤差の分布が持つ本質的性質というものを知るに至った:

 十分大きなサンプル数で測定を行えば、その測定の誤差値の分布は正規分布に従う。

逆に言えば、小さなサンプル数の測定における誤差分布は、正規分布に従うとは必ずしも言えない。

大数の法則

ある実験を繰り返し行なった時、得られる結果の平均値がある値に近づいてゆくことが、観察されている。例えばコイントスの実験を1万回も行えば、表の出た回数の平均値は1/2付近となる。ここまでは確率論は全く関係ないことに注意する。これは一つの事実であり、確率は関係ない。ここまでは実験を繰り返し行うと、結果の平均値がある値に近づいてゆくように見える、という事実を述べているに過ぎない。確率論がどう言おうとも、この事実を変えることは出来ない。*1

 

この経験的な事実を確率論の枠組みで理論的に裏付け、説明するのが、大数の法則である。これは別に特殊なことをやっているのではなく、他の科学理論でも一般に行われていることである。例えば物理学では原子論という枠組みを使って、気体持つ性質を説明する。現実に対して何かモデルを構築し、それによって現実を説明するという科学の基本姿勢は変わらない。要するに、確率論は偶然という物理現象(と呼ぶのは些か抵抗があるが)についての理論だと考えれば良い。*2

 

大数の法則

要は、

平均値は確率に収束する。

*1:もしこの事実を疑うなら、自分でコイントスを1万回ほどやってみれば良い。ちなみにやったことがあるが、途中から苦行になってくる。

*2:ただしこの見方はだいぶ古典的確率論に偏っている。なぜなら現代的確率論では確率とは単に集合の大きさを測定する方法の一つであり、必ずしも現実と整合性が取れている必要がないからである。

古典的確率論と現代的確率論について

古典的確率論について

古典的確率論は確率を直感的に定義する:

 \displaystyle{(事象Aが発生する確率) = \frac{(事象Aのイベント数)}{(全イベント数)}}

この定義に従えば、原理的にはイベント数を「数える」ことで確率を計算することが出来る。古典的確率論で専ら興味があるのは個々の事象についての確率を求めるということである。(だから試験にはもってこいだ。「~の確率を求めよ」という問題が自然に出てくる。)

 

現代的確率論について

現代的確率論においては、確率は求めるものではなく、既に与えられているものと考えられている。そして、その上に何が築けるかに興味がある。

現代的確率論で言う確率とは、集合の「大きさ」を何らかの尺度(今の場合は「事象の起きやすさ)を元に与えるモノ=集合関数*1だと、非常に抽象化して捉えている。この視点に立つと、古典的確率論が扱う「確率」は、確率と呼ばれる集合関数を定義する一つの方法論を与えているに過ぎないことになる。実際、古典的確率は「全体に対する集合Aの割合」として集合Aの「大きさ」を測る。しかし一般には「割合」である必要はどこにもない。とは言っても、古典的確率論は現実世界に対する良いモデルを与えてくれるので、応用上役に立つ。

 

*1:集合に対して値を対応させる写像

統計学を現実世界に適応するための仮定について

統計学は、他の様々な現実を説明しようと試みる理論と同じく、現実に対して何らかのモデルを用意する。そのモデルが現実を上手く表現できていればいるほど、統計学は現実に対して有効な記述を行うことが出来る。

 

統計学が用意しているのは、個々のモデルについての理論的枠組みであって、それが実際に現実に当てはまるかどうかはこちらの判断に委ねられている。

こういう事情は例えば幾何学にもある。ユークリッド幾何学は数学的な理論であるが、これは現実の空間に対する精度の良いモデルとして用いられている。しかし、より精度の高いモデルも提案されていて、それは一般相対性理論を背景とした、リーマン幾何学*1である。

ユークリッド幾何学が我々の現実とどれだけ乖離しているのかという問題は、ユークリッド幾何学というモデルで考察できる範囲を超えている。それは物理学等が答えるべき問題である。

統計学も同じことなのだが、我々の直感から構成されているユークリッド幾何学と違って、統計学の提供するモデルを現実に当てはめることには、しばしば精神的ギャップを覚えることがある。

 

 

*1:正確には擬リーマン幾何学