今回は秘書問題について記事を投稿しようと思います。
研究でも取り組んでいるので、その内容を一部紹介します。
秘書問題とは
- 秘書を1人雇いたいとする。
- n人が応募してきている。nという人数は既知である。
- 応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
- 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
- 毎回の面接後、その応募者を採用するか否かを即座に決定する。
- その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
- 不採用にした応募者を後から採用することはできない。
- このような状況で、最良の応募者を選択することが問題の目的である。
(wikipediaより引用しております)
応募者が100人でも100,000,000人であっても、最適ポリシーに従えば約 37% の確率で最善の応募者を選択できる。
ここで言う最適ポリシーとは、n / eまでの面接者のなかで採用評価が良かった人を決めて、n / e以降でその人よりも評価の良かったひとを採用するやり方のことですね。
取り組んでいる論文
https://arxiv.org/pdf/1711.10652.pdf興味ある方は一読してみるといいかもしれません。
二つの容量制限
この論文ではhard capacity constraintとexpected capacity constraintについて議論されており、
主にexpected capacity constraintについての論文です。
hard capacity constranit : 採用数に達し次第終了。
expected capacity constraint : 最後まで採用活動は続けることができる。
後者のメリットは、最後まで採用活動を続けるので、評価の高いひとを採用できる確率が上がることで、デメリットは採用予定数よりも大幅に超えてしまうことがあることです。
前者のメリットは後者とは逆になる感じになります。
結論
この論文では、ハード容量制約を期待値容量制約に緩和することで、いくつかの重要なオンライン問題、つまり秘書とナップザックの問題の新しいパラダイムをおり、この緩和により、クラウドサーバーでのジョブスケジューリングなどの最新のアプリケーションによって十分に動機付けられたオンラインアルゴリズムの柔軟性が高まり、秘書とナップザックの問題の両方が文献で注目されています。期待値容量制約の下で、ハード容量制約と比較して、k秘書問題の競合率は2倍に増加することを示しています。期待値容量制約を考慮することは、競争力の根本的な改善を可能にするハード容量制約があるオンラインの問題について研究できる刺激的な新しい方向性であると考えている。とのことです。
紹介されたアルゴリズムの紹介
t-Thresholdアルゴリズム(expected capacity constranit)
thresholdは日本語で閾値と言う意味です。
閾値tを境して、採用する人を判定期間と実際に採用する人を決定する期間に分けます。
競合比の定義
一人だけを採用する秘書問題は上記の競合比となっております。
t-Thresholdアルゴリズムの競合比は1 – 1 / eとなっています。
π : ランダムな順列
A : 採用するアルゴリズム(ここで言うtThresholdアルゴリズム)
i* : 一番評価の高い秘書
P : 確率の演算子
I : すべての順列
minの下に書いてある I を具体的に説明すると|π| = 100, 100000のような順列をすべて含む順列の集合のようなものです。
そのようなすべての順列の中から一番評価の高い秘書を採用する確率の一番低かったのを競合比とすると言うことです。
ソースコード
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <random>
#include <time.h>
#include <stdlib.h>
using namespace std;
void print_value(vector<double> v) {
int cnt = 0;
for(int i = 0; i < v.size(); i++) {
cnt++;
cout << v[i] << " ";
if(cnt % 10 == 0)
cout << endl;
}
cout << endl;
}
int main(void) {
int n; //アイテム数
int repeat; //繰り返す回数
int best_cnt = 0;
vector<double> v; //重み
cout << "アイテム数 : "; cin >> n;
cout << "繰り返す回数 : "; cin >> repeat;
int t = n / ( exp(1.0) ); //閾値
double R = 0.0;
vector<double> S; //選択するアイテムセット
srand(time(NULL));
for(int i = 0; i < n; i++) {
v.push_back( (double)rand() / RAND_MAX );
}
double best_item = v[0];
for(int i = 1; i < v.size(); i++) {
if(best_item < v[i])
best_item = v[i];
}
//cout << best_item << endl;
for(int i = 0; i < repeat; i++) {
random_device seed_gen;
mt19937 engine(seed_gen());
shuffle(v.begin(), v.end(), engine);
for(int j = 0; j < t; j++) {
if(v[j] > R)
R = v[j];
}
//cout << "最初のR: " << R << endl;
for(int j = t ; j < n; j++) {
if(R < v[j]) {
S.push_back(j);
R = v[j];
}
}
for(int s : S) {
//cout << v[s] << endl;
if(v[s] == best_item)
best_cnt++;
}
//cout << endl;
S.clear();
R = 0.0;
}
double μ = (double)best_cnt / repeat;
printf("競合比 : %lf\n", μ);
}
/*
実行結果
アイテム数 : 10000
繰り返す回数 : 10000
競合比 : 0.633800
*/下記の画像は n = 10000で実行した場合の何人秘書をする確率で、左から0 ~ 5人を指しています。
一人だけを採用する確率が一番高いことになっています。
コメント