論文の概要: 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ハードである。 実際には、モンテカルロサンプリング法を用いて、特に大規模において高忠実度予測を得るために大量の実行を必要とする影響をしばしば推定する。 したがって,サンプリング手法の代替として解析技術を開発することが望ましい。 本稿では、スケーラブルな動的メッセージパッシングアプローチに基づく、一般的な独立カスケードモデルにおける影響関数の推定アルゴリズムを提案する。 この手法は、単一のモンテカルロシミュレーションの計算複雑性を持ち、一般的なグラフ上の期待展開の上界を提供し、木のようなネットワークに対して正確な答えを与える。 また,線形しきい値モデルの確率バージョンに対する動的メッセージパッシング方程式も提供する。 その結果、シミュレーションベースの技術と比較して、実行時間内で潜在的に大きなサンプリング係数が節約されるため、大規模な問題インスタンスへの対処が可能になる。

関連論文リスト

• High-dimensional prediction for count response via sparse exponential weights [0.0]
  本稿では,高次元カウントデータ予測のための新しい確率的機械学習フレームワークを提案する。 重要な貢献は、データ予測をカウントするために調整された新しいリスク尺度であり、PAC-ベイズ境界を用いた予測リスクの理論的な保証である。 以上の結果から,非漸近性オラクルの不等式や,空間性に関する事前知識を伴わない速度-最適予測誤差が示唆された。
  論文  参考訳（メタデータ） (2024-10-20T12:45:42Z)
• A sparse PAC-Bayesian approach for high-dimensional quantile prediction [0.0]
  本稿では,高次元量子化予測のための確率論的機械学習手法を提案する。 擬似ベイズ的フレームワークとスケールした学生tとランゲヴィン・モンテカルロを併用して効率的な計算を行う。 その効果はシミュレーションや実世界のデータを通じて検証され、そこでは確立された頻繁な手法やベイズ的手法と競合する。
  論文  参考訳（メタデータ） (2024-09-03T08:01:01Z)
• Estimating Causal Effects from Learned Causal Networks [56.14597641617531]
  本稿では、離散可観測変数に対する因果影響クエリに応答する代替パラダイムを提案する。 観測データから直接因果ベイズネットワークとその共起潜伏変数を学習する。 本手法は, 推定手法よりも有効であることを示す。
  論文  参考訳（メタデータ） (2024-08-26T08:39:09Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。 理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。 シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
  論文  参考訳（メタデータ） (2023-06-05T21:08:34Z)
• 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)
• 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)

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

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