論文の概要: Towards Feature-Based Performance Regression Using Trajectory Data
- arxiv url: http://arxiv.org/abs/2102.05370v1
- Date: Wed, 10 Feb 2021 10:19:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-12 01:00:16.688607
- Title: Towards Feature-Based Performance Regression Using Trajectory Data
- Title(参考訳): 軌道データを用いた特徴量に基づく性能回帰
- Authors: Anja Jankovic and Tome Eftimov and Carola Doerr
- Abstract要約: ブラックボックス最適化は非常に活発な研究領域であり、毎年多くの新しいアルゴリズムが開発されている。
アルゴリズムの多様性はメタプロブレム(メタプロブレム):どのアルゴリズムが与えられた問題を選択するか?
過去の研究では、探索ランドスケープ分析に基づくインスタンスごとのアルゴリズム選択が、このメタプロブレムに取り組むための効率的な手段であることが示されている。
- 参考スコア(独自算出の注目度): 0.9281671380673306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Black-box optimization is a very active area of research, with many new
algorithms being developed every year. This variety is needed, on the one hand,
since different algorithms are most suitable for different types of
optimization problems. But the variety also poses a meta-problem: which
algorithm to choose for a given problem at hand? Past research has shown that
per-instance algorithm selection based on exploratory landscape analysis (ELA)
can be an efficient mean to tackle this meta-problem. Existing approaches,
however, require the approximation of problem features based on a significant
number of samples, which are typically selected through uniform sampling or
Latin Hypercube Designs. The evaluation of these points is costly, and the
benefit of an ELA-based algorithm selection over a default algorithm must
therefore be significant in order to pay off. One could hope to by-pass the
evaluations for the feature approximations by using the samples that a default
algorithm would anyway perform, i.e., by using the points of the default
algorithm's trajectory.
We analyze in this paper how well such an approach can work. Concretely, we
test how accurately trajectory-based ELA approaches can predict the final
solution quality of the CMA-ES after a fixed budget of function evaluations. We
observe that the loss of trajectory-based predictions can be surprisingly small
compared to the classical global sampling approach, if the remaining budget for
which solution quality shall be predicted is not too large. Feature selection,
in contrast, did not show any advantage in our experiments and rather led to
worsened prediction accuracy. The inclusion of state variables of CMA-ES only
has a moderate effect on the prediction accuracy.
- Abstract(参考訳): ブラックボックス最適化は非常に活発な研究分野であり、毎年多くの新しいアルゴリズムが開発されている。
この多様性は、異なるアルゴリズムが異なるタイプの最適化問題に最も適しているため、必要である。
しかし、この変種はメタプロブレム(メタプロブレム):どのアルゴリズムが与えられた問題を選択するか?
過去の研究では、探索的ランドスケープ分析(ela)に基づく個人毎のアルゴリズム選択が、このメタ問題に取り組む効率的な手段であることが示されている。
しかし、既存のアプローチでは、かなりの数のサンプルに基づいて問題の特徴を近似する必要がある。
これらの点の評価はコストがかかり、既定アルゴリズムに対するelaベースのアルゴリズム選択の利点は、利益を得るためには重要でなければならない。
デフォルトアルゴリズムがいずれにせよ実行するであろうサンプル、すなわちデフォルトアルゴリズムの軌道の点を用いて、特徴近似の評価を副次的に通過させることが期待できる。
本稿では,このようなアプローチがいかにうまく機能するかを分析した。
具体的には,機能評価の予算を定め,CMA-ESの最終解の質を正確に予測できることを検証した。
我々は, 従来のグローバルサンプリング手法に比べ, 軌道に基づく予測の損失が驚くほど小さいこと, 解の質が予測される残りの予算が大きすぎること, を観察する。
対照的に、特徴選択は我々の実験で何の利点も示さず、むしろ予測精度を悪化させた。
CMA-ESの状態変数を含むことは、予測精度に適度な影響しか与えない。
関連論文リスト
- DynamoRep: Trajectory-Based Population Dynamics for Classification of
Black-box Optimization Problems [0.755972004983746]
簡単な統計量を用いて最適化アルゴリズムの軌道を記述する特徴抽出法を提案する。
提案するDynamoRep機能は,最適化アルゴリズムが動作している問題クラスを特定するのに十分な情報を取得する。
論文 参考訳(メタデータ) (2023-06-08T06:57:07Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳(メタデータ) (2022-09-27T09:06:37Z) - Per-run Algorithm Selection with Warm-starting using Trajectory-based
Features [5.073358743426584]
インスタンスごとのアルゴリズム選択は、与えられた問題の場合、1つまたは複数の適切なアルゴリズムを推奨する。
提案手法は,実行毎のアルゴリズム選択を行うオンラインアルゴリズム選択方式を提案する。
提案手法は静的なインスタンスごとのアルゴリズム選択よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-04-20T14:30:42Z) - Trajectory-based Algorithm Selection with Warm-starting [2.3823600586675724]
本研究では,アルゴリズムの性能予測シナリオにおいて,性能回帰モデルとアルゴリズム選択モデルの品質と精度について検討する。
ウォームスタートを用いたトラジェクトリベースラン毎のアルゴリズム選択の有望な性能を示す。
論文 参考訳(メタデータ) (2022-04-13T14:00:55Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳(メタデータ) (2022-02-22T18:37:23Z) - Benchmarking Feature-based Algorithm Selection Systems for Black-box
Numerical Optimization [0.0]
特徴に基づくアルゴリズムの選択は、目に見えない問題において最適化アルゴリズムのポートフォリオから最適なアルゴリズムを自動的に見つけることを目的としている。
本稿では,24個のノイズレスブラックボックス最適化ベンチマーク関数のアルゴリズム選択システムについて分析する。
アルゴリズム選択システムの性能は, 逐次最小二乗プログラミングをプリゾルバとして利用することにより, 大幅に向上できることを示す。
論文 参考訳(メタデータ) (2021-09-17T07:17:40Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳(メタデータ) (2021-09-13T18:10:52Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳(メタデータ) (2020-07-06T15:20:17Z) - Landscape-Aware Fixed-Budget Performance Regression and Algorithm
Selection for Modular CMA-ES Variants [1.0965065178451106]
市販の教師あり学習手法を用いて,高品質な性能予測が可能であることを示す。
このアプローチを,モジュール型CMA-ESアルゴリズム群から選択した,非常に類似したアルゴリズムのポートフォリオ上でテストする。
論文 参考訳(メタデータ) (2020-06-17T13:34:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。