論文の概要: Pipeline Interventions

• arxiv url: http://arxiv.org/abs/2002.06592v2
• Date: Fri, 28 Aug 2020 19:49:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 18:24:49.085824
• Title: Pipeline Interventions
• Title（参考訳）: パイプライン干渉
• Authors: Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani
• Abstract要約: 本稿では, 層状有向非巡回グラフと連続層間の遷移を規定する行列の集合によって定義されるエンフェペリン介入問題について述べる。 このグラフは、異なる人口の人々が機会を提供する方法のスタイル化されたモデルであり、最終的には何らかの報酬をもたらす。 我々は、社会福祉と、最も高い期待値の人口に対する価値を最大化しようとする公正なモチベーションの最大化という2つの目的を考察する。
• 参考スコア（独自算出の注目度）: 15.27567660320295
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the \emph{pipeline intervention} problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e. some node in the first layer of the graph) according to a fixed probability distribution, and then stochastically progress through the graph according to the transition matrices, until they reach a node in the final layer of the graph; each node in the final layer has a \emph{reward} associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people's stochastic transitions through the graph, subject to a budget constraint. We consider two objectives: social welfare maximization, and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the \emph{least} expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive FPTAS) for constant width networks. We also tightly characterize the "price of fairness" in our setting: the ratio between the highest achievable social welfare and the highest social welfare consistent with a maximin optimal solution. Finally we show that for polynomial width networks, even approximating the maximin objective to any constant factor is NP hard, even for networks with constant depth. This shows that the restriction on the width in our positive results is essential.
• Abstract（参考訳）: 階層化有向非巡回グラフと連続する層間の遷移を管理する確率行列の集合によって定義される, \emph{pipeline intervention}問題を導入する。 このグラフは、異なる人口の人々が機会を提供する方法のスタイル化されたモデルであり、最終的には何らかの報酬をもたらす。 我々のモデルでは、個人は、固定された確率分布に従って初期位置(すなわち、グラフの第1層のノード)に生まれ、その後、遷移行列に従って、グラフの最終層のノードに到達するまで、そのグラフを確率的に進行する。 パイプラインの介入問題は、予算の制約の下で、人々の確率的遷移を管理する遷移行列に対して、どのように最もコストのかかる変更を行うかを問う。 我々は、社会福祉の最大化と、人口に対する価値(開始ノード)を期待値で最大化しようとする公正動機の最大化という2つの目的を考察する。 決定論的解を求めるか、ランダム化を許すかによって、極大目的の2つの変種を区別できると考える。 各目的に対して、一定幅ネットワークに対する効率的な近似アルゴリズム(加算FPTAS)を提案する。 また, 達成可能な社会福祉の最大値と, 最適解と一致した社会福祉の最高値との比率を, 設定において「公正の価格」を強く特徴づける。 最後に、多項式幅ネットワークにおいて、任意の定数係数に対して最大目的を近似するさえも、一定深さのネットワークであってもNP困難であることを示す。 これは、ポジティブな結果の幅の制限が不可欠であることを示している。

関連論文リスト

• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。 観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。 さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
  論文  参考訳（メタデータ） (2024-06-18T12:16:00Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Graph Neural Network Surrogates of Fair Graph Filtering [13.854091527965297]
  後続目的に対するフィルタ対応ユニバーサル近似フレームワークを提案する。 これにより、実行時にトレーニングされた適切なグラフニューラルネットワークが、フィルタと同じようなものになる。 私たちは、パリティ制約を満たす際の代替手段よりも、我々のアプローチが等しく良いか、あるいは優れていることを示しています。
  論文  参考訳（メタデータ） (2023-03-14T18:14:40Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• High-dimensional limit theorems for SGD: Effective dynamics and critical scaling [6.950316788263433]
  我々は、勾配降下(SGD)の要約統計の軌跡に対する極限定理を証明する。 下記の有効弾道力学が人口減少の勾配流と一致するステップサイズにおける重要なスケーリング体制を示す。 この実効力学の固定点について、対応する拡散極限は極めて複雑であり、さらに退化することもある。
  論文  参考訳（メタデータ） (2022-06-08T17:42:18Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Biased Edge Dropout for Enhancing Fairness in Graph Representation Learning [14.664485680918725]
  本稿では,グラフ表現学習における公平性向上と相反するバイアスド・エッジ・ドロップアウトアルゴリズム(fairdrop)を提案する。 FairDropは、多くの既存のアルゴリズムに簡単に接続でき、効率的で適応可能で、他の公平性誘導ソリューションと組み合わせることができます。 提案手法は,すべてのモデルのフェアネスを小さく,あるいは無視可能な精度低下まで改善できることを実証する。
  論文  参考訳（メタデータ） (2021-04-29T08:59:36Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback [15.533908352376853]
  影響カスケードによって到達されるノードの期待数を最大化する$k$ノードのセットを探します。 適応性ギャップは $lceil nrceil $ で上界であることを示し、$n$ はグラフ内のノード数である。 また、0-有界グラフ、すなわち無向グラフにおいて、適応性ギャップは少なくとも$frac3e3e3-1approx 3.16$であることを示す。
  論文  参考訳（メタデータ） (2020-06-27T14:43:34Z)

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

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