2010/04/06

マルコフ連鎖を使って簡単な問題を解いてみよう

"Cute Gyoza / Meat Dumpling Key Chain" by ♥ Rainbowcatz ♥

はじめに

人工無能、一時期流行りましたねー。

難そうなわりに以外と簡単で、しかも結果が面白いということでRubyやなんかで実装している記事をよく見かけました。そういった中でマルコフ連鎖が注目されていた時期が一時期ありましたが、正直あれはマルコフ連鎖を利用しているというよりは、別のアルゴリズムにマルコフ連鎖という名前をつけたというか、あんまり関連性がないなーという印象でした。

マルコフ連鎖の本質はそういうことではなく、状態の遷移確率を行列によって求めたり、定常分布を固有値問題で計算するところにある、と自分は考えています。マルコフ連鎖についてのより詳しい説明は他のブログにお任せするとして(自分がやるとすぐにボロが出てしまう)、今回はマルコフ連鎖を使って簡単な問題を解き、実際にマルコフ連鎖がどんな感じなのか確かめてみることにします。

もんだい

二つの箱A,Bが用意されている。2つの箱の内部は完全に遮蔽されており、外部からは確認することができない。また、Aの箱には赤玉がN個、Bの箱には白玉がN個入っている。

ここで、両方の箱に腕を突っ込み、それぞれの箱から玉を一個づつ取り出し、交換し、反対側の箱のなかに入れることにしよう。今回の場合、Aの箱には赤玉がN-1、白玉が1個入ることになる。もちろん、Bの箱には赤玉が1個、白玉がN-1個入っている。

この試行をひたすら続けて、そう、例えば無限回行ってみよう。この場合、Aの箱に入っている赤玉の数はどれくらいであろうか?個数に対応した確率分布を求めよ。

回答

1回、2回ならまだしも、無限回なんて計算できるかクソが!そんなふうに考えていた時期が俺にもありました。

まず、Aの箱における赤玉の個数をmとおきます。すると、これは状態mの遷移問題と考えることができ、マルコフ連鎖が使えます。

また、1期間後にとりうることのできるmの遷移はm-1, m, m+1の3通りしか存在しません。以上を利用して、各mにおける状態の遷移確率を求めることができます。

まず、mがm+1に遷移する確率(m->m+1)を求めてみましょう。この場合、確率はAの箱の白玉が選ばれる確率とBの箱の赤玉が選ばれる確率の積に等しいので、

と表せます。

同様にして、m->m, m->m-1 についても表していきます。
  • mがmに遷移する確率は(i)Aの箱の赤玉が選ばれる確率とBの箱の赤玉が選ばれる確率の積と(ii)Aの箱の白玉が選ばれる確率とBの箱の白玉が選ばれる確率の積 の和((i)+(ii))に等しい。
  • mがm-1に遷移する確率は確率はAの箱の赤玉が選ばれる確率とBの箱の白玉が選ばれる確率に等しい。
以上の議論をまとめると、i->jへの遷移行列pijは以下のように表せます。

ここで、遷移行列はN×Nの次元を持っているものとします。

以上を利用して遷移行列を求め、pythonを用いて定常分布を算出しました。プログラムのソースコードを以下に示します。
#!/usr/bin/env python
#-*- coding:utf-8 -*-
"""
eig.py [N]

定常確率分布を記述したファイルを新しく書き込むプログラムです。
引数には箱に入っている玉の数を指定します。引数が指定されなかった場合には、N=10が用いられます。
"""

import sys

def main():
    number = int(sys.argv[1]) if len(sys.argv) == 2 else 10
    P = getStateMatrix(number)
    result = getFiniteStateSpace(P)
    fp = file("%i.dat" % number, "w")
    fp.write("\n".join([str(abs(num)) for num in result]))
    fp.close()

def getStateMatrix(n):
    """n個における遷移確率行列を返します"""
    from scipy import matrix
    P = [[getState(i, j, n) for j in xrange(n+1)] for i in xrange(n+1)]
    return matrix(P)

def getState(i, j, N):
    if   j == i-1: return float(i*i)/(N*N)
    elif j == i:   return float(2*i*(N-i))/(N*N)
    elif j == i+1: return float((N-i)**2)/(N*N)
    else: return 0.0

