マルコフ連鎖の話

データ分析

#機械学習

じょんすみす

2017.12.09

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、小澤です。

当エントリは「Machine Learning Advent Calendar 2017」の9日目のエントリです。

前回、単語のn-gramの話をしましたが、これはマルコフ性というものを仮定したモデルになります。マルコフ性というのは１つ前の状態のみが現在の状態に影響を与えると仮定したものになっています。

マルコフ過程とマルコフ連鎖

現在とか、過去とか時間軸的な話が出てきました。

マルコフ過程は上記のような1つ前の状態のみが現在の状態に影響をあたえると単純なモデルですが、時系列的な話にも発展していきます。実際のデータ分析では時間を軸に取った何かするということはよくあるでしょう。

また、時系列のみならず、他の用途でも利用可能です。例えば、本アドベントカレンダー1日目の線形回帰を発展させ、一般化線形モデルに拡張させたのが2日目のロジスティック回帰ですが、これをさらに発展させて階層ベイズモデルを利用した際にMCMC法というパラメータ推定の手法が出てきます。

このMCMCはMarkov Chain Monte Carlo(マルコフ連鎖モンテカルロ)の略となっています。このMCMC法の一種であるギブスサンプリングは後日yoshimさんが書く予定の潜在意味解析の手法であるLDAでも利用されています。そのため、この辺はきっと彼がくわしくかいてくれるんじゃないですかねぇw

また、Googleが発案した検索結果のランキング手法で大変有名なPage Rankですが、こちらもこのマルコフ連鎖の性質を利用したものになっています(余談ですが、Page Rankの名前の由来はホーム"ページ"に対するランキングではなく、Google創業者の1人であるラリー・ペイジから来ています)。

ランダムウォーク

さて、では最初にランダムウォークモデルを紹介します。

これは、どのようなものかというと3歩進んで2歩下がるみたいな感じです。

まず、家の玄関からスタートして、コイントスをします。その結果が表なら1歩前に進んで、裏なら1歩後ろに下がります。そしてまたコイントスをして...を繰り返していきます。連続で表が出続ければ最終的に会社に到達して、連続で裏が出続ければ最終的にベッドに戻ります。さて、n回コイントスをした時に今どこにいるでしょうか？

というのがランダムウォークになります。

試しにやってみましょう。

def random_walk():
    # スタート地点は0
    now = 0
    result = []

    for i in range(100):
        # ランダムに0か1を出して、0なら1歩後退, 1なら一歩前進
        if randint(2) == 0: 
            now -= 1
        else:
            now += 1
        result.append((i, now))
    return result

# 結果をプロット
df = pd.DataFrame(random_walk(), columns=['time', 'pos'])
df.plot.line('time', 'pos')

結果は以下のようになります。

上側に行くほど会社に近づいて、下に行くほどベッドに近づいてるとします。寝るか出社するか迷いながら出社へと向かっているようです。

この結果はランダムなので、実行するたびに異なります。うまくいけばベットにたどり着けるかもしれません。

ランダムウォークでは、現在の位置を次はそこから1歩先か1歩前のみに移動することになります。それ以前が進む方向に向かう傾向あったか、戻る方向に向かう傾向にあったかは関係ありません。その日は寒かったとかも関係ありません。これが、過去1つ前まで考慮する状態になっています。

数式的に書くと、

[latex] P(X_{t+1} | X_t, X_{t-1}, ... X_0)　= P(X_{t+1} | X_t) [/latex]

のように、条件としてtよりも前の時間の位置がなくても確率が変わらない状態になります。なお、現在の位置をX_tとして、次の位置X_{t+1}がどこになっているかを表すとします。

さて、ここでこの人が勤続年数2500日になったとしましょう。雑な計算のでおよそ10年間です(1年の勤務日数を　250日として)。どれくらいの割合で出社できて、どれくらいの割合でベッドに戻ったのでしょうか？

df2 = pd.DataFrame([random_walk()[-1][1] for _ in range(2500)], columns=['result'])
df2.plot.hist('result')

結果は以下のようになります。

