論文の概要: Machine Learning for Online Algorithm Selection under Censored Feedback

• arxiv url: http://arxiv.org/abs/2109.06234v1
• Date: Mon, 13 Sep 2021 18:10:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-15 15:51:15.138208
• Title: Machine Learning for Online Algorithm Selection under Censored Feedback
• Title（参考訳）: 検閲フィードバックによるオンラインアルゴリズム選択のための機械学習
• Authors: Alexander Tornede and Viktor Bengs and Eyke H\"ullermeier
• Abstract要約: オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
• 参考スコア（独自算出の注目度）: 71.6879432974126
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. As the latter is known to exhibit a heavy-tail distribution, an algorithm is normally stopped when exceeding a predefined upper time limit. As a consequence, machine learning methods used to optimize an algorithm selection strategy in a data-driven manner need to deal with right-censored samples, a problem that has received little attention in the literature so far. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. Moreover, we adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon. In an extensive experimental evaluation on an adapted version of the ASlib benchmark, we demonstrate that theoretically well-founded methods based on Thompson sampling perform specifically strong and improve in comparison to existing methods.
• Abstract（参考訳）: オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 後者はヘビーテール分布を示すことが知られているため、アルゴリズムは通常、事前定義された上限時間を超えると停止される。 結果として、データ駆動方式でアルゴリズム選択戦略を最適化するために使用される機械学習手法は、正しい検閲されたサンプルを扱う必要がある。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 さらに、ランタイム指向の損失に適応し、時間軸に依存しない空間的および時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。 Aslibベンチマークの適応版に対する広範な実験的評価において、トンプソンサンプリングに基づく理論上十分に確立された手法が、既存の手法と比較して特に強力で改善されていることを示す。

関連論文リスト

• Frugal Algorithm Selection [1.079960007119637]
  問題のすべてのインスタンスにうまく機能するアルゴリズムは存在しない。 本研究では、トレーニング対象のトレーニングインスタンスのサブセットを選択することで、このコストを削減する方法について検討する。 我々は,この問題を3つの方法でアプローチする: 能動的学習を用いて予測の不確実性に基づいて決定し, アルゴリズム予測器をタイムアウト予測器で拡張し, 徐々に増加するタイムアウトを用いてトレーニングデータを収集する。
  論文  参考訳（メタデータ） (2024-05-17T19:23:30Z)
• Scalable and Decentralized Algorithms for Anomaly Detection via Learning-Based Controlled Sensing [40.14838268469627]
  本研究では,ある時刻に観測対象のプロセスを選択する異常検出アルゴリズムを開発した。 検出アルゴリズムの目的は、所望値を超える精度で異常を識別することである。
  論文  参考訳（メタデータ） (2021-12-08T11:20:36Z)
• 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)
• 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)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。