論文の概要: Fair Polylog-Approximate Low-Cost Hierarchical Clustering
- arxiv url: http://arxiv.org/abs/2311.12501v1
- Date: Tue, 21 Nov 2023 10:20:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 01:05:54.237968
- Title: Fair Polylog-Approximate Low-Cost Hierarchical Clustering
- Title（参考訳）: fair polylog-approximate 階層クラスタリング
- Authors: Marina Knittel, Max Springer, John Dickerson, MohammadTaghi Hajiaghayi
- Abstract要約: 公正な機械学習、特にクラスタリングの研究は、現代のインテリジェントシステムが提起した多くの倫理的論争から、近年重要になっている。
そこで,本研究では,真に多元論的に近似した低コストな階層クラスタリングを提案する。
- 参考スコア（独自算出の注目度）: 14.088810363740208
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Research in fair machine learning, and particularly clustering, has been
crucial in recent years given the many ethical controversies that modern
intelligent systems have posed. Ahmadian et al. [2020] established the study of
fairness in \textit{hierarchical} clustering, a stronger, more structured
variant of its well-known flat counterpart, though their proposed algorithm
that optimizes for Dasgupta's [2016] famous cost function was highly
theoretical. Knittel et al. [2023] then proposed the first practical fair
approximation for cost, however they were unable to break the
polynomial-approximate barrier they posed as a hurdle of interest. We break
this barrier, proposing the first truly polylogarithmic-approximate low-cost
fair hierarchical clustering, thus greatly bridging the gap between the best
fair and vanilla hierarchical clustering approximations.
- Abstract（参考訳）: 現代のインテリジェントなシステムが生み出した多くの倫理的な議論を考えると、公正な機械学習、特にクラスタリングの研究は近年重要になっている。
アフマド人など。
2020年]ダスガプタの[2016]有名なコスト関数を最適化するアルゴリズムは、非常に理論的であったものの、有名なフラット関数のより強固で構造化された変種である \textit{hierarchical}クラスタリングにおける公平性の研究を確立した。
クニッテルとアル。
2023] では, コストに対する最初の実用的公平な近似を提案したが, 利害のハードルとなる多項式近似障壁を破ることができなかった。
この障壁を破って、最初の真の多対数近似のフェア階層的クラスタリングを提案し、最良のフェアとバニラ階層的クラスタリングのギャップを大きく橋渡しします。
関連論文リスト
- 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) - Robust Fair Clustering: A Novel Fairness Attack and Defense Framework [33.87395800206783]
フェアクラスタリングアルゴリズムに対する新しいブラックボックスフェアネス攻撃を提案する。
我々は、最先端のモデルが我々の攻撃に非常に影響を受けやすいことを発見した。
また,最初のロバストなフェアクラスタリング手法であるConsensus Fair Clustering (CFC)を提案する。
論文 参考訳（メタデータ） (2022-10-04T23:00:20Z) - Generalized Reductions: Making any Hierarchical Clustering Fair and
Balanced with Low Cost [30.815665515439598]
私たちは階層的クラスタリングの文脈で公平性を研究する最初の人です。
階層内の任意のレベルにわたって、公平性とクラスタバランスを保証するために、既存の階層的なクラスタリングを変更する方法を示す。
論文 参考訳（メタデータ） (2022-05-27T19:04:00Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Uniform Concentration Bounds toward a Unified Framework for Robust
Clustering [21.789311405437573]
センターベースのクラスタリングの最近の進歩は、ロイドの有名な$k$-meansアルゴリズムの欠点によって改善され続けている。
様々な手法は、ローカル・ミニマ(英語版)の貧弱さ、異常値に対する感度、ユークリッドの対応に適さないデータに対処しようとする。
本稿では,一般的な相似性尺度に基づく中心クラスタリングのための密結合型ロバストフレームワークを提案する。
論文 参考訳（メタデータ） (2021-10-27T03:43:44Z) - Efficient Algorithms For Fair Clustering with a New Fairness Notion [5.21410307583181]
我々は、Chierichettiらによって最初に導入されたフェアクラスタリングの問題を再考する。
既存のクラスタリングのソリューションはスケーラビリティが低いか、クラスタリングの目的と公平性のトレードオフを最適に達成できないかのいずれかです。
バランス特性を厳密に一般化し、細粒度効率とフェアネストレードオフを可能にする、$tau$-fair Fairnessと呼ばれる新しいフェアネスの概念を提案する。
論文 参考訳（メタデータ） (2021-09-02T04:52:49Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳（メタデータ） (2021-07-05T19:20:34Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Fair Hierarchical Clustering [92.03780518164108]
従来のクラスタリングにおける過剰表現を緩和する公平性の概念を定義する。
我々のアルゴリズムは、目的に対して無視できない損失しか持たない、公平な階層的なクラスタリングを見つけることができることを示す。
論文 参考訳（メタデータ） (2020-06-18T01:05:11Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳（メタデータ） (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。