Oddwit

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持ってなかった。