論文の概要: Sample Complexity of Opinion Formation on Networks with Linear Regression Models
- arxiv url: http://arxiv.org/abs/2311.02349v2
- Date: Wed, 13 Nov 2024 02:03:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-14 19:24:31.380393
- Title: Sample Complexity of Opinion Formation on Networks with Linear Regression Models
- Title(参考訳): 線形回帰モデルを用いたネットワーク上のオピニオン形成のサンプル複雑度
- Authors: Haolin Liu, Rajmohan Rajaraman, Ravi Sundaram, Anil Vullikanti, Omer Wasim, Haifeng Xu,
- Abstract要約: ネットワークにおける意見収束のサンプル複雑性について検討する。
我々のフレームワークは、認識された意見形成ゲームに基づいて構築されている。
人工ネットワークと実世界のネットワークの実証結果は、我々の理論的な発見を強く支えている。
- 参考スコア(独自算出の注目度): 36.75032460874647
- License:
- Abstract: Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal resources, so as to avoid polarization and ensure community-wide convergence of opinion? To tackle such challenges, we initiate the study of sample complexity of opinion convergence in networks. Our framework is built on the recognized opinion formation game, where we regard the opinion of each agent as a data-derived model, unlike previous works that treat opinions as data-independent scalars. The opinion model for every agent is initially learned from its local samples and evolves game-theoretically as all agents communicate with neighbors and revise their models towards an equilibrium. Our focus is on the sample complexity needed to ensure that the opinions converge to an equilibrium such that the final model of every agent has low generalization error. Our paper has two main technical results. First, we present a novel polynomial time optimization framework to quantify the total sample complexity for arbitrary networks, when the underlying learning problem is (generalized) linear regression. Second, we leverage this optimization to study the network gain which measures the improvement of sample complexity when learning over a network compared to that in isolation. Towards this end, we derive network gain bounds for various network classes including cliques, star graphs, and random regular graphs. Additionally, our framework provides a method to study sample distribution within the network, suggesting that it is sufficient to allocate samples inversely to the degree. Empirical results on both synthetic and real-world networks strongly support our theoretical findings.
- Abstract(参考訳): ソーシャル・ネットワークが連携する地域社会において、新たなワクチンに対する意識を広めることを目指す公衆衛生担当者について検討する。
偏極を避け、コミュニティ全体の意見の収束を確保するために、最小限のリソースで情報を分配するにはどうすればいいのか?
このような課題に対処するために、ネットワークにおける意見収束のサンプル複雑性の研究を開始する。
このフレームワークは認識された意見形成ゲームに基づいて構築されており、各エージェントの意見は、従来の意見がデータに依存しないスカラーとして扱う作業とは異なり、データ由来のモデルとみなす。
全てのエージェントの意見モデルは、まずその局所的なサンプルから学習され、すべてのエージェントが隣人と通信し、彼らのモデルを均衡に向けて修正するため、ゲーム理論的に進化する。
我々の焦点は、すべてのエージェントの最終モデルが一般化誤差が低いように、意見が平衡に収束することを保証するために必要なサンプルの複雑さである。
我々の論文には2つの主要な技術的結果がある。
まず、基礎となる学習問題が(一般化)線形回帰である場合、任意のネットワークに対する全サンプルの複雑さを定量化する新しい多項式時間最適化フレームワークを提案する。
第2に、この最適化を活用して、ネットワーク上の学習におけるサンプルの複雑さの改善を分離して測定するネットワークゲインについて検討する。
この目的のために、クリッド、スターグラフ、ランダム正規グラフを含む様々なネットワーククラスに対するネットワークゲインバウンドを導出する。
さらに、本フレームワークは、ネットワーク内のサンプル分布を研究する方法を提供し、その程度に逆らってサンプルを割り当てるだけで十分であることを示す。
人工ネットワークと実世界のネットワークの実証結果は、我々の理論的な発見を強く支えている。
関連論文リスト
- Simplicity bias and optimization threshold in two-layer ReLU networks [24.43739371803548]
過度なパラメータ化にもかかわらず、ネットワークはトレーニングデータを補間するのではなく、より単純な解へと収束することを示す。
我々の分析は、ニューロンが特定の方向に向かっているいわゆる早期アライメントフェーズに依存しています。
論文 参考訳(メタデータ) (2024-10-03T09:58:57Z) - Improving Network Interpretability via Explanation Consistency Evaluation [56.14036428778861]
本稿では、より説明可能なアクティベーションヒートマップを取得し、同時にモデル性能を向上させるフレームワークを提案する。
具体的には、モデル学習において、トレーニングサンプルを適応的に重み付けするために、新しいメトリクス、すなわち説明整合性を導入する。
そこで,本フレームワークは,これらのトレーニングサンプルに深い注意を払ってモデル学習を促進する。
論文 参考訳(メタデータ) (2024-08-08T17:20:08Z) - Decentralized Learning Strategies for Estimation Error Minimization with Graph Neural Networks [94.2860766709971]
統計的に同一性を持つ無線ネットワークにおける自己回帰的マルコフ過程のサンプリングとリモート推定の課題に対処する。
我々のゴールは、分散化されたスケーラブルサンプリングおよび送信ポリシーを用いて、時間平均推定誤差と/または情報の年齢を最小化することである。
論文 参考訳(メタデータ) (2024-04-04T06:24:11Z) - Fitting Low-rank Models on Egocentrically Sampled Partial Networks [4.111899441919165]
本稿では,egocentricly sampled network に対する一般的な低ランクモデルに適合する手法を提案する。
この手法は、エゴセントリックな部分的ネットワーク推定に関する最初の理論的保証を提供する。
本手法を複数の合成および実世界のネットワーク上で評価し,リンク予測タスクにおいて競合性能を実現することを示す。
論文 参考訳(メタデータ) (2023-03-09T03:20:44Z) - An Information-Theoretic Framework for Supervised Learning [22.280001450122175]
後悔とサンプルの複雑さという独自の概念を持つ新しい情報理論フレームワークを提案する。
本稿では、ReLUアクティベーションユニットを用いたディープニューラルネットワークによって生成されたデータから学習する際のサンプルの複雑さについて検討する。
我々は、ランダムな単層ニューラルネットワークの実験的な解析により、理論結果を裏付けることで結論付ける。
論文 参考訳(メタデータ) (2022-03-01T05:58:28Z) - Transfer Learning In Differential Privacy's Hybrid-Model [10.584333748643774]
本研究では,キュレーターデータセット内のn個の個人を異なる分布から抽出するハイブリッドモデルにおいて,機械学習の問題点について検討する。
この移行学習問題に対する一般的なスキーム -- Subsample-Test-Reweigh -- を与えます。
論文 参考訳(メタデータ) (2022-01-28T09:54:54Z) - Anomaly Detection on Attributed Networks via Contrastive Self-Supervised
Learning [50.24174211654775]
本論文では,アトリビュートネットワーク上の異常検出のためのコントラスト型自己監視学習フレームワークを提案する。
このフレームワークは、新しいタイプのコントラストインスタンスペアをサンプリングすることで、ネットワークデータからのローカル情報を完全に活用します。
高次元特性と局所構造から情報埋め込みを学習するグラフニューラルネットワークに基づくコントラスト学習モデルを提案する。
論文 参考訳(メタデータ) (2021-02-27T03:17:20Z) - Estimating informativeness of samples with Smooth Unique Information [108.25192785062367]
サンプルが最終的な重みを知らせる量と、重みによって計算される関数を知らせる量を測定します。
線形化ネットワークを用いてこれらの量の効率的な近似を行う。
本稿では,データセットの要約など,いくつかの問題に適用する。
論文 参考訳(メタデータ) (2021-01-17T10:29:29Z) - Robust Finite Mixture Regression for Heterogeneous Targets [70.19798470463378]
本稿では,サンプルクラスタの探索と,複数の不完全な混合型ターゲットを同時にモデル化するFMRモデルを提案する。
我々は、高次元の学習フレームワークの下で、無症状のオラクルのパフォーマンス境界をモデルに提供します。
その結果,我々のモデルは最先端の性能を達成できることがわかった。
論文 参考訳(メタデータ) (2020-10-12T03:27:07Z) - Imbalanced Data Learning by Minority Class Augmentation using Capsule
Adversarial Networks [31.073558420480964]
本稿では,2つの同時手法を合体させて,不均衡な画像のバランスを回復する手法を提案する。
我々のモデルでは、生成的および識別的ネットワークは、新しい競争力のあるゲームをする。
カプセルGANの合体は、畳み込みGANと比較して非常に少ないパラメータで重なり合うクラスを認識するのに効果的である。
論文 参考訳(メタデータ) (2020-04-05T12:36:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。