論文の概要: Scalable Spectral Clustering with Group Fairness Constraints
- arxiv url: http://arxiv.org/abs/2210.16435v1
- Date: Fri, 28 Oct 2022 23:23:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 15:47:51.261093
- Title: Scalable Spectral Clustering with Group Fairness Constraints
- Title(参考訳): グループフェアネス制約付きスケーラブルスペクトルクラスタリング
- Authors: Ji Wang, Ding Lu, Zhaojun Bai and Ian Davidson
- Abstract要約: スペクトルクラスタリング(SC)のためのスケーラブルアルゴリズムを提案する。
群フェアネス(英: group fairness)は統計パリティ(英: statistics parity)としても知られ、各クラスタにおいて、各保護群は全体と同じ割合で表される。
- 参考スコア(独自算出の注目度): 24.543118404418035
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There are synergies of research interests and industrial efforts in modeling
fairness and correcting algorithmic bias in machine learning. In this paper, we
present a scalable algorithm for spectral clustering (SC) with group fairness
constraints. Group fairness is also known as statistical parity where in each
cluster, each protected group is represented with the same proportion as in the
entirety. While FairSC algorithm (Kleindessner et al., 2019) is able to find
the fairer clustering, it is compromised by high costs due to the kernels of
computing nullspaces and the square roots of dense matrices explicitly. We
present a new formulation of underlying spectral computation by incorporating
nullspace projection and Hotelling's deflation such that the resulting
algorithm, called s-FairSC, only involves the sparse matrix-vector products and
is able to fully exploit the sparsity of the fair SC model. The experimental
results on the modified stochastic block model demonstrate that s-FairSC is
comparable with FairSC in recovering fair clustering. Meanwhile, it is sped up
by a factor of 12 for moderate model sizes. s-FairSC is further demonstrated to
be scalable in the sense that the computational costs of s-FairSC only increase
marginally compared to the SC without fairness constraints.
- Abstract(参考訳): 公正性をモデル化し、機械学習におけるアルゴリズムバイアスを補正する研究と産業の努力の相乗効果がある。
本稿では,グループフェアネス制約付きスペクトルクラスタリング(SC)のためのスケーラブルアルゴリズムを提案する。
群フェアネスは統計パリティとしても知られ、各クラスタにおいて、各保護群は全体と同じ割合で表される。
FairSCアルゴリズム (Kleindessner et al., 2019) はより公平なクラスタリングを見つけることができるが、計算ヌルスペースのカーネルや密度行列の平方根が明確に定義されているため、高いコストで妥協される。
本稿では, ヌルスペース射影とHotellingのデフレを取り入れたスペクトル計算の新たな定式化を行い, 結果のアルゴリズムであるs-FairSCは, スパース行列ベクトル積のみを伴い, フェアSCモデルの空間性を完全に活用できることを示す。
修正確率ブロックモデルの実験的結果から, s-fairsc は fairsc と同等であることが判明した。
一方、中程度のモデルサイズでは12倍に高速化される。
また, s-fairsc の計算コストは, 公平性制約を伴わない sc と比較してわずかに増大する程度である。
関連論文リスト
- Semantic Equitable Clustering: A Simple, Fast and Effective Strategy for Vision Transformer [57.37893387775829]
textbfSemantic textbfEquitable textbfClustering (SEC) という,高速かつバランスの取れたクラスタリング手法を導入する。
SECは、グローバルなセマンティックな関連性に基づいてトークンを効率的かつ直接的な方法でクラスタ化する。
我々は、textbf27Mパラメータと textbf4.4G FLOPs のみを用いて、印象的な textbf84.2% 画像分類精度が得られる多用途視覚バックボーン SecViT を提案する。
論文 参考訳(メタデータ) (2024-05-22T04:49:00Z) - Fuzzy K-Means Clustering without Cluster Centroids [79.19713746387337]
ファジィK平均クラスタリングは教師なしデータ解析において重要な計算手法である。
本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィK平均クラスタリングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-04-07T12:25:03Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Robust Fair Clustering: A Novel Fairness Attack and Defense Framework [33.87395800206783]
フェアクラスタリングアルゴリズムに対する新しいブラックボックスフェアネス攻撃を提案する。
我々は、最先端のモデルが我々の攻撃に非常に影響を受けやすいことを発見した。
また,最初のロバストなフェアクラスタリング手法であるConsensus Fair Clustering (CFC)を提案する。
論文 参考訳(メタデータ) (2022-10-04T23:00:20Z) - Local Sample-weighted Multiple Kernel Clustering with Consensus
Discriminative Graph [73.68184322526338]
マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。
本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。
実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
論文 参考訳(メタデータ) (2022-07-05T05:00:38Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Efficient Algorithms For Fair Clustering with a New Fairness Notion [5.21410307583181]
我々は、Chierichettiらによって最初に導入されたフェアクラスタリングの問題を再考する。
既存のクラスタリングのソリューションはスケーラビリティが低いか、クラスタリングの目的と公平性のトレードオフを最適に達成できないかのいずれかです。
バランス特性を厳密に一般化し、細粒度効率とフェアネストレードオフを可能にする、$tau$-fair Fairnessと呼ばれる新しいフェアネスの概念を提案する。
論文 参考訳(メタデータ) (2021-09-02T04:52:49Z) - Deep Fair Discriminative Clustering [24.237000220172906]
2値および多状態保護状態変数(PSV)に対するグループレベルの公正性の一般概念について検討する。
本稿では,クラスタリング目標とフェアネス目標とを組み合わせて,フェアクラスタを適応的に学習する改良学習アルゴリズムを提案する。
本フレームワークは, フレキシブルフェアネス制約, マルチステートPSV, 予測クラスタリングなど, 新規なクラスタリングタスクに対して有望な結果を示す。
論文 参考訳(メタデータ) (2021-05-28T23:50:48Z) - Socially Fair k-Means Clustering [3.3409719900340256]
我々は、異なるグループに対して公平なコストを提供するクラスタセンターを選択するための、公平なk平均目標とアルゴリズムを提案する。
このアルゴリズムであるFair-Lloydは、ロイドのk平均に対する修正であり、その単純さ、効率、安定性を継承している。
論文 参考訳(メタデータ) (2020-06-17T18:05:17Z) - Fair Algorithms for Hierarchical Agglomerative Clustering [17.66340013352806]
Hierarchical Agglomerative Clustering (HAC)アルゴリズムは、現代のデータサイエンスで広く利用されている。
たとえデータセットが特定の保護されたグループに対するバイアスを含むとしても、これらのアルゴリズムが公平であることを保証することが不可欠である。
公平性制約を強制するHACを行うための公正アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-07T01:41:56Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳(メタデータ) (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。