論文の概要: Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
- arxiv url: http://arxiv.org/abs/2503.11575v2
- Date: Wed, 11 Jun 2025 20:39:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-13 15:37:22.199389
- Title: Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
- Title（参考訳）: 最高価格選択のための公正なスコーリング関数の発見:ハードネスから練習へ
- Authors: Guangya Cai,
- Abstract要約: 我々は、上位k$選択のための公平な線形スコアリング関数を同定する問題に対処する。
既存のアルゴリズムは特に高次元において効率的にスケールしない。
我々の解はSOTAと比較して最大数桁のスピードアップを達成する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- 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 rise of automated decision-making software, it is important that the outcome of this process, called top-$k$ selection, is fair. Here we consider the problem of identifying a fair linear scoring function for top-$k$ selection. The function computes a score for each item as a weighted sum of its (numerical) attribute values, and must ensure that the selected subset includes adequate representation of a minority or historically disadvantaged group. Existing algorithms do not scale efficiently, particularly in higher dimensions. Our hardness analysis shows that in more than two dimensions, no algorithm is likely to achieve good scalability with respect to dataset size, and the computational complexity is likely to increase rapidly with dimensionality. However, the hardness results also provide key insights guiding algorithm design, leading to our dual-algorithm solution: (1) For small values of $k$, our hardness analysis reveals a gap in the hardness barrier. By addressing various engineering challenges, including achieving efficient parallelism, we turn this potential of efficiency into an optimized algorithm delivering substantial practical performance gains. (2) For large values of $k$, where the hardness is robust, we employ a practically efficient algorithm which, despite being theoretically worse, achieves superior real-world performance. Experimental evaluations on real-world datasets then explore scenarios where worst-case behavior does not manifest, identifying areas critical to practical performance. Our solution achieves speed-ups of up to several orders of magnitude compared to SOTA, an efficiency made possible through a tight integration of hardness analysis, algorithm design, practical engineering, and empirical evaluation.
- Abstract（参考訳）: スコアリング関数に基づいて$n$アイテムのデータセットから$k$ "best"項目のサブセットを選択することは、意思決定における重要なタスクである。
自動意思決定ソフトウェアの台頭を考えると、このプロセスの成果がトップ$k$選択(top-$k$ selection)と呼ばれ、公正であることが重要である。
ここでは、上位k$選択のための公平な線形スコアリング関数を同定する問題を考察する。
関数は各項目のスコアを(数値的な)属性値の重み付け和として計算し、選択されたサブセットが少数あるいは歴史的に不利なグループの適切な表現を含むことを保証しなければならない。
既存のアルゴリズムは特に高次元において効率的にスケールしない。
我々の硬度分析は、2次元以上の場合、データセットサイズに関して優れたスケーラビリティを実現するアルゴリズムは存在せず、計算複雑性は次元性によって急速に増大する可能性が高いことを示している。
しかし、ハードネスの結果はまたアルゴリズム設計を導く重要な洞察を与えており、この二元アルゴリズムの解決策に繋がる: 1)k$の小さな値の場合、ハードネス分析はハードネス障壁のギャップを露呈する。
効率的な並列性を達成することを含む様々な工学的課題に対処することにより、この効率のポテンシャルを最適化されたアルゴリズムに転換し、実質的な性能向上を実現する。
2) 硬さが堅牢な大容量の$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。