論文の概要: Algorithm Instance Footprint: Separating Easily Solvable and Challenging
Problem Instances
- arxiv url: http://arxiv.org/abs/2306.00479v1
- Date: Thu, 1 Jun 2023 09:28:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 17:23:31.084585
- Title: Algorithm Instance Footprint: Separating Easily Solvable and Challenging
Problem Instances
- Title（参考訳）: アルゴリズムインスタンスのフットプリント - 容易に解決可能かつ困難な問題インスタンスを分離する
- Authors: Ana Nikolikj, Sa\v{s}o D\v{z}eroski, Mario Andr\'es Mu\~noz, Carola
Doerr, Peter Koro\v{s}ec, Tome Eftimov
- Abstract要約: ブラックボックス最適化では、アルゴリズムインスタンスが問題インスタンスのセットで動作し、他のインスタンスにフェールする理由を理解することが不可欠である。
本稿では,解き易い問題インスタンスの集合と解き易い問題インスタンスの集合からなるアルゴリズムインスタンスフットプリントの定式化手法を提案する。
- 参考スコア（独自算出の注目度）: 0.7046417074932257
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In black-box optimization, it is essential to understand why an algorithm
instance works on a set of problem instances while failing on others and
provide explanations of its behavior. We propose a methodology for formulating
an algorithm instance footprint that consists of a set of problem instances
that are easy to be solved and a set of problem instances that are difficult to
be solved, for an algorithm instance. This behavior of the algorithm instance
is further linked to the landscape properties of the problem instances to
provide explanations of which properties make some problem instances easy or
challenging. The proposed methodology uses meta-representations that embed the
landscape properties of the problem instances and the performance of the
algorithm into the same vector space. These meta-representations are obtained
by training a supervised machine learning regression model for algorithm
performance prediction and applying model explainability techniques to assess
the importance of the landscape features to the performance predictions. Next,
deterministic clustering of the meta-representations demonstrates that using
them captures algorithm performance across the space and detects regions of
poor and good algorithm performance, together with an explanation of which
landscape properties are leading to it.
- Abstract（参考訳）: ブラックボックス最適化では、アルゴリズムインスタンスが問題インスタンスのセットでなぜ動作するのかを理解し、他のインスタンスで失敗し、その振る舞いを説明することが不可欠である。
本稿では,解くのが容易な問題インスタンス群と,解くのが難しい問題インスタンス群からなるアルゴリズムインスタンス足跡を定式化する手法を提案する。
このアルゴリズムインスタンスの振る舞いは、問題インスタンスのランドスケープ特性とさらに関連付けられ、どのプロパティが問題インスタンスを簡単または困難にするかを説明する。
提案手法は,問題インスタンスのランドスケープ特性とアルゴリズムの性能を同一ベクトル空間に埋め込むメタ表現を用いる。
これらのメタ表現は、アルゴリズムのパフォーマンス予測のための教師付き機械学習回帰モデルを訓練し、ランドスケープの特徴の重要性をパフォーマンス予測に評価するためにモデル説明可能性技術を適用して得られる。
次に、メタ表現の決定論的クラスタリングにより、空間をまたいだアルゴリズムのパフォーマンスをキャプチャし、どのランドスケープ特性がそれにつながるのかを説明するとともに、貧弱で優れたアルゴリズム性能の領域を検出することが示される。
関連論文リスト
- 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) - Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案する。
アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
論文 参考訳（メタデータ） (2024-05-18T17:38:25Z) - On the Utility of Probing Trajectories for Algorithm-Selection [0.24475591916185496]
アルゴリズムの選択に対する機械学習のアプローチは、通常、インスタンスを入力として記述するデータを取る。
我々は、インスタンスの観点から純粋にアルゴリズムの選択を見ることは誤解を招く可能性があると論じる。
本稿では,アルゴリズム選択のためのモデルのトレーニングに使用できるインスタンスを記述するための,新しいアルゴリズム中心の手法を提案する。
論文 参考訳（メタデータ） (2024-01-23T13:23:59Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Invariant Causal Mechanisms through Distribution Matching [86.07327840293894]
本研究では、因果的視点と不変表現を学習するための新しいアルゴリズムを提供する。
実験により,このアルゴリズムは様々なタスク群でうまく動作し,特にドメインの一般化における最先端のパフォーマンスを観察する。
論文 参考訳（メタデータ） (2022-06-23T12:06:54Z) - Instance Space Analysis for the Car Sequencing Problem [4.822624702094427]
インスタンスが解決しにくい特性について検討する。
カーシーケンシング問題を解決するための6つのアルゴリズムの性能を比較する。
その結果,新しいアルゴリズムは最先端であることがわかった。
論文 参考訳（メタデータ） (2020-12-18T05:26:13Z) - Data-driven Algorithm Design [21.39493074700162]
データ駆動型アルゴリズム設計は、現代のデータ科学とアルゴリズム設計の重要な側面である。
パラメータの小さな微調整は、アルゴリズムの振る舞いのカスケードを引き起こす可能性がある。
バッチおよびオンラインシナリオに対して、強力な計算および統計的パフォーマンス保証を提供する。
論文 参考訳（メタデータ） (2020-11-14T00:51:57Z) - A black-box adversarial attack for poisoning clustering [78.19784577498031]
本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。
我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
論文 参考訳（メタデータ） (2020-09-09T18:19:31Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。