マルコフ連鎖を説明してみる。

えー説明の正確性については勘弁して下さいｗ
内容もとてつもなく初歩的なものです。
マルコフ連鎖って聞いた時に「あーこんなことしてるんだな」というアイデアが解るように・・・なるといいなｗ

以下の地点ABCを行き来するすごろくみたいなものをしてると思いましょう。

矢印の上にはその移動が起きる確率が書いてあります。
つまり、Aなら
AからB：1/3
AからC：1/3
AからA：1/3
という確率で移動します。

これを一覧表（マトリックス）にするとこんなかんじです。

 

で、まぁとりあえず何が知りたいの？って話になるわけです。
ここで知りたいことはx回移動させた時にコマがA,B,Cのそれぞれにいる確率です。

この確率を知るにはx回移動させる事を１０万回位実験してみればいい訳ですが、
マルコフさんがちゃんと数式で計算しました。
今回はその計算過程はパスということでｗ

で、マルコフはこの計算を行うことによって、移動回数xを増やしてゆくと最初にコマがA,B,Cの何処にいようとも、x回移動させた後にコマがA,B,Cにいる確率はある値に収束して行く事を発見しました。（この部分が前回の小話とつながってくるわけです）

まぁこれが実際何に使えるんですかねぇ？というお話に当然成るわけです。

ウェブ広告の例で行けばアトリビューション分析がこれに当たると思います。
広告A,Bと順番に見て、Cでクリックして購入ページまで行きました。という行動なんかはとてもすごろくっぽいですよね。（経済学なんかではMarkov model of User behaviorとかって言います）
つまりいくつかのページ（上で言えばA,B,C）があって、現在あるページ（A）にいる人が購入ページ（C）まで行く確率はどんなもんなのかを知ることが出来ると。
すると、その確率からページ（というか広告）Aの価値を計算できるようになります。

これによって広告間の価値の比較が可能になります。
今までも価値の比較は可能だったのですが、その場合最後にクリックされた広告のみを評価していたので、観閲による効果は考慮されていませんでした。その為必ずしも正確な比較が行えているとは言えない状況でした。
しかし、広告がアドサーバーから配信されるようになってユーザーの広告観閲のログが取れるようになり、そこにマルコフモデルを当てはめることによって観閲効果を含んだ価値で比較することが可能になったわけです。

多分もっと他の部分でも応用が可能で、例えばソーシャルゲームのユーザー行動にも当てはめることが可能でしょうし、スーパーマーケットにおける消費者行動なんかもマルコフモデルで分析が出来るんではないでしょうか？

 

参考にしたもの

ハーバード大学の統計学　第３１回
説明不要の名門大学の統計学がなんとタダで受講できてしまうというこの恐ろしさ・・・もとい便利さ。
まだ頭が柔らかいうちにこれだけの質の教育リソースにタダでアクセスできることは本当にありがたいと思います。
統計学の基礎的な知識があって、そこそこの英語力がないとまず理解不能だとは思いますが、その２つがある場合には素晴らしい教材となり得る講義でした。（そして前回の小話はここからのネタｗ）

R library for discrete Markov chain simulation

こちらはRでとりあえずマルコフ連鎖をシュミレートしてみたいという人におすすめです。
x回移動した時の確率は出してはくれませんが、x回の移動をシミュレートしてくれます。

 

Budget Optimization for Online Advertising Campaigns
with Carryover Effects

Newyork UniversityのPhDにいる人が書いたペーパー。
内容を全部読んだわけではないのですが、マルコフモデルでユーザー行動を説明して、インターネットの広告に観閲効果があることを説明しようとしてます。
そして、計測した効果を元に最適な予算プランの生成をmapreduceで使用可能な最適化アルゴリズムで行ってます。
このペーパーはちゃんと読んだら要約でもしようかなと思います。