def getFiniteStateSpace(mat):
    """
    i->jに遷移する確率を行列(i,j)で表現した遷移確率行列から、定常分布を求めます。
    この関数は行列を転置する必要がない点に注意してください。
    
    mat : N×Nの遷移確率行列(numpyのmatrixでなければならない)
    戻り値 : N次元の定常分布ベクトル
    """
    from scipy import linalg
    la, v = linalg.eig(mat.T)
    result = zip(la, v.T)
    
    # 定常分布を求めるため、固有値が1に近い順で固有ベクトルをソートする
    result_sorted = sorted(result,
                           cmp=lambda x, y: cmp(abs(1.0-x), abs(1.0-y)),
                           key=lambda x: x[0])
    
    eig_value   = result_sorted[0][0]
    # 固有値が1近傍でなかったら例外を送出
    assert abs(eig_value - 1.0) < 1.0e-6, "the eigen value of FSS is apart from 1.0"
    
    fss = result_sorted[0][1]    
    return fss/sum(fss) # 正規化

if __name__ == "__main__":
 sys.exit(main())

実行は対象のソースコードを"eig.py"として保存してから、カレントディレクトリを適切なディレクトリに移動した後で、コマンドライン上から"python eig.py 10"のように指定してあげます。この場合、N=10(赤玉10個, 白玉10個)の際に遷移するであろう定常分布のデータが"10.dat"として書き出されます。

ここで、試しにN=6, 10, 50, 100における確率分布を載せておきます。
N = 6 のとき。離散的でよく分からないが、N=3付近の確率が一番高くなっている。
N = 10, 50 のとき。だんだん滑らかになっていく。
N = 100 のとき。N=50付近のピークが非常に鋭くなっている。

以上より、Nを増やせば増やすほど、N/2近傍により鋭いピークが表れるようになることが確認できます。

どーいうことが言いたいのか

結局のところ、お手玉の数を増やせば増やすほどmは中央付近で安定するわけです。「いや、最初に赤玉と白玉分けられているじゃん」それはそうなんですけど、今回の場合は無限回試行しているので、最初どのように分布してようが全く関係ないわけで。

最初は偏っていた分布がごちゃごちゃやっている内に中央付近に移動し、そこから多少のゆらぎはあるかもしれないが、結果的に中央へと帰ってしまうような、そういうイメージです。

まとめ

確率を無限回にすっ飛ばしたり、ある時点での確率分布を求めたり、モンテカルロ法にも使われているマルコフ連鎖はとっても賢くてすごいやつという記事なのでした

前のセメスターのレポートを微妙に公開してみるという話

前のセメスターで、『固有値問題』『フーリエ変換』『モンテカルロ法』を利用した問題を作成し、レポートを提出するよう求められた授業がありました。

物理学科で『固有値問題』といいますと、普通は『時間に依存しないSchrodinger e.q.を解いて粒子の波動関数を求める』といった問題が一般的なんですが、そんな問題を解いてもみんな同じことやってるので正直つまらない。別に物理と絡めて解けと指示されたわけではありませんので、そんなら違う問題でもいーかということで自分はマルコフ連鎖を使用して、簡単な問題を解いてみるといったレポートを提出しました。

この問題は自分で設定したんですが、正直簡単なわりになかなかきれいにできてる(うわー自画自賛)ということで、このまま埋もれたままにするのはもったいないなーと思いまして、微妙に一部分を変更して公開してみることにしました。この記事利用してレポート書いたら多分すぐにバレるし、別に問題ないかなぁと。

2010/04/04

Bloggerにはてなスターを設置するためには(まとめ)

はてなのサービス『はてなスター』は、はてなダイアリーだけしか設置できない…というわけではなく、livedoor, blogger, seeseaなど、外部のブログでも導入することができます。

Bloggerにはてなスターを導入するための具体的な方法は『はてなスターをブログに設置するには』を参照すればすべて書いてありますが、この内容はテンプレートがクラシックなど、標準のものしか対応していません。なのでこのブログのようにいろいろとカスタマイズしているブログに設置するためには、いささか面倒な手順を踏まなければいけません。ここではBloggerでの変更手順を、上記の記事を補足する形で説明します。

