Oddwit

同志社大学の講義ノート共有サイト、Doshisha Corgi（同志社コーギー）を今日、リリースした。

Doshisha Corgi
http://corgi.uni-kaji.com/

ちょうどWikiのように誰でも講義ノートを編集できる。一人が執筆して皆が買うという従来の紙媒体スタイルにはない、新しい価値を提供できるはずだ。あまり授業に出ていないから一部しか書けないという（僕のような）人でも参加できることや、間違った内容が載せられても見ている人が多ければ修正されやすいことなどがポイントだと思う。

最近はOpenCourseWareなどの教育コンテンツ2.0とも呼ぶべきものが流行しだしているし、Corgiも近い将来には大学生活に欠かせないツールとなってることを期待している。

プラットフォームはASP.NETだ。選んだ理由は単に「触れたことのないものを試してみたいから」だったが、それにしてもマイクロソフトには体力を奪われた。簡単なことが簡単にできなさすぎる…。

ASP.NETはフレームワークとしてはいまいちウリどころが掴めない、というのが正直な感想。小さいシステムに向かなさそうだとは思っていたが、だからといって大規模システムに適すのかどうかも判断しかねる。油断しているとビューとコントローラが密着してしまうのが特に気に入らない。ASP.NETの流れに乗っているだけではロジックを後ろに追いやれなかった。

それに、Web特有のひねりや落とし穴を隠蔽してGUIアプリのような感覚でWebアプリを作れるのかと思っていたが、フタを開けてみればそうでもない。ビューへのデータの送り出し方やエスケープのタイミングなどの明確な指針が存在しないし、結局フォームやセッションを扱うときは通常のWebアプリ開発のノウハウが欠かせない。

あ、ちなみに良いところもある。たとえばバリデーションの扱いは大変優れている。テキストボックスなどの横にバリデーション用の部品を配置するだけで、ルール違反の入力があったときはフォームの送信自体も制御してくれる（かのような演出をしてくれる）。POST時に値をチェックして違反なら戻して…というような泥臭い処理はほとんど必要なかった。

さておき、リリースはしたがこれからが大変なところだ。バグをつぶそう。機能を増やそう。宣伝もしよう。でも本当に有意義だという自信が僕を動かすよ。

Yahoo!がPHPエンジニアを雇う時に聞く質問

20問ほど正解してしまった。
そろそろPHPから離れたほうがよさそうだ。少なくともPHP6が出るまでは。

しかし、こういう質問で採用される職には就きたくないなぁとつくづく思う。使い古されて捨てられるのが目に見えるようだ。業界を知らないから憶測の域を出ないが。

あらすじ：
Flashで、遺伝的アルゴリズム（GA)で巡回セールスマン問題を解くアプリを実装してみた。GAではパラメータのチューニングがかなり重要な要素だということが理解できた。

実行はこちら。ソースもあるよ

巡回セールスマン問題

今回扱ったのは、いくつかの都市を全て一回ずつ巡回するとき、最短となるルートを発見しようという、いわゆる「巡回セールスマン問題」。

ごり押しで解こうとなると、12の都市で12!（じゅうにバン！と読む）≒4億7千万通りのルートを試さなければならない。できるだけ少ない試行でそれなりに短いルートを得るために、今回は遺伝的アルゴリズム（Genetic Algorithm, GA）を使う。この実装では、12箇所の場合、調べる回数が数万回にまで減らせることが分かった。

遺伝的アルゴリズム

GAは、生物の進化にヒントを得たおもしろいアルゴリズムだ。定義や一般的なやり方についてはWikipediaあたりを見てもらうとして、ごく簡単に説明すると、生物の進化を模倣したアルゴリズムだ。問題に対するさまざまな解を生き物に見立て、解どうしで交配させて子どもを作ったり、環境に適さないものを淘汰したりすることで、確率的に最適解を見つける。

構成

主なクラスは5つ。

• Agent - 一人のセールスマンをあらわすエージェント。DNAを保持
• Population - セールスマンの集まり。世代を経るなどの動作をする
• World - 都市がばらまかれたマップ。エージェントのDNAを評価する
• Node - 都市。
• GA - アルゴリズムを実行する。

まずはPopulationオブジェクトとWorldオブジェクトを作成・初期化し、それをGAオブジェクトに渡して、myGA.run() で実行するという流れだ。

iPod Shuffleで目的の曲まで素早くたどり着く合理的な方法をマルコフ決定過程で実現するという、キモチワルーイ記事がありました。

http://norvig.com/ipod.html

マルコフ決定過程は最近授業で習ったので、復習も兼ねて解説してみます。うまく解説できていたら拍手してください。

まず基礎知識として、
・Shuffleは画面がないので基本的に手探り
・シャッフルモードと通常モードがある
・この方法は面白いけど実用的じゃない
以上を把握しておきましょう。

■考え方
iPod Shuffleで、たとえば Keith Jarrett の The Song Is You を聴きたいとします。でも今 Art Farmer を聴いてるから、Kまで行くにはボタンをバシバシ押さなくてはいけない。というわけで、

1. シャッフルモードで何回かジャンプし、
2. ある程度目的の曲に近いところに着地したら、通常モードに切り替える

という戦略で、素早く目的の曲にたどり着こうという話です。

問題は２の「ある程度」。じゃあ実際どれだけ近づいた時点で通常モードに切り替えるのが最適なのか、そして平均どれだけ時間がかかるのか、を解明してみましょう。

■言葉の定義
まず次の５つの言葉を定義します。

