論文の概要: Learning Bayesian Networks with Annealing Machine
- arxiv url: http://arxiv.org/abs/2006.06926v4
- Date: Tue, 8 Aug 2023 11:45:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-09 18:09:54.358513
- Title: Learning Bayesian Networks with Annealing Machine
- Title(参考訳): アニーリングマシンによるベイズネットワークの学習
- Authors: Yuta Shikuri
- Abstract要約: アニーリングマシンは、スコアベースのベイズネットワーク構造学習に適用できる可能性がある。
候補となる親集合を高度に同定した効率的な変換法を提案する。
提案手法は,第4世代の富士通デジタルアニールの100ドルKの容量よりも少ない。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent studies have reported that annealing machines are capable of solving
combinatorial optimization problems with high accuracy. Annealing machines can
potentially be applied to score-based Bayesian network structure learning.
However, the bit capacity of an annealing machine is currently limited. To
utilize the annealing technology, converting score-based learning problems into
quadratic unconstrained binary optimizations within the bit capacity is
necessary. In this paper, we propose an efficient conversion method with the
advanced identification of candidate parent sets and their decomposition. We
also provide an integer programming problem to find the decomposition that
minimizes the number of required bits. Experimental results on $7$ benchmark
datasets with variables from $75$ to $223$ show that our approach requires less
bits than the $100$K bit capacity of the fourth-generation Fujitsu Digital
Annealer, a fully coupled annealing machine developed with semiconductor
technology. Moreover, we demonstrate that the Digital Annealer with our
conversion method outperforms existing algorithms on score maximization. These
results highlight the utility of annealing processors in learning Bayesian
networks.
- Abstract(参考訳): 近年の研究では、アニーリングマシンは高い精度で組合せ最適化問題を解決することができると報告されている。
アニーリングマシンは、スコアベースのベイズネットワーク構造学習に応用できる可能性がある。
しかし、現在、アニール機のビット容量は制限されている。
このアニール技術を利用するには、スコアベースの学習問題をビット容量内の2次非制約バイナリ最適化に変換する必要がある。
本稿では,候補となる親集合の高度な同定と分解による効率的な変換手法を提案する。
また、必要なビット数を最小限に抑える分解を見つけるために整数プログラミング問題も提供する。
変数が75ドルから223ドルまでのベンチマークデータセットによる実験結果から,半導体技術で開発された完全結合型アニールマシンであるFujitsu Digital Annealerの100ドルKビット容量よりも,我々のアプローチではビット数が少なくなることがわかった。
さらに,本手法によるディジタルアニーラは,既存のアルゴリズムよりもスコア最大化に優れることを示す。
これらの結果はベイズネットワーク学習におけるアニールプロセッサの有用性を強調した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。