« 読了：Markos, et al.(2018) 次元縮約とクラスタリングを同時にやりたいあなたのためのclustrdパッケージ | メイン | 読了：Conklin & Lipovetsky (2013) マーケティングリサーチにおけるシャープレイ値の使い道 »
2018年10月18日 (木)
Hong, L., Page, S.E. (2004) Groups of diverse problem solvers can outperform groups of high-ability problem solvers. PNAS, 101(46).
都合で無理やり読んだ論文。集合知の研究で有名な、かのスコット・ペイジさんによる理論論文である。身の程知らずにもほどがあるのだが...
(イントロ)
集団の問題解決において集団内の多様性が大事だといわれるのはなぜか。
多くの人がこう考えている。デモグラフィック属性とか文化・エスニシティとか熟達とかの点で多様性がある集団は(これをアイデンティティ多様性と呼ぼう)、問題を表現し解決する方法においても多様性を持っているので(これを機能多様性と呼ぼう)、問題解決のパフォーマンスが高くなる。
では、機能多様性がパフォーマンスにつながるのはなぜか。個々人の能力が低くても、機能多様性があれば、優秀な奴らに勝てるのか。
これを説明する数学的枠組みを提案する。
多様な問題解決者のモデル
解集合$X$を実数値にマッピングする関数$V$があり、この関数の最大化を目指す問題解決者の集団があるんだけど、ひとりひとりの能力は限られている、としよう。たとえば、$X$はエンジンのデザインの可能な集合で、$V$はエンジンの効率性である。
問題解決者たちは内的な言語を持っており、それによって解をエンコードする。ここでいう内的な言語というのは、脳が情報を知覚し貯蔵する神経科学的仕組みだと思ってもよいし、我々が経験と訓練に基づき問題を解釈する仕組みを比喩的に指しているのだと思ってもよい。
この内的言語による解の表現をパースペクティブと呼ぼう。つまり、パースペクティブとは解集合とエージェントの内的言語とのマッピング$M$である。
問題解決者は解を探索する。その探索の仕方を表すために、ある問題解決者が、自分の内的言語で表現された解集合を、解の下位集合へとマッピングするヒューリスティクスを持っていると考え、このマッピングを$A$とする。つまり、問題解決者が検討するのは、$A$によって生成された解の下位集合だけである。
というように考えると、あるエージェントの問題解決能力とは、パースペクティブとヒューリスティクスのペア$(M, A)$である。エージェントが2人いたら、$M$も違うかもしれないし$A$も違うかもしれない。
[←よくわからん。$M$はその人が内的に表象しうるすべての解の集合を生成するマッピングで、$A$はその人が実際に検討する下位集合を生成するマッピングだよね？ $A$で生成された下位集合のなかでどれがいいかを選ぶ能力ってのはないかしらん。解の評価は自明であって、探索さえすればいいという設定なの？ ここではきっとそうなんだろうな]
あるエージェントが問題をエンコードし、ヒューリスティクスを適用し、検討した解のなかで解を選び、選んだ解より高い値を持つ解が検討した集合の中にないとき、選んだ解を局所最適解と呼ぶ。あるエージェントの持つ局所最適解の集合、そしてそのbasins of attractionのサイズが、そのエージェントの能力であるといえるだろう。
[←basins of attractionというのがよくわからん。$A$が生成した解の下位集合のサイズのこと？それとも、$M$が生成しうる解の集合のうち、なんといえばいいんだろうか、後になって「無視してはいなかった」といえるような範囲のこと？]
エージェントの集団が手に入れる解は、個々のエージェントの局所最適解の共通部分に位置する解だけである。このことは、エージェントがチームとしてともに働く手順とは独立に成り立つ。しかし、相互作用の手順がちがえば、すべてのエージェントにとって局所最適解となる解のbasins of attractionも変わってくる。だから、チームの働き方はパフォーマンスに影響する。
計算実験
整数$\{1,\ldots,n\}$を実数に変換するランダム値関数について考える。実は、値は$[0,100]$の一様分布から独立に抽出されている。
エージェントはこの関数を最大化する値を見つけようとする。どのエージェントも、$n$個の解を、円周上に時計回りに並ぶ$n$個の点としてエンコードする(つまり、パースペクティブは皆同じ)。
個々のエージェントは、現在位置の右にある$l$個の点のなかの$k$個をチェックする。そのヒューリスティクスは$\phi = (\phi_1, \ldots, \phi_k)$ ただし$\phi_i \in \{1,\ldots,n\}$で表される。
例を挙げよう[←はい、さっさとそうしてください]。$n=200, k=3, l=12$とする。あるエージェントのヒューリスティクスが(1,4,11), 開始点は194であるとする。このエージェントは
- まず194番の値と194+1=195番の値を比べる。194番のほうが高かったとしよう。
- 194番の値と194+4=198番の値を比べる。198番のほうが高かったとしよう。
- 198番の値と、198+11=209番、すなわち(一周200個なので)9番の値を比べる。9番のほうが高かったとしよう。
- 9番の値と9+1=10番の値を比べる...
- というのを繰り返し、現在位置より高い値がみつからないのが3回続いたらストップする。
あるヒューリスティクス$\phi$のパフォーマンスは、始点$i$のときに到達する停止点を$\phi(i)$として、
$E[V, \phi] = \frac{1}{n} \sum_i^n V[\phi(i)]$
である。$k, l$が決まれば、ヒューリスティクスの集合が決まる。
ここから実験。
ここでは、$l = 12, k=3, n=2000$の結果を報告する。すべてのヒューリスティクスについてパフォーマンスを求めておき、最優秀な10個のエージェントの集団と、ランダムに選んだ10個のエージェントの集団をつくる。
で、エージェントの集団に解を探させる。エージェント1番が解を探し、2番はそこからまた解を探す。順繰りにずっと繰り返して、誰も新しい解を見つけられなくなったらストップ。
結果。ランダム集団のほうが成績が良い。集団内のヒューリスティクスの多様性をみると($\phi$の異同を総当たりで数える)、ランダム集団のほうが多様である。20エージェントに増やすと、成績の差も多様性の差も小さくなる。$l=20$にすると(多様性が高くなりやすくなる)、ランダム群の多様性は実際に高くなり、また成績も上がる。
[いやぁ... 私が素人だからかもしれないけれど、セッティングが抽象的すぎて、「うまいこと騙されている」感が拭えない。まあこれはデモンストレーションで、本題はここからなんでしょね]
数学的定理
エージェントの母集団を$\Phi$とする。以下を想定する。
- エージェントは知的である。すなわち、あるエージェントは、所与の開始点から、weekly betterな解をみつける[←頭のいい人は難しいこと言うから嫌いだよ... 他の解と同等かそれ以上な解を見つけるってことであろう。局所解の集合は列挙可能である。
- 解は難しい。すなわち、「いつも最適解を見つけちゃうエージェント」はいない。
- エージェントは多様である。すなわち、いまここに最適でない解があったら、それよりも良い解を見つけうるエージェントが少なくとも一人は存在する。[←えっ...それ結構強い仮定じゃない...?]
- 最良のエージェントは一意に決まる。
これから次の定理を示す。$\Phi$からエージェントを、なんらかの分布に従って抽出するとき、$N$人を抽出したなかからさらに個人レベルで最良の$N_1$人を選んでつくった集団のパフォーマンスより、最初から$N_1$人を抽出してつくった集団のパフォーマンスのほうが良くなるような$N_1$と$N$($N_1 < N$)が、確率1で存在する。
[と、ここから数学の話になる... 頑張って読み始めたんだけど、気が狂いそうになったので断念。人の頭にはですね、それぞれの限界というものがあるのです]
[2018/11/30追記: この部分はあとでメモを取った]
結語
本論文では、知的問題の解決において、最良の問題解決者からなる集団より、ランダムに選ばれた問題解決者からなる集団のほうがパフォーマンスが良くなる条件を示した。
理想の集団は有能かつ多様な集団だが、問題解決者のプールが大きくなるほど、最良の解決者はどうしても似てくる。
なお、集団が小さすぎるとランダム集団はうまくいかない(局所最適解がたまたま共通してしまうから)。また集団が大きいときには有能集団も多様性が生じてパフォーマンスが上がる。
今後の課題: コミュニケーションコストの考慮、学習の考慮。
... いやー、難しくて死ぬかと思たがな。
この論文、ペイジさんの主著"The Difference" (2007) (邦訳「多様な意見はなぜ正しいか」)の8章の説明があまりに回りくどく、素人向けやからとゆうてこれはないやろ、ええ加減にせえよ、と腹を立て、探して読んでみた次第である。 先生すいませんでした。おとなしくご著書を読みますです。
論文：予測市場 - 読了：Hong & Page (2004) 平凡な人々のグループが賢い人々のグループよりも賢くなるメカニズム