論文の概要: Generalization in portfolio-based algorithm selection
- arxiv url: http://arxiv.org/abs/2012.13315v1
- Date: Thu, 24 Dec 2020 16:33:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 08:19:13.627445
- Title: Generalization in portfolio-based algorithm selection
- Title（参考訳）: ポートフォリオに基づくアルゴリズム選択における一般化
- Authors: Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
- Abstract要約: ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
- 参考スコア（独自算出の注目度）: 97.74604695303285
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Portfolio-based algorithm selection has seen tremendous practical success
over the past two decades. This algorithm configuration procedure works by
first selecting a portfolio of diverse algorithm parameter settings, and then,
on a given problem instance, using an algorithm selector to choose a parameter
setting from the portfolio with strong predicted performance. Oftentimes, both
the portfolio and the algorithm selector are chosen using a training set of
typical problem instances from the application domain at hand. In this paper,
we provide the first provable guarantees for portfolio-based algorithm
selection. We analyze how large the training set should be to ensure that the
resulting algorithm selector's average performance over the training set is
close to its future (expected) performance. This involves analyzing three key
reasons why these two quantities may diverge: 1) the learning-theoretic
complexity of the algorithm selector, 2) the size of the portfolio, and 3) the
learning-theoretic complexity of the algorithm's performance as a function of
its parameters. We introduce an end-to-end learning-theoretic analysis of the
portfolio construction and algorithm selection together. We prove that if the
portfolio is large, overfitting is inevitable, even with an extremely simple
algorithm selector. With experiments, we illustrate a tradeoff exposed by our
theoretical analysis: as we increase the portfolio size, we can hope to include
a well-suited parameter setting for every possible problem instance, but it
becomes impossible to avoid overfitting.
- Abstract（参考訳）: ポートフォリオベースのアルゴリズム選択は、過去20年で大きな成功を収めてきた。
このアルゴリズム構成手順は、まず多様なアルゴリズムパラメータ設定のポートフォリオを選択し、次に与えられた問題インスタンス上でアルゴリズムセレクタを使用して、強い予測性能を持つポートフォリオからパラメータ設定を選択する。
多くの場合、ポートフォリオとアルゴリズムセレクタは、手元のアプリケーションドメインの典型的な問題インスタンスのトレーニングセットを使用して選択される。
本稿では,ポートフォリオに基づくアルゴリズム選択に対する証明可能な最初の保証を提供する。
トレーニングセットがどの程度大きいかを分析し、結果のアルゴリズムセレクタの平均的なパフォーマンスが将来の(予測された)パフォーマンスに近いことを確認します。
1)アルゴリズムセレクタの学習-理論的な複雑さ、2)ポートフォリオのサイズ、3)アルゴリズムのパフォーマンスをパラメータの関数として学習-理論的な複雑さである。
本稿では,ポートフォリオ構築とアルゴリズム選択のエンドツーエンド学習理論分析を紹介する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを証明します。
ポートフォリオのサイズが大きくなるにつれて、可能なすべての問題インスタンスに適切なパラメータ設定を組み込むことが期待できますが、過度な適合を避けることは不可能になります。
関連論文リスト
- Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳（メタデータ） (2022-05-03T07:54:56Z) - Fair Feature Subset Selection using Multiobjective Genetic Algorithm [0.0]
フェアネスと精度を両立させる特徴部分選択手法を提案する。
モデル性能の指標としてF1-Scoreを用いる。
最も一般的なフェアネスベンチマークデータセットの実験では、進化的アルゴリズムを用いることで、フェアネスと精度のトレードオフを効果的に探索できることが示されている。
論文 参考訳（メタデータ） (2022-04-30T22:51:19Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Model Selection in Batch Policy Optimization [88.52887493684078]
バッチポリシー最適化におけるモデル選択の問題について検討する。
我々は,任意のモデル選択アルゴリズムが競争力を得るために最適にトレードオフすべきという誤りの3つの源を同定する。
論文 参考訳（メタデータ） (2021-12-23T02:31:50Z) - Pareto Navigation Gradient Descent: a First-Order Algorithm for
Optimization in Pareto Set [17.617944390196286]
マルチタスク学習のような現代の機械学習アプリケーションは、複数の目的関数をトレードオフするために最適なモデルパラメータを見つける必要がある。
勾配情報のみを用いてOPT-in-Paretoを近似的に解く1次アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-17T04:07:04Z) - Combining K-means type algorithms with Hill Climbing for Joint
Stratification and Sample Allocation Designs [0.0]
これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。
それぞれのソリューションのコストを評価するのに 費用がかかります
上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
論文 参考訳（メタデータ） (2021-08-18T08:41:58Z) - Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。
本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文 参考訳（メタデータ） (2021-07-20T11:23:21Z) - MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using
Shortest Path Embeddings [6.223269541026908]
マルチエージェントパス探索(mapf)問題を最適に解くことは、メイクスパンと全到着時間の最小化の両方においてnpハードであることが知られている。
あらゆる種類の問題でうまく機能する最適なMAPFアルゴリズムは存在せず、どのアルゴリズムを使用するかの標準ガイドラインも存在しない。
私たちは、MAPF問題インスタンスを取り、アルゴリズムのポートフォリオから使用する最速のアルゴリズムを選択しようとする深い畳み込みネットワークMAPFASTを開発しました。
論文 参考訳（メタデータ） (2021-02-24T18:41:37Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。