まず、はてなスターのJavaScriptは、h3タグに囲まれている内容を記事のタイトル、h3タグ内のaタグのリンク先を記事のpermalinkと推測して処理を行っています。よって、ブログのHTML構造がその方式に従っている場合は特に変更する必要はなく、ただheadタグ内直下に
<script type="text/javascript" src="http://s.hatena.com/js/HatenaStar.js"></script>
<script type="text/javascript">
Hatena.Star.Token = 'your-original-token';
</script>
を挿入するだけで良いです。

しかし、h3タグの中にaタグが複数個入っている場合や、ブログタイトルにh2タグなど別のタグを使っている場合には、正解のURLを教えてあげる必要があるため、h3タグの直下に
<h3 class='post-title'>
<a expr:href='data:post.url' style='display:none;' title='permanent link'></a>
とダミーのaタグを挿入し、Hatena.Star.SiteConfigにカスタマイズした辞書を入れてやります。

また、複数のJSを使っている場合、時々JS同士が競合して正常な動作が行われない場合があります。筆者の場合ははてなスターのJSとGoogle AnalyticsのJSが競合してしまったために、Add Starボタンを押してもログインのダイアログが表示され、正常にスターが追加されないというエラーが生じていました(*1)。こういった場合、JavaScriptのロード順を変えることによって解決する場合があります。具体的には、このブログですとbodyタグ終了の直前に以下のようにコードを挿入することによって解決しました。
<script type='text/javascript'>
  var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
  document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
  </script>
<script type='text/javascript'>
  try {
  var pageTracker = _gat._getTracker("your-UA-code");
  pageTracker._trackPageview();
  } catch(err) {}</script>
<script src='http://s.hatena.ne.jp/js/HatenaStar.js' type='text/javascript'></script>
<script type='text/javascript'>
Hatena.Star.Token = 'your-original-token';
Hatena.Star.SiteConfig = {
entryNodes: {
'div.post': {
uri: 'h3 a',
title: 'h3',
container: 'h3'
}
}
};
</script>
要はGoogle Analyticsの次にはてなスターのJSが読み込まれるように修正したわけです。以上の手順によって、はてなスターの正常な動作を確認しました。この記事が皆様のお役に立てば幸いです。

(*1) おそらく競合の原因はクリックイベントのフックによるものと考えられます。

はてなスターを導入してみました

Bloggerでもはてなスターが導入できることを知ったので、試しに導入してみることにしました。導入自体はjavascriptコードを貼り付けて、CSSをちょこっといじるだけの簡単さ。うーん楽ちん。

追記
19:00 と…思ったら…正常にログイン処理が行われていない…
20:00 ん、ちょっとまった。ブックマークからスターつけるときちんと反映されるのに、なんでadd starボタンが機能してないのか。どうやら同じような現象に遭遇してるっぽいBloggerユーザーもいるんだけど、クリティカルな解決方法を提示しているブログが無い。なんでだ。たぶんどっかのjsと衝突しまっているためにこけてるんじゃないかと予想してるんだけど…
21:00 あ、でけた。あとで問題点のまとめを記事にしよう

2010/04/02

近況報告 2/2

前回の記事の続きです。

マダム・エドワルダ―バタイユ作品集 (角川文庫クラシックス)マダム・エドワルダ―バタイユ作品集 (角川文庫クラシックス)
生田 耕作

角川書店 1976-02
売り上げランキング : 161626
おすすめ平均

Amazonで詳しく見る by G-Tools

正直、クリスマスキャロルの次にバタイユさんを見るべきではありませんでした。『マダム・エドワルダ』はまだなんとか理解できた、読めたんですけど、『目玉の話(眼球譚)』はもう完全においてけぼりをくらいました。なんだこれは。なんていうかもう、すごい。さすが嫁に読んでほしくない作品ベスト5にランクインするだけはあるみたいな感じでした。ごめんなさい。ちょっと今の自分には理解できなかったです。

これは思春期に読ませると絶対悪影響が出る本。間違いない。

地下室の手記(光文社古典新訳文庫)地下室の手記(光文社古典新訳文庫)
安岡 治子

光文社 2007-05-10
売り上げランキング : 133420
おすすめ平均

Amazonで詳しく見る by G-Tools

ドフトエフスキーが面白かったので、次も攻めていこうと思った作品。古典とは思えないほど新鮮なテーマを扱っており、非常に面白く読める作品でした。何が新鮮かっていうと、現代におけるひきこもり問題や閉鎖的な人間関係、風潮を、150年も前に捉えてその心理状況を細かく描写しているという点が新鮮。自意識過剰な学生にぜひ読んでもらいたい小説。自分も少なからずそういう面がありましたので、なかなか参考になりました。うーん

