論文の概要: Fair Correlation Clustering

• arxiv url: http://arxiv.org/abs/2002.02274v2
• Date: Mon, 2 Mar 2020 22:27:51 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-03 09:33:16.628384
• Title: Fair Correlation Clustering
• Title（参考訳）: 公正な相関クラスタリング
• Authors: Sara Ahmadian, Alessandro Epasto, Ravi Kumar, Mohammad Mahdian
• Abstract要約: 相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。 相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
• 参考スコア（独自算出の注目度）: 92.15492066925977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study correlation clustering under fairness constraints. Fair variants of $k$-median and $k$-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair correlation clustering under several important types of fairness constraints. Our results hinge on obtaining a fairlet decomposition for correlation clustering by introducing a novel combinatorial optimization problem. We define a fairlet decomposition with cost similar to the $k$-median cost and this allows us to obtain approximation algorithms for a wide range of fairness constraints. We complement our theoretical results with an in-depth analysis of our algorithms on real graphs where we show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.
• Abstract（参考訳）: 本稿では,正当性制約下での相関クラスタリングについて検討する。 近年,$k$-medianおよび$k$-centerクラスタリングのフェア変種が研究され,fairlet decompositionと呼ばれる概念を用いた近似アルゴリズムが提案されている。 数種類のフェアネス制約の下でフェア相関クラスタリングを行う近似アルゴリズムを求める。 その結果,新たな組合せ最適化問題を導入して,相関クラスタリングのためのフェアレット分解を得ることができた。 我々は$k$-medianコストに類似したコストでフェアレット分解を定義し、これにより幅広いフェアネス制約に対する近似アルゴリズムを得ることができる。 我々は,実グラフ上でのアルゴリズムの詳細な解析によって理論的結果を補完し,相関クラスタリングに対する公平な解は,最先端のアルゴリズム(unfair)に比べて少ないコストで得られることを示した。

関連論文リスト

• A Semidefinite Relaxation Approach for Fair Graph Clustering [1.03590082373586]
  本研究では、異なる影響原理の枠組みの中で、公正なグラフクラスタリングを導入する。 我々は、基礎となる最適化問題を近似するために半定緩和法を用いる。
  論文  参考訳（メタデータ） (2024-10-19T22:51:24Z)
• Optimal Group Fair Classifiers from Linear Post-Processing [10.615965454674901]
  本稿では,グループフェアネス基準の統一されたファミリーの下でモデルバイアスを緩和するフェア分類のためのポストプロセッシングアルゴリズムを提案する。 与えられたベースモデルの出力スコアを、(予測された)グループのメンバシップの線形結合である「公正コスト」で再計算することで、公平性を達成する。
  論文  参考訳（メタデータ） (2024-05-07T05:58:44Z)
• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。 制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
  論文  参考訳（メタデータ） (2024-01-23T07:16:32Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。 このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。 このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
  論文  参考訳（メタデータ） (2022-09-27T19:04:36Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Faster Deterministic Approximation Algorithms for Correlation Clustering and Cluster Deletion [5.584060970507507]
  相関クラスタリングは、ペアの類似性と相似性スコアに基づいてデータセットをパーティショニングするフレームワークである。 本稿では, 相関クラスタリング問題とエッジラベリング問題との新たな関係性を示す。 我々は,決定論的定数係数近似の保証を有する相関クラスタリングのための新しい近似アルゴリズムを開発し,標準線形プログラミング緩和を回避する。
  論文  参考訳（メタデータ） (2021-11-20T22:47:19Z)
• A Maximal Correlation Approach to Imposing Fairness in Machine Learning [25.773384159810234]
  我々は,情報理論の観点から,アルゴリズムフェアネスの問題を探究する。 公正度制約を表現するための最大相関フレームワークを導入し、独立性や分離性に基づく公正度基準を強制する正規化要因を導出できることを示した。 これらのアルゴリズムは, 離散データセット(COMPAS, アダルト)と連続データセット(コミュニティ, 犯罪)の両面において, スムーズなパフォーマンス・フェアネストレードオフ曲線を提供し, 最先端の手法と競合することを示す。
  論文  参考訳（メタデータ） (2020-12-30T18:15:05Z)

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

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