注目キーワード

秘書問題をpythonで解いてみた/ベストマッチングを見つける性能は見事

まじめにコーディング練習

 最近、お菓子のレシピや自然薯栽培の記録がメインなエントリでした。
 本職のフルスタックデータサイエンティストの片鱗が、欠片すら感じられないブログでしたが、ぼちぼちテクノロジーな香りのするエントリをアップしていこうかと思い立ちました。

 ということで、初回は、秘書問題のコードを自分の手を動かして実装したので、それをお届けします。

秘書問題とは

 最適停止問題、最適選択問題とも言われています。
 数多くの選択肢の中から、なるべく良い候補を選びだすための数学的アプローチの一つです。
 キッチリとした定義は、Wikipediaから引用した以下のものをご参照ください。

  1. 秘書を1人雇いたいとする。
  2. n 人が応募してきている。n という人数は既知である。
  3. 応募者には順位が付けられ、複数の応募者が同じ順位になることはない(1位からn位まで重複無く順位付けできる)。
  4. 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
  5. 毎回の面接後、その応募者を採用するか否かを即座に決定する。
  6. その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
  7. 不採用にした応募者を後から採用することはできない。
  8. このような状況で、最良の応募者を選択することが問題の目的である。 
     https://ja.wikipedia.org/wiki/%E7%A7%98%E6%9B%B8%E5%95%8F%E9%A1%8C

代表的な例

  • あなたはある企業の経営者で、今回秘書を1名採用することになった。
  • 応募者は100人である。
  • 一人ずつ面接し、その場で採用/不採用の判断をしなければならない。
  • 採用をしたら、その時点で選考は終了する。
  • 一度不採用と判断した候補者を、採用することはできない。

どのような手順で採用をすれば、最も優秀な秘書を採用することができるか?

数学的に証明されている最適解

  1. 応募者が N人いるとき、\frac{N}{e} 人は無条件で採用を見送り、ベンチマークを求める材料にする。
    • \frac{N}{e} 人の中で最も優秀な候補者の評価を記録しておき、Score_{benchmark} とする。
  2. \frac{N}{e} 人以降の候補者と面接し評価を行う。
  3. 面接の結果得られた評価を Score_{benchmark} と比較し、それを上回った候補者を採用し、選考を終了する。

まずは数学的な最適解を確かめる

 数学的に証明されている最適解が、どんな結果をもたらすのか、python で実験コードを組んで確かめるとしましょう。

実験

  • 応募者の人数は100人とする。
  • 各面談における採用候補者の評価の最大値は100とする。
  • シミュレーションを1000回繰り返して、結果を評価する。
  • 生物界で良く見られる正規分布を使って、候補者の評価値を正規ランダムに割り当てる。
    • 人間の身長/体重/筋力などのステータスパラメータも正規分布に近い分布をしていることから、評価値を正規分布に従った乱数で割り当ててみた。
import numpy as np

# 応募者の人数
N = 100

# シミュレーション回数
n_exam = 1000

# 評価値の最大値
max_eval = 100

# 採用結果
# 採用した人間の評価値の履歴
# 採用できなかった場合 0
history = []

np.random.seed(1)

応募者サンプルデータを作る関数

  • 応募者数Nと評価値の最大値max_evalを受けとり、応募者のリスト(各候補者の評価値のリスト)を返す
  • 最小値0、最大値max_eval を使い、最大最小-正規化処理を行う。
def make_application_sample(N, max_eval):
    """
    応募者数Nと評価値の最大値max_evalを受けとり、応募者のリスト(各候補者の評価値のリスト)を返す
    :param N: 応募者数
    :param max_eval: 評価値の最大値
    """
    sample = np.random.normal(10, 10, N)
    min_sample = np.min(sample)
    max_sample = np.max(sample)
    normalized = (sample - min_sample)/(max_sample - min_sample) * max_eval
    return normalized

動作確認をしておきましょう。