もっとも割合が多いのは行くか戻るか迷った挙句最終的に玄関にいたパターンのようです。このようにランダムウォークで最終的にどこまで進めたかは正規分布に従います。

マルコフ連鎖

さて、ランダムウォークで現在の状態から次の状態が決まるイメージがわかったかと思います。例えば、現在5歩進んだ位置だから次は4か6にいるということは成り立ちますが、順調に進んでるから次も進みやすいとかそういうことはありません。

このようなものをマルコフ過程と呼びます。

マルコフ過程において、例えば玄関から会社までは100歩(近すぎますが気にしないでください)、ベッドまでも100歩として101歩進んだ(戻った)状態はないものとします。現在位置は+100 ~ -100までの範囲の整数のうちどれかとなります。このような取りうる値の範囲が決まっているもののことをマルコフ連鎖と呼びます。

マルコフ連鎖の例として天気の移り変わりを見てみましょう。

この図は、今日の天気と明日の天気の関連性を示しています。今日が晴れだった場合、明日も晴れる確率は1/2, 曇りになる確率は1/3, 雨になる確率は1/6としています。本来であれば、明日の天気は今日の天気だけで決まるものではありませんが、こういう状態になっていると過程しておいてください。

この状態遷移を以下のような行列Xで表現します。

これに対して、あるタイミングtにおいて天気wを以下のようなベクトルで表します。

[latex] {\bf w}^T_t = (x_1, x_2, x_3) [/latex]

ここでは

x_1　:　晴れの確率
x_2　:　曇りの確率
x_3　:　雨の確率

としています。時刻tにおける天気が晴れであった場合は

[latex] {\bf w}^T_t = (1, 0, 0) [/latex]

となり

時刻t+1の天気は

[latex] {\bf w}_{t+1} = X{\bf w}_t [/latex]

で求めることができます。さらにt+2は

[latex] {\bf w}_{t+2} = X{\bf w}_{t+1} [/latex]

となりますので、これは

[latex] {\bf w}_{t+2} = XX{\bf w}_t [/latex]

初期状態をt_0とした時、任意のタイミングtの天気は

[latex] {\bf w}_t = X^t {\bf w}_{0} [/latex]

でもとまることがわかります。

Google Page Rankとマルコフ連鎖の収束

マルコフ連鎖で、先ほどの天気のようなt日後の天気予報の計算のようなものを行っていくとします。このとき、天気推移の行列が特定の条件を満たしていると、wの値が収束していきw_{t+1} = w_tとなっていきます。

その辺の理論は難しい話なので、以下あたりを参照してください。

Ergodic theory - Wikipedia

この性質を利用したのが実はGoogleのPage Rank(以下PR)になっています。

PRでの基本的な考え方は以下の通りです。

ある人が特定のページを開く
ページ内のリンクのうちランダム1つをクリックし遷移する
遷移したページにあるリンクのうちランダム1つのリンクをクリックして遷移する

この行動を無限に繰り返した時、その人が開いているのはどのページでしょうか？各ページごとに開かれている確率を表したのがPRとなります。

実際には

ランダムジャンプ(飽きて全然関係なページに飛ぶ)
リンクを張っていないページや複数の孤立した島ができている状態への対応
この性質を利用して複数サイトでお互いリンクを張り合うスパムへの対応

なども含まれますが、ここでは簡単のため、ひたすらリンクを辿り続けられるものとします。

この時、あるページからリンクをたどって他のページへ遷移するという状況は先ほどの天気の例と同じように表すことができます。あるページから3つのリンクが貼られていたとしたら、それぞれ1/3の確率で各ページに移動します。ある人がtのタイミングで各ページにいる確率は同様にベクトルで表されますので、同様の計算が可能になっています。

また、「無限に繰り返す」はこの確率のベクトルが収束するまで繰り返せばいいということになります。

その結果人気のある(より多くのサイトからリンクが貼られているサイト)ほどそこにいる確率が高くなるので、PRも高くなるというは直感的にもなんとなくわかるかと思います。

実際にはウェブサイトは億や兆といった単位の数になりますので、この計算を行うには工夫が必要になりますが、基本的な仕組みはマルコフ連鎖で説明できることがわかっていただけたかと思います。