論文の概要: Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network

• arxiv url: http://arxiv.org/abs/2006.06926v6
• Date: Fri, 14 Feb 2025 02:26:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:46:44.207285
• Title: Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network
• Title（参考訳）: Decomposed Quadratization: ベイズネットワーク学習のための効率的なQUBO定式化
• Authors: Yuta Shikuri,
• Abstract要約: 目的関数で使用されるバイナリ変数の数を最小限にすることが不可欠である。 そこで本研究では,従来の二次化手法よりもビット容量に有利なQUBOの定式化を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on $16$ instances, ranging from $37$ to $223$ variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.
• Abstract（参考訳）: 二次非制約二元最適化(QUBO)問題を解くアルゴリズムとハードウェアは、近年大きな進歩を遂げている。 この進歩は、組合せ最適化問題を二次多項式として定式化することに焦点を当てている。 大規模QUBO問題の解法の性能向上のためには,目的関数で使用されるバイナリ変数の数を最小限に抑えることが不可欠である。 本稿では,従来の四元化手法に比較して,ビット容量に有利なQUBOの定式化を提案する。 鍵となる応用として、この定式化はスコアベースのベイズネットワーク構造学習に必要なバイナリ変数の数を大幅に削減する。 16ドルインスタンスの実験的結果(37ドルから223ドルまで)は、我々のアプローチでは、桁違いの四量化よりもバイナリ変数が少なくなることを実証している。 さらに, 定式化を実装したアニール装置は, スコア最大化において, 既存のアルゴリズムよりも優れていた。

関連論文リスト

• A Simplification Method for Inequality Constraints in Integer Binary Encoding HOBO Formulations [0.0]
  提案手法は,擬似非拘束バイナリ最適化(QUBO)の定式化に伴う課題に対処する。 制約を効率的に統合することにより、量子および古典的解法の計算効率と精度を高めることができる。
  論文  参考訳（メタデータ） (2025-01-16T17:06:25Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。 しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
  論文  参考訳（メタデータ） (2022-10-20T14:54:37Z)
• Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction [104.41634756395545]
  具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。 FedBiOの複雑性は$O(epsilon-1.5)$である。 本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2022-05-03T16:40:22Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions [0.46040036610482665]
  より高次擬似ブール問題をQUBO形式に変換する方法を持つことは有用である。 本稿では, 加算変数数とペナルティ係数を最小化することにより, 既存の立方体-四方体変換法を改善する。
  論文  参考訳（メタデータ） (2021-07-24T22:13:42Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Computational Overhead of Locality Reduction in Binary Optimization Problems [0.0]
  本稿では,2つの局所的(二次的)コスト関数のみに対応可能な解法の大部分に必要な局所性低減の効果について論じる。 Microsoft Azure Quantumのモンテカルロ並列解法を用いて、2つの局所表現へのポスト還元により、問題の解決がかなり困難になることを示す。
  論文  参考訳（メタデータ） (2020-12-17T15:49:55Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。 通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-27T07:15:25Z)

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

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