論文の概要: Fair Clustering Under a Bounded Cost
- arxiv url: http://arxiv.org/abs/2106.07239v1
- Date: Mon, 14 Jun 2021 08:47:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-15 15:34:50.739840
- Title: Fair Clustering Under a Bounded Cost
- Title（参考訳）: 境界コスト下での公平なクラスタリング
- Authors: Seyed A. Esmaeili, Brian Brubach, Aravind Srinivasan, John P.
Dickerson
- Abstract要約: クラスタリングは、データセットをメトリクス空間内の近くのポイントで構成されるクラスタに分割する、基本的な教師なしの学習問題である。
最近の変種であるフェアクラスタリング(英語版)は、各点とその群のメンバーシップを表す色を関連付け、各色が群フェアネスを満たすために各クラスタに等しい表現(およそ)を持つことを要求する。
我々は,集団の実用的目的と集団の平等的目的,および集団の平等的目的を一般化するグループ・レキシミン的目的の2つの公正性を考察する。
- 参考スコア（独自算出の注目度）: 33.50262066253557
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a fundamental unsupervised learning problem where a dataset is
partitioned into clusters that consist of nearby points in a metric space. A
recent variant, fair clustering, associates a color with each point
representing its group membership and requires that each color has
(approximately) equal representation in each cluster to satisfy group fairness.
In this model, the cost of the clustering objective increases due to enforcing
fairness in the algorithm. The relative increase in the cost, the ''price of
fairness,'' can indeed be unbounded. Therefore, in this paper we propose to
treat an upper bound on the clustering objective as a constraint on the
clustering problem, and to maximize equality of representation subject to it.
We consider two fairness objectives: the group utilitarian objective and the
group egalitarian objective, as well as the group leximin objective which
generalizes the group egalitarian objective. We derive fundamental lower bounds
on the approximation of the utilitarian and egalitarian objectives and
introduce algorithms with provable guarantees for them. For the leximin
objective we introduce an effective heuristic algorithm. We further derive
impossibility results for other natural fairness objectives. We conclude with
experimental results on real-world datasets that demonstrate the validity of
our algorithms.
- Abstract（参考訳）: クラスタリングは、データセットをメトリクス空間内の近くのポイントで構成されるクラスタに分割する、基本的な教師なし学習問題である。
最近の変種であるフェアクラスタリング(fair clustering)は、その色とそのグループメンバーシップを表す各点を関連付け、各色がグループフェアネスを満たすために各クラスタに(ほぼ)等しい表現を持つ必要がある。
このモデルでは, クラスタリング目標のコストは, アルゴリズムの公平性によって増大する。
コストの相対的な増加である「公正の価格」は、実際には非有界である。
そこで本稿では,クラスタリング問題に対する制約として,クラスタリング対象の上限を扱い,それに基づく表現の等式を最大化することを提案する。
我々は,2つの公平性目標,すなわち,グループ実用性目標とグループ平等性目標,およびグループ平等性目標を一般化するグループレキシミン目標を考える。
我々は、実用的および平等主義的目的の近似に関する根本的な下限を導き、証明可能な保証付きアルゴリズムを導入する。
レキシミンの目的のために、有効なヒューリスティックアルゴリズムを導入する。
我々はさらに、他の自然の公平性目標に対する不可能性結果も導出する。
提案アルゴリズムの有効性を実証する実世界のデータセットに関する実験結果について結論付けた。
関連論文リスト
- Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳（メタデータ） (2024-09-24T08:59:51Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Fair Labeled Clustering [28.297893914525517]
クラスタリングのダウンストリーム適用と,そのような設定に対してグループフェアネスをどのように確保するかを検討する。
このような問題に対するアルゴリズムを提供し、グループフェアクラスタリングにおけるNPハードのアルゴリズムとは対照的に、効率的な解が可能であることを示す。
また、距離空間における中心位置に関係なく、意思決定者が自由にクラスタにラベルを割り当てることができるような、モチベーションのよい代替設定についても検討する。
論文 参考訳（メタデータ） (2022-05-28T07:07:12Z) - Feature-based Individual Fairness in k-Clustering [14.847868952138795]
公平性の制約を確保しつつ一組の点をクラスタリングする問題を考察する。
我々は、必ずしもクラスタリングに使用されない特徴に基づいて、kクラスタリングにおける個別の公平性という新しい概念を導入する。
論文 参考訳（メタデータ） (2021-09-09T20:42:02Z) - You Never Cluster Alone [150.94921340034688]
我々は、主流のコントラスト学習パラダイムをクラスタレベルのスキームに拡張し、同じクラスタに属するすべてのデータが統一された表現に寄与する。
分類変数の集合をクラスタ化代入信頼度として定義し、インスタンスレベルの学習トラックとクラスタレベルの学習トラックを関連付ける。
代入変数を再パラメータ化することで、TCCはエンドツーエンドでトレーニングされる。
論文 参考訳（メタデータ） (2021-06-03T14:59:59Z) - Deep Fair Discriminative Clustering [24.237000220172906]
2値および多状態保護状態変数(PSV)に対するグループレベルの公正性の一般概念について検討する。
本稿では,クラスタリング目標とフェアネス目標とを組み合わせて,フェアクラスタを適応的に学習する改良学習アルゴリズムを提案する。
本フレームワークは, フレキシブルフェアネス制約, マルチステートPSV, 予測クラスタリングなど, 新規なクラスタリングタスクに対して有望な結果を示す。
論文 参考訳（メタデータ） (2021-05-28T23:50:48Z) - MultiFair: Multi-Group Fairness in Machine Learning [52.24956510371455]
機械学習におけるマルチグループフェアネスの研究(MultiFair)
この問題を解決するために,汎用的なエンドツーエンドのアルゴリズムフレームワークを提案する。
提案するフレームワークは多くの異なる設定に一般化可能である。
論文 参考訳（メタデータ） (2021-05-24T02:30:22Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Probabilistic Fair Clustering [31.628993679745292]
フェアクラスタリングにおける以前の仕事は、グループメンバーシップの完全な知識を前提としている。
近似比を保証したより一般的な設定でクラスタリングアルゴリズムを提案する。
また、異なる群が順序と距離の概念を持つ「計量的メンバーシップ」の問題にも対処する。
論文 参考訳（メタデータ） (2020-06-19T01:34:21Z) - Fair Hierarchical Clustering [92.03780518164108]
従来のクラスタリングにおける過剰表現を緩和する公平性の概念を定義する。
我々のアルゴリズムは、目的に対して無視できない損失しか持たない、公平な階層的なクラスタリングを見つけることができることを示す。
論文 参考訳（メタデータ） (2020-06-18T01:05:11Z) - A Notion of Individual Fairness for Clustering [22.288902523866867]
フェア機械学習における一般的な区別は、特にフェア分類において、グループフェアネスと個人フェアネスの区別である。
本稿では,クラスタリングにおける個別の公正性という自然な概念を提案する。この概念は,クラスタ内の各点が,他のクラスタの点よりも平均的に,自身のクラスタ内の点に近いことを問うものである。
論文 参考訳（メタデータ） (2020-06-08T21:41:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。