OR大研究には、鳩山元首相も研究した秘書問題の話が出ています。
秘書問題とは、下記のような問題です。(wikipediaより)
- 秘書を1人雇いたいとする。
- n 人が応募してきている。n という人数は既知である。
- 応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
- 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
- 毎回の面接後、その応募者を採用するか否かを即座に決定する。
- その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
- 不採用にした応募者を後から採用することはできない。
- このような状況で、最良の応募者を選択することが問題の目的である。
数学美術館には、20人の場合に平均順位を最小化する手順が出ています。
１）最初の５人はスルー。
２）次の５人については、それまでで最高だったら誘う。
３）次の３人については、それまでで最高or２位なら誘う。
４）次の２人については、それまでで３位以内なら誘う。
５）１６番目の人は、それまでで４位以内なら誘う。
６）１７番目の人は、それまでで５位以内なら誘う。
７）１８番目の人は、それまでで７位以内なら誘う。
８）１９番目の人は、それまでで１０位以内なら誘う。
９）最後まで来てしまったらその人を誘う。
この手順で平均3位の美女が選べるそうです。
pythonで確かめてみましょう。
python
import numpy as np
def order1(b):
n = len(b)
c = sorted(zip(b.argsort(), range(n))) # 実際の順位
for i in range(5, n): # 最初の5人スルー
d = b[:i+1]
e = len(d[d < b[i]]) + 1 # 順位
if i < 10:
if e == 1: break
elif i < 13:
if e <= 2: break
elif i < 14:
if e <= 3: break
elif i < 15:
if e <= 4: break
elif i < 16:
if e <= 5: break
elif i < 17:
if e <= 7: break
elif i < 18:
if e <= 10: break
return c[i][1] + 1
np.random.seed(1)
a = np.random.randn(100000, 20)
print(np.mean([order1(b) for b in a]))
>>>
3.12287
だいたい3位ですね。
でも、最初の5人は必ずスルーというのは、腑に落ちません。面接に来てくれた人にも悪いです。上記の例では、標準正規分布(N(0,1))を用いました。
このように予め分布がわかっていれば、単純にあるしきい値以下なら選択するということもできるでしょう。
やってみました。
python
def order2(b, t):
n = len(b)
c = sorted(zip(b.argsort(), range(n))) # 実際の順位
d = b < t
if not d.any(): return n
return c[d.argmax()][1] + 1
np.random.seed(1)
a = np.random.randn(100000, 20)
print(np.mean([order2(b, -0.92) for b in a]))
>>>
2.66621
しきい値は試行錯誤で求めました。さっきより、いいですね。
P.S.
機械学習で、できないか考えてみましたが、上手くいきませんでした。
以上