論文の概要: Scalable Influence Estimation Without Sampling
- arxiv url: http://arxiv.org/abs/1912.12749v1
- Date: Sun, 29 Dec 2019 22:15:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-17 08:03:04.864191
- Title: Scalable Influence Estimation Without Sampling
- Title(参考訳): サンプリングなしのスケーラブルな影響推定
- Authors: Andrey Y. Lokhov, David Saad
- Abstract要約: ネットワーク上の拡散過程では、初期スプレッドラーの集合に影響を受けるノードがいくつあると期待されているか?
本稿では、スケーラブルな動的メッセージパッシングアプローチに基づいて、一般的な独立モデルにおける影響関数を推定するアルゴリズムを提案する。
また、線形しきい値モデルのバージョンに対する動的メッセージパッシング方程式も提供する。
- 参考スコア(独自算出の注目度): 9.873635079670091
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a diffusion process on a network, how many nodes are expected to be
influenced by a set of initial spreaders? This natural problem, often referred
to as influence estimation, boils down to computing the marginal probability
that a given node is active at a given time when the process starts from
specified initial condition. Among many other applications, this task is
crucial for a well-studied problem of influence maximization: finding optimal
spreaders in a social network that maximize the influence spread by a certain
time horizon. Indeed, influence estimation needs to be called multiple times
for comparing candidate seed sets. Unfortunately, in many models of interest an
exact computation of marginals is #P-hard. In practice, influence is often
estimated using Monte-Carlo sampling methods that require a large number of
runs for obtaining a high-fidelity prediction, especially at large times. It is
thus desirable to develop analytic techniques as an alternative to sampling
methods. Here, we suggest an algorithm for estimating the influence function in
popular independent cascade model based on a scalable dynamic message-passing
approach. This method has a computational complexity of a single Monte-Carlo
simulation and provides an upper bound on the expected spread on a general
graph, yielding exact answer for treelike networks. We also provide dynamic
message-passing equations for a stochastic version of the linear threshold
model. The resulting saving of a potentially large sampling factor in the
running time compared to simulation-based techniques hence makes it possible to
address large-scale problem instances.
- Abstract(参考訳): ネットワーク上の拡散過程では、初期スプレッドラーの集合に影響を受けるノードがいくつあると期待されているか?
この自然問題は、しばしば影響推定(英語版)と呼ばれ、プロセスが指定された初期状態から始まるある時点であるノードがアクティブであるという限界確率を計算しようとする。
他の多くのアプリケーションでは、このタスクは影響力の最大化に関するよく研究された問題、つまり特定の時間軸によって広がる影響を最大化するソーシャルネットワークにおける最適なスプレッダーを見つけるために不可欠である。
実際、影響推定は候補シードセットを比較するために複数回呼び出す必要がある。
残念なことに、多くの興味のあるモデルでは、マージンの正確な計算は#pハードである。
実際には、モンテカルロサンプリング法を用いて、特に大規模において高忠実度予測を得るために大量の実行を必要とする影響をしばしば推定する。
したがって,サンプリング手法の代替として解析技術を開発することが望ましい。
本稿では、スケーラブルな動的メッセージパッシングアプローチに基づく、一般的な独立カスケードモデルにおける影響関数の推定アルゴリズムを提案する。
この手法は、単一のモンテカルロシミュレーションの計算複雑性を持ち、一般的なグラフ上の期待展開の上界を提供し、木のようなネットワークに対して正確な答えを与える。
また,線形しきい値モデルの確率バージョンに対する動的メッセージパッシング方程式も提供する。
その結果、シミュレーションベースの技術と比較して、実行時間内で潜在的に大きなサンプリング係数が節約されるため、大規模な問題インスタンスへの対処が可能になる。
関連論文リスト
- Deep Ensembles Meets Quantile Regression: Uncertainty-aware Imputation
for Time Series [49.992908221544624]
時系列データは、しばしば多くの欠落した値を示し、これは時系列計算タスクである。
従来の深層学習法は時系列計算に有効であることが示されている。
本研究では,不確実性のある高精度な計算を行う非生成時系列計算法を提案する。
論文 参考訳(メタデータ) (2023-12-03T05:52:30Z) - Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood
Estimation for Latent Gaussian Models [69.22568644711113]
我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。
理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。
シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
論文 参考訳(メタデータ) (2023-06-05T21:08:34Z) - Efficient distributed representations beyond negative sampling [4.5687771576879594]
本稿では,分散表現を効率よく学習する手法について述べる。
我々は,sotfmax正規化定数を線形時間で推定でき,効率的な最適化戦略を設計できることを示した。
論文 参考訳(メタデータ) (2023-03-30T15:48:26Z) - Approximate Gibbs Sampler for Efficient Inference of Hierarchical Bayesian Models for Grouped Count Data [0.0]
本研究は、推定精度を維持しつつ、HBPRMを効率的に学習するための近似ギブスサンプリング器(AGS)を開発した。
実データと合成データを用いた数値実験により,AGSの優れた性能を示した。
論文 参考訳(メタデータ) (2022-11-28T21:00:55Z) - FaDIn: Fast Discretized Inference for Hawkes Processes with General
Parametric Kernels [82.53569355337586]
この研究は、有限なサポートを持つ一般パラメトリックカーネルを用いた時間点プロセス推論の効率的な解を提供する。
脳磁図(MEG)により記録された脳信号からの刺激誘発パターンの発生をモデル化し,その有効性を評価する。
その結果,提案手法により,最先端技術よりもパターン遅延の推定精度が向上することが示唆された。
論文 参考訳(メタデータ) (2022-10-10T12:35:02Z) - Sampling Approximately Low-Rank Ising Models: MCMC meets Variational
Methods [35.24886589614034]
一般相互作用が$J$である超キューブ上の二次定値イジングモデルを考える。
我々の一般的な結果は、低ランクのIsingモデルに対する最初のサンプリングアルゴリズムを示唆している。
論文 参考訳(メタデータ) (2022-02-17T21:43:50Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳(メタデータ) (2021-12-07T11:26:41Z) - Fast Bayesian Estimation of Spatial Count Data Models [0.0]
シミュレーション問題ではなく最適化問題として変分ベイズ(VB)を導入する。
VB法は、観測されていないパラメータと空間依存性を持つ負二項モデルにおける後部推論のために導出される。
VBアプローチは、シミュレーションと経験的研究において、通常の8コアプロセッサ上でのMCMCの約45倍から50倍高速である。
論文 参考訳(メタデータ) (2020-07-07T10:24:45Z) - Slice Sampling for General Completely Random Measures [74.24975039689893]
本稿では, 後続推定のためのマルコフ連鎖モンテカルロアルゴリズムについて, 補助スライス変数を用いてトランケーションレベルを適応的に設定する。
提案アルゴリズムの有効性は、いくつかの一般的な非パラメトリックモデルで評価される。
論文 参考訳(メタデータ) (2020-06-24T17:53:53Z) - Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
高速後部サンプリングのための簡易かつ汎用的なアプローチを提案する。
分離されたサンプルパスがガウス過程の後部を通常のコストのごく一部で正確に表現する方法を実証する。
論文 参考訳(メタデータ) (2020-02-21T14:03:16Z) - A Deep Learning Algorithm for High-Dimensional Exploratory Item Factor
Analysis [0.0]
探索項目因子分析(IFA)のための深層学習に基づくVIアルゴリズムについて検討する。
提案手法は、探索型IFAのための重要重み付きオートエンコーダ(IWAE)と呼ばれる深層人工ニューラルネットワークモデルを適用する。
IWAEは標本サイズやIWサンプル数の増加に伴って,より正確な推定値が得られることを示す。
論文 参考訳(メタデータ) (2020-01-22T03:02:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。