論文の概要: Online Influence Maximization under Linear Threshold Model

• arxiv url: http://arxiv.org/abs/2011.06378v3
• Date: Sun, 25 Apr 2021 04:51:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-26 07:42:33.233565
• Title: Online Influence Maximization under Linear Threshold Model
• Title（参考訳）: 線形閾値モデルに基づくオンライン影響最大化
• Authors: Shuai Li, Fang Kong, Kejie Tang, Qizhi Li, Wei Chen
• Abstract要約: オンライン・インフルエンス(OIM)は、影響力伝達モデルパラメータを学習するソーシャル・ネットワークにおいて一般的な問題である。 本稿では,線形しきい値(LT)モデルでOIMに対処する。 群観察変調された性質滑らか性(GOM)を証明することにより、次数 $tildeO(mathrmpoly(m)sqrtT)$ を後悔する。 また,モデルに依存しない,O(mathrmpoly(m) T2/3)$という残差を持つOIM-ETCアルゴリズムも提供する。
• 参考スコア（独自算出の注目度）: 17.06633823730587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online influence maximization (OIM) is a popular problem in social networks to learn influence propagation model parameters and maximize the influence spread at the same time. Most previous studies focus on the independent cascade (IC) model under the edge-level feedback. In this paper, we address OIM in the linear threshold (LT) model. Because node activations in the LT model are due to the aggregated effect of all active neighbors, it is more natural to model OIM with the node-level feedback. And this brings new challenge in online learning since we only observe aggregated effect from groups of nodes and the groups are also random. Based on the linear structure in node activations, we incorporate ideas from linear bandits and design an algorithm LT-LinUCB that is consistent with the observed feedback. By proving group observation modulated (GOM) bounded smoothness property, a novel result of the influence difference in terms of the random observations, we provide a regret of order $\tilde{O}(\mathrm{poly}(m)\sqrt{T})$, where $m$ is the number of edges and $T$ is the number of rounds. This is the first theoretical result in such order for OIM under the LT model. In the end, we also provide an algorithm OIM-ETC with regret bound $O(\mathrm{poly}(m)\ T^{2/3})$, which is model-independent, simple and has less requirement on online feedback and offline computation.
• Abstract（参考訳）: オンライン影響最大化(OIM)は、影響伝播モデルパラメータを学習し、同時に拡散する影響を最大化するソーシャルネットワークで一般的な問題である。 これまでのほとんどの研究は、エッジレベルのフィードバックの下で独立カスケード(IC)モデルに焦点を当てていた。 本稿では,線形しきい値(LT)モデルでOIMに対処する。 LTモデルのノードアクティベーションは、すべてのアクティブな隣人の集合効果に起因するため、ノードレベルのフィードバックでOIMをモデル化することはより自然である。 これは、ノードのグループによる集約効果のみを観察し、グループもランダムであるため、オンライン学習に新たな課題をもたらします。 ノードアクティベーションにおける線形構造に基づいて、線形帯域のアイデアを取り入れ、観測されたフィードバックに整合したアルゴリズムLT-LinUCBを設計する。 群観測変調(gom)有界な平滑性特性の証明により、ランダム観測による影響差の新たな結果として、$m$ がエッジ数、$t$ がラウンド数である$\tilde{o}(\mathrm{poly}(m)\sqrt{t})$ が与えられる。 これは、LTモデルの下でのOIMに対する最初の理論的結果である。 最終的に、OIM-ETCアルゴリズムは、O(\mathrm{poly}(m)\ T^{2/3})$で、モデルに依存しず、単純で、オンラインのフィードバックやオフラインの計算に必要のない。

関連論文リスト

• Zeroth-Order Adaptive Neuron Alignment Based Pruning without Re-Training [3.195234044113248]
  我々は、高密度事前学習モデルの関数情報を利用して、アクティベーションのアライメントw.r.tを最大化するスパースモデルを得る。 我々は,アクティベーション間のニューロンアライメントを最大化するために,ブロックワイドと行ワイドの間隔比を変更するエンフェップアップアルゴリズムであるtextscNeuroAlを提案する。 提案手法は,4つの異なるLLMファミリーと3つの異なる空間比で検証し,最新の最先端技術よりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2024-11-11T15:30:16Z)
• Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons [79.98542868281473]
  RLHF(Reinforcement Learning with Human Feedback)の理論的枠組みを提供する。 学習した報酬モデルに基づいてポリシーをトレーニングする際、MLEは失敗し、悲観的なMLEは特定のカバレッジ仮定の下で性能を改善したポリシーを提供する。
  論文  参考訳（メタデータ） (2023-01-26T18:07:21Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver [32.212146650873194]
  報酬信号のガイダンスを使わずにRLモデルを効率的に学習するためのアプローチを提案する。 特に、私たちは、探索フェーズにおけるモデル学習に集中するプラグインソルバアプローチを採用しています。 新たな探索アルゴリズムを確立することで,プラグインアプローチは環境との相互作用を$tildeO(d2H3/epsilon2)$とすることでモデルを学習することを示す。
  論文  参考訳（メタデータ） (2021-10-07T07:59:50Z)
• Online Learning of Independent Cascade Models with Node-level Feedback [1.52292571922932]
  本稿では,ノードレベルのフィードバック下での独立カスケードモデルに対するオンライン学習問題を詳細に解析する。 既存のICモデルの作業は、エージェントが観測されたすべてのエッジの明確な結果を知っているエッジレベルのフィードバックモデルにのみ光を当てている。 我々は,ICモデルに対する理論的後悔とエッジレベルのフィードバックとを一致させて,$mathcalO( sqrtT)$の累積後悔を実現するオンラインアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-09-06T14:51:54Z)
• Momentum Pseudo-Labeling for Semi-Supervised Speech Recognition [55.362258027878966]
  本稿では,半教師付き音声認識のための簡易かつ効果的な手法として,モーメント擬似ラベル(MPL)を提案する。 MPLは、平均的な教師メソッドにインスパイアされて、相互に相互作用し、学習するオンラインとオフラインの2つのモデルで構成されている。 実験の結果,MPLはベースモデルよりも効果的に改善され,様々な半教師付きシナリオに拡張可能であることが示された。
  論文  参考訳（メタデータ） (2021-06-16T16:24:55Z)
• Model-based Reinforcement Learning for Continuous Control with Posterior Sampling [10.91557009257615]
  連続状態空間における強化学習(PSRL)のためのモデルベース後方サンプリングについて検討した。 MPC-PSRLはモデルに基づく後部サンプリングアルゴリズムであり,行動選択のためのモデル予測制御を行う。
  論文  参考訳（メタデータ） (2020-11-20T21:00:31Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)
• Logistic-Regression with peer-group effects via inference in higher order Ising models [36.89034666809275]
  我々は、これらの拡張を高階の十分な統計量を持つモデルに適用し、ピアグループ効果を持つソーシャルネットワーク上でのモデリング行動について検討する。 MPLE (Maximum Pseudo-Likelihood Estimator) に対する$sqrtd/n$の統計的誤差率を示す。 我々のモデルは、最近の研究で研究されているベニラロジスティック回帰とピアエフェクトモデルを一般化し、これらの結果を高次相互作用に対応するように拡張する。
  論文  参考訳（メタデータ） (2020-03-18T15:02:47Z)

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

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