論文の概要: Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis
- arxiv url: http://arxiv.org/abs/2007.02816v2
- Date: Fri, 10 Jul 2020 08:07:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-13 01:32:58.849604
- Title: Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis
- Title（参考訳）: Run2Survive:生存分析に基づくアルゴリズム選択のための決定論的アプローチ
- Authors: Alexander Tornede, Marcel Wever, Stefan Werner, Felix Mohr, Eyke
H\"ullermeier
- Abstract要約: 生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
- 参考スコア（独自算出の注目度）: 75.64261155172856
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithm selection (AS) deals with the automatic selection of an algorithm
from a fixed set of candidate algorithms most suitable for a specific instance
of an algorithmic problem class, where "suitability" often refers to an
algorithm's runtime. Due to possibly extremely long runtimes of candidate
algorithms, training data for algorithm selection models is usually generated
under time constraints in the sense that not all algorithms are run to
completion on all instances. Thus, training data usually comprises censored
information, as the true runtime of algorithms timed out remains unknown.
However, many standard AS approaches are not able to handle such information in
a proper way. On the other side, survival analysis (SA) naturally supports
censored data and offers appropriate ways to use such data for learning
distributional models of algorithm runtime, as we demonstrate in this work. We
leverage such models as a basis of a sophisticated decision-theoretic approach
to algorithm selection, which we dub Run2Survive. Moreover, taking advantage of
a framework of this kind, we advocate a risk-averse approach to algorithm
selection, in which the avoidance of a timeout is given high priority. In an
extensive experimental study with the standard benchmark ASlib, our approach is
shown to be highly competitive and in many cases even superior to
state-of-the-art AS approaches.
- Abstract（参考訳）: アルゴリズム選択 (as) はアルゴリズム問題クラスの特定のインスタンスに最も適した固定されたアルゴリズムのセットからアルゴリズムの自動選択を扱う。
候補アルゴリズムの非常に長いランタイムのため、アルゴリズム選択モデルのトレーニングデータは通常、すべてのアルゴリズムが全インスタンスで完了するまで実行されないという意味で、時間制約の下で生成される。
したがって、トレーニングデータは通常検閲された情報を含んでいるが、アルゴリズムの真の実行時間は不明のままである。
しかし、標準的なASアプローチの多くは、そのような情報を適切な方法で扱えない。
一方、サバイバル分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズム実行時の分散モデルを学習するための適切な方法を提供する。
このようなモデルを,アルゴリズム選択に対する洗練された決定論的アプローチの基礎として活用します。
さらに,このような枠組みを生かして,タイムアウトの回避が優先されるアルゴリズム選択に対するリスク・アバースアプローチを提唱する。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
関連論文リスト
- Frugal Algorithm Selection [1.079960007119637]
問題のすべてのインスタンスにうまく機能するアルゴリズムは存在しない。
本研究では、トレーニング対象のトレーニングインスタンスのサブセットを選択することで、このコストを削減する方法について検討する。
我々は,この問題を3つの方法でアプローチする: 能動的学習を用いて予測の不確実性に基づいて決定し, アルゴリズム予測器をタイムアウト予測器で拡張し, 徐々に増加するタイムアウトを用いてトレーニングデータを収集する。
論文 参考訳（メタデータ） (2024-05-17T19:23:30Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳（メタデータ） (2020-11-17T17:27:33Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。