iPod Shuffleでマルコフ決定過程
iPod Shuffleで目的の曲まで素早くたどり着く合理的な方法をマルコフ決定過程で実現するという、キモチワルーイ記事がありました。
マルコフ決定過程は最近授業で習ったので、復習も兼ねて解説してみます。うまく解説できていたら拍手してください。
まず基礎知識として、
・Shuffleは画面がないので基本的に手探り
・シャッフルモードと通常モードがある
・この方法は面白いけど実用的じゃない
以上を把握しておきましょう。
■考え方
iPod Shuffleで、たとえば Keith Jarrett の The Song Is You を聴きたいとします。でも今 Art Farmer を聴いてるから、Kまで行くにはボタンをバシバシ押さなくてはいけない。というわけで、
- シャッフルモードで何回かジャンプし、
- ある程度目的の曲に近いところに着地したら、通常モードに切り替える
という戦略で、素早く目的の曲にたどり着こうという話です。
問題は２の「ある程度」。じゃあ実際どれだけ近づいた時点で通常モードに切り替えるのが最適なのか、そして平均どれだけ時間がかかるのか、を解明してみましょう。
■言葉の定義
まず次の５つの言葉を定義します。
「状態」
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持ってなかった。
CodeIgniterが急激にいやになってきた
新しいアプリをCodeIgniter（略してCI）で作ろうとしている。
構成が分かりやすく拡張もしやすかったのですばらしい第一印象を受けて、これならスラスラ作れそうだと思っていたが、しばらく作業をしてみると徐々に気に入らない部分が見えてきた。
ParserがSmartyじゃない
テンプレートの中で変数を使うためにいちいち< ?php ～ ?>を書いていると可読性が著しく下がるため、パフォーマンスが犠牲になるとはいえ僕としてはSmartyのようなテンプレートエンジンを使いたい。（これに関しては初めから分かっていたし独自ライブラリを作ったので今は問題ない。）
セッションをクッキーに直書きする
見たときは目を疑った。PHPのセッションデータはふつうセッションID（鍵）だけをクッキーに保存し、データ自体はサーバー側に保存するのだが、CIではシリアライズしたデータそのものをクッキーに保存していた。データベースを使うオプションもあるがそれでもデータはクッキー。従って保存できるデータ量が限られる。（これも独自ライブラリで修正したが、かなり大掛かりな作業になった。）
セッションを読み書きするメソッド名が長い
get()とset()にすればいいものを、userdata()とset_userdata()などという面倒臭いメソッド名がついているから、わざわざ自分でエイリアスを書いた。
バリデーションがダサい
ここは特に問題が多い。
まずライブラリのメソッドの中身に「$_POST」がハードコーディングされているため、任意の変数をバリデートできない。なぜこんな仕様になっているのか理解に苦しむ。柔軟性を考えると（というか何も考えなくても）普通に引数で取るしかないと思うのだが。
そして、任意のエラーをあとから手動で追加するメソッドが用意されていないから、わざわざ自分でメソッドを書くはめになる。
そして、エラーメッセージを変数で取得するとデフォルトで<p>～</p>に囲まれて来るという驚きのダサさを発揮してくれる。
そして、ルールを設定するためのコードが可読性の低いものになる。
正直、これは使い物にならない。こうしてみるとEthnaのバリデーションはよくできていたと思う。
i18nクラスを呼び出すときの名前がバラバラ
状況によってLangだったりLanguageだったりする。非常に分かりにくい。
何かを取得するメソッド名がバラバラ
クラスによって。たとえば$config->item(’key’)、$lang->line(’key’)、$session->userdata(’key’)。同じネイティブライブラリなんだから全部get()とかにしてくれ。
同じライブラリを二度呼び出すと死ぬ
たとえばバリデーションライブラリを呼び出すときは
$this->load->library('validation');となる。これ自体は大変分かりやすくていいのだが、何らかの都合でこれと同じ行が二度目に出てくると、単純にクラスの再宣言ということでエラーが出て倒れる。ものすごく簡単に防げるはずだが、それがないために場合によってはものすごく不便だ。
今のところはこんなものだがまだ増える予感がする。
さてどうしよう、ここまで手を加えたからには粘って使うべきか、それとも見切りをつけて別のフレームワークへ行くべきか…。