まじめにコーディング練習
最近、お菓子のレシピや自然薯栽培の記録がメインなエントリでした。
本職のフルスタックデータサイエンティストの片鱗が、欠片すら感じられないブログでしたが、ぼちぼちテクノロジーな香りのするエントリをアップしていこうかと思い立ちました。
ということで、初回は、秘書問題のコードを自分の手を動かして実装したので、それをお届けします。
秘書問題とは
最適停止問題、最適選択問題とも言われています。
数多くの選択肢の中から、なるべく良い候補を選びだすための数学的アプローチの一つです。
キッチリとした定義は、Wikipediaから引用した以下のものをご参照ください。
- 秘書を1人雇いたいとする。
- n 人が応募してきている。n という人数は既知である。
- 応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
- 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
- 毎回の面接後、その応募者を採用するか否かを即座に決定する。
- その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
- 不採用にした応募者を後から採用することはできない。
- このような状況で、最良の応募者を選択することが問題の目的である。
https://ja.wikipedia.org/wiki/%E7%A7%98%E6%9B%B8%E5%95%8F%E9%A1%8C
代表的な例
- あなたはある企業の経営者で、今回秘書を1名採用することになった。
- 応募者は100人である。
- 一人ずつ面接し、その場で採用/不採用の判断をしなければならない。
- 採用をしたら、その時点で選考は終了する。
- 一度不採用と判断した候補者を、採用することはできない。
どのような手順で採用をすれば、最も優秀な秘書を採用することができるか？
数学的に証明されている最適解
- 応募者が
N人いるとき、\frac{N}{e}人は無条件で採用を見送り、ベンチマークを求める材料にする。\frac{N}{e}人の中で最も優秀な候補者の評価を記録しておき、Score_{benchmark}とする。
\frac{N}{e}人以降の候補者と面接し評価を行う。- 面接の結果得られた評価を
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
動作試験をしてみましょう。
引数 verbose に True をセットして、デバッグ情報を表示しながら実験結果を観察します。
- 時折、採用失敗していますが、採用に成功する時は高い評価の候補者を引き当てている様子がうかがえますね。
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％の確率で、採用プロセスが失敗に終わるということになります・・・（汗
- 採用基準を過剰に厳しくする場面があるということですね。
- 裏を返せば、約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)
続編をアップロードしました！
目次 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 […]
こちらのエントリも併せてどうぞ！
目次 1 まじめにコーディング練習1.1 秘書問題とは1.1.1 代表的な例1.2 数学的に証明されている最適解1.3 まずは数学的な最適解を確かめる2 実験2.1 応募者サンプルデータを作る関数2.2 自然対数 e を取得する2.3 秘書問題を解く関数を実装する3 実験を実施4 採用結果の期待値（ […]
目次 1 概要2 命名規則(Naming)2.1 避けるべき名前2.2 命名規則(Naming Conventions)2.2.1 Protected/private メソッド・プロパティ2.2.2 ダンダー(__)を使ったprivate化の注意点2.2.3 モジュール化：クラスや関数のまとめ方2. […]
目次 1 Python でExcelファイルをいじってみたらzip圧縮ファイルだった！2 このエントリを読むと得られるであろうもの3 実験環境についての説明4 今回使用するPythonモジュールを読み込む5 xlsxファイルをzipファイルとして読み込んでみる6 zipファイルのアーカイブからxml […]
目次 1 Pythonでtar.gzアーカイブを扱う方法2 Python の tarfile モジュール3 tarfile モジュールのインポート4 tar.gz アーカイブを読み込む5 tar.gz アーカイブを出力するコード6 まとめ等 Pythonでtar.gzアーカイブを扱う方法 備忘録＆ […]
目次 1 Apache Beam チュートリアル2 Apache Beam 概要2.0.1 (補足) Apache Beam のリリース状況3 概念3.1 Runner(実行環境)3.2 パイプライン処理を構成する概念4 基本的なパイプラインの開発の流れ4.1 パイプライン処理内の各工程の詳細5 動 […]
目次 1 長期保有シミュレーション1.1 背景2 シミュレーションの準備2.1 データファイルの設置場所3 シミュレーション処理3.1 使用するモジュール群の読み込み3.2 視覚化処理の設定3.3 価格データの読み込みと前処理3.3.1 前処理3.3.1.1 カンマ区切りのOHLCの処理3.3.1. […]
目次 1 概要2 Anacondaで開発環境を構築2.1 自然言語処理用の開発環境を conda で構築3 mecab 本体のインストール4 neologd のインストール＆設定4.1 ビルド環境の整備4.2 neologd のインストール4.3 mecab の辞書を neologd に変更する4. […]
目次 1 概要2 感染フェーズの数値化とは2.1 Phase Position の分布から分かること2.2 Phase Position 上位国の顔ぶれ3 序盤から感染爆発に襲われた欧米先進国4 感染者の重症化率から分かること4.1 重症化率の高い国は医療崩壊のリスクに晒されている5 医療崩壊リスク […]
目次 1 秘書問題をもうちょっとだけ掘り下げる2 おさらい：シミュレーションの定義3 今回の評価基準：評価期待値4 実験5 Python コード実装！5.1 序盤定義部分5.2 応募者サンプルデータを作る関数5.3 秘書問題を解く関数を実装する6 実験6.1 実験結果を描画する7 レビューまとめ8 […]
目次 1 新型コロナ・致死率の時系列推移を分析した結果分かったこと1.1 新型コロナのニュースで頻繁に見かける国々と日本の比較：1.2 ヨーロッパにおける致死率の二極化：1.3 新型コロナ対策に成功している国？での比較 新型コロナ・致死率の時系列推移を分析した結果分かったこと 先日から使い始めたジ […]