make_application_sample(100, 100)

得られたサンプル応募者の定義リストは、次のようになりました。
最小値0、最大値100の正規乱数分布になっている様子が見て取れます。

    array([  53.78784841,   40.3479351 ,   62.29642954,   39.7620505 ,
             69.17411358,   75.98334767,   42.20611683,   80.79121217,
             51.71554969,   80.03114254,   65.45657544,   79.36128205,
             36.28827468,   54.38096201,   86.04983267,   43.99061257,
             15.14793344,   17.07080078,    5.61124944,   13.58376626,
             48.18537837,   82.53584002,   47.56367384,   63.12668628,
             54.31597689,   56.72515781,   53.13298785,   53.01142151,
             65.923975  ,   32.65108587,   77.08093901,   75.24958526,
             52.58712358,   72.91999047,   42.29749386,   45.63304894,
             59.72727207,   52.68541544,   47.43139186,   42.88477554,
             45.22105292,   75.6388007 ,   17.05587863,   63.71540328,
             51.74613654,   71.34327893,   67.01961609,    0.        ,
             68.4335972 ,   63.14186585,   56.99574542,   47.02622286,
             73.89324798,   48.15712544,   93.83967261,   68.02176261,
            100.        ,   40.58644981,   20.86449566,   71.07858497,
             73.88151795,   57.27005977,   25.27743054,   47.44852165,
             69.11116767,   52.80826613,   54.19416279,   52.98543513,
             37.57080497,   45.71846334,   27.55851906,   92.48290921,
             46.89007316,   66.25822033,   35.78290239,   72.69916966,
             18.48183916,   75.26172227,   55.83260427,   99.44672748,
             29.99779761,   58.10374596,   64.01492287,   81.60849188,
             47.95739114,   58.30868871,   13.00854833,   39.67930391,
             65.72992122,   78.99232559,   50.82548655,   98.34417599,
             92.32619876,   55.31872817,    7.50008691,   20.42467572,
             40.74243771,   79.22943783,   62.85729422,   13.98853533])

自然対数 e を取得する

np.e で自然対数を取得することができます。
numpy モジュールにビルトインされているものがあるので、それを使います。

> np.e
    2.718281828459045

秘書問題を解く関数を実装する

  • 応募者数Nと評価値の最大値max_evalを受けとり、秘書問題を1回解き、結果を返す。
    • 結果は、採用した候補者の評価値である。
      • 採用に失敗した場合は、評価値は 0 となる。
  • デバッグ情報を出力する設定のフラグ verbose を用意しておく。
    • シミュレーションを実施する際には verbose=False とする。(そうでないと、画面がデバッグ情報で埋め尽くされて大変である)
def parse_secretary_problem(N, max_eval, verbose=False):
    """

    :param N: 応募者数
    :param max_eval: 評価値の最大値
    :param verbose: デバッグ情報を表示するか?
    :return : 採用結果(候補者の評価値/失敗した場合は 0)
    """
    sample = make_application_sample(N, max_eval)

    # 先頭から N/e 人を無条件で採用を見送り、ベンチマーク評価値を作る
    pos_bench = np.int(N/np.e)
    score_bench = np.max(sample[0:pos_bench])
    if verbose:
        print("採用見送り人数: {}".format(pos_bench))
        print("ベンチマークスコア:{}".format(score_bench))
    result = 0
    for _score in sample[pos_bench:]:

        # 面談者の評価値が、ベンチマークを上回ったか?
        if _score >= score_bench:
            # ベンチマークを上回ったら、そこで採用して、選考プロセスを終了する
            result = _score
            break
    return result

動作試験をしてみましょう。
引数 verboseTrue をセットして、デバッグ情報を表示しながら実験結果を観察します。

  • 時折、採用失敗していますが、採用に成功する時は高い評価の候補者を引き当てている様子がうかがえますね。
