論文の概要: Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis
- arxiv url: http://arxiv.org/abs/2004.14724v3
- Date: Mon, 6 Sep 2021 11:43:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 05:44:38.276241
- Title: Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis
- Title（参考訳）: スパルシリティ制約下でベイズネットワークを学習する:パラメータ化複雑性解析
- Authors: Niels Gr\"uttemeier and Christian Komusiewicz
- Abstract要約: 本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
- 参考スコア（独自算出の注目度）: 7.99536002595393
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning the structure of an optimal Bayesian network
when additional constraints are posed on the network or on its moralized graph.
More precisely, we consider the constraint that the network or its moralized
graph are close, in terms of vertex or edge deletions, to a sparse graph class
$\Pi$. For example, we show that learning an optimal network whose moralized
graph has vertex deletion distance at most $k$ from a graph with maximum degree
1 can be computed in polynomial time when $k$ is constant. This extends
previous work that gave an algorithm with such a running time for the vertex
deletion distance to edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We
then show that further extensions or improvements are presumably impossible.
For example, we show that learning optimal networks where the network or its
moralized graph have maximum degree $2$ or connected components of size at most
$c$, $c\ge 3$, is NP-hard. Finally, we show that learning an optimal network
with at most $k$ edges in the moralized graph presumably has no $f(k)\cdot
|I|^{O(1)}$-time algorithm and that, in contrast, an optimal network with at
most $k$ arcs can be computed in $2^{O(k)}\cdot |I|^{O(1)}$ time where $|I|$ is
the total input size.
- Abstract（参考訳）: 本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
より正確には、ネットワークまたはそのモラル化されたグラフが頂点または辺削除の観点から、スパースグラフクラス$\pi$に近しいという制約を考える。
例えば、モラル化グラフが最大次数 1 のグラフから最大$k$ の頂点削除距離を持つ最適なネットワークを学習することは、$k$ が定数である多項式時間で計算できることを示す。
これは、頂点削除距離をエッジレスグラフ [korhonen & parviainen, nips 2015] に走らせるようなアルゴリズムを与える以前の作業を拡張している。
次に、さらなる拡張や改善はおそらく不可能であることを示す。
例えば、ネットワークまたはそのモラル化されたグラフが最大2ドルまたは連結されたコンポーネントが最大$c$,$c\ge 3$である最適ネットワークの学習はNPハードであることを示す。
最後に、モラル化されたグラフにおいて、少なくとも$k$のエッジを持つ最適ネットワークを学習するには、おそらく$f(k)\cdot |I|^{O(1)}$-timeアルゴリズムが存在しないことを示し、対照的に、$k$のアークを持つ最適ネットワークは、$|I|$が全入力サイズである場合、$2^{O(k)}\cdot |I|^{O(1)}$ timeで計算できることを示した。
関連論文リスト
- Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文 参考訳（メタデータ） (2023-05-25T22:27:42Z) - Random Projection Forest Initialization for Graph Convolutional Networks [0.6554326244334866]
グラフ畳み込みネットワーク(GCN)は、グラフのような非構造化データにディープラーニングを拡張するための大きなステップであった。
ランダムプロジェクションフォレスト(rpForest)を用いたグラフの構築とGCNの初期化を行う新しい方法を提案する。
rpForestを使えば、さまざまな重要度を示すエッジに様々な重みを割り当てることができ、学習が促進されます。
論文 参考訳（メタデータ） (2023-02-22T11:49:19Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with
Feedback Graphs [34.37963000493442]
本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。
両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
論文 参考訳（メタデータ） (2022-06-02T05:01:40Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Maximizing Influence of Leaders in Social Networks [15.05158252504978]
我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。
提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
論文 参考訳（メタデータ） (2021-06-11T02:31:46Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。