校正された機械学習予測によるアルゴリズム

要旨: 予測を伴うアルゴリズムの分野では、現実世界での性能を改善するために、オンライン・アルゴリズムの設計に機械学習の助言を取り入れます。中心となる考慮事項は、予測をどの程度信頼できるかです。既存の手法ではしばしば、利用者が集約された信頼水準を指定する必要がありますが、現代の機械学習モデルは予測レベルの不確実性に関する推定値を提供できます。本論文では、このギャップを埋めるための原理的かつ実用的な手段として、キャリブレーション（校正）を提案し、キャリブレーションされた助言の利点を2つの事例研究を通じて示します。すなわち、スキー・レンタル問題とオンラインのジョブスケジューリング問題です。スキー・レンタルでは、予測に依存したほぼ最適な性能を達成するアルゴリズムを設計し、高分散の設定においては、キャリブレーションされた助言が、不確実性の定量化のための代替手法よりも、より効果的な指針を与えることを証明します。ジョブスケジューリングでは、キャリブレーションされた予測器を用いることで、既存の手法に比べて大幅な性能向上が得られることを示します。実世界データに対する評価により、理論的結果が検証され、予測を伴うアルゴリズムに対するキャリブレーションの実用的なインパクトが強調されます。