Hatena::Grouptumblr

saitamanodoruji

くこかー
saitamanodoruji.tumblr.com
 | 

2013-07-25

Exponential Endless Summer を改訂しました (version 2013)

06:15 | Exponential Endless Summer を改訂しました (version 2013) - saitamanodoruji を含むブックマーク はてなブックマーク - Exponential Endless Summer を改訂しました (version 2013) - saitamanodoruji

要旨

  • もっとランダムに Post ID を選べるようになりました.
  • 2010-11-30 が選ばれやすい現象が起きないようになりました.

JavaScript のコードは記事の最後に載せてあります.

Exponential Endless Summer とは

Exponential Endless Summer (EES) は Tumblr の Post ID をランダムに選ぶためのスクリプトです*1. Post ID の選び方が時間に関して等確率になるような機能を比較的少ないパラメータ*2で実現できます.

方法

EES は Post ID の上限と下限を引数として受け取り, その間から 1 つの Post ID を選び出します. この動作のために EES は 2 つの関数を必要とします. 初めにこれらの関数を準備します.

まず, Unix time  t \[msec\] 対 Post ID N のデータ*3t に関して n 個の区間に分割し, それぞれの区間についてデータに指数関数でフィッティングをかけて

f(t) = \{A_1 \exp(B_1t)\hspace{10}{\text{\rm{if} \it{t} \leq \it{t_1}}}\\{A_2 \exp(B_2t)\hspace{10}{\text{\rm{if} \it{t_1} < \it{t} \leq \it{t_2}}}\\{\hspace{20}\cdots}\\{A_n \exp(B_nt)\text{\hspace{10}\rm{if} \it{t_{n-1}} < \it{t}}}\hspace{30}\cdots\hspace{10}(1)

という関数を求めます. 境界値  t_i は原則として  f_i(t_i) = f_{i+1}(t_i) を満たすよう選びます*4. 例外は Post ID が不連続的に増加している場合 *5です. 必要なパラメータは 3n - 1 個です.

Fig. 1 Exponential Endless Summer の動作

http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130725/20130725045432_original.png

次に, 逆関数 t = f^{-1}(N) を (1) 式から次のように求めておきます.

f^{-1}(N) = \{{\frac{1}{B_1}\ln{\frac{N}{A_1}}\hspace{10}{\text{\rm{if} \it{N} \leq f(t_1)}}}\\{\frac{1}{B_2}\ln{\frac{N}{A_2}}\hspace{10}{\text{\rm{if} f(t_1) < \it{N} \leq f(t_2)}}}\\{\hspace{20}\cdots}\\{\frac{1}{B_n}\ln{\frac{N}{A_n}}\hspace{10}{\text{\rm{if} f(t_{n-1}) < \it{N}}}}\hspace{30}\cdots\hspace{10}(2).*6

EES は ff^{-1} を用いて, 以下の手順で Post ID を選びます (Fig. 1).

  1. Post ID の上限 N_{newest} と下限 N_{oldest}f^{-1} によって Unix time t_{newest}, t_{oldest} に変換する
  2. Math.random()t_{drawn} (t_{oldest} \leq t_{drawn} \leq t_{newest}) を選ぶ
  3. f を用いて t_{drawn} を Post ID N_{drawn} に変換する

去年のバージョンとその問題点

Fig. 2 Exponential Endless Summer 2012

http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130723/20130723052059_original.png

去年のバージョン (EES2012) ではデータを 2 つの区間に分割しました (n=2). それから 1 年ほどの間に Post ID の増え方が f_2(t) からかなり外れてきていて (Fig. 2), その影響で 2012-06 以降のポストは選ばれにくくなっています.

また特定の日付 (2010-11-30, 2010-12-13) が選ばれやすい現象も問題でした.

EES2013

今回はデータを 10 の区間に分割してフィッティングを行いました (n=10) (Fig. 3 left). 特に 2010-11-30, 2010-12-13 周辺については, これらの日付が選ばれやすい現象が起こらないように細かく分割しています (Fig. 3 right).

Table 1 にフィッティングパラメータをまとめました. f_5f_6 の境界である t_5 及び f_6f_7 の境界である t_6 には Post ID の不連続的な増加が存在する時刻を使っています.

Post ID の不連続的な増加は以下のような URL で確認できます. Dashboard では permalink の title 属性値に時刻が記載されています.

Fig. 3 Exponential Endless Summer 2013. (left) 全体図 (right) 2010-11 付近の拡大図
http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130723/20130723055505_original.png http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130723/20130723090539_original.png

Table. 1 EES2013 のフィッティングパラメータ. フィッティング関数は  f_i(t) = A_i \exp(B_it),\hspace{10}{\text{\rm{if} \it{t_{i-1}} < \it{t} \leq \it{t_i}}.

iA_iB_it_it_i の決め方t_i の日付
12.374E-2685.342E-101182114958836f_i = f_(i+1) となる t2007-06-18T06:15:58+09:00
22.292E-631.349E-101193135035175f_i = f_(i+1) となる t2007-10-23T19:23:55+09:00
31.214E-113.509E-111241622616806f_i = f_(i+1) となる t2009-05-07T00:10:16+09:00
41.259E-225.546E-111283088065116f_i = f_(i+1) となる t2010-08-29T22:21:05+09:00
53.805E-296.716E-111291075200000Post ID の不連続点2010-11-30T09:00:00+09:00
65.579E-286.521E-111292241600000Post ID の不連続点2010-12-13T21:00:00+09:00
74.482E-286.541E-111307576237375f_i = f_(i+1) となる t2011-06-09T08:37:17+09:00
82.424E-286.588E-111313586050187f_i = f_(i+1) となる t2011-08-17T22:00:50+09:00
93.923E-133.922E-111340572542928f_i = f_(i+1) となる t2012-06-25T06:15:42+09:00
102.157E-032.249E-11

ランダムさの評価

Endless Summer (taizooo's mod), EES2012, EES2013 の 3 つの手法を用いてそれぞれ 10000 回の Post ID 選択を行い, 引いた Post ID を元に Dashboard ( http://www.tumblr.com/2/{PostID} ) を開き, その一番上のポストの日付を記録して, 引いた回数を月毎に集計して作ったヒストグラムが Fig. 4 です. Dashboard が空だった場合にはそのデータは捨てています. Dashboard の取得に使ったアカウントの following を gist-6110816 に置きました *7.

EES2012 (Fig. 4b) の問題点であった最近のポストが選ばれにくい現象と 2010-11 のポストを選びやすい現象が EES2013 (Fig. 4c) では解消されています. また, 年末のポストがより選ばれやすい taizooo's mod (Fig. 4a) と 2007 年後半及び 2009 年から 2011 年にかけてのポストが選ばれやすい EES2012 に比べて, EES2013 は各月の選ばれる確率に偏りが少ないこともわかります.


Fig. 4 三種類の Endless Summer で引いた Post ID のヒストグラム. (a) taizooo's mod (b) EES2012 (c) EES2013
http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130724/20130724041516_original.png http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130724/20130724040830_original.png
http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130724/20130724040831_original.png

Unix time - Post ID 変換の精度の比較

Fig. 5 EES2012 と EES2013 の \Delta t = t_{dsbd} - t_{drawn} の分布の比較. サンプル数はそれぞれ 10000, 階級は日単位.

http://cdn-ak.f.st-hatena.com/images/fotolife/s/saitamanodoruji/20130725/20130725034929_original.png

EES2013 では Unix time - Post ID 変換の精度が上がりました.

10000 回の Post ID 選択をやって得たデータから \Delta t = t_{dsbd} - t_{drawn} のヒストグラムを作ったのが Fig. 5 です. ここで  t_{drawn} はランダムに選んだ Unix time, t_{dsbd}N = f(t_{drawn}) に対応する Dashboard (http://www.tumblr.com/dashboard/2/N) を開いたときに一番上にあるポストの Unix time です (Fig. 1).

つまり, ある Unix time tDashboard が見たいと思って EES2013 の f(t) を使ったときに, 実際に開かれた DashboardUnix time t_{dsbd}t からどれくらいズレているのかというのが \Delta t です.

\Delta t が 10 日以内である確率は約 95 %, 5 日以内である確率は約 67 % でした. \Delta t の分布は following によって変わるはずですが, ある程度 following が多ければ (Dashboard に表示される単位時間あたりのポスト数が多ければ) この値に近くなると思います.

コード

draw() に Post ID の下限と上限を与えると, その間からひとつ Post ID を選んで返します. http://www.tumblr.com/dashboard/2/{PostID} を開く場合には, Post ID がだいたい 700000 より小さくなるとポストが表示されない場合が出てくるので, 空の dsbd を開きたくない場合にはそのあたりを下限に設定するのが良いと思います. 個々のアカウントの following の状況によって Dashboard が空にならない最小の Post ID (Dashboard の底) が違うと思うので, それを調べて下限に設定するのが良いと思います*8.

getPostIDFromUnixTime(utime)f(t) に, getUnixTimeFromPostID(postID)f^{-1}(N) に対応しています.

// Exponential Endless Summer 2013
var draw = function(oldestID, newestID) {
  var oldestUTime = getUnixTimeFromPostID(oldestID);
  var newestUTime = getUnixTimeFromPostID(newestID);
  var drawnUTime = oldestUTime + Math.floor((newestUTime - oldestUTime) * Math.random());
  return getPostIDFromUnixTime(drawnUTime);
}

var getPostIDFromUnixTime = function(utime) {
  if (utime < 1149465600000) {
    return;
  } else if (utime === Number.POSITIVE_INFINITY) {
    return Number.POSITIVE_INFINITY;
  }
  for (var i = 0; i < params.length; i++) {
    if (utime <= params[i].upperBound) {
      return Math.ceil(params[i].coefA * Math.exp(params[i].coefB * utime));
    }
  }
}

var getUnixTimeFromPostID = function(postID) {
  if (postID < 1) { return; }
  for (var i = 0; i < params.length; i++) {
    if (postID <= getPostIDFromUnixTime(params[i].upperBound)) {
      return Math.floor(Math.log(postID/params[i].coefA)/params[i].coefB);
    }
  }
}

var params = [
  // f_i(t) = A_i * exp(B_i * t)
  {coefA: 2.374 * Math.pow(10, -268), coefB: 5.342 * Math.pow(10, -10), upperBound: 1182114958836},
  {coefA: 2.292 * Math.pow(10, -63), coefB: 1.349 * Math.pow(10, -10), upperBound: 1193135035175},
  {coefA: 1.214 * Math.pow(10, -11), coefB: 3.509 * Math.pow(10, -11), upperBound: 1241622616806},
  {coefA: 1.259 * Math.pow(10, -22), coefB: 5.546 * Math.pow(10, -11), upperBound: 1283088065116},
  {coefA: 3.805 * Math.pow(10, -29), coefB: 6.716 * Math.pow(10, -11), upperBound: 1291075200000},
  {coefA: 5.579 * Math.pow(10, -28), coefB: 6.521 * Math.pow(10, -11), upperBound: 1292241600000},
  {coefA: 4.482 * Math.pow(10, -28), coefB: 6.541 * Math.pow(10, -11), upperBound: 1307576237375},
  {coefA: 2.424 * Math.pow(10, -28), coefB: 6.588 * Math.pow(10, -11), upperBound: 1313586050187},
  {coefA: 3.923 * Math.pow(10, -13), coefB: 3.922 * Math.pow(10, -11), upperBound: 1340572542928},
  {coefA: 2.157 * Math.pow(10, -3), coefB: 2.249 * Math.pow(10, -11), upperBound: Number.POSITIVE_INFINITY},
]

使用例

http://saitamanodoruji.tumblr.com/exponentialEndlessSummer2013 にテストページを作りました.

GreasemonkeysharedObject を持たせていて, sharedObject.AutoPagerize.filter が使える環境があれば gist:2931824 にある Endless Summer on dsbd for Greasemonkey を試してみてください.

(追記: taizooo さんが bookmarklet 版 Endless Summer に EES2013 を入れてくれました. endless summer on dsbd - Hatena::Let)

(追記: mamemomonga さんが reblog machine 開発版に搭載してくれました. reblog machine開発版)

今後

来年も夏が始まる頃に見直せるといいかなと思っています. 梅雨明けと競う感じで.

(2013-07-31: ランダム選択のデータを集めた方法に関する記述を追加, \Delta t の分布に関する記述を追加, Post ID の下限の推奨値に関する記述を修正.)

*1:Endless Summer on dsbd の起源は http://taizooo.tumblr.com/post/60322576 .

*2:スクリプトに月毎の Post ID のデータを持たせると 2006-06 から 2013-07 までで 86 個のパラメータが必要になる. 今回のスクリプトが用いているパラメータは 29 個なのでそれよりは少ない.

*3:今回用いたデータは https://gist.github.com/saitamanodoruji/5883517 に置いた.

*4:2012 年のバージョンではこれが満たされてないので, Post ID に選ばれない区間ができてしまっていて良くなかった.

*5:2010-11-30, 2010-12-13 がこれにあたる.

*6:f(t) に不連続点がある場合には f^-1(N) は単射じゃないからその場合逆関数って呼んじゃいけない気がする. それから f^-1(N) は f(t) の不連続点に対応する部分を直線で補完しないと N = f{f^-1(N)} が満たされない場合が出てくるけど, これによる不具合は特に出ないと思うのでやってない.

*7:following を 400 以下にして david の最初のポストまで Dashboard で見えるようにしておけばよかった. Dashboard にポストの抜けがあるせいでヒストグラムの左端に近い部分が見えていない.

*8:このとき following が多いと Dashboard に表示されないアカウントができてポストの抜けが生じるので Dashboard の底が時間によって変化するはず. 2008 年 7 月の時点で Dashboard に抜けができない following の上限は 400 で順次増やすという公式な回答があったけど, いま自分のメインアカウントが following 458 で抜けがあるのであまり増えてないか 400 のままじゃないかと思う.

 |