姉妹編: 機械学習で秘書問題を解いた

01. 秘書問題と厳密な解

Wikipedia より。

秘書を1人雇いたいとする。
n 人が応募してきている。 n という人数は既知である。
応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
毎回の面接後、その応募者を採用するか否かを即座に決定する。
その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
不採用にした応募者を後から採用することはできない。
このような状況で、最良の応募者を選択することが問題の目的である。

最良の応募者を選択できる確率を最大化する戦略とその効果は以下の通りである

最初の n/e 人の応募者は採用しない（注: e は自然対数の底）
それ以降は、面接した応募者がそれまでの応募者の中で最良であった場合に採用する
最善の応募者を選択する確率は 1/e すなわち約 37% になり、 n に依存しない

例えば応募者が100人の場合、あてずっぽに採用すると 1% の確率でしか最良の人を採用できないが、上記の戦略で採用する場合、確率は 37% にまで跳ね上がる。自然対数の底が出てきたり、確率が n に依存しないという非自明な結果であるというのが非常に面白い。

02. 応用版秘書問題とその解

秘書問題は面白いのだが、現実に当てはめる場合よく似た別の問題の方が興味がある。つまり、「最良の応募者を選択できる戦略」ではなく、「選択した応募者の期待値を最大化する戦略」が知りたいことの方が圧倒的に多い。何が何でも一番を狙うのではなく、できるだけ良い人を狙うというアプローチだ。

このように問題設定をすると、少しばかり問題を拡張する必要がでてくる。つまり、期待値を最大化するということは、単純な順位の期待値ではなく、応募者が何らかのスコアを持っているとしなければならないからだ。順位はオーディナルであり、期待値はカーディナルだから。期待値といったときに、順位の期待値ではなく、応募者のスコアの期待値を計算する必要がある。

つまり以下のように秘書問題を拡張する。

秘書を1人雇いたいとする。
n 人が応募してきている。 n という人数は既知である。
各応募者はスコアを持ち、複数の応募者が同じスコアになることはない
各応募者のスコアは、区間 [0, 1) から無作為に選ぶ（つまり、スコアは一様に分布すると仮定）
無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
毎回の面接後、その応募者を採用するか否かを即座に決定する。
その応募者を採用するか否かは、それまで面接した応募者のスコアにのみ基づいて決定する。
不採用にした応募者を後から採用することはできない。
このような状況で、選択した応募者のスコアの期待値を極小化することが問題の目的である。

選択した応募者のスコアの期待値を極小化する戦略は以下の通りとなる

最初の √n 人の応募者は採用しない
それ以降は、面接した応募者のスコアがそれまでの応募者の中で最良であった場合に採用する

オリジナルの秘書問題と比べよう。十分大きい n に対して √n < n / e であるから、期待値重視の場合はより早く採用過程を始める必要がある。 n = 100 の場合、オリジナル場合は 37 人目から採用過程を始めるのに対し、応用版では 11 人目から採用過程を始めるということになる。

03. JavaScript で検証

前述の結果は数学的に厳密に解けている。そのためわざわざシミュレーションをする必要はないが、さらなる応用問題を考える場合（後述）、数式で解くことはできなくなる。そのため、乱数を使ったシミュレーションでその解を確かめることは有用であろう。本稿では JavaScript(Node.js) を使う。ただ、JavaScriptは max, min 関数や shuffle 関数を持っていないので、 lodash というライブラリを使う。

const _ = require('lodash');

応募者を作成する関数を定義しよう。オリジナルと応用版で少し違う。以下のように定義した。

const sample = n => _.shuffle(_.range(n));
const sample2 = n => Array(n).fill(0).map(() => Math.random());

上述のように応募者の配列を作ると、選考者のアルゴリズムは共用できる。与えられた配列に対して、r人は採用せず、r+1人目から実質的な選考作業に入る。採用する人のインデックスを返却する。

