論文の概要: Efficient k-means with Individual Fairness via Exponential Tilting

• arxiv url: http://arxiv.org/abs/2406.16557v1
• Date: Mon, 24 Jun 2024 11:50:31 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-25 15:04:12.028940
• Title: Efficient k-means with Individual Fairness via Exponential Tilting
• Title（参考訳）: 指数的ティルティングによる個人の公平性を考慮した効率的なk-means
• Authors: Shengkun Zhu, Jinshan Zeng, Yuan Sun, Sheng Wang, Xiaodong Li, Zhiyong Peng,
• Abstract要約: 位置に基づくリソース割り当てのシナリオでは、全てのポイントを平等に扱うという原則を達成するために、個別に公平なクラスタリングがしばしば用いられる。 本稿では,クラスタリングにおける個別の公平性を実現することを目的とした,新しいアルゴリズムである傾きk平均(TKM)を提案する。
• 参考スコア（独自算出の注目度）: 13.72284501663574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In location-based resource allocation scenarios, the distances between each individual and the facility are desired to be approximately equal, thereby ensuring fairness. Individually fair clustering is often employed to achieve the principle of treating all points equally, which can be applied in these scenarios. This paper proposes a novel algorithm, tilted k-means (TKM), aiming to achieve individual fairness in clustering. We integrate the exponential tilting into the sum of squared errors (SSE) to formulate a novel objective function called tilted SSE. We demonstrate that the tilted SSE can generalize to SSE and employ the coordinate descent and first-order gradient method for optimization. We propose a novel fairness metric, the variance of the distances within each cluster, which can alleviate the Matthew Effect typically caused by existing fairness metrics. Our theoretical analysis demonstrates that the well-known k-means++ incurs a multiplicative error of O(k log k), and we establish the convergence of TKM under mild conditions. In terms of fairness, we prove that the variance generated by TKM decreases with a scaled hyperparameter. In terms of efficiency, we demonstrate the time complexity is linear with the dataset size. Our experiments demonstrate that TKM outperforms state-of-the-art methods in effectiveness, fairness, and efficiency.
• Abstract（参考訳）: 位置情報に基づく資源配分のシナリオでは、各個人と施設間の距離がほぼ等しくなり、公平性を確保することが望まれる。 個別に公平なクラスタリングは、これらのシナリオに適用可能な全ての点を平等に扱うという原則を達成するためにしばしば用いられる。 本稿では,クラスタリングにおける個別の公平性を実現することを目的とした,新しいアルゴリズムである傾きk平均(TKM)を提案する。 我々は指数傾斜を2乗誤差の和(SSE)に統合し、傾きSSEと呼ばれる新しい目的関数を定式化する。 本研究では,傾いたSSEをSSEに一般化し,座標勾配法と一階勾配法を用いて最適化できることを実証する。 本稿では,各クラスタ内の距離の分散である新しいフェアネス尺度を提案し,既存のフェアネス指標によって引き起こされるマシュー効果を緩和する。 我々の理論的解析は、よく知られたk-means++がO(k log k)の乗法誤差を生じ、穏やかな条件下でTKMの収束を確立することを証明している。 公平性の観点からは、TKMによって生じる分散はスケールされたハイパーパラメータによって減少することを示す。 効率の面では、データセットのサイズと時間複雑性が線形であることを示します。 実験の結果,TKMは有効性,公平性,効率性において最先端の手法よりも優れていた。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Dataless Quadratic Neural Networks for the Maximum Independent Set Problem [23.643727259409744]
  pCQO-MISはエッジ数ではなくグラフ内のノード数でスケールすることを示す。 提案手法は,分散の排除,サンプリング,データ中心のアプローチを回避する。
  論文  参考訳（メタデータ） (2024-06-27T21:12:48Z)
• Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
  異種データを用いた因果推論のための協調的逆確率スコア推定器を提案する。 異質性の増加に伴うメタアナリシスに基づく手法に対して,本手法は有意な改善を示した。
  論文  参考訳（メタデータ） (2024-04-24T09:04:36Z)
• Imbalanced Data Clustering using Equilibrium K-Means [1.0878040851638]
  セントロイドベースのクラスタリングアルゴリズムは、大規模なクラスタに対する学習バイアスに悩まされている。 本稿では,ボルツマン演算子に基づく新たなクラスタリング目的関数を提案する。 提案された新しいアルゴリズムは平衡K平均 (EKM) と呼ばれ、2つのステップ間で交互に行われる。
  論文  参考訳（メタデータ） (2024-02-22T12:27:38Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• Push--Pull with Device Sampling [8.344476599818826]
  複数のエージェントが協力して、基礎となる通信グラフを交換することで、ローカル関数の平均を最小化する分散最適化問題を考察する。 ネットワーク全体の勾配追跡と分散低減を併用したアルゴリズムを提案する。 理論解析により,局所目的関数が強凸である場合,アルゴリズムは線形に収束することを示した。
  論文  参考訳（メタデータ） (2022-06-08T18:18:18Z)
• Metrizing Fairness [5.323439381187456]
  本研究では,2つの集団集団の個人に有意な影響を及ぼす教師付き学習問題について検討した。 我々は、統計パリティ(SP)のような群フェアネス基準に関して公正な予測子を求める。 本稿では,厳密なSP制約が保証される条件を特定し,予測精度を向上させる。
  論文  参考訳（メタデータ） (2022-05-30T12:28:10Z)
• Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
  正規化フローの微分同相性に基づいて、閉領域上の累積分布関数(CDF)を推定する。 一般的なフローアーキテクチャとUCIデータセットに関する実験は,従来の推定器と比較して,サンプル効率が著しく向上したことを示している。
  論文  参考訳（メタデータ） (2022-02-23T06:11:49Z)
• KL Guided Domain Adaptation [88.19298405363452]
  ドメイン適応は重要な問題であり、現実世界のアプリケーションにしばしば必要である。 ドメイン適応文学における一般的なアプローチは、ソースとターゲットドメインに同じ分布を持つ入力の表現を学ぶことである。 確率的表現ネットワークにより、KL項はミニバッチサンプルにより効率的に推定できることを示す。
  論文  参考訳（メタデータ） (2021-06-14T22:24:23Z)
• Manifold-adaptive dimension estimation revisited [0.0]
  多様体適応型ファラマンド-ゼーペスヴァリ-アウディベルト次元推定器を再検討し改善する。 局所的なFSA推定値の確率密度関数を計算する。 大域的内在次元の最大公算式を導出する。
  論文  参考訳（メタデータ） (2020-08-07T15:27:26Z)

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

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