遺産相続ゲーム―地獄の喜劇 (岩波現代文庫)遺産相続ゲーム―地獄の喜劇 (岩波現代文庫)
Michael Ende

岩波書店 2008-10-16
売り上げランキング : 83802
おすすめ平均

Amazonで詳しく見る by G-Tools
鏡のなかの鏡―迷宮 (岩波現代文庫)鏡のなかの鏡―迷宮 (岩波現代文庫)
Michael Ende

岩波書店 2001-01
売り上げランキング : 15666
おすすめ平均

Amazonで詳しく見る by G-Tools

最後にこの2冊を読んで終了。ミヒャエル・エンデは中学生のころから大好きで、今思えば自分の性格の形成に重要な役割を果たしていた作家でした。遺産相続ゲームは前々から読んでみたかった作品で、現代における社会問題をうまく劇の中に暗喩として組み込んだ戯曲です。メモを取りながら楽しく読ませていただきましたが、強いて言うなら冒頭の筆者の言い訳と最後の作者ノートはいらなかったんじゃ無いかなという気がします。だってこれのおかげで考える楽しみが半減してしまったんですよ。それはそれで答え合わせのようで楽しんだ部分もあるんですけど…
最後の鏡の中の鏡はこれで3度目です。今思うと、この作品って宗教やら資本主義やら現代社会やらの皮肉が多分に込められた作品だったんですね。中学、高校のときはそういう意図に全く気づかず、なんか雰囲気が不思議で面白いなぁとか情景描写が独特だなぁとか、そういった感覚で読んでいたような気がします。うーん、これは成長なのか、それとも純粋に楽しめなくなったのか、どうなんでしょう。

というかこれ、いま思ったら読んではいけない毒書小説の内3冊も読んでるじゃないですか。うわーだめだこりゃ。でも面白かったから、それはそれでいいか。

よーし、これで貴重な春休みが終わったので、いまんところはマクロ経済とミクロ経済を攻めていきたいと考えています。とにかく大学のうちは選り好みしないで、いろんなものに手を出してみたいです。はい。

追記(4/4)
あ、思ったんですけど、こーいった類の、いわゆる古典ってやつは、回りの知人や教授なんかと話をしていかないと、本当に本質が掴めずに訳わかんないまま終わります。普通の小説を読んでいく感じで読み進んでしまうと、ただ長ったらしい割に展開が薄く、つまんねーとか思ってしまうので注意。カラマーゾフの兄弟なんてあれ自分一人じゃ絶対に気づかないだろって箇所が何個もありました。本当に、せめてあれだけは、一人で読むことをお勧めしません。

2010/04/01

近況報告 1/2

"Recent Photos" by Art Pets Photography

大学生は当たり前ですが休みが2ヵ月もありー個人的にはそんなにいらないんじゃないかとも思うわけですがー特に4年生ともなりますと、自分の周りではそれはもう、いろんな人が好き勝手なことをやっているわけであります。具体例を挙げますと、雀荘でプロとして活躍していたり、iPhone, Androidなどのアプリを開発していたり、いきなり数十万を持って地球一周すると豪語して日本を飛び出していったり、おら医者になるとか言って医学部に入りなおしたり、路上でライブやってたり、かと思えば大学の図書館で泊まり込んで24時間勉学に励んでいたり、などなど…みなさん生き生きと活動をしているなぁという実感を持ちまして、自分もそれじゃあ社会人になって後悔しないような大学生活を送っていこうと、決意を新たにしたわけでございます。

で、自分はといいますと、ひたすら本を読んでおりました。なんだそれだけかと思うかもしれませんが、今まで自分が読むものと言えば技術書や学術書で、特に文学というものを深く嗜好してはおりませんでしたので、聡明な文学部の方と協力しながら、ひたすら本を読み込むという作業を行っていました。
ですから自分の春休みは、本を読んで、TOEICの対策をして、仕事をして、ちょくちょく飲み会やら気になる人と会う、という一日の繰り返しでした。というわけで、いままでどんな本を読んで、どんな感想を持ったのか、少し羅列してみることにします。