const createPicker = r => (arr) => {
  if (r === 0) return 0;
  const minval = _.min(arr.slice(0, r));
  let pickIndex;
  for (let i = r; i < arr.length; i += 1) {
    if (arr[i] < minval) {
      pickIndex = i;
      break;
    }
  }
  if (!pickIndex) pickIndex = arr.length - 1;
  return pickIndex;
};

道具がそろったので実際にシミュレーションをしてみよう。100人の応募者がいる場合に、r人採用を見送り r+1 人目から採用をする戦略をとる。r を 1刻みで増やしていき、厳密解のところで極値をとることを確認しよう。各ステップで10000回のシミュレーションを行う。

// simulator
function simulateSecretary(nSample, n, r) {
  const pick = createPicker(r);
  const stat = Array(n).fill(0);
  for (let i = 0; i < nSample; i += 1) {
    const arr = sample(n);
    const picked = arr[pick(arr)];
    stat[picked] += 1;
  }
  console.log(r, (stat[0] / nSample * 100).toFixed(3));
}

function simulateSecretary2(nSample, n, r) {
  const pick = createPicker(r);
  let accum = 0;
  for (let i = 0; i < nSample; i += 1) {
    const arr = sample2(n);
    accum += arr[pick(arr)];
  }
  const ev = accum / nSample;
  console.log(r, ev.toFixed(3));
}

// main
const N = 100;
console.log('original');
for (let r = 1; r < N - 1; r += 1) {
  simulateSecretary(10000, N, r);
}
console.log('modified');
for (let r = 1; r < N - 1; r += 1) {
  simulateSecretary2(10000, N, r);
}

出力の一部を抜粋する。まずは、オリジナル版の最良の候補者を選択できる確率。たしかに r = 36 の時に確率が最大になり、その値が 1/e に非常に近い。

1 '5.257'
2 '8.522'
3 '11.043'
...
32 '36.810'
33 '36.967'
34 '36.916'
35 '37.148'
36 '37.395'
37 '37.004'
38 '36.995'
...
96 '0.483'
97 '0.489'
98 '0.495'

応用版での選択した応募者のスコアの期待値。確かに r = 10 程度の時にスコアが最小になっているように見える。

1 '0.255'
2 '0.176'
3 '0.140'
4 '0.121'
5 '0.108'
6 '0.101'
7 '0.097'
8 '0.095'
9 '0.095'
10 '0.095'
11 '0.096'
12 '0.099'
13 '0.101'
14 '0.104'
15 '0.108'
16 '0.110'
17 '0.113'
...
95 '0.480'
96 '0.483'
97 '0.489'
98 '0.495'

04. さらなる応用

秘書問題はさらなる応用が考えられている。それらをいくつか紹介しよう。

応募者数 n は未知だよね普通

現実には応募者が何人来るかわからないことが多い。 n が未知の場合、どのような戦術がよいのか？も難しい問題らしい。しかし、これを一般化したモデルでも 1/e 最良選択 とよばれるより一般化された戦略がoptimalであることが知られている。

選考コスト

選考にはコストがかかる。何人も面接するのがめんどくさいので、人は早めに選考を終える傾向があることが知られている。まあ理由は選考コストだけでなく、行動経済的な理由があるのかもしれないが。

何人も選ぶ

新たにチームを作るなどのように、選択するのを1人ではなく、k 人にするという応用もある。これは解かれているようだ。

行動経済の知見

行動経済学の成果をモデルに入れ込んでもいいかもしれない。計画錯誤、参照点依存性（プロスペクト理論）あたりの知見は取り込めそうだ

スコアの分布

スコアが一様分布でなく正規分布などに応用することが可能だと思う。

05. さらなるシミュレーション

こうしたシミュレーションができるのは、戦術がr でパラメトライズされているから。より複雑な場合は、この戦術が最適であるかは保証されない。そのため、機械学習の力を借りることが必要になりそう。

機械学習で同様の結果を出せると思うので、そのうちやる。
-> やった機械学習で秘書問題を解いた

06. 補足

英語版のWikipedia の方が詳しい
googolゲームと呼ばれる派生もかなり面白い
odds algolithm が最適性を示すらしい