論文の概要: Fair Disaster Containment via Graph-Cut Problems
- arxiv url: http://arxiv.org/abs/2106.05424v1
- Date: Wed, 9 Jun 2021 22:52:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-11 14:06:47.038158
- Title: Fair Disaster Containment via Graph-Cut Problems
- Title（参考訳）: グラフカット問題による公平な災害封じ込め
- Authors: Amy Babay, Michael Dinitz, Prathyush Sambaturu, Aravind Srinivasan,
Leonidas Tsepenekas, Anil Vullikanti
- Abstract要約: アルゴリズム設計と機械学習におけるグラフカット問題に対する公平性について検討する。
具体的には、人口統計学と確率論的個人公正という、2つの異なる公正の定義を取り入れる。
我々の結果は、証明可能な理論的保証を持つ様々な近似アルゴリズムを含む。
- 参考スコア（独自算出の注目度）: 16.755292230626168
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph cut problems form a fundamental problem type in combinatorial
optimization, and are a central object of study in both theory and practice. In
addition, the study of fairness in Algorithmic Design and Machine Learning has
recently received significant attention, with many different notions proposed
and analyzed in a variety of contexts. In this paper we initiate the study of
fairness for graph cut problems by giving the first fair definitions for them,
and subsequently we demonstrate appropriate algorithmic techniques that yield a
rigorous theoretical analysis. Specifically, we incorporate two different
definitions of fairness, namely demographic and probabilistic individual
fairness, in a particular cut problem modeling disaster containment scenarios.
Our results include a variety of approximation algorithms with provable
theoretical guarantees.
- Abstract（参考訳）: グラフカット問題は組合せ最適化の基本的な問題タイプを形成し、理論と実践の両方において中心的な研究対象となっている。
さらに、アルゴリズム設計と機械学習における公正性の研究は、最近、様々な文脈において多くの異なる概念が提案され分析され、大きな注目を集めている。
本稿では, グラフ切断問題に対する公平性について, 最初の公正な定義を与えて検討し, 厳密な理論的解析をもたらす適切なアルゴリズム手法を実証する。
具体的には、人口統計学と確率論的個人公正という2つの異なるフェアネスの定義を、特定のカット問題モデリング災害封じ込めシナリオに取り入れる。
我々の結果は、証明可能な理論的保証を持つ様々な近似アルゴリズムを含む。
関連論文リスト
- A Semidefinite Relaxation Approach for Fair Graph Clustering [1.03590082373586]
本研究では、異なる影響原理の枠組みの中で、公正なグラフクラスタリングを導入する。
我々は、基礎となる最適化問題を近似するために半定緩和法を用いる。
論文 参考訳（メタデータ） (2024-10-19T22:51:24Z) - Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案する。
アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
論文 参考訳（メタデータ） (2024-05-18T17:38:25Z) - A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and
Future Directions [64.84521350148513]
グラフは、現実世界の無数に存在する相互接続構造を表す。
グラフ学習方法のような効果的なグラフ分析により、ユーザはグラフデータから深い洞察を得ることができる。
しかし、これらの手法はデータ不均衡に悩まされることが多く、グラフデータでは、あるセグメントが豊富なデータを持っているのに、他のセグメントが不足しているのが一般的な問題である。
これは、より正確で代表的な学習結果のために、これらのデータ分散スキューを補正することを目的として、グラフ上の不均衡学習の出現する分野を必要とする。
論文 参考訳（メタデータ） (2023-08-26T09:11:44Z) - Multivariate Systemic Risk Measures and Computation by Deep Learning
Algorithms [63.03966552670014]
本稿では,主観的最適度と関連するリスク割り当ての公平性に着目し,重要な理論的側面について論じる。
私たちが提供しているアルゴリズムは、予備項の学習、二重表現の最適化、およびそれに対応する公正なリスク割り当てを可能にします。
論文 参考訳（メタデータ） (2023-02-02T22:16:49Z) - Learning node embeddings via summary graphs: a brief theoretical
analysis [55.25628709267215]
グラフ表現学習は多くのグラフマイニングアプリケーションにおいて重要な役割を果たすが、大規模なグラフの埋め込みを学習することは依然として問題である。
最近の研究は、グラフの要約(つまり、より小さな要約グラフへの埋め込みを学習し、元のグラフのノード埋め込みを復元することでスケーラビリティを向上させる。
本稿では,導入したカーネル行列に基づく3つの特定の埋め込み学習手法について,詳細な理論的解析を行う。
論文 参考訳（メタデータ） (2022-07-04T04:09:50Z) - A Survey on Fairness for Machine Learning on Graphs [2.3326951882644553]
この調査は、リレーショナルデータに対する公平性に特化した最初の調査である。
グラフマイニングの公正性において、最先端技術に関する包括的なレビューを提示することを目的としている。
論文 参考訳（メタデータ） (2022-05-11T10:40:56Z) - Explaining Algorithmic Fairness Through Fairness-Aware Causal Path
Decomposition [37.823248189626014]
本稿では,モデルの相違点の同定問題について検討する。
特徴重要度を学習する既存の解釈方法とは異なり,特徴変数間の因果関係を考察する。
我々のフレームワークはまた、モデルに依存しないものであり、様々な量的格差の尺度に適用できる。
論文 参考訳（メタデータ） (2021-08-11T17:23:47Z) - Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
本稿では,より広い範囲の最適化問題を含むサドル点問題に対して,PFLを初めて検討した。
この問題に対処するための新しいアルゴリズムを提案し、滑らかな(強く)凸-(強く)凹点問題を理論的に解析する。
両線形問題に対する数値実験と, 対向雑音を有するニューラルネットワークは, 提案手法の有効性を実証する。
論文 参考訳（メタデータ） (2021-06-14T10:36:25Z) - All of the Fairness for Edge Prediction with Optimal Transport [11.51786288978429]
グラフにおけるエッジ予測の課題に対する公平性の問題について検討する。
本稿では,任意のグラフの隣接行列に対して,グループと個々の公正性のトレードオフを伴う埋め込み非依存の補修手順を提案する。
論文 参考訳（メタデータ） (2020-10-30T15:33:13Z) - A Theory of Multiple-Source Adaptation with Limited Target Labeled Data [66.53679520072978]
モデル選択のアイデアに基づく新しいアルゴリズムのファミリーは,このシナリオにおいて非常に望ましい保証から恩恵を受けることを示す。
また,本アルゴリズムの実用性を示すいくつかの実験結果についても報告する。
論文 参考訳（メタデータ） (2020-07-19T19:34:48Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳（メタデータ） (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。