アルゴリズムの選択

アルゴリズム選択(インスタンスごとのアルゴリズム選択またはオフライン アルゴリズム選択とも呼ばれる) は、インスタンスごとにポートフォリオからアルゴリズムを選択するメタアルゴリズム手法です。これは、多くの実際的な問題において、異なるアルゴリズムは異なるパフォーマンス特性を持つという観察に基づいています。つまり、あるアルゴリズムは一部のシナリオではパフォーマンスが良くても、他のシナリオではパフォーマンスが悪く、別のアルゴリズムではその逆になります。どのアルゴリズムをいつ使用するかを特定できれば、各シナリオを最適化し、全体的なパフォーマンスを向上させることができます。これが、アルゴリズム選択の目的です。アルゴリズム選択手法を適用するための唯一の前提条件は、補完的なアルゴリズムのセットが存在する (または構築できる) ことです。

アルゴリズムのポートフォリオ、インスタンスのセット、およびコストメトリックが与えられた場合、アルゴリズム選択問題は、すべてのインスタンスにわたるコストが最適化されるように、インスタンスからアルゴリズムへのマッピングを見つけることです。^{[1] [2]}${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$${\displaystyle i\in {\mathcal {I}}}$${\displaystyle m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R} }$${\displaystyle s:{\mathcal {I}}\to {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle \sum _{i\in {\mathcal {I}}}m(s(i),i)}$

アルゴリズム選択のよく知られた応用は、ブール充足可能性問題である。ここでは、アルゴリズムのポートフォリオは（補完的な）SATソルバーのセットであり、インスタンスはブール式であり、コストメトリックは、たとえば平均実行時間または未解決のインスタンスの数である。したがって、目標は、個々のインスタンスごとにパフォーマンスの高いSATソルバーを選択することです。同様に、アルゴリズム選択は、他の多くの困難な問題（混合整数計画、CSP、AI計画、TSP、MAXSAT、QBF、回答セットプログラミングなど）に適用できます。SATの競争で優勝したシステムは、SATzilla、^[3] 3S ^[4]およびCSHC ^[5]です。${\displaystyle {\mathcal {NP}}}$

機械学習では、アルゴリズムの選択はメタ学習としてよく知られています。アルゴリズムのポートフォリオは機械学習アルゴリズム（ランダムフォレスト、SVM、DNNなど）で構成され、インスタンスはデータセットであり、コストメトリックはエラー率などです。したがって、目標は、どの機械学習アルゴリズムが各データセットで小さなエラーを持つかを予測することです。

アルゴリズム選択問題は主に機械学習技術で解決されます。問題のインスタンスを数値的特徴で表現することにより、与えられたインスタンスに対するマッピングを学習することで、アルゴリズム選択を多クラス分類問題として捉えることができます。 ${\displaystyle f}$${\displaystyle f_{i}\mapsto {\mathcal {A}}}$${\displaystyle i}$

インスタンス特徴はインスタンスの数値表現です。例えば、ブール式の変数の数、節の数、節の平均長^[6]、またはMLデータセットのサンプル数、特徴、クラスバランスを数えて、インスタンスの特性についての印象を得ることができます。

私たちは 2 種類の機能を区別しています:

1. 静的特徴は、ほとんどの場合、いくつかのカウントと統計です (例: SAT の節と変数の比率)。これらの特徴は、非常に単純な特徴 (例: 変数の数) から非常に複雑な特徴 (例: 変数節グラフに関する統計) まで多岐にわたります。
2. プローブ機能 (ランドマーク機能とも呼ばれる) は、インスタンスでアルゴリズムの動作の分析を実行することによって計算されます (例: ML データ セットでの安価な決定木アルゴリズムの精度、またはブール式での確率的ローカル検索ソルバーの短時間の実行)。これらの機能は、単純な静的機能よりもコストがかかることがよくあります。

使用されるパフォーマンス メトリックに応じて、機能の計算にコストが伴う場合があります。たとえば、実行時間をパフォーマンス メトリックとして使用する場合、インスタンス機能の計算にかかる時間をアルゴリズム選択システムのパフォーマンスに含めます。SAT 解決は具体的な例ですが、CNF式のインスタンス機能は非常に安価 (たとえば、DIMAC 形式の CNF では変数の数を取得するのに一定時間で実行できる) か、非常に高価 (たとえば、数十秒または数百秒かかるグラフ機能) になる可能性があるため、このような機能コストを無視することはできません。 ${\displaystyle m}$

このようなシナリオでは、実際には特徴計算のオーバーヘッドを考慮することが重要です。そうしないと、アルゴリズム選択アプローチのパフォーマンスについて誤解を招く印象を与えてしまいます。たとえば、どのアルゴリズムを選択するかを完全な精度で決定できるが、特徴がポートフォリオ アルゴリズムの実行時間である場合、ポートフォリオ アプローチにはメリットがありません。特徴コストが省略された場合、これは明らかではありません。

最初に成功したアルゴリズム選択アプローチの1つは、各アルゴリズムのパフォーマンスを予測し、インスタンスに対して最も予測されたパフォーマンスが最も高いアルゴリズムを選択するというものでした。^[3]${\displaystyle {\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R} }$${\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}$${\displaystyle i}$

一般的な仮定は、与えられたインスタンスのセットは均質なサブセットにクラスタリングでき、これらのサブセットのそれぞれには、そこに含まれるすべてのインスタンスに対して 1 つの優れたパフォーマンスを発揮するアルゴリズムがあるというものです。したがって、トレーニングは、教師なしクラスタリング アプローチを使用して均質なクラスターを識別し、各クラスターにアルゴリズムを関連付けることから構成されます。新しいインスタンスがクラスターに割り当てられ、関連付けられたアルゴリズムが選択されます。^[7]${\displaystyle {\mathcal {I}}}$

より現代的なアプローチは、教師あり学習を使用して均質なインスタンスのサブセットを識別する コストに敏感な階層的クラスタリング^[5]です。

多クラス分類の一般的なアプローチは、すべてのクラスのペア（ここではアルゴリズム）間のペアワイズモデルを学習し、ペアワイズモデルによって最も頻繁に予測されたクラスを選択することです。ペアワイズ予測問題のインスタンスには、2つのアルゴリズムのパフォーマンスの違いによって重み付けすることができます。これは、大きな差のある予測を正しく取得することが最も重要であるという事実に基づいていますが、パフォーマンスの違いがほとんどない場合は、誤った予測に対するペナルティは小さくなります。したがって、分類モデルをトレーニングするための各インスタンスには、コストが関連付けられています。^[8]${\displaystyle i}$${\displaystyle {\mathcal {A}}_{1}}$${\displaystyle {\mathcal {A}}_{2}}$${\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}$

アルゴリズム選択問題は、次の仮定の下で効果的に適用できます。

• アルゴリズムのポートフォリオはインスタンス セットに関して補完的です。つまり、他のすべてのアルゴリズムのパフォーマンスを支配する単一のアルゴリズムは存在しません(補完分析の例については右の図を参照)。${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$${\displaystyle {\mathcal {A}}\in {\mathcal {P}}}$${\displaystyle {\mathcal {I}}}$
• 一部のアプリケーションでは、インスタンス機能の計算にはコストがかかります。たとえば、コスト メトリックが実行時間である場合は、インスタンス機能の計算時間も考慮する必要があります。このような場合、機能の計算コストは​​、アルゴリズムの選択によるパフォーマンスの向上よりも大きくしてはなりません。

アルゴリズムの選択は単一のドメインに限定されず、上記の要件が満たされていれば、あらゆる種類のアルゴリズムに適用できます。適用ドメインには以下が含まれます。

• 難しい組み合わせ問題: ^[10] SAT、混合整数計画、CSP、AI計画、TSP、MAXSAT、QBF、解答集合プログラミング
• 組み合わせオークション
• 機械学習では、この問題はメタ学習として知られている。
• ソフトウェア設計
• ブラックボックス最適化
• マルチエージェントシステム
• 数値最適化
• 線形代数、微分方程式
• 進化アルゴリズム
• 車両経路問題
• 電力システム

アルゴリズムの選択に関する広範な文献のリストについては、文献の概要を参照してください。

オンライン アルゴリズム選択とは、解決プロセス中に異なるアルゴリズムを切り替えることを指します。これは、ハイパーヒューリスティックとして役立ちます。対照的に、オフライン アルゴリズム選択では、特定のインスタンスのアルゴリズムを解決プロセスの前に 1 回だけ選択します。

アルゴリズム選択の拡張は、インスタンスごとのアルゴリズムスケジューリング問題であり、1つのソルバーだけを選択するのではなく、インスタンスごとに各アルゴリズムの時間予算を選択します。このアプローチは、インスタンスの特徴があまり有益ではなく、単一のソルバーが誤って選択される可能性が高い場合に特に、選択システムのパフォーマンスを向上させます。^[11]

並列計算の重要性が高まっていることから、並列計算のためのアルゴリズム選択の拡張として並列ポートフォリオ選択が考えられ、並列ポートフォリオで同時に実行するアルゴリズムのサブセットを選択する。^[12]

• アルゴリズム選択ライブラリ (ASlib)
• アルゴリズム選択に関する文献