論文の概要: Bayesian Inference of Random Dot Product Graphs via Conic Programming
- arxiv url: http://arxiv.org/abs/2101.02180v1
- Date: Wed, 6 Jan 2021 18:29:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-11 03:30:24.271147
- Title: Bayesian Inference of Random Dot Product Graphs via Conic Programming
- Title(参考訳): コーニックプログラミングによるランダムドット製品グラフのベイズ推定
- Authors: David Wu, David R. Palmer, Daryl R. Deford
- Abstract要約: 本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定する凸コーンプログラムを提案する。
また、この手法がケイトクラブグラフと米国上院の投票グラフの潜在構造を復元することを示した。
- 参考スコア(独自算出の注目度): 1.7188280334580195
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a convex cone program to infer the latent probability matrix of a
random dot product graph (RDPG). The optimization problem maximizes the
Bernoulli maximum likelihood function with an added nuclear norm regularization
term. The dual problem has a particularly nice form, related to the well-known
semidefinite program relaxation of the MaxCut problem. Using the primal-dual
optimality conditions, we bound the entries and rank of the primal and dual
solutions. Furthermore, we bound the optimal objective value and prove
asymptotic consistency of the probability estimates of a slightly modified
model under mild technical assumptions. Our experiments on synthetic RDPGs not
only recover natural clusters, but also reveal the underlying low-dimensional
geometry of the original data. We also demonstrate that the method recovers
latent structure in the Karate Club Graph and synthetic U.S. Senate vote graphs
and is scalable to graphs with up to a few hundred nodes.
- Abstract(参考訳): 本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定するための凸錐プログラムを提案する。
最適化問題は、追加の核ノルム正規化項でベルヌーイ最大度関数を最大化する。
双対問題は、MaxCut問題のよく知られた半定値プログラム緩和に関連して、特によい形式を持つ。
原始双対最適性条件を用いて、原始解と双対解のエントリとランクを制限した。
さらに, 最適目的値を限定し, 軽度な技術的仮定の下で, わずかに修正されたモデルの確率推定の漸近的一貫性を証明した。
RDPGの合成実験は、自然クラスターを復元するだけでなく、元のデータの低次元形状も明らかにする。
また,この手法は,空手クラブグラフとアメリカ合衆国上院世論投票グラフの潜在構造を復元し,数百ノードまでのグラフに拡張可能であることを実証した。
関連論文リスト
- Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。
ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文 参考訳(メタデータ) (2024-10-24T19:57:56Z) - Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳(メタデータ) (2024-09-24T04:39:47Z) - Graph Matching via convex relaxation to the simplex [5.355990925686151]
本稿では,2つの入力グラフの最適アライメントを求めるグラフマッチング問題に対処する。
この問題に対処するための一般的なアプローチは、NP-hard emphQuadratic Assignment Problem (QAP) の凸緩和である。
単位単純度に新しい凸緩和を導入し、この問題を解決するための閉形式反復を用いた効率的なミラー降下スキームを開発する。
論文 参考訳(メタデータ) (2023-10-31T16:44:26Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳(メタデータ) (2023-02-08T08:17:43Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained
Graphical Models? [13.572602792770288]
ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。
我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
論文 参考訳(メタデータ) (2020-06-26T12:06:10Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳(メタデータ) (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。