論文の概要: Finding a Fair Scoring Function for Top-$k$ Selection: Hardness, Algorithms, and Experiments
- arxiv url: http://arxiv.org/abs/2503.11575v1
- Date: Fri, 14 Mar 2025 16:40:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-17 13:06:55.325072
- Title: Finding a Fair Scoring Function for Top-$k$ Selection: Hardness, Algorithms, and Experiments
- Title（参考訳）: 上位k$選択のための公正なスコーリング関数の探索:硬さ、アルゴリズム、実験
- Authors: Guangya Cai,
- Abstract要約: ここでは, 線形スコアリング関数を, 公平なトップ$k$選択に対して同定する問題を考える。
関数は各項目のスコアを(数値的な)属性値の重み付け和として計算する。
既存のアルゴリズムは大規模で高次元のデータセットに効果的にスケールしない。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Selecting a subset of the $k$ "best" items from a dataset of $n$ items, based on a scoring function, is a key task in decision-making. Given the widespread use of automated decision-making software nowadays, it is important that the outcome of this process, called top-$k$ selection, is fair. Here we consider the problem of identifying a linear scoring function for top-$k$ selection that is fair. The function computes a score for each item as a weighted sum of its (numerical) attribute values. Additionally, the function must ensure that the subset selected is a faithful representative of the entire dataset for a minority or historically disadvantaged group. Existing algorithms do not scale effectively on large, high-dimensional datasets. Our theoretical analysis shows that in more than two dimensions, no algorithm is likely to achieve good scalability with respect to dataset size (i.e., a run time of $O(n\cdot \text{polylog}(n))$), and the computational complexity is likely to increase rapidly with dimensionality. However, there are exceptions for small values of $k$ and for this case we provide significantly faster algorithms. We also provide efficient practical variants of these algorithms. Our implementations of these take advantage of modern hardware (e.g., exploiting parallelism). For large values of $k$, we give an alternative algorithm that, while theoretically worse, performs better in practice. Experimental results on real-world datasets demonstrate the efficiency of our proposed algorithms, which achieve speed-ups of up to several orders of magnitude compared to the state of the art (SoTA).
- Abstract（参考訳）: スコアリング関数に基づいて$n$アイテムのデータセットから$k$ "best"項目のサブセットを選択することは、意思決定における重要なタスクである。
近年、自動意思決定ソフトウェアが広く使われていることを考えると、このプロセスの成果であるトップ・ドル・セレクション(top-k$ selection)が公平であることが重要である。
ここでは、公平なトップ=k$選択に対する線形スコアリング関数を同定する問題を考察する。
関数は各項目のスコアを(数値的な)属性値の重み付け和として計算する。
さらに、選択されたサブセットが少数または歴史的に不利なグループのデータセット全体の忠実な代表であることを保証する必要がある。
既存のアルゴリズムは大規模で高次元のデータセットに効果的にスケールしない。
我々の理論的分析は、2次元以上の場合、データセットサイズ(すなわち、$O(n\cdot \text{polylog}(n))$)に関して優れたスケーラビリティを達成するアルゴリズムは存在しないことを示している。
しかし、$k$の小さな値には例外があり、この場合、かなり高速なアルゴリズムを提供する。
また、これらのアルゴリズムの効率的な実用的変種も提供する。
これらの実装は、現代のハードウェア(例えば、並列性を活用)を活用しています。
k$の大きい値に対して、理論的には悪いが、実際はより良い性能を示す代替アルゴリズムを与える。
実世界のデータセットによる実験結果から,提案アルゴリズムの効率性を示すとともに,最先端(SoTA)と比較して最大数桁の高速化を実現している。
関連論文リスト
- Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。
目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。
そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
論文 参考訳（メタデータ） (2025-02-13T01:27:11Z) - Approximate Top-$k$ for Increased Parallelism [1.2557921586915128]
そこで本研究では,バケット付き近似式をk$のアルゴリズムで評価する。
上位$が正確であるという要件を緩和することで、バケット付きアルゴリズムは利用可能な並列性を劇的に向上させることができる。
PyTorch用の高速なバケット付きトップ$実装もリリースしています。
論文 参考訳（メタデータ） (2024-12-05T17:17:28Z) - The Limits of Assumption-free Tests for Algorithm Performance [6.7171902258864655]
与えられたモデリングタスクにおいてアルゴリズムはどの程度うまく機能し、どのアルゴリズムが最善を尽くすか?
一方、特定のトレーニングデータセットに対して$A$を実行して生成された特定の適合モデルが$n$であるのか?
論文 参考訳（メタデータ） (2024-02-12T03:19:30Z) - Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。
提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
論文 参考訳（メタデータ） (2023-03-01T18:49:10Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Max-Min Diversification with Fairness Constraints: Exact and
Approximation Algorithms [17.57585822765145]
本稿では,小データセットに適した正確なアルゴリズムと,大データセットにスケールする任意の$varepsilon in (0, 1)$に対して$frac1-varepsilon integer 5$-approximationアルゴリズムを提案する。
実世界のデータセットに対する実験は、提案アルゴリズムが既存のデータセットよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-01-05T13:02:35Z) - Compactness Score: A Fast Filter Method for Unsupervised Feature
Selection [66.84571085643928]
本稿では,CSUFS (Compactness Score) と呼ばれる高速な教師なし特徴選択手法を提案する。
提案アルゴリズムは既存のアルゴリズムよりも正確で効率的である。
論文 参考訳（メタデータ） (2022-01-31T13:01:37Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - An Efficient $k$-modes Algorithm for Clustering Categorical Datasets [8.528384027684194]
我々は, OTQT と呼ばれる$k$-modes の斬新で効率的な実装を提供する。
OTQTは既存の$k$-modesアルゴリズムでは検出不可能な目的関数を改善するために更新されていることを証明している。
OTQTはイテレーション毎に常に正確で、最終最適化までほぼ常に高速である(一部のデータセットではわずかに遅い)。
論文 参考訳（メタデータ） (2020-06-06T18:41:36Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。