論文の概要: Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation

• arxiv url: http://arxiv.org/abs/2606.24672v1
• Date: Tue, 23 Jun 2026 15:04:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 22:16:49.022874
• Title: Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation
• Title（参考訳）: 確率的ブール関数評価のためのコスト最適決定図
• Authors: Xia Zong, Tuomo Lehtonen, Jussi Rintanen,
• Abstract要約: 本稿では,変数選択,プルーニング,キャッシングを含む分岐とバウンドのアルゴリズムを提案する。 ランダムなインスタンスの実験はスケーラビリティを実証し、グレディビーム探索変種(英語版)の効率-品質トレードオフを定量化する。 この問題は$#P$-hardで$mathrmSPACEP$に含まれることを証明します。
• 参考スコア（独自算出の注目度）: 4.473327661758546
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many decision-making scenarios, acquiring information incurs different costs. We consider the problem of constructing a deterministic evaluation strategy that minimizes the expected cost of evaluating a propositional formula under variable costs and a probability distribution over truth assignments. We present a branch-and-bound algorithm with variable-selection heuristics, pruning, and caching. To the best of our knowledge, it is the first practical exact algorithm for this level of generality. Experiments on random instances demonstrate scalability and quantify the efficiency-quality trade-off of a greedy beam-search variant. We additionally evaluate a structured heart-disease diagnosis instance. Finally, we prove that the problem is $\#P$-hard and contained in $\mathrm{PSPACE}$.
• Abstract（参考訳）: 多くの意思決定シナリオでは、情報の取得は異なるコストを発生させる。 本稿では,提案式を可変コストで評価することの期待されるコストを最小化し,真理問題に対する確率分布を推定する決定論的評価戦略を構築することの問題点を考察する。 本稿では,変数選択ヒューリスティックス,プルーニング,キャッシングを用いた分岐結合アルゴリズムを提案する。 我々の知る限りでは、これはこのレベルの一般化のための最初の実用的な正確なアルゴリズムである。 ランダムなインスタンスの実験はスケーラビリティを実証し、グレディビーム探索変種(英語版)の効率-品質トレードオフを定量化する。 また, 心不全診断症例も検討した。 最後に、問題は$\#P$-hardであり、$\mathrm{PSPACE}$に含まれることを証明します。

関連論文リスト

• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  我々は、この問題を*予算付きヘテロスケダティックなマルチジャッジ推定*として定式化する。 K$のプロンプト-レスポンスペア、J$の既知のコストと未知のクエリ-ジャッジ分散が与えられた場合、目標は、$ell_p$-errorを最小化しながら、有界スコアベクトルを推定することである。 EST-IVWEは,予算の低次項までのオラクルIVWEレートと一致していることを示す。
  論文  参考訳（メタデータ） (2026-05-22T08:26:08Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs [3.1269598124014264]
  ランダムで未知のコストでBOCVS問題を拡張するための新しいアルゴリズムを提案する。 提案アルゴリズムは,BOCVS問題の目的を従来よりも効果的に解決し,品質的後悔とコスト的後悔の両面において,サブ線形率を達成する。
  論文  参考訳（メタデータ） (2024-12-20T13:00:39Z)
• A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization [4.608510640547952]
  我々は、Dy Searchのほぼ最適最適化誤差を保証する。 誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
  論文  参考訳（メタデータ） (2022-08-13T19:57:04Z)
• Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
  本稿では,軽度条件下での有限個の判定問題に対して,対話型意思決定のための最初のインスタンス最適化アルゴリズムを設計する。 本研究の結果は, 具体的問題に着目し, 多腕バンディットの古典的ギャップ依存境界と, 線形バンディットに関する先行研究を復元した。
  論文  参考訳（メタデータ） (2022-06-06T02:56:10Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Distributionally Robust Optimization with Markovian Data [8.126833795693699]
  本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。 本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
  論文  参考訳（メタデータ） (2021-06-12T10:59:02Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)

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

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