論文の概要: Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization

• arxiv url: http://arxiv.org/abs/2505.11089v1
• Date: Fri, 16 May 2025 10:23:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-19 14:36:14.668946
• Title: Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization
• Title（参考訳）: サブモジュール差分最適化によるベイジアンネットワーク構造学習のための不正確なカラム生成
• Authors: Yiran Yang, Rui Chen,
• Abstract要約: 最先端のBNSLIPの定式化は、指数関数的に多くの変数と制約に悩まされる。 このような課題に対処するためのIPの標準的なアプローチは、行と列の生成テクニックを採用することである。 我々の行と列の生成アプローチは、最先端のスコアベースアプローチよりも高い品質のソリューションが得られることを示す。
• 参考スコア（独自算出の注目度）: 3.802887999217352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we consider a score-based Integer Programming (IP) approach for solving the Bayesian Network Structure Learning (BNSL) problem. State-of-the-art BNSL IP formulations suffer from the exponentially large number of variables and constraints. A standard approach in IP to address such challenges is to employ row and column generation techniques, which dynamically generate rows and columns, while the complex pricing problem remains a computational bottleneck for BNSL. For the general class of $\ell_0$-penalized likelihood scores, we show how the pricing problem can be reformulated as a difference of submodular optimization problem, and how the Difference of Convex Algorithm (DCA) can be applied as an inexact method to efficiently solve the pricing problems. Empirically, we show that, for continuous Gaussian data, our row and column generation approach yields solutions with higher quality than state-of-the-art score-based approaches, especially when the graph density increases, and achieves comparable performance against benchmark constraint-based and hybrid approaches, even when the graph size increases.
• Abstract（参考訳）: 本稿では,ベイジアンネットワーク構造学習(BNSL)問題を解決するためのスコアベース整数プログラミング(IP)手法を検討する。 最先端のBNSLIPの定式化は、指数関数的に多くの変数と制約に悩まされる。 このような問題に対処するためのIPの標準的なアプローチは、行と列を動的に生成する行と列の生成技術を採用することであるが、複雑な価格問題はBNSLの計算上のボトルネックのままである。 一般クラスである$\ell_0$-penalized chance scoresに対して、サブモジュラー最適化問題の差分として価格問題を再構成し、不正確な方法として凸アルゴリズムの差分(DCA)を適用して価格問題を効率的に解決する方法を示す。 実験により, 連続ガウスデータに対して, グラフ密度が大きくなると, 行と列の生成手法は, 最先端のスコアベースアプローチよりも高い品質の解が得られること, グラフサイズが大きくなると, ベンチマーク制約ベースおよびハイブリッドアプローチに対して同等の性能が得られることを示した。

関連論文リスト

• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  生成拡散モデルは、様々なクロスドメインアプリケーションで人気がある。 これらのモデルは複雑なネットワーク最適化問題に対処する上で有望である。 本稿では拡散モデルに基づく解生成という,拡散モデル生成のための新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-13T07:56:21Z)
• Machine Learning-Enhanced Ant Colony Optimization for Column Generation [5.82410475933163]
  列生成は、多数の変数や列を含む最適化問題を解決するための強力な手法である。 サブプロブレムから複数の高品質カラムを効率よく生成する機械学習強化アリコロニー最適化(MLACO)を提案する。
  論文  参考訳（メタデータ） (2024-04-23T01:00:09Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
  論文  参考訳（メタデータ） (2021-12-08T03:58:25Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。 本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。 最適ではないにもかかわらず、性能は桁違いに向上することを示す。 結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
  論文  参考訳（メタデータ） (2021-06-23T09:46:11Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)

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

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