読了: Hsu, Martin, Sanborn, & Griffiths (2019) 人間MCMC・離散バージョン

Hsu, A.S., Marting, J.B., Sanborn, A.N., Griffiths, T.L. (2019) Identifying category representations for complex stimuli using discrete Markov chain Monte Carlo with people. Behavior Research Methods, 51, 1706-1716.

 最近は仕事の都合で、朝から晩までMCMCのことばっかり考えているんだけど、本論文はSanborn & Griffiths (2007) の後続論文。彼らが考案した測定手法・人間MCMCに焦点を当てた解説論文である。
 掲載誌は、私が院生の頃はBRMICという誌名で、結構トンチキなのが平気で載っていたものであったが… 立派になったねえ…

 いわく…
 [イントロのメモは省略するけど、ビッグデータの時代にはデータに人力で正しくアノテーションをつけることが大事になる、とかなんとか。そうきたか]
 計算機科学・統計学にMCMCという手法があって、複雑な確率分布からサンプルを得るのに使う。Gilks, et al.(1996)を読んでください。人気があるのはM-Hアルゴリズム。現在状態を\(x\)として、提案分布\(q(x’, x)\)から次の状態\(x’\)をドローしてきて、なんらかの受容関数によって受容するかどうかを決める。
 我らが人間MCMC(MCMCP)の核心にあるアイデアがこれ。刺激\(x\)がカテゴリ\(c\)のメンバーだと知覚される程度を\(p(x|c)\)として、受容関数を$$ P_{choice}(x’; x|c) = \frac{p(x’|c)}{p(x’|c) + p(x|c)} $$ とする。これはMCMCでいうところのBarker受容関数と等価になる。いっぽう上の式はかの有名なLuce選択ルールであって、人間の選択データによくあてはまっている。
 というマルコフ連鎖でもって、ヒトが持っているカテゴリがわかります。詳しくはSanborn et al.(2010)をみてねー。

 さて、これを大きなデータセットに当てはめようとすると新しい問題が生じる。提案分布は、現在状態を所与として提案状態を得る確率とその逆とが等しくないといけない。そりゃまあ、刺激が固定されたパラメータ集合で記述されるんなら、そういう連続分布なり離散分布なりを作るのは楽ですよ。でも画像とか文章とかだったらどうすんだよという話である。
 そこでご提案しましょう!離散人間MCMC(d-MCMCP)です!

 まず、刺激のデータベースをつくる。
 次に、刺激の対称的な類似度行列\(S\)をつくる。ラフなもので良い。
 この類似性を使って刺激のグラフをつくる。fully connected、free of closed cyclesで、aperiodicなものにすること。そうすれば、長い目で見ればマルコフ連鎖は定常分布に収束する。\(S\)の出来は効率性にしか影響しない。
 具体的に言うと、グラフはエッジが双方向でノード次数がすべて同じであればよい。形式的に書くと、隣接行列を\(G\)として、\(\sum_{ij} G_{ij} = b, G_{ii} = 0, G_{ij} = G_{ji}\)という制約の下で\(\sum_{ij} G_{ij} S_ij \)を最大化する\(G\)を求めれば良い。こういうのを最大ウェイトb-マッチング問題と言って、すでに正確アルゴリズムとか近似アルゴリズムとかがある。
 提案分布はいろいろありうる。一番シンプルなのは\(b\)個の近隣に一様に行くという奴。あるいは反復幾何提案分布というのを使っても良い。これは、パラメータを固定した幾何分布から\(n_{geom}\)をドローし、ステップ数\(n_{geom}\)の移動をするというもの(行き先は\(b\)個の近隣から一様に選ぶ)。探索が広くなり局所最大から逃げられる。[←へー。イテレーションごとに\(n_{geom}\)ステップだけランダムウォークするというアイデアだと思うけど、これ、あるイテレーションのなかで戻るのはありなんだろうか、それとも必ず\(n_{geom}\)ステップ先に行くべきなんだろうか。わざわざステップ数を幾何分布で決めているんだから、きっと後者なんだろうな]

 実験を3つ報告する。

 実験1、顔画像の分類。
 被験者は学生60人。1271枚の顔画像データベースを使う。EkmanのFACSの分類がついている。
 類似性行列をつくって[よくわからんがなにかをPCAにかけて上位成分のユークリッド距離をとったそうだ]、最大ウェイトb-マッチング問題の近似アルゴリズムでグラフをつくった。次数は6と16。
 提案分布として次の3つを試した。[ちょっとびっくりした。意外に好き勝手に決めていいんですね…]

  • 90%の確率で、6次のグラフ上での一様ランダムウォーク。10%の確率で一様分布。
  • 90%の確率で、16次のグラフ上での一様ランダムウォーク。10%の確率で一様分布。
  • 90%の確率で、6次のグラフ上での幾何提案分布。10%の確率で一様分布。

 [面倒なので手続きは読み飛ばしたけど、要するに、画像が2枚出てきてhappyなほうを選ぶというのを繰り返すんだと思う。ひとりが1本のMCMC連鎖をつくることになる。25分かかったそうだ]
 結果… [読んでないけどなんかいろいろ分析している模様]

 実験2. [ちゃんと読んでないけど、どっちの単語がmoralityと関係してますか、という課題らしい。提案分布は次数10のグラフ上の一様ランダムウォーク。被験者の政治的立場によって結果が違うんだってさ]

 実験3. [これもちゃんと読んでないけど、風景写真の季節判定らしい。類似性は色ヒストグラムからつくっていて、乱暴で笑ってしまったが、要するにその上を歩くと既約で非周期で可逆なマルコフ連鎖になるようなグラフでありさえすればなんでもよくて、似てない状態同士がつながっていてそれほど問題ないのだろう。提案分布は次数5のグラフ上での一様ランダムウォーク]

 結論. [略]
————–
 いやあ、楽しいですね。25分間延々キーを押し続ける羽目になった学生さんたちには同情するけどさ。