カラマーゾフの兄弟1 (光文社古典新訳文庫)カラマーゾフの兄弟1 (光文社古典新訳文庫)
亀山 郁夫

光文社 2006-09-07
売り上げランキング : 3999
おすすめ平均

Amazonで詳しく見る by G-Tools
まずはこれ。でででん。「この小説すげぇ!」という人が自分の回りに何人もおり、しかも『東大教官がすすめる100冊』にぶっちぎりトップになっているということで今までずっと読んでみたかった書籍(*1)なのですが、正直これ去年の夏に読もうとして挫折したんです。とにかく登場人物は多いし、愛称があるし、メインキャラクターの紹介で数百ページ続くし、文学に慣れてないのにこれはだいぶハードルが高い代物でした。

今回は前回の反省を生かして、常にノートを取るようにし、重要な箇所は線を引いてノートと比較してみるなどして、一日100ページくらいのゆったりしたペースで読み込んでいきました。あとは周りの人に質問をして、さらなる理解を深めるといった形です。この書籍は全部で5巻くらいあって、1巻につき大体500ページあるので、1ヵ月くらいで読破することができました。やった。

この小説の凄いところは、もうありとあらゆる欲が凄まじいリアリティを持って描かれているところです。そして、その欲にかかわる普遍的な悩みや行動が、これまでかというまでにせめぎあっているわけです。『こういう人間いるよなぁ』とも思いますし、『あ、これ自分だわ』とも思うような、そういう小説です(*2)。

個人的には2巻の大審問官とゾシマ長老の話が一番楽しめました。あれが一番読み応えのある箇所です。特に無心論者が多い日本では、大審問官の話はある程度共感できるのではないでしょうか。二者の対立した意見をそれぞれ『プロとコントラ(天使と悪魔)』とする亀山氏の解説は、なるほどなという印象です。

この小説はまた数年後にもう一回読み込んでおくことにします。とにかくこの作品は一回読んだだけでは完全に理解することはできません。しかも数年経ちますとまた全然違う印象になっているでしょうし。フョードルの心境が理解できるようになる日は来るんでしょうか。

(*1) 今回読んだ古典新訳文庫の亀山訳は誤訳が酷いということで、よく批判の対象となっています。確かに論文なんかで使うにはこの訳は不適切かなぁと思う箇所は(サイトを見るかぎりですと)いくつか存在しますが、普通に楽しむ分にはこれで問題無いような気がします。特に本をあまり読まない方々にとってはなおさらです。

(*2) ちなみに自分が一番近いなぁと思ったキャラクターは、イワンとコーリャです。イワンの独白やコーリャの暴走部分はなんかこう、自分を客観的に見ているようで、単調直入に言うとすんごく苦痛でした。あと1巻のドミートリーが自身の恋愛観をアリョーシャに伝えている箇所とかもう…あばばばばば

クリスマス・キャロル (光文社古典新訳文庫)クリスマス・キャロル (光文社古典新訳文庫)
池 央耿

光文社 2006-11-09
売り上げランキング : 124146
おすすめ平均

Amazonで詳しく見る by G-Tools
続けて重い本を読みたくなかったので、息抜きとして読んだ本。イギリスの文豪ディケンズの代表的な作品。読んでたら涙ぐんでしまい、周りの人に見られてちょっと恥ずかしかったので、読むときは家など人に見られない場所がおすすめです。ページ数も170Pと非常に少ないので、自分は2日で読了しました。

とにかく有名すぎる作品で、内容は非常にありきたりです。ですが、今後の先行きが不透明で、ますます拝金、功利主義がその勢力を強めている現在だからこそ、こういった作品が重要になってくるのだと思います。

最後にamazonのレビューで共感したtongue氏の文章を引用して終わります。
スクルージは守銭奴というより、心に傷を抱えながら、懸命に世間と戦い、いつしか損得しか信じなくなってしまった企業家といったほうがぴったりだ。そんな男が精霊の導きで、幼い自分や青春時代の自分を思い出し、少しずつ人間らしい暖かい心を取り戻していく。その暖かさの象徴は暖炉を囲んだ食事であり、家族だ。本書は子供より大人に読んでほしい。大人たちは多かれ少なかれ、スクルージであると思うから。
あーだめだ。たった2冊書いただけでこんなに多くなってしまった。また明日続きを書くことにします。