論文の概要: Fair Representation Clustering with Several Protected Classes
- arxiv url: http://arxiv.org/abs/2202.01391v1
- Date: Thu, 3 Feb 2022 03:45:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-04 14:45:09.782848
- Title: Fair Representation Clustering with Several Protected Classes
- Title（参考訳）: いくつかの保護クラスによる公正表現クラスタリング
- Authors: Zhen Dai, Yury Makarychev, Ali Vakilian
- Abstract要約: 我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
- 参考スコア（独自算出の注目度）: 13.53362222844008
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of fair $k$-median where each cluster is required to
have a fair representation of individuals from different groups. In the fair
representation $k$-median problem, we are given a set of points $X$ in a metric
space. Each point $x\in X$ belongs to one of $\ell$ groups. Further, we are
given fair representation parameters $\alpha_j$ and $\beta_j$ for each group
$j\in [\ell]$. We say that a $k$-clustering $C_1, \cdots, C_k$ fairly
represents all groups if the number of points from group $j$ in cluster $C_i$
is between $\alpha_j |C_i|$ and $\beta_j |C_i|$ for every $j\in[\ell]$ and
$i\in [k]$. The goal is to find a set $\mathcal{C}$ of $k$ centers and an
assignment $\phi: X\rightarrow \mathcal{C}$ such that the clustering defined by
$(\mathcal{C}, \phi)$ fairly represents all groups and minimizes the
$\ell_1$-objective $\sum_{x\in X} d(x, \phi(x))$.
We present an $O(\log k)$-approximation algorithm that runs in time
$n^{O(\ell)}$. Note that the known algorithms for the problem either (i)
violate the fairness constraints by an additive term or (ii) run in time that
is exponential in both $k$ and $\ell$. We also consider an important special
case of the problem where $\alpha_j = \beta_j = \frac{f_j}{f}$ and $f_j, f \in
\mathbb{N}$ for all $j\in [\ell]$. For this special case, we present an $O(\log
k)$-approximation algorithm that runs in $(kf)^{O(\ell)}\log n + poly(n)$ time.
- Abstract（参考訳）: 我々は、各クラスタが異なるグループの個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
公正表現 $k$-median 問題では、計量空間において点のセット $x$ が与えられる。
各点 $x\in x$ は $\ell$ グループに属する。
さらに、各群 $j\in [\ell]$ に対して、フェア表現パラメータ $\alpha_j$ と $\beta_j$ が与えられる。
a $k$-clustering $C_1, \cdots, C_k$ が全ての群を表すのは、群 $j$ in cluster $C_i$ が $\alpha_j |C_i|$ と $\beta_j |C_i|$ の間にあるときである。
その目的は、$(\mathcal{c}, \phi)$ で定義されるクラスタリングがすべての群を表し、$\ell_1$-objective $\sum_{x\in x} d(x, \phi(x))$ を最小化するような、$\phi: x\rightarrow \mathcal{c}$ と$\phi: x\rightarrow \mathcal{c}$ を見つけることである。
我々は、$n^{o(\ell)}$で実行される$o(\log k)$近似アルゴリズムを示す。
この問題の既知のアルゴリズムについても注意。
(i)不公平の制約を付加項で破る、又は
(ii)$k$と$\ell$の両方で指数関数的な時間で実行する。
また、すべての$j\in [\ell]$に対して、$\alpha_j = \beta_j = \frac{f_j}{f}$ と $f_j, f \in \mathbb{N}$ が問題の重要な特別な場合を考える。
この特別な場合には、$(kf)^{o(\ell)}\log n + poly(n)$ timeで実行される$o(\log k)$近似アルゴリズムを示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。
私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
論文 参考訳（メタデータ） (2024-05-16T18:17:44Z) - Approximation Algorithms for Fair Range Clustering [14.380145034918158]
本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。
目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。
特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
論文 参考訳（メタデータ） (2023-06-11T21:18:40Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。
これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文 参考訳（メタデータ） (2021-11-08T20:18:10Z) - FPT Approximation for Socially Fair Clustering [0.38073142980733]
距離関数 $d(.,.)$ を持つ距離空間 $mathcalX$ において点の集合 $P$ が与えられる。
社会的に公正な$k$-median問題の目標は、すべてのグループに対する最大平均コストを最小限に抑える、セットの$CサブセットF$ of $k$センターを見つけることである。
本研究では、社会的に公正な$k$-medianと$k$-meansに対する$(5+varepsilon)$と$(33+varepsilon)$近似アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-12T11:53:18Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。