for i in range(10):
    print(parse_secretary_problem(N, max_eval, verbose=True))
    print("=" * 70)
    採用見送り人数: 36
    ベンチマークスコア:90.17712426832686
    98.0985491323
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:88.692212923457
    93.1224094908
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:100.0
    0
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:100.0
    0
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:100.0
    0
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:66.05066809236064
    100.0
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:80.45601314069636
    82.433141944
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:100.0
    0
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:99.29357029363545
    100.0
    ======================================================================
    採用見送り人数: 36
    ベンチマークスコア:100.0
    0
    ======================================================================

実験を実施

  • 秘書問題をn_exam回解いて、採用結果を蓄積し、採用結果の統計値を求めます。
    • 採用結果は history に格納され、numpy配列にします。
    • history の中身に対して統計値を計算します。
history = []
for i in range(n_exam):
    history.append(parse_secretary_problem(N, max_eval, verbose=False))
history = np.array(history)

採用結果の期待値(採用失敗時も含む)

 採用に失敗した場合も含めた期待値を計算します。
 おや、60 前後とは・・・単純な期待値だけを見ると、ちょっと不安になりますが、もっと詳しく見て行きましょう。

> np.mean(history)
    60.090639673539847

採用できた場合の期待値

  • ベンチマーク評価値を超える候補者を採用できた場合の評価値の期待値を求める。
  • ほぼベストな人を採用していることが分かる。
    • 100に近い評価値である!
> np.mean(history[history > 0])
    95.685731964235416

採用が出来た確率

  • 採用が出来た(=ベンチマーク評価値を超える候補者が見つかったケース)の確率を求めたところ、約63%でした。
    • 裏を返せば、約37%の確率で、採用プロセスが失敗に終わるということになります・・・(汗
      • 採用基準を過剰に厳しくする場面があるということですね。
> np.sum(history > 0)/n_exam
    0.628

ベストの候補者をドンピシャで採用できた確率

  • ベストな候補者をドンピシャで採用できた確率は、約35.5%
  • 採用が成功した場合、約56.53% の確率でベストな候補者を引き当てることに成功します。(条件付き確率)
> np.sum(history >= max_eval)/n_exam
    0.35499999999999998

実験レビュー

  • ベスト候補者か、それに準ずる候補者を採用することが出来る。
  • ただし、約37%の確率で採用プロセス自体が失敗する!
  • ベンチマークに使った評価値は、かなり使える。

今後試したい項目

  • 採用プロセスの失敗確率を減らし、なおかつ採用候補者の期待評価値を維持できる、ベストエフォートなパラメータを探ってみたいところです。
    • 自分の現職の会社で採用に携わっているが、採用プロセス自体が失敗に終わると言うのは悪夢。
      • パーフェクトな評価の候補者ではなくとも十分許容できる範囲かつ採用プロセスを成功裏に終わらせる匙加減を知りたい。

追記(2020/01/19)

 続編をアップロードしました!

YUUKOU's 経験値

目次 1 秘書問題をもうちょっとだけ掘り下げる2 おさらい:シミュレーションの定義3 今回の評価基準:評価期待値4 実験…

数学問題をPythonで解くエントリ

こちらも併せてご覧いただけます!

目次 1 まじめにコーディング練習1.1 秘書問題とは1.1.1 代表的な例1.2 数学的に証明されている最適解1.3 まずは数学的な最適解を確かめる2 実験2.1 応募者サンプルデータを作る関数2.2 自然対数 e を取得する2.3 秘書問題を解く関数を実装する3 実験を実施4 採用結果の期待値( […]

目次 1 秘書問題をもうちょっとだけ掘り下げる2 おさらい:シミュレーションの定義3 今回の評価基準:評価期待値4 実験5 Python コード実装!5.1 序盤定義部分5.2 応募者サンプルデータを作る関数5.3 秘書問題を解く関数を実装する6 実験6.1 実験結果を描画する7 レビューまとめ8 […]

最新情報をチェックしよう!