論文の概要: Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs

• arxiv url: http://arxiv.org/abs/2501.07432v1
• Date: Mon, 13 Jan 2025 15:59:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:25:22.009729
• Title: Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs
• Title（参考訳）: 重み付きCSPに対するインシシット・ハッティング・セット・アプローチの実証評価
• Authors: Aleksandra Petrova, Javier Larrosa, Emma Rollón,
• Abstract要約: 重み付きCSP問題に対する既存の参照アルゴリズムの代替策について検討する。 我々の実証研究は、WCSPにとって最良の選択肢を特定するのは容易ではないことを示している。
• 参考スコア（独自算出の注目度）: 46.010796136659536
• License:
• Abstract: SAT technology has proven to be surprisingly effective in a large variety of domains. However, for the Weighted CSP problem dedicated algorithms have always been superior. One approach not well-studied so far is the use of SAT in conjunction with the Implicit Hitting Set approach. In this work, we explore some alternatives to the existing algorithm of reference. The alternatives, mostly borrowed from related boolean frameworks, consider trade-offs for the two main components of the IHS approach: the computation of low-cost hitting vectors, and their transformation into high-cost cores. For each one, we propose 4 levels of intensity. Since we also test the usefulness of cost function merging, our experiments consider 32 different implementations. Our empirical study shows that for WCSP it is not easy to identify the best alternative. Nevertheless, the cost-function merging encoding and extracting maximal cores seems to be a robust approach.
• Abstract（参考訳）: SAT技術は、様々な領域で驚くほど効果的であることが証明されている。 しかし、Weighted CSP問題専用アルゴリズムは常に優れている。 これまでによく研究されていないアプローチの1つは、Implicit Hitting Set アプローチと SAT の使用である。 本研究では,既存の参照アルゴリズムの代替策について検討する。 代替案は、主に関連するブールのフレームワークから借用されたもので、IHSアプローチの2つの主要なコンポーネントである、低コストのヒットベクトルの計算と、それらの高コストコアへの変換のトレードオフについて検討している。 それぞれに4つのレベルの強度を提案します。 また,コスト関数のマージの有用性を検証した結果,32種類の実装について検討した。 我々の実証研究は、WCSPにとって最良の選択肢を特定するのは容易ではないことを示している。 それでも、コスト関数のマージ符号化と最大コアの抽出は、堅牢なアプローチであるようだ。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Cost Aware Best Arm Identification [13.380383930882784]
  emphCost Aware Best Arm Identification (CABAI)と呼ぶ。 平方根規則に基づくemphChernoff Overlap (CO)と呼ばれる単純なアルゴリズムを提案する。 この結果から,不均一な動作コストを無視すると,実行時の準最適性が得られ,また,簡単なアルゴリズムにより,幅広い問題に対してほぼ最適性能が得られることがわかった。
  論文  参考訳（メタデータ） (2024-02-26T16:27:08Z)
• Stochastic Average Gradient : A Simple Empirical Investigation [0.0]
  平均勾配 (SAG) は有限個の滑らかな関数の和を最適化する手法である。 SAGは、単純な玩具問題において、他のイテレーションよりも早く収束し、単純な機械学習問題において、他の多くのイテレーションよりも優れたパフォーマンスを発揮する。 また,運動量アルゴリズムとAdamを組み合わせたSAGを提案する。
  論文  参考訳（メタデータ） (2023-07-27T17:34:26Z)
• Efficient computation of the Knowledge Gradient for Bayesian Optimization [1.0497128347190048]
  One-shot Hybrid KGは、これまで提案されていたアイデアをいくつか組み合わせた新しいアプローチであり、計算が安価で、強力で効率的である。 すべての実験はBOTorchで実施され、同等または改善された性能で計算オーバーヘッドを劇的に削減した。
  論文  参考訳（メタデータ） (2022-09-30T10:39:38Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Revisiting Bayesian Optimization in the light of the COCO benchmark [1.4467794332678539]
  本稿では,共通かつあまり一般的ではない設計選択のbo(gaussian process based)の性能への影響について,大規模な調査を行う。 この研究のために開発されたコードは、RパッケージDiceOptimの新バージョン(v2.1.1)をCRANで利用可能にしている。
  論文  参考訳（メタデータ） (2021-03-30T19:45:18Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。 本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
  論文  参考訳（メタデータ） (2021-01-25T01:49:10Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)

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

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