« 読了：「ウィンザーの陽気な女房たち」「女のいない男たち」 | メイン | 読了：Jurca & Falting (2008) オンライン自白剤 »
2014年8月 4日 (月)
Faltings, B., Li, J.J., Jurca, R. (2012) Eliciting Truthful Measurements from a Community of Sensors. 3rd International Conference on the Internet of Things.
ベイジアン自白剤について調べていて見つけたもの。仕事とは直接関係ないので、別に読まなくてもいいんだけど、あまりにナナメウエな発想に呆れて、つい目を通した。第三著者のRadu Jurcaさんという方、チューリッヒのgoogleにお勤めらしいのだが、こういう(私から見て)想像の範囲を超えた突拍子もない研究をしていて、気になる人である。
いろんなモノがネットでつながる時代になると、個々人が所有するモノから広く情報を集めて活用したくなる。そういうのをコミュニティ・センシングという。ところが、個々人が正しい値を報告してくれるとは限らない。もしあとで正解がわかるなら、それと突き合せて報酬を渡すこともできるだろうが、ふつう正解はわからない。そこで、真実申告にインセンティブを与えるメカニズム、その名も「ピア自白剤 peer truth serum」を考えました。という論文。
たとえば、大気汚染を測っているセンサーについて考えよう。ある場所と時点において、大気汚染のレベル V がN段階で表現できるとする。すなわち V = {v_1, ... v_N}。
各エージェントは観察 o に基づきレポート s を刻々とセンターに送りつづける。センター側は集めた情報をモデルに入力し(それがどんなモデルかはこの際どうでもよい)、地域 l, 時点 t における汚染がレベルvである確率 R^{l,t}(v) を出力する。
各エージェントは、次の時点でセンターが出力する汚染レベルが v である確率 R^{l, t+1}(v) について、自分なりの信念を持っている。o を測定する前の信念(事前信念)をPr^{l, t}(v), 測定した後の信念(事後信念)を Pr^{l,t}_o (v) とする。以下、上添字 l, t は略記する。
各エージェントがどうやって信念を更新しているのかは問わないが、ベイズの定理に従って、次のような意味で「合理的に更新」していると想定する。
[命題1] Pr_x(x) / Pr(x) ＞ Pr_x(y) / Pr(y)
すなわち、センサーが「あっ汚染度高っぽい！」と観察したとして、「汚染度は高だ」という主観確率は変わるだろうし、ひょっとしたら「汚染度は中だ」の主観確率も変わるだろう。それはどうでもいいけど、「汚染度は高だ」の主観確率の増大率は、「汚染度は中だ」の主観確率の増大率よりも高くなきゃおかしい、という話である。
さて、ピア自白剤の基本的なアイデアは以下のとおり。
事前確率分布 R が共有されているとしよう(←なかなかぴんとこなかったのだが、センターが発表した最新の確率分布だと考えればよいのだと思う)。さらにセンターは、誰かのレポート m を参照値としているとしよう(←これも意味がよくわからなかったのだが、エージェントがそう信じているという点がポイントで、実際に誰の測定値を参照値にしているかはどうでもよい)。
レポート s を報告してきたエージェントに対する報酬を、\alpha + \beta \tau (s, m, R) とする。ただし、\alphaと\betaは正。\tau(s, m, R)は、s=mのときに 1/R(m), それ以外のときに0とする。
つまり、「あなたのレポートsがセンター側の参照値 mと一致しているときのみ、m の共有事前確率に反比例した報酬を払いますよ」というルールである。
これがなぜ真実申告メカニズムなのかというと...
まず、すべてのエージェントの事前信念が、共有事前分布とある程度一致している場合について考えよう。任意のvについての事前信念 Pr(v)の上下±\epsilonの範囲内に、共有されている事前確率 R(v)が入っているものとする。すなわち
Pr(v) + \epsilon ＞ R(v) ＞ Pr(v) - \epsilon
さて、oを観察し s をレポートするエージェントの報酬の期待値は
pay(o, s) = \alpha + \beta \sum_x Pr_o (x) \tau (s, x, R) = \alpha + \beta Pr_o(s) / R(s)
これが真実申告メカニズムであるとは、任意の v について pay(o, o) ≧ pay(o, v) であるということだ。上の式を代入して
Pr_o(v) / R(v) ≦ Pr_o(o) / R(o)
逆数をとって
R(v) / Pr_o(v) ≧ R(o) / Pr_o(o)
左辺分子のR(v)の下限は Pr(v) - \epsilon, 右辺分子の上限はPr(o) + \epsilonだから、この式は
(Pr(v)-\epsilon) / Pr_o(v) ≧ (Pr(o)+\epsilon) / Pr_o(o)
のときに成り立つ。つまり、エージェントの事前信念と共有事前分布 のあいだのずれが \epsilon 未満であれば、ピア自白剤ルールは真実申告メカニズムになる。イエーイ。
この \epsilon の値は単純な算術で求められる。つまり、すべての v, o (v \neq o) において
( Pr(v)Pr_o(o) - Pr(o)Pr_o(v) ) / ( Pr_o(v) + Pr_o(o) )
を求めた、その最小値が \epsilon である。
... ほんまかいな。試してみましょう。いま、大気汚染のレベルが{低, 中, 高}の3段階で、
エージェントの事前信念は{0.2, 0.6, 0.2}
「低」を観察したエージェントの事後信念は{0.6, 0.3, 0.1}
「中」を観察したエージェントの事後信念は{0.1, 0.8, 0.1}
「高」を観察したエージェントの事後信念は{0.1, 0.3, 0.6}
としよう(これは合理的更新である)。計算すると \epsilon = 1/9なので、共有事前分布をたとえば {0.25, 0.5, 0.25} とする(ズレは\epsilon未満におさまっている)。あるエージェントが「低」を観察したとしよう。「低」と報告したら報酬の期待値は 0.6/0.25 = 2.4。「中」と報告したら 0.3/0.5 = 0.6。「高」と報告したら0.1/0.25=0.4。真実申告において期待値最大である。「中」「高」を観察した場合でもそうなる。
さあ、ここからがすごく厄介です。
エージェントの事前信念が共有事前分布と一致しているとは限らない。たとえば上の例で、共有事前分布が{0.5, 0.1, 0.4}だとしよう。エージェントが「低」を観察したとして、「低」と報告したら報酬の期待値は 0.6/0.5 = 1.2, 「中」と報告したら0.3/0.1=3, 「高」と報告したら0.1/0.4=0.25。「低」を観察したにも関わらず、「中」と報告したほうが期待値が大きい。つまり、エージェントは嘘をつく動機を持っている。
ところが... ここでまた呆気にとられたのだけど、著者はこう主張する。こういう場合は「中」と報告してもらったほうがいいのではないか？ だって、エージェントは「現に目の前で交通渋滞が起きている」というような、センターが知らないことを知っているのかもしれないのだから。
真の分布 Q(\dot) を想定する。すべての v において共有事前分布 R(v) よりも事前信念 Pr(v)のほうが真の分布 Q(v)に近いとき、事前信念 Pr (\dot) は"informed"であると呼ぶことにする。
ここの段落、すごくわかりにくいので逐語訳。
こうした場合、公共的なマップ R がなるべく早くプライベートな信念へと収束することがもっともhelpfulだろう。そこで以下では次のことを示す。ピア自白剤はhelpfulな報告にインセンティブを与える。すなわち、必ずしもtruthfulではないやりかたで、公共的なマップを真の分布へと近づけていく報告にインセンティブを与える。
したがって、収束は2つの段階を通じて生じる。
1) まず、さまざまなプライベートな事前分布と、公表されている汚染マップが、同一の分布へと収束し、共通の参照枠を構築する。
2) この参照枠が構築されると、インセンティブはtruthfulな報告に与えられるようになり、公共的マップとプライベートな事前分布が真の分布へと漸近的に収束する。
こうした2段階プロセスはコミュニティ･センシングにとってとても意義あるものである。なぜなら、センサーはふつうシステムにある長い時間にわたって存在し、その初期フェイズはネットワークに参加する際に通過しさえすればよいからである(since a sensor is usually present in the system for an exteded period of time and will only have to pass the initial phase once when joining the network)。
ううむ、なにをいっているのかさっぱりわからない。truthfulな報告とは、客観的真実に近い報告という意味ではなく、観察をそのまま報告するということでしょう？ ピア自白剤がhelpfulかどうかはともかく、ピア自白剤がtruthfulな報告を引き出すとはいえないのではないか？
まあとにかく、ピア自白剤がhelpfulだという説明を追いかけよう。
すべてのエージェントの事前分布がinformedだという想定の下で、次の命題が成り立つ。
[命題2] Pr(a)/R(a) ＞ Pr(b)/R(b) ならば、aを観察したエージェントがbと報告することはない。
証明。あるエージェントが a を観察したとする。このエージェントが「参照値 m は真実である」と信じているとしよう。このときは、aを報告する期待値は Pr_a(a) / R(a)。aを観察してbを報告する期待値はPr_a(b) / R(b)。前者のほうが大きいことは簡単に示せる(略)。したがってこのエージェントはbではなくaを報告する。
では、このエージェントが「参照値 m を報告しているエージェントはなんらかのinformedな事前分布のせいで嘘をついている」と信じていたらどうなるか。この場合でも、そいつがaを観察しているにも関わらずbと報告することはない。だからやはり、このエージェントはbではなくaと報告する。証明終わり。
現在の共有事前分布Rにおいて、エージェントから見て過小評価されている (R(a)＜Pr(a)) 値の集合をA, 過大評価されている値の集合をBとする。informedな事前分布を持っているエージェントについて、次の命題が成り立つ。
[命題3] Bの報告総数は、そのエージェントのPr(b)の和を超えない。
証明。aにおいてR(a)/Pr(a)＜1, bにおいてR(b)/Pr(b) ≧1である。命題2より、Aのなかにはいっている値を観察したエージェントがBのなかの値を報告することはない。したがって、Bの報告総数は、Bの値の真の頻度の和 \sum Q(b) を超えない。このエージェントはinformedだから、\sum Pr(b)は \sum R(b)よりも \sum Q(b)に近い。ということは、\sum Q(b) ≦ \sum Pr(b) ≦ \sum R(b) という順に並ぶ。ということは、Bの報告総数は、そのエージェントのPr(b)の和を超えない。証明終わり。
すでに狐につままれているが、まだ続くぞ！
[命題4] 有限回の更新を通じて、R(b) ＜ Pr(b) + \epsilon, R(a) ＞ Pr(a) - \epsilonである。
証明。命題3より、Bの報告総数はエージェントの事前信念の和を超えない。したがって共通事前確率は次第に減少し事前信念に近づく。逆にAの報告総数はエージェントの事前信念の和以上である。したがって共通事前確率は次第に増大し事前信念に近づく。証明終わり。
というわけで、エージェントがinformedな事前信念を持っていれば、ピア自白剤の下での報告を集積してつくった共通事前分布はその事前信念に近づいていく、というわけである。
ぐぬぬぬぬ。全然納得できない。すごく騙されているような気がするんだけど、どこで騙されたのかわからない。。。
ここで当然の疑問となるのは、エージェントの事前信念がinformedでなかったらどうなるのさ？ という点であるが... 全訳しよう。
プライベートな事前分布がinformedでない場合、こうした収束は生じるかもしれないが保証されない。もっとも、そんな事例は現実的でない。エージェントがセンターの知らない背景情報を持っていたら事前信念はinformedであるはずだし、そうでないならそのエージェントはセンターが示した分布を信じるはずだから。また、これとは別の問題として、エージェントのプライベートな事前分布がinformedではあるがお互いに著しく異なっていたらどうなるか、という問題もある。
どちらの場合にせよ、合理的なエージェントなら、モデルの出力についての彼らの信念を、公表された分布 R へと徐々に近づけていくはずである。したがって、それらはいずれ単一の分布へと収束する。もっともこうした収束は遅すぎるかもしれないが。
ううううむ。そうか？そうなのか？
論文は、このあと簡単な数値例を示し、正解を使ったproper scoring ruleよりも提案法のほうが優れていることを示している。省略。
いやあ、最初から最後まで奇想天外、話がどう転がるか全くわからない論文であった。
そもそも、タイトルにはeliciting truthful measurement と書いてあるけれど、ある報告において真実申告が均衡解になるようなメカニズムを提案しているわけではないのである。
よくわからないんだけど、あるエージェントがものすごく奇妙な、informedでない事前信念を持っていたとして(「日付に３のつく日は大気汚染がひどくなるはずだ、だから空気は綺麗だけど汚染度高って報告しちゃうぞ」とか)、報酬と確率分布Rをフィードバックするということを繰り返したとして、このエージェントが事前信念を修正するという保証はどこにあるのだろうか。合理的なエージェントならばベイズの定理に従う、とはいえるだろう。合理的なエージェントならば各時点における期待効用の最大化を図るはずだ、ともいえるだろう。でも、合理的なエージェントならば報酬のフィードバックの繰り返しを通じて変な外部情報に頼るのをやめてくれるはずだ、といえる理由はあるのだろうか？
まあとにかく、こんな問題と発想があるのかという意味で、大変勉強になりました。
論文：予測市場 - 読了：Faltings, Li, & Jurca (2012) センサーのためのピア自白剤