「状態」
iPodでは、状態とは「今どの曲を再生しているか」を指します。なので、N曲入っているiPodではN個の状態が存在します。1GBのShuffleでは N=250 ぐらいですね。

「アクション」（方策）
シークボタンを押すことで次の曲へ行くのが、アクションに相当します。ここでは「シャッフル移動」と「シーケンシャル移動」という二つのアクションを定義。シーケンシャルは通常モードで移動することを指しますが、一曲だけの移動ではなく、ある曲から目的の曲にたどりつくまでの一連の移動を指すことにします。

「遷移」
ある状態から＋あるアクションを取ることによって遷移しうる先を、その確立とともに列挙します。シーケンシャル移動では、上で決めたように必ず目的の曲へたどり着きます。シャッフル移動では、等確率でN個の状態のどれかへ遷移します。

「コスト」（報酬）
それぞれの遷移にはコスト、ここでは時間がかかります。シーケンシャルでの移動には1秒かかるとしましょう。シャッフルではイントロを再生して曲名を思い出さないといけないので5秒ないし10秒くらいでしょうか。

「価値」
それぞれの状態には価値があります。これは、ある状態から目的の状態へ行くためにかかりそうなコストによって決まります。簡単に言うと、目的の曲に近いほど価値が高いわけです。

■状態の価値判断
ある状態の価値 V(s) を、目的の状態にたどり着くまでにかかるであろうコストとします。すべての s について V(s) を計算すればいいんですが、問題は、V(s) はその遷移先の価値 V(s’) に依存するという無限ループになっていることです。

というわけで、最初は全部の V(s) を適当に予測しておき、修正差異がなくなるまで繰り返し修正していきます（価値反復アルゴリズム）。差異がなくなるというか、閾値ε（エプシロン）以下になるまでですね。

最初の適当な予測として、常にシーケンシャル移動した場合のコストを使います。というわけで t を目的の曲とした場合、状態 s の価値は s-t の絶対値です。

修正する際には、最良のアクションを取った場合にかかる目的地へのコストを、新たな価値として設定します。これはシーケンシャルでは常に s-t。シャッフルでは、シャッフルにかかる時間 T + 着地点の価値 V(r) の平均です。

■価値判断のプログラム
では価値反復アルゴリズムをPHPでコーディングしてみます。iPod Shuffleは最後の曲の次に最初の曲が来るループになっているので、目的地 $target は常にN/2 であるとして考えます。
$n はiPodにある曲の数、
$t は一回のシャッフルにかかる時間、
$epsilon は収束したと判断する閾値です。

function ValueIteration( $n, $t, $epsilon = 0.001 ){
	$target = $N/2;
	$states = range($N);// 0～N-1の配列
	$v1 = array();		// 旧価値
	$v2 = array();		// 新価値
	
	// 適当な予測
	foreach ($states as $state){
		$v1[$state] = abs($state-$target);
		$v2[$state] = 0;
	}
	
	// ここからが反復
	while(true){
		$diffs = array();
		foreach ($states as $state){
			$diffs[$key] = abs($v2[$state]-$v1[$state]);
		}
		if (max($diffs) <$epsilon){
			break;
		} else {
			$shufcost = $t + average($v1);
			$seqcost  = abs($state-$target);
			foreach ($states as $state){
				$v2[$state] = min($seqcost, $shufcost);
				list($v1, $v2) = array($v2, $v1);
			}
		}
	}
	return $v2;
}

以下の細かい関数は省略しています。
range($num): 0～$num-1が入った配列を返す
average($array): 配列の値の平均を返す

list($v1, $v2) = array($v2, $v1) は見慣れない書き方かもしれませんが、$v1と$v2を入れ替えているだけです。

これで、全ての曲について価値が判断できました。

■実行
では上の価値判断に基づいて、当初の問題
・いつシャッフルから通常モードに切り替えればよいのか
・どれぐらい時間がかかるのか
を解決しましょう。
$nは曲数、
$tは一回のシャッフルにかかる時間です。

function ipodshuffle($n=250, $t=5){
	$target = $n/2;
	$values = ValueIteration($n, $t);
	$states = range($n);
	$seqs = array();
	foreach ($states as $state){
		if ($values[$state] == $target-$state){
			$seqs[$state] = $state;
		}
	}
	$solution = $target - min($seqs);
	$average = average($values);
	echo "N={$n}、T={$t}のとき → ";
	echo "{$solution}曲以上離れていたらシャッフル\n";
	echo "かかる時間は{$average}秒ぐらい。";
}

■実行結果
実行するとこんな感じでしょうか。って言っても実際には実行してみてないので動かしたらバグってるかもしれません。値はネタ元からコピーです。

N=250、T=5のとき → 35曲以上離れていたらシャッフル
かかる時間は30.4秒ぐらい。

■結論と感想
というわけで、1GBのiPod Shuffleを持っている人は、シャッフルしてみて35曲以上離れてそうならもう一度シャッフルしてみましょう。もちろん、これは判断5秒での計算なので、もっと早く判断できるならもっと近くに行くまでシャッフルしたほうがお得でしょう。

■何か間違ってそうならツッコんでください。

■あれ、割引率使ってないけどいいのか…？
使うとしたら$diffsの全ての値をγ倍すればいいのかな。

■ネタ元の言語はPythonでしたがPHPで書き直しました。Python便利やなぁ～。
min([s for s in range(N) if V[s] == t-s])
一行でこんだけ書けるとは。

■しかし画面がないと35曲以上離れてるかどうか判断するのって相当難しそうやけども。

■あ、てかおれiPod Shuffle持ってなかった。