論文の概要: 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)アルゴリズムのパフォーマンスをパラメータの関数として学習-理論的な複雑さである。
本稿では,ポートフォリオ構築とアルゴリズム選択のエンドツーエンド学習理論分析を紹介する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを証明します。
ポートフォリオのサイズが大きくなるにつれて、可能なすべての問題インスタンスに適切なパラメータ設定を組み込むことが期待できますが、過度な適合を避けることは不可能になります。
関連論文リスト
- A Survey of Meta-features Used for Automated Selection of Algorithms for Black-box Single-objective Continuous Optimization [4.173197621837912]
単目的連続ブラックボックス最適化の分野におけるアルゴリズム選択への重要な貢献について概説する。
自動アルゴリズム選択、構成、性能予測のための機械学習モデルについて検討する。
論文 参考訳（メタデータ） (2024-06-08T11:11:14Z) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - PS-AAS: Portfolio Selection for Automated Algorithm Selection in
Black-Box Optimization [4.842307002343618]
自動アルゴリズム選択のパフォーマンスは、選択するアルゴリズムのポートフォリオに依存する。
実際には、おそらくポートフォリオのアルゴリズムを選択する最も一般的な方法は、いくつかの参照タスクにおいてうまく機能するアルゴリズムを欲しがる選択である。
提案手法は,アルゴリズムの振る舞いのメタ表現を作成し,そのメタ表現の類似性に基づいて,アルゴリズムの集合からグラフを構築し,グラフアルゴリズムを適用して,多様な,代表的,非冗長なアルゴリズムの最終的なポートフォリオを選択する。
論文 参考訳（メタデータ） (2023-10-14T12:13:41Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Output-sensitive ERM-based techniques for data-driven algorithm design [29.582038951852553]
データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。
提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。
本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
論文 参考訳（メタデータ） (2022-04-07T17:27:18Z) - Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。
本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文 参考訳（メタデータ） (2021-07-20T11:23:21Z) - Leveraging Benchmarking Data for Informed One-Shot Dynamic Algorithm
Selection [0.9281671380673306]
進化的アルゴリズムの適用における重要な課題は、目の前の問題に最も適したアルゴリズムインスタンスの選択である。
本研究では, 疑似ブール最適化問題の解法として, このような先行性能データを用いて, 動的アルゴリズム選択スキームを推論する方法について分析する。
論文 参考訳（メタデータ） (2021-02-12T12:27:02Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。