論文の概要: Fast algorithms to improve fair information access in networks
- arxiv url: http://arxiv.org/abs/2409.03127v2
- Date: Wed, 19 Feb 2025 18:36:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-20 13:56:25.466825
- Title: Fast algorithms to improve fair information access in networks
- Title（参考訳）: ネットワークにおける公正情報アクセス改善のための高速アルゴリズム
- Authors: Dennis Robert Windham, Caroline J. Wendt, Alex Crane, Madelyn J Warr, Freda Shi, Sorelle A. Friedler, Blair D. Sullivan, Aaron Clauset,
- Abstract要約: ネットワーク上で$k$のシードノードを選択することで、アクティベーションの最小確率を最大化する問題を考える。
我々は,確率推定を必要としない新しいスケーラブルアルゴリズムを設計し,評価する。
6ドルドメインから引き出された174ドルのネットワークのベンチマークコーパスを新たに提供します。
- 参考スコア（独自算出の注目度）: 8.174758604182268
- License:
- Abstract: We consider the problem of selecting $k$ seed nodes in a network to maximize the minimum probability of activation under an independent cascade beginning at these seeds. The motivation is to promote fairness by ensuring that even the least advantaged members of the network have good access to information. Our problem can be viewed as a variant of the classic influence maximization objective, but it appears somewhat more difficult to solve: only heuristics are known. Moreover, the scalability of these methods is sharply constrained by the need to repeatedly estimate access probabilities. We design and evaluate a suite of $10$ new scalable algorithms which crucially do not require probability estimation. To facilitate comparison with the state-of-the-art, we make three more contributions which may be of broader interest. We introduce a principled method of selecting a pairwise information transmission parameter used in experimental evaluations, as well as a new performance metric which allows for comparison of algorithms across a range of values for the parameter $k$. Finally, we provide a new benchmark corpus of $174$ networks drawn from $6$ domains. Our algorithms retain most of the performance of the state-of-the-art while reducing running time by orders of magnitude. Specifically, a meta-learner approach is on average only $20\%$ less effective than the state-of-the-art on held-out data, but about $75-130$ times faster. Further, the meta-learner's performance exceeds the state-of the-art on about $20\%$ of networks, and the magnitude of its running time advantage is maintained on much larger networks.
- Abstract（参考訳）: ネットワーク上で$k$のシードノードを選択することで、これらのシードから始まる独立したカスケードの下でのアクティベーションの最小限の確率を最大化する。
このモチベーションは、ネットワークの最も有利なメンバーでさえ、情報にアクセスしやすくすることで公正性を促進することである。
我々の問題は、古典的な影響の最大化の目的の変種と見なすことができるが、解くのがやや難しく、ヒューリスティックスのみが知られている。
さらに、これらの手法のスケーラビリティは、繰り返しアクセス確率を見積もる必要性により、著しく制約される。
我々は,確率推定を必要としない新しいスケーラブルアルゴリズムを設計し,評価する。
最先端技術との比較を容易にするために、我々はさらに3つの貢献を行い、より広い関心を持つかもしれない。
実験評価に使用されるペアワイズ情報伝達パラメータを選択するための原理的手法と,パラメータ$k$の値の範囲でアルゴリズムの比較を可能にする新しい性能指標を提案する。
最後に、6ドルのドメインから引き出された174ドルのネットワークからなる新しいベンチマークコーパスを提供する。
我々のアルゴリズムは最先端の性能を保ちながら、実行時間を桁違いに減らしている。
具体的には、メタラーナーのアプローチは、最先端のデータよりも平均20～130ドル低いが、約75～130ドル高速である。
さらに、メタラーナーの性能は、約20 %のネットワークで最先端のネットワークを超え、そのランニングタイムのアドバンテージの規模は、はるかに大きなネットワークで維持される。
関連論文リスト
- A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。
ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。
理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
論文 参考訳（メタデータ） (2023-09-09T13:54:34Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Two Losses Are Better Than One: Faster Optimization Using a Cheaper
Proxy [6.170898159041277]
本稿では,関連関数をプロキシとして利用することにより,目的物を計算困難勾配で最小化するアルゴリズムを提案する。
我々のアルゴリズムは、$delta$-smooth目的の勾配降下に一致する速度で収束を保証する。
我々のアルゴリズムは機械学習に多くの可能性があり、合成データ、物理シミュレータ、混合公開データ、プライベートデータなどを活用するための原則化された手段を提供する。
論文 参考訳（メタデータ） (2023-02-07T15:50:49Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - FairGRAPE: Fairness-aware GRAdient Pruning mEthod for Face Attribute
Classification [4.909402570564468]
フェアネス対応型GRADient Pruning mEthod(FairGRAPE)を提案する。
本手法は,各モデルの重みの群ごとの重要度を算出し,プルーニングにおけるグループ間の総重要度を相対的に維持する重みのサブセットを選択する。
我々の手法は高い刈り取り率(99%)の設定において極めて効果的である。
論文 参考訳（メタデータ） (2022-07-22T05:44:03Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳（メタデータ） (2021-07-05T19:20:34Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Progressive Skeletonization: Trimming more fat from a network at
initialization [76.11947969140608]
本稿では,接続感度が最大となるスケルトン化ネットワークを提案する。
次に、目的を最大化する2つの近似手順を提案する。
提案手法は, 高い刈り込みレベルにおいて, 性能を著しく向上させる。
論文 参考訳（メタデータ） (2020-06-16T11:32:47Z) - Towards Deep Learning Models Resistant to Large Perturbations [0.0]
敵対的堅牢性は、機械学習アルゴリズムの必須特性であることが証明されている。
とよばれるアルゴリズムは、大きくても合理的で摂動のマグニチュードが与えられたディープニューラルネットワークのトレーニングに失敗することを示した。
論文 参考訳（メタデータ） (2020-03-30T12:03:09Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。