« 2018年10月 | メイン | 2019年1月 »
2018年11月27日 (火)
ここからの話のあらすじ
ある価値関数の最大化を図る多数のエージェントについて考える。以下のように仮定する。
- エージェントは知的である。すなわち、あるエージェントは所与の開始点からweekly betterな下位を見つける[他の解と同等かそれ以上に良い解という意味であろう]。局所最適解は列挙できる。
- 問題は難しい。「常に最適解を見つけるエージェント」は存在しない。
- エージェントは多様である。最適でないいかなる解についても、それよりも良い解を見つけるエージェントがひとつは存在する。
- 最良のエージェントは一意に決まる。
この仮定の下で、次のことを示す。エージェントの母集団$\Phi$から、なんらかの分布に従ってエージェントを独立に抽出したとき、$N_1$個のエージェントの集団的パフォーマンスが、$N$個のエージェントのなかの$N_1$個の最良なエージェントの集団的パフォーマンスを上回るような、標本サイズ$N_1$と$N$ ($N_1 < N$) が確率1で存在する。
本編
解の集合を$X$とし、価値関数を$V: X \rightarrow [0,1]$とする。この価値関数は値$x^*$においてユニークな最大値$V(x^*)=1$をとるものとする。[原文: which has a unique maximum at $x^*$. つまり$x^*$はひとつだけってことだと思うんだけど、合っているかしらん]
個々のエージェントは確率分布$v$とマッピング$\phi: X \rightarrow X$で特徴づけられるとしよう。エージェントは、$X$からある確率分布$v$に従って初期値を抽出し、そこから探索をはじめる。初期値$x$から探索を開始したときに落ちる局所最適解を$\phi(x)$とする。つまり探索は決定論的で、スタート地点が決まれば停止地点も決まる。
あるエージェントが持つマッピング$\phi$は次の仮定を満たさなければならない。
- (i) $X$に属するすべての$x$について、$V(\phi(x)) \geq V(x)$
- (ii) $\phi(\phi(x)) = \phi(x)$
[あ...これって「エージェントは知的だ」って言ってるのかな]
解の集合$X$は有限加算でもいいし連続でもいいんだけど、話を簡単にするために有限だということにしておく。
エージェント$(\phi, v)$のパフォーマンスを、その探索の期待値
$E(V; \phi, v) = \sum_{x \in X} V(\phi(x)) v(x)$
とする。
分析の都合上、すべてのエージェントが同じ$v$を持ち、$v$はfull supportを持つとする[また難しいことをいうね... 解集合$X$を通じた和が1ということだろうか]。
エージェントの集合$\Phi$について定義しよう。
- 仮定1: 困難性. $\Phi$に属するすべての$\phi$について、$\phi(x) \neq x^*$であるような$x$が$X$のなかに存在する。
- 仮定2: 多様性. $X \backslash \{x^*\}$に属するすべての$x$について、$\phi(x) \neq x$であるような$\phi$が$\Phi$のなかに存在する。
- 仮定3: 一意性. $argmax\{E(V; \phi, v): \phi \in \Phi\}$はユニークに決まる。
仮定2が云っているのは、いまあるエージェントがスタックしたとしても、別のアプローチでそこからさらに改善できる他のエージェントが、母集団には必ず存在する、ということである。
ある集団がスタックするのは、その集団の全てのエージェントが局所最適解に落ちた時だと仮定する。そのほかに、エージェントの集団が協働する方法については特に仮定を置かない。協働する方法の例としては、エージェントがひとつづつ系列的に問題にアプローチするという方法が挙げられる(あるエージェントがスタックしたら、次のエージェントはその地点から探索を始める)。
さて、ここからは、
- (1)$\Phi$から確率分布$\mu$($\Phi$においてfull supportを持つ)に従って$N$個のエージェントを独立に抽出し、
- (2)これを性能$E(V; \phi, v)$で並び替え、上位から$N_1$個のエージェントを得ておき、
- (3)再び$\mu$に従って、$\Phi$から$N_1$個のエージェントを独立に抽出し、
- (2)の$N_1$個の同時パフォーマンスと、(3)の$N_1$個の同時パフォーマンスとを比べる。
このとき、次の定理が成り立つ。
定理1. 仮定1-3を満たすエージェントの集合を$\Phi$とし、$\Phi$を通じてfull supportを持つ確率分布を$\mu$とする。このとき、確率1で、以下の特性を持つ経路(sample path)が存在する。すなわち、$\mu$に従って$\Phi$から独立に抽出された$N_1$個のエージェントの同時パフォーマンスが、$\mu$に従って$\Phi$から独立に抽出された$N$個のエージェントのなかの優れた$N_1$個のエージェントの同時パフォーマンスを上回るような、正整数$N, N_1$ ($N > N_1$) が存在する。
補題とその証明
定理1について証明するために、まず以下の補題1を導入する。
上で述べた(1)(2)と(3)は互いに独立なランダム事象である。
ここでは(3)に注目しよう。その経路を固定して$w_1$とし、最初の$n_1$個のエージェントを$\phi^1(w_1), \ldots, \phi^{n_1}(w_1)$とする。
こいつらの同時パフォーマンスは、こいつらが共有する局所最適解を$\tilde{y}$として、$V(\tilde{y})$である。$\tilde{y}$の確率分布を$\eta_{w_1}^{n_1}: X \rightarrow [0,1]$とする。この確率分布は、初期値の確率分布$v$と、エージェントがどうやって協働するかというモデルによって決まる。
さて、補題1の登場です。
補題1. $Pr\{w_1: \lim_{n_1 \rightarrow \infty} \sum_{x \in X} V(x) \eta^{n_1}_{w_1} (x) = 1 \} = 1$
[えーと、要するに、エージェント数が無限大であれば、協働してみつける解の価値の期待値が1になる、つまり最適化がみつかる、どうやって協働するかは問題じゃない、ということであろう]
証明。
$\epsilon$を、$0 < \epsilon < 1$を満たす任意の定数とする。
$A_{n_1} \equiv \{w_i: 1 - \sum_{x \in X} V(x) \eta^{n_1}_{w_1}(x) > \epsilon\}$ とする。
[えーと、つまり、$n_1$個のエージェントが協働してみつける解の期待値が$1-\epsilon$を下回るような、不運なエージェント選択のことを$A_{n_1}$と呼びましょうってことね]
[この定義は本文にはないけれど、メモしやすいように]
$B_{n_1} \equiv \{w_1: \phi^1(w_1), \ldots, \phi^{n_1}(w_1)$が$x^*$以外に共通の局所最適解をもつ $\}$とする。
あきらかに、$A_{n_1}$は$B_{n_1}$の部分集合である。従って$Pr(A_{n_1}) \leq Pr(B_{n_1})$である。
[奴らが正解じゃない局所最適解を共有しているときにはじめて、協働してみつける解が最適解じゃなくなるわけだから、これはまあ当然であろう]
$m \equiv \min \{\mu(\phi): \phi \in \Phi\}$ とする。$\mu$はfull supportを持つので、$m > 0$である。
[えーと... あるエージェントが母集団から選ばれる確率の最小値を$m$と呼んでいるわけか。定義によりそれは$0$より大きいわけね]
仮定2(多様性)より、任意の$x \in X\backslash \{x^*\}$について、$\mu(\{\phi \in \Phi: \phi(x) = x\}) \leq 1-m$である。
[えーと、最適解を除くどんな開始点であれ、あるエージェントを選んだ時にそいつがその開始点でいきなりスタックしちゃうという確率は1ではない。そこを抜け出せるエージェントが母集団には必ずいる。そいつが選ばれる確率は最小で$m$だ。だから、いきなりスタックしちゃう奴を選んでしまう確率は最大で$1-m$だ。ってことですね]
独立性により、
$Pr(B_{n_1})$
$\leq \sum_{x \in X\backslash \{x^*\}} Pr\{w_1: x$が$\phi^1(w_1), \ldots, \phi^{n_1}(w_1)$の共通の局所最適解である$\}$
$\leq \sum_{x \in X\backslash \{x^*\}} (1-m)^{n_1}$
$\leq (|X| - 1)(1-m)^{n_1}$
[はい深呼吸。ゆっくり考えよう。
2行目は、エージェントが最適解じゃない共通の局所最適解を持つ確率は、最適解以外のあらゆる解について「それこそが共通の局所最適解でした」となる確率を足しあげたものと同じか小さい、ってことね。共通の局所最適解は複数あるかもしれないから、ってことですかね。
3行目は、最適解以外のあらゆる解について、そこであるエージェントがスタックしちゃう確率は$1-m$、そこで全員がスタックしちゃう確率はその$n_1$乗、ってことね。なるほど、これは母集団からの抽出が独立だからいえることだ。
4行目は... 最適解以外のあらゆる解の個数はせいぜい$|X|-1$だといっているのだと思う。なぜ不等号になっているのかわからない。最適解$x^*$は1つしかないはずだから、$|X|-1$と等しいのではなかろうか。それとも$x^*$は複数ありうるってことなんだろうか]
したがって、
$\sum_{n_1 = 1}^{\infty} Pr(A_{n_1}) \leq \frac{|X|-1}{m} < \infty$
[わからん...なぜ$Pr(A_{n_1}) \leq (|X| - 1)(1-m)^{n_1}$からこれが出てくるのかがわからん... 勘だけど、これは私の基礎学力のせいで、頭のいい人なら「ああほにゃららの公理ね」とか云いそうな気がする...]
Borel-Cantelliの補題により、ここから
$Pr\{w_1: 1-\sum_{x \in X} V(x) \eta^{n_1}_{w_1}(x) > \epsilon$ infinitely often $\} = 0$
ここから
$Pr\{w_1: \lim_{n_1 \rightarrow \infty} \sum_{x \in X} V(x) \eta_{w_1}^{n_1}(x) = 1 \} = 1$
[これは残念ながら完全にお手上げ。全くわからん。いや、まあいいよ、人の専門性は尊重するよ俺は。専門家がそういってるんだから信じるよ]
定理1の証明
準備はできた。いよいよ定理1の証明である。
今度は(1)(2)のほうのランダム事象、すなわち、$N$個ランダムに選んでそこから優れた奴を$N_1$個選ぶ、というランダム事象に注目する。
仮定3(一意性)により、$\Phi$においてもっとも優れたエージェントは一意に決まる。こいつを$\phi^*$とする。
大数の法則により、
$\displaystyle Pr \{w_2: \lim_{n \rightarrow \infty} \frac{ \# \{ i \in \{i, \ldots, n\}: \phi^i (w_2) = \phi^*\}}{n} = \mu(\phi^*) \} = 1$
[えーと、選んだ$n$個のエージェントに占める優秀エージェントの割合は、$n$が無限大であれば$\mu(\phi^*)$だ、ってことね？ ごく当然のことを超回りくどく書いている気がするけど、あとの説明の都合であろう]
ここまでに述べた2つの漸近特性
$\lim_{n_1 \rightarrow \infty} \sum_{x \in X} V(x) \eta_{w_1}^{n_1}(x) = 1$
$\displaystyle \lim_{n \rightarrow \infty} \frac{ \# \{ i \in \{i, \ldots, n\}: \phi^i (w_2) = \phi^*\}}{n} = \mu(\phi^*)$
を兼ね備えている、経路$w = (w_1, w_2)$の集合を$\Omega$とする。補題1より$Pr(\Omega) = 1$である。
以下、$w = (w_1, w_2)$を任意の値に固定して考える。
$\epsilon_1 \equiv 1-E(V; \phi^*, v)$とする[最優秀エージェントがみつける解の期待値と、正解の価値すなわち1との差ってことね]。仮定1(困難性)より、$\epsilon_1$は正である。
ひとつめの漸近特性から、次のことがいえる。$\bar{n}_1 > 0$であり、かつ任意の$n_1 \geq \bar{n}_1$ について
$\sum_{x \in X} V(x) \eta_{w_1}^{n_1}(x) > 1 - \epsilon_1 = E(V; \phi^*, v)$
であるような、正の整数$\bar{n}_1$が存在する。
[ううう、数学っぽい言い回しで目が回るけど、こういうことだろう。見つかる解の価値の期待値$\sum_{x \in X} V(x) \eta_{w_1}^{n_1}(x)$は、$n_1$が大きくなるにつれて1に近づく。逆にいうと、$n_1$が無限大でない限り、見つかる解の価値の期待値は1にはならない。見つかる解の期待値が、「最優秀エージェントが見つける解の期待値」よりも必ず大きくなるようにするためには、$n_1$は最低でも何個ないといけません、という下限について考えることができる。この下限を$\bar{n}_1$とする。それは当然0よか大きい]
ふたつめの漸近特性から、こういうことがいえる。$\bar{n} > 0$であり、かつ任意の$n \geq \bar{n}$について
$\displaystyle \frac{ \# \{ i \in \{i, \ldots, n\}: \phi^i (w_2) = \phi^*\}}{n} > \frac{\mu(\phi^*)}{2} $
であるような、正の整数$\bar{n}$が存在する。
[今度はこういうことね。$n$個選んだエージェントに占める最優秀エージェントの割合は、$n$が大きくなるにつれ、$\mu(\phi^*)$に近づく。逆にいうと、$n$が無限大でない限り、それはぴったり$\mu(\phi^*)$になるとは限らない。それが必ず$\mu(\phi^*)/2$よりも大きくなるようにするためには、$n$は最低でも何個ないといけません、というような下限について考えることができる。この下限が$\bar{n}$である。えっそんなの決めらんないでしょ、と戸惑ったが、ああそうか、$w$を固定しているから下限も固定されているわけだ]
以下、$N_1 = \bar{n}_1$, $N = \max\left( \frac{2\bar{n}_1}{\mu(\phi^*)}, \bar{n} \right)$とする。
[きたー！この最大値は怪しい！スルッと書いているけど、きっとここで$\frac{2\bar{n}_1}{\mu(\phi^*)}$というのを持ち出すところにトリックがあるのだ。以下、これの謎の式を$C$と呼ぼう]
上のひとつめの式から、
$\sum_{x \in X} V(x) \eta_{w_1}^{N_1}(x) > 1 - \epsilon_1 = E(V; \phi^*, v)$
[$n_1$を$N_1=\bar{n}_1$に書き換えている。$\bar{n}_1$はこの不等式が成り立つ$n_1$の下限だから、書き換えてもオッケーだ]
上のふたつめの式から、
$\displaystyle \frac{ \# \{ i \in \{i, \ldots, N\}: \phi^i (w_2) = \phi^*\}}{N} > \frac{\mu(\phi^*)}{2} $
[もともとこの式の$N$は、$N$じゃなくてエージェントの標本サイズ$n$だった。えーと、この式が成り立つ標本サイズの下限が$\bar{n}$であり、$N$は定義により$\bar{n}$そのもの、ないしそれより大きい謎の値$C$だ。だから$n$を$N$に書き換えてもオッケーだ]
両辺を$N$倍して
$\# \{ i \in \{i, \ldots, N\}: \phi^i (w_2) = \phi^*\} > \frac{\mu(\phi^*)N}{2} $ (1)
$N$の定義より、$N \geq \frac{2\bar{n}_1}{\mu(\phi^*)}$だから、$\frac{\mu(\phi^*)N}{2} \geq \bar{n}_1$。従って
$\# \{ i \in \{i, \ldots, N\}: \phi^i (w_2) = \phi^*\} > N_1 $ (2)
[さあ、ここでトリックが発動している。ゆっくり考えよう。
著者らがここでやりたいことは、$N$人の「予選通過者たち」から選りすぐった$N_1$人の「エリートさんたち」よりも、いきなり選んだ$N_1$人の「凡人さんたち」が優れるような、$N$と$N_1$が存在する、という証明である。著者らは話の先を見越しつつ、$N$と$N_1$として2枚のカードを切ったうえで、その状況下で凡人さんたちのほうが優れていることを示さなければならない。
さきに、$n_1$人の凡人さんたちが「最優秀君」に勝つための$n_1$の下限を$\bar{n}_1$とした。で、著者らは$N_1$を$\bar{n}_1$に設定するというカードを切った。著者らは$N$として、あとで勝負に勝てるようなカードを切りたい。
あとで種明かしされるんだけど、著者らは「じゃーん！エリートさんたちは実はみんな最優秀君でした！」という状況をつくりたいのである。そのためには、予選通過者に含まれる最優秀君の人数$\# \{ i \in \{i, \ldots, N\}: \phi^i (w_2) = \phi^*\} $が$N_1=\bar{n}_1$を超えていないといけない。つまり、式(2)が成立するようなカードを切りたい。
そこでこう考える。式(2)はいったん忘れよう。予選通過者に含まれる最優秀君の人数 $\# \{ i \in \{i, \ldots, N\}: \phi^i (w_2) = \phi^*\}$は、期待値$\mu(\phi^*) N$の回りの値である。期待値の半分$\frac{\mu(\phi^*) N}{2}$を仮の防衛ラインとし、最優秀君の人数が必ずこれを上回るように$N$を設定する。その下限を$\bar{n}$とする。$N > \bar{n}$だ。
次に、仮の防衛ラインが$N_1=\bar{n}_1$を超えるように$N$を設定することにする。つまり、$\frac{\mu(\phi^*) N}{2} > \bar{n}_1$となるように$N$を設定する。つまり$N > \frac{2\bar{n}_1}{\mu(\phi^*)} = C$だ。
そこで著者らは$N$として、$N > \bar{n}$と$N > C$を共に満たす$N$、すなわち$N = \max(C, \bar{n})$というカードを切った訳である。
こうしてみると、仮の防衛ラインの分母$2$というのは特に意味のない値で、ほんとはなんでもいいのではなかろうか]
ここからなにがいえるか。
ひとつめの式
$\sum_{x \in X} V(x) \eta_{w_1}^{N_1}(x) > 1 - \epsilon_1 = E(V; \phi^*, v)$
の左辺は、独立に抽出された$N_1$個のエージェントの同時パフォーマンスの期待値だ。いっぽう右辺は$\phi^*$(最優秀くん)のパフォーマンスの期待値である。
ふたつめの式
$\# \{ i \in \{i, \ldots, N\}: \phi^i (w_2) = \phi^*\} > N_1 $
は、独立に抽出した$N$個のエージェントのなかの$\phi^*$の個数が、$N_1$個以上であることを示している。つまり、そこから優秀な奴を$N_1$個選べば、そいつらはみな$\phi^*$である。みんな$\phi^*$なんだから、そいつらの同時パフォーマンスは$E(V; \phi^*, v)$だ。
つまり、ここでひとつ目の式の右辺は、$\phi^*$(最優秀くん)のパフォーマンスの期待値であるだけでなく、$N$個から選抜された$N_1$個のエージェントの同時パフォーマンスの期待値でもある。それよりも、独立に抽出された$N_1$個のエージェントの同時パフォーマンスの期待値のほうが高い。
そういう$N$と$N_1$が存在する、ということである。
以上、Hong & Page (2004,PNAS)における証明。よんどころない事情によりメモをとった。
はっきりいおう。キツネにつままれたような気分であると！
雑記 - まず選手をランダムに選んでそこから優秀な選手を選抜するより、最初から同数の選手をランダムに選抜したほうが、集団の成績は高くなる、ということが必ずあるという証明 (Hong & Page, 2014)
« 2018年10月 | メイン | 2019年1月 »