September 2016
Volume 31 Number 9
テストの実行 - 秘書問題
.jpg "James McCaffrey")
秘書を雇うことを考えているとします。100 人の応募者があり、毎日 1 人と面接します。毎回面接が終わるたびに、その応募者を雇うかどうかを即決しなければなりません。その応募者を雇わなかった場合、後からその応募者に接触することはできません。100 人の候補者全員と面接する時間はありません。では、どのようなアルゴリズムを使えば、最良の応募者を選択するチャンスが最も大きくなるでしょう。
ここまで説明してきたことが、秘書問題の一例です。秘書問題の解法は、多くの重要な場面で使用されます。たとえば、機械学習では、最良予測モデルを選択する確率を最適化する過程でトレーニングを停止するためのアプローチを見つけ出す必要があることがよくあります。
秘書問題は、広くは最良選択問題と呼ばれることもある問題の一部で、最適停止問題と呼ばれる問題の一部でもあります。確か、秘書問題が最初に取り上げられたのは、(やや形式は異なっていましたが) 1960 年に発行された雑誌「Scientific American」だったと記憶しています。この問題の興味深いバリエーションはたくさんあります。
今回は、1/e 停止規則を使ってこの秘書問題に取り組む方法を紹介します。今回の主旨を理解するには、図 1 のデモ プログラムを調べるのが一番です。このデモは C# を使用してコーディングしていますが、コードを別の言語にリファクタリングしても大きな問題は起きません。
.png "秘書問題のデモ プログラムの実行")
図 1 秘書問題のデモ プログラムの実行
今回は、少なくとも中級レベルのプログラミング能力があることを前提としますが、秘書問題の知識は問いません。デモ プログラムの完成版のソース コードをここに掲載していますが、付属のコード ダウンロードからソースを入手することもできます。
1/e 停止規則
一定の条件下では、1/e 規則 (アルゴリズム) を使えば、秘書問題で最良の応募者を選択できる確率を理論上最大にできることが数学的に証明されています。秘書問題でいう候補者 (Candidate) とはある特定の時点で見つかった最良の応募者のことです。この単語 Candidate を大文字で始めているのは、英語の通常の意味では使用していないことを強調するためです。通常の英語では候補者と応募者は基本的には同じ意味を持ちます。
これ以降の説明では、N は応募者の総数を表し、e はオイラー定数を表します。e は約 2.71828 に相当します。1/e 規則を言葉で表現すると、「最初の N / e 人の応募者をスキップしますが、最良の候補者 (Candidate) はトラックします。その後、最初に出現する候補者 (Candidate) を雇用します。最初の N / e 人の応募者をスキップした後に新しい候補者 (Candidate) が現れなければ失敗し、だれも雇用できません」
このアルゴリズムを明確にするため、具体的な例を取り上げます。1/e 停止アルゴリズムを図にすると、図 2 のようになります。この場合は応募者を 10 人としています。各応募者には 0.0 から 9.0 までの評価点が付けられています (この評価点は面接を行うまでわかりません)。評価点は値が大きいほど高評価です。応募者の評価点は以下のようになっています。
(5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0)
0 1 2 3 4 5 6 7 8 9
.png "秘書問題の 1/e アルゴリズム")
図 2 秘書問題の 1/e アルゴリズム
この図は、応募者 0 は最初の面接者で評価点が 5.0、応募者 1 は 2 番目の面接者で評価点が 2.0 というように考えてください。この場合、最良の応募者は評価点 9.0 の応募者 8 になります。
スキップする応募者の数は N / e = 10 / 2.71828 = 3.6788 になります。切り捨ての場合は 3、四捨五入する場合は 4 とします。お分かりのように、N が非常に小さな数にならない限り、切り捨てでも四捨五入でも大差はありません。ここでは 3 に切り捨てるものとします。
応募者 0 と面接します。評価点は 5.0 です。この応募者は、(まだ 1 人しか面接していませんが) これまで面接した中でも最良の応募者なので候補者 (Candidate) になります。次に、応募者 1 と面接します。この応募者の評価点は 2.0 で、5.0 より低いため候補者 (Candidate) にはなりません。応募者 2 と面接し、評価点が 7.0 なので、この応募者が新しい候補者 (Candidate) になります。この時点で最初の N / e = 3 人の応募者の面接を済ませたので、この後出現する最初の新しい候補者 (Candidate) を雇用する準備が整いました。
応募者 3 と面接しますが、評価点が 1.0 なので候補者 (Candidate) にはなりません。応募者 5 と面接しますが、評価点が 0.0 (ふむ、 この応募者と一緒に働いていたことがあります) なので、候補者 (Candidate) にはなりません。応募者 6 と面接し、評価点が 8.0 であることが分かります。この点数はこれまであった中で最高の評価です。したがってこの応募者が候補者 (Candidate) になります。最初の N / e 人の応募者の面接は済ませているので応募者 6 を雇用することになります。
この例では、1/e アルゴリズムは最良の応募者を見つけていません。ただし、2 番目に適した応募者は見つけています。秘書問題に 1/e アルゴリズムを使用する場合、N 人の応募者の中から最良の応募者を選択する確率は 1 / e = 1 / 2.71828 = 0.3679 です。
デモ プログラム
デモ プログラムを作成するには、Visual Studio を起動して、「SecretaryProblem」という新しい C# コンソール アプリケーション プログラムを作成します。このデモ プログラムは .NET との大きな依存関係がないため、どのバージョンの Visual Studio でも機能します。テンプレート コードが読み込まれたら、ソリューション エクスプローラー ウィンドウで Program.cs ファイルを右クリックし、名前を「SecretaryProblemProgram.cs」というわかりやすい名前に変更します。Visual Studio によって Program クラスの名前が自動的に変更されます。エディター ウィンドウの上部にある不要な using ステートメントを、最上位レベルの System 名前空間を参照するステートメントを除いてすべて削除します。
今回のデモ プログラムは 2 つの部分に分かれています。Main メソッドの最初の数行は、10 人の応募者を使う今回の秘書問題の例に当てはめる 1/e アルゴリズムを示しています。2 番目の部分は、100 人の応募者を使って 1/e アルゴリズムを 10,000 回実行するシミュレーションを示しています。
デモの最初の部分の呼び出し側コードで重要なのは以下の数行です。
double[] ratings =
new double[] { 5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0 };
Console.WriteLine("Applicant ratings are: \n");
for (int i = 0; i < ratings.Length; ++i)
Console.Write(ratings[i].ToString("F1") + " ");
Console.WriteLine("\n");
int selected = Select(ratings, true); // Verbose
まず、double 型の配列として応募者を定義します。ここで配列のインデックスが応募者 ID を表し、各セルの値が応募者の評価点を表します。この秘書問題の基本バージョンは、すべての応募者の評価点が異なる、つまり同じ評価点の応募者はいないことを前提としています。
プログラムで定義している Select メソッドは評価点の配列を受け取り、1/e アルゴリズムを使用して応募者を選別し、選択した応募者のインデックスを返します。Select メソッドにはアルゴリズムの進捗状況が分かるように多くの WriteLine ステートメントを含めています (図 1 参照)。
デモの 2 番目の部分の呼び出し側コードで重要なのは以下の数行です (読みやすくするために若干編集しています)。
int numHiringSessions = 10000;
int numApplicants = 100;
double pBest = Simulation(numApplicants, numHiringSessions);
Console.WriteLine("Simulation prob of best applicant = " +
pBest.ToString("F4"));
double pTheory = 1 / Math.E;
Console.WriteLine("Theoretical prob of best applicant = " +
pTheory.ToString("F4"));
プログラムで定義している Simulation メソッドは固定数の応募者を受け取ります。この設計を変えて、シミュレーションの毎回の試行で応募者数をランダムに選択できるようにすることもできます。Simulation メソッドの内部では、進捗状況を出力しないバージョンの Select メソッドをループして呼び出し、最良の応募者が選択された回数をトラックします。
Select メソッド
Select メソッドは以下の定義から始めます。
static int Select(double[] ratings)
{
int numApplicants = ratings.Length;
int numSkip = (int)(numApplicants / Math.E);
int candidate = 0; // Best applicant seen
double bestRating = ratings[0];
double rating = 0.0;
bool readyToHire = false;
...
応募者の数は ratings 配列のセル数によって決まります。Select メソッドにパラメーター N を追加して、応募者数を明示的に指定する方法も考えられます。変数 numSkip は、限定された範囲で最良の応募者をトラックするときに、最初にスキップする応募者の数です。切り捨ての代わりに四捨五入を使用する場合は以下のようにします。
int numSkip = (int)Math.Round(numApplicants / Math.E);
変数 candidate は雇用処理中のある時点で見つかった最良の応募者です。変数 bestRating はその候補者 (Candidate) の評価点です。この 2 つの変数は、最初の応募者の値に初期化します。-1 や -1.0 のようなダミー値は使用しません。
変数 rating は現在の応募者の評価点を表します。この変数は読みやすくするためだけに使用しています。ブール型の変数 readyToHire は最初の numSkip-1 人の応募者の処理中は false に設定し、その処理を終えると true に設定します。
メソッド Select の本文は短く、比較的シンプルです。
...
for (int applicant = 0; applicant < numApplicants; ++applicant) {
rating = ratings[applicant];
if (applicant >= numSkip) readyToHire = true;
if (rating > bestRating) {
candidate = applicant;
bestRating = rating;
if (readyToHire == true) return candidate;
}
}
return -1;
}
このメソッドでは、ratings 配列内の各応募者を順番に処理します。応募者ごとに処理を行い、現在の応募者の評価点がそれまでの最良 (最高) の評価点よりも大きければ、その応募者を候補者 (Candidate) にします。ブール型変数 readyToHire が false のときは、候補者 (Candidates) を特定するだけで、返しません。readyToHire が true のときは、最初に見つかった有効な候補者 (Candidate) を返し、秘書問題で即時雇用する応募者にします。
設計を変えて、1 つの処理ループを 2 つの処理ループにすることもできます。その場合、最初のループでスキップする応募者を反復処理し、2 つ目のループで最初に有効な候補者 (Candidate) を特定します。
// 1. prelim loop
for (int applicant = 0; applicant < numSkip; ++applicant)
{
// Track best rating seen
}
// 2. hiring loop
for (int applicant = numSkip; applicant < numApplicants; ++applicant)
{
// Return first Candidate found
}
最初の numSkip 人の応募者の後に新しい候補者 (Candidate) が現れない可能性があります。例えば、8 人の候補者の評価点が (7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0) だとします。変数 numSkip は 8 / 2.71828 = 2 に設定されることになります。最初の 2 人の応募者の面接を済ませた時点で最高の評価点は 7.0 となり、残りの 6 人の応募者からはだれも候補者 (Candidate) として特定されないことになります。候補者 (Candidate) が見つからない場合、メソッド Select はダミー値 -1 を返します。
Simulation メソッド
Simulation メソッドを大まかな疑似コードで表すと以下のようになります。
generate applicants / ratings
determine optimal rating
set number_times_best_applicant_selected = 0
loop numTrials times
randomize order of applicants
select an applicant using 1/e algorithm
if selected applicant is optimal
++number_times_best_applicant_selected
end-if
end-loop
return number_times_best_applicant_selected / numTrials
Simulate メソッドは、以下の定義から始めます。
static double Simulation(int numApplicants, int numTrials)
{
double[] ratings = new double[numApplicants];
for (int i = 0; i < numApplicants; ++i)
ratings[i] = (i * 1.0);
double optimalRating = 1.0 * (numApplicants - 1);
int numBestSelected = 0;
...
前述のように、応募者とその評価点は配列に格納し、配列のインデックスが応募者 ID、セル値が評価点を表します。セル 0 を 0.0 に、セル 1 を 1.0 に設定し、以降は同じ要領で設定します。たとえば、N = 100 人の応募者がいる場合、応募者ID は 0 ～ 99 になり、最高の評価点は 99.0 になります。
メソッド Simulation のメイン処理ループは以下のようになります。
for (int trial = 0; trial < numTrials; ++trial) {
Shuffle(ratings);
int selected = Select(ratings);
if (selected == -1) // failed to select an applicant
continue;
double rating = ratings[selected];
if (rating == optimalRating)
++numBestSelected;
}
プログラムで定義する Shuffle メソッドは、Fisher-Yates 法ミニアルゴリズムを使用して評価点を再配置します。
static void Shuffle(double[] ratings)
{
for (int i = 0; i < ratings.Length; ++i)
{
int ri = rnd.Next(i, ratings.Length); // random index in [i, N)
double tmp = ratings[i];
ratings[i] = ratings[ri];
ratings[ri] = tmp;
}
}
Fisher-Yates 法は機械学習やシミュレーションのプログラムでよく使われるアルゴリズムで、線形コレクションの値をシャッフルします。Python や R などの多くのプログラミング言語には、標準関数ライブラリの一部として組み込みのシャッフル メソッドがあります。今回プログラムで定義した Shuffle メソッドでは、クラススコープの Random オブジェクトが存在することを前提としています。
class SecretaryProblemProgram
{
static Random rnd = new Random(0);
static void Main(string[] args)
{
...
評価点をランダムに並べ替えた後、メソッド Simulation の処理ループは Select メソッドを呼び出し、1/e アルゴリズムを使って応募者を選択してから、その応募者が最良の応募者かどうかをチェックします。
最良の候補者をチェックする際、2 つの浮動小数点値が正確に等しいかどうかを比較します。
if (rating == optimalRating)
++numBestSelected;
この方法は一般的に不適切な考え方です。一部の浮動小数点値は固定小数点値の概数としてのみ格納される場合があるためです。今回のような特殊な例では、2 つの浮動小数点数が正確に一致しているかどうかを比較する方法でも問題ありませんが、通常は正確に一致していることを比較するのではなく、非常に近い値であることを比較することになります。
まとめ
今回示した情報は主に、2003 年に W. Stein、D. Seale、および A. Rapoport が共同で執筆した研究論文「Analysis of Heuristic Solutions to the Best Choice Problem」(最良選択問題に対するヒューリスティック解法の分析) を基にしています。この研究論文はインターネット上のさまざまな場所で PDF の形式で見つかります。この論文では、1/e 規則と 2 つの追加規則について数学的な分析が行われています。
「候補者カウント」規則は n 番目の候補者 (Candidate) を自由に選択します。たとえば、n = 3 の場合、3 番目に見つかった候補者 (Candidate) を選択します。今回冒頭で示した応募者とその評価点が (5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0) になっている例では、3 番目の候補者 (Candidate) は評価点が 8.0 の応募者 6 になります。偶然にも 1/e 規則と同じになります。つまり、「候補者カウント」規則はあまり効果的ではありません。
「非候補者の次」規則は、非候補者 k 人が出現した後の最初の候補者 (Candidate) を選択します。たとえば、k = 3 とします。今回と同じ応募者と評価点では、最初の k 人に非候補者の評価点は 2.0、1.0、および 4.0 です。次の候補者 (Candidate) は評価点 8.0 の応募者 6 になります。ここでも偶然ですが、1/e 規則と同じになります。「非候補者の次」規則も問題なく機能することが分かります。
秘書問題の全体的な構造を理解すると、その主要原理が関係するシナリオが相当な数存在することがわかります。不確かな停止点が関係するプログラミング作業に直面したときは必ず、秘書問題の考え方が役に立つでしょう。
Dr.James McCaffrey は、ワシントン州レドモンドの Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。Dr.連絡先は jammc@microsoft.com (英語のみ) です。
この記事のレビューに協力してくれたマイクロソフト技術スタッフの Chris Lee および Kirk Olynyk に心より感謝いたします。