論文の概要: Efficient Bayesian Network Structure Learning via Parameterized Local
Search on Topological Orderings
- arxiv url: http://arxiv.org/abs/2204.02902v1
- Date: Wed, 6 Apr 2022 15:38:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-07 18:15:39.653675
- Title: Efficient Bayesian Network Structure Learning via Parameterized Local
Search on Topological Orderings
- Title（参考訳）: 位相順序のパラメータ化局所探索による効率よいベイズネットワーク構造学習
- Authors: Niels Gr\"uttemeier, Christian Komusiewicz, Nils Morawietz
- Abstract要約: そこでは,変数のトポロジ的順序付けによって解を記述する。
このようなトポロジカル順序が与えられた場合、サブ指数FPT時間における逆距離$r$の最適DAGを計算することができる。
また、「ウィンドウ反転距離」と呼ばれる関連する距離を導入し、それに対応する局所探索問題もFPT時間で解けることを示す。
- 参考スコア（独自算出の注目度）: 10.635248457021495
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In Bayesian Network Structure Learning (BNSL), one is given a variable set
and parent scores for each variable and aims to compute a DAG, called Bayesian
network, that maximizes the sum of parent scores, possibly under some
structural constraints. Even very restricted special cases of BNSL are
computationally hard, and, thus, in practice heuristics such as local search
are used. A natural approach for a local search algorithm is a hill climbing
strategy, where one replaces a given BNSL solution by a better solution within
some pre-defined neighborhood as long as this is possible. We study
ordering-based local search, where a solution is described via a topological
ordering of the variables. We show that given such a topological ordering, one
can compute an optimal DAG whose ordering is within inversion distance $r$ in
subexponential FPT time; the parameter $r$ allows to balance between solution
quality and running time of the local search algorithm. This running time bound
can be achieved for BNSL without structural constraints and for all structural
constraints that can be expressed via a sum of weights that are associated with
each parent set. We also introduce a related distance called `window inversions
distance' and show that the corresponding local search problem can also be
solved in subexponential FPT time for the parameter $r$. For two further
natural modification operations on the variable orderings, we show that
algorithms with an FPT time for $r$ are unlikely. We also outline the limits of
ordering-based local search by showing that it cannot be used for common
structural constraints on the moralized graph of the network.
- Abstract（参考訳）: ベイズネットワーク構造学習(英: bayesian network structure learning、bnsl)では、各変数に対して変数セットと親スコアが与えられ、おそらくいくつかの構造制約の下で親スコアの和を最大化するベイズネットワーク(英: bayesian network)と呼ばれるdagの計算を目指している。
BNSLの非常に制限された特別な場合でさえ計算が困難であり、実際は局所探索のようなヒューリスティックな手法が用いられる。
局所探索アルゴリズムの自然なアプローチはヒルクライミング戦略であり、ある所与のBNSL解を、それが可能である限り、定義済みの近傍でより良い解に置き換えるものである。
本研究では,変数の位相的順序付けによって解を記述する順序に基づく局所探索について検討する。
このような位相的順序を与えられた場合、局所探索アルゴリズムの解の質と実行時間のバランスをとることができるパラメータ $r$ は、最小指数 fpt 時間で逆距離 $r$ 内にある最適な dag を計算することができる。
この実行時間制限は、構造的制約を伴わないbnslと、各親集合に関連付けられた重みの和によって表現できる全ての構造的制約に対して達成することができる。
また, 'window inversions distance' と呼ばれる関連する距離を導入し,パラメータ $r$ の副指数 fpt 時間で対応する局所探索問題も解くことができることを示した。
変数順序付けに関する2つの自然な修正操作に対して、FPT時間$r$のアルゴリズムは不可能であることを示す。
また,ネットワークのモラル化グラフにおける共通の構造制約には使用できないことを示すことにより,順序付けに基づく局所探索の限界を概説する。
関連論文リスト
- Pathfinding with Lazy Successor Generation [12.02023514105999]
位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。
単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。
そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
論文 参考訳（メタデータ） (2024-08-27T23:25:25Z) - Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - Learning nonparametric DAGs with incremental information via high-order
HSIC [13.061477915002767]
そこで本研究では,DAGを同定するために,親の判断したサブセットに基づく識別可能性条件を提案する。
最適相では、一階のヒルベルト最適独立基準(HSIC)に基づく最適化問題により、推定骨格が初期決定された親部分集合として与えられる。
チューニングフェーズでは、骨格は削除、追加、DAG形式化戦略によって局所的に調整される。
論文 参考訳（メタデータ） (2023-08-11T07:07:21Z) - OFA$^2$: A Multi-Objective Perspective for the Once-for-All Neural
Architecture Search [79.36688444492405]
once-for-All(OFA)は、異なるリソース制約を持つデバイスのための効率的なアーキテクチャを探索する問題に対処するために設計された、ニューラルネットワーク検索(NAS)フレームワークである。
我々は,探索段階を多目的最適化問題として明示的に考えることにより,効率の追求を一歩進めることを目指している。
論文 参考訳（メタデータ） (2023-03-23T21:30:29Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - CausNet : Generational orderings based search for optimal Bayesian
networks via dynamic programming with parent set constraints [5.7460673927330035]
動的プログラミングに基づくアルゴリズムを組込み次元削減と親集合同定により実装する。
これにより、探索空間が劇的に減少し、大規模データに適用できる。
合成データと実データの両方にアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2022-07-18T03:26:41Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳（メタデータ） (2021-06-14T13:01:46Z) - 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) - Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds [5.158632635415881]
最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である
CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
論文 参考訳（メタデータ） (2021-04-18T07:46:28Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。